線形サポートベクトルマシン

機械学習論

線形サポートベクトルマシン

線形モデルとカーネルモデル

▶ 特徴ベースモデル（線形モデル）

f(x;w) =w₁x₁+w₂x₂+. . .+w_dx_d

▶ 事例ベースモデル（カーネルモデル）

f(x;α) =α1k(x,x1) +α2k(x,x2) +. . .+αnk(x,xn)

▶ スパースモデリング

▶ 特徴スパースモデル

{wˆ_j}^dj=1の多くが０となるモデル：特徴jが不要

▶ 事例スパースモデル

{αˆ_i}ⁿi=1の多くが０となるモデル：事例iが不要

I. Takeuchi, ML 2/36

Part1

２クラス分類問題とマージン最大化

分類問題

分類問題の例題

検査番号 肥満度x₁ 血圧x₂ 健康/糖尿病y

1 31.0 150 +1

2 19.0 160 +1

3 28.0 120 +1

4 31.0 170 +1

5 29.0 120 +1

6 20.0 100 −1

7 18.0 130 −1

8 24.0 110 −1

9 15.0 150 −1

10 15.0 110 −1

I. Takeuchi, ML 4/36

データの２次元プロット

80 100 120 140 160 180 200

10 15 20 25 30 35 40

Blood Pressure (BP)

Body Mass Index (BMD)

線形分類境界

80 100 120 140 160 180 200

10 15 20 25 30 35 40

Blood Pressure (BP)

Body Mass Index (BMD)

I. Takeuchi, ML 6/36

線形分類境界

▶ 2次元入力(x= [x1 x2]^⊤∈R²)の場合

f(x₁, x₂) =w₀+w₁x₁+w₂x₂= 0

▶ d次元入力(x∈R^d)の場合

f(x) =w₀+w^⊤x= 0

分類境界の関数値

▶ 右図の分類境界の方程式は

f(x1, x2) =−230 + 4x1+x2= 0

で与えられる. このとき,以下の10点のうち, 1, 2, 6, 7の4点に おけるf(x1, x2)の値を計算してみよう

ID x1 x2 y 1 31.0 150 +1 2 19.0 160 +1 3 28.0 120 +1 4 31.0 170 +1 5 29.0 120 +1 6 20.0 100 −1 7 18.0 130 −1 8 24.0 110 −1 9 15.0 150 −1

10 15.0 110 −1 ⁸⁰

100 120 140 160 180 200

10 15 20 25 30 35 40

Blood Pressure (BP)

Body Mass Index (BMD)

I. Takeuchi, ML 8/36

計算結果

ID x1 x2 y f

1 31.0 150 +1 +44 2 19.0 160 +1 +06 3 28.0 120 +1 +02 4 31.0 170 +1 +64 5 29.0 120 +1 +06 6 20.0 100 −1 −50 7 18.0 130 −1 −28 8 24.0 110 −1 −24 9 15.0 150 −1 −20

10 15.0 110 −1 −60 ⁸⁰

100 120 140 160 180 200

10 15 20 25 30 35 40

Blood Pressure (BP)

Body Mass Index (BMD)

▶ f(x)の符号（正/負）は分類境界のどちら側かを表す

▶ |f(x)|の値は分類境界からの距離を表す

線形分離可能

▶ すべてのデータ点に対して以下を満たす超平面が存在するとき線 形分離可能という:

yi=−1 ⇒ f(xi)<0, y_i= +1 ⇒ f(x_i)>0.

I. Takeuchi, ML 10/36

最適な分類境界は？

▶ 以下の3つの分類境界はすべてのデータ点を正しく分類している が..

80 100 120 140 160 180 200

10 15 20 25 30 35 40

Blood Pressure (BP)

Body Mass Index (BMD)

80 100 120 140 160 180 200

10 15 20 25 30 35 40

Blood Pressure (BP)

Body Mass Index (BMD)

80 100 120 140 160 180 200

10 15 20 25 30 35 40

Blood Pressure (BP)

Body Mass Index (BMD)

(a)−230 + 4x1+ 1x2= 0 (b)−215 + 4x1+ 1x2= 0 (c)−232 + 4.5x1+ 1x2= 0

マージンとマージン最大化

▶ データ点と分類境界の符号付距離をマージンという

