@wjcper2008 2017-02-28T15:39:08.000000Z 字数 4371 阅读 1676

SMO优化算法

机器学习基础 SVM

http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
http://blog.csdn.net/xuanyuansen/article/details/41153023

1. SMO简介

SMO算法(Sequential minimal optimization)由Microsoft Research的John C. Platt 在1998年提出, 并成为最快的二次规划优化算法, 特别针对线性SVM和数据稀疏时性能更优。关于SMO最好的资料就是他本人写的《Sequential Minimal Optimization A Fast Algorithm for Training Support Vector Machines》了。

对于SVM的对偶问题, 数据集 $\{(x_i,y_i)\}$ , 要求解 ${\alpha_1,\cdots,\alpha_n}$ 上求最大值 $W(\alpha)$ 二次规划问题:

min α s . t . W (α) = \sum i n α i - 1 2 \sum i, j = 1 n y i y j α i α j < x i, x j > 0 \leq α i \leq C \sum i n y i α i = 0, i = 1, \dots, n (1)

$\begin{equation}\label{eq:SVMDual} \begin{array}{ll} \min_{\alpha} & W(\alpha) = \sum_i^n \alpha_i - \frac12\sum_{i,j=1}^n y_i y_j \alpha_i \alpha_j <x_i,x_j> \\ s.t. & 0 \leq \alpha_i \leq C \\ & \sum_i^n y_i \alpha_i = 0,~ i=1,\cdots,n \end{array} \end{equation}$

2. SMO的更新公式推导

2.1 步骤一:视为一个二元函数

求解 ${\alpha_1,\cdots,\alpha_n}$ , 思路如下:

按照坐标上升法(目标求最大值), 可固定除 $\alpha_i$ 以外的所有的 $\alpha$ , 然后在 $\alpha_i$ 上求极值.

然而, 对于SVM, 由于约束条件 $\sum_{k=1}^n y_k \alpha_k = 0$ . 如果固定其他的 $\alpha$ , 那么 $\alpha_i$ 将不是变量.

因此, SMO算法需要同时选择两个 $\alpha$ 进行同时更新, 比如 $\alpha_i$ 和 $\alpha_j$ , 固定其他参数. 又由于

y i α i + y j α j = - \sum k = 3 l y k α k = ϵ, (2)

$\begin{equation} \label{eq:SVMequ} y_i\alpha_i + y_j\alpha_j = -\sum_{k=3}^l y_k\alpha_k = \epsilon, \end{equation}$

可以简化目标函数 $W(\alpha)$ 为只关于 $\alpha_i$ 和 $\alpha_j$ 的二元函数, Const表示常数项(不包含 $\alpha_i$ 和 $\alpha_j$ ).

min Ψ (α i, α j) = 1 2 K i i α 2 i + 1 2 K j j α 2 j + y i y j K i j α i α j - (α i + α j) + y i v i α i + y j v j α j + C o n s t (3)

$\begin{equation}\label{eq:SMOObj} \begin{array}{ll} \min Ψ(\alpha_i,\alpha_j) = & \frac12K_{ii}\alpha_i^{2}+\frac12K_{jj}\alpha_j^2+y_iy_jK_{ij}\alpha_i\alpha_j \\ & -(\alpha_i+\alpha_j)+y_iv_i\alpha_i+y_jv_j\alpha_j+Const \end{array} \end{equation}$
其中,

vk=∑Nl≠i,jαjyjK(xk,xl), k=i,j $v_k=\sum_{l\neq i,j}^N\alpha_jy_jK(x_k,x_l),~k=i,j$ .

2.2 步骤二: 视为一元函数

等式约束 $\eqref{eq:SVMequ}$ , 其中 $\epsilon$ 在某步迭代中可视为常数. 在等式两边乘以 $y_i$ , 且 $y^2_i = 1$ , 然后, 将上式用 $\alpha_i$ 用 $\alpha_j$ 表示, 得

α i = (ϵ - y j α j) y i

$\alpha_i=(\epsilon-y_j\alpha_j)y_i$

并代回到 $\eqref{eq:SMOObj}$ 中, 得

min Ψ (α j) = 1 2 K i i (ϵ - α j y j) 2 + 1 2 K j j α 2 j + y i K i j (ϵ - α j y j) α j - (ϵ - y j α j) y i - α j + v i (ϵ - y j α j) + y j v j α j + C o n s t (4)

$\begin{equation}\label{eq:SMOObj1} \begin{array}{ll} \min \Psi(\alpha_j) = & \frac12K_{ii}(\epsilon-\alpha_jy_j)^{2}+\frac12K_{jj}\alpha_j^2+y_iK_{ij}(\epsilon-\alpha_jy_j)\alpha_j \\ & -(\epsilon-y_j\alpha_j)y_i - \alpha_j + v_i(\epsilon-y_j\alpha_j) + y_jv_j\alpha_j+Const \end{array} \end{equation}$

