admin
Tweet Share Share

Last Updated on August 15, 2020

Gradient boostingは予測モデル構築の最も強力な技術の1つである。

この投稿では、勾配ブースティング機械学習アルゴリズムを発見し、その由来と仕組みについて優しく紹介します。

  • 学習理論と AdaBoost からのブーストの由来。
  • 様々な正則化スキームで基本アルゴリズムよりパフォーマンスを向上させる方法。

私の新しい本「XGBoost With Python」でプロジェクトを始めましょう。

Let’s get started.

A Gentle Introduction to the Gradient Boosting Algorithm for Machine Learning
Photo by brando.n, some rights reserved.

Need help with XGBoost in Python?

Take my free 7-day email course and discover xgboost (with sample code).

Click to sign-up now and also get a free PDF Ebook version of the course.

Start Your free Mini-Course now!

ブーストの起源

ブーストの考え方は、弱い学習者をより良くなるように修正することができるかという考えから生まれました。

Michael Kearnsは、その目標を「Hypothesis Boosting Problem」と表現し、実用的な立場から次のように述べている。

… 比較的悪い仮説を非常に良い仮説に変換する効率的なアルゴリズム

– Thoughts on Hypothesis Boosting , 1988

弱い仮説または弱い学習者は、性能がランダムな偶然よりも少なくともわずかに良いものと定義される。

これらのアイデアは、機械学習問題の複雑さを調査するためのフレームワークである、分布のない、または PAC (Probably Approx Correct) 学習に関する Leslie Valiant の研究を基礎としています。

Hypothesis boosting は、弱い学習者が扱える観測を残し、残りの難しい観測を扱うために新しい弱い学習者の開発に集中し、観測をフィルタリングするというアイデアでした。

このアイデアは、前のものが困難と判断して誤分類した例に再集中して、それぞれが一連の仮説を得るために弱い学習方法を数回使用することです。 … ただし、これがどのように行われるかはまったく明らかではないことに注意してください

– Probably Approx Correct: Nature’s Algorithms for Learning and Prospering in a Complex World, page 152, 2013

AdaBoost 最初のブースト アルゴリズム

応用で大成功した最初のブースティングは、適応ブースト、略してAdaBoostである。

ブースティングとは、大まかで適度に不正確な経験則を組み合わせて、非常に正確な予測ルールを作成するこの一般的な問題を指します。

– A decision-theoretic generalization of on-line learning and an application to boosting , 1995

AdaBoost の弱い学習者は単一の分岐を持つ決定木で、その短さから決定スタンプと呼ばれている。 新しい弱い学習者が順次追加され、より困難なパターンに集中して学習する。

これは、アルゴリズムがこれらのサンプルを正しく分類するモデルを識別するまで、分類が困難なサンプルは、より大きな重みを受けることを意味する

– Applied Predictive Modeling, 2013

予測は、個々の精度で重み付けした弱い学習者の予測に対する多数決により作成される。 AdaBoost アルゴリズムの最も成功した形式は、バイナリ分類問題用で、AdaBoost.M1 と呼ばれていました。

AdaBoost アルゴリズムについては、

  • Boosting and AdaBoost for Machine Learning という投稿で詳しく知ることができます。

Gradient Boosting としての AdaBoost の一般化

AdaBoost および関連アルゴリズムは、まず Breiman が ARCing アルゴリズムと呼ぶ統計フレームワークに再キャストされました。 アーキング・アルゴリズムの各ステップは、加重最小化とそれに続く再計算で構成されている。 統計的なフレームワークは、ブースティングを数値最適化問題として捉え、勾配降下のような手順を用いて弱い学習器を追加することにより、モデルの損失を最小化することを目的としています。 これは、一度に1つの新しい弱い学習者が追加され、モデル内の既存の弱い学習者は凍結され、変更されないままであるからである。

この段階的戦略は、新しいものが追加されたときに以前に入力された項を再調整する段階的アプローチとは異なることに注意。

– Greedy Function Approximation:

How Gradient Boosting Works

Gradient Boosting には 3 つの要素があります。

Loss Function

使用する損失関数は、解決する問題のタイプに依存します。

これは微分可能でなければなりませんが、多くの標準的な損失関数がサポートされており、独自のものを定義することもできます。

Gradient Boosting フレームワークの利点は、使用したい損失関数ごとに新しいブースト アルゴリズムを派生させる必要がなく、代わりに、任意の微分可能損失関数が使用できる汎用フレームワークであるということです。

特に回帰木は、分割のために実際の値を出力し、その出力は一緒に追加することができ、後続のモデルの出力を追加して予測値の残差を「修正」できるように使用される。

