支持向量机原理详解(二): 拉格朗日对偶函数，SVM的对偶问题
前文推导了SVM形成的优化问题，本文将详细推导其拉格朗日对偶问题。
本文内容：
- 拉格朗日对偶函数和对偶问题
- SVM的对偶问题
为了推导SVM的对偶问题，首先需要补充一些基础知识。关于拉格朗日对偶函数和对偶问题，Stephen Boyd和Lieven Vandenberghe的经典'Convex Optimization'一书有非常详细的讲解(Chapter 5: Duality)。中文译本为《凸优化》(王书宁等译)。
<文中粗体表示向量，标量则不加粗。>
4. 拉格朗日对偶函数 & 对偶问题
以下内容参考文献[1] Convex Optimization, Chapter 5: Duality.
考虑一个标准形式的优化问题：
\min_{\mathbf{x}}{f_0\left( \mathbf{x} \right)}\\ \begin{align} s.t. \ f_i\left(\mathbf{x} \right)&\leq 0, \ i=1,\ldots,m\\ h_i\left(\mathbf{x} \right)&= 0, \ i=1,\ldots,p\\ \end{align}\tag{I}
其中， \mathbf{x}\in \mathbf R^n 为问题的优化变量， f_0: \mathbf R^n\rightarrow \mathbf R 为目标函数；
共 m 个不等式约束，约束函数分别为 f_i: \mathbf R^n\rightarrow \mathbf R, \ i = 1, \dots, m ，
和 p 个等式约束，约束函数分别为 h_i: \mathbf R^n\rightarrow \mathbf R, \ i = 1, \dots, p 。
定义域(domain) \mathcal D = \bigcap_{i=0}^{m}\mathbf{dom}f_i \cap \bigcap_{i=1}^{p}\mathbf{dom}h_i 非空。
定义问题 \left( \rm I \right) 的拉格朗日函数(Lagrangian) L: \mathbf R^n \times \mathbf R^m \times \mathbf R^p \rightarrow \mathbf R 为：
L\left( \mathbf x, \mathbf \lambda, \mathbf \nu \right)=f_0\left( \mathbf x \right)+\sum_{i=1}^{m}{\lambda_i f_i\left( \mathbf x \right)}+\sum_{i=1}^{p}{\nu_i h_i\left( \mathbf x \right)}\tag{1}\\
其定义域 \mathbf{dom}L=\mathcal D \times \mathbf R^m \times \mathbf R^p 。其中 \lambda_i, \ \nu_i 分别称为不等式约束和等式约束的拉格朗日乘子(Lagrange multiplier)；相应地，向量 \mathbf \lambda = \left[ \lambda_1, \ldots, \lambda_m \right]^T 和 \mathbf \nu = \left[ \nu_1, \ldots, \nu_p \right]^T 称为问题 \left( \rm I \right) 的对偶变量或拉格朗日乘子向量。
注：符号 \times 表示笛卡尔积(Cartesian product)，对于两个集合A，B，有：
A\times B = \left\{ \left( a,\ b \right) \vert \ a \in A \ and \ b\in B\right\} \\
一般要求 \mathbf \lambda \succeq \mathbf 0 ，即 \lambda_i \geq 0, \ i = 1, \ldots, m ，称为对偶可行(dual feasible)。这里符号 \succeq 表示element-wise的比较，即逐个元素的比较。
定义拉格朗日对偶函数(Lagrange dual function) g: \mathbf R^m \times \mathbf R^p \rightarrow \mathbf R 为 L\left( \mathbf x, \mathbf \lambda, \mathbf \nu \right) 对 \mathbf x\in \mathcal D 取最小值：
g\left(\mathbf \lambda, \mathbf \nu \right)=\inf_{\mathbf x\in \mathcal D}{L\left( \mathbf x, \mathbf \lambda, \mathbf \nu \right)}\tag{2}\\
其中，inf表示下确界(infimum)，这里可近似理解为min，以下用min表示。对偶函数为凹函数(concave function)，不管问题 \left( \rm I \right) 是否为凸。
记问题 \left( \rm I \right) 的最优值为 p^\star。假设 \mathbf {\tilde{x}} 为一可行解，则其满足约束条件： f_i\left(\mathbf{\tilde{x}} \right)\leq 0, \ h_i\left(\mathbf{\tilde{x}} \right)= 0 。所以对任意 \mathbf \lambda \succeq \mathbf 0, \ \mathbf \nu ，由(1)式有 L\left( \mathbf {\tilde{x}}, \mathbf \lambda, \mathbf \nu \right)\leq f_0\left( \mathbf {\tilde{x}} \right) ，进而
g\left(\mathbf \lambda, \mathbf \nu \right)=\min_{\mathbf x\in \mathcal D}{L\left( \mathbf x, \mathbf \lambda, \mathbf \nu \right)}\leq L\left( \mathbf {\tilde{x}}, \mathbf \lambda, \mathbf \nu \right)\leq f_0\left( \mathbf {\tilde{x}} \right) \tag{3}\\
因为(3)式对任意可行解都成立，所以有
g\left(\mathbf \lambda, \mathbf \nu \right)\leq p^\star \\
这说明，对偶函数 g\left(\mathbf \lambda, \mathbf \nu \right) 给出了问题 \left( \rm I \right) 最优值 p^\star 的下界。那么 g\left(\mathbf \lambda, \mathbf \nu \right) 能给出的最好的下界是多少呢？(如果等于 p^\star 就太完美了。)这就形成了如下的优化问题：
\max_{\mathbf \lambda, \ \mathbf \nu}{g\left(\mathbf \lambda, \mathbf \nu \right)}\\\tag{II} s.t. \ \mathbf \lambda\succeq \mathbf 0
问题 \left( \rm II \right) 称为问题 \left( \rm I \right) 的拉格朗日对偶问题(Lagrange dual problem)，相应地，问题 \left( \rm I \right) 称为原问题(primal problem)。 \left( \rm II \right) 的变量为原问题的拉格朗日乘子，其最优解 \left( \lambda^*, \ \nu^* \right) 称为(对偶)最优拉格朗日乘子。不管原问题是否是凸优化问题，对偶问题都是凸优化问题(max一个凹函数)。
<弱对偶性weak duality>
记对偶问题的最优值为 d^\star ，原问题的最优值为 p^\star，则 d^\star 是对偶函数 g\left(\mathbf \lambda, \mathbf \nu \right) 能给出的 p^\star 的最好的下界，且有
d^\star \leq p^\star\\
称为弱对偶性。即使原问题非凸，弱对偶性也成立。
<强对偶性strong duality>
如果等式
d^\star = p^\star \\
成立，则称强对偶性成立。
强对偶性的成立需要满足一定的条件(参考文献[1], page 226)：
- 首先，需要原问题为凸优化问题，即如下形式(参考文献[1], page 136)：
\min_{\mathbf{x}}{f_0\left( \mathbf{x} \right)}\\ \begin{align} s.t. \ f_i\left(\mathbf{x} \right)&\leq 0, \ i=1,\ldots,m\\ \mathbf {a_i^Tx}&= b_i, \ i=1,\ldots,p\\ \end{align}
其中， f_0, f_1, \ldots, f_m 为凸函数(convex function)，等式约束为仿射函数(affine function)。
(凸优化问题往往有强对偶性，但不一定。)
2. 满足一定的约束准则(constraint qualifications)。比如Slater's condition：存在 \mathbf x \in \mathbf{relint} \mathcal {\ D} (定义域 \mathcal{D} 的相对内部，relative interior)，使得
\begin{align} f_i\left(\mathbf{x} \right)&\lt 0, \ i=1,\ldots,m\\ \mathbf {a_i^Tx}&= b_i, \ i=1,\ldots,p\\ \end{align}\\
成立(即满足等式约束且使不等式约束严格成立)。这样的 \mathbf x 称为严格可行(strictly feasible)。
Slater's theorem表明：如果Slater's condition成立，且原问题为凸问题，则强对偶性成立。
此时对偶问题的最优值等于原问题的最优值，最优对偶间隙(optimal duality gap) p^\star - d^\star = 0 。
5. SVM的对偶问题
幸运的是，SVM的原问题是凸优化问题(凸二次规划):
\min_{\mathbf{w},b, \mathbf{\xi}}{\frac{1}{2}\mathbf{w^Tw}}+C\sum_{i=1}^{N}{\xi_i} \tag{III}\\ \begin{align} s.t. \ \ \ y_i \left( \mathbf{w^Tx_i}+b \right)&\geq 1-\xi_i, \ i=1,\ldots,N\\ \xi_i &\geq 0, \ i=1,\ldots,N\\ \end{align}
且强对偶性成立。所以可以通过求解其对偶问题来得到原问题的最优解。
由(1)式，问题 \left( \rm III \right) 的拉格朗日函数为
L\left( \mathbf w,b, \mathbf \xi, \mathbf \alpha, \mathbf \mu \right)={\frac{1}{2}\mathbf{w^Tw}}+C\sum_{i=1}^{N}{\xi_i}-\sum_{i=1}^{N}{\alpha_i \left[ y_i \left( \mathbf{w^Tx_i}+b \right)-1+\xi_i \right]}-\sum_{i=1}^{N}{\mu_i \xi_i}\tag{4}\\
这里用 \mathbf \alpha = \left[ \alpha_1, \ldots, \alpha_N \right]^T 和 \mathbf \mu = \left[ \mu_1, \ldots, \mu_N \right]^T 分别表示两组不等式约束的拉格朗日乘子。
[注：优化问题的标准形式 \left( \rm I \right) 中不等式约束为 \leq ，而 \left( \rm III \right) 中不等式约束为 \geq ，所以拉格朗日函数中用的减号。这里 \left( \rm III \right) 没有等式约束，假设有，也同样乘以拉格朗日乘子，然后加到 L 上，不过不要求等式约束的拉格朗日乘子非负。]
为简化表示，将(4)式中的相关求和项用向量点积表示，如 \sum_{i=1}^{N}{\xi_i} = \mathbf {1^T \xi} ， \sum_{i=1}^{N}{\mu_i \xi_i} = \mathbf {\mu^T \xi} 等，有
\begin{align} L\left( \mathbf w,b, \mathbf \xi, \mathbf \alpha, \mathbf \mu \right)&={\frac{1}{2}\mathbf{w^Tw}}+C\cdot \mathbf{1^T\xi}-\sum_{i=1}^{N}{\alpha_i y_i \mathbf{w^Tx_i}}-b\cdot\mathbf{\alpha^Ty}+\mathbf{1^T\alpha}-\mathbf{\alpha^T\xi}-\mathbf{\mu^T\xi}\\ &={\frac{1}{2}\mathbf{w^Tw}}-\sum_{i=1}^{N}{\alpha_i y_i \mathbf{w^Tx_i}}-b\cdot\mathbf{\alpha^Ty}+\mathbf{1^T\alpha}+\left(C\cdot \mathbf{1^T-\alpha^T-\mu^T}\right)\mathbf \xi \tag{5}\\ \end{align}
其中， \mathbf{1} 表示各元素都为1的N维向量， \mathbf \xi = \left[ \xi _1, \ldots, \xi _N \right]^T ， \mathbf y = \left[ y_1, \ldots, y_N \right]^T 。
根据(2)式，问题 \left( \rm III \right) 的拉格朗日对偶函数为：
g\left( \mathbf \alpha, \mathbf \mu \right)=\min_{\mathbf w,b, \mathbf \xi} L\left( \mathbf w,b, \mathbf \xi, \mathbf \alpha, \mathbf \mu \right)\\
对偶问题为：
\max_{\mathbf \alpha, \mathbf \mu}{g\left( \mathbf \alpha, \mathbf \mu \right)} \tag{IV}\\ \begin{align} s.t. \mathbf \alpha \succeq \mathbf 0\\ \mathbf \mu \succeq \mathbf 0\\ \end{align}
下面计算 g\left( \mathbf \alpha, \mathbf \mu \right)=\min_{\mathbf w,b, \mathbf \xi} L\left( \mathbf w,b, \mathbf \xi, \mathbf \alpha, \mathbf \mu \right) 。将 L 对各变量求梯度并令其为0：
\begin{align} \frac{\partial L}{\partial\mathbf w} &=\mathbf{w}-\sum_{i=1}^{N}{\alpha_i y_i \mathbf{x_i}}=\mathbf 0 \tag{6-1}\\ \frac{\partial L}{\partial\mathbf \xi} &= C\cdot \mathbf 1 - \mathbf \alpha - \mathbf \mu = \mathbf 0\tag{6-2}\\ \frac{\partial L}{\partial b} &=\sum_{i=1}^{N}{\alpha_i y_i}=\mathbf {\alpha^T y} = 0\tag{6-3}\\ \end{align}\\
将(6-1)～(6-3)式代回对偶函数：
\begin{align} g\left( \mathbf \alpha, \mathbf \mu \right)&={\frac{1}{2}\mathbf{w^Tw}}-\sum_{i=1}^{N}{\alpha_i y_i \mathbf{w^Tx_i}}+\mathbf{1^T\alpha}\\ &= {\frac{1}{2}\mathbf{w^Tw}}-\mathbf{w^T}\sum_{i=1}^{N}{\alpha_i y_i \mathbf{x_i}}+\mathbf{1^T\alpha}\\ &= -{\frac{1}{2}\mathbf{w^Tw}}+\mathbf{1^T\alpha}\\ &= -\frac{1}{2}\left[\sum_{i=1}^{N}{\left(\alpha_i y_i \mathbf{x_i}\right)^T} \right]\sum_{j=1}^{N}{\alpha_j y_j \mathbf{x_j}}+\mathbf{1^T\alpha}\\ &= -\frac{1}{2}\sum_{i=1}^{N}{\sum_{j=1}^{N}{\alpha_i \alpha_j y_i y_j \mathbf{x_i}^T\mathbf{x_j}}} +\mathbf{1^T\alpha}\\ &= -\frac{1}{2}\mathbf{\alpha^T Q \alpha} +\mathbf{1^T\alpha}\\ \end{align}\\
其中， \mathbf{Q} 为对称矩阵，其 i 行 j 列的元素为 \mathbf{Q_{ij}}=y_i y_j \mathbf{x_i^T x_j} 。
所以对偶问题 \left( \rm IV \right) 转化为：
\max_{\mathbf \alpha, \ \mathbf \mu}{-\frac{1}{2}\mathbf{\alpha^T Q \alpha} +\mathbf{1^T\alpha}}\\ \begin{align} s.t. \ \ \ \mathbf \alpha \succeq \mathbf 0\tag{7-1}\\ \mathbf \mu \succeq \mathbf 0\tag{7-2}\\ C\cdot \mathbf 1 - \mathbf \alpha - \mathbf \mu = \mathbf 0\tag{7-3}\\ \mathbf {\alpha^T y} = 0\tag{7-4}\\ \end{align}
其中，约束条件(7-3)和(7-4)分别是(6-2)和(6-3)式。
调整约束条件，用(7-2)和(7-3)消掉 \mathbf \mu ，得 \mathbf \alpha \preceq C\cdot \mathbf 1 ，并和(7-1)合并，则对偶问题转化为
\max_{\mathbf \alpha}{-\frac{1}{2}\mathbf{\alpha^T Q \alpha} +\mathbf{1^T\alpha}}\\ \begin{align} s.t. \ \ \ \mathbf 0 \preceq \mathbf \alpha \preceq C\cdot \mathbf 1\\ \mathbf {\alpha^T y} = 0\\ \end{align}
现在变量只有 \mathbf \alpha 了。进一步将max转化为min，得到凸二次规划问题：
\min_{\mathbf \alpha}{\frac{1}{2}\mathbf{\alpha^T Q \alpha} -\mathbf{1^T\alpha}}\tag{V}\\ \begin{align} s.t. \ \ \ \mathbf 0 \preceq \mathbf \alpha \preceq C\cdot \mathbf 1\\ \mathbf {\alpha^T y} = 0\\ \end{align}
记对偶问题 \left( \rm V \right) 的最优解为 \mathbf \alpha^* = \left[ \alpha_1^*, \ldots, \alpha_N^* \right]^T ，则由(6-1)式可得到原问题的最优解 \mathbf{w^*} 为：
\mathbf{w^*}=\sum_{i=1}^{N}{\alpha_i^* y_i \mathbf{x_i}}\tag{8}\\
至于最优解 b^* 的计算，跟支持向量和 \alpha_i^* 的取值有关，涉及KKT条件，后文再详细推导。
在得到这个最优分离超平面 \mathbf{w^{*T}x}+b^*=0 后，对于新的样本 \mathbf{x_{new}} ，通过决策函数 y_{new} = sign\left( \mathbf{w^{*T}x_{new}}+b^* \right) 来进行分类。由(8)式得：
\mathbf{w^{*T}x_{new}}+b^* = \sum_{i=1}^{N}{\alpha_i^* y_i \mathbf{x_i^T x_{new}}} +b^*\\
所以分类决策函数：
y_{new} = sign\left( \sum_{i=1}^{N}{\alpha_i^* y_i \mathbf{x_i^T x_{new}}} +b^* \right)\tag{9}\\
实际上，并不需要用所有的样本 \left( i=1, \ldots, N \right) 来计算(8)和(9)，因为在最优解 \mathbf \alpha^* = \left[ \alpha_1^*, \ldots, \alpha_N^* \right]^T 中，大部分 \alpha_i^* 为0，只需保留 \alpha_i^*\gt 0 的样本信息即可计算(8)和(9)。这些 \alpha_i^*\gt 0 的样本就是所谓的支持向量(support vector)(参考文献[4], page 113)，详细推导见后续。
所以最优解：
\mathbf{w^*}=\sum_{support \\ vectors}{\alpha_i^* y_i \mathbf{x_i}}\tag{10}\\
分类决策函数：
y_{new} = sign\left(\sum_{support \\ vectors}{\alpha_i^* y_i \mathbf{x_i^T x_{new}}} +b^* \right) \tag{11}\\
<为什么要通过对偶问题得到SVM原问题的最优解？>(参考文献[4], page 103)
- 通常来说，SVM的对偶问题更容易求解。若样本数为N，每个样本 \mathbf x 为K维，则SVM原问题的变量 \mathbf{w},b, \mathbf{\xi} 分别为K维，1维，和N维，有2*N个不等式约束；而对偶问题的变量 \mathbf \alpha 为N维，有2*N个不等式约束和1个等式约束。
2. 便于引入核函数，使SVM适用于非线性数据。这一点可以从(11)式中的向量点积 \mathbf{x_i^T x_{new}} 得到启发：将数据映射到高维空间，然后定义核函数来计算高维空间中的向量点积，和核PCA类似。详细推导见后续。
To be continued...
参考文献
[1] Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, 2004.
中文译本：凸优化。 Stephen Boyd and Lieven Vandenberghe 著。 王书宁，许鋆，黄晓霖译。清华大学出版社，北京，2013年。
[2] C. Cortes and V. Vapnik. Support-Vector Networks. Machine Learning, 20:273–297, 1995.
[3] Christopher J. C. Burges. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery, 2, 121-167, 1998.
[4] 李航，统计学习方法，清华大学出版社，北京，2012年。第7章。
