Support Vector Machines

支持向量机(Support Vector Machines)

优化目标

监督学习算法的性能大多类似，因此重要的不是选择算法，而是应用算法的水平。诸如特征的选择以及正则化参数的选择。SVM在学习复杂的非线性方程时提供了更为清晰、强大的方式。

从逻辑回归来修改

在逻辑回归中，每个样本$(x,y)$都会为总代价函数增加一项。忽略$\frac{1}{m}$，当$y=1$,代价函数项为$-log(\frac{1}{1+e^{-\theta^Tx}})$，随着$Z$增大而减小，当$y=0$，代价函数项为$-log(1-\frac{1}{1+e^{-\theta^Tx}})$，随着$Z$增大而增大。在这个基础上支持向量机的代价函数，做了如图变换，即对于正样本的代价函数，$Z>1$时代价函数为0，对于负样本的代价函数,$Z < -1$时代价函数为0，其他时候为线性函数，暂时可以不必考虑其斜率如何。

左边的函数为$cost_1^{(z)}$,右边的函数为$cost_0^{(z)}$

构建支持向量机

有了代价函数形式，最小化问题为

$$\frac{1}{m}(\sum_{i=1}^{m}y^{(i)}(-logh\_\theta{(x^{(i)})})+(1-y^{(i)})(-log(1-h\_\theta(x^{(i)}))))$$

然后再加上正则化参数
由于$\frac{1}{m}$不影响优化，可以先不考虑。
不同于逻辑回归中$A+\lambda B$的正则化优化形式，这里采用$CA+B$的正则化优化形式。
所以，代价函数的形式为:

$$min\_\Theta C\sum_{i=1}{m}[y^{(i)}cost_1(\theta^Tx^{(i)})+(1-y^{(i)})cost_0(\theta^Tx^{(i)})]+\frac{1}{2}\sum\_{i=1}^n\theta_j^{2}$$

假设函数的形式为:

$$h\_\theta{(x)} =\begin{cases} 1, & \text{if $\theta^Tx\geq0$ } \\ 0, & \text{otherwise}\end{cases}$$

与逻辑回归输出概率不同，SVM的假设函数直接预测y是1还是0

大边界的直观理解(Large Margin Intuition)

支持向量机不仅要求正确分开输入样本，还引入了安全的间距因子，即$y=1$,我们希望$\theta^Tx \geq 1$,$y=0$，我们希望$\theta^Tx \leq -1$

常数C的影响

若C非常大，我们希望在使第一项为0的前提下优化问题。要想让第一项为0，则要遵从以下约束，如果$y^{(i)}=1$,$\theta^Tx^{(i)} \geq 1$，如果$y^{(i)}=0$,$\theta^Tx^{(i)} \leq -1$。在这个基础上求解关于$\theta$的函数，会得到一个有趣的决策边界。

间距

上图可以有很多决策边界进行分割，但是支持向量机会选择黑色这条决策边界，它在分离正负样本上显得更好，就是这个黑线具有更大的**间距**。 **支持向量机的间距，是支持向量机具有鲁棒性的原因，因为它努力用一个最大间距来分离样本** 在代价函数最小化的过程中，我们希望找出$y=1$和$y=0$两种情况下都使得代价函数中左边一项尽量为0的参数。如果找到这样的参数，最小化问题变为。 $$min\frac{1}{2}\sum\_{j=1}^n\theta_j^2$$ 参数遵从的约束见“常数C的影响” 使用大间距分类器，学习算法会受**异常点**的影响。这样就需要考虑$C=\frac{1}{\lambda}$，回顾$\lambda$对过拟合和欠拟合的影响。 因此： $C$较大时，$\lambda$较小，可能会导致过拟合，高方差 $C$较小时，$\lambda$较大，可能会导致欠拟合，高偏差 ## 大边界分类的数学原理 ### 向量内积

$u^Tv$是向量$u$和$v$的内积，$||u||=\sqrt{u_1^2+u_2^2}$，再看向量$v$，已知$v_1$和$v_2$这两个分量，将向量$v$投影到$u$上，长度为$p$,那么另外一种计算内积的方法是$p||u||$(PS:我怎么觉得需要证明一下,想想原来是三角函数emmm)
有了向量内积的知识，再来理解支持向量机中的目标函数。

决策边界需要满足的条件

假如仅有两个特征,忽略截距$\theta_0$，那么$\theta=[\theta_1 \quad \theta_2]$，目标函数为$\frac{1}{2}||\theta||^2$,所以支持向量机所要做的就是极小化参数$\theta$长度的平方。

