【机器学习基础】系列博客为参考周志华老师的《机器学习》一书，自己所做的读书笔记。
本文为原创文章，未经本人允许，禁止转载。转载请注明出处。
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)中有不等式约束，因此上述过程需满足KKT条件，即要求：
\[\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$呢？有两种方法：
- 这是一个二次规划问题，可使用通用的二次规划算法来求解。
- 使用更为高效的其他算法，例如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)等。
