SVM——支持向量机，人脸识别实验

　　最基本的SVM(Support Vector Machine)旨在使用一个超平面&＃xff0c;分离线性可分的二类样本&＃xff0c;其中正反两类分别在超平面的一侧。SVM算法则是要找出一个最优的超平面。

　　下面从简单到复杂介绍三种SVM形式&＃xff0c;然后介绍一种快速优化SVM的算法&＃xff0c;最后用SVM实现人脸识别。

优化函数定义

　　给定一个特征空间线性可分的数据集&＃xff1a;

$T &＃61; \{(x_1,y_1),(x_2,y_2),...,(x_N,y_N)\}$

　　特征分布类似下图&＃xff1a;

　　如上图&＃xff0c;当特征空间为二维时&＃xff0c;超平面就是比二维空间低一维度的直线。任意维超平面定义如下(其中$x$是$n$维特征向量&＃xff0c;$w,b$是超平面系数)&＃xff1a;

$wx&＃43;b &＃61; 0$

　　对于正例应有$wx_i&＃43;b > 0$&＃xff0c;反例应有$wx_i&＃43;b <0$&＃xff0c;也就是说&＃xff0c;如果分类正确&＃xff0c;应有&＃xff1a;

$y_i(wx_i&＃43;b)> 0$

　　从直观上看&＃xff0c;最优超平面&＃xff0c;应该在将所有样本都正确分类的基础上&＃xff0c;最大化超平面与离超平面最近的样本点的距离。点到面的距离公式中学学过

$\displaystyle \frac{|wx&＃43;b|}{|| w ||}$

　　综上&＃xff0c;优化的问题用数学方式表达&＃xff1a;

$\displaystyle\max\limits_{w,b}\min\limits_{i}(\frac{y_i(wx_i&＃43;b)}{||w||})$

　　或者

$\begin{align*} &\max\limits_{w,b}\;\gamma \\ &\;\text{s.t.}\;\;\;y_i(\frac{w}{||w||}x_i&＃43;\frac{b}{||w||})\ge \gamma,\;\;i&＃61;1,2,...,N \end{align*}$

　　其中$\gamma$为最小距离。令$ \hat{\gamma}&＃61;\gamma||w|| $&＃xff0c;即所谓“函数距离”&＃xff0c;上式可变为&＃xff1a;

$\begin{align*} &\max\limits_{w,b}\;\frac{\hat{\gamma}}{||w||} \\ &\;\text{s.t.}\;\;\;y_i(wx_i&＃43;{b})\ge \hat{\gamma },\;\;i&＃61;1,2,...,N\end{align*}$

　　$\hat{\gamma}$没有被$||w||$规范化&＃xff0c;因此大小与$||w||$有关。而$w,b$等比例变化时&＃xff0c;超平面并不会变。因此&＃xff0c;可以固定$||w||&＃61;1$&＃xff0c;最大化$\hat{\gamma}$&＃xff0c;即&＃xff1a;

$\begin{align*} &\max\limits_{w,b}\;\hat{\gamma}\\ &\;\text{s.t.}\;\;\;y_i(wx_i&＃43;{b})\ge \hat{\gamma },\;\;i&＃61;1,2,...,N;\\ &\;\;\;\;\;\;\;\;\; ||w||&＃61;1 \end{align*}$ 

　　或者固定$\hat{\gamma}&＃61;1$&＃xff0c;最小化$||w||$&＃xff0c;也就是&＃xff1a;

$\begin{align*} &\min\limits_{w,b}\;\frac{1}{2}||w||^2 \\ &\;\text{s.t.}\;\;\;y_i(wx_i&＃43;{b})\ge 1,\;\;i&＃61;1,2,...,N\end{align*}$

　　通常是最小化$||w||$。这是一个凸二次规划问题&＃xff0c;即待优化的函数$\frac{1}{2}||w||^2$是二次函数&＃xff0c;不等式约束条件$1-y_i(wx_i&＃43;{b})\le 0$为可微凸函数(这是仿射函数&＃xff0c;自然是凸函数)。

对偶算法

　　上述带约束优化满足原始问题最优值与对偶问题最优值取等的条件&＃xff0c;因此可以使用拉格朗日对偶性(点击链接)将原始优化问题转换为其对偶问题求解。原始问题的拉格朗日函数为&＃xff1a;

