一些推导关键步骤

目标函数

最原始的想法自然是考虑几何间隔 \[ \begin{array}{cc}{\max _{\vec{w}, b} \gamma} \\ {s . t . \quad \tilde{y}_{i}\left(\frac{\overrightarrow{\mathbf{w}}}{\|\overrightarrow{\mathbf{w}}\|_{2}} \cdot \overrightarrow{\mathbf{x}}_{i}+\frac{b}{\|\overrightarrow{\mathbf{w}}\|_{2}}\right) \geq \gamma, i=1,2, \cdots, N}\end{array} \]
但是几何间隔可以用函数间隔表示，且函数间隔可以缩放而不影响分类超平面的选择，因此才有令函数间隔等于1，再取倒数把max换成min，化简了目标函数 \[ \begin{array}{c}{\min _{\vec{w}, b} \frac{1}{2}\|\overrightarrow{\mathbf{w}}\|_{2}^{2}} \\ {\text {s.t.} \quad \tilde{y}_{i}\left(\overrightarrow{\mathbf{w}} \cdot \overrightarrow{\mathbf{x}}_{i}+b\right)-1 \geq 0, i=1,2, \cdots, N}\end{array} \]

min-max

在将问题定义为带有不等式约束的最优化问题之后，就要用到拉格朗日对偶性来将原始问题转为对偶问题
统计学习方法的描述如下：
- 对于最优化问题： \[ \begin{array}{ll}{\min _{x \in \mathbf{R}^{n}} f(x)} & {} \\ {\text { s.t. } \quad c_{i}(x) \leqslant 0, \quad i=1,2, \cdots, k} \\ {\qquad \begin{array}{ll}{h_{j}(x)=0,} & {j=1,2, \cdots, l}\end{array}}\end{array} \]
- 引入广义拉格朗日函数 \[ L(x, \alpha, \beta)=f(x)+\sum_{i=1}^{k} \alpha_{i} c_{i}(x)+\sum_{j=1}^{I} \beta_{j} h_{j}(x) \]
- 定义 \[ \theta_{P}(x)=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta) \]
- 可以判断，假如不满足约束条件的话，可以令拉格朗日乘子不为0从而使上式无穷大，满足情况的话，上式要最大只能让\(\alpha\)为0，\(\beta\)则不起作用，因此： \[ \theta_{P}(x)=\left\{\begin{array}{l}{f(x)} \ x满足原始问题约束 \\ {+\infty} \ 其他 \end{array}\right. \]
这样原始的最小化一个f就转换为最小化一个最大化的\(\theta\)，即 \[ \min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta) \]

对偶

max和min对换位置就得到对偶问题，即先针对\(x\)优化，再针对\(\alpha,\beta\)优化 \[ \begin{array}{l}{\max _{\alpha, \beta} \theta_{D}(\alpha, \beta)=\max _{\alpha, \beta} \min _{x} L(x, \alpha, \beta)} \\ {\text { s.t. } \quad \alpha_{i} \geqslant 0, \quad i=1,2, \cdots, k}\end{array} \]
对偶问题和原始问题的关系： \[ d^{*}=\max _{\alpha, \beta: \alpha_{i} \geqslant 0} \min _{x} L(x, \alpha, \beta) \leqslant \min _{x} \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)=p^{*} \]
证明：先看两边的里面一部分，左边是\(\min \ L\)，右边是\(\max \ L\)，尽管自变量不一样，但是当自变量固定时，必然有\(\min _{x} L(x, \alpha, \beta) \leqslant L(x, \alpha, \beta) \leqslant \max _{\alpha, \beta: \alpha_{i} \geqslant 0} L(x, \alpha, \beta)\)，现在把里面整体看成一个函数，只看外面，即比较左边的\(\max f_1\)和\(\min f_2\)，由上可知\(f_1\)处处小于等于\(f_2\)，那即便是\(f_1\)的最大值，也一定小于等于\(f_2\)的最小值，也就是所谓的“鸡头小于凤尾”，前提是鸡群里的每一只鸡小于等于凤群里的每一只凤。
SVM满足强对偶关系，即上式取到等号，因此优化原问题可以转化为优化对偶问题，方便引入核函数。
原始的min-max问题可以直接解，但不是对min-max形式直接求偏导，因为先对\(\alpha\)求偏导没有意义，我们是希望得到\(w,b\)使得对任意的\(\alpha \neq 0\)，\(\max L\)都可以取到最小值。

求解

转换为对偶问题之后，先对\(w,b\)求导令其为0，之后将得到的\(w,b\)回代入对偶问题得到： \[ 带入对偶问题：L(\overrightarrow{\mathbf{w}}, b, \vec{\alpha})=\frac{1}{2}\|\overrightarrow{\mathbf{w}}\|_{2}^{2}-\sum_{i=1}^{N} \alpha_{i} \tilde{y}_{i}\left(\overrightarrow{\mathbf{w}} \cdot \overrightarrow{\mathbf{x}}_{i}+b\right)+\sum_{i=1}^{N} \alpha_{i} \\ \] \[ \begin{aligned} L(\overrightarrow{\mathbf{w}}, b, \vec{\alpha})=\frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} & \alpha_{i} \alpha_{j} \tilde{y}_{i} \tilde{y}_{j}\left(\overrightarrow{\mathbf{x}}_{i} \cdot \overrightarrow{\mathbf{x}}_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \tilde{y}_{i}\left[\left(\sum_{j=1}^{N} \alpha_{j} \tilde{y}_