第6章 支持向量机

在深度学习流行之前，支持向量机及其核方法一直是机器学习领域中的主流算法，尤其是核方法至今都仍有相关学者在持续研究。

6.1 间隔与支持向量

6.1.1 图6.1的解释

回顾第5章5.2节的感知机模型可知，图6.1中的黑色直线均可作为感知机模型的解，因为感知机模型求解的是能将正负样本完全正确划分的超平面，因此解不唯一。而支持向量机想要求解的则是离正负样本都尽可能远且刚好位于"正中间"的划分超平面，因为这样的超平面理论上泛化性能更好。

6.1.2 式(6.1)的解释

$n$维空间的超平面定义为${\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b=0$，其中$\mathbf{w},\mathbf{x}\in {\mathbb{R}}^n$，$\mathbf{w}=(w_1;w_2;...;w_n)$称为法向量，$b$称为位移项。超平面具有以下性质：

(1)法向量$\mathbf{w}$和位移项$b$确定一个唯一超平面；

(2)超平面方程不唯一，因为当等倍缩放$\mathbf{w}$和$b$时（假设缩放倍数为$\alpha$），所得的新超平面方程$\alpha {\mathbf{w}}^{\mathrm{T}}\mathbf{x}+\alpha b=0$和${\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b=0$的解完全相同，因此超平面不变，仅超平面方程有变；

(3)法向量$\mathbf{w}$垂直于超平面；

(4)超平面将$n$维空间切割为两半，其中法向量$\mathbf{w}$指向的那一半空间称为正空间，另一半称为负空间，正空间中的点${\mathbf{x}}^{+}$代入进方程${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}^{+}+b$其计算结果大于0，反之负空间中的点代入进方程其计算结果小于0；

(5)$n$维空间中的任意点$\mathbf{x}$到超平面的距离公式为$r=\frac{|{\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b|}{\Vert \mathbf{w}\Vert }$，其中$\Vert \mathbf{w}\Vert$表示向量$\mathbf{w}$的模。

6.1.3 式(6.2)的推导

对于任意一点${\mathbf{x}}_0=(x_1^0;x_2^0;...;x_n^0)$，设其在超平面${\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b=0$上的投影点为${\mathbf{x}}_1=(x_1^1;x_2^1;...;x_n^1)$，则${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_1+b=0$。根据超平面的性质(3)可知，此时向量$\overrightarrow{{\mathbf{x}}_1{\mathbf{x}}_0}$与法向量$\mathbf{w}$平行，因此

$$|\mathbf{w}\cdot \overrightarrow{{\mathbf{x}}_1{\mathbf{x}}_0}|=|\Vert \mathbf{w}\Vert \cdot \cos \pi \cdot \Vert \overrightarrow{{\mathbf{x}}_1{\mathbf{x}}_0}\Vert |=\Vert \mathbf{w}\Vert \cdot \Vert \overrightarrow{{\mathbf{x}}_1{\mathbf{x}}_0}\Vert =\Vert \mathbf{w}\Vert \cdot r$$

又

$$\begin{array}{rl}\mathbf{w}\cdot \overrightarrow{{\mathbf{x}}_1{\mathbf{x}}_0}& =w_1(x_1^0-x_1^1)+w_2(x_2^0-x_2^1)+...+w_n(x_n^0-x_n^1)\\ & =w_1{x}_1^0+w_2{x}_2^0+...+w_n{x}_n^0-(w_1{x}_1^1+w_2{x}_2^1+...+w_n{x}_n^1)\\ & ={\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_0-{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_1\\ & ={\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_0+b\end{array}$$

所以

$$|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_0+b|=\Vert \mathbf{w}\Vert \cdot r$$

$$r=\frac{\left|{\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b\right|}{\Vert \mathbf{w}\Vert }$$

6.1.4 式(6.3)的推导

支持向量机所要求的超平面需要满足三个条件，第一个是能正确划分正负样本，第二个是要位于正负样本正中间，第三个是离正负样本都尽可能远。式(6.3)仅满足前两个条件，第三个条件由式(6.5)来满足，因此下面仅基于前两个条件来进行推导。

对于第一个条件，当超平面满足该条件时，根据超平面的性质(4)可知，若$y_i=+1$的正样本被划分到正空间（当然也可以将其划分到负空间），$y_i=-1$的负样本被划分到负空间，以下不等式成立

$$\{\begin{array}{ll}{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b⩾0,& y_i=+1\\ {\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b⩽0,& y_i=-1\end{array}$$

对于第二个条件，首先设离超平面最近的正样本为${\mathbf{x}}_{\ast }^{+}$，离超平面最近的负样本为${\mathbf{x}}_{\ast }^{-}$，由于这两样本是离超平面最近的点，所以其他样本到超平面的距离均大于等于它们，即

$$\{\begin{array}{ll}\frac{|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b|}{\Vert \mathbf{w}\Vert }⩾\frac{|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{+}+b|}{\Vert \mathbf{w}\Vert },& y_i=+1\\ \frac{|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b|}{\Vert \mathbf{w}\Vert }⩾\frac{|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{-}+b|}{\Vert \mathbf{w}\Vert },& y_i=-1\end{array}$$

结合第一个条件中推导出的不等式，可将上式中的绝对值符号去掉并推得

$$\{\begin{array}{ll}\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }⩾\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{+}+b}{\Vert \mathbf{w}\Vert },& y_i=+1\\ \frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }⩽\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{-}+b}{\Vert \mathbf{w}\Vert },& y_i=-1\end{array}$$

基于此再考虑第二个条件，"位于正负样本正中间"等价于要求超平面到${\mathbf{x}}_{\ast }^{+}$和${\mathbf{x}}_{\ast }^{-}$这两点的距离相等，即

$$\frac{\left|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{+}+b\right|}{\Vert \mathbf{w}\Vert }=\frac{\left|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{-}+b\right|}{\Vert \mathbf{w}\Vert }$$

综上，支持向量机所要求的超平面所需要满足的条件如下

$$\{\begin{array}{ll}\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }⩾\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{+}+b}{\Vert \mathbf{w}\Vert },& y_i=+1\\ \frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }⩽\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{-}+b}{\Vert \mathbf{w}\Vert },& y_i=-1\\ \frac{|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{+}+b|}{\Vert \mathbf{w}\Vert }=\frac{|{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{-}+b|}{\Vert \mathbf{w}\Vert }& \end{array}$$

但是根据超平面的性质(2)可知，当等倍缩放法向量$\mathbf{w}$和位移项$b$时，超平面不变，且上式也恒成立，因此会导致所求的超平面的参数$\mathbf{w}$和$b$有无穷多解。因此为了保证每个超平面的参数只有唯一解，不妨再额外施加一些约束，例如约束${\mathbf{x}}_{\ast }^{+}$和${\mathbf{x}}_{\ast }^{-}$代入进超平面方程后的绝对值为1，也就是令${\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{+}+b=1,{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_{\ast }^{-}+b=-1$。此时支持向量机所要求的超平面所需要满足的条件变为

$$\{\begin{array}{ll}\frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }⩾\frac{+1}{\Vert \mathbf{w}\Vert },& y_i=+1\\ \frac{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}{\Vert \mathbf{w}\Vert }⩽\frac{-1}{\Vert \mathbf{w}\Vert },& y_i=-1\end{array}$$

由于$\Vert \mathbf{w}\Vert$恒大于0，因此上式可进一步化简为

$$\{\begin{array}{ll}{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b⩾+1,& y_i=+1\\ {\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b⩽-1,& y_i=-1\end{array}$$

6.1.5 式(6.4)的推导

根据式(6.3)的推导可知，${\mathbf{x}}_{\ast }^{+}$和${\mathbf{x}}_{\ast }^{-}$便是"支持向量"，因此支持向量到超平面的距离已经被约束为$\frac{1}{\Vert \mathbf{w}\Vert }$，所以两个异类支持向量到超平面的距离之和为$\frac{2}{\Vert \mathbf{w}\Vert }$。

6.1.6 式(6.5)的解释

式(6.5)是通过"最大化间隔"来保证超平面离正负样本都尽可能远，且该超平面有且仅有一个，因此可以解出唯一解。

6.2 对偶问题

6.2.1 凸优化问题

考虑一般地约束优化问题

$$\begin{array}{ll}\min & f(\mathbf{x})\\ \text{s.t.}& g_i(\mathbf{x})⩽0,i=1,2,...,m\\ & h_j(\mathbf{x})=0,j=1,2,...,n\end{array}$$

若目标函数$f(\mathbf{x})$是凸函数，不等式约束$g_i(\mathbf{x})$是凸函数，等式约束$h_j(\mathbf{x})$是仿射函数，则称该优化问题为凸优化问题。

由于$\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$和$1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)$均是关于$\mathbf{w}$和$b$的凸函数，所以式(6.6)是凸优化问题。凸优化问题是最优化里比较易解的一类优化问题，因为其拥有诸多良好的数学性质和现成的数学工具，因此如果非凸优化问题能等价转化为凸优化问题，其求解难度通常也会减小。

6.2.2 KKT条件

考虑一般的约束优化问题

$$\begin{array}{ll}\min & f(\mathbf{x})\\ \text{s.t.}& g_i(\mathbf{x})⩽0,i=1,2,...,m\\ & h_j(\mathbf{x})=0,j=1,2,...,n\end{array}$$

若$f(\mathbf{x}),g_i(\mathbf{x}),h_j(\mathbf{x})$的一阶偏导连续，${\mathbf{x}}^{\ast }$是优化问题的局部解，$\mathbf{\mu }=({\mu }_1;{\mu }_2;...;{\mu }_m),\mathbf{\lambda }=({\lambda }_1;{\lambda }_2;...;{\lambda }_n)$为拉格朗日乘子向量，$L(\mathbf{x},\mathbf{\mu },\mathbf{\lambda })=f(\mathbf{x})+{\sum }_{i=1}^m{\mu }_i{g}_i(\mathbf{x})+{\sum }_{j=1}^n{\lambda }_j{h}_j(\mathbf{x})$为拉格朗日函数，且该优化问题满足任何一个特定的约束限制条件，则一定存在${\mathbf{\mu }}^{\ast }=({\mu }_1^{\ast };{\mu }_2^{\ast };...;{\mu }_m^{\ast }),{\mathbf{\lambda }}^{\ast }=({\lambda }_1^{\ast };{\lambda }_2^{\ast };...;{\lambda }_n^{\ast })$，使得：

(1) ${\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })=\nabla f({\mathbf{x}}^{\ast })+{\sum }_{i=1}^m{\mu }_i^{\ast }\nabla g_i({\mathbf{x}}^{\ast })+{\sum }_{j=1}^n{\lambda }_j^{\ast }\nabla h_j({\mathbf{x}}^{\ast })=0$；

(2) $h_j({\mathbf{x}}^{\ast })=0,j=1,2,...,n$；

(3) $g_i({\mathbf{x}}^{\ast })⩽0,i=1,2,...,m$；

(4) ${\mu }_i^{\ast }⩾0,i=1,2,...,m$；

(5) ${\mu }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })=0,i=1,2,...,m$。

以上5条便是Karush--Kuhn--Tucker Conditions（简称KKT条件）。KKT条件是局部解的必要条件，也就是说只要该优化问题满足任何一个特定的约束限制条件，局部解就一定会满足以上5个条件。常用的约束限制条件可查阅维基百科"Karush--Kuhn--Tucker Conditions"词条以及查阅参考文献[1]的第4.2.2节，若对KKT条件的数学证明感兴趣可查阅参考文献[1]的第4.2.1节。

6.2.3 拉格朗日对偶函数

考虑一般地约束优化问题

$$\begin{array}{ll}\min & f(\mathbf{x})\\ \text{s.t.}& g_i(\mathbf{x})⩽0,i=1,2,...,m\\ & h_j(\mathbf{x})=0,j=1,2,...,n\end{array}$$

设上述优化问题的定义域为$D=\mathrm{dom}f\cap \bigcap _{i=1}^m\mathrm{dom}{g}_i\cap \bigcap _{j=1}^n\mathrm{dom}{h}_j$，可行集为$\tilde{D}=\{\mathbf{x}|\mathbf{x}\in D,g_i(\mathbf{x})⩽0,h_j(\mathbf{x})=0\}$（显然$\tilde{D}$是$D$的子集），最优值为$p^{\ast }=\min \{f(\tilde{\mathbf{x}})\},\tilde{\mathbf{x}}\in \tilde{D}$。上述优化问题的拉格朗日函数定义为

$$L(\mathbf{x},\mathbf{\mu },\mathbf{\lambda })=f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^n{\lambda }_j{h}_j(\mathbf{x})$$

其中$\mathbf{\mu }=({\mu }_1;{\mu }_2;...;{\mu }_m),\mathbf{\lambda }=({\lambda }_1;{\lambda }_2;...;{\lambda }_n)$为拉格朗日乘子向量。相应地拉格朗日对偶函数$\Gamma (\mathbf{\mu },\mathbf{\lambda })$（简称对偶函数）定义为$L(\mathbf{x},\mathbf{\mu },\mathbf{\lambda })$关于$\mathbf{x}$的下确界，即

$$\Gamma (\mathbf{\mu },\mathbf{\lambda })=\underset{\mathbf{x}\in D}{\inf }L(\mathbf{x},\mathbf{\mu },\mathbf{\lambda })=\underset{\mathbf{x}\in D}{\inf }\left(f(\mathbf{x})+\sum _{i=1}^m{\mu }_i{g}_i(\mathbf{x})+\sum _{j=1}^n{\lambda }_j{h}_j(\mathbf{x})\right)$$

对偶函数有如下性质：

(1)无论上述优化问题是否为凸优化问题，其对偶函数$\Gamma (\mathbf{\mu },\mathbf{\lambda })$恒为凹函数，详细证明可查阅参考文献[2]的第5.1.2和3.2.3节；

(2)当$\mathbf{\mu }⪰0$时（$\mathbf{\mu }⪰0$表示$\mathbf{\mu }$的分量均为非负），$\Gamma (\mathbf{\mu },\mathbf{\lambda })$构成了上述优化问题最优值$p^{\ast }$的下界，即

$$\Gamma (\mathbf{\mu },\mathbf{\lambda })⩽p^{\ast }$$

其推导过程如下：

设$\tilde{\mathbf{x}}\in \tilde{D}$是优化问题的可行点，则$g_i(\tilde{\mathbf{x}})⩽0,h_j(\tilde{\mathbf{x}})=0$，因此，当$\mathbf{\mu }⪰0$时，${\mu }_i{g}_i(\tilde{\mathbf{x}})⩽0,{\lambda }_j{h}_j(\tilde{\mathbf{x}})=0$恒成立，所以

$$\sum _{i=1}^m{\mu }_i{g}_i(\tilde{\mathbf{x}})+\sum _{j=1}^n{\lambda }_j{h}_j(\tilde{\mathbf{x}})⩽0$$

根据上述不等式可以推得

$$L(\tilde{\mathbf{x}},\mathbf{\mu },\mathbf{\lambda })=f(\tilde{\mathbf{x}})+\sum _{i=1}^m{\mu }_i{g}_i(\tilde{\mathbf{x}})+\sum _{j=1}^n{\lambda }_j{h}_j(\tilde{\mathbf{x}})⩽f(\tilde{\mathbf{x}})$$

又

$$\Gamma (\mathbf{\mu },\mathbf{\lambda })=\underset{\mathbf{x}\in D}{\inf }L(\mathbf{x},\mathbf{\mu },\mathbf{\lambda })⩽L(\tilde{\mathbf{x}},\mathbf{\mu },\mathbf{\lambda })$$

所以

$$\Gamma (\mathbf{\mu },\mathbf{\lambda })⩽L(\tilde{\mathbf{x}},\mathbf{\mu },\mathbf{\lambda })⩽f(\tilde{\mathbf{x}})$$

进一步地

$$\Gamma (\mathbf{\mu },\mathbf{\lambda })⩽\min \{f(\tilde{\mathbf{x}})\}=p^{\ast }$$

6.2.4 拉格朗日对偶问题

在$\mathbf{\mu }⪰0$的约束下求对偶函数最大值的优化问题称为拉格朗日对偶问题（简称对偶问题）

$$\begin{array}{ll}\max & \Gamma (\mathbf{\mu },\mathbf{\lambda })\\ \text{s.t.}& \mathbf{\mu }⪰0\end{array}$$

上一节的优化问题称为主问题或原问题。

设对偶问题的最优值为$d^{\ast }=\max \{\Gamma (\mathbf{\mu },\mathbf{\lambda })\},\mathbf{\mu }⪰0$，根据对偶函数的性质（2）可知$d^{\ast }⩽p^{\ast }$，此时称为"弱对偶性"成立，若$d^{\ast }=p^{\ast }$，则称为"强对偶性"成立。由此可以看出，当主问题较难求解时，如果强对偶性成立，则可以通过求解对偶问题来间接求解主问题。由于约束条件$\mathbf{\mu }⪰0$是凸集，且根据对偶函数的性质（1）可知$\Gamma (\mathbf{\mu },\mathbf{\lambda })$恒为凹函数，其加个负号即为凸函数，所以无论主问题是否为凸优化问题，对偶问题恒为凸优化问题。

一般情况下，强对偶性并不成立，只有当主问题满足特定的约束限制条件（不同于KKT条件中的约束限制条件）时，强对偶性才成立，常见的有"Slater条件"。Slater条件指出，当主问题是凸优化问题，且存在一点$\mathbf{x}\in \mathrm{relint}D$能使得所有等式约束成立，除仿射函数以外的不等式约束严格成立，则强对偶性成立。由于式(6.6)是凸优化问题，且不等式约束均为仿射函数，所以式(6.6)强对偶性成立。

对于凸优化问题，还可以通过KKT条件来间接推导出强对偶性，并同时求解出主问题和对偶问题的最优解。具体地，若主问题为凸优化问题，目标函数$f(\mathbf{x})$和约束函数$g_i(\mathbf{x}),h_j(\mathbf{x})$的一阶偏导连续，主问题满足KKT条件中任何一个特定的约束限制条件，则满足KKT条件的点${\mathbf{x}}^{\ast }$和$({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$分别是主问题和对偶问题的最优解，且此时强对偶性成立。下面给出具体的推导过程。

设${\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast }$是任意满足KKT条件的点，即

$$\{\begin{array}{l}{\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })=\nabla f({\mathbf{x}}^{\ast })+{\sum }_{i=1}^m{\mu }_i^{\ast }\nabla g_i({\mathbf{x}}^{\ast })+{\sum }_{j=1}^n{\lambda }_j^{\ast }\nabla h_j({\mathbf{x}}^{\ast })=0\\ h_j({\mathbf{x}}^{\ast })=0,j=1,2,...,n\\ g_i({\mathbf{x}}^{\ast })⩽0,i=1,2,...,m\\ {\mu }_i^{\ast }⩾0,i=1,2,...,m\\ {\mu }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })=0,i=1,2,...,m\end{array}$$

由于主问题是凸优化问题，所以$f(\mathbf{x})$和$g_i(\mathbf{x})$是凸函数，$h_j(\mathbf{x})$是仿射函数，又因为此时${\mu }_i^{\ast }⩾0$，所以$L(\mathbf{x},{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$是关于$\mathbf{x}$的凸函数。根据${\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })=0$可知，此时${\mathbf{x}}^{\ast }$是$L(\mathbf{x},{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$的极值点，而凸函数的极值点也是最值点，所以${\mathbf{x}}^{\ast }$是最小值点，因此可以进一步推得

$$\begin{array}{rl}L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })& =\min \{L(\mathbf{x},{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })\}\\ & ={\inf }_{\mathbf{x}\in D}\left(f(\mathbf{x})+\sum _{i=1}^m{\mu }_i^{\ast }{g}_i(\mathbf{x})+\sum _{j=1}^n{\lambda }_j^{\ast }{h}_j(\mathbf{x})\right)\\ & =\Gamma ({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })\\ & =f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{\mu }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^n{\lambda }_j^{\ast }{h}_j({\mathbf{x}}^{\ast })\\ & =f({\mathbf{x}}^{\ast })\end{array}$$

其中第二个等式是根据下确界函数的性质推得，第三个等式是根据对偶函数的定义推得，第四个等式是$L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$的展开形式，最后一个等式是因为${\mu }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })=0,h_j({\mathbf{x}}^{\ast })=0$。

由于${\mathbf{x}}^{\ast }$和$({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$仅是满足KKT条件的点，并不一定是$f(\mathbf{x})$和$\Gamma (\mathbf{\mu },\mathbf{\lambda })$的最值点，所以$f({\mathbf{x}}^{\ast })⩾p^{\ast }⩾d^{\ast }⩾\Gamma ({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$，但是上式又推得$f({\mathbf{x}}^{\ast })=\Gamma ({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$，所以$p^{\ast }=d^{\ast }$，因此推得强对偶性成立，且${\mathbf{x}}^{\ast }$和$({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$分别是主问题和对偶问题的最优解。

Slater条件恰巧也是KKT条件中特定的约束限制条件之一，所以式(6.6)不仅强对偶性成立，而且可以通过求解满足KKT条件的点来求解出最优解。

KKT条件除了可以作为凸优化问题强对偶性成立的充分条件以外，其实对于任意优化问题（并不一定是凸优化问题），若其强对偶性成立，KKT条件也是主问题和对偶问题最优解的必要条件，而且此时并不要求主问题满足KKT条件中任何一个特定的约束限制条件。下面同样给出具体的推导过程。

设主问题的最优解为${\mathbf{x}}^{\ast }$，对偶问题的最优解为$({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$，目标函数$f(\mathbf{x})$和约束函数$g_i(\mathbf{x}),h_j(\mathbf{x})$的一阶偏导连续，当强对偶性成立时，可以推得

$$\begin{array}{rl}f({\mathbf{x}}^{\ast })& =\Gamma ({\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })\\ & ={\inf }_{\mathbf{x}\in D}L(\mathbf{x},{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })\\ & ={\inf }_{\mathbf{x}\in D}\left(f(\mathbf{x})+\sum _{i=1}^m{\mu }_i^{\ast }{g}_i(\mathbf{x})+\sum _{j=1}^n{\lambda }_j^{\ast }{h}_j(\mathbf{x})\right)\\ & ⩽f({\mathbf{x}}^{\ast })+\sum _{i=1}^m{\mu }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })+\sum _{j=1}^n{\lambda }_j^{\ast }{h}_j({\mathbf{x}}^{\ast })\\ & ⩽f({\mathbf{x}}^{\ast })\end{array}$$

其中，第一个等式是因为强对偶性成立时$p^{\ast }=d^{\ast }$，第二和第三个等式是对偶函数的定义，第四个不等式是根据下确界的性质推得，最后一个不等式成立是因为${\mu }_i^{\ast }⩾0,g_i({\mathbf{x}}^{\ast })⩽0,h_j({\mathbf{x}}^{\ast })=0$。

由于$f({\mathbf{x}}^{\ast })=f({\mathbf{x}}^{\ast })$，所以上式中的不等式均可化为等式。第四个不等式可化为等式，说明$L(\mathbf{x},{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })$在${\mathbf{x}}^{\ast }$处取得最小值，所以根据极值的性质可知在${\mathbf{x}}^{\ast }$处一阶导${\nabla }_{\mathbf{x}}L({\mathbf{x}}^{\ast },{\mathbf{\mu }}^{\ast },{\mathbf{\lambda }}^{\ast })=0$。最后一个不等式可化为等式，说明${\mu }_i^{\ast }{g}_i({\mathbf{x}}^{\ast })=0$。此时再结合主问题和对偶问题原有的约束条件${\mu }_i^{\ast }⩾0,g_i({\mathbf{x}}^{\ast })⩽0,h_j({\mathbf{x}}^{\ast })=0$便凑齐了KKT条件。

6.2.5 式(6.9)和式(6.10)的推导

$$\begin{array}{rl}L(\mathbf{w},b,\mathbf{\alpha })& =\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+\sum _{i=1}^m{\alpha }_i(1-y_i({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b))\\ & =\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+\sum _{i=1}^m({\alpha }_i-{\alpha }_i{y}_i{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i-{\alpha }_i{y}_{i}b)\\ & =\frac{1}{2}{\mathbf{w}}^{\mathrm{T}}\mathbf{w}+\sum _{i=1}^m{\alpha }_i-\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i-\sum _{i=1}^m{\alpha }_i{y}_{i}b\end{array}$$

对$\mathbf{w}$和$b$分别求偏导数并令其为零

$$\frac{\partial L}{\partial \mathbf{w}}=\frac{1}{2}\times 2\times \mathbf{w}+0-\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i-0=0⟹\mathbf{w}=\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i$$

$$\frac{\partial L}{\partial b}=0+0-0-\sum _{i=1}^m{\alpha }_i{y}_i=0⟹\sum _{i=1}^m{\alpha }_i{y}_i=0$$

6.2.6 式(6.11)的推导

因为${\alpha }_i⩾0$，且$\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$和$1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)$均是关于$\mathbf{w}$和$b$的凸函数，所以式(6.8)也是关于$\mathbf{w}$和$b$的凸函数。根据凸函数的性质可知，其极值点就是最值点，所以一阶导为零的点就是最小值点，因此将式(6.9)和式(6.10)代入式(6.8)后即可得式(6.8)的最小值（等价于下确界），再根据对偶问题的定义加上约束${\alpha }_i⩾0$，就得到了式(6.6)的对偶问题。由于式(6.10)也是$\alpha i$必须满足的条件，且不含有$\mathbf{w}$和$b$，因此也需要纳入对偶问题的约束条件。根据以上思路进行推导的过程如下：

$$\begin{array}{rl}\underset{\mathbf{w},b}{\inf }L(\mathbf{w},b,\mathbf{\alpha })& =\frac{1}{2}{\mathbf{w}}^{\mathrm{T}}\mathbf{w}+\sum _{i=1}^m{\alpha }_i-\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i-\sum _{i=1}^m{\alpha }_i{y}_{i}b\\ & =\frac{1}{2}{\mathbf{w}}^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i-{\mathbf{w}}^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i+\sum _{i=1}^m{\alpha }_i-b\sum _{i=1}^m{\alpha }_i{y}_i\\ & =-\frac{1}{2}{\mathbf{w}}^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i+\sum _{i=1}^m{\alpha }_i-b\sum _{i=1}^m{\alpha }_i{y}_i\\ & =-\frac{1}{2}{\mathbf{w}}^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i+\sum _{i=1}^m{\alpha }_i\\ & =-\frac{1}{2}(\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i{)}^{\mathrm{T}}(\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i)+\sum _{i=1}^m{\alpha }_i\\ & =-\frac{1}{2}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i+\sum _{i=1}^m{\alpha }_i\\ & =\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^{\mathrm{T}}{\mathbf{x}}_j\end{array}$$

所以

$$\underset{\mathbf{\alpha }}{\max }\underset{\mathbf{w},b}{\inf }L(\mathbf{w},b,\mathbf{\alpha })=\underset{\mathbf{\alpha }}{\max }\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^{\mathrm{T}}{\mathbf{x}}_j$$

最后将${\alpha }_i⩾0$和式(6.10)作为约束条件即可得式(6.11)。

式(6.6)之所以要转化为式(6.11)来求解，其主要有以下两点理由：

(1)式(6.6)中的未知数是$\mathbf{w}$和$b$，式(6.11)中的未知数是$\mathbf{\alpha }$，$\mathbf{w}$的维度$d$对应样本特征个数，$\mathbf{\alpha }$的维度$m$对应训练样本个数，通常$m\ll d$，所以求解式(6.11)更高效，反之求解式(6.6)更高效；

(2)式(6.11)中有样本内积${\mathbf{x}}_i^{\mathrm{T}}{\mathbf{x}}_j$这一项，后续可以很自然地引入核函数，进而使得支持向量机也能对在原始特征空间线性不可分的数据进行分类。

6.2.7 式(6.13)的解释

因为式(6.6)满足Slater条件，所以强对偶性成立，进而最优解满足KKT条件。

6.3 核函数

6.3.1 式(6.22)的解释

此即核函数的定义，即核函数可以分解成两个向量的内积。要想了解某个核函数是如何将原始特征空间映射到更高维的特征空间的，只需要分解为两个表达形式完全一样的向量内积即可。

6.4 软间隔与正则化

6.4.1 式(6.35)的推导

令

$$\max \left(0,1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)\right)={\xi }_i$$

显然${\xi }_i\ge 0$，且当$1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)>0$时有

$$1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)={\xi }_i$$

当$1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)\le 0$时有

$${\xi }_i=0$$

综上可得

$$1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)⩽{\xi }_i\Rightarrow y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)⩾1-{\xi }_i$$

6.4.2 式(6.37)和式(6.38)的推导

类比式(6.9)和式(6.10)的推导

6.4.3 式(6.39)的推导

式(6.36)关于${\xi }_i$求偏导数并令其为零

$$\frac{\partial L}{\partial {\xi }_i}=0+C\times 1-{\alpha }_i\times 1-{\mu }_i\times 1=0\Rightarrow C={\alpha }_i+{\mu }_i$$

6.4.4 式(6.40)的推导

将式(6.37)、式(6.38)和(6.39)代入式(6.36)可以得到式(6.35)的对偶问题，有

$$\begin{array}{rl}& \frac{1}{2}{\Vert \mathbf{w}\Vert }^2+C\sum _{i=1}^m{\xi }_i+\sum _{i=1}^m{\alpha }_i\left(1-{\xi }_i-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)\right)-\sum _{i=1}^m{\mu }_i{\xi }_i\\ =& \frac{1}{2}{\Vert \mathbf{w}\Vert }^2+\sum _{i=1}^m{\alpha }_i\left(1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)\right)+C\sum _{i=1}^m{\xi }_i-\sum _{i=1}^m{\alpha }_i{\xi }_i-\sum _{i=1}^m{\mu }_i{\xi }_i\\ =& -\frac{1}{2}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i+\sum _{i=1}^m{\alpha }_i+\sum _{i=1}^{m}C{\xi }_i-\sum _{i=1}^m{\alpha }_i{\xi }_i-\sum _{i=1}^m{\mu }_i{\xi }_i\\ =& -\frac{1}{2}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i+\sum _{i=1}^m{\alpha }_i+\sum _{i=1}^m(C-{\alpha }_i-{\mu }_i){\xi }_i\\ =& \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^{\mathrm{T}}{\mathbf{x}}_j\\ =& \underset{\mathbf{w},b,\mathbf{\xi }}{\min }L(\mathbf{w},b,\mathbf{\alpha },\mathbf{\xi },\mathbf{\mu })\end{array}$$

所以

$$\begin{array}{rl}\underset{\mathbf{\alpha },\mathbf{\mu }}{\max }\underset{\mathbf{w},b,\mathbf{\xi }}{\min }L(\mathbf{w},b,\mathbf{\alpha },\mathbf{\xi },\mathbf{\mu })& =\underset{\mathbf{\alpha },\mathbf{\mu }}{\max }\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^{\mathrm{T}}{\mathbf{x}}_j\\ & =\underset{\mathbf{\alpha }}{\max }\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^{\mathrm{T}}{\mathbf{x}}_j\end{array}$$

又因为 ${\alpha }_i\ge 0$，${\mu }_i\ge 0$， $C={\alpha }_i+{\mu }_i$，消去${\mu }_i$可得等价约束条件

$$0⩽{\alpha }_i⩽C,i=1,2,...,m$$

6.4.5 对数几率回归与支持向量机的关系

在"西瓜书"本节的倒数第二段开头，其讨论了对数几率回归与支持向量机的关系，提到"如果使用对率损失函数${\ell }_{\log }$来替代式(6.29)中的$0/1$损失函数，则几乎就得到了对率回归模型(3.27)"，但式(6.29)与式(3.27)形式上相差甚远。为了更清晰的说明对数几率回归与软间隔支持向量机的关系，以下先对式(3.27)的形式进行变化。

将$\mathbf{\beta }=(\mathbf{w};b)$和$\hat{\mathbf{x}}=(\mathbf{x};1)$代入式(3.27)可得

$$\begin{array}{rl}\ell (\mathbf{w},b)& =\sum _{i=1}^m\left(-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)+\ln \left(1+e^{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}\right)\right)\\ & =\sum _{i=1}^m\left(\ln \frac{1}{e^{y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)}}+\ln \left(1+e^{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}\right)\right)\\ & =\sum _{i=1}^m\ln \frac{1+e^{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}}{e^{y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)}}\\ & =\{\begin{array}{cl}{\sum }_{i=1}^m\ln \left(1+e^{-\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)}\right),& y_i=1\\ {\sum }_{i=1}^m\ln \left(1+e^{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}\right),& y_i=0\end{array}\end{array}$$

上式中正例和反例分别用$y_i=1$和$y_i=0$表示，这是对数几率回归常用的方式，而在支持向量机中正例和反例习惯用$y_i=+1$和$y_i=-1$表示。实际上，若上式也换用$y_i=+1$和$y_i=-1$分别表示正例和反例，则上式可改写为

$$\begin{array}{rl}\ell (\mathbf{w},b)& =\{\begin{array}{cl}{\sum }_{i=1}^m\ln \left(1+e^{-\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)}\right),& y_i=+1\\ {\sum }_{i=1}^m\ln \left(1+e^{{\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b}\right),& y_i=-1\end{array}\\ & =\sum _{i=1}^m\ln \left(1+e^{-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)}\right)\end{array}$$

此时上式的求和项正是式(6.33)所表述的对率损失。

6.4.6 式(6.41)的解释

参见式(6.13)的解释

6.5 支持向量回归

6.5.1 式(6.43)的解释

相比于线性回归用一条线来拟合训练样本，支持向量回归而是采用一个以$f(\mathbf{x})={\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b$为中心，宽度为$2ϵ$的间隔带，来拟合训练样本。

落在带子上的样本不计算损失（类比线性回归在线上的点预测误差为0），不在带子上的则以偏离带子的距离作为损失（类比线性回归的均方误差），然后以最小化损失的方式迫使间隔带从样本最密集的地方穿过，进而达到拟合训练样本的目的。因此支持向量回归的优化问题可以写为

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{\ell }_{ϵ}\left(f\left({\mathbf{x}}_i\right)-y_i\right)$$

其中${\ell }_{ϵ}(z)$为"$ϵ$不敏感损失函数"（类比线性回归的均方误差损失）

$${\ell }_{ϵ}(z)=\{\begin{array}{cc}0,& \text{ if }|z|⩽ϵ\\ |z|-ϵ,& \text{ if }|z|>ϵ\end{array}$$

$\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$为L2正则项，此处引入正则项除了起正则化本身的作用外，也是为了和软间隔支持向量机的优化目标保持形式上的一致，这样就可以导出对偶问题引入核函数，$C$为用来调节损失权重的正则化常数。

6.5.2 式(6.45)的推导

同软间隔支持向量机，引入松弛变量${\xi }_i$，令

$${\ell }_{ϵ}\left(f\left({\mathbf{x}}_i\right)-y_i\right)={\xi }_i$$

显然${\xi }_i⩾0$，并且当$|f\left({\mathbf{x}}_i\right)-y_i|⩽ϵ$时，${\xi }_i=0$，当$|f\left({\mathbf{x}}_i\right)-y_i|>ϵ$时，${\xi }_i=|f\left({\mathbf{x}}_i\right)-y_i|-ϵ$，所以

$$|f\left({\mathbf{x}}_i\right)-y_i|-ϵ⩽{\xi }_i$$

$$|f\left({\mathbf{x}}_i\right)-y_i|⩽ϵ+{\xi }_i$$

$$-ϵ-{\xi }_i⩽f\left({\mathbf{x}}_i\right)-y_i⩽ϵ+{\xi }_i$$

因此支持向量回归的优化问题可以化为

$$\underset{\mathbf{w},b,{\xi }_i}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{\xi }_i$$

$$\begin{array}{ll}\text{ s.t. }& -ϵ-{\xi }_i⩽f\left({\mathbf{x}}_i\right)-y_i⩽ϵ+{\xi }_i\\ & {\xi }_i⩾0,i=1,2,\dots ,m\end{array}$$

如果考虑两边采用不同的松弛程度，则有

$$\underset{\mathbf{w},b,{\xi }_i,{\hat{\xi }}_i}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m\left({\xi }_i+{\hat{\xi }}_i\right)$$

$$\begin{array}{ll}\text{ s.t. }& -ϵ-{\hat{\xi }}_i⩽f\left({\mathbf{x}}_i\right)-y_i⩽ϵ+{\xi }_i\\ & {\xi }_i⩾0,{\hat{\xi }}_i⩾0,i=1,2,\dots ,m\end{array}$$

6.5.3 式(6.52)的推导

将式(6.45)的约束条件全部恒等变形为小于等于0的形式可得

$$\{\begin{array}{l}f\left({\mathbf{x}}_i\right)-y_i-ϵ-{\xi }_i\le 0\\ y_i-f\left({\mathbf{x}}_i\right)-ϵ-{\hat{\xi }}_i\le 0\\ -{\xi }_i\le 0\\ -{\hat{\xi }}_i\le 0\end{array}$$

由于以上四个约束条件的拉格朗日乘子分别为${\alpha }_i,{\hat{\alpha }}_i,{\mu }_i,{\hat{\mu }}_i$，所以其对应的KKT条件为

$$\{\begin{array}{l}{\alpha }_i\left(f\left({\mathbf{x}}_i\right)-y_i-ϵ-{\xi }_i\right)=0\\ {\hat{\alpha }}_i\left(y_i-f\left({\mathbf{x}}_i\right)-ϵ-{\hat{\xi }}_i\right)=0\\ -{\mu }_i{\xi }_i=0\Rightarrow {\mu }_i{\xi }_i=0\\ -{\hat{\mu }}_i{\hat{\xi }}_i=0\Rightarrow {\hat{\mu }}_i{\hat{\xi }}_i=0\end{array}$$

又由式(6.49)和式(6.50)有

$$\{\begin{array}{r}{\mu }_i=C-{\alpha }_i\\ {\hat{\mu }}_i=C-{\hat{\alpha }}_i\end{array}$$

所以上述KKT条件可以进一步变形为

$$\{\begin{array}{l}{\alpha }_i\left(f\left({\mathbf{x}}_i\right)-y_i-ϵ-{\xi }_i\right)=0\\ {\hat{\alpha }}_i\left(y_i-f\left({\mathbf{x}}_i\right)-ϵ-{\hat{\xi }}_i\right)=0\\ (C-{\alpha }_i){\xi }_i=0\\ (C-{\hat{\alpha }}_i){\hat{\xi }}_i=0\end{array}$$

又因为样本$({\mathbf{x}}_i,y_i)$只可能处在间隔带的某一侧，即约束条件$f\left({\mathbf{x}}_i\right)-y_i-ϵ-{\xi }_i=0$和$y_i-f\left({\mathbf{x}}_i\right)-ϵ-{\hat{\xi }}_i=0$不可能同时成立，所以${\alpha }_i$和${\hat{\alpha }}_i$中至少有一个为0，即${\alpha }_i{\hat{\alpha }}_i=0$。

在此基础上再进一步分析可知，如果${\alpha }_i=0$，则根据约束$(C-{\alpha }_i){\xi }_i=0$可知此时${\xi }_i=0$。同理，如果${\hat{\alpha }}_i=0$，则根据约束$(C-{\hat{\alpha }}_i){\hat{\xi }}_i=0$可知此时${\hat{\xi }}_i=0$。所以${\xi }_i$和${\hat{\xi }}_i$中也是至少有一个为0，即${\xi }_i{\hat{\xi }}_i=0$。将${\alpha }_i{\hat{\alpha }}_i=0,{\xi }_i{\hat{\xi }}_i=0$整合进上述KKT条件中即可得到式(6.52)。

6.6 核方法

6.6.1 式(6.57)和式(6.58)的解释

式(6.24)是式(6.20)的解；式(6.56)是式(6.43)的解。对应到表示定理式(6.57)当中，式(6.20)和式(6.43)均为$\Omega \left(\Vert h{\Vert }_{\mathbb{H}}\right)=\frac{1}{2}\Vert \mathbf{w}{\Vert }^2$，式(6.20)的$\ell \left(h({\mathbf{x}}_1),h({\mathbf{x}}_2),...,h({\mathbf{x}}_m)\right)=0$，而式(6.43)的$\ell \left(h({\mathbf{x}}_1),h({\mathbf{x}}_2),...,h({\mathbf{x}}_m)\right)=C{\sum }_{i=1}^m{\ell }_{ϵ}(f({\mathbf{x}}_i)-y_i)$，均满足式(6.57)的要求，式(6.20)和式(6.43)的解均为$\kappa (\mathbf{x},{\mathbf{x}}_i)$的线性组合，即式(6.58)。

6.6.2 式(6.65)的推导

由表示定理可知，此时二分类KLDA最终求得的投影直线方程总可以写成如下形式：

$$h(\mathbf{x})=\sum _{i=1}^m{\alpha }_i\kappa \left(\mathbf{x},{\mathbf{x}}_i\right)$$

又因为直线方程的固定形式为

$$h(\mathbf{x})={\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})$$

所以

$${\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})=\sum _{i=1}^m{\alpha }_i\kappa \left(\mathbf{x},{\mathbf{x}}_i\right)$$

将$\kappa \left(\mathbf{x},{\mathbf{x}}_i\right)=\varphi (\mathbf{x}{)}^{\mathrm{T}}\varphi ({\mathbf{x}}_i)$代入可得

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})& =\sum _{i=1}^m{\alpha }_i\varphi (\mathbf{x}{)}^{\mathrm{T}}\varphi ({\mathbf{x}}_i)\\ & =\varphi (\mathbf{x}{)}^{\mathrm{T}}\cdot \sum _{i=1}^m{\alpha }_i\varphi ({\mathbf{x}}_i)\end{array}$$

由于${\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})$的计算结果为标量，而标量的转置等于其本身，所以

$${\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})={\left({\mathbf{w}}^{\mathrm{T}}\varphi (\mathbf{x})\right)}^{\mathrm{T}}=\varphi (\mathbf{x}{)}^{\mathrm{T}}\mathbf{w}=\varphi (\mathbf{x}{)}^{\mathrm{T}}\sum _{i=1}^m{\alpha }_i\varphi ({\mathbf{x}}_i)$$

即

$$\mathbf{w}=\sum _{i=1}^m{\alpha }_i\varphi ({\mathbf{x}}_i)$$

6.6.3 式(6.66)和式(6.67)的解释

为了详细地说明此式的计算原理，下面首先举例说明，然后再在例子的基础上延展出其一般形式。 假设此时仅有4个样本，其中第1和第3个样本的标记为0，第2和第4个样本的标记为1，那么此时有

$$m=4$$

$$m_0=2,m_1=2$$

$$X_0=\{{\mathbf{x}}_1,{\mathbf{x}}_3\},X_1=\{{\mathbf{x}}_2,{\mathbf{x}}_4\}$$

$$\mathbf{K}=\left[\begin{array}{cccc}\kappa \left({\mathbf{x}}_1,{\mathbf{x}}_1\right)& \kappa \left({\mathbf{x}}_1,{\mathbf{x}}_2\right)& \kappa \left({\mathbf{x}}_1,{\mathbf{x}}_3\right)& \kappa \left({\mathbf{x}}_1,{\mathbf{x}}_4\right)\\ \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_1\right)& \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_2\right)& \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_3\right)& \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_4\right)\\ \kappa \left({\mathbf{x}}_3,{\mathbf{x}}_1\right)& \kappa \left({\mathbf{x}}_3,{\mathbf{x}}_2\right)& \kappa \left({\mathbf{x}}_3,{\mathbf{x}}_3\right)& \kappa \left({\mathbf{x}}_3,{\mathbf{x}}_4\right)\\ \kappa \left({\mathbf{x}}_4,{\mathbf{x}}_1\right)& \kappa \left({\mathbf{x}}_4,{\mathbf{x}}_2\right)& \kappa \left({\mathbf{x}}_4,{\mathbf{x}}_3\right)& \kappa \left({\mathbf{x}}_4,{\mathbf{x}}_4\right)\end{array}\right]\in {\mathbb{R}}^{4\times 4}$$

$$1_0=\left[\begin{array}{c}1\\ 0\\ 1\\ 0\end{array}\right]\in {\mathbb{R}}^{4\times 1}$$

$$1_1=\left[\begin{array}{c}0\\ 1\\ 0\\ 1\end{array}\right]\in {\mathbb{R}}^{4\times 1}$$

所以

$${\hat{\mathbf{\mu }}}_0=\frac{1}{m_0}\mathbf{K}{1}_0=\frac{1}{2}\left[\begin{array}{c}\kappa \left({\mathbf{x}}_1,{\mathbf{x}}_1\right)+\kappa \left({\mathbf{x}}_1,{\mathbf{x}}_3\right)\\ \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_1\right)+\kappa \left({\mathbf{x}}_2,{\mathbf{x}}_3\right)\\ \kappa \left({\mathbf{x}}_3,{\mathbf{x}}_1\right)+\kappa \left({\mathbf{x}}_3,{\mathbf{x}}_3\right)\\ \kappa \left({\mathbf{x}}_4,{\mathbf{x}}_1\right)+\kappa \left({\mathbf{x}}_4,{\mathbf{x}}_3\right)\end{array}\right]\in {\mathbb{R}}^{4\times 1}$$

$${\hat{\mathbf{\mu }}}_1=\frac{1}{m_1}\mathbf{K}{1}_1=\frac{1}{2}\left[\begin{array}{c}\kappa \left({\mathbf{x}}_1,{\mathbf{x}}_2\right)+\kappa \left({\mathbf{x}}_1,{\mathbf{x}}_4\right)\\ \kappa \left({\mathbf{x}}_2,{\mathbf{x}}_2\right)+\kappa \left({\mathbf{x}}_2,{\mathbf{x}}_4\right)\\ \kappa \left({\mathbf{x}}_3,{\mathbf{x}}_2\right)+\kappa \left({\mathbf{x}}_3,{\mathbf{x}}_4\right)\\ \kappa \left({\mathbf{x}}_4,{\mathbf{x}}_2\right)+\kappa \left({\mathbf{x}}_4,{\mathbf{x}}_4\right)\end{array}\right]\in {\mathbb{R}}^{4\times 1}$$

根据此结果易得${\hat{\mathbf{\mu }}}_0,{\hat{\mathbf{\mu }}}_1$的一般形式为

$${\hat{\mathbf{\mu }}}_0=\frac{1}{m_0}\mathbf{K}{1}_0=\frac{1}{m_0}\left[\begin{array}{c}{\sum }_{\mathbf{x}\in X_0}\kappa \left({\mathbf{x}}_1,\mathbf{x}\right)\\ {\sum }_{\mathbf{x}\in X_0}\kappa \left({\mathbf{x}}_2,\mathbf{x}\right)\\ ⋮\\ {\sum }_{\mathbf{x}\in X_0}\kappa \left({\mathbf{x}}_m,\mathbf{x}\right)\end{array}\right]\in {\mathbb{R}}^{m\times 1}$$

$${\hat{\mathbf{\mu }}}_1=\frac{1}{m_1}\mathbf{K}{1}_1=\frac{1}{m_1}\left[\begin{array}{c}{\sum }_{\mathbf{x}\in X_1}\kappa \left({\mathbf{x}}_1,\mathbf{x}\right)\\ {\sum }_{\mathbf{x}\in X_1}\kappa \left({\mathbf{x}}_2,\mathbf{x}\right)\\ ⋮\\ {\sum }_{\mathbf{x}\in X_1}\kappa \left({\mathbf{x}}_m,\mathbf{x}\right)\end{array}\right]\in {\mathbb{R}}^{m\times 1}$$

6.6.4 式(6.70)的推导

此式是将式(6.65)代入式(6.60)后推得而来的，下面给出详细地推导过程。

首先将式(6.65)代入式(6.60)的分子可得

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_b^{\varphi }\mathbf{w}& ={\left(\sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\right)}^{\mathrm{T}}\cdot {\mathbf{S}}_b^{\varphi }\cdot \sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\\ & =\sum _{i=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\cdot {\mathbf{S}}_b^{\varphi }\cdot \sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\end{array}$$

其中

$$\begin{array}{rl}{\mathbf{S}}_b^{\varphi }& =\left({\mathbf{\mu }}_1^{\varphi }-{\mathbf{\mu }}_0^{\varphi }\right){\left({\mathbf{\mu }}_1^{\varphi }-{\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}\\ & =\left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x})-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x})\right){\left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x})-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x})\right)}^{\mathrm{T}}\\ & =\left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x})-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x})\right)\left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x}{)}^{\mathrm{T}}-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x}{)}^{\mathrm{T}}\right)\end{array}$$

