Main Content

アンサンブル アルゴリズム

このトピックでは、バギング、ランダム空間、各種のブースティング アルゴリズムなど、Statistics and Machine Learning Toolbox™ でサポートされるアンサンブル学習アルゴリズムについて説明します。アルゴリズムは、fitcensemblefitrensemble または templateEnsemble の名前と値のペアの引数 'Method' を使用して指定できます。学習器のアンサンブルを作成するには、分類の場合は fitcensemble、回帰の場合は fitrensemble を使用します。ECOC マルチクラス学習用のアンサンブル バイナリ学習器を指定するには、templateEnsemble を使用して作成したアンサンブル学習器テンプレートを fitcecoc に渡します。

bootstrap aggregation (バギング) とランダム フォレストの場合は、TreeBagger も使用できます。

'Method' の値アルゴリズムサポートされる問題
'Bag'bootstrap aggregation (バギング) とランダム フォレスト ([1], [2], [3])バイナリおよびマルチクラス分類、回帰
'Subspace'ランダム部分空間 ([9])バイナリおよびマルチクラス分類ランダム部分空間の分類
'AdaBoostM1'バイナリ分類用の適応ブースティング ([5], [6], [7], [11])バイナリ分類
'AdaBoostM2'マルチクラス分類用の適応ブースティング ([5])マルチクラス分類アンサンブル分類の使用によるクラス ラベルの予測
'GentleBoost'ジェントル適応ブースティング ([7])バイナリ分類
'LogitBoost'適応ロジスティック回帰 ([7])バイナリ分類
'LPBoost'線形計画ブースティング ([13])バイナリおよびマルチクラス分類小さいアンサンブルでの LPBoost と TotalBoost
'LSBoost'最小二乗ブースティング ([2], [8])回帰
'RobustBoost'ロバスト ブースティング ([4])バイナリ分類RobustBoost の調整
'RUSBoost'ランダム アンダーサンプリング ブースティング ([12])バイナリおよびマルチクラス分類不均衡データでの分類
'TotalBoost'完全補正ブースティング ([13])バイナリおよびマルチクラス分類小さいアンサンブルでの LPBoost と TotalBoost

適切なアルゴリズムを選択する方法については、適用するアンサンブル集約法の選択を参照してください。

LPBoostTotalBoostRobustBoost など一部のアルゴリズムを使用するには Optimization Toolbox™ が必要であることに注意してください。

bootstrap aggregation (バギング) とランダム フォレスト

Statistics and Machine Learning Toolbox には、バギングおよびランダム フォレスト用に 3 つのオブジェクトが用意されています。

TreeBagger とバギング アンサンブル (ClassificationBaggedEnsemble および RegressionBaggedEnsemble) の違いについては、TreeBagger とバギング アンサンブルの比較を参照してください。

"bootstrap aggregation" ("バギング") は、アンサンブル学習の一種です。データ セットに対して決定木などの弱学習器をバギングするには、データ セットのブートストラップ複製を多数生成し、この複製に対して決定木を成長させます。N 個の観測値から N 個を復元抽出法で無作為に選択することにより、各ブートストラップ複製を取得します (N はデータ セットのサイズ)。さらに、アンサンブル内のすべての木で各決定分岐の予測子を無作為に選択できます。これはランダム フォレスト[2]と呼ばれる手法で、バギング木の精度が向上することが知られています。既定では、各分岐に対して無作為に選択する予測子の個数は、分類の場合は予測子の個数の平方根、回帰の場合は予測子の個数の 3 分の 1 です。モデルに学習をさせた後で関数 predict を使用すると、新しいデータについて学習済みアンサンブルの予測応答を求めることができます。predict は、個々の木による予測を平均します。

