SVM学习

首先让我们回顾一下二分类问题的分界面。

令分界面线性函数为$y(x)=w^{T}x+w_{0}$，$w$称为权重向量，$w_{0}$称为偏置(bias)。偏置的负值也称为阈值(threshold)。也就是说，对于一个输入向量$x$，如果$y(x)\ge 0$，那么被分配为类$C_{1}$。否则被分配为类$C_{2}$。

如图，如果一个点在分界面$y(x)=0$上，那么从原点到该分界面的法向量可以写为$\frac{w^{T}x}{\lVert w\rVert}=-\frac{w_{0}}{\lVert w\rVert}$。令$x_{\perp}$为$x$向量在决策面上的正交投影点到原点的投影向量，那么可以得到

$x=x_{\perp}+r\frac{w}{\lVert w\rVert}$

两边同乘$w^{T}$并加上$w_{0}$，可以得到$w^{T}x+w_{0}=w^{T}x_{\perp}+r \frac{w^{T}w}{\lVert w\rVert}+w_{0}$

$y(x)=r \frac{w^{T}w}{\lVert w\rVert} => r=\frac{y(x)}{\lVert w\rVert}$

为了编程方便，我们一般增加一个dummy input $x_{0}=1$，令$\tilde{w}=\{w_{0},w\}$，$\tilde{x}=\{x_{0},x\}$，$y(x)=\tilde{w}^{T}\tilde{x}$

多分类问题

SVM算法最初是为二值分类问题设计的，当处理多类问题时，就需要构造合适的多类分类器。目前，构造SVM多类分类器的方法主要有两类：一类是直接法，直接在目 标函数上进行修改，将多个分类面的参数求解合并到一个最优化问题中，通过求解该最优化问题“一次性”实现多类分类。这种方法看似简单，但其计算复杂度比较高，实现起来比较困难，只适合用于小型问题中；另一类是间接法，主要是通过组合多个二分类器来实现多分类器的构造，常见的方法有one-against-one和one-against-all两种。

1. 一对多法（one-versus-rest,简称1-v-r SVMs）。训练时依次把某个类别的样本归为一类,其他剩余的样本归为另一类，这样k个类别的样本就构造出了k个SVM。分类时将未知样本分类为具有最大分类函数值的那类。
2. 一对一法（one-versus-one,简称1-v-1 SVMs）。其做法是在任意两类样本之间设计一个SVM，因此k个类别的样本就需要设计$k(k-1)/2$个SVM。当对一个未知样本进行分类时，最后得票最多的类别即为该未知样本的类别。Libsvm中的多类分类就是根据这个方法实现的。这样做的问题其实可以从上图显示，会产生一个ambiguous的区域。

考虑一个K类的分解面包含K个线性函数，$y_{k}(x)=w_{k}^{T}x+w_{k0}$，将点$x$分配给类$C_{k}$，如果$y_{k}(x)>y_{j}(x)$对于所有$j!=k$。类$C_{k}$与类$C_{j}$之间的分界面可以由$y_{k}(x)=y_{j}(x)$给定，即一个$D-1$维的超平面

$(w_{k}-w_{j})^{T}x+(w_{k0}-w_{j0})=0$

对于任一一点类$C_{k}$的点$x$，如图$\hat{x}=\lambda x_{A}+(1-\lambda)x_{B}$，有$y_{k}(\hat{x})=\lambda y_{k}(x_{A})+(1-\lambda)y_{k}(x_{B})$，可证$R_{k}$区域是单连通的且为凸。

SVM（Maximum Margin Classifier)

SVM的一个很好的性质就是模型参数的确定等同于一个凸优化问题，因此肯定有全局最优解。SVM是一个决策机，不像LR等分类器提供后验概率(posterior probabilities)。

$y(x)=w^{T}\phi{(x)}+w_{0}$

其中，$\phi{(x)}$表示特征映射函数。

有N组输入向量$x_{1},...,x_{N}$，其相应的输出值为$t_{1},...,t_{N}$，$t_{n} \in \{-1,1\}$。

感知机存在的问题：保证在有限步内找到解，但是找到的这个解依赖于（任意）初始值$w$和$b$，以及数据点放置的顺序。

$r=\frac{y(x)}{\lVert w\rVert}$这就是所谓的Margin.如果存在多个解能将训练数据正确分类，寻找泛化误差最小(Margin)的解。

$\frac{t_{n}y(x_{n})}{\lVert w\rVert}=\frac{t_{n}(w^{T}\phi{(x)}+b)}{\lVert w\rVert}$

其中，我们注意到一个现象，令$w->kw$，$b->kb$，$\frac{t_{n}y(x_{n})}{\lVert w\rVert}$值不变。

