読者です 読者をやめる 読者になる 読者になる

#11 On transductive support vector machines

論文100本ノック

L. Wang, X. Shen, and W. Pan.
In J. Verducci, X. Shen, and J. Lafferty, editors, Prediction and Discovery. American Mathematical Society, 2007.

この論文のmain contributionは2点。一つ目は、いくつかの仮定を置くとTSMVsはいくつかの仮定の元で通常のSVMより悪くなることはない(!!)ということが理論的に示したところ。二つ目はTSVMsのパラメータの最適化の手法としてCCCPを使った、ということ。大分好みな感じであるが、一つ目のところはProofが追い切れてないです。。。というか数式番号のところが(??)になってて追えな(ry。

TSVMsでの目的関数は(1)式なんだけど、第二項のところがhatな形をしており、全体が凸関数ではなくなってしまい最適化が困難である。これまでの研究では、分枝限定法を使ったものだとか、hatの部分を連続関数で近似してやって、せめて勾配法が使えるようにしよう、という感じでやられていた。

しかし、CCCPができたので、これをうまく使える形に変形してあげようというのがこの論文の言っているところ。第二項のところをs_1s_2に分けてあげる。それぞれは凸関数と凹関数である。残りのところは凸関数であるので、CCCPを利用して最適化のさぶるーてぃーんを回すことができるようになる。

3つほど実験がされているが、ラベルありのみからなるSVMと分枝限定法を使ったものと比較してCCCPを使ったもののほうがほとんどのデータセットで結果がよくなっている。

で、悪化せずによくなっているというのを理論的に保証してあげているのがSection 5以降。Statistical learning theory...