svm优化问题的导出 | 兰溪

SVM - 优化问题的导出

svm的想法其实非常朴素：

• 寻找一个超平面来将所有样本正确分开 (条件1)
• 并且保证超平面到两类样本的边界到超平面的距离和最大且相等 (条件2)

条件一其实就是线性可分的条件，条件二是为了保证鲁棒性，保证两类样本到超平面的距离最大，就相当于保留了判断时的裕量，这样即使数据有噪声，只要噪声不是太过于离谱，都不会产生误判，而保证两类样本边界到超平面距离相等则是为了不偏向某一方。

用图来直观地感受下上面两条约束，svm模型图示如下：

现在我们可以用数学的方式来描述这两个想法。

对于约束一，假设有一个超平面$w^Tx+b=0$可以将两类样本分开，那么对于正类样本$x_p$来说必然有$w^Tx_p+b > 0$；同样地，对于负类样本$x_n$来说也会有$w^Tx_n + b < 0$。如果我们让正类样本标签为$y_p=+1$而负类样本标签为$y_p=-1$，那么我们可以统一描述为

$$y(w^Tx+b) > 0 \tag{1}$$

现在我们来看条件2。

为了对条件2进行建模，我们首先要求空间中任意一点到超平面$w^Tx+b=0$的距离。现在我们假设有一点$x_1$，它到超平面的距离$\gamma$可以写做

$$\gamma=|w^Tx_1+b| \tag{2}$$

这个公式怎么来的呢？我们可以假设点$x_1$在超平面上的投影为$x_0$,那么从$x_1$指向$x_0$的这个向量就等于$x_1 - x_0$，同时这个向量的方向与超平面的法向量是一致的，我们把超平面化为$\frac{w^Tx+b}{||w||} = 0$,可以得到法向量$\frac{w}{||w||}$,所以我们可以得出

$$\frac{\gamma w}{||w||} = x_1 - x_0 \tag{3}$$

其中$\gamma$就是点$x_1$到超平面的距离。式子(3)简单地做一下变形就可以得到式子(4)

$$\frac{\gamma w^Tw}{||w||} = w^T(x_1 - x_0) + b - b = w^Tx_1 + b - (w^Tx_0 + b) \tag{4}$$

因为$x_0$是超平面$w^Tx + b = 0$上面的点，也就意味着$w^Tx_0 + b = 0$,这样如果只看距离的大小而不看方向的话，式子(4)就可以化为

$$\gamma = \frac{|w^Tx_1+b|}{||w||}$$

好了，有了距离公式之后我们可以计算一下两类样本到超平面的边界距离之和了。假设有正类的边界样本$x_+$和负类边界样本$x_-$, 距离之和为

$$\gamma_+ + \gamma_- = \frac{w^T(x_+ - x_-)}{||w||} \tag{5}$$

我们观察一下式子(5)，在给定样本之后，由于分母$||w||$的存在，消除了参数向量$w$的模长的影响, $\frac{w}{||w||}$相当于一个方向与$w$同向的单位向量。于是我们只需要关注参数向量$w$的方向，而不需要关注其长度，从另一个角度来说，我们可以对$w$进行任意倍数的缩放而不会影响超平面。于是我们可以随意地令：

$$\begin{cases} \quad w^T(x_+-x_-)=2 \\ \quad w^Tx_+ + b = 1 \\ \quad w^Tx_- + b = -1 \end{cases}$$

这并没有什么难以理解的，因为不管$w$和$b$的方向如何，我们总是可以对其进行缩放使得上述等式成立。这样由于正负类边界到超平面的距离都缩放到了$1$，式子(5)改写成

$$\gamma_+ + \gamma_- = \frac{2}{||w||} \tag{6}$$

于是约束(1)也需要改写成

$$y(w^Tx+b) \ge 1 \tag{7}$$

于是式子(6)和(7)构成了我们的优化目标与约束：

又由于最大化$\frac{2}{||w||}$与最小化$\frac{||w||^2}{2}$是等价的，而后者可以得到一个更规整的导数，方便后续处理，所以我们把上述的优化问题重写为:

$$\begin{cases} \quad \underset{w,b}{\arg \min} \frac{||w||^2}{2} \\ \quad s.t. \quad y_i(w^Tx_i + b) \ge 1, \quad i = (1, 2, 3, ...m) \end{cases} \tag{8}$$

其实我们重新审视一下式子(8), 约束条件未免太过严格，实际上大多数数据都很少存在这样完美的线性可分的条件，于是我们打算放宽一点限制: 不严格要求对每个样本都满足约束条件$y_i(w^Tx_i + b) \ge 1$，而是允许一定程度地违反该约束，并且违反程度通过$max(0, 1 - y_i(w^Tx_i+b))$来量化并且作为一个正则化项加入到优化目标当中。于是式子(8)进一步写成

$$\underset{w,b}{\arg \min} \frac{||w||^2}{2} + C\sum_{i=1}^m{max(0, 1-y_i(w^Tx_i+b))} \tag{9}$$

现在看一看式子(9),很遗憾，由于含有非线性且不连续的部分，导致式子(9)也难以求解，于是我们只能寻求新的方法。好在这类问题前人们已经研究过了，解决的办法称之为:松弛变量法。在最优化领域，如果我们的约束函数全为’$\ge$’或者’$\le$’条件时，我们希望对满足约束的样本保持原有的约束，而对那些不满足约束的样本适当放松约束(边界变得松弛了)，并且将放松的程度作为一个惩罚量加入最优化目标函数中，这样我们就可以在更大的可行域中去最优化目标函数。在这里的做法是将约束$y_i(w^Tx_i+b) \ge 1$放松到$y_i(w^Tx_i + b) \ge 1-\xi_i$并且将$\xi_i$作为一个惩罚量加入目标函数中去，根据这个想法得到的优化目标与约束为

$$\begin{aligned} & \underset{w,b,\xi_i}{\arg \min} \frac{||w||^2}{2} + C\sum_{i=0}^m\xi_i \\ s.t. & \begin{cases} y_i(w^Tx_i + b) \ge 1-\xi_i, \quad i = (1, 2, 3...,m) \\ \xi_i \ge 0, \quad i = (i, 2, 3...,m) \end{cases} \end{aligned} \tag{10}$$

以上式子就是SVM的带约束优化目标了，解决式$(10)$的方式有很多，一般通用的做法是通过拉格朗日乘子法将带约束问题转换为无约束的最优化问题，从而能够利用梯度下降，坐标上升法等迭代算法来求解。