SVM公式推导

支持向量机的公式推导在机器学习的面试中是经常出现的问题，笔者也曾经因为准备不充分然后在面试中没能推导出支持向量机的公式，因此决定在这里整理一下支持向量机最基础的公式推导部分。

此处只考虑了线性可分情况下的支持向量机，以后再加上非线性可分情况下的支持向量机。

假定样本空间如下

$\{(x_1, y_1), (x_2, y_2), ..., (x_N, y_N)\}$

共有N个向量，其中$x_k$是一个特征向量而不是一个单一数值。

这是一个二分类问题，所以$y = +1$或者$y = -1$。那么我们就可以得到
$y = w^Tx + b = \begin{cases} +1, & w^Tx + b \ge 1 \\ -1, & w^Tx + b \le -1 \end{cases}$
那么，我们可以得到
$y_i \cdot (w^Tx_i + b) \ge 1, i = 1, 2, ..., N$
因为我们现在只讨论线性可分情况下的支持向量机，那么在这个样本空间中一定存在一个超平面可以将样本集按照y的值分割城两个部分，这个超平面可以表示为
$w^Tx + b = 0$
根据这个超平面的表达式以及第一步推到中我们得到的结果，可以得到这个样本集中任意一个样本点距离超平面的距离：
$\gamma = \frac{|w^Tx + b|}{||w||} \ge \frac{1}{||w||}$
由此，我们还可以进一步得到整个margin的宽度：
$\gamma = \frac{2}{||w||}$
由此，根据第一步和第三步的结果，我们可以得到最基本的目标函数：
$arg\,\max_{w, b}\frac{2}{||w||}$ $s.t.\; y_i(w^Tx_i + b) \ge 1,\;i = 1, 2, ..., N$
我们还可以对这个目标函数进一步做变化：
$arg\,\min_{w, b}\frac{1}{2}||w||^2$ $s.t.\; y_i(w^Tx_i + b) \ge 1,\;i = 1, 2, ..., N$
到了这一步，我们无法继续直接进行计算了，因此引入拉格朗日乘子：
$L(w, b, \alpha) = \frac{1}{2}||w||^2 + \sum_i \alpha_i[1 - y_i(w^Tx_i + b)]$
对w和b分别求L的偏导，并令其偏导数等于0：
$\frac{\partial{L}}{\partial{w}} = w - \sum_i \alpha_iy_ix_i = 0 \; \Rightarrow w = \sum_i \alpha_iy_ix_i$ $\frac{\partial{L}}{\partial{b}} = \sum_i \alpha_iy_i = 0$
将第七步得到的w和b代入L函数：
$\begin{equation}\begin{split} L(w, b, \alpha) &= \frac{1}{2}w^Tw + \sum_i\alpha_i - \sum_i\alpha_iy_iw^Tx_i - b\sum_i\alpha_iy_i \\ &= \frac{1}{2}(\sum_i\alpha_iy_ix_i)^T(\sum_i\alpha_iy_ix_i) + \sum_i\alpha_i - \sum_i\alpha_iy_i(\sum_i\alpha_iy_i)^Tx_i \\ &= \frac{1}{2}(\sum_i\alpha_iy_ix_i)^T(\sum_i\alpha_iy_ix_i) + \sum_i\alpha_i - (\sum_i\alpha_iy_ix_i)^T(\sum_i\alpha_iy_ix_i) \\ &= \sum_i\alpha_i - \frac{1}{2}(\sum_i\alpha_iy_ix_i)^T(\sum_i\alpha_iy_ix_i) \\ &= \sum_i\alpha_i -\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{split}\end{equation}$
至此，我们的目标函数已经变成了：
$arg\,\max_\alpha (\sum_i\alpha_i -\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_jx_i^Tx_j)$ $s.t. \; \sum_i \alpha_iy_i = 0$ $\alpha_i\ge 0, i = 1,2,...,N$
使用数值方法解出$\alpha$以后，我们就可以得到：
$w^* = \sum_i \alpha_i^*y_ix_i$

参考文献