既定では、バギング木の葉ごとの最小観測値数は、分類の場合は 1 に、回帰の場合は 5 に設定されます。通常、既定の設定のリーフ サイズを使用して成長したツリーは、非常に深くなります。これらは、アンサンブルの予測力を高めるにはほとんど最適な設定です。多くの場合、予測力を低下させずにリーフ サイズの大きなツリーを成長させることができます。そうすることによって、学習済みアンサンブルのメモリ使用量が少なくなるだけでなく、学習や予測の時間も短縮されます。葉ごとの最小観測値数は、templateTree または TreeBagger の名前と値のペアの引数 'MinLeafSize' を使用して制御できます。バギング アンサンブルの作成に fitcensemblefitrensemble を使用した場合は、関数 templateTree を使用して木学習器のオプションを指定することに注意してください。

バギングされた決定木の特徴量のいくつかは固有なアルゴリズムになります。N 個の観測値から N 個を復元抽出すると、決定木ごとに平均で 37% の観測値が省略されます。このような省略された観測値は "out-of-bag" 観測値と呼ばれます。TreeBagger とバギング アンサンブル (ClassificationBaggedEnsemble および RegressionBaggedEnsemble) には、out-of-bag 観測値を使用するプロパティとオブジェクト関数があります。これらは、名前が oob で始まります。

  • 予測力と特徴量の重要度は、関数 oobPredict を使用して推定できます。oobPredict は、観測値が out-of-bag であるアンサンブル内のすべての木による予測の平均を計算することにより、各観測値について out-of-bag 予測を推定します。

  • 平均 out-of-bag 誤差の推定には、oobError (TreeBagger の場合) または oobLoss (バギング アンサンブルの場合) を使用します。これらの関数は、学習に使用したすべての観測値について、out-of-bag 予測応答と観測された応答を比較します。out-of-bag の平均は真のアンサンブル誤差の不偏推定量です。

  • 特徴量の重要度の out-of-bag 推定を取得するには、OOBPermutedPredictorDeltaError プロパティ (TreeBagger の場合) または oobPermutedPredictorImportance プロパティ (バギング アンサンブルの場合) を使用します。1 変数または 1 列ごとに out-of-bag データが無作為に並べ替えられ、この並べ替えによる out-of-bag 誤差の増加が推定されます。増加がより大きいほど、特徴はより重要になります。したがって、学習の過程で予測力と特徴量の重要度について信頼できる推定が得られるので、バギング アンサンブル用のテスト データを提供する必要はありません。

TreeBagger は、Proximity プロパティで近接行列も提供します。あるツリーの同じリーフに 2 つの観測値が着地するたびに、その近接度は 1 増加します。正規化するには、これらの近接度をアンサンブル内のすべてのツリーにおいて合計し、ツリーの数で除算します。生成される行列は、対角要素が 1 に等しく非対角要素が 0 ~ 1 の範囲にある対称行列です。この行列を使用すると、外れ値である観測値とクラスターを多次元尺度構成法によりデータから検出できます。

バギングの使用例は、以下を参照してください。

TreeBagger とバギング アンサンブルの比較

TreeBagger とバギング アンサンブル (ClassificationBaggedEnsemble および RegressionBaggedEnsemble) は、ほとんどの機能が共通していますが、すべてではありません。また、一部の機能は名前が異なります。

バギング アンサンブルにはない TreeBagger の機能

機能TreeBagger プロパティTreeBagger メソッド
近接行列の計算Proximity

fillprox, mdsprox

fillprox を使用して TreeBagger モデルの近接行列と外れ値を推定するときに、MATLAB® は n 行 n 列の行列の近似計算をメモリ内で行わなければなりません。n は観測値の個数です。したがって、n が中程度~大規模である場合、近接行列と外れ値の推定は行わないでください。

外れ値の計算OutlierMeasure該当なし
分類マージンの使用による予測子の重要度の out-of-bag 推定OOBPermutedPredictorDeltaMeanMargin および OOBPermutedPredictorCountRaiseMargin 該当なし
個別に学習させた 2 つのアンサンブルのマージ該当なしappend
分位点回帰該当なしquantilePredict, quantileError, oobQuantilePredict, oobQuantileError
アンサンブル作成に対する tall 配列のサポート該当なし詳細については、tall 配列を参照してください。

