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

#27 OTL: A Framework of Online Transfer Learning

ICML 論文100本ノック

Peilin Zhao and Steven C.H. Hoi, The 27th International Conference on Machine Learning (ICML 2010), Haifa, Israel, 21-24 June, 2010.

今熱い(?)転移学習とオンライン学習を組み合せてやってみましょうというお話。homogeneousな場合とheterogeneousな場合でそれぞれアルゴリズムを提案し、誤りの個数の上界を理論的に与えている(証明はあんまり追ってないけど)。また、実験的にもよい結果が得られたよ!!という話が書いてある。

Problem Formulation

基本的にはsourceのところで学習器h(x)を、targetのところでf(x)を構築していく。ここではカーネルを使ったものを考えていて、h(x) = \sum_{s=1}^S \alpha_s y_{1_{s}} K_1(x_{1_{s}}, x)とする。マージン最大化をやりたいということで、Sはサポートベクターを表わしている。

そんでもって、target用の関数fも決めてやる必要がある。オンラインでやりたいので、t回目のiterationのfをf_tと書くことにすると、f_t(x_{2_t})の符号で予測をする。

Online Transfer Learning over Homogeneous Domains

(分布は違っていてもいいので)、sourceとtargetの集合が同じ場合を考える(こういうケースをHomogeneousというようだ)。concept driftingというのが大事な考え方になってきて、どういうものかというと

  • 最初はsourceのほうで考えている
  • 時間が経つにつれて、予測したいtarget variableが変化する

というもの。まあ、変わってはいないんだけど、iterationを時間と考えれば変化していくと考えてもよさそう。

こういう問題を解きたいときにbasicとなる考え方はensemble learningと書いてある。アンサンブル学習はよく知らないが、weak learnerを組み合せてより強力な学習器を作ろうぜというやつでboostingやバギングのようなものを含む考え方らしい。ごちゃごちゃ言うより、どういう風にやっているかを具体的に見てみると、hとfのmixtureをやっているだけということであった。で、重みをiterationで変えていく((1)式のように)。これはいいとして、重みのupdate式に謎のs_t(g)という関数が出てきて、なんでこんな形なんだと思うが、Theorem 1で誤り個数の上界を示すために恣意的にやっている(と思う)。他の形でもいいように思うが、fixするよりもいい結果が得られると(あとのほうの)実験の結果のほうでも言っているので、とりあえずこれでやっていく。そうするとTheorem 1で言っているようなMのboundが示せる(意味合いをあとで書く)。

Online Transfer Learning over Heterogeneous Domains

Heterogeneousの説明。出力Yのほうで考えている集合は一緒だが、Xのほうが異なる。sourceがtargetのsubsetになっている場合をこの論文では取り扱っている(x_{2_t} \in X_2 = R^N, R^m \subset R^n)。そして、このX_2を2分割する(x_{2_t}^{(1)} \in X_1x_{2_t}^{(2)} \in X_2 \setminus X_1)。

Heterogeneousなオンラインでは(f_t^{(1)}f_t^{(2)}に対して)co-regularizationという考え方を採用する。co-regularizationとか言われるとおぞましい感じですが、式を見たほうが分かりやすい(?)。
(f_{t + 1}^{(1)}, f_{t + 1}^{(2)}) = \mbox{argmin}_{f^{(1)} \in H_{K_1}, f^{(2)} \in H_{K_2}} \frac{\gamma_1}{2} ||f^{(1)} - f_t^{(1)}||_{H_{K_1}} + \frac{\gamma_2}{2} ||f^{(2)} - f_t^{(2)}||_{H_{K_1}} + C l_t
l_t = \left[1 - y_{2_t} \frac{1}{2} \left(f^{(1)}(x_{2_t}^{(1)}) + f^{(2)}(x_{2_t}^{(2)})\right)\right]_{+}
l_tが損失関数と考えると、普通に正則化している感じだが、f^{(1)}f^{(2)}を同時に正則化しているということでco-regularizationと呼ばれる(はず)。このco-regularizationの最小化をいかにするか?という問題があるが、それはProposition 2で示されている。閉じた形で書けるところが素晴しい。

また、Homogeneousの場合と同様に誤りのboundが示せるということがTheorem 2に書いてある。

Experimental Results

比較する手法がいくつか説明されている。

  • PA
    • sourceから全く学習しない
  • PA method Initialized with the old classifier h(PAIO)
    • hをfを初期化(かな?)
  • OTL(fixed)
    • weightをiterationで変えないで固定

実験で使っているデータはサンプル数も次元数も多くはない(特に次元数)。

Evaluation of Homogeneous OTL Tasks

カーネルの設定とかはfix。3つのデータセットで実験しているが、どれもOTLが一番Mistakeが少ない結果になっている。計算時間は一番短いPAの2-2.5倍くらいになっている。Figure 3の(c)はなんでデータ増やしてもMistakeが減らないのはなんでだろう => (b)と(c)はconcept driftを起こしているデータだから。データ数とサポートベクターの数がほとんど一致していて、denseなモデルになっている。

Evaluation of Heterogenous OTL Tasks

どれも提案手法が一番精度はよいが、Homogeneousな場合と同様にSupport Vectorの数が多く、denseなモデルになってしまうためpredictするのに時間がかかってしまうのは欠点。

その他

PAのことを詳しく追ったことがそういえばなかったので、ちょっと調査。MIRAと関係があったというか、MIRAってPAのことだったのね。