支持向量机

\(R^n\)空间中的点\(x\in R^n\)，超平面\(f(x)=w^Tx+b=0,w\in R^n,b\in R\)。 整个n维空间被分成两部分。\(w\)就是这个超平面的法向量。\(w\)指向的那个方向就是\(f(x)\)为正的那一部分。

点到超平面距离：\(\frac{|ax_0+by_0+c|}{\sqrt{a^2+b^2}}\)。为了想让距离体现出点在超平面的哪一侧，通常不加这个绝对值符号：\(\frac{ax_0+by_0+c}{\sqrt{a^2+b^2}}\)。

对于高维超平面，给出点\(x_0\in R^n\)，\(w\)为法向量，从\(x_0\)引垂线到\(x_1\)，则\(x_0-x_1=l\frac{w}{|w|}\)，故\(|l|=|x_0-x_1|\)，且\(x_1\)在超平面上。\(x_1=x_0-\frac{lw}{|w|},f(x_1)=w^Tx_1+b=(w,x_1)+b=(w,x_0)-l|w|+b=0\)，最终得到：\(l=\frac{(w,x_0)+b}{|w|}=\frac{w^Tx_0+b}{|w|}=\frac{f(x_0)}{|w|}\)

现在平面上有若干个两种颜色的点，尝试将其二分类。使用感知机模型很容易找到一个超平面将其区分，但这样的效果好吗？支持向量机希望找到的超平面是尽可能好的，希望不同分类的点中到超平面的最短垂直距离尽可能大。直观来看，如果两个分类的点到超平面的最短距离一样大，那么这个超平面既不能往上移动，也不能往下移动。

形式化来说，对于\((x_1,y_1)...(x_n,y_n),x_i\in R^k,y_i\in \{0,1\}\)，给出\(w\in R^k,b\in R\)，分类平面\(f(x)=w^Tx+b=0\)。带符号距离：\(\frac{w^Tx_i+b}{|w|}\)。我们希望的是\(y_i(\frac{w^Tx_i+b}{|w|})>0\)，表示确实分开了，希望\(max_{w,b}(min_i \frac{y_i(w^Tx_i+b)}{|w|})\)

优化问题：\(max_{w\in R^k,b\in R}(min_{i}\frac{y_i(w^Tx_i+b)}{w})\)，约束条件为\(y_i(w^Tx_i+b)>0\)。

极小化风险？极大化收益？把\(y_i(w^Tx_i+b)\)看作收益，\(|w|\)看作风险，则优化问题1：\(max_{w,b}(min_i(y_iw^Tx_i+b))\)，约束条件为\(||w||=1\)（风险固定）。优化问题2：\(min||w||\)，约束条件为\(min_i(y_i(w^Tx_i+b))\geq 1\)，这等价于\(min||w||^2\)，约束条件为\(\forall i\in[1,n],y_i(w^Tx_i+b))\geq 1\)。

求解这个问题可以引入二次规划，通常形式为：

有现成的包可以对其进行求解。

如果不使用二次规划的话，那么就可以从对偶问题的角度出发，受拉格朗日乘子法的启发：

\(max_{a_i\geq 0}(||w||^2+\Sigma_{i=1}^n a_i(1-y_i(w^Tx_i+b)))\)

如果约束条件都满足，即\(1-y_i(w^Tx_i+b)\leq0\)，因为\(a_i\geq0\)，因此求和号里是恒小于等于0的。因此只有ai等于0的时候才能得到极大，此时要极大化的就是\(||w||^2\)。 而如果\(1-y_i(w^Tx_i+b)>0\)，那么极大化的结果是正无穷。

求极小的时候，\(min_{b,w}(max_{a_i\geq 0}(||w||^2+\Sigma_{i=1}^n a_i(1-y_i(w^Tx_i+b))))\)等于求\(min\ ||w||^2\)且满足约束条件\(1-y_i(w^Tx_i+b)\leq0\)

现在就把一个二次规划问题转换为带有拉格朗日乘子法性质的问题。\(a_i\)必须是正的！

现在把min和max交换一下位置，问题等价于\(max_{a_i\geq 0}(min_{b,w}(||w||^2+\Sigma_{i=1}^n a_i(1-y_i(w^Tx_i+b))))\)。为什么对于这个问题可以交换呢？因为里面的这部分是关于\(w\)的凸函数，通常这种情况下是可以交换的。此时\(a_i\)固定，可以对\(w,b\)求梯度：\(2w=\Sigma_{i=1}^na_iy_ix_i,\Sigma_{i=1}^na_iy_i=0\)。可以得到\(w=\frac{1}{2}\Sigma_{i=1}^na_iy_ix_i\)，将其回代，得到：\(max_{a_i\geq0}(-\frac{1}{4}\Sigma_{i,j=1}^na_ia_jy_iy_jx_i^Tx_j+\Sigma_{i=1}^na_i)\)，且\(\Sigma_{i=1}^na_iy_i=0\)。眼前的这个优化问题中，\(y_i\)都是给定的，\(x_i\)也都是给定的。因此这个问题就变成了针对于\(a_i\)的一个问题。其中\(a_i\)都是一次的和二次的，针对\(a_i\)的约束也都是一次的和二次的。可以发现这是一个对于\(a_i\)的二次规划问题。把对于\(w\)的二次规划问题转换为对于\(a_i\)的二次规划问题后究竟得到了什么信息呢？主要体现：对于\(a_i\)的二次规划问题中，\(x_i^Tx_j=(x_i,x_j)\)，如果这个内积是另外一种形式，这丝毫不影响二次规划的结果。分析如下：对于\(\Phi:R^k\to R^m(k<m)\)，经过非线性变换：\(x\to\Phi(x)\)，这个变换过程可能是非线性的，当然也可能就是简单的升维。\((x_1,y_1)...(x_n,y_n)\to(\Phi(x_1),y1)...(\Phi(x_n),y_n)\)。对于低维空间线性不可分的点，升维变换后可能就线性可分了。问题变为：\(max_{a_i\geq0}(-\frac{1}{4}\Sigma_{i,j=1}^na_ia_jy_iy_j(\Phi(x_i),\Phi(x_j))+\Sigma_{i=1}^na_i),\Sigma_{i=1}^na_iy_i=0,a_i\geq 0\)。如果解出了所有的a，那么应该怎么区分原来的点呢？此时\(w=\Sigma_{i=1}^na_iy_i\Phi(x_i)\)，超平面\(R^m:(w,x)+b=0\)等价于\((\Sigma_{i=1}^na_iy_i\Phi(x_i),\Phi(X))+b=0\)。其放到低维空间是超曲面。

更一般的内积：\(K(x_i,x_j)=(\Phi(x_i),\Phi(x_j))\)，也可以是这样的：\(K(x_i,x_j)=(a+b(x_i,x_j))^m\)。条件是，不论什么样的内积，其构成的二维矩阵必须是正定的。满足这样的条件的函数\(K\)：核函数。其可以对应到\(\Phi:R^k\to R^m\)。这里的m可以小于等于正无穷。

二次规划：\(max_{a_i\geq0}(-\frac{1}{4}\Sigma_{i,j=1}^na_ia_jy_iy_jK(x_i,x_j)+\Sigma_{i=1}^na_i)\)，且要满足约束条件。\(f(x)=\Sigma_{i=1}^na_iy_iK(x_i,X)+b\)，分类问题就变成\(f(x)>0\ or \ <0\)。最后可能绝大部分\(a_i=0\)，不等于0的\(a_i\)对应的点就构成了支持向量。