Evidence Contrary to the Statistical View of Boosting

Evidence Contrary to the Statistical View of Boosting
David Mease, Abraham Wyner; 9(Feb):131--156, 2008.

AdaBoostは強力な学習アルゴリズムである。しかも、2000年代になって、Additive Modelという統計モデルの上で論じられ、なぜAdaboostやその派生アルゴリズムが良好なのか、解析が進んできた。学習を繰り返しても過学習を起こさない、といわれてきたが、その後の研究で、その反例がいくつも報告されているように、未解明な問題も残っている。この論文では、弱学習器には決定木よりもDecision Stumpの方がよい、決定木の場合に多数学習を繰り返すと過学習を起こす、指数損失よりも二項対数尤度最小化の方がよい、学習回数を打ち切ったほうがよい、インスタンスウェイトの変更を穏やかに行うほうがよいなどの報告などは、必ずしも正しくないことをSyntheticなモデルから作られるデータを使って精密に論じる。あまりに精密で、４章はskip。

著者らの意図は、Friedmanら以来の統計モデルによる分析の限界を指摘し、別の視点からなのか、より包括的な理論に基づいてなのかはわからないが、Adaboostの研究が次の段階に進んでいくように方向付けることであるらしい。

Friedman以降のBoostingの理論的分析のよいサーベイになっていると思われるほか、RによるBoostingの実装例やこの論文で使ったサンプルコードなどもポイントしている。

Greedy Function Approximation: A Gradient Boosting Machine

Greedy Function Approximation: A Gradient Boosting Machine - Friedman (ResearchIndex)

AdaBoostやLogitBoostの枠組みでは、真の分布が未知であるために、これを訓練例を代用してある損失関数を最小化する。ところが、これは代用品に過ぎないだけでなく、たとえばノイズが多い場合には問題になりそうだと想像がつく。Gradient Boostingでは、訓練例をそのまま用いる代わりに、関数空間において最小に情報を適用し、弱学習機を設計する枠組みを与える。また、ノイズの問題だけでなく、指数損失関数以外の損失関数を採用する上でもアドバンテージがある。このような枠組みを与えた上で、least-absolute-deviationやHuber-lossや、それらを弱学習器としてRegession Treeを採用した具体的なアルゴリズムを示している。

Asymmetric Boosting

Hamed Masnadi-Shirazi, Nuno Vasconcelos, Asymmetric boosting, In Proceedings of the 24th international conference on Machine learning, 2007.

Asymmetricとは、ここではinbalanced dataとか、cost sensitive learningといった意味。AdaBoostをConst sensitive learningに拡張する。これまでに、AdaC1,　AdaC2, AdaC3 (Sun et al., 2005), CSB0, CSB1, CSB2 (Ting, 2000),　AdaCostなどが提案されてきたが、インスタンスウェイトの更新や最急降下法のふり幅の決め方をヒューリスティックに補正したものにとどまっていた。

提案のAsymmetric AdaBoostでは、非対称なコストが与えられたときに、このコストの元でのベイズの誤り確率に近づけるという基準（このアイディアがこの論文の最大のポイント）で、インスタンスウェイトの更新とふり幅を決めるという、理論的裏づけを持ったアルゴリズムである。オリジナルのAdaBoostは、（コストが対象な）ベイズの誤り確率に近づける（＝指数損失関数を使う）ので、これの自然な拡張となっている。そのため、コストを対象にした場合、Asymmetric AdaBoostはおのずからAdaBoostと同じになる。

さらに、Cost sensitiveであることを人工的なデータで裏付けたり、AdaBoostと同様に、training errorが下がりきった後でも、test errorが低下するというLarge margin classifierの特性を引き継いでいることを実験で示している上、精度も従来手法を上回り、安定性もよい。

論文の構成もよく、読みやすい。

Transductive Inference for Text Classification using Support Vector Machines

Transductive Inference for Text Classification using Support Vector Machines - Joachims (ResearchIndex)

テキスト分類へのSVMの応用、SVMlight等で有名なJoachimsの論文。ICML1999のBest Papersにも選ばれている。

Transductive Learningを簡単に定義すると、h:x->yはtraining data:{(x,y)}とtest data:{(x*,y*)}では同一。しかしp(x)とp(x*)が異なる。この下で、エラーを最小化する問題だと定義する。

提案するAlgorithm TSVMのアイディアは、

1. training data: {x, y}を用いてquadratic programmingを解き、これにより得られた仮説h0によるtest dataの分類結果を初期割り当て{(x*,y*)}とする。
2. エラー最小となるよう割り当て{(x*,y*)}を変更し、この割り当てと{(x,y)}を用いて、SVMで学習を行う。
3. 再び得られた仮説hによるtest dataの分類結果を割り当て{(x*,y*)}とする。
4. 結果が収束するまで2～3を繰り返す。

最適解を得るためには、可能な{(x*,y*)}の割当をすべて試し、エラー最小とする割り当てに対するSVMでの学習結果を仮説hとするべきだろうが、計算量が多すぎる。そのための回避方法。ちゃんと読んでないのだが、山登りをどうやるか、というところには工夫があるとは言っていない。既知の探索問題の解放を適用することも可能だろう。

この論文のcontributionは、TSVMアルゴリズムそのものというより、Transductive Learningをシンプルに定式化し、結果が良好ということ？アルゴリズム自体に凄さみたいなものはあまり感じないのだが。なお、わかりやすさという点でも、とても優れた論文だと思う。例がわかりやすいし、どのような判別関数を学習したいのか、直感的に良くわかる。

それよりも、TSVMではSVMlightを使っているのだが、SVMlightが解く最適化問題(OP3 Inductive SVM (primal))のほうが面白そう。なので、次の論文も興味がある。

