ICML2014 : A Divide-and-Conquer Solver for Kernel Support Vector Machines

はじめが肝心なので、今日はこれ。
http://jmlr.org/proceedings/papers/v32/hsieha14.pdf

概要

SVMは通常サンプル数が膨大であった場合、計算量がボトルネックとなる。

そこで分割統治SVM（DC-SVM）を開発し、複数のサブ問題に分割して独立に解くことにした。

適切なカーネルクラスタリングであれば、サブ問題から得られた解は全体の解となる確率が高いことを理論的に示した。LIBSVMを7倍のスピードで最適解を出した。

early prediction strategyを組み合わせると100倍まで高速化。

divideステップでkernel kmeansによって分割したサブ問題の解を得、

conquerステップでサブ問題の解を接着(glued)してglobal problemの初期解を決定しcoordinate descentメソッドによって最適解に収束させるらしい。

先行研究ではエレガントな分割方法はなかった！とか。Bayesian Prediction Scheme (BCM)とかがあるらしい。

目的関数をk分割すると計算量も減少。

カーネルマトリクスの固有値などから求まる値などによって、サブ問題から得られた解（双対問題）と真の解による目的関数の値の差の上限が得られる。

上のような式からある条件下では、サブ問題の解でなかったxiが全体の問題の解とならないことがわかる。らしい。

しかし小さいクラスターに分割すればするほど現実の解とはなれてしまう。

はじめは大量のクラスターに分割し、そこから得られた解をもとにもう少し大きなクラスターに対してSVMを解けばより早く収束するのではないかと筆者たちは考えた。

そこでmultiple levelの分割統治では、

l回にわけて問題をとくが、（for lmax ... 1）
毎回k^l個サンプリングしてクラスタリング→そこから得られたラグランジュ乗数αが正になっている、すなわちうまく分類できなかったというデータ点からさらにサンプリングを行い、それを繰り返す。

最終的に得られたαを初期値として、すべてのデータセットに関してSVMを解く。

という説明であっているのか。。