将其代入上式可得

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_b^{\varphi }\mathbf{w}=& \sum _{i=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\cdot \left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x})-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x})\right)\cdot \left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x}{)}^{\mathrm{T}}-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x}{)}^{\mathrm{T}}\right)\cdot \sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\\ =& \left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\sum _{i=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\varphi (\mathbf{x})-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\sum _{i=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\varphi (\mathbf{x})\right)\\ & \cdot \left(\frac{1}{m_1}\sum _{\mathbf{x}\in X_1}\sum _{i=1}^m{\alpha }_i\varphi (\mathbf{x}{)}^{\mathrm{T}}\varphi \left({\mathbf{x}}_i\right)-\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\sum _{i=1}^m{\alpha }_i\varphi (\mathbf{x}{)}^{\mathrm{T}}\varphi \left({\mathbf{x}}_i\right)\right)\end{array}$$

由于$\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)=\varphi ({\mathbf{x}}_i{)}^{\mathrm{T}}\varphi (\mathbf{x})$为标量，所以其转置等于本身，即$\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)=\varphi ({\mathbf{x}}_i{)}^{\mathrm{T}}\varphi (\mathbf{x})={\left(\varphi ({\mathbf{x}}_i{)}^{\mathrm{T}}\varphi (\mathbf{x})\right)}^{\mathrm{T}}=\varphi (\mathbf{x}{)}^{\mathrm{T}}\varphi ({\mathbf{x}}_i)=\kappa {\left({\mathbf{x}}_i,\mathbf{x}\right)}^{\mathrm{T}}$，将其代入上式可得

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_b^{\varphi }\mathbf{w}=& \left(\frac{1}{m_1}\sum _{i=1}^m\sum _{\mathbf{x}\in X_1}{\alpha }_i\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)-\frac{1}{m_0}\sum _{i=1}^m\sum _{\mathbf{x}\in X_0}{\alpha }_i\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)\right)\\ & \cdot \left(\frac{1}{m_1}\sum _{i=1}^m\sum _{\mathbf{x}\in X_1}{\alpha }_i\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)-\frac{1}{m_0}\sum _{i=1}^m\sum _{\mathbf{x}\in X_0}{\alpha }_i\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)\right)\end{array}$$

