データマイニングと機械学習-SVM

分類問題2:
サポートベクターマシン
⼭本祐輔
静岡⼤学情報学部准教授
[email protected]
第6回データマイニングと機械学習 2023
2023年5月31日

View Slide

講義のトピック
機械学習
教師あり学習
教師なし学習強化学習
・クラスタリング
・データ圧縮
・分類
・回帰
…
…
3
行動情報学科に
特有の応用手法
時系列データ分析
時間経過とともに変化する
データに対する分析⼿法
・K近傍法
・サポートベクタマシン
・ニューラルネットワーク

View Slide

K-近傍法（k-NN: k nearest neighbor）のアイデア
4
対象データまでの距離が最も近いK個のデータの
ラベルのうち、最も多いラベルに分類する
？
K=5:⻘
K=3:緑
K=1:⻘
多数決

View Slide

K-近傍法のメリット・デメリット
5
メリット
• 単純なのに強⼒
• データの背後にある分布を仮定しなくてよい
（ノンパラメトリックな⼿法）
デメリット
• 推論フェーズの計算量が⼤きい（毎回の距離計算）
• 次元の呪いの影響を受けやすい

View Slide

教師あり学習のための機械学習アルゴリズムの分類
6
ロジスティック回帰
ナイーブベイズ
K近傍法
ランダムフォレスト & 決定木
ニューラルネットワーク
訓練データをすべて記憶して
おき，それら全部を使って
予測を⾏う（推論計算が遅い）
訓練データの背後にあるモデル
を抽出し，それを予測時に使う
（推論計算は速い）
インスタンスベースモデルベース
本⽇学ぶのはコレ

View Slide

1 一世を風靡した学習アルゴリズム
7

View Slide

教師あり学習の歴史（⼀部抜粋）
ロジスティック回帰
決定木
パーセプトロン
単純ベイズ分類器
ランダムフォレスト
k-近傍法
ベイジアンネットワーク
深層学習
1958年
1957年
1951年
1979年
1985年
1992年
1960年代
2001年
2010年代
8
⼀世を⾵靡した強⼒なアルゴリズム．
深層学習が台頭した今でも，状況に
よっては⽤いられることも．

View Slide

サポートベクターマシン（SVM）
入力
・ベクトルデータ
・正則化係数 !
・カーネル関数 "
学習
by SVM
9
それほど多くないデータでも精度よく推論したい時に有効
ID
血圧
（上）
喫煙
頻度
年齢
心臓
疾患
1 110 5 74 なし
2 160 17 53 あり
… … … … …
⼼臓疾患データ
学習済み
モデル
ML
血圧 … 疾患
124 ？
未知データ
推論⼼臓疾患あり
出力
ラベル（基本的には2値）

View Slide

2次元平⾯上で考える分類問題
●と×のデータ集合が与えられたときに，
未知の2次元データが●か×をどう予測する？
Q.
X
0
Y
?
▲
?
▲
10

View Slide

●と×のデータを2分するような直線を見つける
A.
X
0
Y
?
▲
?
▲
直線より下側なら「●」
直線より上側なら「×」
ax+by+c=0
11

View Slide

●と×のデータを2分するような直線を見つける
A.
X
0
Y
直線といっても複数考えられる…どれがベストか？
A
B
C
12

View Slide

機械学習の⾄上命題
13
機械学習
汎化性能の高い
予測モデルの構築
未知データに対する予測性能を⾼める必要あり
（訓練データに最適化しすぎても意味がない（過学習））

View Slide

X
0
Y
▲
▲
▲
▲
学習に使用したデータは
真の分布を完全に表現しているとは限らない
▲
▲
できる限り未知のデータにも対応できる直線にしたい… 14

View Slide

X
0
Y
A
B
C
未知のデータがどこに出現するか分からない状況で
未知データが●か×かを予測するベスト直線は？
Q.
15

View Slide

X
0
Y
A
Q.
16
B

View Slide

X
0
Y
B
Q.
17

