サポートベクターマシン

#サポートベクターマシン（SVM）
「マージン最大化」と呼ばれる考えに基づき、主に２値の分類問題に使われる。また、計算コストが比較的大きいので、中小規模のデータセットで使われる。

##マージン最大化
直線から一番近いデータのことをサポートベクトルという。マージン最大化の目的は、マージン（直線とデータの距離）を一番大きくするベクトルを見つけることである。
この時の直線は、

```math 
W^TX_i + b
```
マージンは、このように表すことができる。

```math 
M = \frac{W^TX_+ + b}{||W||}  = \frac{-(W^TX_- + b)}{||W||}
```
よって、マージン最大化は以下の最適化問題によって表現できる。

```math 
max_{w,b} M,　 \frac{t_i(W^TX_i + b)}{||W||},　 i = 1,2,...,n
```
###線形分離可能と線形分離不可能
データを分類するための直線を引いた時、どのクラスに属するのかある程度分類できれば線形分離可能という。一方、どのクラスに属するのか不安定で、データにばらつきがある場合は線形分離不可能という。
マージン最大化では、線形分離可能な場合と不可能な場合で異なる計算式を用いる。まずは、線形分離可能な場合の最適化問題を解く。
####線形分離可能な場合
#####マージン最適化問題

```math 
min_{w,b} \frac{1}{2}||W||^2\\
t_i(W^TX_i + b) ≤1\\
i = 1,2,...,n
```
####線形分離不可能な場合
#####マージン最適化問題

```math 
min _{w, ξ} (\frac{1}{2}||W||^2 + C∑ξ_i)\\
\\
t_i(W^TX_i + b)  ≧1ーξ_i  ,ξ_i≧0 
\\
i = 1,2,...,n
```
##双体表現
SVMのマージン最大化は、ハードマージン、ソフトマージンの最適化問題によって定式化できる。これらの最適化問題を主問題と呼ぶ。
そして、世の中には線形分離不可能な場合がたくさんある。よって、多くの場合SV分類の主問題を直接解くことはできない。
そこで、主問題を双体問題と呼ばれる別の形に表現して最適化を考えることで、変数を減らせる可能性やカーネル関数を利用できるため効率的に非線形の分類が可能になる。
双体問題を理解するために必須なのが、ラグランジュ未定乗数法である。
###ラグランジュ未定乗数法
制約付き最適化問題の代表的な解放である。

```math 
L(x,a) = f(x) + ∑a_ig_i(x)
```
SVMの主問題を双体問題にした後、それをラグランジュの未定乗数法を用いて子の最適化問題を解く。

```math 
目的関数　min _{w, ξ} (\frac{1}{2}||W||^2 + C∑ξ_i)\\
\\
不等式制約　t_i(W^TX_i + b)  ≧1ーξ_i 　 ,ξ_i≧0 　i = 1,2,...,n
\\
```
ラグランジュ関数（ラグランジュ乗数はα、βを用いる）

```math 
L(w,b,ξ,a,β) = \frac{1}{2}||W||^2 + C∑ξ_i - ∑a_i(t_i(W^TX_i + b) - 1 + ξ_i) - ∑β_iξ_i
```
これを用いると、元の最適化問題は、下記のような双体問題の式で書ける。

```math 
max_a (L(a) = ∑a_i - \frac{1}{2}∑∑a_ia_jy_iy_jX^T_iX_j)\\
∑a_iy_i = 0 \\
 0≦a_i≦C \\
i = 1,2,...,n
```
##カーネル法
このようにして表現できた双体問題を今度はカーネル法を用いて解く。

```math 
k(x_i,x_j) = φ(X)^T_iφ(X)_j
```
ここである特定の条件を満たす関数を用いるとφ(X)を直接計算せずに内積を計算することができる。

```math 
φ(X)^T_iφ(X)_j = (X^Ty)^2
```
##サポートベクトルマシンの実装

```python
import mglearn
import matplotlib.pyplot as plt
from sklearn.model_selection import train_test_split
from sklearn import svm
from sklearn.svm import LinearSVC
from sklearn.datasets import load_iris

iris = load_iris()

X = iris.data[50:, 2:]
y = iris.target[50:] - 1

mglearn.discrete_scatter(X[:, 0], X[:, 1], y)
plt.legend(['versicolor', 'virginica'], loc='best')
plt.show()
```
![SVM1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/07e9be8f-9747-fb8d-f68f-d1de4b41b151.png)


```python
X_train, X_test, y_train, y_test = train_test_split(X, y, stratify=y, random_state=0) 

svm = LinearSVC().fit(X_train, y_train)

def plot_separator(model):
    plt.figure(figsize=(10, 6))
    mglearn.plots.plot_2d_separator(model, X)
    mglearn.discrete_scatter(X[:, 0], X[:, 1], y)
    plt.xlabel('petal length')
    plt.ylabel('petal width')
    plt.xlim(2.8, 7.0)
    plt.ylim(0.8, 2.6)
    plt.show()

plot_separator(svm)
```
![SVM2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/f778d1b1-57ca-71fc-11dc-7169519a3a7f.png)