▶ すべてのデータ点のうち、分類境界に最も近いデータ点のマージ ンをデータ全体のマージンと呼ぶこともある

I. Takeuchi, ML 12/36

演習問題１

線形分類境界

f(x₁, x₂) =w₀+w₁x₁+w₂x₂= 0

と正しく分類されているi番目の学習データ点(xi1, xi2)との距離が y_i(w₀+w₁x_i1+w₂x_i2)

√w₁²+w₂²

と与えられ,

y_if(x_i) =y_i(w₀+w₁x_i1+w₂x_i2)

に比例することを示せ.

演習問題１の解答

I. Takeuchi, ML 14/36

マージン最大化

▶ 2次元入力の場合 max

w0,w1,w2∈R

{ min

i∈{1,...,n}

[yi(w0+w1xi1+w2xi2)

√w²₁+w²₂

]}

▶ d次元入力の場合 max

w0∈R,w∈R^d

{ min

i∈{1,...,n}

[yi(w0+w^⊤xi)

√w^⊤w ]}

▶ 線形分類境界からの符号付距離をマージンと呼ぶ マージン ∝ y_if(x_i) =y_i(w₀+w^⊤x_i)

Part2

二次計画問題としての定式化

I. Takeuchi, ML 16/36

二次計画問題

▶ 二次計画問題（二次関数を線形制約のもとで最小化）：

min

z₁,...,z_m∈R

∑m

k=1

∑m

ℓ=k

a_kℓz_kz_ℓ+

∑m

k=1

b_kz_k

s.t.

∑m

k=1

c_1kz_k+d₁≤0,

...

∑m

k=1

chkzk+dh≤0

二次計画問題（行列・ベクトル表現）

▶ 行列，ベクトル（mはパラメータの次元数，hは制約数）

m×mA =







a₁₁ · · · a_1m

.. .

.. .

.. .

am1 · · · amm





, b m×1=





 b₁

.. . bm





, C h×m=







c₁₁ · · · c_1m ..

. ..

. .. . c_h1 · · · c_hm





, d h×1=





 d₁

.. . dm







▶ ニ次計画問題の行列・ベクトル表現

I. Takeuchi, ML 18/36

二次計画問題の例題

▶ 以下の（等式制約の）二次計画問題を解け

zmin₁,z₂ −z₁z₂ s.t. z₁+z₂= 1

メモ１

演習問題２

▶ マージン最大化問題 max

w₀∈R,w∈R^d

{ min

i∈{1,...,n}

[y_i(w₀+w^⊤x_i)

√w^⊤w ]}

が以下の二次計画問題に変換できることを示せ min

w₀∈R,w∈R^d w^⊤w

s.t. y_i(w₀+w^⊤x_i)≥1 ∀i∈ {1, . . . , n}.

I. Takeuchi, ML 20/36

演習問題２（ヒント１）

▶ マージン最大化問題 max

w0∈R,w∈R^d

{ min

i∈{1,...,n}

[yi(w0+w^⊤xi)

√w^⊤w ]}

において，マージンが最小となるデータを(x_j, y_j)とすると，

max

w0∈R,w∈R^d

yj(w0+w^⊤xj)

√w^⊤w

s.t. y_i(w₀+w^⊤x_i)≥y_j(w₀+w^⊤x_j) ∀i∈ {1, . . . , n}.

演習問題２（ヒント２）

▶ 分類境界の方程式は定数倍しても変わらないので，最適化問題 max

w0∈R,w∈R^d

yj(w0+w^⊤xj)

√w^⊤w

s.t. yi(w0+w^⊤xi)≥yj(w0+w^⊤xj) ∀i∈ {1, . . . , n}.

をマージン

y_j(w₀+w^⊤x_j) = 1

となるようにw₀とw を定数倍すると，

max

w₀∈R,w∈R^d

√ 1 w^⊤w

s.t. y_i(w₀+w^⊤x_i)≥1 ∀i∈ {1, . . . , n}.

I. Takeuchi, ML 22/36

演習問題２（ヒント３）

▶ 最適化問題 max

w₀∈R,w∈R^d

√ 1 w^⊤w

s.t. y_i(w₀+w^⊤x_i)≥1 ∀i∈ {1, . . . , n}.