View Slide

X
0
Y
C
Q.
18
B

View Slide

X
0
Y
直線に最も近い訓練データから直線までの距離
（マージン）が最大となるような直線がベスト！！
A.
19
B

View Slide

X
0
Y
A
20
A.

View Slide

X
0
Y
C
21
A.

View Slide

サポートベクター
（直線に最も近い点）
サポートベクターマシンの直感的なアイデア
X
0
Y
マージンを最大化する超平面を見つける
（分類境界とサポートベクターの距離）
!(#) = 0
（直線に最も近い点）
22

View Slide

数学的準備：超平⾯の数式表現（1/2）
23
x
y
x
y
z
2次元空間での直線
!" + $% + & = 0 !" + $% + &) + * = 0
3次元空間での平⾯

View Slide

数学的準備：超平⾯の数式表現（2/2）
24
x1
2次元空間での直線
+#"# + +$"$ + +% = 0 '!
(!
+ '"
("
+ ⋯ + '#
= 0
N次元空間での超平⾯
x2
! = ($!
, $"
)
？
x1
x2
xN
ベクトルwとxの内積
w=(w1
, w2
)
※ 実は wは法線ベクトル
⟹ -&
. + +% = 0

View Slide

数学的準備：2次元空間での点と直線間の垂直距離
25
x1
直線: '!
$!
+ '"
$"
+ '#
= 0
x2 ($!
′, $"
′)
+ =
|'!
(!
$ + '"
("
$ + '#
|
'!
" + '"
"
⾼校で習った公式
L

View Slide

数学的準備：N次元空間での点と超平⾯の間の距離
26
|(!)!
"
+ ⋯ + (#)#′ + ($|
(!
%
+ ⋯ + (#
%
=
|-%#$ + '#
|
-
x1
x2
xN
!$ = ($!
$ , $"
$ , … , $%
′) + =
L
直線: ,&! + '#
= 0
ベクトルで表現
(- ! = ,&! + '#
)
=
|!(#)|
-

View Slide

サポートベクターマシンの定式化: 設定
X1
0
Xn
N次元空間上の点 ! : " ! = (%
"
! , … , %#
(!))
点 ! のラベル値 y(!) = *
1
−1
… 点 . が×の場合
… 点 . が●の場合
27

View Slide

サポートベクターマシンの定式化: 設定
X1
0
Xn
N次元空間上の点 ! : " ! = (%
"
! , … , %#
(!))
点 ! のラベル値 y(!) = *
1
−1
… 点 . が×の場合
… 点 . が●の場合
y = −1の点
y = 1の点
28

View Slide

サポートベクターマシンの定式化 : ⽬標設定(1/2)
X1
0
Xn
点 1 について y(')
= 1 の場合，2(4 '
) ≥ 1
y(')
= −1の場合，2 4 '
≤ −1
目標1: 以下を満たす 2(4) を見つけたい
! # = 0
(& ' = )!'" + +#
)
29

View Slide

サポートベクターマシンの定式化 : ⽬標設定(2/2)
X1
0
Xn
目標2: 2(4) のマージンを最大化させたい
! # = 0
(& ' = )!'" + +#
)
×で - ! に
最も近い点 /
●で - ! に
最も近い点 .
0' 0(
⟹ argmax
8
49
+ 4:
30

View Slide

サポートベクターマシンの最適化問題を解く
点 ! について y(") = 1 の場合，%(' " ) ≥ 1
目標1: 以下を満たす !(#) を見つけたい
目標2: !(#) のマージンを最大化させたい
⟹ argmax
8
49
+ 4:
… 式(1)
… 式(2)
y(") = −1の場合，% ' " ≤ −1
31

View Slide

点 ! について y(") = 1 の場合，%(' " ) ≥ 1
y(") = −1の場合，% ' " ≤ −1
⟹ argmax
8
49
+ 4:
… 式(1)
… 式(2)
⟹ argmax
&, ()
|!(#(*))|
-
+
|!(# , )|
-
点と超平⾯間の距離公式
32

View Slide

点 ! について y(") = 1 の場合，%(' " ) ≥ 1
y(") = −1の場合，% ' " ≤ −1
⟹ argmax
8
49
+ 4:
… 式(1)
… 式(2)
式(1)より
≥ argmax
&, ()
1
-
+
1
-
= argmax
&, ()
2
-
(& ' = )!'" + +#
)
⟹ argmax
&, ()
|!(#(*))|
-
+
|!(# , )|
-
33

View Slide

点 ! について y(") = 1 の場合，%(' " ) ≥ 1
y(") = −1の場合，% ' " ≤ −1
⟹ argmax
8
49
+ 4:
… 式(1)
… 式(2)
≥ argmax
&
1
-
+
1
-
= argmax
&
2
- ⟹ argmin
&, ()
-
2
逆数の最⼩化と等価
34

View Slide

点 ! について y(") = 1 の場合，%(' " ) ≥ 1
y(") = −1の場合，% ' " ≤ −1
⟹ argmax
8
49
+ 4:
… 式(1)
… 式(2)
≥ argmax
&
1
-
+
1
-
= argmax
&
2
- ⟹ argmin
&
-
2 2乗を最⼩化
しても同じ
⟹ argmin
&
- "
2
35

View Slide

サポートベクターマシンの最適化問題：問題設定の変形
点 ! について y(") = 1 の場合，%(' " ) ≥ 1
y(") = −1の場合，% ' " ≤ −1
⟹ argmax
8
49
+ 4:
… 式(1)
… 式(2)
⟹ argmin
;
- $
2
… 式(3) 最⼩化問題!!
SVMの最適化は不等式制約下の最小化問題に帰着される
（不等式制約）
36

View Slide

数理最適化の定⽯
37
（不）等式制約下での
関数最小化
ラグランジュの未定乗数法

View Slide

サポートベクターマシンに関する最適化問題の最終形
38
<(=(!)
, … , =(#)
) = @
'*!
#
=(')
−
1
2
@
'*!
#
@
+*!
#
=(')
=(+)
B(')
B(+)
4 ' ,
4(+)
∑
123
4 "(1)#(1) = 0 および "(3) …, "(5) ≥ 0 の条件下で
を最⼤化する " 1 を⾒つける(ただし ; = ∑'*!
#
=(')
B(')
4('))
(. = 1, … , 7)
ベクトルの内積

View Slide

サポートベクターマシンの最適化を例で考える（1/4）
X1
0
X2
! # = 0
(& ' = +$
,$
+ +%
,%
+ +#
)
' $ = (3, 4)
' % = (1,2)
' & = (2, 6)
学習データとして2次元のデータが3つ与えられたとし，
SVMを適用して最適な分離境界線を見つけたい
39
(* ! = 1)
(* " = 1)
(* # = −1)

View Slide

40
<(=(!)
, =(%)
, =(-)
) = @
'*!
-
=(')
−
1
2
@
'*!
-
@
+*!
-
=(')
=(+)
B(')
B(+)
4 ' ,
4(+)
ただし , = 8(!)$(!) − 8 " $ " + 8(/)$(/) = 38 ! − 8 " + 28(/)
48 ! − 28 " + 68(/)
+
=(!)
− = %
+ =(-)
= 0 および =(!)
, =(%)
, =(-)
≥ 0 の条件下で
以下の関数F を最⼤化したい

View Slide

41
=(!)
− = %
+ =(-)
= 0 および =(!)
, =(%)
, =(-)
+
= −
25
2
= ! %
−
5
2
=(%) %
− 20 =(-) %
+11=(!)
=(%)
+ 14= %
= -
− 30= -
= !
− = !
+ = %
− =(-)
< = !
, = %
, = -

View Slide

微分などを駆使し，各変数についてFを最⼤化すればよい
42
=(!)
− = %
+ =(-)
= 0 および =(!)
, =(%)
, =(-)
= −
25
2
= ! %
−
5
2
=(%) %
− 20 =(-) %
+11=(!)
=(%)
+ 14= %
= -
− 30= -
= !
− = !
+ = %
− =(-)
< = !
, = %
, = -
9(: ! ) = … : ! "
+ … :(!) + …
変数1つに着⽬すれば…単なる2次関数!!
いわゆる
2次計画問題！

View Slide

理想世界でのサポートベクターマシン
X1
0
Xn
1
,
マージンの外側でデータの分布がキレイに分かれる
!(#) = 0
この領域には
データはない
43

View Slide

サポートベクターマシンを使う現実的な状況
X1
0
Xn
ノイズ1
ノイズ2
ノイズ3
学習で使うデータにノイズが混入する
44

View Slide

サポートベクターマシンを使う現実的な状況
X1
0
Xn
ノイズ1
ノイズ2
ノイズ3
<-
<"
学習で使うデータにノイズが混入する
ノイズを考慮してサポートベクターマシンを修正したい… 45

View Slide

サポートベクターマシン with ハードマージンの最適化問題
点 ! について y(") = 1 の場合，% ' " ≥ 1
y(") = −1の場合，% ' " ≤ −1
⟹ argmin
;
- $
2
46

View Slide

サポートベクターマシン with ソフトマージンの最適化問題
点 ! について y(") = 1 の場合，% ' " ≥ 1 − ,"
y(") = −1の場合，% ' " ≤ −(1 − ,")
⟹ argmin
;
- $
2
+ 8 9
9I#
J
:9
反対側に⾏っても
認めてあげる (3 ≥ 0)
反対側に⾏った分は
ペナルティを与える
47

View Slide

サポートベクターマシン with ソフトマージンに関する最適化問題の最終形
48
<(=(!)
, … , =(#)
) = @
'*!
#
=(')
−
1
2
@
'*!
#
@
+*!
#
=(')
=(+)
B(')
B(+)
4 ' ,
4(+)
∑
123
4 "(1)#(1) = 0 および ∀*, "(1), +(1) ≥ 0 の条件下で
#
=(')
B(')
4(')
,
(. = 1, … , 7) ∀., ? = 8 ' + @ ' , @ ' A ' = 0)

View Slide

Hands-on タイム
以下のURLにアクセスして，
サポートベクターマシンを体験してみましょう
https://dmml2023.hontolab.org/
49

View Slide

2 「トリック」を使う
非線形SVM
50

View Slide

線形分離不可能な問題
51
X
0
Y
どうやっても1つの直線で分離できないデータ分布がある
線形分離不可能

View Slide

線形分離不可能な問題の解決策
52
X
0
Y
0 X
Y
Z = X2+Y2
複数の直線（超平面）を
組み合わせる
高次元化された空間で
分離超平面を見つける

View Slide

データの⾼次元化の例
53
! = ($!
, $"
)
!# = (1, 2$!
, 2$"
, 2$!
$"
, $!
", $"
")
: 2次の多項式に写像（変換）
;(.)
線形分離不能なデータも
高次元化すればSVMで分類しやすくなる

View Slide

⾼次元化対応のサポートベクターマシンの最適化問題（1/2）
点 ! について y(!) = 1 の場合，- .(" ! ) ≥ 1 − 0!
y(!) = −1の場合，- .(" ! ) ≤ −(1 − 0!)
⟹ argmin
!
( "
2
+ + ,
#$%
&
-#
⾼次元化関数
をかます
X
0
Y
0 X
Y
Z
マージン
最⼤化
⾼次元空間
に B で写像
54

View Slide

⾼次元化対応のサポートベクターマシンの最適化問題（2/2）
55
<(=(!)
, … , =(#)
) = @
'*!
#
=(')
−
1
2
@
',+*!
#
=(')
=(+)
B(')
B(+)
K(4 '
)!K(4(+)
)
∑
123
4 "(1)#(1) = 0 および ∀*, "(1), +(1) ≥ 0 の条件下で
#
=(')
B(')
4(')
,
∀., ? = 8 ' + @ ' , @ ' A ' = 0)
⾼次元化された

View Slide

⾼次元空間の内積計算は⼤変
56
. = ("#, "$)
? = (%#, %$)
;L . = 1, 2"#, 2"$, 2"#"$, "#
$
, "$
$
;L(?) = (1, 2%#, 2%$, 2%#%$, %#
$
, %$
$
)
: 2次の多項式に写像（変換）
;L(.)
内積計算
;L . &
;L ?
= 1 + 2(!
=!
+ 2("
="
+ 2(!
("
=!
="
+ (!
"=!
" + ("
"="
"
2次元ベクトルでも1ペアの内積計算でのかけ算回数が11回に…
これではSVMの学習の
計算コストが膨大に…

View Slide

カーネルトリック
57
. = "#, "$ , ? = (%#, %$)
!!
", $ = 1 + "" ( $ #
= 1 + )$
*$
+ )#
*#
#
= 1 + 2%"
4"
+ 2%6
46
+ 2%"
%6
4"
46
+ %"
64"
6 + %6
646
6
= +!
" "+!
$
かけ算回数 = 2 + 1 回
式展開
が与えられたとき
カーネル関数を使えば，明示的に
高次元変換しなくても効率よく内積を計算できる
多項式変換したベクトルの内積と同じに!!

View Slide

最適化⽅法は線形SVMと全く同じ（記号が変わっただけ）
カーネルトリックを使った⾮線形SVMの最適化問題
58
<(=(!)
, … , =(#)
) = @
'*!
#
=(')
−
1
2
@
',+*!
#
=(')
=(+)
B(')
B(+)
K/(4 '
)!K/(4(+)
)
∑
123
4 "(1)#(1) = 0 および ∀*, "(1), +(1) ≥ 0 の条件下で
#
=(')
B(')
4(')
,
∀., ? = 8 ' + @ ' , @ ' A ' = 0)
多項式カーネルで計算簡略化
= @
'*!
#
=(')
−
1
2
@
',+*!
#
=(')
=(+)
B(')
B(+)
"/(4 '
, 4(+)
)

View Slide

代表的なカーネル関数 for SVM
59
A(., ?) = & + .&
B ? M
A(., ?) = C
N 4NO $
$P$
多項式カーネル動径基底カーネル
・⼊⼒ベクトルの成分の組合せを
成分とする⾼次元ベクトルを想定
・⽂書分類タスクでよく⽤いられる
（パラメータd=2）
・無限次元空間にベクトルを射影
・最もよく⽤いられるカーネル．
分布の特徴が未知の時に使う
・ガウスカーネルと呼ばれることも
Radial Basis Function
画像出典: https://scikit-learn.org/stable/auto_examples/svm/plot_iris_svc.html

View Slide

サポートベクターマシンの⻑所・短所
60
• ⾼次元空間でも汎化性能が⾼い
• 次元数に対して学習データ数が
少なくても性能を発揮
• 計算量が多い（DNNほどではない）
• データ数に対して次元数がかなり
⼤きいと，過学習が起きる
• パラメータが少ない（DNNよりは）
※ DNN = Deep Neural Network

View Slide

Hands-on タイム
以下のURLにアクセスして，
非線形SVMを体験してみましょう
https://dmml2023.hontolab.org/
61

View Slide

今後の予定
62

View Slide

今後の予定
63
回実施⽇トピック
1 04/12 ガイダンス
2 04/19 機械学習の概要 & はじめての機械学習
3 04/26 演習：決定⽊
4 05/10 クラスタリング1：k-means & 階層的クラスタリング
5 05/17 クラスタリング2：密度ベースクラスタリング
6 05/24 分類1：K近傍法 & 教師あり機械学習のお作法
7 05/31 分類2：サポートベクターマシン
8 06/07 分類3：ニューラルネットワーク⼊⾨

View Slide

数学記号（集合）
64
集合（太字でない⼤⽂字アルファベット）
)
集合の要素（太字でない⼩⽂字アルファベット）
*
, = -$
, -#
, … , -%
= ) ) ∈ 0 ∧ 2 ) > 0}
外延表現：要素を並べる書き⽅
内包表現：要素の条件を指定する書き⽅
（xが実数でかつ f (x)がゼロより⼤きくなるようなxの集合）
集合の書き⽅
集合の⼤きさ（要素数） |)|

View Slide

例
65
6 = 0, 1, 2, …
8 = … , −2, −1, 0, 1, 2, …
: = 2n + 1 | n ∈ 6
（⾃然数）
（整数）
（奇数）
= = りんご, みかん, なし
|=| = 3

View Slide

数学記号（ベクトル）
66
!
ベクトル（太字の⼩⽂字）
断りがない限り，縦ベクトル
. $ = "#
$
+ ⋯ + "Q
$
ベクトルの要素の書き⽅
実数を成分とする
m次元ベクトル
. =
"#
⋮
"Q
∈ GQ
= "#, … , "Q
&
ベクトルの⼤きさ
! と書くことも
. B ? = .&
? = ∑ "R%R
!, C と書くことも

View Slide

数学記号（⾏列）
67
⾏列（太字の⼤⽂字）
? =
)$$
⋯ )%$
⋮
)&$
⋱
⋯
⋮
)&%
∈ 0&×%
Dの各列（縦ベクトル）
を使った書き⽅
実数を成分とする
m⾏ n 列の⾏列
= )() &×% こんな書き⽅も
= "$
, … , "%
!
⾏列の
要素の書き⽅

View Slide

機械学習でよく⾒かける数学的処理（1/3）
68
9
9I#
S
"9 = "# + "$ + ⋯ + "S
J
9I#
S
"9 = "#"$ … "S
C
C)*
2(")
数列の和
数列の積
偏微分
T 4 = (!)! + (%)% + ⋯ + (0)0
例:
U
U)0
T 4 = (0

View Slide

69
argmax
$∈&
1($)
argmin
'∈&
1($)
max
'∈&
1($)
min
'∈&
1($)
関数を最⼤化
関数を最⼩化
実数の範囲でパラメータxを
動かし関数f(x)を最⼤化・最⼩化
関数を最⼤化する
パラメータ
関数を最⼩化する
パラメータ
関数を最適化する
実数を⾒つける

View Slide

70
sign $ = 5
1: $ > 0
0: $ = 0
−1: $ < 0
符号関数
値の符号に応じて
・正なら1
・負なら-1
・ゼロなら0
を返す関数と覚える
画像出典: https://ja.wikipedia.org/wiki/符号関数
(sgn % と書くことも)

View Slide

機械学習でよく出くわす瞬時に理解すべき数式
71
>.! % = >/ .!
>? % = ?/>/
@
*
'*
(*
= -/#
Matrix Cookbook: http://www2.imm.dtu.dk/pubdb/edoc/imm3274.pdf
A
A#
# " =
A
A#
#/# = 2#
A
A#
B# = B/
A
A#
-/# = -
A
A#
# − D " = 2(- − D)
A
A#
># − E " = 2>/(># − E)
> + ? % = >/ + ?/

View Slide

⾏列サイズの⾒積もり
72
⾏列A はm⾏ k列（m×k），⾏列B はk⾏ n列（k×n），
⾏列 Wはm⾏ m列（m×m），ベクトルxは m⾏ 1列（m×1）
とする．このとき以下の演算結果のサイズは？
Q1. ;(!
Q2. !(Q3. !(! スカラー
スカラー
(k×1)の⾏列（k次元ベクトル）
（m×k）の⾏列と（k×n）の⾏列の積をとると，
（m×n）の⾏列ができあがると覚えておけばよい

View Slide

データマイニングと機械学習-SVM

データマイニングと機械学習-SVM

Y. Yamamoto

More Decks by Y. Yamamoto

Other Decks in Technology

Featured

Transcript