サポートベクトルマシン

ニューラル情報処理 第０９回

サポートベクトルマシン

Ichiro Takeuchi

Nagoya Institute of Technology

分類問題

分類問題の例題

検査番号 肥満度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

竹内 一郎, 2/25

データの２次元プロット

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)

竹内 一郎, 4/25

線形分類境界

▶ 2次元入力(x= [x₁ x₂]^⊤∈R²)の場合 f(x₁, x₂) =w₀+w₁x₁+w₂x₂ = 0

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

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

課題

1

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

f(x₁, x₂) =−230 + 4x₁+x₂ = 0

で与えられる. このとき, 以下の10点のうち, 1, 2, 6, 7 の4点におけるf(x₁, x₂)の値を計算せよ

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)

竹内 一郎, 6/25

課題

1

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)|の値は分類境界からの距離を表す

線形分離可能

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

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

竹内 一郎, 8/25

最適な分類境界は？

▶ 以下の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 + 4x₁+ 1x₂= 0 (b)−215 + 4x₁+ 1x₂= 0 (c)−232 + 4.5x₁+ 1x₂= 0

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

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

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

竹内 一郎, 10/25

課題２

線形分類境界

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

と正しく分類されているi 番目の学習データ点(x_i1, x_i2) と の距離が

y_i(w₀+w₁x_i1+w₂x_i2)

√w²₁+w²₂

と与えられ,

y_if(x_i) =y_i(w₀+w₁x_i1+w₂x_i2) に比例することを示せ.

課題２の解答

竹内 一郎, 12/25

マージン最大化

▶ 2次元入力の場合

w0,wmax1,w2∈R

{ min

i∈{1,...,n}

[y_i(w₀+w₁x_i1+w₂x_i2)

√w²₁ +w²₂

]}

▶ d次元入力の場合

max

w0∈R,w∈R^d

{ min

i∈{1,...,n}

[y_i(w₀+w^⊤x_i)

√w^⊤w ]}

問題の変換（１）

▶ マージン最大化問題

max

w0∈R,w∈R^d

{

i∈{1,...,n}min

[y_i(w₀+w^⊤x_i)

√w^⊤w ]}

▶ マージンが最小となるデータを(xj, yj)とすると,

max

w0∈R,w∈R^d

y_j(w₀+w^⊤x_j)

√w^⊤w

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

竹内 一郎, 14/25

問題の変換（２ー１）

▶ 分類境界の方程式は定数倍しても変らない、すなわち、

w₀+w^⊤x= 0 ⇔ κ(w₀+w^⊤x) = 0

なので、最適解におけるマージンが1となるように定 数倍し、変数を

w₀ ← κw₀ w ← κw と変換する

問題の変換（２−２）

▶ マージン最大化（変換１の適用後）

max

w0∈R,w∈R^d

y_j(w₀+w^⊤x_j)

√w^⊤w

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

▶ マージンyj(w0+w^⊤xj)が１となるように定数倍：

max

w0∈R,w∈R^d

√ 1 w^⊤w

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

竹内 一郎, 16/25

問題の変換（３）

▶ マージン最大化（変換１、２の適用後）

max

w0∈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. y_i(w₀+w^⊤x_i)≥1 ∀i∈ {1, . . . , n}.

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

SVM)

min

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

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

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

竹内 一郎, 18/25

線形分離ができない場合

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

罰則

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

罰則を以下のように定義 ξ_i :=

{ 0 if y_if(x_i)≥1, 1−y_if(x_i) if y_if(x_i)<1.

竹内 一郎, 20/25

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

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は調整パラメータ)

損失関数

▶ ヒンジ損失

ℓ(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 Logistic Loss

竹内 一郎, 22/25

課題３

以下の２つの問題が等価であることを証明せよ

▶ 問題1 (ソフトマージン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}.

▶ 問題2（ヒンジ損失最小化）

min

w0∈R,w∈R^d

1

2w^⊤w+C

∑n

i=1

max{0,1−yi(w0+w^⊤xi)}

ヒント：区分線形関数の最小化

▶ 以下のような区分線形関数を最小化する問題を考える

▶ この問題は以下の制約なし最小化問題となる minz max{a₁+b₁z,a₂+b₂z, . . . ,a_k+b_kz}

▶ この問題は以下の制約あり最適化問題となる minz,t t

s.t.a₁+b₁z ≤t,a₂+b₂z ≤t, . . . ,a_k+b_kz ≤t

竹内 一郎, 24/25

課題３の解答