TreeBagger にはないバギング アンサンブルの機能

機能説明
ハイパーパラメーターの最適化名前と値のペアの引数 'OptimizeHyperparameters' を使用する。
学習を高速化するための数値予測子のビン化名前と値のペアの引数 'NumBins' を使用する。
predict 用のコード生成モデルに学習をさせた後で、新しいデータについてラベルを予測する C/C++ コードを生成できます。C/C++ コードの生成には MATLAB Coder™ が必要です。詳細については、コード生成の紹介を参照してください。

TreeBagger とバギング アンサンブルにおける名前の違い

機能TreeBaggerバギング アンサンブル
予測子ごとの分離基準の貢献度DeltaCriterionDecisionSplit プロパティpredictorImportance (分類) または predictorImportance (回帰) の最初の出力
予測子の関連付けSurrogateAssociation プロパティpredictorImportance (分類) または predictorImportance (回帰) の 2 番目の出力
予測子の重要度に関する out-of-bag 推定OOBPermutedPredictorDeltaError プロパティoobPermutedPredictorImportance (分類) または oobPermutedPredictorImportance (回帰) の出力
誤差 (誤分類の確率または平均二乗誤差)error メソッドと oobError メソッドが用意されています。loss メソッドと oobLoss メソッド (分類)、または loss メソッドと oobLoss メソッド (回帰)
追加した木の学習とアンサンブルへの追加growTrees メソッドresume メソッド (分類) または resume メソッド (回帰)
ツリーごとの分類マージンの平均meanMargin メソッドと oobMeanMargin メソッドが用意されています。edgeoobEdge メソッド (分類)

さらに、モデルの学習と応答の予測を行うときに、2 つの重要な違いがあります。

  • TreeBagger に誤分類コスト行列を渡した場合、この行列が木に渡されます。fitcensemble に誤分類コスト行列を渡した場合、この行列を使用してクラスの事前確率が調整されます。その後 fitcensemble は、調整された事前確率と既定のコスト行列を木に渡します。既定のコスト行列は、K クラスでは ones(K)–eye(K) です。

  • ClassificationBaggedEnsembleloss および edge メソッドとは異なり、TreeBaggererror および meanMargin メソッドは、それぞれのクラスの事前確率について、入力観測値の重みを正規化しません。

ランダム部分空間

ランダム部分空間アンサンブル (Subspace) を使用して、判別分析 (ClassificationDiscriminant) または k 最近傍法 (ClassificationKNN) 分類器の精度を向上させます。また、Subspace アンサンブルはすべての予測子をもつアンサンブルよりも少ないメモリを使用し、さらに欠損値 (NaN) も処理できます。

基本のランダム部分空間アルゴリズムでは以下のパラメーターを使用します。

  • m は各学習器で標本を取り出す次元 (変数) の数です。m の設定には名前と値のペア NPredToSample を使用します。

  • d はデータ内の次元数で、X データ行列の列 (予測子) の数を示します。

  • n は、アンサンブル内に存在する学習器の数です。NLearn を入力して n を設定します。

基本のランダム部分空間アルゴリズムは以下の手順を実行します。

  1. m 予測子のセットを非復元抽出法により d の候補値から無作為に選択します。

  2. m 個の選択された予測子のみを使用して、弱学習器を学習させます。

  3. 弱学習器が n になるまで、手順 1 と 2 を繰り返します。

  4. 弱学習器の score 予測を平均して予測し、score の平均が最も高いカテゴリを分類します。

d の次元から選択可能なすべての m 個の予測子のセットで、弱学習器が作成されるよう選択できます。これを行うには、学習器の数を示す n を 'AllPredictorCombinations' に設定します。この場合、アンサンブルには nchoosek(size(X,2),NPredToSample) 個の弱学習器があります。

関数 fitcensemble は、後続の学習器が前に使用された予測子を使用する確率が下がるように、学習器の予測子を選択した後で予測子の重みを小さくします。このように重み付けを行うと、一様に重み付けするよりも学習器内の予測子が均等に分布される傾向をもちます。

