SVM推导

SVM(support vector machine)支持向量机. ## 1 间隔与支持向量 + 样本集 $D=\{(x_1, y_1), \cdots, (x_m, y_m)\}$, 其中 $x_i\in \mathbb{R}^d, y_i\in\{-1, 1\}, i=1,\cdots,m$. + 划分超平面为 $$ w^T x + b = 0, $$ 其中$w=(w_1, \cdots, w_d)^T$. + 点 $x$ 到平面的距离: 设 $x_0$ 是平面上一点, 即它满足 $$ w^T x_0 + b = 0, $$ 则 $x$ 到平面的距离即为向量 $x-x_0$ 在平面法向 $\frac{w}{\lVert w\rVert}$ 上投影长度: $$ \frac{\lvert w^T(x-x_0)\rvert}{\lVert w\rVert} = \frac{\lvert w^T x + b\rvert}{\lVert w\rVert}. $$ 由此我们还可以知道, 原点到平面距离为 $$ \frac{\lvert w^T 0 + b\rvert}{\lVert w\rVert} = \frac{\lvert b\rvert}{\lVert w\rVert}. $$ + **支持向量:** 设超平面 $(w, b)$ 能将样本分类正确, 即对 $(x_i, y_i)\in D$ 有 $$ \left\{ \begin{aligned} w^Tx_i + b &> 0 \quad y_i = +1\\ w^Tx_i + b &< 0 \quad y_i = -1 \end{aligned} \right. $$ 通过变换$w$以及$b$可以使得下式成立: $$ \left\{ \begin{aligned} w^Tx_i + b &\geq 1 \quad y_i = +1\\ w^Tx_i + b &\leq -1 \quad y_i = -1 \end{aligned} \right. $$ 若$D$中样本使得上式等号成立, 则称其为**支持向量**. 两个异类支持向量到超平面的距离之和为 $$ \gamma = \frac{2}{\lVert w\rVert}, $$ 称其为**间隔**. + **目标:** 寻找 $(w, b)$ 使 $\gamma$ 最大, 即 $$ \begin{aligned} &\max_{w, b} \frac{2}{\lVert w\rVert} \\ &s.t.\left\{ \begin{aligned} w^Tx_i + b &\geq 1 \quad y_i = +1\\ w^Tx_i + b &\leq -1 \quad y_i = -1 \end{aligned} \right. \Leftrightarrow y_i(w^T x_i+b)\geq 1, \end{aligned} $$ 转变为极小化问题: $$ \begin{aligned} &\min_{w, b} \frac12 \lVert w\rVert^2 \\ &s.t.\quad y_i(w^T x_i+b)\geq 1, \quad i=1,\cdots,m. \end{aligned} \tag{1.1} $$ 这是个凸二次规划问题, 可以用相应的优化方法求解. ## 2 对偶问题 Lagrange 乘子法得到的 Lagrange 函数为 $$ L(w, b, \alpha) = \frac12 \lVert w\rVert^2 + \sum_{i= 1}^{m} \alpha_i\left(1-y_i(w^T x_i+b) \right), $$ 其中 $\alpha = (\alpha_1, \cdots, \alpha_m)^T$. 将 $L$ 对 $w$ 和 $b$ 的偏导置零, 有 $$ \begin{aligned} \frac{\partial L(w, b, \alpha)}{\partial w} &= w - \sum_{i=1}^{m}\alpha_i y_i x_i = 0 \Rightarrow w = \sum_{i = 1}^{m}\alpha_i y_i x_i, \\ \frac{\partial L(w, b, \alpha)}{\partial b} &= \sum_{i = 1}^{m}\alpha_i y_i = 0. \end{aligned} $$ 将上面第一式代入$L(w, b, \alpha)$, 再考虑上面第二式的约束, 得到对偶问题 $$ \begin{aligned} &\quad \max_{\alpha}\frac12 \sum_{i = 1}^{m}\alpha_i y_i x_i^T\sum_{i = 1}^{m}\alpha_i y_i x_i + \sum_{i = 1}^{m}\alpha_i\left( 1-y_i(\sum_{i = 1}^{m}\alpha_i y_i x_i^T x_i + b) \right) \\ & = \max_{\alpha} \sum_{i = 1}^{m} \alpha_i - \frac12 \sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_i \\ &\qquad s.t. \\ &\qquad\qquad \begin{aligned} \sum_{i = 1}^{m} \alpha_i y_i &= 0 \\ \alpha_i &\geq 0 \qquad i=1,\cdots,m. \end{aligned} \end{aligned} $$ 求出这个问题的解 $\alpha$, 则可求出法向 $w=\sum_{i = 1}^{m}\alpha_i y_i x_i$, 于是得到分类函数: $$ f(x) = \sum_{i = 1}^{m}\alpha_i y_i x_i^T x + b. \tag{2.1} $$ 另外, 因为 $(1.1)$ 式有不等式约束, 所以上述过程还需满足 KKT(Karush-Kuhn-Tucker) 条件: $$ \left\{ \begin{aligned} \alpha_i &\geq 0 \\ y_i(f(x_i) - 1) &\geq 0 \\ \alpha_i(y_i f(x_i) - 1) &= 0 \end{aligned} \right. $$ **分析:** 1. 若 $\alpha_i = 0$, 则对 $(2.1)$ 式不起作用; 2. 若 $\alpha_i > 0$, 则必有 $y_i f(x_i) = 1$, 即 $x_i$是支持向量, $$ \begin{aligned} &\Rightarrow y(w^T x_i+b) = 1\\ &\Rightarrow b = \frac{1}{y_i} - w^T x_i. \end{aligned} $$ 因此, 我们有 $$ \begin{aligned} f(x) &= \sum_{i = 1}^{m} \alpha_i y_i x_i^T x + b \\ &= \sum_{x_i \text{为支持向量}} \alpha_i y_i x_i^T x + b. \end{aligned} $$ 理论上, 我们只需任取一个正支持向量 $x_{i_0}$, 即可计算出 $b=1-w^T x_{i_0}$. 但现实中, 我们常用更鲁棒的方法计算 $$ b = \frac{1}{\lvert S\rvert} \sum_{s\in S}\left(\frac{1}{y_s} - \sum_{i\in S}\alpha_i y_i x_i^T x_s \right) $$ 其中 $S=\{i: \alpha_i > 0 \}$. 即有**最终公式** $$ f(x) = \sum_{i\in S} \alpha_i y_i x_i^T x + \frac{1}{\lvert S\rvert} \sum_{s\in S}\left(\frac{1}{y_s} - \sum_{i\in S}\alpha_i y_i x_i^T x_s \right). $$ ## 3 求解对偶问题 $$ \begin{aligned} &\max_{\alpha} \sum_{i = 1}^{m} \alpha_i - \frac12 \sum_{i = 1}^{m}\sum_{j = 1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_i \\ &\ s.t. \\ &\qquad \begin{aligned} \sum_{i = 1}^{m} \alpha_i y_i &= 0 \\ \alpha_i &\geq 0 \qquad i=1,\cdots,m. \end{aligned} \end{aligned} \tag{3.1} $$ + SMO(sequential minimal optimization)算法: 利用约束 $\sum_{i = 1}^{m}\alpha_i y_i = 0$, 不断执行以下步骤: 1. 选取一对需更新的变量 $\alpha_i$, $\alpha_j$; 2. 固定 $\alpha_i$ 和 $\alpha_j$ 以外的参数, 求解 $(3.1)$更新 $\alpha_i$ 和 $\alpha_j$. + 怎么开始第一步? 选取的 $\alpha_i$ 和 $\alpha_j$ 对应的两样本之间间隔最大. **分析:**固定其他参数后, 仅优化两个参数的过程能做到非常高效. 仅考虑 $\alpha_i$ 和 $\alpha_j$, 约束条件可写为 $$ \alpha_i y_i + \alpha_j y_j = c = -\sum_{k\neq i,j}\alpha_k \alpha_k \qquad \alpha_i, \alpha_j \geq 0, $$ 用其消去 $(3.1)$ 中变量 $\alpha_j$, 则得到一个关于 $\alpha_i$ 的单变量二次规划问题, 仅有的约束是 $\alpha_i \geq 0$, 这样的二次规划问题具有闭式解(解析解), 于是不必调用数值优化算法, 即可高校计算出更新后的 $\alpha_i$ 和 $\alpha_j$. ## 4 参考文献 + 周志华,《机器学习》, 清华大学出版社