ブートストラップ集約

ブートストラップ集約法は、バギング（bootstrap agg regatingに由来）またはブートストラッピングとも呼ばれ、機械学習（ ML ）のアンサンブルメタアルゴリズムであり、 ML分類および回帰アルゴリズムの安定性と精度を向上させるために設計されています。また、分散と過学習を軽減します。通常は決定木法に適用されますが、あらゆる種類の手法に使用できます。バギングは、アンサンブル平均化アプローチの特殊なケースです。

技術の説明

サイズの標準トレーニングセットが与えられると、バギングにより、から均一に、かつ復元サンプリングを行うことで、それぞれサイズの新しいトレーニングセットが生成されます。復元サンプリングを行うと、各で一部の観測が繰り返される可能性があります。の場合、が大きいについて、セットにはの一意のサンプルの割合 (1 - 1/ e ) (~63.2%) が含まれ、残りは重複すると予想されます。^[1]この種のサンプルはブートストラップサンプルとして知られています。復元サンプリングでは、サンプリング時に以前に選択されたサンプルに依存しないため、各ブートストラップがピアから独立していることが保証されます。次に、上記のブートストラップサンプルを使用してモデルをフィッティングし、出力の平均化 (回帰の場合) または投票 (分類の場合) によって組み合わせます。 $D$ $n$ $m$ $D_{i}$ $n'$ $D$ $D_{i}$ $n'=n$ $n$ $D_{i}$ $D$ $m$

バギングは「不安定な手法の改善」^[2]につながる。これには、例えば人工ニューラルネットワーク、分類木と回帰木、線形回帰におけるサブセット選択などが含まれる。^[3]バギングは原画像学習を改善することが示された。^[4]^[5]一方、k近傍法などの安定した手法の性能をわずかに低下させる可能性がある。^[2]

アルゴリズムのプロセス

キーワード

ブートストラップ集約には、オリジナルデータセット、ブートストラップデータセット、そしてOut-of-Baggingデータセットの3種類のデータセットがあります。以下の各セクションでは、オリジナルデータセットを除く各データセットの作成方法について説明します。オリジナルデータセットとは、与えられた情報すべてを指します。

ブートストラップデータセットの作成

ブートストラップデータセットは、元のデータセットからオブジェクトをランダムに選択して作成されます。また、元のデータセットと同じサイズである必要があります。ただし、ブートストラップデータセットには重複したオブジェクトが含まれる可能性があるという違いがあります。以下に、その仕組みを示す簡単な例と図を示します。

元のデータセットが12人のグループだとします。彼らの名前は、Emily、Jessie、George、Constantine、Lexi、Theodore、John、James、Rachel、Anthony、Ellie、Jamalです。

名前のグループをランダムに選択し、ブートストラップデータセットにJames、Ellie、Constantine、Lexi、John、Constantine、Theodore、Constantine、Anthony、Lexi、Constantine、Theodoreが含まれているとします。この場合、ブートストラップサンプルにはConstantineの重複が4つ、LexiとTheodoreの重複が2つ含まれていました。

アウトオブバッグデータセットの作成

out-of-bagデータセットは、ブートストラップデータセットに含まれなかった残りの人々を表します。これは、元のデータセットとブートストラップデータセットの差を取ることで計算できます。この場合、選択されなかった残りのサンプルは、Emily、Jessie、George、Rachel、Jamalです。両方のデータセットはセットであるため、差を取る際には、ブートストラップデータセット内の重複する名前は無視されることに注意してください。下の図は、計算方法を示しています。

応用

ブートストラップデータセットとアウトオブバッグデータセットの作成は、ランダムフォレストなどのアンサンブル学習アルゴリズムの精度をテストするために不可欠となります。例えば、ブートストラップ/アウトオブバッグデータセットを用いて50本のツリーを生成するモデルは、10本のツリーを生成するモデルよりも精度が高くなります。このアルゴリズムは複数のツリー、つまり複数のデータセットを生成するため、ブートストラップデータセットからオブジェクトが取り残される可能性は低くなります。次のセクションでは、ランダムフォレストアルゴリズムの仕組みについてより詳しく説明します。

