機械学習論 Lec06
カーネルサポートベクトルマシン
Part1
カーネルを用いた双対表現
線形モデルとカーネルモデル
▶
特徴ベースモデル：モデルの主表現（Primal Representation）f (x; w) = w 1 x 1 + w 2 x 2 + . . . + w d x d
▶
事例ベースモデル：モデルの双対表現（Dual Representation)f (x; α) = α 1 k(x, x 1 ) + α 2 k(x, x 2 ) + . . . + α n k(x, x n )
双対表現とカーネル関数
▶
事例ベースモデル：モデルの双対表現（Dual Representation)f (x; α) = α 1 k(x, x 1 ) + α 2 k(x, x 2 ) + . . . + α n k(x, x n )
▶
カーネル関数：２つの事例x i
とx i
′ の類似度を表す関数k(x i , x i
′)
カーネル行列とカーネルベクトル
▶
カーネル行列K ∈ R n × n
K =
k(x 1 , x 1 ) k(x 1 , x 2 ) · · · k(x 1 , x n ) k(x 2 , x 1 ) k(x 2 , x 2 ) · · · k(x 2 , x n )
.. . .. . . . . .. . k(x n , x 1 ) k(x n , x 2 ) · · · k(x n , x n )
∈ R n × n
▶
任意のx ∈ R n
に対するカーネルベクトルk(x) ∈ R n
k(x) =
k(x, x 1 ) k(x, x 2 )
.. . k(x, x n )
∈ R n
内積カーネル
▶
最も基本的なカーネル関数：内積カーネル関数k(x i , x i
′) = x ⊤ i x i
′▶
内積カーネルの場合のカーネル行列K = XX ⊤
▶
内積カーネルの場合のカーネルベクトルk(x) = X x
リッジ回帰分析の双対表現
▶
リッジ回帰分析E(w) = 1
2 (y − Xw) ⊤ (y − Xw) + λ 2 w ⊤ w
▶
双対変数α ∈ R n
の導入α = 1
λ (y − X w)
▶
最適性条件∂E(w)
∂w = 0 ⇔ − X ⊤ (y − Xw) + λw = 0
⇔ w = X ⊤ 1
λ (y − X w) = X ⊤ α
目的関数の双対表現
▶
リッジ回帰分析の目的関数E(w) = 1
2 (y − Xw) ⊤ (y − Xw) + λ 2 w ⊤ w
は，双対変数
α
と内積カーネル行列K
を用いて以下のように表さ れるE(α) = 1
2 α ⊤ (KK + λK)α − (Ky) ⊤ α + 1 2 y ⊤ y
メモ１
モデルの双対表現
▶
線形モデルf (x; w) = w 1 x 1 + . . . + w d x d
は，双対変数
α
と内積カーネルベクトルk(x)
を用いて以下のよ うに表されるf (x; α) = α ⊤ k(x) = α 1 k(x, x 1 ) + . . . + α n k(x, x n )
メモ２
カーネルを用いた線形モデルの拡張
▶
カーネル関数を内積カーネルから他のものへ換えることにより線 形モデルを拡張でき，これをカーネル法（kernel method
）と呼ぶ▶
他の一般的なカーネルの例▶ （q次）多項式カーネル
k(x, x ′ ) = (x ⊤ x ′ + 1) q
▶ ガウシアンカーネル
k(x, x ′ ) = exp (
− ∥ x − x ′ ∥ 2 2
2s 2 )
▶
文字列カーネル，グラフカーネルなど，ベクトル表現できない構 造データに対するカーネルも多数あり演習問題１
▶
以下のような特徴変換を考える[ x 1 x 2
] 7→ ϕ
√ 1 2x 1
√ 2x 2
x 2 1 x 2 2
√ 2x 1 x 2
２次の多項式カーネルが以下のように表されることを示せ．
k(x, x ′ ) = (x ⊤ x ′ + 1) 2 = ϕ(x) ⊤ ϕ(x ′ )
#
多項式カーネルは特徴空間ϕ(x)
における内積を表すものと解釈できる演習問題１の解答
ϕ(x) ⊤ ϕ(x ′ ) = 1 + 2x 1 x ′ 1 + 2x 2 x ′ 2 + x 2 1 + x ′ 1 2 + x 2 2 + x ′ 2 2 + 2x 1 x ′ 1 x 2 x ′ 2 .
(1 + x 1 x ′ 1 + x 2 x ′ 2 ) 2 = 1 + 2x 1 x ′ 1 + 2x 2 x ′ 2 + x 2 1 + x ′ 1 2 + x 2 2 + x ′ 2 2 + 2x 1 x ′ 1 x 2 x ′ 2 .
Part2
カーネルSVM
サポートベクトルマシン（ SVM ）
▶
ハードマージンSVM min
w
0∈R ,w ∈R
dw ⊤ w
s.t. y i (w 0 + w ⊤ x i ) ≥ 1 ∀ i ∈ { 1, . . . , n } .
▶
ソフトマージンSVM min
w
0∈R ,w ∈R
d, { ξ
i∈R}
ni=11
2 w ⊤ w + C
∑ n i=1
ξ i
s.t. y i (w 0 + w ⊤ x i ) ≥ 1 − ξ i , ξ i ≥ 0 ∀ i.
主 SVM 問題
▶
主SVM
モデルf (x) = w 0 + w ⊤ x
▶
主SVM
モデルの学習min
w
0∈R ,w ∈R
d, { ξ
i∈R}
ni=11
2 w ⊤ w + C
∑ n i=1
ξ i
s.t. y i (w 0 + w ⊤ x i ) ≥ 1 − ξ i , ξ i ≥ 0 ∀ i.
双対 SVM 問題
▶
双対SVM
モデルf (x) = α 0 +
∑ n i=1
α i y i x ⊤ x i
▶
双対SVM
モデルの学習min
α ∈R
n1 2
∑ n i=1
∑ n j=1
α i α j y i y j x ⊤ i x j −
∑ n i=1
α i
s.t.
∑ n i=1
α i y i = 0, 0 ≤ α i ≤ C, ∀ i.
カーネル SVM
▶
双対SVM
モデルf (x) = α 0 +
∑ n i=1
α i y i k(x, x i )
▶
双対SVM
モデルの学習min
α ∈R
n1 2
∑ n i=1
∑ n i
′=1
α i α i
′y i y i
′k(x i , x i
′) −
∑ n i=1
α i
s.t.
∑ n i=1
α i y i = 0, 0 ≤ α i ≤ C, ∀ i.
双対変数 α i とマージンの関係
双対変数 α i とマージンの関係
双対変数 α i とマージンの関係
双対変数 α i とマージンの関係
双対変数 α i とマージンの関係
双対変数 α i とマージンの関係
SVM の最適性条件
▶
双対変数α i
とマージンの関係マージンの外側
y i f (x i ) > 1 α i = 0
マージン上y i f (x i ) = 1 0 ≤ α i ≤ C
マージンの内側y i f (x i ) < 1 α i = C
▶
サポートベクトルと非サポートベクトル▶ 双対モデル
f (x) = α 0 +
∑ n i=1
α i y i k(x i , x)
▶ マージンの外側にあるデータは
α i = 0
なので分類境界f
に 影響を与えない．▶
SVM
は事例に対するスパース性を持つ（一部の事例のみを 保持しておけばよい）（余談）研究紹介
-2 -1 0 1 2
-3 -2 -1 0 1 2
x2
x1
Before safe screening
Toy Data (n = 1000 and d = 2)
（余談）研究紹介
[
[
Before safe screening
Toy Data (n = 1000 and d = 2)
（余談）研究紹介
-2 -1 0 1 2
-3 -2 -1 0 1 2
x2
x1
[
[
Before safe screening After safe screening
Toy Data (n = 1000 and d = 2)
（余談）研究紹介
[
[
[
[
Before safe screening After safe screening
Toy Data (n = 1000 and d = 2)
（余談）研究紹介
[
[
[
[
Before safe screening After safe screening
Toy Data (n = 1000 and d = 2)
（余談）研究紹介
[
[
[
[
Before safe screening After safe screening Toy Data (n = 1000 and d = 2)
Optimality is guaranteed even if we remove some samples.
演習問題２
▶ SVM
はマージンy i f (x i )
が1
より大きい事例は分類境界に影響を 与えない事例スパース性を有している．一方，ロジスティック回帰 分析はそのような性質を有していない．両者の損失関数の違いに 基づいてこのような違いが生じるのか説明せよ．0 0.5 1 1.5 2 2.5 3 3.5 4
-3 -2 -1 0 1 2 3
los s
Logistic Hinge Loss
Logistic Loss
演習問題２の解答
Part2
SVM
の学習（SMOアルゴリズム）カーネル SVM の双対問題
▶ y i , y i
′ もまとめ,以下の行列Q
を導入するQ
n × n
:=
y 1 y 1 k(x 1 , x 1 ) · · · y 1 y n k(x 1 , x n ) .. . . . . .. . y n y 1 k(x n , x 1 ) · · · y n y n k(x n , x n )
▶ SVM
双対最適化問題α min ∈R
n1 2
∑ n i=1
∑ n i
′=1
α i α i
′Q ii
′−
∑ n i=1
α i
s.t.
∑ n i=1
α i y i = 0, 0 ≤ α i ≤ C, ∀ i.
SMO アルゴリズム
▶ Sequential Minimal Optimization (SMO) Algorithm 1: while optimality conditions are NOT satisfied do 2: for h = 1, . . . , n do
3: update α h with the other variables { α i } i ̸ =h fixed 4: end for
5: end while
▶ LASSO
のShooting
アルゴリズム同様，１変数の最適化を繰り返すSVM の１変数の最適化
▶ 1
個の双対変数α h
に関する最適化問題min
α
h∈R
1 2
∑ n i=1
∑ n j=1
α i α j Q ij −
∑ n i=1
α i
s.t. 0 ≤ α i ≤ C, ∀ i.
が以下のように整理できる：
min
α
h∈R
1
2 Q hh α 2 h −
1 − ∑
i ̸ =h
Q hi α i
α h
s.t. 0 ≤ α h ≤ C.
演習問題３
▶ SMO
アルゴリズムのステップ３のα h
の更新式がα h =
C if C < (1 − ∑
i ̸ =h Q hi α i )/Q hh
0 if 0 > (1 − ∑
i ̸ =h Q hi α i )/Q hh
(1 − ∑
i ̸ =h Q hi α i )/Q hh otherwise
と表されることを示せ.
演習問題３のヒント
演習問題３の解答
まとめ