```python
svm_100 = LinearSVC(C=100).fit(X_train, y_train)
plot_separator(svm_100)
```
![SVM3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/14669080-1e91-6cab-b8bc-14ab7649b129.png)


```python
print("score on training set: {:.2f}".format(svm.score(X_train, y_train)))
print("score on test set: {:.2f}".format(svm.score(X_test, y_test)))
```
score on training set: 0.91
score on test set: 1.00

```python
print("score on training set: {:.2f}".format(svm_100.score(X_train, y_train)))
print("score on test set: {:.2f}".format(svm_100.score(X_test, y_test)))
```
score on training set: 0.92
score on test set: 1.00
##カーネル法・多クラス分類への実装

```python 
import mglearn 
import numpy as np 
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons

moons = make_moons(n_samples=200, noise=0.1, random_state=0)

X = moons[0]
y = moons[1]

plt.figure(figsize=(12, 8))
mglearn.discrete_scatter(X[:, 0], X[:, 1],y)
plt.plot()
```
![kernel1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/46abe62d-ec97-bd98-92c5-fe67f1d9bf0d.png)


```python
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import LinearSVC

X_train, X_test, y_train, y_test = train_test_split(X, y, stratify=y, random_state=0)

scaler = StandardScaler()
X_train_scaled = scaler.fit_transform(X_train)
X_test_scaled = scaler.fit_transform(X_test)

lin_svm = LinearSVC().fit(X_train_scaled, y_train)

plt.figure(figsize=(20, 8))
mglearn.plots.plot_2d_separator(lin_svm, X)
mglearn.discrete_scatter(X[:, 0], X[:, 1], y)
plt.xlabel("$x_0$", fontsize=20)
plt.ylabel("$x_1$", fontsize=20)
```
![kernel2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/7b4988d6-7f85-22e7-fe85-a01f42597b78.png)


```python
from sklearn.preprocessing import PolynomialFeatures

poly = PolynomialFeatures(degree=3)
X_train_poly = poly.fit_transform(X_train)
X_test_poly = poly.fit_transform(X_test)

X_train_poly_scaled = scaler.fit_transform(X_train_poly)
X_test_poly_scaled = scaler.fit_transform(X_test_poly)

from sklearn.pipeline import Pipeline
poly_svm = Pipeline([
    ('poly', PolynomialFeatures(degree=3)),
    ('scaler', StandardScaler()),
    ('svm', LinearSVC())                     
])

def plot_decision_function(model):
    _x0 = np.linspace(-1.5, 2.5, 100)
    _x1 = np.linspace(-1.0, 1,5, 100)
    x0, x1 = np.meshgrid(_x0, _x1)
    X = np.c_[x0.ravel(), x1.ravel()]
    y_pred = model.predict(X).reshape(x0.shape)
    y_decision = model.decision_function(X).reshape(x0.shape)
    plt.contourf(x0, x1, y_pred, cmap=plt.cm.brg, alpha=0.2)
    plt.contourf(x0, x1, y_decision, levels=[y_decision.min(), 0, y_decision.max()], alpha=0.3)

def plot_dataset(X,y):
    plt.plot(X[:, 0][y==0], X[:, 1][y==0], "bo", ms=15)
    plt.plot(X[:, 0][y==1], X[:, 1][y==1], "r^", ms=15)
    plt.xlabel("$x_1$", fontsize=20)
    plt.ylabel("$x_2$", fontsize=20, rotation=0)

plt.figure(figsize=(12, 8))
plot_decision_function(poly_svm)
plot_dataset(X, y)
plt.show()   
```
![kernel3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/b024aaa3-0345-04f0-d84d-7eed853746d8.png)


```python
from sklearn.svm import SVC

kernel_svm = Pipeline([
    ('scaler', StandardScaler()),
    ('svm', SVC(kernel='poly', degree=3, coef0=1))                       
])

kernel_svm.fit(X, y)

plt.figure(figsize=(12, 8))
plot_decision_function(kernel_svm)
plot_dataset(X, y)
plt.show()
```
![kernel4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/2519a268-5da0-2017-0a0f-2fb11020c57f.png)


```python
plt.figure(figsize=(20, 15))

for i, degree in enumerate([2, 3, 5, 10]):
    poly_kernel_svm = Pipeline([
        ('scaler', StandardScaler()),
        ('svm', SVC(kernel='poly', degree=degree, coef0=1))                                    
    ])
    poly_kernel_svm.fit(X, y)

    plt.subplot(221 + i)
    plot_decision_function(poly_kernel_svm)
    plot_dataset(X, y)
    plt.title("d = {}".format(degree), fontsize=30)

plt.show()  
```
![kernel5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/906331/338eb8cf-88f7-cc42-fc42-f3ff6eee75f0.png)