[TOC]
支持向量机
硬间隔支持向量机(hard margin)
问题的假设和动机
针对二分类问题，并且假设样本是线性可分的，也就是我能找到一个超平面，一刀下去，正例反例各占一边，不考虑样本不均衡等等一些问题。这个超平面应该怎么找，并且什么样的才是比较好的。假设超平面为 $ w^Tx + b = 0$, 实际上要找的就是 $w$ 和 $b$， 首先，这个超平面最起码要能把样本划分开，也就是说，$x$为正样本，$ w^Tx + b > 0$ , 反之， $ w^Tx + b < 0$。
空间中一个点到超平面的距离
假设空间中的点x到平面的投影为$x_0$ ,则
$x = x_0 + \frac{rw}{| w|}$, $r$就是x到超平面的距离，来计算一下这个 $r$ 需要注意的是：这里的r是有正负号的。同时用 $w^T$ 乘以两边，并且加上 b， 得到
$$
w^Tx + b = w^Tx_0 + b + \frac{rw^Tw}{| w |}
$$
由于 $ w^Tx_0 + b = 0$,化简一下得到：
$$
r = \frac{w^Tx + b}{| w |}
$$
方便描述一点，令$ f(x) = w^Tx + b $.
假设,在正样本中，距离超平面最近的点的距离是c，负样本是dd是小于0的，那么所有正样本中 $\frac{f(x_i)}{| w |} \geq c $,而负样本$\frac{f(x_i)}{| w |} \leq d $, 再假设，正负样本的标签分别为 $ y_i \in \lbrace 1,-1 \rbrace$, 接下来得到，正样本：$y_i\frac{f(x_i)}{| w |} \geq c $,负样本:$y_i\frac{f(x_i)}{| w |} \geq -d $,对所有的样本$y_i\frac{f(x_i)}{| w |} \geq e = \min\lbrace c,-d \rbrace > 0$. 再改进一下，实际上e为多少不好确定，但这没关系，因为对于一个超平面而言，同时对w和b放大或缩小一个倍数，这个超平面还是这个超平面，所以干脆让 $y_if(x_i) \geq 1 $. 也就是上面假设了距离超平面最近的满足正样本 $ w^Tx_i + b =1 $ ,负样本 $ w^Tx_i + b =-1 $ ,
目标函数
到目前为止，我们已经知道了我们要找的这个超平面至少要满足的条件，满足这样的超平面有无数个，我们要找一个我们认为比较好的超平面。那究竟咋样才比较好呢？ 到超平面的距离最近的正负样本的距离分别为$\frac{1}{| w |}$和$\frac{-1}{| w |} $, 两者的间隔为 $\frac{2}{| w |}$（注意并不是它俩的距离，而是$ w^Tx_i + b =1 $ 和$ w^Tx_i + b =-1 $的距离）。直观上来看，两者的间隔越大，模型的泛化性能就越好，可以把最大化间隔当做一个先验假设（有没有更合理的科学解释）。于是就得到了如下优化目标：
$$
\begin{equation}
\begin{array}{c l}
\max & \frac{2}{| w |} \
\text{subject to} & y_i(w^Tx_i+b) \geq 1, \quad i = 1,2,\cdots m
\end{array}
\end{equation}
$$
为了便于求解，转化成
$$
\begin{equation}
\begin{array}{c l}
\min & \frac{| w |^2}{2} \
\text{subject to} & y_i(w^Tx_i+b) \geq 1, \quad i = 1,2,\cdots m
\end{array}
\end{equation}
$$
它的对偶问题
其实从优化的角度来看，非常简单，还是写一下吧，就是用Lagrange 乘子法来求解上面的凸二次规划问题。因为根据它的对偶形式，后面再加上核函数，使得SVM可以很容易的求解非线性问题，让它变得非常强大。
写出来它的Lagrange函数：
$$
L(w,b,\lambda) = \frac{| w |^2}{2} - \sum_i^m \lambda_i(y_i(w^Tx_i + b) - 1)
$$
定义原问题的对偶函数为：
$$
g(\lambda) = \inf_{w,b}L(w,b,\lambda) \quad subject\quad to \quad\lambda \geq 0
$$
求Lagrange 函数在（w,b）的最小值,关于w和b求导得到
$$
\frac{\partial L}{\partial w} = w - \sum_i^m \lambda_i y_i x_i = 0 \
\frac{\partial L}{\partial b} = \sum_i^m \lambda_iy_i = 0
$$
于是我们得到，下列结果，并代入对偶函数：
$$
g(\lambda) = -\frac{1}{2} \sum_i^m \sum_j^m \lambda_i \lambda_j y_i y_j x_i^T x_j + \sum_i^m \lambda_i
\
subject \quad to \quad \lambda_i \geq 0
\
\sum_i^m \lambda_iy_i = 0\quad i = 1,2,\cdots,m
$$
依旧是一个凸的二次规划问题，可以使用SMO方法高效求解。
KKT条件
$$
\frac{\partial L}{\partial w} = w - \sum_i^m \lambda_i y_i x_i = 0
\
(\text{目标函数的梯度在约束函数梯度的锥包})
\
\frac{\partial L}{\partial b} = \sum_i^m \lambda_iy_i = 0
\
y_i(w^Tx_i+b) \geq 1, \quad i = 1,2,\cdots m(\text{解应该在原来的可行域})
\
\lambda_i \geq 0
\
\lambda_i(y_i(w^Tx_i + b) - 1) = 0, \quad i = 1,2,\cdots m(\text{互补松弛条件})
$$
由互补松弛性质，lagrange乘子只在边界约束的点上不为0，那些边界约束的点正是支持向量，而其他点对应的lagrange乘子都为0.
为什么要把原问题转换为对偶问题求解？以及核方法的引入
上面对SVM的建模基于一个假设就是样本集本身就是线性可分的，当样本集非线性可分的时候，一个超平面就不能完成分类的任务。一般情况下，低维不可分的问题，在高维情况下往往是线性可分的，所以我们可以对原来的特征空间作升维操作。
举个例子，假设原来是一个二维特征空间，样本$x=(x_1,x_2)$,而真实的分类平面是一个二次的曲面，也就是$ax_1^2 + b x_2^2 + c x_1x_2 + dx_1 + e x_2 + f = 0 $,我们依旧可以将其转化为线性问题，如，令 $ y_1 = x_1^2, y_2 = x_2^2, y_3 = x_1x_2,y_4 = x_1, y_5=x_2 $, 即对原来的特征空间做了一个映射：$\phi(x) \rightarrow y $,我们来寻求这个超平面就行了 $w^Ty + f = 0。$
但是注意这时候y是4维的，问题由原来的二维问题变成了4维问题，如果样本的分布比较复杂，可能需要将特征空间转化为非常高的维度才可以实现线性可分，这时候很容易出现维数灾难，而且也不太容易确定映射具体长什么样比较好。注意到即使我们将原特征空间映射到高维特征空间，在将其转化为对偶问题的时候，也只是需要求内积 $ \phi(x_i)^T\phi(x_j) $, 如果我们不显示的确定 $ \phi $, 只要能够确定最后的内积，这样就成功避开了维数灾难的发生，也达到了升维的作用。
只要$\phi$满足$[\phi(x_i)^T\phi(x_j)]_{i=1,j=1}^m$为半正定矩阵，$\phi$就能作为核函数使用。
最后，由法向量和样本之间的对偶表示的关系，最后的分类函数长这个样子：
$$
f(x) = \sum_i^m \lambda_i y_i \phi(x_i)^T \phi(x_i)
$$
$ \lambda_i $ 由对偶问题解出来，而内积由事先的核函数给出。由于Lagrange乘子的稀疏性质，对于训练好的支持向量机预测样本的时候应该是很迅速的？
常用的核函数
- 线性核：$x_i^Tx_j$
- 多项式核：$(x_i^Tx_j)^d$
- 高斯核（RBF）: $\exp(-\frac{|x_i-x_j|^2}{2\sigma^2})$
核支持向量机 VS 线性支持向量机（这里一般指soft margin,下节讨论）
核支持向量机可以处理非线性可分的问题，模型的容量要大于线性支持向量机，正所谓No Free Lunch，核支持向量机更容易过拟合，而且核支持向量机的计算复杂度要大于线性支持向量机，在数据量比较大的时候表现的尤为明显。
核SVM计算量大主要表现两方面，一是在模型训练的时候，二是模型预测的时候。主要原因都是核SVM经常需要转换为对偶问题来求解，需要计算出核矩阵，也就是嵌入空间中样本之间的内积。而在预测的时候，$w$又需要表示成其对偶形式：
预测样本x：
$$w^Tx+b \quad VS \quad \sum_{i=1}^m \lambda_iy_iK(x_i,x)$$
若内积运算需要 $O(n)$，那么线性与核SVM的时间花费分别为$$O(n)\text{和}O(mn)$$
软间隔支持向量机(soft margin)
硬间隔支持向量机很容易造成过拟合，原因就是，我们在推导的时候，约束条件不能容忍一个样本出错，很容易受outlier的影响。于是，引入软间隔，意思是说，我可以容忍部分样本分类出错，但是也不能出错太多。在这种假设下优化目标变为：
$$
\min \frac{| w |^2}{2} + C\sum_{i=1}^m \max\lbrace 0,1-y_i(w^Tx_i + b)\rbrace
$$
令 $ \xi_i = max\lbrace 0,1-y_i(w^Tx_i + b)\rbrace$,则 $ \xi_i \geq 1-y_i(w^Tx_i + b), \xi_i \geq 0$,上式可转化成等价形式
$$
\min \frac{| w |^2}{2} + C\sum_{i=1}^m \xi_i
\
subject\quad to \quad
\xi_i \geq 1-y_i(w^Tx_i + b),
\
\xi_i \geq 0.\quad i=1,2,\cdots,m
$$
$ \xi$可以看作一个松弛变量。软间隔支持向量机的对偶问题和核方法与硬间隔基本一致，但由于出现了松弛变量，使得软间隔的对偶问题变为：
$$
\begin{array}{c,l}
\max \quad & g(\lambda) = -\frac{1}{2} \sum_i^m \sum_j^m \lambda_i \lambda_j y_i y_j x_i^T x_j + \sum_i^m \lambda_i
\
subject \quad to & \quad 0 \leq \lambda_i \leq C
\
& \sum_i^m \lambda_iy_i = 0\quad i = 1,2,\cdots,m
\end{array}
$$
与硬间隔支持向量机相比，软间隔的对偶问题只是对Lagrange乘子加个了个约束，有一个上界。
References
[1] 周志华，机器学习
[2] Large-scale Linear and Kernel Classification