$\displaystyle \begin{gather}L(w,b,\alpha) &＃61; \frac{1}{2}||w||^2- \sum\limits_{i&＃61;1}^{N}\alpha_iy_i(wx_i&＃43;b)&＃43;\sum\limits_{i&＃61;1}^{N}\alpha_i,\,\,\alpha\ge 0  \label{}\end{gather}$

　　因此原始问题为&＃xff1a;

$\displaystyle \begin{gather} \min\limits_{w,b}\max\limits_{\alpha\ge 0 }L(w,b,\alpha)  \label{}\end{gather}$

　　则对偶问题为&＃xff1a;

$\displaystyle \begin{gather}\max\limits_{\alpha\ge 0 } \min\limits_{w,b}L(w,b,\alpha)  \label{}\end{gather}$

　　由KKT条件1式令梯度为0&＃xff0c;计算对偶问题内部的$\min$函数

$\begin{aligned} &\nabla_wL(w,b,\alpha) &＃61; w-\sum\limits_{i&＃61;1}^{N}\alpha_iy_ix_i&＃61;0 \\ &\nabla_bL(w,b,\alpha) &＃61; -\sum\limits_{i&＃61;1}^{N}\alpha_iy_i&＃61;0 \\ \end{aligned}$

　　得

$\begin{gather} &w &＃61; \sum\limits_{i&＃61;1}^{N}\alpha_iy_ix_i \\ &\sum\limits_{i&＃61;1}^{N}\alpha_iy_i&＃61;0 \label{}\end{gather}$

　　代入$(3)$式&＃xff0c;经过计算&＃xff0c;对偶问题变为&＃xff1a;

$\begin{gather} \begin{array}{lcl} \min\limits_{\alpha}\displaystyle\frac{1}{2}\sum\limits_{i&＃61;1}^{N}\sum\limits_{j&＃61;1}^{N}\alpha_i\alpha_jy_iy_j(x_ix_j)-\sum\limits_{i&＃61;1}^{N}\alpha_i \\ \begin{aligned} \text{s.t.}\;&\sum\limits_{i&＃61;1}^{N}\alpha_iy_i&＃61;0\\ &\alpha_i\ge 0,i &＃61; 1,2,...,N \end{aligned} \end{array} \end{gather}$

　　这样&＃xff0c;只需先优化对偶问题&＃xff0c;计算出最优的$\alpha^*$&＃xff0c;再代入$(4)$式即可算出最优$w^*$。对于$b$&＃xff0c;因为至少有一个$\alpha_j^*>0$(如果全都为0&＃xff0c;由$(4)$式有$w&＃61;0$&＃xff0c;不符合约束)&＃xff0c;对应KKT条件2式

$\alpha_i(y_i(wx_i&＃43;b)-1)&＃61;0$

　　于是有

$y_j(w^*x_j&＃43;b^*)-1&＃61;0$

　　实际上这个$x_j$就是与超平面最近的的样本&＃xff0c;也就是所谓的支持向量。另外也说明了这个优化问题的解一定在不等式约束的边界上&＃xff0c;而不在其内部。于是&＃xff0c;提取$b^*$并将$(4)$式代入&＃xff0c;得&＃xff1a;

$\begin{gather}\displaystyle b^* &＃61; y_j-\sum\limits_{i&＃61;1}^{N}\alpha_i^*y_i(x_ix_j)\end{gather}$

　　综上&＃xff0c;计算最优$w^*,b^*$的操作就是&＃xff1a;先$(6)$式算出$\alpha^*$&＃xff0c;再代入$(4),(7)$式算出$w^*,b^*$。

　　但是$(6)$实际上并不好算&＃xff0c;当样本量一大&＃xff0c;$\alpha$需要分类讨论的情况数以指数级上升(即每个$\alpha$是否为0)&＃xff0c;后面介绍开销小的算法。

参数计算

　　有时样本会有特异点&＃xff0c;不能保证每个样本都满足不等式约束。因此修改上面的“硬间隔最大化”为“软间隔最大化”&＃xff0c;则线性可分SVM变为线性SVM。即添加一个松弛变量$\xi$&＃xff0c;允许原来的不等式约束不一定严格满足&＃xff0c;当然在优化函数中也要把这一损失加上&＃xff0c;乘上惩罚参数$C$。得到如下最优化问题&＃xff1a;