Subspace の使用例は、ランダム部分空間の分類を参照してください。

ブースティング アルゴリズム

バイナリ分類用の適応ブースティング

AdaBoostM1 という名前の適応ブースティングは、バイナリ分類のブースティング アルゴリズムとして一般的に利用されています。アルゴリズムでは、学習器に連続的に学習を行わせます。インデックス t をもつすべての学習器について、AdaBoostM1 は重み付き分類誤差を計算します。

εt=n=1Ndn(t)I(ynht(xn)),

ここで

  • xn は、観測値 n の予測子値のベクトルです。

  • yn は真のクラス ラベルです。

  • ht はインデックス t をもつ学習器の予測 (仮説) です。

  • I はインジケーター関数です。

  • dn(t) は、ステップ t における観測値 n の重みです。

AdaBoostM1 は、次に学習器 t によって誤分類された観測値の重みを増加させ、学習器 t によって正しく分類された観測値の重みを減少させます。次の学習器 t + 1 は、更新された重み dn(t+1) をもつデータで学習を行います。

学習が完了した後で、AdaBoostM1 は次の式を使用して新しいデータの予測を計算します。

f(x)=t=1Tαtht(x),

ここで

αt=12log1εtεt

は、アンサンブルに存在する弱仮説の重みです。

AdaBoostM1 による学習は、指数損失の逐次最小化と見なすことができます。

n=1Nwnexp(ynf(xn)),

ここで

  • yn ∊ {–1,+1} は真のクラス ラベルです。

  • wn は最大で 1 まで正規化される観測値の重みです。

  • f(xn) ∊ (–∞,+∞) は予測された分類スコアです。

観測値の重み wn は、fitcensemble に渡した元の観測値の重みです。

AdaBoostM1 アンサンブル分類の predict メソッドの 2 番目の出力は、2 つのクラスと N 個の観測値の N 行 2 列の行列です。この行列の 2 列目は常に 1 列目の負数に等しくなります。predict メソッドはマルチクラス モデルと一致する 2 つのスコアを返します。ただし、2 番目の列は常に最初の列の負数になるため、これは冗長です。

AdaBoostM1 が最もよく使用されるのは、木の決定株 (既定の設定) または浅いツリーで使用される場合です。ブースティングされた決定株の性能が低い場合は、最小親ノード サイズを学習データの 4 分の 1 に設定します。

既定の設定では、ブースティング アルゴリズムの学習率は 1 です。学習率を低い値に設定した場合には、アンサンブル学習率は低くなりますが、最終的には良い結果が得られます。最もよく使用される学習率は、0.1 です。1 より低い学習率を使用することは、“縮小” と呼ばれる場合があります。

AdaBoostM1 の使用例は、コストを考慮して 2 つの分類モデルを比較するECOC マルチクラス学習のアンサンブル テンプレートの作成を参照してください。

マルチクラス分類用の適応ブースティング

AdaBoostM2 という名前の適応ブースティングは、複数クラス用に拡張された AdaBoostM1 です。重み付き分類誤差の代わりに、AdaBoostM2 では、N 個の観測値と K クラスに対して、重み付き疑似損失を使用します。

εt=12n=1Nkyndn,k(t)(1ht(xn,yn)+ht(xn,k)),

ここで

  • ht(xn,k) はステップ t での学習器の予測における信頼性であり、0 (まったく信頼できない) から 1 (信頼性が高い) までの範囲のクラス k で表されます。

  • dn,k(t) は、ステップ t におけるクラス k の観測値の重みです。

  • yn は真のクラス ラベルで、K の値のいずれかになります。

  • 2 番目の合計は、真のクラス yn 以外のすべてのクラスを対象としたものです。

