Mathematical Foundation of Statistical Learning

情報学習理論
渡辺澄夫
東京工業大学
深層学習
ニューラルネットワーク
ボルツマンマシン
教師なし学習
教師あり学習
自己組織化
競合学習
サポートベクタマシン
教師あり学習の枠組み
学習データ
X1, X2, …, Xn
Y1, Y2, …, Yn
q(x,y)
f(x,w)
テストデータ
情報源
X
Y
学習モデル
サポートベクトルマシン(SVM)
カテゴリ識別の問題
(xi,yi) i =1,2,…,n
N
xi ∈ R
yi = 1 or –1
カテゴリに対応
SVM2
1
N
x∈R
H
φ(x)∈R
sgn(t) =
1 (t≧0)
-1 (t<0)
y = sgn(w・φ(x)+b)
w, b, φ(x) をどのように決めるか?
-1
y
SVM3
H
R
マージンを最大にする
w b を選ぶことにする
y=w・φ(x)+b
SVM4
双対問題を解くことにより 最適な (w,b) は
サポートベクトルに関する係数 {ai} を用いた
和で表される
w = Σ aiyiφ(xi)
b = yi- w・φ(xi)
(ai>0となる任意のiについて)
識別を行う関数は次のものになる
y = sgn( Σ ai yi φ(xi)・φ(x) + b )
パターンの識別
パターンA
パターンB
もしも二つのパターンの分布がわかっていれば
誤識別を最小にする境界を見つけるのは難しくない
カテゴリ識別のための従来方法
高次元データ
特徴量を計算して低次元に移す
パターンA
パターンB
優れた特徴量を探し出せるかどうかが問題だった
カテゴリ識別のための現代方法
高次元データ
遥かな高次元へ移して
線形分離できるようにする
マージン最大化により
識別境界を作る。
最適な識別ではないが
実問題で極めて強力。
SVMの応用
文字・画像の認識
遺伝子解析
WWWページの識別
応用多数
学習する対象についての知識を持たなくても
知識を持つ場合と同等以上の精度が実現される
こともある。
SVMの応用2
SVMのように情報空間を他の空間に移動してから
処理を行なう型の学習モデルをカーネルマシンという。
高次元空間の中のデータを扱う場合には有効である
ことが多い。
カーネル(1)
カーネル関数
N
x∈R
H
φ(x)∈R
としてどのようなものが最適であるかは
わかっていない。
計算量を減らすためのφは提案されている
カーネル(2)
カーネル関数の例 : 多項式カーネル
φ
2
R
½
6
R
½
½
φ(x1,x2) = (1, 2 x1, 2 x2, x12, x22, 2 x1x2)
カーネル(3)
カーネルトリック
½
φ(x1,x2) = (1, 2 x1, 2
½
x2, x12,
2,
½
x 2 2 x 1x 2)
φ(x1,x2) ・φ(y1,y2)
= 1 +2x1y1+2x2y2 +x12y12+x22y22 +2x1x2y1y2
= { 1+ (x1y1+x2y2) }
2
= { 1+ (x1,x2)・(y1,y2) }
2
R6 の空間の内積がR2の内積で計算できる
カーネル(4)
φ(x) ・φ(y) = { 1+ (x・y)}
2
R6 の空間の内積がR2の内積で計算できるので
新しいデータ x についても
w・φ(x) +b = Σ αiyiφ(xi)・ φ(x) + b
= Σ αiyi { 1+ (xi・x) }2 + b
ここで Σ はサポートベクトルの和。識別関数は
y = sgn( w・φ(x) +b )
= sgn( Σ αiyi { 1+ (xi・x) }2 + b )
問1
SVMが、もともとの空間にどのような識別境界を
作るかを考えてみよう。
φ(x,y) = (x2,y2,x)
w = (1,a,2)
とする。 a が -∞<a<∞を動くとき、集合
{(x,y) ∈R2 ; w ・φ(x,y) = 0 }
はどのように変わるか.
ガウスカーネル(1)
カーネル関数の他の例 : ガウス・カーネル
定数 β>0 とし、α=(2β)1/2 とおく。
N
R
φ(x) =
e-β||x||2 (1,
φ
R
∞
αx αx αx αx αx
αx,
,
, …, … )
1/2
1/2
6
2
は直積を表す
ガウス・カーネル(2)
このとき
φ(x) =
e-β||x||2 (1,
αx αx αx αx αx
αx,
,
1/2
61/2
2
φ(y) =
e-β||y||2 (1,
αy αy αy αy αy
αy,
,
,…)
1/2
1/2
6
2
,…)
なので、内積は (α2=2βを用いて)
φ(x)・j(y)
= e-β||x||2 e-β||y||2
× (1+ 2β (x・y) +(2β (x・y))2/2+ (2β (x・y))3/6+・・・)
= exp(-β||x||2)exp(-β||y||2)exp(2βx・y)=exp(-β||x-y||2)
ガウス・カーネル(3)
1
N
x∈R
H
φ(x)∈R
-1
y
ガウスカーネルで識別を行う関数は
y = sgn( Σ ai yi φ(xi)・φ(x) + b )
= sgn( Σ ai yi exp( -β||x-xi||2)+ b )
定数 β によって識別の方法が変わる。
(注)これは、実は昔からある神経回路網の一種・・・
問2
βの大きさ
サポート
ベクトル数
識別境界
の複雑さ
未知データ
正答率
1
5
25
125