木は貪欲に構築され、ジニなどの純度スコアに基づいて最適な分割点を選択するか、損失を最小化する。

AdaBoost の場合のように、最初は、決定スタンプと呼ばれる単一の分割のみを持つ非常に短い決定木が使用されていました。 より大きな木は、一般に 4 ～ 8 レベルで使用できる。

層、ノード、分割、または葉ノードの最大数など、特定の方法で弱い学習者を制約するのが一般的である。

Additive Model

木は一度に1つずつ追加され、モデル内の既存の木は変更されない。

勾配降下法は、木を追加するときに損失を最小にするために使われる。

伝統的に、勾配降下法は回帰式の係数やニューラルネット内の重みなどの一連のパラメータを最小化するために使われている。 エラーまたは損失を計算した後、そのエラーを最小化するように重みが更新されます。

パラメータの代わりに、弱い学習者サブモデル、より具体的には決定木が使用されます。 損失を計算した後、勾配降下手順を実行するために、損失を減らす（つまり、勾配に従う）木をモデルに追加する必要があります。 木をパラメータ化することでこれを行い、木のパラメータを修正し、（残留損失を減らすことで）正しい方向に進む。

一般にこのアプローチは、関数的勾配降下または関数付き勾配降下と呼ばれている。

最適化する分類器の重み付き組み合わせを生成する 1 つの方法は、関数空間における勾配降下

– Boosting Algorithms as Gradient Descent in Function Space , 1999

モデルの最終出力を修正または改善するために、新しい木の出力が既存の一連の木の出力に追加される。

一定の数の木が追加されるか、損失が許容レベルに達するか、外部検証データセットで改善されなくなると、学習が停止する。

Improvements to Basic Gradient Boosting

Gradient boosting は欲深いアルゴリズムで、すぐに学習データセットをオーバーフィットすることができる。

アルゴリズムのさまざまな部分にペナルティを課す正則化手法の恩恵を受けることができ、一般にオーバーフィッティングを減らすことでアルゴリズムのパフォーマンスを向上させることができます。

このセクションでは、基本的な Gradient Boosting に対する 4 つの拡張について見ていきます:

  1. Tree Constraints
  2. Shrinkage
  3. Random sampling
  4. Penalized Learning

Tree Constraints

弱い学習者はスキルを持ちながらも弱いままということが重要である。

There are a number of ways that the trees can be constrained.

A good general heuristic is that the more trees will need in the model, and the reverse, where less constrained individual trees, the fewer trees that will be required.これは、ツリー作成の制約が多いほど、モデルにより多くのツリーが必要になり、逆に制約が少ないほど、必要とされるツリーは少なくなるということである。

決定木の構築に課すことができるいくつかの制約を以下に示します:

  • 木の数、一般にモデルにさらに木を追加すると、オーバーフィットに非常に時間がかかることがあります。 アドバイスとしては、それ以上の改善が見られないまで木を追加し続けることである。
  • 木の深さ、深い木はより複雑な木であり、短い木が好まれる。 一般に、4-8レベルでより良い結果が見られる。
  • ノードの数または葉の数、深さのように、これは木のサイズを制限することができるが、他の制約が使用されている場合は、対称構造に制約されることはない。
  • Number of observations per splitは、分割が考慮される前に、学習ノードにおける学習データの量に対する最小限の制約を課す
  • Minim improvement to lossは、木に追加される任意の分割の改善に対する制約である。

2. 重み付け更新

各木の予測値は順次加算される。

この合計に対する各木の貢献度は、アルゴリズムによる学習を遅らせるために重み付けすることができる。 この重み付けは、縮小または学習率と呼ばれる。

各更新は、「学習率パラメータ v」の値によって単純にスケールされる

– 欲張り関数による近似。 学習が遅くなり、その結果、より多くの木をモデルに追加する必要があり、その結果、学習に時間がかかり、木の数と学習速度の間の構成のトレードオフが提供される。 A Gradient Boosting Machine , 1999

0.1 以下の値だけでなく、0.1 から 0.3 の範囲の小さな値を持つことが一般的である。

確率最適化の学習率と同様、縮小は個々の木の影響を減らし、将来の木のためにスペースを残してモデルを向上させることができます。

– Stochastic Gradient Boosting、1999年

Stochastic Gradient Boosting

バギング アンサンブルとランダム フォレストに対する大きな洞察は、トレーニング データセットのサブサンプルから貪欲に木を作成することを可能にしたことである。

この同じ利点は、勾配ブースティング モデルにおけるシーケンスのツリー間の相関を減らすために使用できる。

