Additive Logistic Regression: a Statistical View of Boosting

Additive Logistic Regression: a Statistical View of Boosting - Friedman, Hastie, Tibshirani (ResearchIndex)

http://citeseer.ist.psu.edu/friedman98additive.html

ブースティングといえば、AdaBoostに始まり、いろいろな工夫がなされたけども、結局AdaBoostに尽きる。いろいろな変種はあるけれど、シンプルで実装しやすく、かつ性能もいい、理論的にも美しい、という各側面においてAdaBoostを超えるものはなかなか見つからない。LogitBoostを除いては。

というふうに、聞いたことがあった。たしかに、そんな感じなのかなと思っていた。それだけにLogitBoostの論文は抑えておきたいと思っていた。

この論文を読んでも、すぐにはLogitBoostを実装できるか、というとちょっと難しいような木もするのだけれど（私の知識不足もあるとは思う）、AdaBoostを取り込んだ枠組みを定めて、それを超えるようなアルゴリズムを生み出している。具体的には、Boostingをadditiveモデルとみなす枠組みを定める。すると、AdaBoostはマージンを指数損失関数の意味での、ニュートン法を用いて最小化しているものとみなすことができる。同様にReal AdaBoostはマージンの指数損失関数を逐次的に最適化する回帰モデルとみなすことができる。

そして、LogitBoostは、Newton法によりadditive modelを最尤化（log-likelihoodを最大化）するアルゴリズムとして提案されている。

AdaBoostにおいて、なんで訓練データのDistributionをe/(1-e)をかけて更新し、weak learnerのウェイトをlog{(1-e)/e}にするのか、理論的な背景もわかる（これはAdaBoostの一番初めの論文をまだ見てないので、そこに書いてあるのかもしれない）。確かに上述の、マージンの指数損失関数をNewton法で最小化するときに一致する。

後半はマルチクラスへの拡張である。こちらはまだ十分わかったとはいえない。

AdaBoost.M1,AdaBoostM2は次を参照。

Experiments with a New Boosting Algorithm - Freund, Schapire (ResearchIndex)

http://citeseer.ist.psu.edu/freund96experiments.html

Real AdaBoostはこちらを。AdaBoost.MH, AdaBoost.MO, AdaBoost.MRという、マルチクラス対応したバージョンも乗っている。それぞれ、Hamming loss, Output coding, Ranking lossに基づくマルチクラスへの拡張版、となっている。

Improved Boosting Algorithms Using Confidence-rated Predictions

http://portal.acm.org/citation.cfm?id=337870&coll=Portal&dl=GUIDE&CFID=12943902&CFTOKEN=29884119