再生核ヒルベルト空間!!(キリッ

半教師あり学習の資料作りがあと"Manifold regularization"だけになったんだが、これがいままでより頭に入ってこない。今までの論文とかは他との差分を読めばおkというような感じだったが、差分取るもとのがない、って感じである。というわけで基礎体力が足りていない。この手のは論文じゃなくて本で勉強したほうが頭に入ってくる気がするので、この辺の本を読むことにしよう。

学習システムの理論と実現

学習システムの理論と実現

  • 作者: 渡辺澄夫,萩原克幸,赤穂昭太郎,本村陽一,福水健次,岡田真人,青柳美輝
  • 出版社/メーカー: 森北出版株式会社
  • 発売日: 2005/07/25
  • メディア: 単行本
  • 購入: 2人 クリック: 10回
  • この商品を含むブログ (9件) を見る
カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)

カーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)

再生核ヒルベルト空間

マーサーカーネルは特徴ベクトルの内積として捉えることもできるが、もっと直接的にカーネルのことを定義できないだろうか、という考えのもとで作られたのが再生核ヒルベルト空間。マーサーカーネルの固有関数の線形和で書けるような関数集合(要素が関数!)の全体を\mathcal{F}としよう。\mathcal{F}から2つ要素を取ってくる。f, g \in \mathcal{F}
f(\cdot) = \sum_{j=1}^{h} c_j \psi_j (\cdot)

g(\cdot) = \sum_{j=1}^{h} d_j \psi_j (\cdot)
とする。\mathcal{F}は関数を要素とするような集合で、その要素はマーサーカーネルの線形和で書けるものに絞るよ!ってことですね(繰り返し)。

\gamma_jの付近は学習システムの理論と実現のp48付近を見てください。次に、集合\mathcal{F}の要素間での内積を以下のように定義する(内積の公理を満たしていればよいということを思い出そう)。
\langle f, g \rangle = \sum_{j=1}^h \frac{c_j d_j}{\gamma_j}
この内積を\mathcal{F}内積と呼ぶ。カーネルk(x, y)のxを固定した関数*1\gamma_j \psi_j(x)を係数とした\mathcal{F}の要素と見なすことができる。\mathcal{F}の要素ということなので、fとカーネルのxを固定したほうとの(1変数)関数との\mathcal{F}内積を取ってみる。
\langle f, k(x, \cdot) \rangle = \sum_{j=1}^h \frac{c_j \gamma_j \psi_j(x)}{\gamma_j} = f(x)
となる(内積の結果で返ってきているのは関数fにxを適用した「スカラー」であることに注意)。fとカーネルの1変数を固定した関数を投げるとf(に値を適用した結果)が返ってくる(再生)すると言う意味で\mathcal{F}のつくるヒルベルト空間(内積が定義できて完備な空間)のことを再生核ヒルベルト空間(RKHS:reproducing kernel Hilbert space)と呼ぶ。delta関数もそういう性質があるようだ。

カーネル関数k(x, y)はこの再生性によりk(x, \cdot)k(\cdot, y)(両方とも\mathcal{F}の要素である!)との\mathcal{F}内積として考えることができる。何がうれしいかというとxの特徴ベクトルを陽に取る必要はなく、xの特徴量はカーネルの1変数を固定した関数k(x, \cdot)であって、その特徴量同士の内積は\mathcal{F}内積を考えればよい、ということである。なるほど。

*1:Haskellの関数の部分適用のイメージ

#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を求めることである。
http://www.cs.uchicago.edu/files/tr_additional/TR-2004-06.pdf
これはリプレゼンター定理を使うことにより、以下のように書くことができる。
http://www.cs.uchicago.edu/files/tr_additional/TR-2004-06.pdf
リプレゼンター定理により、問題は\alpha_iを求める問題に帰着し、fは\alpha_iとカーネルの線形和の形に限定できる、ということが分かる。

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

XとYの同時分布からYを積分消去したXの周辺分布が未知だったとしよう(既知の場合はとりあえず省略)。ここではラベルなしデータも使いたいわけで、ラベル伝播のようなことがうまく動くためにはラベルの変化はスムーズ(近くにいるラベルは同じラベルである確率が高い)であることを要求する。近くのノードのラベルの差の二乗にエッジの重みをかけたものを目的関数に入れてあげると問題は以下のように定式化できる。
http://www.cs.uchicago.edu/files/tr_additional/TR-2004-06.pdf
すぐ予想がつくけど、グラフラプラシアンな形に持っていける。
http://www.cs.uchicago.edu/files/tr_additional/TR-2004-06.pdf
ここではsmoothnessの制約としてグラフラプラシアンを入れたが、他のものでもできる(p8のRemark 1。拡散カーネルっぽいのもあったり)。さて、この論文ではこの関数を最小にするようなfはリプレゼンター定理の拡張のような形
http://www.cs.uchicago.edu/files/tr_additional/TR-2004-06.pdf
で書けると述べている(証明関係はSection 3)。すごく綺麗である。

アルゴリズム

Laplacian Regularized Least Squres(LapRLS)

4章は具体的に\alpha_iのようなパラメータをどのように求めていくか、というような話である。Regularized Least Squaresの付近はカーネル多変量解析―非線形データ解析の新しい展開 (シリーズ確率と情報の科学)にも書かれている付近の話なので飛ばす。これをグラフラプラシアンに拡張したLaplacian Regularized Least Squres(LapRLS)はclosed formで書けて
http://www.cs.uchicago.edu/files/tr_additional/TR-2004-06.pdf
とできる。\gamma_I = 0と置けばRegularized Least Squresと同じになるので、(当たり前だけど)自然な拡張になっていることが分かる。

Laplacian Support Vector Machines

ラベルありのみからなるSVMは省略。前に自分が書いたノートがあった。

Laplacian Support Vector Machinesも似たような感じである。ただ、\alpha\betaの関係式が
http://www.cs.uchicago.edu/files/tr_additional/TR-2004-06.pdf
と若干複雑になっている。\beta^{*}を求めるためにはQPを解かないといけないのはSVMと同じであるが、若干複雑になっている。