線形 SVM

入力空間𝜒 ∈ 𝐑^𝑛およびデータ集合𝒙₁, 𝒙₂, … , 𝒙_𝑟が与えられたとすると，線形SVMの識別関 数は次のように定義できる：

𝑓(𝐱) = 𝑠𝑖𝑔𝑛(𝑔(𝐱)) = 𝑠𝑖𝑔𝑛(𝐰^T𝐱 + 𝑏) (A.5) 関数𝑠𝑖𝑔𝑛(𝑢)は，𝑢 >0のとき1，𝑢 ≤0のとき-1をとる符号関数である．また，自由度とし て係数𝐰と𝑏をパラメータとして与えている．係数𝐰は線形識別器の重みベクトルと呼ばれ，

𝑏はバイアス項と呼ばれるパラメータである．ここで，n個の学習パターン𝐱_𝒊(𝑖 = 1,2, … , 𝑛)

の満たすべき条件を，

𝑔(𝐱) = 𝐰^T𝐱_𝒊+ 𝑏 {≥ 1 𝐱_𝒊 ∈ 𝜒₁

≤ −1 𝐱_𝒊∈ 𝜒₂ (A.6) とする．点𝐱_𝑖から平面𝑔(𝐱) = 0までの距離は|𝑔(𝐱_𝒊)| ‖𝐰‖⁄ であるから，式(A.6)は，識別関数

𝑔(𝐱) = 0から距離1 ‖𝐰‖⁄ の範囲内，すなわち平面𝑔(𝐱) = ±1の間に学習パターンが存在しな



 







H1 H²

いことを意味する．ここで，𝐱_𝑖の属するクラスを変数𝑦_𝑖で表し，

𝑦_𝑖 = {1 𝐱_𝒊 ∈ 𝜒₁

−1 𝐱_𝒊 ∈ 𝜒₂ (A.7)

と定義し，𝐱_𝑖の教師信号と呼ぶ．また𝒚 = (𝑦₁, 𝑦₂, … , 𝑦_𝑛)^𝑇とすると，式(A.6)は𝑦_𝑖を用いて，

𝑦_𝑖⋅ (𝐰^T𝐱_𝒊+ 𝑏) ≥ 1 𝑖 = 1,2, … , 𝑛 (A.8) と書ける．図A.2の平面𝐻₁, 𝐻₂間の距離(マージン)は2 ‖𝐰‖⁄ であり，これを最大にする𝑓(𝐱) は，扱いやすくするために‖𝐰‖²を考えて，式(A.8)で表現される制約関数のもと，

𝜏(𝐰) =1

2‖𝐰‖² (A.9)

を最小化することで推定できる．

図 A.2：制約付き線形識別関数

一般に，制約付きの最適化問題は，その双対問題を考えたほうがより簡単な問題に帰着 する場合が多い．そこで，この凸最適化問題を解くため，式(A.9)のラグランジュ関数を計 算する．制約条件である式(A.8)は，以下のように書き換えることができる：

1 − 𝑦_𝑖⋅ (𝐰^T𝐱_𝒊+ 𝑏) ≤ 0 (A.10) この制約条件から，以下のラグランジュ関数が導き出せる：

𝐿(𝐰, 𝑏, 𝛂) =1

2‖𝐰‖²− ∑ 𝛼_𝑖(𝑦_𝑖(𝐰^𝑡𝐱_𝑖+ 𝑏) − 1)

𝑛

𝑖=1

(A.11) ここで，𝛼_𝑖 ≥ 0はラグランジュ乗数である．最適化問題を解くには，このラグランジュ関 数を𝛼_𝑖について最大化し，𝐰と𝑏について最小化する．

最適解においては，パラメータ𝐰と𝑏についての𝐿の導関数は鞍点において，𝐿の勾配が0 となるので，次式が成立する：

𝜕

𝜕𝑏𝐿(𝐰, 𝑏, 𝛂) = 0 (A.12)

𝜕

𝜕𝐰𝐿(𝐰, 𝑏, 𝛂) = 0 (A.13)

式(A.12)から次式が成立する：

∑ 𝛼_𝑖𝑦_𝑖 = 0

𝑛

𝑖=1

(A.14) また，式(A.13)から次式が成立する：

𝐰 = ∑ 𝛼_𝑖𝑦_𝑖𝐱_𝑖

𝑛

𝑖=1

(A.15)

結局，𝐰は学習データの展開式となる．𝐰の解はただ一つに決まるが，ラグランジュ乗数𝛼_𝑖は

その必要がない．

最適解において，以下の条件が満たされる：

𝛼_𝑖[1 − 𝑦_𝑖(𝐰^𝑡𝐱_𝑖+ 𝑏)] = 0 𝑖 = 1,2, … , 𝑛 1 − 𝑦_𝑖(𝐰^𝑡𝐱_𝑖+ 𝑏) ≤ 0 𝑖 = 1,2, … , 𝑛

𝛼_𝑖≥ 0 𝑖 = 1,2, … , 𝑛

} (A.16)

これはクーン・タッカー(Kuhn-Tucker)条件と呼ばれ，ラグランジュ未定乗数法を用いた 際，成り立つ．この条件を満たし，𝛼_𝑖 ≥ 0を有する学習データ𝐱_𝑖をサポートベクターと呼

ぶ．𝛼_𝑖 = 0となるサポートベクター以外の学習データは凸最適化問題の解放には関係ない

ものとなる．つまり，サポートベクター以外の学習データは式(A.8)の制約条件を自動的に 満たし，式(A.15)の展開項の部分には現れない．

式(A.11)のラグランジュ関数に式(A.14)，式(A.15)の条件を代入すると，双対問題となる 以下の凸最適化問題を得ることができる：

目的関数 ∑ 𝛼_𝑖

𝑛

𝑖=1

−1

2 ∑ 𝛼_𝑖𝛼_𝑗

𝑛

𝑖,𝑗=1

𝑦_𝑖𝑦_𝑗(𝐱_𝑖^T𝐱_𝒋) → 𝛂について最小化

制約条件

𝛼_𝑖 ≥ 0, 𝑖 = 1,2, … , 𝑛

∑ 𝛼_𝑖𝑦_𝑖= 0

𝑛

𝑖=1

(A.17)

最適な𝛂から𝐰を得るには，式(A.15)の関係を用いる．また𝑏は 𝑏 = −1

2(𝐰^𝐭𝐱_+𝟏+ 𝐰^𝐭𝐱_−𝟏) (A.18)

で求められる．ここで，𝐱_+𝟏, 𝐱_−𝟏は，それぞれクラス 1，-1に属するサポートベクターであ る．

式(A.15)の展開式を識別関数の式(A.5)に代入することによって，式(A.5)の識別関数を，分 類されるパターンとサポートベクターとの内積で評価される次式に書き換えることができ る：

𝑓(𝐱) = 𝑠𝑖𝑔𝑛 (∑ 𝛼_𝑖𝑦_𝑖𝐱_𝑖^T𝐱_𝒋

𝑛

𝑖=1

+ 𝑏) (A.19)

以上より，凸二次計画問題を解くことで，識別関数

𝑓(𝐱) = 𝑠𝑖𝑔𝑛(𝐰^𝐭𝐱 + 𝑏) (A.20)

を得ることができる．

実際に線形SVMを実装し，識別関数の決定を行った例を図A.3に示す．

図 A.3：線形SVMによる識別結果