疑似損失の解釈は分類誤差より難しいですが、基本的概念は同じです。疑似損失は、アンサンブル内の任意の学習器の分類精度を測定するために使用できます。疑似損失は、通常は AdaBoostM1 の重み付き分類誤差と同じように動作します。ブースティング アンサンブルの最初のいくつかの学習器では、疑似損失の値は低くなります。その後、学習ステップが進むと、アンサンブル学習速度は遅くなり、疑似損失値は 0.5 に接近するほどに増加します。

AdaBoostM2 の使用例については、アンサンブル分類の使用によるクラス ラベルの予測を参照してください。

ジェントル適応ブースティング

ジェントル適応ブースティング (GentleBoost、Gentle AdaBoost としても知られています) では、AdaBoostM1LogitBoost の機能が結合されています。AdaBoostM1 と同様に、GentleBoost は指数損失を最小化します。ただし、数値最適化の設定は異なります。LogitBoost と同様に、すべての弱学習器は回帰モデルを応答値 yn ∊ {–1,+1} に当てはめます。

fitcensemble はアンサンブル オブジェクトの FitInfo プロパティに平均二乗誤差を計算して格納します。平均二乗誤差は次の式で求められます。

n=1Ndn(t)(y˜nht(xn))2,

ここで

  • dn(t) は、ステップ t における観測値の重みです (重みの合計は 1)。

  • ht(xn) は、応答値 yn に近似された回帰モデル ht の予測です。

個々の学習器の強度が弱くなるに従って、重み付けられた平均二乗誤差は 1 に近づきます。

GentleBoost の使用例は、ビン化と並列計算の使用による ECOC 分類器の学習の高速化アンサンブル分類における不均衡データまたは一様ではない誤分類コストの処理を参照してください。

適応ロジスティック回帰

適応ロジスティック回帰 (LogitBoost) もバイナリ分類用の一般的なアルゴリズムです。LogitBoostAdaBoostM1 と同じように機能しますが、二項分布からの逸脱度を最小化するという点が異なります。

n=1Nwnlog(1+exp(2ynf(xn))),

ここで

  • yn ∊ {–1,+1} は真のクラス ラベルです。

  • wn は最大で 1 まで正規化される観測値の重みです。

  • f(xn) ∊ (–∞,+∞) は予測された分類スコアです。

二項分布からの逸脱度により、誤分類の程度が大きい観測値 (ynf(xn) が高い負の値になる観測値) への重みの割り当てが低くされます。LogitBoost を使用すると、クラスが適切に分割されないようなデータに対しても、AdaBoostM1 より高い平均精度を達成できます。

LogitBoost アンサンブルの学習器 t は、回帰モデルを応答値に当てはめます。

y˜n=yn*pt(xn)pt(xn)(1pt(xn)),

ここで

  • y*n ∊ {0,+1} は、(-1 ではなく 0 に) ラベルを付け直されたクラスです。

  • pt(xn) は、観測値 xn がクラス 1 になる確率を現在のアンサンブルで推定した値です。

fitcensemble はアンサンブル オブジェクトの FitInfo プロパティに平均二乗誤差を計算して格納します。平均二乗誤差は次の式で求められます。

n=1Ndn(t)(y˜nht(xn))2,

ここで

  • dn(t) は、ステップ t における観測値の重みです (重みの合計は 1)。

  • ht(xn) は、応答値 y˜n に近似された回帰モデル ht の予測です。

値 yn の範囲は –∞ ~ +∞ です。そのため、平均二乗誤差には、明確な限界がありません。

LogitBoost の使用例は、アンサンブル分類に学習をさせる数値予測子の値のビン化による学習の高速化を参照してください。

線形計画ブースティング

線形計画ブースティング (LPBoost) は、TotalBoost と同様に、学習セットの最小 "マージン" を最大化しようとすることにより、マルチクラス分類を実行します。この試行では最適化アルゴリズム (具体的には LPBoost の線形計画法) が使用されます。そのため、LPBoostTotalBoost を使用するには Optimization Toolbox のライセンスが必要です。

