For x - 中川研究室

機械学習勉強会 2010.5.13
Semi-Supervised Learning with the
Graph Laplacian: The Limit of
Infinite Unlabelled Data
東京大学中川研究室
楊斌
1
紹介する論文
• Semi-Supervised Learning with the Graph
Laplacian: The Limit of Infinite Unlabelled
Data (B. Nadler, N. Srebro, X. Zhou NIPS
2009)
2009/2/19
2
AGENDA
1 問題設定
2 連続化
3 一次元の場合
4 高次元の場合
5 実験
6 Fourier-Eigenvector Methods
7 まとめ
3
SSL (Semi-Supervised Learning)
• 問題設定(SSL)：
– y: Ω→Y={-1,1}
n=l+u
– l labeled points: (x1, y1),…, (xl, yl)
– u unlabeled points: xl+1,…, xl+u～ p(x) (i.i.d.)
– 目標：y(x) s.t. yi=y(xi) where i=1,2,…,l
• 本論文：
– Number of labeled points: l 固定
– Number of unlabeled points: u→∞
– 学習結果の評価（p(x)が与えられた時）
2009/2/19
4
Graph Laplacian Regularization
• [15] Semi-Supervised Learning Using
Gaussian Fields and Harmonic Functions
(X. Zhu et al ICML 2003)
– G(V, E)
– 類似度行列 W={wij}
– wij:ノードi, jの類似度
|| xi  x j ||
– e.g.
wij  G (
)

where G ( z )  e
2009/2/19
z2 2
or  ( z  1) etc.
5
Graph Laplacian Regularization
• Formulation
yˆ ( x)  arg min I n ( y ) subject to y ( xi )  yi , i  1,..., l
y
where
1
I n ( y)  2
n
n
2
w
(
y
(
x
)

y
(
x
))
 ij i
j
i , j 1
wijが大きい場合、 y(xi) = y(xj)
とは等しいことを望ましい
2009/2/19
6
AGENDA
1 問題設定
2 連続化
3 一次元の場合
4 高次元の場合
5 実験
6 Fourier-Eigenvector Methods
7 まとめ
7
連続化
• lを固定して、u→∞ （ n→∞ ）
1
I n ( y)  2
n
n
n
2
w
(
y
(
x
)

y
(
x
))
 ij i
j
i 1 j 1
lim I n ( y)  I ( ) ( y)
n 


 
2009/2/19
G(
|| x  x ||

)( y ( x)  y ( x)) 2 p( x) p( x)dxdx
8
連続化した問題設定
• σ→0、   ( log n n ) i.e.

d
lim
n 
d
C
d 2
I n ( y )  lim
 0
d
log n n
d
C
d 2
I
( )

( y)
 J ( y )   || y ( x) ||2 p ( x) 2 dx

where C   d || z ||2 G (|| z ||) dz  
R
yˆ ( x)  arg min J ( y) subject to y( xi )  yi , i  1,..., l
y
2009/2/19
9
AGENDA
1 問題設定
2 連続化
3 一次元の場合
4 高次元の場合
5 実験
6 Fourier-Eigenvector Methods
7 まとめ
10
Euler-Lagrange equation
• y: [a,b]→X
• f: [a,b]×X×TX→R
b
J ( y)   f ( x, y( x), y( x))dx
a
• yはJの最小値であるとき
d 

f ( x, y, y) 
f ( x, y, y)
dx y
y
2009/2/19
11
一次元の場合
• Labeled data: a≦x1< x2<… <xl≦b
• 各区間 x∊(xi, xi+1)
J ( y)   || y( x) ||2 p( x) 2 dx   || y( x) ||2 p( x) 2 dx

2009/2/19

12
一次元の場合
J ( y)   || y( x) ||2 p( x) 2 dx   || y( x) ||2 p( x) 2 dx


• Euler-Lagrange
b
J ( y)   f ( x, y( x), y( x))dx
a
f ( x, y, y) || y ||2 p( x) 2
d 

f ( x, y, y) 
f ( x, y, y)
dx y
y
d 2
p ( x) y  0
dx
2009/2/19
13
一次元の場合
d 2
p ( x) y  0
• Euler-Lagrange dx
2
p
( x) y  C (定数)
• 積分して
1
• 再積分 y  C  2 dx  C '
p ( x)
• 初期条件：y(xi)=yi, y(xi+1)=yi+1

y ( x)  y 

