FOREWORDS

SVM，全称Support Vector Machine，也就是支持向量机。
SVM可以说是目前最受欢迎的机器学习模型，对于线性分类/非线性分类都有非常强大的适应能力。

本文是进阶文，为了不浪费大家的时间，读之前请问自己以下几个问题：
"What is data classification? "
"Why do we use it?" --- stupid question, aha?
"What is perceptron?" --- not details needed, just conception.(very important!)

IF 以上的问题，你还无法给自己一个答案：
        All right，请继续努力，对于机器学习/数据挖掘来说，所有人都需要一个过程，时间会给你答案。对于我的菜鸟经历来说，感知机是机器学习分类算法的最初实现，而SVM是让分类变得更加可信。如果接下来时间允许，我会另写一篇有关感知机的博文。
ELSE :
        Good，听听我对SVM的理解和我所做的尝试。

生活中我们需要一些勇气去追寻自己的理想。

Some Fundamental Ideas

• 间隔最大化（核心）
• 核函数的引用 （将线性分类的应用拓展到非线性问题，最牛A的地方）

%下面我会用python对线性可分情况进行解释以上概念，同时引入一些新的概念。

import numpy as np
import seaborn as sns
import matplotlib.pylab as plt
from sklearn import datasets
iris = datasets.load_iris()
plt.plot(iris['data'][iris['target']==0,2],iris['data'][iris['target']==0,3],'o')
plt.plot(iris['data'][iris['target']==1,2],iris['data'][iris['target']==1,3],'o')
plt.xlabel(iris['feature_names'][2])
plt.ylabel(iris['feature_names'][3])
plt.legend([iris['target_names'][0],iris['target_names'][1]])

我们得到的图像如下：

Hyperplane.png

note: 箭头是我后期标注的，绿色箭头是分隔超平面比较极端的情况，黄色和红色分别代表分隔超平面可移动的方向。
分隔超平面的函数表示：[图片上传失败...(image-9ba451-1529905115287)]
间隔包括，函数间隔和几何间隔。
函数间隔，functional margin， 描述样本点到超平面的远近，[图片上传失败...(image-b8277c-1529905115287)])
几何间隔，geometric margin，表示样本点到超平面的空间距离， [图片上传失败...(image-feaf29-1529905115287)]}{||W||})

我们定义 几何间隔
[图片上传失败...(image-3660f4-1529905115287)]
执行SVM的目标：间隔最大化
note：超平面的数量是无限的，每一个超平面我们都选合理的几何间隔，然后在所有的几何间隔中，我们选取最大的几何间隔，从而确定满足间隔最大化，也就是说它存在唯一解。这是一个最优化问题。

最大间隔分离超平面，[图片上传失败...(image-2d362c-1529905115287)]
[图片上传失败...(image-864403-1529905115287)]-1\geq0,,i=1,2,...,N)

我们的目标就是要求解上述的max值。
从几何间隔和函数间隔的定义可以看出，分割面的向量w对gamma的值影响是最直接的。
比如：我将w和b扩大N倍，变为Nw和Nb，那么函数间隔同样变为N倍，也因此说明左右上述最优化问题最直接的变量就是分母的|W|。既然分子对最优化的影响远小于分母，那么，我们姑且令分子为1。
也因此，上述的max问题变为：
[图片上传失败...(image-cf75fc-1529905115287)]
[图片上传失败...(image-98a3c2-1529905115287)]-1\geq0,,i=1,2,...,N)

我们发现可以用等价原理将上述的形式转化
[图片上传失败...(image-591a28-1529905115287)]

于是我们得到了新的约束最优化问题。
[图片上传失败...(image-22179c-1529905115287)]
[图片上传失败...(image-fdabf-1529905115287)]-1\geq0,,i=1,2,...,N)
这是一个凸二次规划的问题。

在解决这个问题之前，还需要引入一个核心keyword--------支持向量
这也就是为什么取该算法叫做支持向量机的原因。
所谓的支持向量，就是训练数据集的样本点与分隔超平面距离最近的样本点，我们叫做支持向量。
%我用python做一个图展示下

import seaborn as sns
sns.set_style('darkgrid')
x=iris['data'][:,(2,3)]
y=(iris['target']==0).astype(np.float64)
clf=svm.SVC(kernel='linear')
clf.fit(x,y)
w=clf.coef_[0]
xx=np.linspace(1.5,3.5)
b=clf.intercept_[0]
yy=(-b-w[0]*xx)/w[1]
yy1=(-w[0]*xx-(-w[0]*clf.support_vectors_[0,0]-w[1]*clf.support_vectors_[0,1]))/w[1]
yy2=(-w[0]*xx-(-w[0]*clf.support_vectors_[1,0]-w[1]*clf.support_vectors_[1,1]))/w[1]
plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1],marker='o',c='',edgecolors='g')
plt.scatter(clf.support_vectors_[:,0],clf.support_vectors_[:,1],edgecolors='g',s=105)
plt.plot(iris['data'][iris['target']==0,2],iris['data'][iris['target']==0,3],'o')
plt.plot(iris['data'][iris['target']==1,2],iris['data'][iris['target']==1,3],'o')
plt.xlabel(iris['feature_names'][2])
plt.ylabel(iris['feature_names'][3])
plt.legend([iris['target_names'][0],iris['target_names'][1]])
plt.plot(iris['data'][iris['target']==2,2],iris['data'][iris['target']==2,3],'o')
plt.plot(xx,yy)
plt.plot(xx,yy1,'-.')
plt.plot(xx,yy2,'-.')

plot.png

现在回顾之前说到的，我们的函数间隔取的是所有样本点最小的，我们的几何间隔取的是最小间隔集合里最大的，也就是说最终得到的值对应的支持向量将直接决定分离超平面，其他的样本点并不起作用，就是说去掉其他样本点，我们依然会得到一样的超平面，支持向量决定最大间隔超平面，这种重要性决定了为什么我们对该算法起名SVM。

AFTERWORDS

接下来的内容就是要求解条件约束最优化问题，我们用到了对偶算法，所以下一篇会重点描述对偶算法，以及如何确定支持向量和W。以及后面会涉及到软间隔问题，核函数的使用，以及SMO算法。

路还长，不要被眼前的困境迷失了双眼。just keep doing~