分類のマージンは、真のクラスについて予測されたソフト分類 "スコア" と、偽のクラスの最大スコアの差を表します。ツリーの場合、葉ノードの分類の "スコア" は、そのノードでの分類の事後確率です。あるノードにおける分類の事後確率とは、分類によって実際にそのノードに達するのに要した学習シーケンスの数を、そのノードまでの学習シーケンスの数で除算した値です。詳細は、margin詳細を参照してください。

最小マージンを最大化するのはなぜでしょうか。まず、汎化誤差 (新しいデータでの誤差) は負のマージンが発生する確率です。Schapire と Singer [10] は、負のマージンが発生する確率に関して次のような不等式を確立しました。

Ptest(m0)Ptrain(mθ)+O(1NVlog2(N/V)θ2+log(1/δ)).

ここで、m はマージン、θ は任意の正の数値、V は分類器空間の Vapnik-Chervonenkis 次元、N は学習セットのサイズ、δ は正の少数です。この不等式は、多数の独立同一分布の学習セットとテスト セットに対して確率が 1–δ の場合に成立します。この不等式から、汎化誤差を小さくするには、学習セットで観測数を最小化してマージン θ より小さくすればよいことがわかります。

LPBoost は、一連の線形プログラミングの問題によって最小マージンの最大化するよう反復します。同様に、その双対性から、LPBoost は最大 "エッジ" を最小化します。エッジとは重み付けされた平均マージンです (詳細を参照してください)。反復を実行するたびに、問題の制約が増えていきます。そのため、大きな問題に対しては、最適化の問題の制約が非常に多くなり、解決に時間がかかることになります。

LPBoost は通常、重み付けされた多数の学習器をもつアンサンブルを作成します。この重みは、他の学習器の桁数より小さい桁数です。そのため、重要でないアンサンブルのメンバーをより確実に削除できるようにするため、compact メソッドでは LPBoost アンサンブルのメンバーを重みの大きい順に並べ替えられます。これにより、removeLearners メソッドを使用して、重要性が最も低いメンバーをアンサンブルから簡単に削除できるようになります。

LPBoost の使用例については、小さいアンサンブルでの LPBoost と TotalBoostを参照してください。

最小二乗ブースティング

最小二乗ブースティング (LSBoost) はアンサンブル回帰を当てはめます。ステップごとに、アンサンブルは新しい学習器を、実際に観測された応答とこれまでに学習させたすべての学習器を対象に集約された予測との差分に当てはめます。アンサンブルは近似によって平均二乗誤差を最小化します。

LearnRate パラメーターを渡すことによって、LSBoost を縮小で使用できます。既定の設定では、このパラメーターは 1 に設定されており、アンサンブルは最大速度で学習を行います。LearnRate0 から 1 までの値に設定した場合は、アンサンブルはすべての新しい学習器を yn – ηf(xn) に当てはめます。ここで、

  • yn は、観測された応答です。

  • f(xn) は、これまでに観測値 xn について学習を行ったすべての弱学習器から集約された予測です。

  • η は学習率です。

LSBoost の使用例については、アンサンブル回帰に学習をさせるブースティング回帰アンサンブル回帰の最適化およびアンサンブルの正則化を参照してください。

ロバスト ブースティング

AdaBoostM1LogitBoost などのブースティング アルゴリズムでは、ブースティングのステップごとに誤分類された観測値の重みを増加させます。これらの重みは非常に大きくなる可能性があります。その場合は、ブースティング アルゴリズムが少数の誤分類された観測値に集中して、学習データの大部分が無視されてしまう可能性があります。その結果、平均分類精度が低下します。このような状況では、ロバスト ブースティング (RobustBoost) の使用を試すことができます。このアルゴリズムでは、全データ分の重みを少数の誤分類された観測値に割り当ててしまうようなことはほとんど起こりません。そのため、優れた平均分類精度を達成できます。RobustBoost を使用するには Optimization Toolbox のライセンスが必要です。

AdaBoostM1LogitBoost とは異なり、 RobustBoost では、特定の損失関数を最小化することはありません。代わりに、一定のしきい値を超える分類マージンをもつ観測値の数を最大化します。