の目的関数を２乗して逆数をとると，

min

w0∈R,w∈R^d w^⊤w

s.t. yi(w0+w^⊤xi)≥1 ∀i∈ {1, . . . , n}.

ハードマージンサポートベクトルマシン（ SVM)

min

w₀∈R,w∈R^d w^⊤w

s.t. y_i(w₀+w^⊤x_i)≥1 ∀i∈ {1, . . . , n}.

（線形分離可能な場合に適用可能）

I. Takeuchi, ML 24/36

Part3

ソフトマージンサポートベクトルマシン（SVM）

線形分離ができない場合

線形分離可能 線形分離不能

I. Takeuchi, ML 26/36

罰則

▶ マージンが1となるようにスケールを調整したので、罰則を以下 のように定義

ξi:=

{ 0 ifyif(xi)≥1, 1−yif(xi) ifyif(xi)<1.

ソフトマージン SVM

▶ ハードマージンSVM min

w0∈R,w∈R^d w^⊤w

s.t. y_i(w₀+w^⊤x_i)≥1 ∀i∈ {1, . . . , n}.

▶ 罰則と緩和（ソフトマージンSVM）

min

w0∈R,w∈R^d,{ξi∈R}ⁿi=1

1

2w^⊤w+C

∑n

i=1

ξi

s.t. y_i(w₀+w^⊤x_i)≥1−ξ_i, ξ_i≥0 ∀i∈ {1, . . . , n}.

(C >0はチューニングパラメータ; cf. クロスバリデーション)

I. Takeuchi, ML 28/36

SVM の損失関数表現

▶ （ソフトマージン）SVMは以下のように表現できる：

( ˆw0,w) = arg minˆ

w0,w

∑n

i=1

ℓ(yi, f(xi)) +λ∥w∥²2

ただし，ℓ(y_i, f(x_i))はヒンジ損失関数：

ℓ(yi, f(xi)) = max{0,1−yif(xi)}

0 0.5 1 1.5 2 2.5 3 3.5 4

-3 -2 -1 0 1 2 3

loss

LogisticHinge Loss

SVM とロジスティック回帰分析の損失関数

▶ ヒンジ損失

ℓ(y_if(x_i)) = max{0,1−y_if(x_i)}

▶ ロジスティック損失

ℓ(y_if(x_i)) = log(1 + exp(−y_if(x_i)))

0 0.5 1 1.5 2 2.5 3 3.5 4

-3 -2 -1 0 1 2 3

loss

LogisticHinge Loss Logistic Loss

I. Takeuchi, ML 30/36

演習問題３

▶ SVMが

wmin₀,w

∑n

i=1

max{0,1−yif(xi)}+λ∥w∥²2

と表され，L₂正則化付きロジスティック回帰分析（y_i∈ {−1,+1} の場合）が

wmin₀,w

∑n

i=1

log(1 + exp(−y_if(x_i))) +λ∥w∥²2

と表されることを示せ．ただし，

f(x_i) =w₀+w^⊤x_i

SVM に関するヒント：区分線形関数の最小化

▶ 区分線形関数

▶ 区分線形関数の最小化（制約なし最適化表現）

minz max{a1+b1z,a2+b2z, . . . ,ak+bkz}

▶ 区分線形関数の最小化（制約付き最適化表現）

minz,t t

s.t.a1+b1z≤t,a2+b2z≤t, . . . ,ak+bkz≤t

I. Takeuchi, ML 32/36

ロジスティック回帰分析に関するヒント

▶ ロジスティック回帰分析の学習＝尤度最大化（yi∈ {0,1}表現）

max

w∈R^d

∑n

i=1

(

y_ilog 1

1 + exp(−w^⊤xi)+ (1−y_i) log exp(−w^⊤x_i) 1 + exp(−w^⊤xi)

)

において，yi∈ {−1,+1}の表現では，事後確率が P(yi= +1|xi) = 1

1 + exp(−yiw^⊤xi) と書ける

演習問題３の解答

I. Takeuchi, ML 34/36

まとめ

まとめ

▶ SVMはマージン最大化の考え方に基づいて導出された

▶ SVMは二次計画問題として定式化される

▶ SVMは正則化付きの損失関数最小化問題としても定式化できる

I. Takeuchi, ML 36/36