设$\mathbf{\alpha }=({\alpha }_1;{\alpha }_2;...;{\alpha }_m{)}^{\mathrm{T}}\in {\mathbb{R}}^{m\times 1}$，同时结合式(6.66)的解释可得到${\hat{\mathbf{\mu }}}_0,{\hat{\mathbf{\mu }}}_1$的一般形式，上式可以化简为

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_b^{\varphi }\mathbf{w}& =\left({\mathbf{\alpha }}^{\mathrm{T}}{\hat{\mathbf{\mu }}}_1-{\mathbf{\alpha }}^{\mathrm{T}}{\hat{\mathbf{\mu }}}_0\right)\cdot \left({\hat{\mathbf{\mu }}}_1^{\mathrm{T}}\mathbf{\alpha }-{\hat{\mathbf{\mu }}}_0^{\mathrm{T}}\mathbf{\alpha }\right)\\ & ={\mathbf{\alpha }}^{\mathrm{T}}\cdot \left({\hat{\mathbf{\mu }}}_1-{\hat{\mathbf{\mu }}}_0\right)\cdot \left({\hat{\mathbf{\mu }}}_1^{\mathrm{T}}-{\hat{\mathbf{\mu }}}_0^{\mathrm{T}}\right)\cdot \mathbf{\alpha }\\ & ={\mathbf{\alpha }}^{\mathrm{T}}\cdot \left({\hat{\mathbf{\mu }}}_1-{\hat{\mathbf{\mu }}}_0\right)\cdot {\left({\hat{\mathbf{\mu }}}_1-{\hat{\mathbf{\mu }}}_0\right)}^{\mathrm{T}}\cdot \mathbf{\alpha }\\ & ={\mathbf{\alpha }}^{\mathrm{T}}\mathbf{M}\mathbf{\alpha }\end{array}$$