Maximum Margin Solution

(marginalization with respect to the prior distribution of the parameters in a Bayesian approach for a simple linearly separable dataset leads to a decision boundary that lies in the middle of the region separating the
data points. The large margin solution has similar behaviour.)

其中，$\frac{1}{\lVert w\rVert}$与$n$无关。

我们令$t_{n}(w^{T}\phi{(x)}+b)=1$为距离surface最近的点，那么所有的数据点都应该满足$t_{n}(w^{T}\phi{(x)}+b)\ge 1$。当等号成立时，约束 ative；不成立时，约束Inactive。

优化问题简化为求解

$maximize\quad\lVert w\rVert^{-1}$ subject to $t_{n}(w^{T}\phi{(x)}+b)\ge 1$,$n=1,...,N$

等同于

$argmin_{w,b}\quad\frac{1}{2}\lVert w\rVert^{2}$ subject to $t_{n}(w^{T}\phi{(x)}+b)\ge 1$,$n=1,...,N$

引入其拉格朗日形式

其中$a=a_{1},..,a_{N}$。注意拉格朗日乘子项前的符号，因为我们是对$w$和$b$最小化，而对$a$做最大化。令目标函数对$w$和$b$求偏导并令其为0。

代入上式消去$w$和$b$，可以得到该问题的对偶形式(dual representation)。

其中。（这个性质非常好！！！参见内积：相似性的度量一文）。

有M个变量的二次规划问题(quadratic programming)时间复杂度为$O(M^{3}$。对偶问题只有N个变量，对于基函数的个数$M$小于样本数$N$而言，求解对偶问题似乎并不有优势。

好处是：对偶形式可以使用核函数，因为内积求解非常方便。在高维空间，特征维数远远大于样本数，甚至无穷维空间，这样的好处是显而易见的。

 核函数是正定的，这使得$\tilde{L}(a)$有一个下界，从而使得优化问题well-defined。

对于输入样本$x$，根据训练出来的模型预测其输出。

$y(x)=w^{T}\phi{(x)}+b$, $w=\sum_{n=1}^{N} a_{n}t_{n}\phi_{(x_{n})}$

讨论：b的值没有出现在对偶问题中，利用原始可以找到$b^{*}$。

KKT条件

对于每个数据点，要么$a_{n}=0$，要么$t_{n}y(x_{n})=1$。 对于$a_{n}=0$的点不会出现在对偶优化问题中，所以对模型参数无作用，对于预测新的输入点无贡献。剩余的数据点称为支持向量(support vectors)。

求解优化问题我们可以得到$a=(a_{1},...,a_{N}$向量，并决定阈值（偏置）b的大小。对于任何支持向量$x_{n}$满足$t_n}y(x_{n})=1$。

其中$S$表示支持向量的下标。

等式两边乘以$t_{n}$，使得$t_{n}^{2}=1$。

我们可以从损失函数形式来理解SVM，其损失函数即所谓的Hinge Loss。

$\E_{\infty}$为函数，当$z\ge 0$时等于0，否则为$\infty$。确保约束成立。

随机梯度下降法（Stochastic Gradient Descent）求解以下的线性SVM模型：

w的梯度为：

传统的梯度下降法需要把所有样本都带入计算，对于一个样本数为n的d维样本，每次迭代求一次梯度，计算复杂度为O(nd) ，当处理的数据量很大而且迭代次数比较多的时候，程序运行时间就会非常慢。

随机梯度下降法每次迭代不再是找到一个全局最优的下降方向，而是用梯度的无偏估计 来代替梯度。每次更新过程为：

由于随机梯度每次迭代采用单个样本来近似全局最优的梯度方向，迭代的步长应适当选小一些以使得随机梯度下降过程尽可能接近于真实的梯度下降法。

LIblinear，官网上是这样介绍的：”LIBLINEAR is a linear classifier for data with millions of instances and features“，即主要专门为百万级别的数据和特征实现的线性分类器。

1.  当你面对海量的数据时，这里的海量通常是百万级别以上。海量数据分为两个层次：样本数量和特征的数量。
2. 使用线性和非线性映射训练模型得到相近的效果。
3. 对模型训练的时间效率要求较高。

http://blog.csdn.net/orangehdc/article/details/38682501

 

 

讨论：SVM在高维空间里构建分类器后，为什么这个分类器不会对原空间的数据集Overfitting呢？

第一，SVM求解最优分类器的时候，使用了L2-norm regularization，这个是控制Overfitting的关键。第二，SVM不需要显式地构建非线性映射，而是通过Kernel trick完成，这样大大提高运算效率。

附录：