支持向量机Support Vector Machine

机器学习初学者，原本是写来自己看的，写的比较随意。难免有错误，还请大家批评指正！对其中不清楚的地方可以留言，我会及时更正修改

支持向量机是广泛应用在工业界和学术界的一个比较流行的算法，与逻辑回归和神经网络相比，SVM在学习复杂的非线性方程时，提供了一种更为清晰更加强大的方式。

优化目标Optimization Objective

在逻辑回归中，我们有hθ(x)=11+e−z=11+e−θTx，hθ(x)=g(z)是一个sigmoid函数。
如果有一个y=1的样本，我们希望hθ(x)≈1，即θTx≫0；
如果有一个y=0的样本，我们希望hθ(x)≈0，即θTx≪0；
再来看一下代价函数：

其中，左右两边紫红色的线被定义成两个函数，分别是cost1(z)和cost0(z)，即costy(z)
可以将cost函数理解成
z=θTx
cost0(z)=max(0,k(1+z))
cost1(z)=max(0,k(1−z))
使用新的cost函数对逻辑回归的最小化问题进行替代，拿掉与最小化不相关的值m，得到支持向量机的最小化目标：

其中C=1/λ
新的假设函数：

大间距分类器Large Margin Intuition

人们有时将支持向量机看作是大间距分类器，但只是一个直观上的理解。在上述的cost函数中，
如果y=1，我们希望θTx≥1；
如果y=0，我们希望θTx≤−1。
当常数C很大时，我们需要选择合适的参数使得∑项等于0，此时，优化目标变成了J(θ)=12∑nj=1θ2j
在支持向量机中，决策边界有一个特殊的属性就是，它距离正样本和负样本都尽可能的远。决策边界与样本点之间的最近距离成为间距Margin。因为SVM的决策边界到正负样本都有一个大间距，因此也称之为大间距分类器。
注：仅仅当C很大时，才可能实现大间距

大间距分类器背后的数学知识

核函数

对支持向量积算法进行一些改变，构造复杂的非线性分类器，这里使用核函数来达到这个目的。
给定x，基于与标记点l(1),l(2),l(3)的邻近性计算新的特征，定义
fi=similarity(x,l(i))=exp(−∥∥x−l(i)∥∥22σ2)=exp(−∑nj=1(x−l(i)j)22σ2)
其中的相似性函数similarity又被称为高斯核函数，其具有以下性质：
当x≈l(i)时，fi≈1；
当x距离l(i)较远时，fi≈0。
每个标记点都给出了假设函数中用到的特征，l(1)→f1, l(2)→f2, l(3)→f3,⋯，假设函数可以写成：
hθ(x)=θ1f1+θ2f2+θ3f3+…
σ2也是高斯核函数的参数，它可以修正特征fi的衰减速率，如下图：

下面我们来看如何选择这些标记点，一个方法是这些标记点与训练样本中的点完全重合，即有m个标记点。给定样本x，我们有f1=similarity(x,l(1)),f2=similarity(x,l(2)),f3=similarity(x,l(3))等等。由此可得到一个特征向量f(i)，对应的，设定f0=1，则有：
x(i)→⎡⎣⎢⎢⎢⎢⎢f(i)1=similarity(x(i),l(1))f(i)2=similarity(x(i),l(2))…f(i)m=similarity(x(i),l(m))⎤⎦⎥⎥⎥⎥⎥
现在，我们使用新的特征构建支持向量机的最小化算法：
minθC∑mi=1[y(i)cost1(θTf(i))+(1−y(i))cost0(θTf(i))]+12∑nj=1θ2j
注：相对于和其他机器学习算法的组合，核函数和支持向量机的组合能够使算法计算更快。
-选择SVM参数-
如果C较大，我们会得到更高的方差，更低的偏差（λ小，过拟合）
如果C较小，我们会得到更低的方差，更高的偏差（λ大，解决了过拟合）
如果σ2较大，特征fi变化的更平滑，导致更高的偏差和更低的方差
如果σ2较小，特征fi变化的更陡峭，导致更低的偏差和更高的方差

使用SVM

在实际应用过程中，有很多写好的SVM库可以使用，推荐使用’liblinear’和’libsvm’，需要做的工作主要有
- 选择参数C
- 选择核函数（即相似性函数）
-不使用核函数（即线性核函数），是一个标准的线性分类器
-选择m和n的大小，n大m小
-使用高斯核函数，需要选择σ2
-选择m和n的大小，n小m大

注：使用高斯核函数之前要进行特征缩放
注：并不是所有的核函数都是可用的，它必须符合”Mercer’s Theorem”，它保证了SVM包的优化可能正确运行。需要使用训练集和交叉验证集训练C和其他参数

多元分类问题

许多SVM包已经内置了多元分类
也可以使用’one-vs-all’的方法进行多元分类，类似之前的逻辑回归。

逻辑回归 VS 支持向量机

• 如果n很大，和m差不多大，使用逻辑回归或线性核函数的SVM
• 如果n很小，m适中，使用高斯函数的SVM
• 如果n很小，m很大，则手动增加一些新的特征，然后使用逻辑回归或没有核函数的SVM

注：神经网络的方法可以适配以上三种情况，但其训练速度会慢很多