T. Joachims, 11 in: Making large-Scale SVM Learning Practical. Advances in Kernel Methods - Support Vector Learning, B. Schölkopf and C. Burges and A. Smola (ed.), MIT Press, 1999.

Boosting for Transfer Learning

Wenyuan Dai, et. al, Boosting for Transfer Learning, ICML2007.

少しの新しい学習データがあれば、Adaboostを借りて、古い学習データの中から使えるものを選び出す（高いウェイトをつける）、という方法。前半のIterationでは新しい学習データを強化し、後半で新しい分布に対しても有用な古い学習データを強化する。PACの枠組みで、理論的な裏づけも当然ある。構成とわかりやすさがよい。ページが限られており、詳細な定理の証明はないが、直感的にどういうことなのかの説明が特にわかりやすかった。

実験はSVMをweak leanerとした本手法と、SVMを比較している。これがちょっと首をかしげた。斜め読みなのではずしているかもしれないが、weaklearnerとboostingを戦わせるのって意味があるの？Adaboostと戦わせる、という流れなのかと思ったが違う。weak learnerにSVMを使うって、実用上どうなのか？

追記：まず、比較はSVM vs. TrAdaBoostだけでなく、TSVM vs. TrAdaBoostもやっている。SVMとの比較では、確かにweak learnerとの比較には疑問があるのだが、次のように述べている。「Transductive Learningでは、必ずしも汎化誤差を小さくしない場合があるため、SVMと比べてみた」。汎化誤差を必ずしも小さくしないことは、次の論文で研究されている。

R. Caruana, Multitask learning, Machine Learning, 28(1), pp101--126, 1997.

またTSVMとの比較では、確かにTSVMよりもいい結果を出している。TrAdaBoostでは、新しい分布上での学習データも学習時に利用するが、この条件でもそう。ただ、TrAdaBoostは、新しい分布の学習データが不可欠な点は注意。だが、これ自体悪くはない。そういう仮定の下で、上手に問題を解く、と言う方向性はあり。

2007 ICML: Accepted Papers

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

関連エントリ：
本のフロク: Experiments with a New Boosting Algorithm - Freund, Schapire
http://inakoshi.cocolog-nifty.com/booksblog/2007/01/experiments_wit.html

Experiments with a New Boosting Algorithm - Freund, Schapire

Experiments with a New Boosting Algorithm - Freund, Schapire (ResearchIndex)
http://citeseer.ist.psu.edu/freund96experiments.html

1996年現在の実験を中心にまとめた論文。Weak learner(FindAttrTest, FindDecRule, C4.5)と、アンサンブル学習アルゴリズム（Adaboost.M1, Adaboost.M2, Bagging）の組み合わせをUCI ML Repositoryのデータと手書き数字認識へ適用し、評価・比較を行っているのが主要なContribution。

Adaboost.M1とAdaboost.M2のアルゴリズムと、training errorのupper boundを与える定理がピシッとまとまっている。定理の証明はfull paperを。

A Decision-Theoretic Generalization of on-Line Learning and an Application to Boosting - Freund, Schapire (ResearchIndex)
http://citeseer.ist.psu.edu/89601.html

Adaboost.M2はError Correcting Output Coding (ECOC)の視点を得て、拡張されている。

Using Output Codes to Boost Multiclass Learning Problems - Schapire (ResearchIndex)
http://citeseer.ist.psu.edu/4853.html

ECOCはこちらを。

Solving Multiclass Learning Problems via Error-Correcting Output Codes - Dietterich, Bakiri (ResearchIndex)
http://citeseer.ist.psu.edu/dietterich95solving.html

Learning a kernel function for classification with small training samples

Learning a kernel function for classification with small training samples
http://portal.acm.org/citation.cfm?id=1143895

Boosting margin based distance functions for clustering
http://portal.acm.org/citation.cfm?id=1015389

Boostingのテクニックを用いてカーネル学習を行うsemi-supervised learning。Boostingを使うので、学習するカーネルはweak kernel（後述）の線形結合になる。weak kernelとは、誤解されやすい言葉だが、Boostingのweak learnerのように、線形結合されるもの、というくらいの意味。weak kernelに何を使うか、という選択肢に関しては、制約つきEMを解くことによって得られるノンパラメトリックなカーネルを使う。つまり、Boostingによってインスタンスの分布を更新しながら、制約つきEMを解くことによって得られるカーネルの線形結合を、最終的なカーネルとする。

制約つきEMは、インスタンスとクラスラベルのペアを教師データとするのではなく、インスタンスのペアが同じGaussian Distributionに基づいて発生した、というインスタンスのproduct spaceに関する情報を教師データとして、それを守るようなGaussian Distributionを定式化し、EMアルゴリズムでそれをとく、という手法らしい。引用論文を後でチェックするつもり。

マハラノビス距離を学習する方法ともうひとつ（忘れた）が、semi-supervised learningおよびクラスタリングにおける距離関数の学習法として主流らしいが、実験によればこの手法はそれらをしのぐ非常によい結果を出している。だが、一編目の論文にある手法ですら上に述べたように、いろいろな手法の組み合わせでできていて複雑だし、Boostingを使っている、といっても繰り返し回数を固定で打ち切るようなことをしていて、アルゴリズム的に完成系という感じではない。今後、理論的な裏づけがなされていくのだろうか？複雑なのでうまく理論的な解析ができるのかよくわからない。

二編目のほうは、semi-supervised learning以外に、retrievalの実験が結構よくて、一編目の技術だけではカバーできないようなケース（インスタンスの分布がそもそもGaussianにならないようなケース）に対応する拡張はしていて、進歩はしているのだが、アイディア・テクニックの面白さはすべて一編目にあるような感じ。

これらの論文を軸にして、semi-supervised learningの最近の研究を洗っていけると楽しそう。