決定木の作成

アルゴリズムの次のステップでは、ブートストラップされたデータセットから決定木を生成します。これを実現するために、プロセスでは各遺伝子/特徴を調べ、特徴の有無によって陽性または陰性の結果が生じるサンプル数を決定します。この情報を使用して、特徴を分類器として使用した場合の真陽性、偽陽性、真陰性、偽陰性をリストする混同行列を計算します。これらの特徴は、混同行列に基づくさまざまな分類指標に従ってランク付けされます。一般的な指標には、陽性の正確さの推定値（真陽性から偽陽性を差し引いて計算）、「良さ」の尺度、情報ゲインなどがあります。これらの特徴は、サンプルを2つのセット、つまり最上位の特徴を持つものと持たないものに分割するために使用されます。

下の図は、深さ2の決定木を用いてデータを分類する例です。例えば、特徴1は満たしているが特徴2は満たしていないデータポイントには「いいえ」と判定されます。特徴1は満たしていないが特徴3は満たしているデータポイントには「はい」と判定されます。

このプロセスは、目的の深さに達するまで、ツリーの連続するレベルごとに再帰的に繰り返されます。ツリーの最下部では、最終的な特徴量に対して陽性と判定されたサンプルは通常陽性と分類され、その特徴量を持たないサンプルは陰性と分類されます。これらのツリーは、新しいデータを分類するための予測変数として使用されます。

ランダムフォレスト

アルゴリズムの次の部分では、ブートストラップされた木の間にさらに別の変動要素を導入します。各木はブートストラップされたサンプルセットのみを検査するだけでなく、分類器としてランク付けする際には、少数ながらも一貫した固有の特徴のみが考慮されます。つまり、各木は、少数の一定数の特徴と、元のデータセットの数以下の可変数のサンプルに関するデータのみを認識します。その結果、木はより多様な知識から導き出された、より幅広い回答を返す可能性が高くなります。この結果、ランダムフォレストが生成されます。ランダムフォレストは、ランダム性のない単一の決定木に比べて多くの利点があります。ランダムフォレストでは、各木は、サンプルの特徴に基づいて、サンプルを陽性と分類するかどうかを「投票」します。そして、サンプルは多数決に基づいて分類されます。この例を下の図に示します。ランダムフォレスト内の4つの木は、変異A、B、F、Gを持つ患者が癌であるかどうかを投票します。4つの木のうち3つが「はい」と投票するため、患者は癌陽性と分類されます。

ランダムフォレストはその特性から、最も正確なデータマイニングアルゴリズムの一つと考えられており、データに過剰適合する可能性が低く、大規模なデータセットでも迅速かつ効率的に実行されます。 ^[6]データセット内の統計変数間の観測された関係性を導き出そうとする回帰とは対照的に、ランダムフォレストは主に分類に役立ちます。このため、ランダムフォレストは、過去のデータに基づいて将来の結果を予測できることが重要な銀行、医療、株式市場、電子商取引などの分野で特に有用です。 ^[7]上記の例に見られるように、その応用の一つとして、遺伝的要因に基づいて癌を予測するための有用なツールがあります。

ランダムフォレストを設計する際には、考慮すべき重要な要素がいくつかあります。ランダムフォレストのツリーが深すぎると、特異度が高すぎるために過剰適合が発生する可能性があります。フォレストが大きすぎると、実行時間の増加によりアルゴリズムの効率が低下する可能性があります。また、ランダムフォレストは、変動性の低いスパースデータを与えられた場合、一般的にパフォーマンスが良くありません。^{[7]しかし、}ニューラルネットワークなどの同様のデータ分類アルゴリズムに比べて解釈がはるかに簡単で、一般的にトレーニングに必要なデータが少ないため、多くの利点があります。^[要出典]ランダムフォレストの不可欠な要素として、ブートストラップ集約は分類アルゴリズムにとって非常に重要であり、以下で説明するように、新しいデータを分析するときに精度を向上させる変動性の重要な要素を提供します。

ランダムフォレストとバギングの改善

