对偶支持向量机的价值
对于求解非线性支持向量机系数的QP，有$\tilde d+1$个变量和$N$个约束条件，对于经过非线性特征变换后$Z$空间的特征维数$\tilde d$一般很大。当$\tilde d$很大时，求解比较具有挑战性。
对偶支持向量机是支持向量机的另一种形式，它不依赖$\tilde d$，有$N$个变量和$N+1$个约束条件。
拉格朗日乘子法
正则化采用带约束的最小化方法 \[ \min\limits_{\mathbf w} E_{in}(\mathbf w)\mbox{ s.t. }\mathbf w^T\mathbf w \leq C， \] 可以通过如下等价的拉格朗日乘子法实现 \[ \min\limits_{\mathbf w} E_{aug}(\mathbf w)=E_{in}(\mathbf w)+{\lambda\over N}\mathbf w^T\mathbf w。 \] 正则化通过将$\lambda$作为确定值，代替$C$作为约束条件，求解更容易。对偶支持向量机不同于正则化，它将$N$个$\lambda$视为变量求解。
当$\boldsymbol\alpha_n$为拉格朗日乘子时，求解支持向量机参数的拉格朗日函数为 \begin{equation} \mathcal L(b, \mathbf w, \boldsymbol \alpha) = {1\over 2}\mathbf w^T\mathbf w + \sum_{n=1}^N\alpha_n\left(1-y_n\left(\mathbf w^T\mathbf z_n+b\right)\right)。 \end{equation}
拉格朗日对偶问题
根据拉格朗日函数，可得 \begin{equation} \begin{aligned} \mbox{SVM}\equiv &\min\limits_{b,\mathbf w}\max\limits_{\mbox{all }\alpha_n\geq 0}\mathcal L(b,\mathbf w, \boldsymbol\alpha)\\ =&\min\limits_{b,\mathbf w}\left(\infty\mbox{ if violating };{1\over 2}\mathbf w^T\mathbf w\mbox{ if feasible}\right)。 \end{aligned} \end{equation} 根据$b$和$\mathbf w$取值的划分，分两种情况解释上述公式：
- 任意violating的$(b,\mathbf w)$：$\max\limits_{\mbox{all } \alpha_n\geq 0}\left(\square+\sum_n\alpha_n(\mbox{some positive})\right)\rightarrow\infty$；
- 任意feasible的$(b,\mathbf w)$：$\max\limits_{\mbox{all } \alpha_n\geq 0}\left(\square+\sum_n\alpha_n(\mbox{all non-positive})\right)=\square$。
对$\alpha’_n\geq 0$的任意$\boldsymbol\alpha’$可得 \[ \min\limits_{b,\mathbf w}\max\limits_{\mbox{all } \alpha_n\geq 0}\mathcal L(b,\mathbf w, \boldsymbol\alpha)\geq\min\limits_{b,\mathbf w}\mathcal L(b,\mathbf w, \boldsymbol\alpha’)， \] 于是有 \begin{equation} \min\limits_{b,\mathbf w}\max\limits_{\mbox{all } \alpha_n\geq 0}\mathcal L(b,\mathbf w, \boldsymbol\alpha)\geq\max\limits_{\mbox{all } \alpha_n\geq 0}\min\limits_{b,\mathbf w}\mathcal L(b,\mathbf w, \boldsymbol\alpha)。 \end{equation}
若果解决了对偶问题，就得到原问题的下界。上式右边将对$b$和$\mathbf w$的优化问题转化成了对$\alpha_n$的优化问题，同时内层是对$b$和$\mathbf w$无约束条件的最优化，方便求解。
如果上式中只是“$\geq$”，则表示弱对偶（weak duality）；如果上式中“$=$”成立，则为强对偶（strong duality）。对于QP，“$=$”成立的条件是：（1）原问题是凸的；（2）原问题有解（对本问题而言，数据是可分的）；（3）线性约束条件。
对于支持向量机，“$=$”成立，求解右边的问题即可。
化简拉格朗日对偶问题
对于对偶问题，内层无约束优化取得最小值的条件是 \[ {\partial \mathcal L(b, \mathbf w, \boldsymbol\alpha)\over\partial b} = 0;\quad{\partial \mathcal L(b, \mathbf w, \boldsymbol\alpha)\over\partial w_i} = 0， \] 也就是 \[ \sum_{n=1}^N\alpha_ny_n=0;\quad\mathbf w=\sum_{n=1}^N\alpha_ny_n\mathbf z_n。 \] 将上述变量带入对偶问题，可以化解为 \[ \max\limits_{\mbox{all }\alpha_n\geq 0,\sum y_n\alpha_n=0,\mathbf w=\sum\alpha_ny_n\mathbf z_n}\min\limits_{b,\mathbf w}\left(\frac{1}{2}\mathbf w^T\mathbf w+\sum_{n=1}^N\alpha_n-\mathbf w^T\mathbf w\right)， \] 继续将$\mathbf w$的取值带入，可得 \begin{equation*} \max\limits_{\mbox{all }\alpha_n\geq 0,\sum y_n\alpha_n=0,\mathbf w=\sum\alpha_ny_n\mathbf z_n}\left(-\frac{1}{2}\left\lVert\sum_{n=1}^N\alpha_ny_n\mathbf z_n\right\rVert^2+\sum_{n=1}^N\alpha_n\right)， \end{equation*} 化为二次规划的标准形式为 \begin{equation} \begin{aligned} \min\limits_{\boldsymbol\alpha}&\quad\frac{1}{2}\sum_{n=1}^N\sum_{m=1}^N\alpha_n\alpha_my_ny_m\mathbf z_n^T\mathbf z_m-\sum_{n=1}^N\alpha_n \\ \mbox{subject to}&\quad\sum_{n=1}^Ny_n\alpha_n=0\\ &\quad\alpha_n\geq 0,\mbox{ for }n=1,2,\ldots,N， \end{aligned} \label{eq:qp-dual-svm} \end{equation}
该优化问题有$N$个变量，$N+1$个约束条件。根据QP的标准形式，可以得到利用QP求解对偶二次规划的系数 \[ \begin{aligned} &q_{n,m}=y_ny_m\mathbf z_n^T\mathbf z_m;\quad\mathbf p=-\mathbf 1_N;\\ &\mathbf a_{\geq}=\mathbf y,c_{\geq}=0;\quad\mathbf a_{\leq}=-\mathbf y,c_{\leq}=0;\\ &\mathbf a_n^T=\mbox{n-th unit direction},c_n=0。 \end{aligned} \] 为了利用标准的QP，将“$=$”约束转换成了“$\geq$”和“$\leq$”约束。通常情况$q_{n,m}\neq 0$，系数对应着$N\times N$的非稀疏矩阵，$N$很大时需要占用很大的存储空间。因此，通常会采用针对支持向量机设计的特殊QP加速求解过程。
对偶支持向量机优化问题的矩阵形式为 \begin{equation} \begin{aligned} \min\limits_{\boldsymbol\alpha}&\quad\frac{1}{2}\boldsymbol\alpha^T\mathbf Q_D\boldsymbol\alpha-\mathbf 1^T\boldsymbol\alpha \\ \mbox{subject to}&\quad\mathbf y^T\boldsymbol\alpha=0\\ &\quad\alpha_n\geq 0,\mbox{ for }n=1,2,\ldots,N， \end{aligned} \label{eq:qp-dual-svm2} \end{equation} 其中$q_{n,m}=y_ny_m\mathbf z_n^T\mathbf z_m$，$\alpha_n$的约束界也可以表示为矩阵形式 \begin{equation} \mathbf I_N\boldsymbol\alpha \geq \mathbf 0_N。 \end{equation}
KKT条件
原问题和对偶问题都是最佳解需要$b,\mathbf w,\boldsymbol\alpha$之间满足如下条件：
- 原问题可行：$y_n(\mathbf w^T\mathbf z_n+b)\geq 1$；
- 对偶问题可行：$\alpha_n\geq 0$；
- 对偶问题内最优化：$\sum_{n=1}^N\alpha_ny_n=0;\mathbf w=\sum_{n=1}^N\alpha_ny_n\mathbf z_n$；
- 原问题内最优化：$\alpha_n\left(1-y_n\left(\mathbf w^T\mathbf z_n+b\right)\right)=0$，这个条件也称为complementary slackness，其中至少一项为$0$。
这称为KKT条件，它是原问题和对偶问题都是最佳解的必要（necessary）条件，此处也是充分（sufficient）条件。
####Example
For a single variable $w$, consider minimizing ${1\over 2}w^2$ subject to two linear constraints $w\geq 1$ and $w\leq 3$. We know that the Lagrange function $\mathcal L(w,\alpha)={1\over 2}w^2+\alpha_1(1-w)+\alpha_2(w-3)$. Which of the following equations that contain $\alpha$ are among the KKT conditions of the optimization problem?
- $\alpha_1\geq 0$ and $\alpha_2\geq 0$
- $w=\alpha_1-\alpha_2$
- $\alpha_1(1-w)=0$ and $\alpha_2(w-3)=0$
- all of the above
Answer：4
通过KKT条件，可以利用$\boldsymbol\alpha$求解$b$和$\mathbf w$。利用KKT条件3容易求解$\mathbf w$，利用KKT条件4，当$\alpha_n>0$时，$1-y_n\left(\mathbf w^T\mathbf z_n+b\right)=0$两边同时乘以$y_n$可得$b$， \begin{equation} \left\{ \begin{aligned} b=&y_n-\mathbf w^T\mathbf z_n \quad\mbox{if }\alpha_n\neq 0；\\ \mathbf w=&\sum_{n=1}^N\alpha_ny_n\mathbf z_n。 \end{aligned} \right. \end{equation} 利用不同$\alpha_n>0$时的数据，理论上求解到的$b$应该是一样的，可以计算多个$b$然后平均得到更稳定的解。
支持向量
$\alpha_n>0$对应的点一定在边界上，这些点称为支持向量。也有些在边界上的点，对应的$\alpha_n$不一定大于$0$。容易发现，计算$b$和$\mathbf w$只需要支持向量就够了。
从计算公式可以发现，$\mathbf w$可以由$y_n\mathbf z_n$的线性组合表示，也就是$\mathbf w$可由数据表示，这和PLA算法相似 \begin{equation*} \mathbf w_{SVM}=\sum_{n=1}^N\alpha_n\left(y_n\mathbf z_n\right)， \mathbf w_{PLA}=\sum_{n=1}^N\beta_n\left(y_n\mathbf z_n\right)， \end{equation*} 其中$\beta_n$表示犯错误的次数。
两种形式的支持向量机
原始支持向量机适合特征维数$\tilde d$较少的情形，对偶形式的支持向量机适合数据点$N$较少的情形，两者都是通过最优化找到最大边界的判别界。
事实上，对偶形式的支持向量机和特征维数$\tilde d$也有关系，$q_{n,m}=y_ny_m\mathbf z_n^T\mathbf z_m$的计算也是$\mathbb R^{\tilde d}$空间的内积。