RobustBoost は、時間発展に基づいて学習を行います。このアルゴリズムは、t = 0 から始まります。ステップごとに、RobustBoost は最適化問題を解いて、時間 Δt での肯定的なステップと、それに対応する学習データ Δm の平均マージンにおける肯定的な変更を行います。次の 3 つの条件のいずれかが真の場合に、RobustBoost は学習を停止し、終了します。

  • 時間 t が 1 に到達する。

  • Δt および Δm の更新によっては、RobustBoost が最適化問題の解を求めることができなくなる。

  • RobustBoost は、要求した数の学習器を作成できます。

RobustBoost の結果は、どのような終了条件でも使用できます。交差検証または独立したテスト セットを使用することによって、分類精度を推定します。

RobustBoost で得られる精度を高くするには、関数 fitcensemble で次の 3 つのパラメーターを調整します。このパラメーターは RobustErrorGoalRobustMaxMargin および RobustMarginSigma です。はじめに、RobustErrorGoal の値を 0 から 1 まで変化させます。RobustErrorGoal について指定できる最大値は、他の 2 つのパラメーターによって決まります。高すぎる値を指定した場合は、fitcensemble はエラー メッセージを表示し、RobustErrorGoal に使用できる値の範囲を示します。

RobustBoost の使用例については、RobustBoost の調整を参照してください。

ランダム アンダーサンプリング ブースティング

ランダム アンダーサンプリング ブースティング (RUSBoost) は、不均衡なデータを分類する場合、つまり、学習データの一部のクラスのメンバーが他のクラスよりはるかに少ない場合に特に効果的です。RUS は「Random Under Sampling」の略です。このアルゴリズムでは、N (学習データで最もメンバー数が少ないクラスのメンバー数) をサンプリングの基本単位として使用します。これよりメンバー数が多いクラスは、各クラスの観測値の中から N 件だけを抽出してアンダーサンプリングされます。つまり、クラス数が K の場合、アンサンブル内の弱学習器のそれぞれについて、RUSBoost は K 個のクラスのそれぞれから N 件の観測値があるデータのサブセットを抽出します。ブースティングはマルチクラス分類用の適応ブースティングの手順に従って実行され、アンサンブルの再度の重み付けと構築が行われます。

RUSBoost アンサンブルを構築する場合、RatioToSmallest という名前のオプションの名前と値のペアがあります。K 個の値 (各値は割り当てられたクラスの標本数 N の倍数) があるベクトルを指定します。たとえば、最も小さいクラスのメンバー数が N = 100 の場合、RatioToSmallest = [2,3,4] は各弱学習器のメンバー数がクラス 1 では 200、クラス 2 では 300、クラス 3 では 400 であることを表します。RatioToSmallest が特定のクラスのメンバー数より大きい値を導き出した場合、RUSBoost はメンバーを復元抽出します。それ以外の場合、RUSBoost はメンバーを非復元抽出します。

RUSBoost の使用例については、不均衡データでの分類を参照してください。

完全補正ブースティング

完全補正ブースティング (TotalBoost) は、線形計画ブースティング (LPBoost) と同様に、学習セットの最小 "マージン" を最大化しようとすることにより、マルチクラス分類を実行します。この試行では最適化アルゴリズム (TotalBoost の二次計画法) が使用されます。そのため、LPBoostTotalBoost を使用するには Optimization Toolbox のライセンスが必要です。

分類のマージンは、真のクラスについて予測されたソフト分類 "スコア" と、偽のクラスの最大スコアの差を表します。ツリーの場合、葉ノードの分類の "スコア" は、そのノードでの分類の事後確率です。あるノードにおける分類の事後確率とは、分類によって実際にそのノードに達するのに要した学習シーケンスの数を、そのノードまでの学習シーケンスの数で除算した値です。詳細は、margin詳細を参照してください。

最小マージンを最大化するのはなぜでしょうか。まず、汎化誤差 (新しいデータでの誤差) は負のマージンが発生する確率です。Schapire と Singer [10] は、負のマージンが発生する確率に関して次のような不等式を確立しました。