上記の手法はランダムフォレストとバギング（ブートストラッピングとも呼ばれます）を利用しています。しかし、実行時間と投票時間、予測精度、そして全体的なパフォーマンスを向上させるために使用できる特定の手法があります。効率的なランダムフォレストを作成するための重要な手順は次のとおりです。

ツリーの最大深度を指定します。すべてのノードが純粋になるまでランダムフォレストを続行するのではなく、過剰適合の可能性をさらに減らすために、特定のポイントでランダムフォレストを切断する方が適切です。
データセットの整理: 非常に大きなデータセットを使用すると、焦点を当てている内容をより正確に表す小さなセットよりも、提供されたデータを示す結果が少なくなる可能性があります。
- 元のバギングプロセスだけでなく、各ノード分割でデータのプルーニングを継続します。
精度と速度のどちらを選ぶか：求める結果に応じて、フォレスト内の木の数を増減させると効果的です。一般的に、木の数を増やすとより正確な結果が得られ、木の数を減らすとより速く結果が得られます。

アルゴリズム（分類）

分類には、トレーニングセット、インデューサ、ブートストラップサンプル数を入力として用いる。出力として分類器を生成する^[12] $D$ $I$ $m$ $C^{*}$

置換により新しいトレーニングセットを作成する $m$ $D_{i}$ $D$
分類器は、セットの分類を決定するために各セットから構築されます。 $C_{i}$ $D_{i}$ $I$ $D_{i}$
最後に、元のデータセットで以前に作成された分類器のセットを使用して分類器が生成され、サブ分類器によって最も頻繁に予測された分類が最終的な分類になります。 $C^{*}$ $C_{i}$ $D$ $C_{i}$

