【机器学习基础】第十七课:支持向量机之对偶问题

求解支持向量机,二次规划

Posted by x-jeff on November 18, 2020

【机器学习基础】系列博客为参考周志华老师的《机器学习》一书,自己所做的读书笔记。
本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.对偶问题

我们希望求解

\[\begin{align*} &\min \limits_{\mathbf w,b} \quad \frac{1}{2} \lVert \mathbf w \rVert ^2 \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} s.t.& y_i(\mathbf w^T \mathbf x_i +b) \geqslant 1,i=1,2,...,m \\ \end{array} \end{align*} \tag{1.1}\]

来得到最大间隔划分超平面所对应的模型:

\[f(\mathbf x)=\mathbf w^T \mathbf x +b \tag{1.2}\]

其中$\mathbf w,b$是模型参数。注意到式(1.1)本身是一个凸二次规划(convex quadratic programming)问题,能直接用现成的优化计算包求解,但我们可以有更高效的办法。

“二次规划”相关内容见本文第2部分。

对式(1.1)使用拉格朗日乘子法可得到其“对偶问题”(dual problem)。具体来说,对式(1.1)的每条约束添加拉格朗日乘子$\alpha _i \geqslant 0$,则该问题的拉格朗日函数可写为:

\[L(\mathbf w,b,\mathbf \alpha)=\frac{1}{2} \lVert \mathbf w \rVert ^2 + \sum_{i=1}^m \alpha_i (1-y_i (\mathbf w^T \mathbf x_i +b)) \tag{1.3}\]

其中$\mathbf \alpha=(\alpha_1;\alpha_2;…;\alpha _m)$。令$L(\mathbf w,b,\mathbf \alpha)$对$\mathbf w$和$b$的偏导为零可得:

\[\mathbf w=\sum_{i=1}^m \alpha_i y_i \mathbf x_i \tag{1.4}\] \[0=\sum_{i=1}^m \alpha_i y_i \tag{1.5}\]

将式(1.4)代入式(1.3),即可将$L(\mathbf w,b,\mathbf \alpha)$中的$\mathbf w$和$b$消去,再考虑式(1.5)的约束,就得到式(1.1)的对偶问题:

\[\begin{align*} &\max \limits_{\mathbf \alpha} \quad \sum_{i=1}^m \alpha_i-\frac{1}{2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \mathbf x_i^T \mathbf x_j \\ & \begin{array}{r@{\quad}l@{}l@{\quad}l} s.t.& \sum_{i=1}^m \alpha_i y_i=0 \\ & \alpha_i \geqslant 0,i=1,2,...,m \\ \end{array} \end{align*} \tag{1.6}\]

关于“对偶问题”的讲解请见:对偶问题

解出$\mathbf \alpha$后,求出$\mathbf w$与$b$即可得到模型:

\[\begin{align} f(\mathbf x) & = \mathbf w^T \mathbf x +b \\ & = \sum_{i=1}^m \alpha_i y_i \mathbf x_i ^T \mathbf x + b \end{align} \tag{1.7}\]

从对偶问题式(1.6)解出的$\alpha_i$是式(1.3)中的拉格朗日乘子,它恰对应着训练样本$(\mathbf x_i,y_i)$。注意到式(1.1)中有不等式约束,因此上述过程需满足KTT条件,即要求:

\[\left \{ \begin{array}{c} \alpha_i \geqslant 0 \\ y_i f(\mathbf x_i) -1 \geqslant 0 \\ \alpha_i (y_i f(\mathbf x_i)-1)=0 \end{array} \right. \tag{1.8}\]

于是,对任意训练样本$(\mathbf x_i,y_i)$,总有$\alpha_i=0$或$y_i f(\mathbf x_i)=1$。若$\alpha _i=0$,则该样本将不会在式(1.7)的求和中出现,也就不会对$f(\mathbf x)$有任何影响;若$\alpha _i >0$,则必有$y_i f(\mathbf x_i)=1$,所对应的样本点位于最大间隔边界上,是一个支持向量。⚠️这显示出支持向量机的一个重要性质:训练完成后,大部分的训练样本都不需保留,最终模型仅与支持向量有关。

那么我们该如何求解式(1.6),得到$\mathbf \alpha$呢?有两种方法:

  1. 这是一个二次规划问题,可使用通用的二次规划算法来求解。
  2. 使用更为高效的其他算法,例如SMO(Sequential Minimal Optimization)算法。

求出$\mathbf \alpha$后,可通过式(1.4)求得$\mathbf w$的值。

如何确定偏移项$b$呢?注意到对任意支持向量$(\mathbf x_s,y_s)$都有$y_s f(\mathbf x_s)=1$,即:

\[y_s(\sum _{i\in S} \alpha_i y_i \mathbf x_i^T \mathbf x_s +b)=1 \tag{1.9}\]

其中$S=\{i \mid \alpha_i > 0,i=1,2,…,m \}$为所有支持向量的下标集。理论上,可选取任意支持向量并通过求解式(1.9)获得$b$,但现实任务中常采用一种更鲁棒的做法:使用所有支持向量求解的平均值:

\[b=\frac{1}{\mid S \mid} \sum_{s\in S} (y_s - \sum _{i \in S} \alpha_i y_i \mathbf x_i ^T \mathbf x _s )\]

2.二次规划

二次规划(Quadratic Programming,简称QP)是一类典型的优化问题,包括凸二次优化非凸二次优化。在此类问题中,目标函数是变量的二次函数,而约束条件是变量的线性不等式。

假定变量个数为d,约束条件的个数为m,则标准的二次规划问题形如:

\[\begin{align*} &\min \limits_{\mathbf x} \quad \frac{1}{2} \mathbf x^T \mathbf Q \mathbf x + \mathbf c^T \mathbf x \\ & \begin{array}{r@{\quad}r@{}l@{\quad}l} s.t.& \mathbf A \mathbf x \leqslant \mathbf b \\ \end{array} \end{align*} \tag{2.1}\]

非标准二次规划问题中可以包含等式约束。注意到等式约束能用两个不等式约束来代替;不等式约束可通过增加松弛变量的方式转化为等式约束。

其中$\mathbf x$为d维向量,$\mathbf Q \in \mathbb R^{d \times d}$为实对称矩阵,$\mathbf A \in \mathbb R^{m\times d}$为实矩阵,$\mathbf b \in \mathbb R^m$和$\mathbf c \in \mathbb R^d$为实向量,$\mathbf A \mathbf x \leqslant \mathbf b$的每一行对应一个约束。

若$\mathbf Q$为半正定矩阵,则式(2.1)目标函数是凸函数,相应的二次规划是凸二次优化问题;此时若约束条件$\mathbf A \mathbf x \leqslant \mathbf b$定义的可行域不为空,且目标函数在此可行域有下界,则该问题将有全局最小值。若$\mathbf Q$为正定矩阵,则该问题有唯一的全局最小值。若$\mathbf Q$为非正定矩阵,则式(2.1)是有多个平稳点和局部极小点的NP难问题

常用的二次规划解法有椭球法(ellipsoid method)、内点法(interior point)、增广拉格朗日法(augmented Lagrangian)、梯度投影法(gradient projection)等。