$\begin{gather} \begin{array}{lcl} \min\limits_{w,b,\xi}\;\displaystyle\frac{1}{2}||w||^2&＃43;C\sum\limits_{i&＃61;1}^{N}\xi_i \\ \begin{aligned} \text{s.t.}\;\;\;&y_i(wx_i&＃43;{b})\ge 1-\xi_i,\;\;i&＃61;1,2,...,N\\ &\xi_i\ge 0,\;\;i&＃61;1,2,...,N\\ \end{aligned} \end{array}\end{gather}$

　　显然待优化函数与不等式约束都是凸函数(仿射函数也是凸函数)。因此同样符合KKT条件&＃xff0c;可以对偶化计算。拉格朗日函数为&＃xff1a;

$ \begin{aligned} \displaystyle L(w,b,\xi,\alpha,\mu) &＃61;& \frac{1}{2}||w||^2&＃43;C\sum\limits_{i&＃61;1}^{N}\xi_i-\sum\limits_{i&＃61;1}^{N}\alpha_i(y_i(wx_i&＃43;b)-1&＃43;\xi_i)-\sum\limits_{i&＃61;1}^{N}\mu_i\xi_i,\\ &\text{where}\;\;\alpha_i\ge 0,\mu_i\ge 0 \end{aligned} $

　　则原始问题变为&＃xff1a;

$ \min\limits_{w,b,\xi}\max \limits_{\alpha\ge 0 ,\mu \ge 0}L(w,b,\xi,\alpha,\mu) $

　　其对偶问题为&＃xff1a;

$\begin{gather} \max \limits_{\alpha\ge 0 ,\mu \ge 0}\min\limits_{w,b,\xi}L(w,b,\xi,\alpha,\mu) \end{gather}$

　　由KKT条件1式令梯度为0&＃xff0c;计算对偶问题内部$\min$函数&＃xff0c;得&＃xff1a;

\begin{align} &\nabla_wL(w,b,\xi,\alpha,\mu) &＃61; w-\sum\limits_{i&＃61;1}^{N}\alpha_iy_ix_i&＃61;0 \\ &\nabla_bL(w,b,\xi,\alpha,\mu) &＃61; -\sum\limits_{i&＃61;1}^{N}\alpha_iy_i&＃61;0 \notag\\ &\nabla_{\xi_i}L(w,b,\xi,\alpha,\mu) &＃61; C-\alpha_i-\mu_i&＃61;0 \notag \end{align}

　　代入$(9)$式&＃xff0c;对偶问题变为&＃xff1a;

\begin{gather} \begin{array}{lcl} \min\limits_{\alpha}\displaystyle\frac{1}{2}\sum\limits_{i&＃61;1}^{N}\sum\limits_{j&＃61;1}^{N}\alpha_i\alpha_jy_iy_j(x_ix_j)-\sum\limits_{i&＃61;1}^{N}\alpha_i \\ \begin{aligned} \text{s.t.}\;&\sum\limits_{i&＃61;1}^{N}\alpha_iy_i&＃61;0\\ &0\le\alpha_i\le C,\;\;i &＃61; 1,2,...,N \end{aligned} \end{array} \end{gather}

　　其中$\alpha_i\le C$是由于$C-\alpha_i&＃61;\mu_i\ge0 $。类似地&＃xff0c;接下来的操作就是&＃xff1a;

　　1、算出$(11)$式的最优$\alpha^*$。

　　2、$\alpha^*$代入$(10)$式计算$w^*$。

　　3、找出满足$\alpha_j^*$满足$0<\alpha_j^*

　　　　此时$\mu_j^* &＃61; C-\alpha_j^*>0$&＃xff0c;由KKT条件2式&＃xff0c;有$\mu_j^*\xi_j^*&＃61;0$&＃xff0c;因此$\xi_j^*&＃61;0$。

　　　　同样地&＃xff0c;由KKT2式&＃xff0c;有$\alpha_j^*(y_j(w^*x_j&＃43;b^*)-1&＃43;\xi_j^*)&＃61;0$&＃xff0c;因$\alpha_j^*>0$&＃xff0c;于是有&＃xff1a;