i
1 p 2 (t )dt
xi
xi 1
xi
2009/2/19
x
2
( yi 1  yi )
1 p (t )dt
14
Reproducing Kernel Hilbert Space
• 定義(Reproducing Kernel)
– f, g∊H (Hilber関数空間）
– 内積< f , g >，ノルム|| f ||=< f , f >1/2
– K(y,x) is called a reproducing kernel of H, if:
• For every x∊X, Kx(y)=K(y,x)
• For every x∊X, f∊H, f(x)=<f, Kx>
– we get:
• For x,y∊X, Kx(y)=<Kx, Ky>
• For x,y∊X, K (y, x)=<Kx, Ky>
• For x∊X, ||Kx||=<Kx, Kx>1/2=K(x, x) 1/2
2009/2/19
15
Reproducing Kernel Hilbert Space
• 定義(RKHS)
– H is RKHS, if there exists a K of H.
• カーネル関数Kが与えられた
– カーネル関数Kを内積として
– Kx(・) ( =K(・,x) )を基底として
– Hilbert空間を作る
– f(x)=ΣiaiK(x,xi)
– || f ||K=ΣijaiajK(xi,xj)
2009/2/19
16
Regularize as a RKHS
• Theorem 1:
2009/2/19
17
Regularize as a RKHS
• Proof:
2009/2/19
18
Regularize as a RKHS
• Representer Theoremにより、
• Kp：
1
K p ( x, x)  Ap 
2
2009/2/19

x
x
1
dt
2
p (t )
19
AGENDA
1 問題設定
2 連続化
3 一次元の場合
4 高次元の場合
5 実験
6 Fourier-Eigenvector Methods
7 まとめ
20
高次元の場合
1
– l=2の場合のみ証明された
– x0=0, y(x0)=0, ||x1||=1, y(x1)=1
y ( x)  min(
J ( y )  
B ( 0 )
2009/2/19
p 2 ( x)
2
dx 
|| x ||

2
pmax
2
0
-1
,1)
1
2
d 2
dx

p
V

max d

0
B ( 0 )
21
高次元の場合(l >2)
• 各labeledデータに対して、yεを作る：
x1  1
y ( x)  min(
x3  1
x2  1
|| x  x1 ||

0
 1,0)
y ( x)  max( 1 
|| x  x2 ||
1

0
,0)
y ( x)  min(
|| x  x3 ||

 1,0)
0
-1
-1
1
0
-1
2009/2/19
-1
22
極限の意味
• yεの特徴：
yε
– Labeledデータの値=Label
– 他の領域はほとんど定数
1
0
-1
• Penaltyの導入：
-1
Labeled
データ数
1 l
ˆy  arg min (  ( y( x j )  y j ) 2  I n ( y))
l j 1
y( x)
=0
2009/2/19
→0
23
AGENDA
1 問題設定
2 連続化
3 一次元の場合
4 高次元の場合
5 実験
6 Fourier-Eigenvector Methods
7 まとめ
24
実験１
2009/2/19
25
実験２
2009/2/19
26
有限なσ
• なぜσ→0？
wij  G (
|| xi  x j ||

)
e.g. G ( z )  e
or  ( z  1) etc.
– σ0>0
– σの潜在的な意味は、||xi-xj||<σ0であれば、iとj
のLabelは同じ(yi=yj)であるはず。
z2 2
2009/2/19
27
AGENDA
1 問題設定
2 連続化
3 一次元の場合
4 高次元の場合
5 実験
6 Fourier-Eigenvector Methods
7 まとめ
28
Fourier-Eigenvector
• [3] Using Manifold Structure for Partially
Labeled Classification (M. Belkin et al
NIPS 2007)
• Algorithm
– 隣接行列 W={wij}
• wij=1:i, jが隣接; wij=0:i, jが隣接しない
– Lagrange行列Lの固有ベクトルの計算
• L(=D-W) , where Dii=ΣjWij
• p個の最小固有値λ1, λ2,… , λpに対応する固有ベクト
ルe1, e2,… , epを計算する
2009/2/19
29
Fourier-Eigenvector
2
Err
(
a
)

(
y

a
e
(
i
)
)
– エラー関数：
i1 i  j 1 j j
l
•
•
•
•
p
a=(a1, a2,…, ap)T：係数
y=(y1, y2,…, yl)T：Label
Elab=(e1, e2,…, ep)：l×p 行列
エラー関数を最小化：
arg min ( Err (a))  (ETlabElab ) 1 ETlaby
a
– Unlabeledデータの分類：
 1 ( p a j e j (i )  0)

j 1
yi  
p
 1 ( j 1 a j e j (i )  0)


2009/2/19
30
極限の場合
• Unlabeledデータの数l→∞
– Well-posed
– 理由：low density separation assumption
• 低密度領域で分割する
• 近似的に、区分的な定数密度関数になる
2009/2/19
31
AGENDA
1 問題設定
2 連続化
3 一次元の場合
4 高次元の場合
5 実験
6 Fourier-Eigenvector Methods
7 まとめ
32
まとめ
• [15] Semi-Supervised Learning Using
Gaussian Fields and Harmonic Functions
(X. Zhu et al ICML 2003)
– lを固定して、u→∞すると、“ill-posed”になる
– 原因：Sobolev Embedding Theoremによって、
Rdの場合、(d+1)/2次微分が必要
– 対処：L→L(d+1)/2
2009/2/19
33
再考
• σについて
   (d log n n ) i.e.

d
?
  O(d 1 n ) i.e.
lim
n 
d
C d  2
log n n

d
1n
I n ( y )  lim

M
 0
d
C d  2
I ( ) ( y )
 J ( y )   || y ( x) ||2 p ( x) 2 dx

where C   d || z ||2 G (|| z ||) dz  
R
2009/2/19
wij  G (
|| xi  x j ||

)
z2 2
e.g. G ( z )  e
or  ( z  1) etc.
34
35

Download Report