以上便是式(6.70)分子部分的推导，下面继续推导式(6.70)的分母部分。将式(6.65)代入式(6.60)的分母可得：

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w^{\varphi }\mathbf{w}& ={\left(\sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\right)}^{\mathrm{T}}\cdot {\mathbf{S}}_w^{\varphi }\cdot \sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\\ & =\sum _{i=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\cdot {\mathbf{S}}_w^{\varphi }\cdot \sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\end{array}$$

其中

$$\begin{array}{rl}{\mathbf{S}}_w^{\varphi }& =\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}\left(\varphi (\mathbf{x})-{\mathbf{\mu }}_i^{\varphi }\right){\left(\varphi (\mathbf{x})-{\mathbf{\mu }}_i^{\varphi }\right)}^{\mathrm{T}}\\ & =\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}\left(\varphi (\mathbf{x})-{\mathbf{\mu }}_i^{\varphi }\right)\left(\varphi (\mathbf{x}{)}^{\mathrm{T}}-{\left({\mathbf{\mu }}_i^{\varphi }\right)}^{\mathrm{T}}\right)\\ & =\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}\left(\varphi (\mathbf{x})\varphi (\mathbf{x}{)}^{\mathrm{T}}-\varphi (\mathbf{x}){\left({\mathbf{\mu }}_i^{\varphi }\right)}^{\mathrm{T}}-{\mathbf{\mu }}_i^{\varphi }\varphi (\mathbf{x}{)}^{\mathrm{T}}+{\mathbf{\mu }}_i^{\varphi }{\left({\mathbf{\mu }}_i^{\varphi }\right)}^{\mathrm{T}}\right)\\ & =\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}\varphi (\mathbf{x})\varphi (\mathbf{x}{)}^{\mathrm{T}}-\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}\varphi (\mathbf{x}){\left({\mathbf{\mu }}_i^{\varphi }\right)}^{\mathrm{T}}-\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}{\mathbf{\mu }}_i^{\varphi }\varphi (\mathbf{x}{)}^{\mathrm{T}}+\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}{\mathbf{\mu }}_i^{\varphi }{\left({\mathbf{\mu }}_i^{\varphi }\right)}^{\mathrm{T}}\end{array}$$