加入我们有很多决策边界都能把训练集分开，即满足上面讲的约束，那应该怎样选择参数$\theta$呢?事实上,参数$\theta$向量和决策边界是正交的(因为决策边界的斜率就和参数$\theta$的方向垂直)

所以要想尽量满足约束条件$p||\theta||\geq1$或者$p||\theta||\leq-1$，而且要让$||\theta||$尽量小，那么就要让$p$的绝对值尽量大，而如何让让$p$尽量大呢？就要让$x$与$\theta$之间的余弦值的绝对值越大，如何才能做到呢？支持向量机就会选择下边的决策边界，它试图极大化这些$p^{(i)}$的范数，即训练样本到决策边界的距离。

核函数(Kernels)

给定一个训练实例$x$，我们利用$x$的各个特征与预先选定的地标(landmarks)$l^{(1)}$，$l^{(2)}$，$l^{(3)}$的近似程度来选取新的特征$f_1,f_2,f_3$。

例如:

$$f_1 = similarity(x,l^{(l)})=exp(-\frac{||x-l^{(1)}||^2}{2\sigma^2})$$

其中$||x-l^{(1)}||^2=\sum_{j=1}^n(x_j-l_j^{(1)})^2$，为实例$x$中所有特征与地标$l^{(1)}$之间的距离的核。
具体而言,$similarity(x,l^{(1)})$就是核函数，高斯核函数(Gaussian Kernel)。如果训练实例与地标距离越短，则$f$近似于1，如果越长，则近似于0。$f$随$x$改变的速率受$\sigma$控制。

$f$是特征，所以$\theta^Tf$决定着假设函数预测的值

如何选择地标

根据训练集数量选择地标数量，令$l^{(n)}=x^{(n)}$，新特征建立在原有特征与训练集中所有其他特征之间的距离的基础之上。

$$f^{(i)}=[f_0^{(i)}=1\quad... f_m^{(i)}=sim(x^{(i)},l^{(m)})]$$

支持向量机假设

• 给定$x$，计算新特征$f$，当$\theta^T f\geq0$，预测$y=1$,反之
• 相应的代价函数为: $$minC\sum_{i=1}^{m}[y^{(i)}cost_1(\theta^Tf^{(i)})+(1-y^{(i)})cost_0(\theta^Tf^{(i)})]+\frac{1}{2}\sum\_{j=1}^{n=m}\theta_j^{2}$$

其中$\sum_{j=1}^{n=m}\theta_j^{2}=\theta^T\theta$,需要用$\theta^T M\theta$代替,$M$是根据核函数不同选择的一个矩阵，这是为了简化计算。

没有介绍代价函数的计算方法，可以使用鲜有软件报进行计算(如liblinear,libsvm)。使用之前需要编写核函数，如果使用高斯核函数，使用之前进行特征缩放是必要的。

支持向量机也可以不适用核函数，或者成为线性核函数。

$C$和$\sigma$的影响

$C=\frac{1}{\lambda}$

• C 较大时，相当于λ较小，可能会导致过拟合，高方差；
• C 较小时，相当于λ较大，可能会导致低拟合，高偏差；
• $\sigma$较大时，可能会导致低方差，高偏差；
• $\sigma$较小时，可能会导致低偏差，高方差。

使用支持向量机

高斯核函数之外的其他选择

• 多项式核函数（Polynomial Kernel）
• 字符串核函数（String kernel）
• 卡方核函数（ chi-square kernel）
• 直方图交集核函数（histogram intersection kernel）

这些核函数都要满足莫塞尔定理

多类分类

一对多方法，k个类需要k个模型，k个参数向量$\theta$

需要做的事

• 参数C的选择
• 选择核函数或相似函数

逻辑回归与支持向量机的使用准则

n为特征数，m为训练样本数。

• 如果相较于m而言，n要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。
• 如果n较小，而且m大小中等，例如n在 1-1000 之间，而m在10-10000 之间，使用高斯核函数的支持向量机。
• 如果n较小，而m较大，例如n在1-1000之间，而m大于50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。

值得一提的是，神经网络在以上三种情况下都可能会有较好的表现，但是训练神经网络可能非常慢，选择支持向量机的原因主要在于它的代价函数是凸函数，不存在局部最小值。

当你有非常非常大的训练集，且用高斯核函数是在这种情况下，我经常会做的是尝试手动地创建，拥有更多的特征变量，然后用逻辑回归或者不带核函数的支持向量机

但是通常更加重要的是，你有多少数据，你有多熟练是否擅长做误差分析和排除学习算法，指出如何设定新的特征变量和找出其他能决定你学习算法的变量等方面。通常这些方面会比你使用逻辑回归还是SVM这方面更加重要。