2.3 对一元函数 $\Psi$ 求极值点

对 $\Psi$ 式 $\eqref{eq:SMOObj1}$ 关于 $\alpha_j$ 求导,并令其为0. 可求得 $\alpha_j$ 的更新解析解.

\partial Ψ ( α 2 ) \partial α 2 = (K i i + K j j - 2 K i j) α j - K 11 ζ y 2 + K 12 ζ y 2 + y 1 y 2 - 1 - v 1 y 2 + v 2 y 2 = 0

$\begin{array}{ll} \frac{\partial \Psi (\alpha_2)}{\partial \alpha_2}= & (K_{ii}+K_{jj}-2K_{ij})\alpha_j-K_{11}\zeta y_2 \\ & +K_{12}\zeta y_2+y_1y_2-1-v_1y_2+v_2y_2=0 \end{array}$
具体的算法步骤描述如下:

image_1b9vr5kh4rmc1m37h5tslv16nq9.png-36.5kB

使用启发式算法选择更新的 $\alpha_i$ 和 $\alpha_j$ 对, 使得目标值更新, 最大程度的向全局最优值逼近.

固定其他参数, $W(\alpha)$ 关于 $\alpha_i$ 和 $\alpha_j$ 求导, 得到子问题的极值. [而 $\alpha_j$ 又可由 $\alpha_i$ 表示]

SMO之所以高效就是因为在固定其他参数后，对一个参数优化过程很高效.

3. SMO的变量 $\alpha$ 上界和下界

由 $\eqref{eq:SVMequ}$ 可知,

y i α i + y j α j = ϵ (5)

$\begin{equation} y_i\alpha_i + y_j\alpha_j = \epsilon \end{equation}$
以及

0 \leq α \leq C (6)

$\begin{equation} 0 \leq \alpha \leq C \end{equation}$

当 $y_i$ 和 $y_j$ 异号时, 如-1和+1. 有 $\alpha_i - \alpha_j = \epsilon$ 或 $\alpha_j - \alpha_i = \epsilon$ .

对于 $\alpha_i - \alpha_j = \epsilon$ 情况, 有 $\alpha_i = \alpha_j + \epsilon$ .
对于 $\alpha_i$ 的下界, 当 $\alpha_j =0$ 取得. 故, $L_{\alpha_i} = \max\{0, \epsilon\} = \max\{0, \alpha_i - \alpha_j\}$ .
对于 $\alpha_i$ 的上界, 当 $\alpha_j =C$ 取得. 故, $H_{\alpha_i} = \min\{C, \epsilon+C\} = \min\{0, \alpha_i - \alpha_j + C\}$ .
对于 $\alpha_j - \alpha_i = \epsilon$ 情况, 有 $\alpha_i = \alpha_j - \epsilon$ .
对于 $\alpha_i$ 的下界, 当 $\alpha_j =0$ 取得. 故, $L_{\alpha_i} = \max\{0, -\epsilon\} = \max\{0, \alpha_i - \alpha_j\}$ .
对于 $\alpha_i$ 的上界, 当 $\alpha_j =C$ 取得. 故, $H_{\alpha_i} = \min\{C, -\epsilon+C\} = \min\{0, \alpha_i - \alpha_j + C\}$ .

当 $y_i$ 和 $y_j$ 同号时, 如都为+1或-1. 有 $\alpha_i + \alpha_j = \epsilon$ 或 $\alpha_j + \alpha_i = -\epsilon$ .

对于 $\alpha_i + \alpha_j = \epsilon$ 情况, 有 $\alpha_i = \epsilon - \alpha_j$ .
对于 $\alpha_i$ 的下界, 当 $\alpha_j =C$ 取得. 故, $L_{\alpha_i} = \max\{0, \epsilon - C\} = \max\{0, \alpha_i + \alpha_j - C\}$ .
对于 $\alpha_i$ 的上界, 当 $\alpha_j = 0$ 取得. 故, $H_{\alpha_i} = \min\{C, \epsilon\} = \min\{0, \alpha_i + \alpha_j\}$ .
对于 $\alpha_i + \alpha_j = -\epsilon$ 情况, 有 $\alpha_i = -\epsilon - \alpha_j$ .
对于 $\alpha_i$ 的下界, 当 $\alpha_j = C$ 取得. 故, $L_{\alpha_i} = \max\{0, -\epsilon - C\} = \max\{0, \alpha_i + \alpha_j - C\}$ .
对于 $\alpha_i$ 的上界, 当 $\alpha_j = 0$ 取得. 故, $H_{\alpha_i} = \min\{C, -\epsilon\} = \min\{0, \alpha_i + \alpha_j\}$ .