由于

$$\begin{array}{rl}\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}\varphi (\mathbf{x}){\left({\mathbf{\mu }}_i^{\varphi }\right)}^{\mathrm{T}}& =\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x}){\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}+\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x}){\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}\\ & =m_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}+m_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}\end{array}$$

且

$$\begin{array}{rl}\sum _{i=0}^1\sum _{\mathbf{x}\in X_i}{\mathbf{\mu }}_i^{\varphi }\varphi (\mathbf{x}{)}^{\mathrm{T}}& =\sum _{i=0}^1{\mathbf{\mu }}_i^{\varphi }\sum _{\mathbf{x}\in X_i}\varphi (\mathbf{x}{)}^{\mathrm{T}}\\ & ={\mathbf{\mu }}_0^{\varphi }\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x}{)}^{\mathrm{T}}+{\mathbf{\mu }}_1^{\varphi }\sum _{\mathbf{x}\in X_1}\varphi (\mathbf{x}{)}^{\mathrm{T}}\\ & =m_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}+m_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}\end{array}$$

所以

$$\begin{array}{rl}{\mathbf{S}}_w^{\varphi }& =\sum _{\mathbf{x}\in D}\varphi (\mathbf{x})\varphi (\mathbf{x}{)}^{\mathrm{T}}-2\left[m_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}+m_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}\right]+m_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}+m_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}\\ & =\sum _{\mathbf{x}\in D}\varphi (\mathbf{x})\varphi (\mathbf{x}{)}^{\mathrm{T}}-m_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}-m_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}\end{array}$$