i = 1 から m まで {
    D' = Dからのブートストラップ標本（復元標本）
    Ci = I(D')
}
C*(x) = argmax #{i:Ci(x)=y} (最も頻繁に予測されるラベル y)
         y∈Y

例: オゾンデータ

バギングの基本原理を説明するために、オゾンと温度の関係の分析を以下に示します( Rousseeuwおよび Leroy ^{[説明が必要]} (1986)のデータ、Rで分析を実行)。

散布図に基づくと、このデータセットでは気温とオゾンの関係は非線形であるように見えます。この関係を数学的に記述するために、LOESS平滑化器（帯域幅0.5）が使用されています。データセット全体に対して単一の平滑化器を作成するのではなく、100個のブートストラップサンプルが抽出されました。各サンプルは元のデータのランダムなサブセットで構成され、マスターセットの分布と変動性に類似しています。各ブートストラップサンプルに対して、LOESS平滑化器が適合されました。そして、これらの100個の平滑化器から、データの範囲全体にわたる予測が行われました。黒い線は、これらの初期予測を表しています。これらの線は予測に一致しておらず、データポイントに過剰適合する傾向があります。これは、線の流れが不安定であることからも明らかです。

元のデータセットのサブセットに対応する100個のスムージング器の平均をとることで、1つのバギングされた予測変数（赤線）が得られます。赤線の流れは安定しており、どのデータポイントにも過度に一致していません。

メリットとデメリット

利点:

多数の弱い学習器を集約すると、通常、セット全体にわたって単一の学習器よりも優れたパフォーマンスを示し、過剰適合が少なくなる。
高分散低バイアス弱学習器の分散を低減し^[13] 、効率性を向上させることができる（統計）
それぞれのブートストラップは集約前に個別に処理できるため、並列に実行できます。 ^[14]

デメリット:

高いバイアスを持つ弱い学習者の場合、バギングは集約的にも高いバイアスを持ち込むことになる^[13]
モデルの解釈可能性の喪失。
データセットによっては計算コストが高くなる場合があります。

歴史

ブートストラップ集約の概念は、ブラッドリー・エフロンによって開発されたブートストラッピングの概念に由来しています。^{[15]ブートストラップ集約は}レオ・ブレイマンによって提唱され、彼は「バギング」（ bootstrap agg regating ）という略語も考案しました。ブレイマンは1994年に、ランダムに生成されたトレーニングセットの分類を組み合わせることで分類精度を向上させるというバギングの概念を開発しました。彼は、「学習セットに摂動を加えることで構築された予測変数に大きな変化をもたらすことができるのであれば、バギングによって精度を向上させることができる」と主張しました。^[3]

参照

参考文献

^ Aslam, Javed A.; Popa, Raluca A.; Rivest, Ronald L. (2007); 統計監査の規模と信頼度の推定について、電子投票技術ワークショップ (EVT '07) の議事録、ボストン、マサチューセッツ州、2007 年 8 月 6 日。より一般的には、 (異なるが同等の可能性がある)セットから置換値を使用して抽出する場合、一意の抽出の期待数はです。 $n'$ $n$ $n(1-e^{-n'/n})$
^ ab Breiman, Leo (1996). 「バギング予測子」.機械学習. 24 (2): 123– 140. CiteSeerX 10.1.1.32.9399 . doi :10.1007/BF00058655. S2CID 47328136.
^ ab Breiman, Leo (1994年9月). 「バギング予測子」(PDF) .技術レポート(421). カリフォルニア大学バークレー校統計学部. 2019年7月28日閲覧。
^ Sahu, A.、Runger, G.、Apley, D.、「マルチフェーズカーネル主成分アプローチとアンサンブルバージョンによる画像ノイズ除去」、IEEE応用画像パターン認識ワークショップ、pp.1-7、2011年。
^ シンデ、アミット、アンシュマン・サフ、ダニエル・アプリー、ジョージ・ルンガー。「カーネルPCAとバギングによる変分パターンの原像」IIE Transactions、第46巻、第5号、2014年
^ 「ランダムフォレスト - 分類の説明」. stat.berkeley.edu . 2021年12月9日閲覧。
^ ab 「機械学習におけるランダムフォレスト入門」。工学教育プログラム（EngEd）| セクション。 2021年12月9日閲覧。
^ 「ランダムフォレストの長所と短所」HolyPython.com . 2021年11月26日閲覧。
^ K, Dhiraj (2020年11月22日). 「ランダムフォレストアルゴリズムの利点と欠点」. Medium . 2021年11月26日閲覧。
^ チーム、Towards AI（2020年7月2日）。「決定木ではなくランダムフォレストを選ぶ理由 – Towards AI – 世界をリードするAIとテクノロジーの出版物」。 2021年11月26日閲覧。
^ 「ランダムフォレスト」。Corporate Finance Institute 。2021年11月26日閲覧。
^ Bauer, Eric; Kohavi, Ron (1999). 「投票分類アルゴリズムの実証的比較：バギング、ブースティング、およびバリアント」.機械学習. 36 : 108–109 . doi : 10.1023/A:1007515423169 . S2CID 1088806.
^ ab 「バギング（ブートストラップ集約）とは？」CFI . Corporate Finance Institute . 2020年12月5日閲覧。
^ Zoghni, Raouf (2020年9月5日). 「バギング（ブートストラップ・アグリゲーティング）の概要」The Startup – Medium経由。
^ Efron, B. (1979). 「ブートストラップ法：ジャックナイフ法の新たな一考察」. The Annals of Statistics . 7 (1): 1– 26. doi : 10.1214/aos/1176344552 .

さらに読む

Breiman, Leo (1996). 「バギング予測子」.機械学習. 24 (2): 123– 140. CiteSeerX 10.1.1.32.9399 . doi :10.1007/BF00058655. S2CID 47328136.
アルファロ、E.、ガメス、M.、ガルシア、N. (2012)。「adabag: AdaBoost.M1、AdaBoost-SAMME、Bagging を使用した分類用の R パッケージ」。 {{cite journal}}:ジャーナルを引用するには|journal=（ヘルプ）が必要ですCS1 maint: multiple names: authors list (link)
Kotsiantis, Sotiris (2014). 「分類問題への対応におけるバギングとブースティングのバリアント：概観」Knowledge Eng. Review . 29 (1): 78– 100. doi :10.1017/S0269888913000313. S2CID 27301684.
ベームケ、ブラッドリー、グリーンウェル、ブランドン (2019). 「バギング」. Rによる実践機械学習. チャップマン＆ホール. pp. 191– 202. ISBN 978-1-138-49568-5。