李航《统计学习方法》SMO算法推导中的思考

1. p.128

图中，从上式到下式的推导不是很明了，困惑在于上式中右边含有 $α_{1}, α_{2}$ 这样岂不是和左边的 $α_{2}$ 相消？若能相消，上述求偏导的过程中岂不是忽略了 $v_{1}, v_{2}$ 是 $α_{1}, α_{2}$ 的函数？答案并非如此，左边的 $α$ 与右边的 $α_{2}$ 相当不同。

2. 定理7.6的证明

即求最优化问题:

min_{α_{1}, α_{2}} W (α_{1}, α_{2}) = \frac{1}{2} K_{11} α_{1}^{2} + \frac{1}{2} K_{2} 2 α_{2}^{2} + y_{1} y_{2} K_{21} α_{1} α_{2} - (α_{1} + α_{2}) + y_{1} α_{1} \sum_{i = 3}^{N} y_{i} α_{i} K_{i 1} + y_{2} α_{2} \sum_{i = 3}^{N} y_{i} α_{i} K_{i 2} s . t . α_{1} y_{1} + α_{2} y_{2} = - \sum_{i = 3}^{N} y_{i} α_{i} = ς (1) 0 \leq α_{i} \leq C, i = 1, 2 (2)

沿着约束方向未经剪辑的解为:

α_{2}^{n e w, u n c} = α_{2}^{o l d} + \frac{y_{2} (E_{1} - E_{2})}{η}

其中，

η = K_{11} + K_{22} - 2 K_{21} = ‖ Φ (x_{1}) - Φ (x_{2}) ‖^{2} E_{i} = g (x_{i}) - y_{i}, i = 1, 2 g (x) = \sum_{i = 1}^{N} α_{i} y_{i} K (x_{i}, x) + b

$E_{i}$ 为函数 $g (x_{i})$ 对输入 $x_{i}$ 的预测值与真实输出 $y_{i}$ 之间的差.

证明：

引入记号变量 $v_{i} = \sum_{j = 3}^{N} α_{j} y_{j} K (x_{i}, x_{j}) = g (x_{i}) - \sum_{j = 1}^{2} α_{j} y_{j} K (x_{i}, x_{j}) - b, i = 1, 2$
再由 $α_{1} y_{1} + α_{2} y_{2} = ς$ 和 $y_{i}^{2} = 1$ 可将目标函数 $W (α_{1}, α_{2})$ 表示成只含 $α_{2}$ 的函数:

W (α_{2}) = \frac{1}{2} K_{11} (ς - α_{2} y_{2})^{2} + \frac{1}{2} K_{22} α_{2}^{2} + y_{2} K_{21} (ς - α_{2} y_{2}) α_{2} - (ς - α_{2} y_{2}) y_{1} - α_{2} + v_{1} (ς - α_{2} y_{2}) + y_{2} v_{2} α_{2}

对 $α_{2}$ 求偏导可得:

\frac{\partial W}{\partial α_{2}} = K_{11} α_{2} + K_{22} α_{2} - 2 K_{21} α_{2} - K_{11} ς y_{2} + K_{21} ς y_{2} + y_{1} y_{2} - 1 - v_{1} y_{2} + v_{2} y_{2}

令其等于0,即可求出上述问题的最优解,得到:

(K_{11} + K_{22} - 2 K_{21}) α_{2} = y_{2} (y_{2} - y_{1} + ς K_{11} - ς K_{21} + v_{1} - v_{2}) (2 - 1)

这里，不同与书上，我先求 $v_{1} - v_{2}$ ,
由 $v_{i}$ 的定义可知 $v_{1} - v_{2}$ 为:

v_{1} - v_{2} = ⟮ g (x_{1}) - \sum_{j = 1}^{2} y_{j} α_{j} K_{1 j} - b ⟯ - ⟮ g (x_{2}) - \sum_{j = 1}^{2} y_{j} α_{j} K_{2 j} - b ⟯ = g (x_{1}) - g (x_{2}) + y_{1} α_{1} K_{21} - y_{1} α_{1} K_{11} + y_{2} α_{2} K_{22} - y_{2} α_{2} K_{21} ∵ α_{1} y_{1} + α_{2} y_{2} = ς, y_{1}^{2} = 1 ∴ α_{1} = (ς - y_{2} α_{2}) y_{1}, 代 入 得 ， = g (x_{1}) - g (x_{2}) + (ς - y_{2} α_{2}) K_{21} - (ς - y_{2} α_{2}) K_{11} - y_{2} α_{2} K_{21} + y_{2} α_{2} K_{22} = g (x_{1}) - g (x_{2}) + ς K_{21} - ς K_{11} + y_{2} α_{2} (K_{11} + K_{22} - 2 K_{21})

值得注意的是， $v_{1} - v_{2}$ 中的 $α_{1}, α_{2}$ 是没有更新前的 $α$ ,即 $α^{o l d}$

∴ v_{1} - v_{2} = g (x_{1}) - g (x_{2}) + ς K_{21} - ς K_{11} + y_{2} α_{2}^{o l d} (K_{11} + K_{22} - 2 K_{21})

将上式代入到式（2-1）中即可求得 $α_{2}^{n e w, u n c} = α_{2}^{o l d} + \frac{y_{2} (E_{1} - E_{2})}{η}$

李航《统计学习方法》SMO算法推导中的思考

1. p.128

2. 定理7.6的证明

证明：

相关推荐