再将此式代回${\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w^{\varphi }\mathbf{w}$可得

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w^{\varphi }\mathbf{w}=& \sum _{i=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\cdot {\mathbf{S}}_w^{\varphi }\cdot \sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\\ =& \sum _{i=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\cdot \left(\sum _{\mathbf{x}\in D}\varphi (\mathbf{x})\varphi (\mathbf{x}{)}^{\mathrm{T}}-m_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}-m_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}\right)\cdot \sum _{i=1}^m{\alpha }_i\varphi \left({\mathbf{x}}_i\right)\\ =& \sum _{i=1}^m\sum _{j=1}^m\sum _{\mathbf{x}\in D}{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\varphi (\mathbf{x})\varphi (\mathbf{x}{)}^{\mathrm{T}}{\alpha }_j\varphi \left({\mathbf{x}}_j\right)-\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}{m}_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}{\alpha }_j\varphi \left({\mathbf{x}}_j\right)\\ & -\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}{m}_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}{\alpha }_j\varphi \left({\mathbf{x}}_j\right)\end{array}$$

其中，第1项

$$\begin{array}{rl}\sum _{i=1}^m\sum _{j=1}^m\sum _{\mathbf{x}\in D}{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\varphi (\mathbf{x})\varphi (\mathbf{x}{)}^{\mathrm{T}}{\alpha }_j\varphi \left({\mathbf{x}}_j\right)& =\sum _{i=1}^m\sum _{j=1}^m\sum _{\mathbf{x}\in D}{\alpha }_i{\alpha }_j\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)\kappa \left({\mathbf{x}}_j,\mathbf{x}\right)\\ & ={\mathbf{\alpha }}^{\mathrm{T}}\mathbf{K}{\mathbf{K}}^{\mathrm{T}}\mathbf{\alpha }\end{array}$$

