此文是学习林轩田老师的机器学习技法第二课——Dual Support Vector Machine——的课堂笔记，有关 SVM 公式推导。
给定原公式：
$$
\frac{1}{2}\min_{b, \mathbf{w}} \mathbf{w^T w} \\
s.t. \ y_n(\mathbf{w^T \mathbf{x_n}} + b) \ge 1
$$
（为简化求解，公式与前次笔记稍有不同，但等价）这节课做了一系列的变换，最终有什么效果呢？
参考
拉格朗日乘数法
拉格朗日乘数法可以把限制条件和目标函数结合成一个整体。原公式整合成：
$$
L(b, \mathbf{w}, \alpha) = \frac{1}{2} \mathbf{w^T w} + \sum_{n=1}^{N}\alpha_n(1 - y_n(\mathbf{w^T \mathbf{xn}} + b))
$$
SVM 求解公式变为：
$$
\min{b,\mathbf{w}} (\max_{all\ \alphan \ge 0}L(b, \mathbf{w}, \alpha)) = \min{b, \mathbf{w}}(\infty\ if\ violate;\ \mathbf{w^T w}\ if\ feasible)
$$
拉格朗日对偶问题
利用对偶问题，对上步的求解公式取下限：
$$
\min{b,\mathbf{w}} (\max{all\ \alphan \ge 0}L(b, \mathbf{w}, \alpha)) \ge \max{all\ \alpha’n \ge 0} (\min{b,\mathbf{w}} L(b, \mathbf{w}, \alpha’))
$$
至于为何成立我没有细究，只能说这符合直觉。因为，考虑 $L(b, \mathbf{w}, \alpha)$ 为一个波动的函数，视 $\max$ 为取波峰， $\min$ 取波谷，那么从波峰中最小的应该不小于波谷中最大的。
有证明表示，对拉格朗日对偶问题，如果满足 强对偶 的三个条件，原始函数为凸函数、原始问题可解、原始限制条件是线性的，就可以在上式中取等，而 SVM 刚好满足。 : P
关于 $\alpha$ 函数
接下来对求解公式做2步“简化”，使之成为仅关于 $\alpha$ 的函数。
去 $b$： 考虑在极值点，变量的梯度都应该为 $0$，所以 $b$ 的梯度
$$-\sum_{n=1}^N \alpha_n yn = 0$$
把该式置于条件中并化简，得到求解公式等价式：
$$
\max{\alphan} \min\mathbf{w}(\frac{1}{2} \mathbf{w^T w} + \sum_{n=1}^{N}\alpha_n(1 - y_n \mathbf{w^T \mathbf{x_n}})) \\
s.t.\ all\ \alphan \ge 0,\ \sum{n=1}^N \alpha_n y_n = 0
$$
去 $\mathbf{w}$： $\mathbf{w}$ 的梯度
$$\mathbf{w}i - \sum{n=1}^N \alpha_n yn x{n,i} = 0 \\
\Rightarrow \mathbf{w} = \sum_{n=1}^{N} \alpha_n y_n \mathbf{xn}$$
把该式置于条件中并经过化简，得到最终的求解公式：
$$
\max{\alphan} (-\frac{1}{2}|\sum{n=1}^{N} \alpha_n y_n \mathbf{xn}|^2 + \sum{n=1}^{N}\alpha_n) \\
s.t.\ all\ \alphan \ge 0,\ \sum{n=1}^N \alpha_n yn = 0,\ \mathbf{w} = \sum{n=1}^{N} \alpha_n y_n \mathbf{x_n}
$$
注意其中的 $\mathbf{x_n}$ 及其求和均为向量，原本的求最小因为消去 $b, \mathbf{w}$ 而除去。
KKT 条件
对凸优化问题，KKT 条件是一组解成为最优解的充分必要条件。（见“优化问题中的对偶性理论”）而 SVM 求解原式和对偶式（强对偶）都有最优解，所以最优解满足 KKT 条件。
这其中有 2 个条件可以用于从最最优 $\alpha$ 中解出最做优 $b, \mathbf{w}$
$$
\mathbf{w} = \sum_{n=1}^{N} \alpha_n y_n \mathbf{x_n} \\
\alpha_n(1 - y_n(\mathbf{w^T \mathbf{x_n}} + b)) = 0
$$
二次规划求解
与上一课一样，因为求解问题是一个二次规划问题，所以可以借助相关的工具。在此之前，需要做一些变换。
最大化变最小化 最优化工具往往求最小值。求解公式取相反数：
$$
\min_{\alphan} (\frac{1}{2}|\sum{n=1}^{N} \alpha_n y_n \mathbf{xn}|^2 - \sum{n=1}^{N}\alpha_n) \\
$$
隐藏 $\mathbf{w}$ 的限制条件 使公式完全变为关于 $\alpha$ 的函数，剩下的 $x, y$ 都是已知量
$$
s.t.\ all\ \alphan \ge 0,\ \sum{n=1}^N \alpha_n y_n = 0
$$
展露二次项系数 求解公式中二次项系数不易发现，做拆分：
$$|\sum_{n=1}^{N} \alpha_n y_n \mathbf{xn}|^2 \\
=(\sum{n=1}^{N} \alpha_n y_n \mathbf{xn})^\mathbf{T}(\sum{n=1}^{N} \alpha_n y_n \mathbf{xn})
=(\sum{m=1}^{N} \alpha_m y_m \mathbf{xm^T})(\sum{n=1}^{N} \alpha_n y_n \mathbf{xn})\\
=\sum{m=1}^{N} \sum_{n=1}^{N} y_m \mathbf{x_m^T} y_n \mathbf{x_n} \alpha_m \alpha_n
$$
注意该式原始是2个（由多个向量求和得到的）向量的内积，最后一步变换使用了向量的分配律。可见，二次项 $\alpha_m \alpha_n$ 的系数为 $y_m \mathbf{x_m^T} y_n \mathbf{x_n}$。
最后给出 完整公式：
$$
\min_{\alphan} (\frac{1}{2}\sum{m=1}^{N} \sum_{n=1}^{N} y_m \mathbf{x_m^T} y_n \mathbf{x_n} \alpha_m \alphan - \sum{n=1}^{N}\alpha_n) \\
s.t.\ all\ \alphan \ge 0,\ \sum{n=1}^N \alpha_n yn = 0
$$
利用二次规划工具解决该问题，解出 $\alpha$ 后，再利用 KKT 公式的2个条件，解出 $\mathbf{w}, b$:
$$
\mathbf{w} = \sum{n=1}^{N} \alpha_n y_n \mathbf{x_n} \\
b = y_n - \mathbf{w^T \mathbf{x_n}}\ ,\ s.t.\ \alpha_n \ne 0
$$
值得注意的是，二次项系数矩阵是 $N \times N$ 的大型矩阵，而且并非上节课的对角矩阵，需要专为 SVM 设计的二次规划求解工具。
SV 与后续
很明显，利用 $\alpha$ 求解 $\mathbf{w}, b$ 时，如果 $\alpha_i$ 为0，对求解没有影响。也就是说，对应 $\alpha_i = 0$ 的向量（数据点）对求解没有影响。联系上节课，即对应 $\alpha_i \gt 0$ 的向量为支持向量（SV）。
课程中对原始向量 $\mathbf{x}$ 做了向N维向量 $\mathbf{z}$ 的映射，$\mathbf{x}$ 替换成 $\mathbf{z}$ 后对推导没有影响。而这节课的变换似乎没有简化求解，至于为何目的，只有后续揭晓了。
