Transductive Inference for Text Classification using Support Vector Machines
テキスト分類への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のアイディアは、
- training data: {x, y}を用いてquadratic programmingを解き、これにより得られた仮説h0によるtest dataの分類結果を初期割り当て{(x*,y*)}とする。
- エラー最小となるよう割り当て{(x*,y*)}を変更し、この割り当てと{(x,y)}を用いて、SVMで学習を行う。
- 再び得られた仮説hによるtest dataの分類結果を割り当て{(x*,y*)}とする。
- 結果が収束するまで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.