$\displaystyle b^* &＃61; y_j-\sum\limits_{i&＃61;1}^{N}\alpha_i^*y_i(x_ix_j)$

支持向量

　　在线性SVM中&＃xff0c;因为有松弛变量$\xi$&＃xff0c;不等式约束取等时样本不一定在其类别的边界上。上面只讨论了使用小于$C$的$\alpha_j^*$&＃xff0c;下面做个总结&＃xff1a;
　　1、若$\alpha_i^* &＃61; 0$ &＃xff0c;则$\xi_i &＃61; 0$ &＃xff0c;分类正确&＃xff0c;$x_i$在分离间隔边界的外侧&＃xff1b;

　　2、若$0<\alpha_i^*

　　3、若$\alpha_i^* &＃61; C,0<\xi_i<1$ &＃xff0c;则分类正确&＃xff0c;$x_i$在间隔边界与分离超平面之间&＃xff1b;

　　4、若$\alpha_i^* &＃61; C,\xi_i&＃61;1$&＃xff0c;则分类错误&＃xff0c;$x_i$在分离超平面上&＃xff1b;

　　5、若$\alpha_i^* &＃61; C,\xi_i>1$&＃xff0c;则分类错误&＃xff0c;$x_i$位于分离超平面误分一侧。

　　其中2~5都是支持向量。

合页损失函数

　　线性SVM还有另一种等价的优化目标函数&＃xff1a;

$\begin{gather}\displaystyle \min\limits_{w,b}\sum\limits_{i&＃61;1}^{N}\left[1-y_i(wx_i&＃43;b)\right]_&＃43;&＃43;\lambda||w||^2\end{gather}$

　　其中