第2项

$$\begin{array}{rl}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}{m}_0{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}{\alpha }_j\varphi \left({\mathbf{x}}_j\right)& =m_0\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}{\mathbf{\mu }}_0^{\varphi }{\left({\mathbf{\mu }}_0^{\varphi }\right)}^{\mathrm{T}}\varphi \left({\mathbf{x}}_j\right)\\ & =m_0\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\left[\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x})\right]{\left[\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x})\right]}^{\mathrm{T}}\varphi \left({\mathbf{x}}_j\right)\\ & =m_0\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j\left[\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\varphi (\mathbf{x})\right]\left[\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\varphi (\mathbf{x}{)}^{\mathrm{T}}\varphi \left({\mathbf{x}}_j\right)\right]\\ & =m_0\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j\left[\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\kappa \left({\mathbf{x}}_i,\mathbf{x}\right)\right]\left[\frac{1}{m_0}\sum _{\mathbf{x}\in X_0}\kappa \left({\mathbf{x}}_j,\mathbf{x}\right)\right]\\ & =m_0{\mathbf{\alpha }}^{\mathrm{T}}{\hat{\mathbf{\mu }}}_0{\hat{\mathbf{\mu }}}_0^{\mathrm{T}}\mathbf{\alpha }\end{array}$$

同理，有第3项