ブースティングのこのバリエーションは、ストキャスティック勾配ブースティングと呼ばれる。

– Stochastic Gradient Boosting , 1999

使用可能なストキャスティックブーストのバリエーション：

  • 各ツリー作成前に行をサブサンプル。
  • 各ツリー作成前に列をサブサンプル。

一般に、データの 50% を選択するような積極的なサブサンプリングは有益であることが示されています。

ユーザーからのフィードバックによると、列サブサンプリングを使用すると、従来の行サブサンプリングよりもさらにオーバーフィッティングが防止されます

– XGBoost: A Scalable Tree Boosting System, 2016

Penalized Gradient Boosting

Aditional constraints can be imposed on the parameterized trees in addition to its structure.

CART などの古典的決定木は弱い学習者として使用せず、代わりに葉ノード（ターミナルノードとも呼ぶ）に数値がある回帰木という修正形式が使用される。

そのため、木の葉の重み値は、次のような一般的な正則化関数を使用して正則化することができる：

  • L1 重みの正則化、
  • L2 重みの正則化、

追加の正則化項はオーバーフィットを避けるために最終学習重みを滑らかにするために役立つ。 直感的には、正則化された目的は、単純で予測的な関数を採用したモデルを選択する傾向がある。 A Scalable Tree Boosting System, 2016

Gradient Boosting Resources

Gradient boosting は魅力的なアルゴリズムなので、もっと深く知りたいのではないでしょうか。

このセクションでは、Gradient boosting アルゴリズムについてもっと学ぶために使用できるさまざまなリソースを一覧表示します。

Gradient Boosting Videos

  • Gradient Boosting Machine Learning, Trevor Hastie, 2014
  • Gradient Boosting, Alexander Ihler, 2012
  • GBM, John Mount, 2015
  • Learning.NetScope, 2011 GBM.NetScope, 2011 GBM.NetScope, 2012 学習。 ブースティング、MIT 6.034 Artificial Intelligence、2010
  • xgboost: An R package for Fast and Accurate Gradient Boosting, 2016
  • XGBoost: A Scalable Tree Boosting System, Tianqi Chen, 2016

Gradient Boosting in Textbook

  • Section 8.2.3 Boosting, page 321, An Introduction to Statistical Learning: with Applications in R….
  • Section 8.6 Boosting, page 203, Applied Predictive Modeling.
  • Section 14.5 Stochastic Gradient Boosting, page 390, Applied Predictive Modeling.
  • Section 16.4 Boosting, page 556, Machine Learning.Section 15.1 Boosting, page 4303, Applied Predictive Modeling.Section 15.1 ブースト、p. 330, p. 330, p. 330
  • 第10章ブースティングと加算木、337ページ、『統計的学習の要素』。 データマイニング、推論、予測

Gradient Boosting Papers

  • Thoughts on Hypothesis Boosting , Michael Kearns, 1988
  • A decision-theoretic generalization of on-line learning and an application to boosting , 1995
  • Arcing edge 、 1998
  • Stochastic Gradient Boosting 、 1999
  • Boosting Algorithms as Gradient Descent in Function Space , 1999

Gradient Boostingスライド

  • Introduction to Boosted Trees, 2014
  • A Gentle Introduction to Gradient Boosting, Cheng Li

Gradient Boosting Web ページ

  • ブースティング（機械学習）
  • 勾配ブースティング

    • Scikit-learn における勾配木ブースティング

まとめ

この投稿であなたは機械学習の予測モデル化の勾配ブースターアルゴリズムを発見したことでしょう。

  • 学習理論におけるブースティングの歴史と AdaBoost。
  • Gradient Boosting アルゴリズムが損失関数、弱い学習者、加法モデルでどのように機能するかを学びました。
  • 正則化でgradient boostingの性能を向上させる方法。

gradient boostingアルゴリズムやこの記事について質問がありますか？ コメントで質問していただければ、できる限りお答えします。

Discover The Algorithm Winning Competitions!

Develop Your Own XGBoost Models in Minutes

…Python

Discover how in my new Ebook:
XGBoost With Python

It covers self-study tutorials like:
Algorithm Fundamentals, Scaling, Hyperparameters, and much more…

Bring The Power of XGBoost To Your Own Projects

Skip the Academics.The XGBoost Power to the Own Project.Tech Power to the XGBoost with Python

Discover the Python: The XGBoost With Python

Discover how in the Python: The XGBoost With Python 中身を見る

Tweet Share Share

admin

コメントを残す

メールアドレスが公開されることはありません。

lg