#12 Manifold regularization: A geometric framework for learning from examples (Technical Report TR-2004-06)

Belkin, M., Niyogi, P., & Sindhwani, V. (2004b).
University of Chicago.

さあ、準備は整った。いざゆかん再生核の世界へ(謎。

概要

正則化を使った新しい半教師あり学習のフレームワークのようなものをproposeする。これはSVMや正則化付き二乗和誤差最小化のようなものをspecial caseとして得ることができるものである。再生核ヒルベルト空間を利用し、新しい形のリプレゼンテーション定理を構築した。これによるアルゴリズムはtransductiveなものも真の意味でのsemi-supervisedなものも扱うことができる。

注目すべき点としては

「近くにある点は同じラベルに違いない」という制約を正則化ありの学習に組み込んだ
組み込んだ場合に、ラベルなしデータありの半教師あり学習にリプレゼンター定理が拡張できることを示し、それをうまく活用している
パラメータを変えることで、様々なアルゴリズムと等価なものを作り出すことができ(Table 2)、半教師あり学習の統一的な考え方を示していると考えることができる

という付近かな。

普通の正則化付きの学習

復習から入る。扱いたい学習は、以下のような損失関数と正則化項を最小にする関数fを求めることである。

これはリプレゼンター定理を使うことにより、以下のように書くことができる。

リプレゼンター定理により、問題は $\alpha_i$ を求める問題に帰着し、fは $\alpha_i$ とカーネルの線形和の形に限定できる、ということが分かる。

Xの周辺分布が未知のとき

XとYの同時分布からYを積分消去したXの周辺分布が未知だったとしよう(既知の場合はとりあえず省略)。ここではラベルなしデータも使いたいわけで、ラベル伝播のようなことがうまく動くためにはラベルの変化はスムーズ(近くにいるラベルは同じラベルである確率が高い)であることを要求する。近くのノードのラベルの差の二乗にエッジの重みをかけたものを目的関数に入れてあげると問題は以下のように定式化できる。

すぐ予想がつくけど、グラフラプラシアンな形に持っていける。

ここではsmoothnessの制約としてグラフラプラシアンを入れたが、他のものでもできる(p8のRemark 1。拡散カーネルっぽいのもあったり)。さて、この論文ではこの関数を最小にするようなfはリプレゼンター定理の拡張のような形

で書けると述べている(証明関係はSection 3)。すごく綺麗である。

アルゴリズム

Laplacian Regularized Least Squres(LapRLS)

4章は具体的に $\alpha_i$ のようなパラメータをどのように求めていくか、というような話である。Regularized Least Squaresの付近はカーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)にも書かれている付近の話なので飛ばす。これをグラフラプラシアンに拡張したLaplacian Regularized Least Squres(LapRLS)はclosed formで書けて

とできる。 $\gamma_I = 0$ と置けばRegularized Least Squresと同じになるので、(当たり前だけど)自然な拡張になっていることが分かる。