ブースティング

ブースティング（英えい: Boosting）とは、教師きょうしあり学習がくしゅうを実行じっこうするための機械きかい学習がくしゅうメタアルゴリズムの一種いっしゅ。ブースティングは、Michael Kearns の提示ていじした「一連いちれんの弱よわい学習がくしゅう器きをまとめることで強つよい学習がくしゅう器きを生成せいせいできるか？」という疑問ぎもんに基もとづいている^[1]。弱よわい学習がくしゅう器きは、真しんの分類ぶんるいと若干じゃっかんの相関そうかんのある分類ぶんるい器きと定義ていぎされる。対照たいしょう的てきに、強つよい学習がくしゅう器きとは真しんの分類ぶんるいとよく相関そうかんする分類ぶんるい器きである。

Michael Kearns の疑問ぎもんへの肯定こうてい的てき解答かいとうは、機械きかい学習がくしゅうや統計とうけい学がくに多大ただいな影響えいきょうを及およぼしている。

アルゴリズム[編集へんしゅう]

ブースティングはアルゴリズム的てきに制限せいげんされてはおらず、多おおくの場合ばあい、分布ぶんぷに従したがって弱よわい分類ぶんるい器きに繰くり返かえし学習がくしゅうさせ、それを最終さいしゅう的てきな強つよい分類ぶんるい器きの一部いちぶとするものである。弱よわい分類ぶんるい器きを追加ついかする際さい、何なんらかの方法ほうほうで重おもみ付づけをするのが一般いっぱん的てきで、重おもみ付づけは弱よわい学習がくしゅう器きの正確せいかくさに関連かんれんしているのが一般いっぱん的てきである。弱よわい学習がくしゅう器きが追加ついかされると、データの重おもみ付づけが見直みなおされる。すなわち、誤あやま分類ぶんるいされる例れいは重おもみを増まし、正まさしく分類ぶんるいされる例れいは重おもみを減へらす（boost by majority や BrownBoost などの一部いちぶのブースティングアルゴリズムは、繰くり返かえし誤あやま分類ぶんるいされる例れいの重おもみを減へらす）。従したがって、新あらたに追加ついかされる弱よわい学習がくしゅう器きは、それまでの弱よわい学習がくしゅう器きが誤あやま分類ぶんるいしていた例れいに注目ちゅうもくすることになる。

ブースティング・アルゴリズムには様々さまざまなものがある。初期しょきのブースティング・アルゴリズムとして Robert Schapire の recursive majority gate formulation ^[2]、Yoav Freund の boost by majority ^[3] がある。これらは適応てきおう的てきではなく、弱よわい学習がくしゅう器きの利点りてんを完全かんぜんに生いかしているとは言いえない。

PAC学習がくしゅう（probably approximately correct learning）理論りろんに従したがうブースティング・アルゴリズムだけが真しんのブースティング・アルゴリズムである。他たの類似るいじのアルゴリズムも誤あやまってブースティング・アルゴリズムと呼よばれることがあるが、それらを区別くべつする用語ようごとして "leveraging algorithm" がある^[4]。

例れい[編集へんしゅう]

各種かくしゅブースティング・アルゴリズムの主おもな違ちがいは、データ点てんと仮説かせつの重おもみ付づけの方法ほうほうである。有名ゆうめいなブースティング・アルゴリズムとして AdaBoost があり、これはおそらく初はじめて弱よわい学習がくしゅう器きの適応てきおうを実現じつげんしたものである。それ以外いがいにも最近さいきんでは LPBoost、BrownBoost、LogitBoost などのアルゴリズムがある。ブースティング・アルゴリズムの多おおくは、凸とつコスト関数かんすうを使つかった関数かんすう空間くうかんにおける最さい急降下きゅうこうか法ほうを実行じっこうできる AnyBoost フレームワークに適合てきごうする^[5]。

脚注きゃくちゅう[編集へんしゅう]

^ Michael Kearns. Thoughts on hypothesis boosting. Unpublished manuscript. 1988
^ Rob Schapire. Strength of Weak Learnability. Journal of Machine Learning Vol. 5, pages 197-227. 1990
^ Yoav Freund. Boosting a weak learning algorithm by majority. Proceedings of the Third Annual Workshop on Computational Learning Theory. 1990
^ Nir Krause and Yoram Singer. Leveraging the margin more carefully. In Proceedings of the International Conference on Machine Learning (ICML), 2004.
^ Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. In S.A. Solla, T.K. Leen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pages 512--518. MIT Press, 2000

参考さんこう文献ぶんけん[編集へんしゅう]

Yoav Freund and Robert E. Schapire A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1):119--139, 1997.
Robert E. Schapire and Yoram Singer. Improved Boosting Algorithms Using Confidence-Rated Predictions. Machine Learning, 37(3):297--336, 1998.

外部がいぶリンク[編集へんしゅう]

ブースティング関連かんれんの論文ろんぶんへのリンク集しゅう
ブースティング朱鷺ときの杜もりWiki
ブースティング法ほうの理論りろんと応用おうよう川かわ喜田きた雅則まさのり、統計数理研究所とうけいすうりけんきゅうしょ、2006年ねん10月がつ

[Kearns88-1] Michael Kearns. Thoughts on hypothesis boosting. Unpublished manuscript. 1988

[Schapire90-2] Rob Schapire. Strength of Weak Learnability. Journal of Machine Learning Vol. 5, pages 197-227. 1990

[Freund90-3] Yoav Freund. Boosting a weak learning algorithm by majority. Proceedings of the Third Annual Workshop on Computational Learning Theory. 1990

[Krause04-4] Nir Krause and Yoram Singer. Leveraging the margin more carefully. In Proceedings of the International Conference on Machine Learning (ICML), 2004.

[Mason00-5] Llew Mason, Jonathan Baxter, Peter Bartlett, and Marcus Frean. Boosting algorithms as gradient descent. In S.A. Solla, T.K. Leen, and K.-R. Muller, editors, Advances in Neural Information Processing Systems 12, pages 512--518. MIT Press, 2000

[1]

[2]

[3]

[4]

[5]

アルゴリズム[編集へんしゅう]

例れい[編集へんしゅう]

関連かんれん項目こうもく[編集へんしゅう]

脚注きゃくちゅう[編集へんしゅう]

参考さんこう文献ぶんけん[編集へんしゅう]

外部がいぶリンク[編集へんしゅう]