Seventh week of machine learning on Coursera

如果训练集样本线性可分，那么在样本空间肯定能找到一个划分超平面将正负样本分隔开。
在之前学习的逻辑斯蒂回归(感知机)基于梯度下降的方法来求得这个超平面。但是这种方法求得的超平面是无穷个的（指的是感知机使用梯度下降迭代更新ω和b的过程中，会产生很多超平面方程，具体可参考《统计学习方法》例2.1），那么如何才能找到最优的超平面呢？
由此就引出了我们这节的主题—Support Vector Machine（求间隔最大化的超平面即为最优的超平面）。
样本空间上定义的超平面可以用ω⃗ Tx⃗ +b=0表示，ω⃗ =(ω1;ω2;..;ωd)表示超平面的法向量，b表示离原点的截距项。
可以看出我们想找最优的超平面，就是求得参数ω⃗ 和b的最优值。
|ω⃗ ⋅x⃗ +b|可以相对的表示点x距离超平面的距离。

如上图所示，超平面x1−x2+1=0，法向量为(1,−1)即确实为(ω1,ω2)，求点(1,0)距离超平面的距离，为2‾√,正好为|ω⃗ ⋅x⃗ +b|∥ω⃗ ∥

---

那么。我们知道了SVM是寻找最大间隔的超平面，以此作为最优的超平面。通过对参数ω⃗ 和b寻优来找到最大间隔的超平面，那么现在有个问题，我们以什么标准来判断这个间隔最大呢？
在SVM中，存在函数间隔和几何间隔，我们分别来看一下：
首先说一下为什么寻找最大间隔？
因为我们在分类的时候，如果一个点距离我们的超平面越远，那我们是不是就有更大的可能性将它们正确分类？所以这个间隔就是反映这个样本点距离我们超平面的远近程度。

函数间隔

上面说了|ω⃗ ⋅x⃗ +b|可以相对的表示点x距离超平面的距离，而且SVM是个二分类问题，对正类标签为y=1，对负类标签为y=−1，所以函数间隔为：

我们知道γi是个整数，表示训练集中每个点距离超平面的距离。
但我们发现，如果将ω和b的值增大2倍，超平面没有改变，但函数间隔增大2倍。所以需要引入几何间隔

几何间隔

几何间隔γi=函数间隔∥ω∥，这样避免上述情况的发生。
正式公式:

可以发现，我在一开始举的例子中，求得点(1,0)到超平面的距离为2‾√就是几何间隔。

---

几何间隔最大化

现在我们已经知道了超平面的表达式，知道了选用哪种间隔标准，现在就轮到如何求解使得几何间隔最大化？
支持向量：距离超平面最近的几个训练样本使得|ω⃗ Tx⃗ +b|=1成立，这些样本点称之为支持向量。
注意：这里的|ω⃗ Tx⃗ +b|=1是函数间隔，不是几何间隔，不然不一定能找到一个超平面距离最近的正负样本几何间隔恰好为1.

如图所示，我们希望γ=2∥ω∥越大越好。
所以：

为了最大化间隔，需最大化2∥ω∥,等价于最小化12∥ω∥2
所以线性可分支持向量机的优化问题：

---

Kernel(核函数)

当训练集线性不可分时，可以使用核函数将线性不可分数据转换为高维空间的线性可分数据。
常用的核函数包括多项式核函数、高斯核函数、字符串核函数等。

---

对于如何应用SVM，MATLAB中可以使用liblinear、libsvm等库，scikit-learn也提供了使用SVM的接口。
只需要选择正则项的参数和核函数类别即可。