$[z]_&＃43;&＃61; \left\{ \begin{aligned} &z,\;\;z>0 \\ &0,\;\;z\le0 \end{aligned} \right.$

　　感觉可以直接梯度下降。

等价性证明

　　令$(12)$中

$\left[1-y_i(wx_i&＃43;b)\right]_&＃43;&＃61;\xi_i$

　　则

　　1、有$\xi_i\ge 0$(一个不等式约束成立)&＃xff1b;

　　2、当$1-y_i(wx_i&＃43;b)>0$时&＃xff0c;可得$y_i(wx_i&＃43;b)&＃61;1-\xi_i$&＃xff1b;

　　3、当$1-y_i(wx_i&＃43;b)\le0$时&＃xff0c;$\xi_i&＃61;0$&＃xff0c;有$y_i(wx_i&＃43;b)\ge1-\xi_i$。

　　　　综合2、3&＃xff0c;不论$1-y_i(wx_i&＃43;b)$如何取值&＃xff0c;总有$y_i(wx_i&＃43;b)\ge1-\xi_i$(另一个不等式约束成立)。

　　于是$(12)$可写成&＃xff1a;

\begin{array}{lcl} \min\limits_{w,b,\xi}\displaystyle\sum\limits_{i&＃61;1}^{N}\xi_i&＃43;\lambda||w||^2\\ \begin{aligned} \text{s.t.}\;\;\;&y_i(wx_i&＃43;{b})\ge 1-\xi_i,\;\;i&＃61;1,2,...,N\\ &\xi_i\ge 0,\;\;i&＃61;1,2,...,N\\ \end{aligned} \end{array}

　　然后优化项常系数权重改一下就和$(8)$一模一样了。

　　对于特征分布是非线性的样本&＃xff0c;需要将非线性可分特征映射到另一个空间(维度不变或变高都可)&＃xff0c;变成线性可分特征。然后才能用线性SVM来优化参数。如图下左图到右图&＃xff1a;

　　理论上需要定义确定的映射函数将输入映射成线性可分的特征&＃xff0c;实际上这一中间环节可以隐去。下面说明这一方法。

核技巧

　　定义从输入空间到特征空间的映射$\phi(x):\mathcal{X}\to \mathcal{H}$&＃xff0c;观察线性可分SVM的对偶问题和最终的判别函数&＃xff0c;里面关于样本特征之间的运算都是内积。因此映射后的线性可分的样本特征要做的同样是内积。定义这一内积为&＃xff1a;

$K(x,z)&＃61;<\phi(x),\phi(z)>$&＃xff0c;后面内积直接用$\phi(x)\phi(z)$表示

　　样本的维度比较小还好&＃xff0c;比如上图的二维&＃xff0c;可以直接想出一个映射&＃xff0c;但是当维度很高时就很难想了。因此想到&＃xff0c;可以跳过定义映射&＃xff0c;直接定义这个$K(x,z)$&＃xff0c;称之为核函数。那么什么样的核函数一定可以表示成两个映射后的向量的内积呢&＃xff1f;这样的核函数叫做正定核。

正定核的充要条件

　　设$K:\mathcal{X}\times\mathcal{X}\to R$为对称函数&＃xff0c;则$K(x ,z) $为正定核函数的充要条件是&＃xff1a;

　　对任意$x_i \in \mathcal{X}&＃xff0c; i&＃61;1, 2,..., n, K(x&＃xff0c; z) $对应的Gram 矩阵

$ \left[ \begin{matrix} K(x_1,x_1)&\cdots&K(x_1,x_n)\\ \vdots&&\vdots\\ K(x_n,x_1)&\cdots&K(x_n,x_n)\\ \end{matrix} \right]\succeq 0$

　　$\succeq 0$表示半正定。具体证明请看《统计学习方法》P136~139

常用正定核

　　线性核(即直接内积)&＃xff1a;

$K(x,z)&＃61;xz$

　　多项式核&＃xff1a;

$K(x,z)&＃61;(xz&＃43;1)^p$

　　高斯核&＃xff1a;

$\displaystyle K(x,z)&＃61;\exp(-\frac{||x-z||^2}{2\sigma^2})$

　　使用核函数后&＃xff0c;待优化的对偶问题变为&＃xff1a;

$ \begin{array}{lcl} \min\limits_{\alpha}\displaystyle\frac{1}{2}\sum\limits_{i&＃61;1}^{N}\sum\limits_{j&＃61;1}^{N}\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum\limits_{i&＃61;1}^{N}\alpha_i \\ \begin{aligned} \text{s.t.}\;&\sum\limits_{i&＃61;1}^{N}\alpha_iy_i&＃61;0\\ &0\le\alpha_i\le C,\;\;i &＃61; 1,2,...,N \end{aligned} \end{array} $

　　分类决策函数变为&＃xff1a;

$\displaystyle f(x) &＃61; \text{sign}\left(\sum\limits_{i&＃61;1}^{N}\alpha^*_iy_iK(x_i,x)&＃43;b^*\right)&＃61;\text{sign}\left(\sum\limits_{i\in S}\alpha^*_iy_iK(x_i,x)&＃43;b^*\right)$

　　即原来的直接内积$x_ix$变成了先映射再内积的$K(x_i,x)$。其中$S$为支持向量集合($\alpha$不为0的样本集合&＃xff0c;即2.2支持向量中的2~5)。

　　然而&＃xff0c;选择合适的正定核以使输入映射成线性可分还需要作其它的努力。。。。。。。。。。

　　正如前面所说&＃xff0c;在对偶问题中&＃xff0c;$\alpha$需要分类讨论的情况数随着样本量的增大以指数级上升(即每个$\alpha$是否为0)&＃xff0c;SMO(sequential minimal optimization)算法可以加快对偶问题的优化。它采用迭代的方式&＃xff0c;每次将待优化问题分离出一个小问题求解&＃xff0c;最终求解原问题。

具体流程

初始化

　　初始化所有的$\alpha_i$为常数(通常为0)&＃xff0c;此时这些$\alpha_i$满足对偶问题的两个不等式约束&＃xff1a;

$\begin{gather}&\sum\limits_{i&＃61;1}^{N}\alpha_iy_i&＃61;0\\ &0\le\alpha_i\le C,\;\;i &＃61; 1,2,...,N\\ \label{}\end{gather}$

　　实际上就是满足KKT条件的1和4&＃xff0c;因为$(13)$是条件1使梯度为0得出的&＃xff0c;$(14)$是条件1和4共同得到的。但是&＃xff0c;它们并不一定同时满足KKT条件的2和3(因为原问题没有等式约束&＃xff0c;所以没有条件5)&＃xff1a;

$\begin{gather}\displaystyle\alpha_i(1-\xi_i-y_i(\sum\limits_{j&＃61;1}^N\alpha_jy_jK_{ji}&＃43;b))&＃61;0\label{}\end{gather}$

$\begin{gather}\displaystyle1-\xi_i-y_i(\sum\limits_{j&＃61;1}^N\alpha_jy_jK_{ji}&＃43;b)\le0\label{}\end{gather}$

　　也就是&＃xff1a;

$\begin{gather}y_i(\sum\limits_{j&＃61;1}^N\alpha_jy_jK_{ji}&＃43;b)\left\{\begin{aligned}&\ge1,\;\;\alpha_i&＃61;0\\&&＃61;1,\;\;0<\alpha_i

　　如果条件2和3也都满足的话&＃xff0c;就迭代结束&＃xff0c;也就达到最终的解了。其中每次迭代都会保持$(13),(14)$两个约束成立。

迭代优化

　　每次迭代&＃xff0c;选出最“不好”的两个$\alpha$来进行优化&＃xff0c;固定剩下的$N-2$个$\alpha$(这样的操作有点像小批量梯度下降)。如何才算“不好”的$\alpha$放后面讲&＃xff0c;因为选择$\alpha$基于优化的效率&＃xff0c;为了说明效率所在&＃xff0c;所以先说优化。

　　不失一般性&＃xff0c;假设选择的两个变量是$\alpha_1,\alpha_2$。则这个子问题可以写为(最小化中将与$\alpha_1,\alpha_2$无关的项去了)&＃xff1a;

$\begin{array}{lcl} \begin{aligned} \min\limits_{\alpha_i,\alpha_2}W(\alpha_1,\alpha_2) &＃61; &\frac{1}{2}K_{11}\alpha_1^2&＃43;\frac{1}{2}K_{22}\alpha_2^2&＃43;y_1y_2K_{12}\alpha_1\alpha_2-\\ &(\alpha_1&＃43;\alpha_2)&＃43;y_1\alpha_1\sum\limits_{i&＃61;3}^Ny_i\alpha_iK_{i1}&＃43;y_2\alpha_2\sum\limits_{i&＃61;3}^Ny_i\alpha_iK_{i2} \\ \end{aligned}\\ \begin{aligned} \text{s.t.}\;\;&\alpha_1y_1&＃43;\alpha_2y_2 &＃61; -\sum\limits_{i&＃61;3}^Ny_i\alpha_i &＃61; \varsigma\\ &0\le\alpha_i\le C,\;\;\;i&＃61;1,2 \end{aligned} \end{array}$

　　由$(13)$式&＃xff0c;$\alpha_1$又可以被$\alpha_2$表达&＃xff0c;于是这个子优化就变为一个带约束的一元二次函数最值问题&＃xff0c;初中生的题目。主要操作就是先用导数求出二次函数的驻点&＃xff0c;如果在约束内就为最终解&＃xff0c;在约束外就选约束中与之较近的端点为解。尽管这么简单&＃xff0c;但是为了后面的选择&＃xff0c;还是要推导一下。约束可以在二维坐标系中表示出来&＃xff1a;

　　因为$y_1,y_2$绝对值为1&＃xff0c;所以只要关于它们的符号进行分类。分成两种情况&＃xff0c;$y_1\ne y_2$和$y_1&＃61;y_2$&＃xff0c;于是可取的点分别如上图a、b中斜线所示。设$\alpha_2$取值为$[L,H]$&＃xff0c;则当$y_1\ne y_2$时

$L&＃61;\max(0,\alpha_2-\alpha_1),H&＃61;\min(C,C&＃43;\alpha_2-\alpha_1)$

　　你可能会有为什么不用$\varsigma$而用$\alpha_2-\alpha_1$来算的疑问。这是因为每次迭代都保持$(13)$的成立&＃xff0c;因此直接用$\alpha_2-\alpha_1$方便&＃xff0c;而$\varsigma$需要算$N-2$个求和。又因为计算时利用了$(13),(14)$&＃xff0c;所以这样算出来的$\alpha_1,\alpha_2$依然能维持$(13),(14)$的成立。当$y_1&＃61;y_2$时

$L&＃61;\max(0,\alpha_2&＃43;\alpha_1-C),H&＃61;\min(C,\alpha_2&＃43;\alpha_1)$

　　然后就是简单的先替换$\alpha_1$&＃xff0c;再求导等于0&＃xff0c;整理后得到&＃xff1a;

$(K_{11}&＃43;K_{22}-2K_{12})\alpha_2^*&＃61;(K_{11}&＃43;K_{22}-2K_{12})\alpha_2&＃43;y_2(E_1-E_2)$

　　其中

\begin{gather} \displaystyle E_i&＃61;\left(\sum\limits_{j&＃61;1}^N\alpha_iy_iK(x_j,x_i)&＃43;b\right)-y_i \label{} \end{gather}

　　$E_i$理解为预测函数对$x_i$的预测值与其真实标签$y_i$之差。再定义

$ \eta &＃61; K_{11}&＃43;K_{22}-2K_{12}$

　　$\eta$理解为$x_1,x_2$映射到特征空间中的向量之间的距离(距离二范的平方)&＃xff0c;于是

$\begin{gather}\displaystyle\alpha_2^*&＃61;\alpha_2&＃43;\frac{y_2(E_1-E_2)}{\eta}\label{}\end{gather}$

 　　然后更新$\alpha_2,\alpha_1$&＃xff1a;

$ \alpha_2^{update}&＃61; \left\{ \begin{aligned} &H,&\alpha_2^*>H\\ &\alpha_2^*,&L\le\alpha_2^*\le H\\ &L,&\alpha_2^*

$\alpha_1^{update} &＃61; (\varsigma - \alpha_2^{update}y_2)y_1 &＃61; \alpha_1&＃43;y_1y_2(\alpha_2-\alpha_2^{update})$

　　最后还有$(18)$的$b$的计算&＃xff0c;《统计学习方法》对$b$的计算感觉没有说清楚。

　　在我理解&＃xff0c;这个$b$的更新就是用更新后的$\alpha_1$或$\alpha_2$&＃xff0c;看哪个在$(0,C)$区间&＃xff0c;就用KKT条件2式即$(15)$直接计算$b$&＃xff1b;如果两个$\alpha$都是0或$C$&＃xff0c;则取依然用$(15)$计算两个$b$&＃xff0c;取这两个$b$的平均值。

　　我的疑问是&＃xff1a;首先&＃xff0c;更新完$\alpha_1,\alpha_2$后&＃xff0c;$\alpha_1,\alpha_2$是否保证满足$(15),(16)$式呢&＃xff0c;也就是没说明能不能用$(15)$来算$b$&＃xff1f;其次&＃xff0c;假设它们更新完后满足$(15),(16)$式&＃xff0c;但是如果$\alpha_1,\alpha_2$都不在$(0,C)$区间为什么还能用$(15)$来算$b$呢&＃xff1f;最后&＃xff0c;书中只说了更新$b$&＃xff0c;刚开始的$b$初始化为多少呢&＃xff1f;还请懂的大佬不吝赐教。

变量的选择

　　变量的选择就是先遍历所有的$\alpha_i$&＃xff0c;查看哪个$\alpha_i$违反$(17)$最严重&＃xff0c;作为待更新的$\alpha_1$&＃xff1b;然后再选择使$(19)$中的$|E_1-E_2|$最大的$\alpha_2$&＃xff0c;以使$\alpha_2$变化最大。

　　接下来使用PCA(点击链接)与SVM实现人脸识别。大致流程如下&＃xff1a;

　　0、对人脸数据集预处理。

　　1、将所有训练集人脸存在矩阵中&＃xff0c;每行一张人脸照片。

　　2、使用PCA对矩阵行降维&＃xff0c;提取特征(用于降维、提取特征的矩阵就是所谓“特征脸”)。

　　3、选择SVM的核函数为高斯核&＃xff0c;再选择一组超参数(软间隔权重C、高斯核的方差)来交叉验证。

　　4、用降维后的人脸矩阵交叉验证得到最优超参数。

　　5、用降维人脸矩阵训练使用最优超参数的SVM&＃xff0c;得到训练完成的SVM。

　　6、把以相同方式存在矩阵中的测试集人脸&＃xff0c;先用前面获得的特征脸降维&＃xff0c;再用训练好的SVM测试&＃xff0c;统计数据。

　　用于训练与测试的人脸集如下图&＃xff1a;

 　　数据预处理代码&＃xff1a;

　　数据获取(与训练测试代码存在同目录即可&＃xff0c;不用执行)&＃xff1a;

　　模型训练与测试&＃xff1a;