Ptest(m0)Ptrain(mθ)+O(1NVlog2(N/V)θ2+log(1/δ)).

ここで、m はマージン、θ は任意の正の数値、V は分類器空間の Vapnik-Chervonenkis 次元、N は学習セットのサイズ、δ は正の少数です。この不等式は、多数の独立同一分布の学習セットとテスト セットに対して確率が 1–δ の場合に成立します。この不等式から、汎化誤差を小さくするには、学習セットで観測数を最小化してマージン θ より小さくすればよいことがわかります。

TotalBoost は、"エッジ" (重み付きマージン) が特定の値より下であるという制約のもとで、現在の重み分布と初期の重み分布の間のカルバック・ライブラー ダイバージェンスのプロキシを最小限にします。このプロキシは、このダイバージェンスの 2 次展開です。

D(W,W0)=n=1NlogW(n)W0(n)n=1N(1+W(n)W0(n))Δ+12W(n)Δ2,

ここで、Δ は W(n) (現在の反復と次の反復の重み) と W0 (初期の重み分布。一様分布です) の差を表します。この最適化定式によって、重みは 0 になりません。反復を実行するたびに、問題の制約が増えていきます。そのため、大きな問題に対しては、最適化の問題の制約が非常に多くなり、解決に時間がかかることになります。

TotalBoost は通常、重み付けされた多数の学習器をもつアンサンブルを作成します。この重みは、他の学習器の桁数より小さい桁数です。そのため、重要でないアンサンブルのメンバーをより確実に削除できるようにするため、compact メソッドでは TotalBoost アンサンブルのメンバーを重みの大きい順に並べ替えられます。これにより、removeLearners メソッドを使用して、重要性が最も低いメンバーをアンサンブルから簡単に削除できるようになります。

TotalBoost の使用例については、小さいアンサンブルでの LPBoost と TotalBoostを参照してください。

参照

[1] Breiman, L. "Bagging Predictors." Machine Learning 26, 1996, pp. 123–140.

[2] Breiman, L. "Random Forests." Machine Learning 45, 2001, pp. 5–32.

[4] Freund, Y. "A more robust boosting algorithm." arXiv:0905.2138v1, 2009.

[5] Freund, Y. and R. E. Schapire. "A Decision-Theoretic Generalization of On-Line Learning and an Application to Boosting." J. of Computer and System Sciences, Vol. 55, 1997, pp. 119–139.

[6] Friedman, J. "Greedy function approximation: A gradient boosting machine." Annals of Statistics, Vol. 29, No. 5, 2001, pp. 1189–1232.

[7] Friedman, J., T. Hastie, and R. Tibshirani. "Additive logistic regression: A statistical view of boosting." Annals of Statistics, Vol. 28, No. 2, 2000, pp. 337–407.

[8] Hastie, T., R. Tibshirani, and J. Friedman. The Elements of Statistical Learning, second edition. New York: Springer, 2008.

[9] Ho, T. K. "The random subspace method for constructing decision forests." IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 20, No. 8, 1998, pp. 832–844.

[10] Schapire, R., and Y. Singer. "Improved boosting algorithms using confidence-rated predictions." Machine Learning, Vol. 37, No. 3, 1999, pp. 297–336.

[11] Schapire, R. E. et al. "Boosting the margin: A new explanation for the effectiveness of voting methods." Annals of Statistics, Vol. 26, No. 5, 1998, pp. 1651–1686.

[12] Seiffert, C., T. Khoshgoftaar, J. Hulse, and A. Napolitano. "RUSBoost: Improving classification performance when training data is skewed." 19th International Conference on Pattern Recognition, 2008, pp. 1–4.

[13] Warmuth, M., J. Liao, and G. Ratsch. "Totally corrective boosting algorithms that maximize the margin." Proc. 23rd Int’l. Conf. on Machine Learning, ACM, New York, 2006, pp. 1001–1008.

参考

| | | | | | | | | | | |

関連するトピック