初めてのパターン認識　8章　SVM


# 8章　サポートベクトルマシン

パターン認識学習アルゴリズムの一つである

2クラス問題の線形変別するための関数を導出する

マージン最大化するのが良い　
　(クラス間距離の事)
<img width="293" alt="スクリーンショット 2019-11-13 11.32.45.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/725eeb3d-9cfd-7ecd-e62c-5bf7bfd28a18.png">


線形分離不可の場合　非線形特徴写像によって特徴空間に写像そ線形分離可能にする

そのために高次元空間内での内積計算が大変
ケーネルトリックを用いるとできます
　
今回は　V-SVMと　1クラスSVMを扱う


## 8.1 サポートベクトルマシンの導出

導出のためには最大マージンの式(7.2)を使う
↓ざっくりいうとクラス群の平均値みたいなもの
<img width="357" alt="スクリーンショット 2019-11-13 9.51.09.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/36e71f06-8852-e4cb-1cd5-4490abdbc677.png">


SVMでは標準座標系を用いる
他クラス問題では　1　対　その他　で分類することが多い

###　8.1.1最適識別超平面
クラス付き学習データ　$D_L={(t_i,x_i)}$
がどちらのクラスに属するかの分類をする

$|(w^Tx_i+b)|$は点と線の距離
どの点をとっても　マージン(K)よりは大きい
$(w^Tx_i+b)\geq K$
これをKで割って正規化
その後$t_i$を掛けて符号を考える

$t_i(w^Tx_i+b)\geq1$
と分類がまとめられる

クラス間マージンは　各クラスのデータをｗ方向に射影した長さの差の最小値
<img width="498" alt="スクリーンショット 2019-11-13 13.51.27.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/73d6946c-0302-3644-42db-a7f3da787289.png">
であたえられる

<img width="353" alt="スクリーンショット 2019-11-13 13.57.43.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/e5d1a949-0f4c-aafe-a3ed-718719dd5534.png">


$\frac{2}{||w||}$
の最大値を求める
↓
||w||
の最小値を求める
$t_i(w^Tx_i+b)\geq1$を条件とする

### 8.1.2 KKT条件

この最小化問題を解くために　ラグランジュ関数を使う

条件↓の時(移項して0 =の形にする)
$0=g(x,y)$
$f(x,y)$の最小値は
$f(x,y)-g(x,y)$
となる

<img width="399" alt="スクリーンショット 2019-11-19 12.47.36.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/c047a530-8a48-2d63-c218-e4bfb788d01a.png">

となる


<img width="609" alt="スクリーンショット 2019-11-19 13.07.05.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/5ba629da-0945-9746-29ce-65a4705ac227.png">
∇　なぶら

特に５つ目の式は制約条件に対する者である

式8.7を書き換える

<img width="599" alt="スクリーンショット 2019-11-19 14.00.31.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/8b943f26-435c-8e88-e469-514179dd7576.png">

が得られる　

<img width="485" alt="スクリーンショット 2019-11-19 14.34.04.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/4f48744a-c97b-e971-632a-c122041a671e.png">

制約条件　KTTの2から得ている
制約条件とは　この問題が相対問題となる条件である。


$t_i(w^Tx_i+b)=1 $
のときにサホートベクトル（マージンを考える点）である。
サポートベクトルだけあれば計算ができる
サポートベクトルの平均をとったりすると良い

1個目は式8.8
<img width="603" alt="スクリーンショット 2019-11-19 20.18.00.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/946b2f63-6431-8be0-342a-c5b8e6dd54d2.png">


## 8.2　線形分離可能でない場合の拡張


主問題　KKT条件　双対問題がこんな感じに変わる
<img width="475" alt="スクリーンショット 2019-12-03 18.02.28.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/6abf9b80-ebe1-f1de-c046-60ff0a24820d.png">

<img width="401" alt="スクリーンショット 2019-12-03 18.04.15.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/d6162502-5c16-9395-61ae-2fcfd1006ff7.png">


## 8.3 非線形写像
　
例えばXORは線形識別できない
これを線形識別するために　非線形写像する。

イメージ図　線形識別できていないものが
非線形写像によって識別可能になる。
<img width="275" alt="スクリーンショット 2019-12-03 18.54.38.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/1a3ae599-96f5-244f-2392-a154959ea429.png">


${φ(x_j)}^M_1$
を写像とする

<img width="543" alt="スクリーンショット 2019-12-03 19.11.36.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/a531bb9d-d2a8-6b5f-dc1c-236235138490.png">


カーネル関数で変換した先の値は
グラム行列という名前で保存される。


非線形写像で線形分離が
可能になっても時間がかかるけど
内積計算で済ませば高速な計算が可能である
そのような各関数を内積カーネルという


### 8.3.1 多項式カーネル
$K_p(u,v)=(a + u^Tv)^p$
内積カーネルの一種
多項式カーネルである

<img width="623" alt="スクリーンショット 2019-12-04 6.00.58.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/7db76b56-23bb-32dd-d9da-fdf08ab8d0d5.png">

多項式カーネル　のとき
変換後の次元はこういう風になる
<img width="132" alt="スクリーンショット 2019-12-04 6.40.00.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/393556/ef868445-012c-a1bf-a6e0-5ebd42b54410.png">
二項定理と帰納法を使って証明される

$$ {}_nC_r　\Leftrightarrow   ( n\quad p)$$
であることに注意　二項定理の時は頻出的な表現
例えば　2次元　2乗　の時は

$_4C_2 = 6 $



## 8.4 ν-SVM

誤識別数で判断してた。
データ数で評価が変わっちゃう
誤識別率で判断すれば良いよね
でも
謝り率　←→　機械の複雑さ
トレードオフ


## 参考
https://www.slideshare.net/moa108/8-28571831