一些推导关键步骤
目标函数
- 最原始的想法自然是考虑几何间隔 \[ \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}_