$$\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}{m}_1{\mathbf{\mu }}_1^{\varphi }{\left({\mathbf{\mu }}_1^{\varphi }\right)}^{\mathrm{T}}{\alpha }_j\varphi \left({\mathbf{x}}_j\right)=m_1{\mathbf{\alpha }}^{\mathrm{T}}{\hat{\mathbf{\mu }}}_1{\hat{\mathbf{\mu }}}_1^{\mathrm{T}}\mathbf{\alpha }$$

将上述三项的化简结果代回再将此式代回${\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w^{\varphi }\mathbf{w}$可得

$$\begin{array}{rl}{\mathbf{w}}^{\mathrm{T}}{\mathbf{S}}_w^{\varphi }\mathbf{w}& ={\mathbf{\alpha }}^{\mathrm{T}}\mathbf{K}{\mathbf{K}}^{\mathrm{T}}\mathbf{\alpha }-m_0{\mathbf{\alpha }}^{\mathrm{T}}{\hat{\mathbf{\mu }}}_0{\hat{\mathbf{\mu }}}_0^{\mathrm{T}}\mathbf{\alpha }-m_1{\mathbf{\alpha }}^{\mathrm{T}}{\hat{\mathbf{\mu }}}_1{\hat{\mathbf{\mu }}}_1^{\mathrm{T}}\mathbf{\alpha }\\ & ={\mathbf{\alpha }}^{\mathrm{T}}\cdot \left(\mathbf{K}{\mathbf{K}}^{\mathrm{T}}-m_0{\hat{\mathbf{\mu }}}_0{\hat{\mathbf{\mu }}}_0^{\mathrm{T}}-m_1{\hat{\mathbf{\mu }}}_1{\hat{\mathbf{\mu }}}_1^{\mathrm{T}}\right)\cdot \mathbf{\alpha }\\ & ={\mathbf{\alpha }}^{\mathrm{T}}\cdot \left(\mathbf{K}{\mathbf{K}}^{\mathrm{T}}-\sum _{i=0}^1{m}_i{\hat{\mathbf{\mu }}}_i{\hat{\mathbf{\mu }}}_i^{\mathrm{T}}\right)\cdot \mathbf{\alpha }\\ & ={\mathbf{\alpha }}^{\mathrm{T}}\mathbf{N}\mathbf{\alpha }\end{array}$$

6.6.5 核对数几率回归

将"对数几率回归与支持向量机的关系"中最后得到的对数几率回归重写为如下形式

$$\underset{\mathbf{w},b}{\min }\frac{1}{m}\sum _{i=1}^m\log \left(1+e^{-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)}\right)+\frac{\lambda }{2m}\Vert \mathbf{w}{\Vert }^2$$

其中$\lambda$是用来调整正则项权重的正则化常数。假设${\mathbf{z}}_i=\varphi ({\mathbf{x}}_i)$是由原始空间经核函数映射到高维空间的特征向量，则

$$\underset{\mathbf{w},b}{\min }\frac{1}{m}\sum _{i=1}^m\log \left(1+e^{-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{z}}_i+b\right)}\right)+\frac{\lambda }{2m}\Vert \mathbf{w}{\Vert }^2$$

注意，以上两式中的$\mathbf{w}$维度是不同的，其分别与${\mathbf{x}}_i$和${\mathbf{z}}_i$的维度一致。根据表示定理，上式的解可以写为

$$\mathbf{w}=\sum _{j=1}^m{\alpha }_j{\mathbf{z}}_j$$

将$\mathbf{w}$代入对数几率回归可得

$$\underset{\mathbf{w},b}{\min }\frac{1}{m}\sum _{i=1}^m\log \left(1+e^{-y_i\left({\sum }_{j=1}^m{\alpha }_j{\mathbf{z}}_j^{\mathrm{T}}{\mathbf{z}}_i+b\right)}\right)+\frac{\lambda }{2m}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{\mathbf{z}}_i^{\mathrm{T}}{\mathbf{z}}_j$$

用核函数$\kappa \left({\mathbf{x}}_i,{\mathbf{x}}_j\right)={\mathbf{z}}_i^{\mathrm{T}}{\mathbf{z}}_j=\varphi {\left({\mathbf{x}}_i\right)}^{\mathrm{T}}\varphi \left({\mathbf{x}}_j\right)$替换上式中的内积运算

$$\underset{\mathbf{w},b}{\min }\frac{1}{m}\sum _{i=1}^m\log \left(1+e^{-y_i\left({\sum }_{j=1}^m{\alpha }_j\kappa \left({\mathbf{x}}_i,{\mathbf{x}}_j\right)+b\right)}\right)+\frac{\lambda }{2m}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j\kappa \left({\mathbf{x}}_i,{\mathbf{x}}_j\right)$$

解出$\mathbf{\alpha }=({\alpha }_1,{\alpha }_2,...,{\alpha }_m)$和$b$后，即可得$f(\mathbf{x})={\sum }_{i=1}^m{\alpha }_i\kappa (\mathbf{x},{\mathbf{x}}_i)+b$。

参考文献

[1] 王燕军. 最优化基础理论与方法. 复旦大学出版社, 2011.

[2] 王书宁. 凸优化. 清华大学出版社, 2013.