关于SVM的一些理解
关于支持向量机的理解
1、模型建立
SVM模型要求样本点分类正确，并且所有样本点到超平面的距离尽可能远（即使得距离超平面最近的点到超平面的距离最大化），因此可以得到如下基础优化问题：
maxw,b,||w||=1Ms.t.yi(wTxi+b)>0|wTxi+b|||w||≥M,∀i
又因为yi={+1,−1},∀i，所以我们有yi(wTxi+b)=|wTxi+b|，并且根据||w||=1，我们可以将问题化简为：
maxw,b,||w||=1Ms.t.yi(wTxi+b)≥M,∀i
当最优解M为负数时，说明存在yi(wTxi+b)<0，说明该组样本线性不可分。若线性可分，一定有M≥0。
但是||w||=1是非线性约束，不利于后续求解，因此我们化简去掉范数约束，我们令w′=wM,b′=bM，则有||w′||=||w||M=1M，因此最大化M即为最小化w′，则原优化问题可以写为：
minw,b||w||s.t.yi(wTxi+b)≥1,∀i
为了方便求解，我们考虑优化12||w||2。考虑到实际问题中很难完全线性可分，我们希望不仅最大化间隔M，也容忍一部分的分类错误（在间隔内部或者完全错误分类）。因此我们引入松弛变量ξ=(ξ1,ξ2,…,ξn)，因此我们可以尝试更改(2)中的约束，可以改成以下两种情况：
yi(wTxi+b)≥M−ξi
或者
yi(wTxi+b)≥M(1−ξi)
这两种情况会得到不同的解，第一种是容忍的误分类点到平面的绝对距离；第二种是容忍的误分类点的相对距离，这个距离和间隔M有关。然而，第一个问题是非凸优化问题，而第二个问题是凸优化问题，因此我们偏向于选取第二个。
此外，我们应该给ξi施以一定的约束（显然ξi太大不能够起到分类的作用），当0<ξi<=1时，该样本点在分类间隔内部；当ξi>1时，该样本点错误分类。因此我们希望∑mi=1ξi有界，即∑mi=1ξi≤constant。
实际情况下，我们并不知道constant的取值，而且由于具体问题的不同，constant的取值差异往往会很大（关键是不知道应该取多少，并且都不知道该怎么调整）。因此我们将∑ni=1ξi作为惩罚项加到目标函数中，作为分类错误损失来与最大间隔相平衡，则得到了如下形式的优化问题：
minw,b12||w||2+Cm∑i=1ξis.t.yi(wTxi+b)≥1−ξi,ξi≥0,∀i
这就是SVM的软间隔模型。当C→∞时，就意味着每一个点必须分类正确，即硬间隔模型。\
2、从损失函数的角度考虑
我们换一个角度考虑软间隔模型，首先，逻辑回归是求解如下优化问题（根据最大似然估计推出）：
minw,b−1mm∑i=1[yilogf(xi)+(1−yi)log(1−f(xi))]+λ||w||2
其中f(x)=11+exp(−(wTx+b)),y={0,1}。这是损失函数+正则化项的形式，按{−1,+1}分类时，损失函数可以重写为：
Cost={log(1+e−zi),zi=wTxi+byi=+1log(1+ezi),zi=wTxi+byi=−1
该损失函数称为对率损失：ℓlog(z)=log(1+e−zi),zi=yi(wTxi+b)。 \
如果我们将对率损失更改为铰链损失：ℓhinge(zi)=max(0,1−zi),zi=yi(wTxi+b)，则得到了以下模型：
minw,bm∑i=1ℓhinge(yi(wTxi+b))+λ||w||2
然后，引入松弛变量ξi=max(0,1−zi)，则可得到ξi≥0,ξi≥1−zi，并令C=12λ，则得到了软间隔模型：
minw,b,ξ12||w||2+Cm∑i=1ξis.t.yi(wTxi+b)≥1−ξi,ξi≥0,∀i \
3、拉格朗日对偶问题
下面，我们来求解该优化问题，原问题的拉格朗日函数为：
\begin{equation}
\begin{aligned}
L(\boldsymbol{w},b,\boldsymbol{\xi};\boldsymbol{\alpha},\boldsymbol{\mu})=& {1 \over 2} ||\boldsymbol{w}||^2 +C \sum_{i=1}^m \xi_i \\
& + \sum_{i=1}^m \alpha_i (1-\xi_i-y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b)) - \sum_{i=1}^m \mu_i \xi_i
\end{aligned}
\end{equation}
其中\alpha_i,\mu_i,\xi_i \ge 0\forall i，令L(\boldsymbol{w},b,\boldsymbol{\xi};\boldsymbol{\alpha},\boldsymbol{\mu})对\boldsymbol{w}，b和\boldsymbol{\xi}的偏导为零，可以得到：
\begin{equation}
\begin{aligned}
&\boldsymbol{w} = \sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i \\
&0 = \sum_{i=1}^m \alpha_i y_i \\
&C = \alpha_i + \mu_i
\end{aligned}
\end{equation}
将(8)带入拉格朗日函数(7)，可以得到:
\begin{equation} \nonumber
\begin{aligned}
L(\boldsymbol{\alpha},\boldsymbol{\mu}) = & {1 \over 2} (\sum_{j=1}^m \alpha_j y_j \boldsymbol{x}_j^T) (\sum_{i=1}^m \alpha_i y_i \boldsymbol{x}_i) + \sum_{i=1}^m \alpha_i \\
& -\sum_{i=1}^m \alpha_i y_i (\sum_{j=1}^m \alpha_j y_j \boldsymbol{x}_j^T)\boldsymbol{x}_i +\sum_{i=1}^m(C - \alpha_i - \mu_i)\xi_i \\
& = \sum_{i=1}^m \alpha_i - {1 \over 2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}_j^T \boldsymbol{x}_i
\end{aligned}
\end{equation}
这就是原问题(6)的对偶问题：
\begin{equation}
\begin{aligned}
& \max_{\boldsymbol{\alpha}} && \sum_{i=1}^m \alpha_i -{1 \over 2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \boldsymbol{x}_j^T \boldsymbol{x}_i \\
&\text{s.t.} && \sum_{i=1}^m \alpha_i y_i =0, \\
& && 0 \leq \alpha_i \leq C,\forall i
\end{aligned}
\end{equation}
原问题(6)的KKT条件为：
\begin{equation}
\left\{
\begin{aligned}
& \alpha_i \ge 0,\mu_o \ge 0 \\
& y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b)-1+\xi_i \ge 0,\xi_i \ge 0 \\
& \alpha_i (y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b) -1 + \xi_i) = 0 \\
& \mu_i \xi_i = 0
\end{aligned}
\right.
\end{equation}
满足(8)和(10)的唯一向量即为原问题和对偶问题的最优解。将所解出的最优解\tilde{\alpha_i}带入\boldsymbol{w}即可得到最优超平面h(x) = \sum_{i=1}^m \tilde{\alpha}_i \boldsymbol{x}_i^T \boldsymbol{x}+\tilde{b}。
根据(8)中第三式，可以得到当\alpha_i = 0时，有\mu_i = C > 0（C不取0）， 因此根据(10)可以得到\xi_i=0，所以y_i(\boldsymbol{w}^T \boldsymbol{x}_i + b)-1 \ge 0，即该样本点正确分类，在正确分类内部，并且对最优超平面没有任何影响；
而当\alpha_i > 0时，有y_i(\boldsymbol{w}^T\boldsymbol{x}_i +b)= 1- \xi_i，即该样本是支持向量。
进一步的，若0 < \alpha_i < C，则\mu_i>0,\xi_i=0，该样本点在最大间隔边界上；
若\alpha_i = C，则\mu_i = 0，此时如果\xi_i = 0，则该样本点在最大间隔边界上；如果0 < \xi_i \leq 1，则该样本点在最大间隔内部；如果\xi_i > 1，则该样本点被错误分类。\
4、对偶问题求解
我们下面来求解对偶问题，即求解参数\alpha_i，显然这是一个凸二次规划问题，可以用二次规划的办法来求解，但该问题的规模正比于训练样本数，这会造成很大的开销。因此，我们尝试利用问题的特性来求解，SMO算法就是其中之一。
我们想利用交替迭代的思想，一次求解一个\alpha_i，固定其余的\alpha_j，但是根据(9)，有\sum_{i=1}^m \alpha_i y_i =0，如果一次只求解一个，则这一个\alpha_i就被固定住了，因此我们一次选取一对\alpha_i,\alpha_j，固定其余的\alpha_k，来进行迭代更新。
不妨假设我们选取的为\alpha_1,\alpha_2，记更新前的值为\alpha_1^{\text{old}},\alpha_2^{\text{old}}，更新后的值为\alpha_1^{\text{new}},\alpha_2^{\text{new}}，根据(9)的第二式，有
\begin{equation}
\alpha_1^{\text{old}}y_1+ \alpha_2^{\text{old}}y_2 = - \sum_{i=3}^m \alpha_i y_i = \alpha_1^{\text{new}}y_1+\alpha_2^{\text{new}}y_2
\end{equation}
由于固定了其余的\alpha_i,i \ge 3，并且为了方便，记c = - \sum_{i=3}^m \alpha_i y_i ,K_{ij} = \boldsymbol{x}_i^T \boldsymbol{x}_j^T （显然K_{ij}=K_{ji}），则对偶问题可以简化为：
\begin{equation} \nonumber
\begin{aligned}
\Phi(\alpha_1,\alpha_2)= & \alpha_1+\alpha_2 - {1 \over 2}\Big(\alpha_1^2 K_{11} + 2\alpha_1 \alpha_2 y_1 y_2 K_{12} + \alpha_2^2 K_{22} \\
&+ 2\alpha_1 y_1 \sum_{i=3}^m \alpha_i y_i \boldsymbol{x}_1^T \boldsymbol{x}_i +2 \alpha_2 y_2 \sum_{i=3}^m \alpha_i y_i \boldsymbol{x}_2^T \boldsymbol{x}_i +constant \Big) \\
\text{将}\alpha_1 = &{{c-\alpha_2 y_2}\over y_1}\text{带入} \\
\Phi(\alpha_2)= & -({1 \over 2}K_{11} + {1 \over 2}K_{22} - K_{12})\alpha_2^2 + ({{y_1-y_2} \over {y_1}}) \alpha_2 +cK_{11}y_2 \alpha_2 \\
& - cK_{12} {y_2}\alpha_2 - (\sum_{i=3}^m \alpha_i y_i x_i^T x_2 - \sum_{i=3}^m \alpha_i y_i x_i^T x_1 )y_2 \alpha_2 +constant \\
\text{记}v_1 = & \sum_{i=3}^m \alpha_i y_i x_i^T x_1, v_2 = \sum_{i=3}^m \alpha_i y_i x_i^T x_2 \\
\therefore v_1 = & f(x_1) - b - y_2 \alpha_2^{\text{old}}K_{21} - y_1 \alpha_1^{\text{old}} K_{11} \\
v_2 = & f(x_2) - b - y_2 \alpha_2^{\text{old}}K_{22} - y_1 \alpha_1^{\text{old}} K_{12} \\
\Phi'(\alpha_2)= & -(K_{11} + K_{22} - 2K_{12}) \alpha_2 -(v_2 -v_1)y_2 + 1-y_1y_2 \\
& - (y_1 \alpha_1^{\text{old}} + y_2 \alpha_2^{\text{old}})K_{12} y_2 + (y_1 \alpha_1^{\text{old}} + y_2 \alpha_2^{\text{old}})K_{11}y_2 \\
=& -(K_{11} + K_{22} - 2K_{12}) \alpha_2+f(x_1)y_2-f(x_2)y_2 \\
& + (K_{11}+K_{22}-2K{12})\alpha_2^{\text{old}}+1-y_1y_2 \\
\text{令}\Phi'(\alpha_2) = & 0,E_1 = f(x_1)-y_1, E_2 = f(x_2)-y_2,\eta=K_{11}+K_{22}-2K_{12} \\
\eta \alpha_2^{\text{new}} = & \eta \alpha_2^{\text{old}} + E_1 y_2 -E_2 y_2 +(y_1-y_2) y_2 + y_2 (y_2-y_1). \\
=& \eta \alpha_2^{\text{old}} + (E_1 -E_2) y_2 \\
\because K_{11}+ K_{22} & -2K_{12} = (\boldsymbol{x}_1 -\boldsymbol{x}_2)^2 \ge 0,\text{当且仅当}\boldsymbol{x}_1=\boldsymbol{x}_2\text{时，等号成立} \\
\therefore \alpha_2^\text{new} =& \alpha_2^\text{old} + {{E_1 - E_2} \over \eta}y_2,\text{此时关于$\alpha_2$取到极大值}
\end{aligned}
\end{equation}
但此时求解的是无约束的\alpha_i，由于0 \leq \alpha_i \leq C，并且根据\alpha_1 y_1+ \alpha_2 y_2 =c，我们可以得到：
\begin{equation}\nonumber
\left\{
\begin{aligned}
& y_1 = +1,y_2 =-1 \\
& y_1 = -1,y_2 =+1
\end{aligned}
\right. \Rightarrow \alpha_1 - \alpha_2 = k
\end{equation}
\begin{equation}\nonumber
\left\{
\begin{aligned}
& y_1 = +1,y_2 =+1 \\
& y_1 = -1,y_2 =-1
\end{aligned}
\right. \Rightarrow \alpha_1 + \alpha_2 = k
\end{equation}
如图所示：
因此，若y_1 \neq y_2，则定义\alpha_2^\text{new}的上界为H = \min(C,C-k)=\min(C,C-(\alpha_1^\text{old}-\alpha_2^\text{old}))，下界为L = \max(0,-k)=\max(0,\alpha_2^\text{old} - \alpha_1^\text{old})。
若y_1 = y_2，则定义\alpha_2^\text{new}的上界为H = \min(C,k)=\min(C,\alpha_1^\text{old}+\alpha_2^\text{old})，下界为L = \max(0,k-C)=\max(0,\alpha_2^\text{old} + \alpha_1^\text{old}-C)。
这样我们就得到了剪枝后的\alpha_2更新公式，
\begin{equation}
\alpha_2^{\text{new,clipped}}=
\left\{
\begin{aligned}
&L \quad \alpha_2^\text{new} \leq L \\
&\alpha_2^{\text{new}} \quad L \leq \alpha_2^{\text{new}} \leq H \\
&H \quad \alpha_2^{\text{new}} \ge H
\end{aligned}
\right.
\end{equation}
带入可得到\alpha_1^\text{new}
\begin{equation}
\alpha_1^\text{new} = \alpha_1^\text{old} +y_1y_2(\alpha_2^\text{old}-\alpha_2^\text{new,clipped})
\end{equation}
关于b的选取，根据(11)，当0<\alpha_i<C的时候，我们有
\begin{equation}
y_i(\boldsymbol{w}^T\boldsymbol{x}_i +b) = 1 - \xi_i = 1- 0 =0
\end{equation}
我们选取更鲁棒的做法：对所有S=\{i | 0<\alpha_i <C\}求取平均值，即：
\begin{equation}
b = {1 \over |S|} \sum_{s \in S} ({1\over y_s} - \sum_{i \in S} \alpha_i y_i \boldsymbol{x}_i^T \boldsymbol{x_s})
\end{equation}\
5、如何选取拉格朗日乘子对
下面的问题就在于如何选取这一对拉格朗日乘子\alpha_i,\alpha_j来进行更新，我们用外循环来选取第一个拉格朗日乘子\alpha_i，内循环来选取第二个拉格朗日乘子\alpha_j。
显然，我们希望选取的第一个\alpha_i要违反KKT条件（因为符合KKT条件的\alpha_i根本不需要更新），选取误差精度为tol，则当\alpha_i = 0时，有y_i f(x_i) -1 \ge 0 \Rightarrow y_i E_i \ge 0，违反KKT条件的判定准则为：y_i E_i < -\text{tol}；当0<\alpha_i<C时，有y_i f(x_i) = 1 \Rightarrow y_i E_i = 0， 违反KKT条件的判定准则为：y_i E_i < -\text{tol}或者y_i E_i > \text{tol}；当\alpha_i = C时，有y_i f(x_i) -1 = -\xi_i \leq 0 \Rightarrow y_i E_i \leq 0 ， 违反KKT条件的判定准则为：y_i E_i > \text{tol}。
合并可写成：
\begin{equation}
\left\{
\begin{aligned}
& y_i E_i < -\text{tol} && \quad \alpha_i < C \\
& y_i E_i > \text{tol} &&\quad \alpha_i >0
\end{aligned}
\right.
\end{equation}
又由于边界点（即\alpha_i =0或\alpha_i=C的点）容易保持在边界，而不在边界的样本点容易受到其他样本点的优化的影响，因此我们选择先遍历非边界点集，寻找违反KKT条件的点，后遍历整个样本点集来寻找违反KKT条件的点。
对于第二个\alpha_j，我们考虑一种启发式的选择，直观的感觉是迭代的步长越大，就越能够快速的到达KKT点，然而由于\eta计算较为复杂，因此我们直接考虑分子E_1 -E_2，即选取最大化E_1-E_2的样本点作为\alpha_i。\
6、利用一阶信息
我们将对偶问题(10)写成矩阵的形式：
\begin{equation}
\begin{aligned}
&\min_{\boldsymbol{\alpha}} &&f(\boldsymbol{\alpha}) = {1 \over 2} \boldsymbol{\alpha}^T Q \boldsymbol{\alpha} - \boldsymbol{e}^T \boldsymbol{\alpha} \\
&\text{s.t.} && 0 \leq \boldsymbol{\alpha} \leq C \\
& && \boldsymbol{y}^T \boldsymbol{\alpha} = 0
\end{aligned}
\end{equation}
其中Q = \boldsymbol{y} \boldsymbol{y}^T .* K，K为核矩阵，\boldsymbol{e}为m\times 1的全1向量。
我们一次选择两个拉格朗日乘子\alpha_i,\alpha_j，记下标集为B = \{i,j\}。并且定义\boldsymbol{\alpha}^{k+1} = \boldsymbol{\alpha}^k +\boldsymbol{d}，其中\boldsymbol{d}^T:=[\boldsymbol{d}_B^T,0_N^T]=[0,\dots,d_i,\dots,d_j,\dots,0]，利用一阶条件，有：
\begin{equation}
\begin{aligned}
f(\boldsymbol{\alpha}^{k+1}) &= f(\boldsymbol{\alpha}^k)+\nabla f(\boldsymbol{\alpha}^k)^T \boldsymbol{d} \\
&=f(\boldsymbol{\alpha}^k) + \nabla f(\boldsymbol{\alpha}^k)_B^T \boldsymbol{d}_B
\end{aligned}
\end{equation}
显然\boldsymbol{d}_B是有限长的（若无限长则目标函数f(\boldsymbol{\alpha}^{k+1})的值可以达到无穷），因此不妨给定-\ell \leq d_t \leq \ell,t\in B；进一步的，若\alpha_t^k =0，更新值d_t \ge 0，若\alpha_t^k = C，更新值d_t \leq 0；而且，根据先后更新的条件(22)，有\boldsymbol{y}^T\boldsymbol{\alpha}^k = \boldsymbol{y}^T (\boldsymbol{\alpha}^K+\boldsymbol{d}_B)，化简可以得到\boldsymbol{y}^T \boldsymbol{d}_B =0。
对于每一次更新，我们都希望尽可能下降的更多，即求解如下优化问题：
\begin{equation}
\begin{aligned}
Sub(B):=\min_{\boldsymbol{d}_B}&\quad &&\nabla f(\boldsymbol{\alpha}^k)_B \boldsymbol{d}_B \\
\text{subjectto}& && \boldsymbol{y}_B^T \boldsymbol{d}_B = 0 \\
& && d_t \ge 0,\text{if}\alpha_t =0,t \in B \\
& && d_t \leq 0,\text{if}\alpha_t=C,t \in B \\
& && -\ell \leq d_t \leq \ell,t \in B
\end{aligned}
\end{equation}
我们用\hat{d}_i = y_i d_i,\hat{d}_j = y_jd_j来代替(20)中的d_i,d_j，则目标函数可写成
\begin{equation}
\begin{aligned}
(\nabla f(\boldsymbol{\alpha}^k)_i d_i + \nabla f(\boldsymbol{\alpha}^k)_j d_j) &= (y_i \nabla f(\boldsymbol{\alpha}^k)_i \hat{d}_i +y_j \nabla f(\boldsymbol{\alpha}^k)_j \hat{d}_j) \\
&=(- \nabla f(\boldsymbol{\alpha}^k)_i + \nabla f(\boldsymbol{\alpha}^k)_j) \hat{d}_j
\end{aligned}
\end{equation}
显然d_i=d_j=0是问题(20)的可行解。因此(21)的最小值要么是0要么是一个负数。若-y_i \nabla f(\boldsymbol{\alpha}^k)_i > -y_j \nabla f(\boldsymbol{\alpha}^k)_j，根据\hat{d}_i+\hat{d}_j=0，(21)为负值只有\hat{d}_j<0,\hat{d}_i >0的时候。
因此有y_j d_j <0,y_i d_i >0，根据(20)可以得到
\begin{equation}
\begin{aligned}
y_i d_i > 0 \Rightarrow
\left\{
\begin{aligned}
&y_i =+1,d_i >0 \Rightarrow y_i =+1,\alpha_t < C \\
&y_i =-1,d_i <0 \Rightarrow y_i =-1,\alpha_t > 0
\end{aligned}
\right.
\end{aligned}
\end{equation}
显然(22)最后的”\Rightarrow“并非充要条件，仅仅是必要条件，我们定义集合I_0 = \{i:0<\alpha_i <C\};I_1 = \{i:y_i=1,\alpha_i =0\};I_2 = \{i:y_i = -1,\alpha_i =C\};，令\eta_1 = \max\{-y_i \nabla f(\boldsymbol{\alpha}^k)_i | i \in I_0 \cup I_1 \cup I_2 \}。类似的，可以推出
\begin{equation}
\begin{aligned}
y_j d_j < 0 \Rightarrow
\left\{
\begin{aligned}
&y_i =+1,d_j <0 \Rightarrow y_i =+1,\alpha_t > 0 \\
&y_i =-1,d_j >0 \Rightarrow y_i =-1,\alpha_t < C
\end{aligned}
\right.
\end{aligned}
\end{equation}
类似的定义集合I_3 = \{i:y_i =-1,\alpha_i = 0\};I_4 = \{i:y_i = 1,\alpha_i =C\}，令\eta_2 = \min\{-y_j \nabla f(\boldsymbol{\alpha}^k)_j | j \in I_0 \cup I_3 \cup I_4 \}。
若\eta_1 \leq \eta_2，则不存在d_i,d_j使得目标函数值为负值，即\min Sub(B) =0；若\eta_1 > \eta_2，则存在d_i,d_j使得目标函数可以继续下降，并且根据(21)可以看出，当\{i,j\}满足
\begin{equation}\nonumber
\left\{
\begin{aligned}
&-y_i \nabla f(\boldsymbol{\alpha}^k)_i = {\eta_1} ={ \max\{-y_i \nabla f(\boldsymbol{\alpha}^k)_i | i \in I_0 \cup I_1 \cup I_2 \}} \\
&-y_j \nabla f(\boldsymbol{\alpha}^k)_j = {\eta_2} ={ \min\{-y_j \nabla f(\boldsymbol{\alpha}^k)_j | j \in I_0 \cup I_3 \cup I_4 \}}
\end{aligned}
\right.
\end{equation}
的时候，下降的最快，此时有\hat{d_j}=-\ell,\hat{d_i} = \ell。
类似的，若-y_i \nabla f(\boldsymbol{\alpha}^k)_i < -y_j \nabla f(\boldsymbol{\alpha}^k)_j，根据\hat{d_i}+\hat{d_j} =0，则为使(21)为负值，则必须有\hat{d_j} >0,\hat{d_i} <0。显然这是与上述状况是对称的，这里不再复述。
有趣的是，根据KKT(11)条件，我们有：
\begin{equation}
\left\{
\begin{aligned}
& y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b - y_i ) \ge 0 && \quad \alpha_i = 0 \\
& y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b - y_i ) =0 && \quad 0<\alpha_i<C \\
& y_i(\boldsymbol{w}^T\boldsymbol{x}_i + b - y_i ) \leq 0 && \quad \alpha_i = C
\end{aligned}
\right.
\end{equation}
由(18)可知\nabla f(\boldsymbol{\alpha}) = {y_i\boldsymbol{w}^T \boldsymbol{x}_i -1} ，再根据先前定义的集合I_0,I_1,I_2,I_3,I_4，可将(24)化简为：
\begin{equation}\nonumber
b \ge -y_i \nabla f(\boldsymbol{\alpha})_i,\forall i \in I_0 \cup I_1 \cup I_2;b \leq -y_j \nabla f(\boldsymbol{\alpha})_j,\forall j \in I_0 \cup I_3 \cup I_4;
\end{equation}
即若
\begin{equation}\nonumber
\begin{aligned}
&b_{up} = \max \{-y_i \nabla f(\boldsymbol{\alpha})_i | i \in I_0 \cup I_1 \cup I_2 \} \\
&b_{low}= \min \{-y_j \nabla f(\boldsymbol{\alpha})_j | j \in I_0 \cup I_3 \cup I_4 \}
\end{aligned}
\end{equation}
则只需要b_{low} \leq b_{up}成立，则\exists b满足最优性条件，根据误差精度，可写为b_{low} \leq b_{up} + 2\text{tol}。
可以发现b_{up},b_{low}和我们之前的\eta_1,\eta_2是一致的。因此我们只需要利用b来进行操作。
显然b_{up} < 1,b_{low}>-1，因此我们初始化设置b_{up}=1,b_{low}=-1。然后执行以下步骤：
1、循环遍历整个样本集，更新b_{up}和b_{low}，如果b_{up} < b_{low}则将b_{up},b_{low}对应的“样本对”作为\alpha_i,\alpha_j进行更新。如果所有的都满足条件，则退出，否则执行2。
2、循环遍历非边界支持向量集（即0<\alpha_i <C），更新b_{up}和b_{low}，如果b_{up} < b_{low}则将b_{up},b_{low}对应的样本对作为\alpha_i,\alpha_j进行更新。返回1。
7、利用二阶信息
将目标函数f( \boldsymbol{\alpha})泰勒展开，可以得到：
\begin{equation}\nonumber
\begin{aligned}
f(\boldsymbol{\alpha}^k+\boldsymbol{d}) - f(\boldsymbol{\alpha}^k) &= \nabla f(\boldsymbol{\alpha}^k)^{T}\boldsymbol{d} + {1 \over 2}\boldsymbol{d}^T \nabla^2 f(\boldsymbol{\alpha^k}) \boldsymbol{d} \\
& = \nabla f(\boldsymbol{\alpha}^k)_B^T \boldsymbol{d}_B + {1 \over 2}\boldsymbol{d}_B^T \nabla^2 f(\boldsymbol{\alpha}^k)_{BB} \boldsymbol{d}_B
\end{aligned}
\end{equation}
同样的，为了使的下降的最快，我们尝试求解如下优化问题：
\begin{equation}\nonumber
\begin{aligned}
Sub(B):=\min_{\boldsymbol{d}_B}& \quad && {1 \over 2}\boldsymbol{d}_B^T\nabla^2 f(\boldsymbol{\alpha}^k)_{BB} d_B + \nabla f(\boldsymbol{\alpha}^k)_B^T\boldsymbol{d}_B \\
\text{subjectto}& &&\boldsymbol{y}_B^T \boldsymbol{d}_B = 0 \\
& && d_t \ge 0,\text{if}\alpha_t^k =0,t \in B \\
& && d_t \leq 0,\text{if}\alpha_t^k=C,t \in B
\end{aligned}
\end{equation}
由于\nabla^2 f(\boldsymbol{\alpha}^k)=Q的半正定性，因此Sub(B)有极小值，并非会达到无穷，因此我们去除了-1 \leq d_t \leq 1的约束条件。
类似的，使用二阶条件来选择乘子的步骤如下：\
1、先选择乘子\alpha_i，满足
\begin{equation}\nonumber
i \in \arg\max_t \{-y_t \nabla f(\boldsymbol{\alpha}^k)_t | t\in I_0 \cap I_1 \cap I_2 \}
\end{equation}
2、考虑优化问题Sub(B)，并选择乘子\alpha_j，满足
\begin{equation}\nonumber
j \in \arg\min_t\{Sub(\{i,t\}) | t \in I_0 \cap I_3 \cap I_4,-y_t \nabla f(\boldsymbol{\alpha}^k)_t < -y_i \nabla f(\boldsymbol{\alpha}^k)_i \}
\end{equation}
可以求得目标函数Sub(B)在\hat{d_j} = - {b_{ij} \over a_{ik}}处取的最优值，最优值为
\begin{equation}\nonumber
objvalue = - {b_{ij}^2 \over 2a_{ij}},a_{ij}=K_{ii}+K_{jj} -2K_{ij},b_{ij} = -y_i \nabla f(\boldsymbol{\alpha}^k)_i +y_j \nabla f(\boldsymbol{\alpha}^k)_j
\end{equation}
因此j简化为
\begin{equation}\nonumber
j \in \arg\max_j\{- {b_{ij}^2 \over 2a_{ij}} | j \in I_0 \cap I_3 \cap I_4,-y_j \nabla f(\boldsymbol{\alpha}^k)_j < -y_i \nabla f(\boldsymbol{\alpha}^k)_i \}
\end{equation}
3、选择B=\{i,j\}作为更新的拉格朗日乘子对。\
8、更新偏移量b
此外，我们每一次更新两个乘子之后，需要更新偏移量b： \
1、若0<\alpha_1^\text{new}<C，由KKT条件(11)，可以得到：
\begin{equation}\nonumber
b_1^\text{new} = -E_1 - y_1 K_{11}(\alpha_1^\text{new} - \alpha_1^\text{old})-y_2K_{21}(\alpha_2^\text{new}-\alpha_2^\text{old}) + b^{old}
\end{equation}
2、若0<\alpha_2^\text{new}<C，由KKT条件(11)，可以得到：
\begin{equation}\nonumber
b_2^\text{new} = -E_2 - y_1 K_{12}(\alpha_1^\text{new} - \alpha_1^\text{old})-y_2K_{22}(\alpha_2^\text{new}-\alpha_2^\text{old}) + b^{old}
\end{equation}
3、若同时满足0<\alpha_i^\text{new}<C，则b_1^\text{new} = b_2^\text{new}。 \
4、若同时不满足0<\alpha_i^\text{new}<C，则b_1^\text{new}和b_2^\text{new}以及它们之间的数都满足KKT条件，可以取b = (1/2)(b_1^\text{new}+b_2^\text{new})。\
9、核函数
我们已经知道，升维可以将原始空间中线性不可分的样本转变为线性可分，即将x映射到更高维的特征空间（x \rightarrow \phi(x)）。由于训练集样本个数有限，因此利用高斯核函数等较高维的映射函数会保证样本线性可分性（n个样本升至n-1维就能保证线性可分）。
令\phi(\boldsymbol{x})表示将\boldsymbol{x}映射后的特征向量。因此所对应的最优超平面模型为：
\begin{equation}
f(\boldsymbol{x}) = \boldsymbol{w}^T \phi(\boldsymbol{x})+b
\end{equation}
类似的，我们可以得到如下原问题：
\begin{equation}
\begin{aligned}
& \min_{\boldsymbol{w},b} && {1 \over 2}||\boldsymbol{w}||^2 + C \sum_{i=1}^m \xi_i \\
&\text{s.t.} && y_i(\boldsymbol{w}^T\phi(\boldsymbol{x}_i) + b) \ge 1-\xi_i,\xi_i \ge 0,\forall i
\end{aligned}
\end{equation}
其对偶问题为：
\begin{equation}
\begin{aligned}
& \max_{\boldsymbol{\alpha}} && \sum_{i=1}^m \alpha_i -{1 \over 2} \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j y_i y_j \phi(\boldsymbol{x}_j)^T \phi(\boldsymbol{x}_i) \\
&\text{s.t.} && \sum_{i=1}^m \alpha_i y_i =0, \\
& && 0 \leq \alpha_i \leq C,\forall i
\end{aligned}
\end{equation}
显然我们仅需要计算\phi(\boldsymbol{x_i})^T\phi(\boldsymbol{x_j})，由于\phi(\boldsymbol{x_i})的维数很高，甚至可能是无穷维的，因此计算这个高维向量的内积是十分困难的，因此我们直接建立如下函数：
\begin{equation}
\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j) = \langle \phi(\boldsymbol{x}_i),\phi(\boldsymbol{x}_j) \rangle = \phi(\boldsymbol{x}_i)^T \phi(\boldsymbol{x}_j)
\end{equation}
因此核函数是将两个低维原始样本映射为其对应的高维向量的内积。则该问题最优解可写为：
\begin{equation}
\begin{aligned}
f(\boldsymbol{x}) &= \boldsymbol{w}^T \phi(\boldsymbol{x}) + b \\
& = \sum_{i=1}^m \alpha_i y_i \phi(\boldsymbol{x}_1)^T \phi(\boldsymbol{x}) + b \\
& = \sum_{i=1}^m \alpha_i y_i \kappa(\boldsymbol{x},\boldsymbol{x_i}) + b
\end{aligned}
\end{equation}
实际上，内积是几何意义是两个点之间的相似程度，我们利用核函数\kappa只是希望通过另一种方式来定义相似度。\
10、再生核希尔伯特空间
每一个核函数都相对应的定义了一个称为再生核希尔伯特空间(Reproducing Kernel Hilbert Space,RKHS)的特征空间。RKHS是一个函数空间。
我们给出RKHS的定义：
定义在有界域X上的泛函组成的希尔伯特空间H，如果对任意x \in X，定义L_x:f \rightarrow f(x),\forall f \in H是有界线性泛函，即（|L_x(f)|:=|f(x)| \leq M||f||_{H},\forall f \in H），这称\mathcal{H}为再生核希尔伯特空间。
根据里斯表示定理(Riesz representation theorem)，对于任意一个再生核希尔伯特空间H，都存在唯一的对称，正定函数K(x,y)与之对应，并满足如下两条性质：
\begin{equation} \nonumber
\begin{aligned}
(1) \quad &K(\cdot,x) \in H,\forall x \\
(2) \quad &f(x) = \langle f(\cdot),K(\cdot,x) \rangle_H,\forall f \in H
\end{aligned}
\end{equation}
其中\langle \cdot,\cdot \rangle_H表示H中的内积，K(x,y)为再生核函数，K(\cdot,y): x \rightarrow K(x,y)。
因此我们取f(x)=K(x,y)，有f(x)=K(x,y) = \langle K(\cdot,y),K(\cdot,x) \rangle
Moore-Aronszajn定理：令K:\mathcal{X} \times \mathcal{X} \rightarrow R是对称，正定核函数，则存在唯一的RKHSH \subset R^{\mathcal{X}}与之对应（R^{\mathcal{X}}表示所有将\mathcal{X}映射到R的函数的集合）。
证明：
定义函数空间H_0是由\{K(x,\cdot):x \in \mathcal{X}\}线性组合所组成的空间，并且定义H_0上的内积为：
\begin{equation}\nonumber
\Big\langle \sum_{i=1}^n a_i K(x_i,\cdot),\sum_{j=1}^m b_j K(y_j,\cdot) \Big\rangle_{H_0} = \sum_{i=1}^n \sum_{j=1}^m a_i b_j K(x_i,y_j)
\end{equation}
由于K的对称性和正定性，因此内积也是对称的和非负的。令H为H_0关于该内积的完备空间，因此H是由如下函数组成的集合：
\begin{equation}\nonumber
f(x) = \sum_{i=1}^\infty a_i K(x_i,x)
\end{equation}
其中\sum_{i=1}^\infty a_i^2 K(x_i,x_i) < \infty，该收敛性可由Cauchy–Schwarz不等式证明。
我们验证其再生性(2)：
\begin{equation}\nonumber
\langle f(y),K(y,x) \rangle = \Big\langle \sum_{i=1}^\infty a_iK(x_i,y),K(y,x) \Big\rangle = \sum_{i=1}^\infty a_iK(x_i,x)=f(x)
\end{equation}
为了证明其唯一性，假设存在另一个RKHSG，则对\forall x,y \in \mathcal{X}，有：
\begin{equation}\nonumber
\langle K(x,\cdot),K(y,\cdot) \rangle_H =K(x,y) = \langle K(x,\cdot),K(y,\cdot) \rangle_G
\end{equation}
因此，\langle \cdot,\cdot \rangle_H和\langle \cdot,\cdot \rangle_G都是函数组\{K(x,\cdot):x \in \mathcal{X}\}线性张成的空间。又因为G是完备的并且H_0 \subset G因此G包含H_0的完备集H。
令f \in G,由于H是G中的封闭子集，我们有f = f_{H} + f_{H^{\perp}}，其中f_{H} \in H,f_{H^{\perp}} \in H^{\perp}，则
\begin{equation}\nonumber
f(x) = \langle K(x,\cdot),f \rangle = \langle K(x,\cdot),f_{H} \rangle =f_{H}(x)
\end{equation}}
这表明\forall f \in G,f \in H，因此H包含G，所以有H=G成立。
因此对于给定的核函数，只有唯一的RKHS与之对应。\
11、高斯核函数
首先，我们要了解高斯核函数是将原始模型映射到无限维空间来运算内积进行求解的。
\begin{equation}\nonumber
\begin{aligned}
K(x,y) &= \exp(-{{||x-y||^2} \over {2\sigma^2}}) = \exp(-{{x^2} \over {2\sigma^2}})\exp(-{{y^2} \over {2\sigma^2}})\exp({{2x^Ty} \over {2\sigma^2}}) \\
&=\exp(-{{x^2} \over {2\sigma^2}})\exp(-{{y^2} \over {2\sigma^2}})\Big(\sum_{i=0}^\infty {({{x^Ty} \over {\sigma^2}})^i \over {i!}}\Big) \quad \text{Taylor展开} \\
&=\sum_{i=1}^\infty \exp(-x^2)\exp(-y^2){{1} \over {\sigma^{i} \sqrt{i!}}}{{1} \over {\sigma^{i} \sqrt{i!}}}(x^i)^T y^i \\
&= \phi^T(x)\phi(y)
\end{aligned}
\end{equation}
因此高斯核函数时映射到无穷维的变换，其中x到高维空间的映射为
\begin{equation}\nonumber
\phi(x) = \exp(-x^2)\cdot ({{1}\over{\sigma^1 \sqrt{1!}}}x,{{1}\over{\sigma^2 \sqrt{2!}}}x^2,\dots)
\end{equation}
而SVM问题的最优解可表示为:
\begin{equation}\nonumber
h^{\star}(x) = w^T \phi(x) + b
\end{equation}
若\sigma非常小，则以为着x的高次项系数非常大，或者说前面很多项非常大（因为a^n < n!(n\rightarrow \infty)），这会使得模型非常复杂，则很容易出现过拟合的现象。而如果\sigma非常大，可能会使得x的低次项系数非常小，或者说拟合次数不够，则容易出现欠拟合的现象。\
12、表示定理
令H为核函数\kappa对应的再生核希尔伯特空间，||h||_{H}表示H空间中关于h的范数，对于任意单调递增函数\Omega:[0,\infty] \rightarrow R和任意非负损失函数\ell : R^m \rightarrow [0,\infty]，优化问题
\begin{equation}\nonumber
\min_{h \in H} F(h) = \Omega(||h||_H) + \ell(h(x_1),h(x_2),\dots,h(x_m))
\end{equation}
的解总可以写为
\begin{equation}\nonumber
h^{\star}(x) = \sum_{i=1}^m \alpha_i \kappa(x_i,x)
\end{equation}
证明：
定义映射：\phi:\mathcal{X} \rightarrow R^{\mathcal{X}},\phi(x)=\kappa(\cdot,x)，又因为\kappa是核函数，所以有：
\begin{equation}\nonumber
\phi(x)(y) = \kappa(y,x) = \langle \phi(y),\phi(x) \rangle
\end{equation}
其中\langle \cdot,\cdot \rangle是H上的内积。
对于给定的样本x_1,x_2,\dots,x_m，可以将任意f \in H正交分解成两部分，一部分位于集合\{\phi(x_1),\dots,\phi(x_m)\}张成的空间内，另一部分属于其正交补：
\begin{equation}\nonumber
h = \sum_{i=1}^m \alpha_i \phi(x_i) + v
\end{equation}
其中\langle \phi(x_i),v \rangle =0对于所有的i成立。
根据再生性，有
\begin{equation}\nonumber
\begin{aligned}
h(x_j) &= \langle h(\cdot),\kappa(\cdot,x_j) \rangle = \langle \sum_{i=1}^m \alpha_i \phi(x_i) +v ,\phi(x_j) \rangle \\
&=\sum_{i=1}^m \alpha_i \langle \phi(x_i),\phi(x_j) \rangle
\end{aligned}
\end{equation}
因此，经验风险函数与v无关。又因为v与函数集合张成的空间垂直，我们有：
\begin{equation}\nonumber
\begin{aligned}
\Omega(||f||) &= \Omega\Big(||\sum_{i=1}^m \alpha_i \phi(x_i) +v ||^2 \Big ) \\
&= \Omega\Big(||\sum_{i=1}^m \alpha_i \phi(x_i)||^2 +||v||^2 \Big) \\
& \ge \Omega\Big(||\sum_{i=1}^m \alpha_i \phi(x_i)||^2 \Big)
\end{aligned}
\end{equation}
因此，当v=0时等号成立，此时得到最优解h^{\star}(x)。
可以看出，就算函数g仅仅要求单调非减，也可以将最优解写成该形式。
而对于SVM问题而言，由于偏移项的存在，而我们的正则化项是不会正则化偏移项b的，所以我们令优化模型中的||w||=||h||，因此，根据SVM的模型：
\begin{equation}\nonumber
\min_{w,b}{1 \over 2} ||w||^2 + C\sum_{i=1}^m \ell_{hinge}(1-y_i(w^Tx_i + b))
\end{equation}
可知w的最优解可表示为w = \sum_{i=1}^m \alpha_i \phi(x_i)，因此原问题的最优解为
\begin{equation}\nonumber
f(x) =\sum_{i=1}^m \alpha_i \kappa(x_i,x) + b
\end{equation}
13、支持向量回归
我们可以用类似的想法导出支持向量回归，传统的回归模型通常直接基于输出f(\boldsymbol{x})与真实输出y之间的差别来计算损失，当且仅当f(\boldsymbol{x})与y完全相同时，损失才为零。因此SVR\textb考虑我们能容忍的f(\boldsymbol{x})与y的偏差}，假设能容忍最多为\epsilon的偏差，即仅当|y- f(x)| > \epsilon时才计算损失。
因此SVR模型可写为如下优化问题：
\begin{equation}
\min_{\boldsymbol{w},b}{1 \over 2} ||w||^2 + C \sum_{i=1}^m \ell_{\epsilon}(f(\boldsymbol{x_i} -y_i)
\end{equation}
其中C为正则化参数，\ell_{\epsilon}为\epsilon-不敏感损失函数
\begin{equation}
\ell_{\epsilon}(z) =
\left\{
\begin{aligned}
&0 \quad &&\text{if}|z| \leq \epsilon \\
&|z| - \epsilon \quad &&\text{otherwise}
\end{aligned}
\right. = \max(0,|f(\boldsymbol{x}_i)-y_i| - \epsilon)
\end{equation}
我们可以将间隔带两侧的松弛程度分别进行控制，即引入松弛变量\xi_i，可将式(30)重写为：
\begin{equation}
\begin{aligned}
&\min_{\boldsymbol{w},b,\boldsymbol{\xi}} &&{1 \over 2} ||w||^2 + C \sum_{i=1}^m \xi_i \\
& \text{s.t.} &&\xi_i \ge |y_i -f(\boldsymbol{x}_i)| - \epsilon \\
& && \xi_i \ge 0,\forall i
\end{aligned}
\end{equation}
则优化问题(32)的拉格朗日函数为：
\begin{equation} \nonumber
\begin{aligned}
L(\boldsymbol{w},b,\boldsymbol{\xi};\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}},\boldsymbol{\mu}) =& {1 \over 2} ||w||^2 + C \sum_{i=1}^m \xi_i - \sum_{i=1}^m \alpha_i (\epsilon + \xi_i - y_i + f(\boldsymbol{x}_i)) \\
& - \sum_{i=1}^m \hat{\alpha_i}(\epsilon + \xi_i + y_i -f(x_i)) - \sum_{i=1}^m \mu_i \xi_i \\
= &{1 \over 2}||w||^2 + \sum_{i=1}^m (\hat{\alpha_i} -\alpha)f(\boldsymbol{x}_i) + \sum_{i=1}^m(C-\alpha_i - \hat{\alpha_i} - \mu_i ) \xi_i \\
&- \sum_{i=1}^m (\hat{\alpha_i} -\alpha_i)y_i - \sum_{i=1}^m (\hat{\alpha_i} + \alpha_i) \epsilon
\end{aligned}
\end{equation}
其中，对偶变量均满足约束\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}},\boldsymbol{\mu} \ge 0，再令L(\boldsymbol{w},b,\boldsymbol{\xi};\boldsymbol{\alpha},\boldsymbol{\hat{\alpha}},\boldsymbol{\mu})对\boldsymbol{w},b,\boldsymbol{\xi}的偏导为0可得
\begin{equation}
\begin{aligned}
& \boldsymbol{w} = \sum_{i=1}^m (\hat{\alpha_i} -\alpha_i)\boldsymbol{x}_i \\
&0 = \sum_{i=1}^m (\hat{\alpha_i} - \alpha_i ) \\
&C = \alpha_i + \hat{\alpha_i} + \mu_i,\forall i
\end{aligned}
\end{equation}
将(33)式中的\mu_i看作松弛变量，再带入拉格朗日函数，可以得到SVR的对偶问题：
\begin{equation}
\begin{aligned}
&\max_{\boldsymbol{\alpha},\hat{\boldsymbol{\alpha}}} &&\sum_{i=1}^m [y_i (\hat{\alpha_i} -\alpha_i)-\epsilon(\hat{\alpha} +\alpha)] \\
& &&- {1 \over 2} \sum_{i=1}^m \sum_{j=1}^m (\hat{\alpha_i} -\alpha_i)(\hat{\alpha_j} -\alpha_j) \boldsymbol{x}_i^T \boldsymbol{x}_j \\
&\text{s.t.} && \sum_{i=1}^m (\hat{\alpha_i} -\alpha_i ) =0 \\
& && \alpha_i,\hat{\alpha_i} \ge 0 \\
& && \alpha_i + \hat{\alpha_i} \leq C,\forall i
\end{aligned}
\end{equation}
其对应的KKT条件为：
\begin{equation}
\left\{
\begin{aligned}
&\xi_i \ge 0,y_i -f(\boldsymbol{x}_i) -\epsilon - \xi_i \leq 0,f(\boldsymbol{x}_i)-y_i -\epsilon - \xi_i \leq 0 \\
& \alpha_i (y_i - f(\boldsymbol{x}_i) -\epsilon - \xi_i ) =0 \\
& \hat{\alpha_i} (f(\boldsymbol{x}_i)-y_i -\epsilon - \xi_i ) =0 \\
& (C - \alpha_i -\hat{\alpha_i}) \xi_i =0,\forall i
\end{aligned}
\right.
\end{equation}
可以看出，当y_i - f(\boldsymbol{x}_i) < \epsilon并且f(\boldsymbol{x}_i)-y_i < \epsilon时，即|y_i -f(\boldsymbol{x}_i)| < \epsilon时，有\alpha_i = \hat{\alpha_j} =0,\xi_i =0;当y_i - f(\boldsymbol{x}_i) > \epsilon或者f(\boldsymbol{x}_i)-y_i > \epsilon时，即|y_i -f(\boldsymbol{x}_i)| > \epsilon时，有\alpha_i ,\hat{\alpha_i} 一个为0一个为C，并且\xi_i > 0；当f(\boldsymbol{x_i})-y_i = \epsilon或者y_i - f(\boldsymbol{x_i})= \epsilon时，即|y_i -f(\boldsymbol{x_i})| = \epsilon时，则可能有\alpha_i = \hat{\alpha_j} =0,\xi_i =0，也可能\alpha_i,\hat{\alpha_i}=0一个为0一个不为0，\xi_i =0。
将(33)带入可得到SVR的解为：
\begin{equation}
f(\boldsymbol{x}) = \sum_{i=1}^m (\hat{\alpha_i} -\alpha_i )\boldsymbol{x}_i^T\boldsymbol{x} + b
\end{equation}
由于\alpha_i,\hat{\alpha_i}不可能同时非零，因此支持向量为间隔带外的点，以及一部分间隔带上的点，即其解仍然保持了稀疏性。
对于b的求解，显然，当 0 < \alpha_i <C时，有 \xi_i =0，此时有b = y_i - \epsilon - \sum_{j=1}^m (\hat{\alpha_j} -\alpha_j) \boldsymbol{x}_j^T \boldsymbol{x}_i；当0 < \hat{\alpha_i} <C时，仍然有\xi_i =0，此时b = y_i + \epsilon - \sum_{j=1}^m (\hat{\alpha_j} -\alpha_j) \boldsymbol{x}_j^T \boldsymbol{x}_i。实际中，我们选取所有这些样本点求出的b的均值。
而应用核函数时，类似的，可表示为：
\begin{equation}
f(\boldsymbol{x}) = \sum_{i=1}^m (\hat{\alpha_i} - \alpha_i ) \kappa(\boldsymbol{x},\boldsymbol{x}_i) + b
\end{equation}\
14、用SVM输出概率
如果我们仍然想像逻辑回归那样输出分类的概率，我们需要做一些推广。我们用sigmoid-fitting的方法，将SVM的输出结果进行后处理，转换成后验概率。
\begin{equation}
P(y=1|f) = {1 \over {1+ \exp(Af+B)}}
\end{equation}
因此我们考虑极大似然问题，得到如下优化问题：
\begin{equation}
\max_{z=(A,B)} \prod_{i=1}^m p(y=y_i | \boldsymbol{x}_i)
\end{equation}
其中，
\begin{equation}
\begin{aligned}
& p(y =1 | x_i ) = {1 \over {1+ \exp(Af(\boldsymbol{x}_i)+B)}} \\
& p(y =-1 | x_i ) = 1 - {1 \over {1+ \exp(Af(\boldsymbol{x}_i)+B)}}
\end{aligned}
\end{equation}
我们定义t_i:
\begin{equation}\nonumber
t_i = {{y_i + 1} \over 2}
\end{equation}
因此我们可以将(40)合并成：
\begin{equation}
p(y = y_i | x_i) = t_i p( y=1|x_i) + (1-t_i) (1-p(y=1|x_i))
\end{equation}
对原问题(39)取对数可以得到如下问题：
\begin{equation}
\max_{z=(A,B)} \sum_{i=1}^m[t_i \log(p(y=1|x_i) + (1-t_i) \log(1-p(y=1|x_i)) ]
\end{equation}
为了避免过拟合，我们可以添加A的正则化项，但是这样会增加一个正则化参数\lambda。另一种简单的方法就是外样本数据，即增加一些高斯分布的噪声数据，可是这也会增加一个*未知量（方差）。由于(42)也可以看做拟合模型p_i与实际训练样本分布t_i的差异情况，即KL散度，也称相对熵，显然我们不太希望模型分布过度拟合训练样本的分布，因此我们通过修改训练样本的概率即t_i来增加噪声，即当y_i =1 时，取
\begin{equation}
t_{+} = {{N_{+} + 1} \over {N_{+} + 2}}
\end{equation}
当y_i = -1时，取
\begin{equation}
t_{-} = {1 \over {N_{-} +2 }}
\end{equation}
并且，在实际计算的时候，会遇到\log和\exp极易溢出的问题：\
1、如果Af_i + B为正且较大，那么\exp(Af_i + B) \rightarrow \infty，此时p_i趋近于0，则\log(p_i) \rightarrow \infty。 \
2、如果Af_i + B为负且较小，那么\exp(Af_i + B) \rightarrow 0，此时p_i趋近于1，则\log(1-p_i) \rightarrow \infty。\
因此我们对(42)作出一些变换：
\begin{equation}
\begin{aligned}
\ell&=-(t_i \log(p_i) + (1-t_i) \log(1- p_i)) && \\
&=(t_i - 1) (Af_i + B) + log(1+\exp(Af_i + B)) \quad &&(Af_i + B \leq 0) \\
&=t_i(Af_i + B) + \log(1+\exp(-Af_i -B)) \quad && (Af_i + B > 0) \\
\end{aligned}
\end{equation}\
15、关于相对熵和先验分布
若t为某一个样本真实概率分布，p为该样本的估计概率分布，则相对熵熵为：
\begin{equation}
KL(t \,||\, p) =\sum_{k=1}^N t_{k} \log({1 \over p_k}) - \sum_{k=1}^N t_{k} \log({1 \over t_k}) = \sum_{k=1}^m t_k \log({t_k \over p_k})
\end{equation}
因此对于上述伯努利分布，若t_i表示第i个样本为正例的真实概率，p_i为第i个样本为正例的估计概率，则整个训练集的相对熵可写为：
\begin{equation}\nonumber
KL(t_i \,||\, p_i) = \sum_{i=1}^m [t_i \log({t_i \over p_i}) + (1-t_i) \log ({{1-t_i} \over {1 - p_i}})]
\end{equation}
若对正例样本令t_i =1，负例样本令t_i = 0，就得到了正则化之前的目标优化函数，即最大似然函数。因此最大似然函数即为最小化相对熵
设事件A为正例的概率为\theta，即p(A) = \theta，频率学派认为\theta只是某一个固定的参数，因此为了估计\theta，做了m次独立观察，观察得到数据集D = \{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n) \}，则其最大似然概率（即选择\theta使得该数据集发生的概率最大）为：
\begin{equation}
\mu = \arg\max_{\mu}Pr(D;\mu) = \arg\max_{\mu}\prod_{i=1}^m Pr(D_i;\mu)
\end{equation}
但是贝叶斯学派认为\theta也服从某一个分布，因此刚刚的最大似然就变成了条件概率，我们还需要加上\theta的先验概率：
\begin{equation} \nonumber
\theta = \arg\max_{\theta}Pr(\theta|X) = \arg\max_{\theta}{{Pr(D | \theta) Pr(\theta)} \over {Pr(D)}}
\end{equation}
显然Pr(D)与\theta值无关，因此可化简为
\begin{equation}
\theta = \arg\max_{\theta}Pr(D|\theta)Pr(\theta)
\end{equation}
二项分布的先验概率\theta服从Beta分布，因此带入(48)并且取对数可以得到：
\begin{equation}\nonumber
\begin{aligned}
\tilde{\theta} &= \arg\max_{\theta} \sum_{i=1}^m \{\log Pr(x_i|\theta) \} \log Pr(\theta) \\
&=\arg\max_{\theta} \sum_{i=1}^m y_i \log \theta + (1-y_i) \log(1-\theta) + \log {{\theta^{\alpha -1}(1- \theta)^{\beta -1}} \over B(\alpha,\beta)} \\
&=\arg\max_{\theta} (m_{+} + \alpha -1) \log \theta + (\beta - 1 + m_{-})\log(1-\theta) + \text{constant} \\
&={{m_{+} +\alpha -1} \over {m+\alpha+\beta -2}}
\end{aligned}
\end{equation}
这样就得到了极大后验概率\tilde{\theta}，显然取到0和1的概率相等，因此我们取一次正例一次负例的情况为先验概率（即\alpha =\beta =2），然后我们分别观察正例和负例的情况，即分别取m=N_{+},m_{+} = m和m=N_{-},m_{+} = 0，即可得到先前的正则化后的t_i。
这里我们可以注意到，我们更改了t_i之后，则原目标函数变为：
\begin{equation}\nonumber
\begin{aligned}
\min_KL(t_i \, || \, p) =& \min\sum_{i=1}^m [t_i \log({t_i \over p_i}) + (1-t_i) \log ({{1-t_i} \over {1 - p_i}})] \\
=& \min \sum_{i=1}^m t_i \log(t_i) - t_i \log(p_i) \\
&+ (1-t_i) \log(1-t_i) - (1-t_i) \log(1-p_i) \\
=& \min -\sum_{i=1}^m t_i \log(p_i) + (1-t_i) \log(1-p_i) \\
=& \max \sum_{i=1}^m t_i \log(p_i) + (1-t_i) \log(1-p_i)
\end{aligned}
\end{equation}
结果仍然与式(42)相同。
16、 用SVM处理多分类问题
处理多分类问题，我们有多种策略，假设我们需要分成k类，有两种最基本的考虑：
1、one-against-one：将将k类中的每一类都两两比较，显然这需要训练{{k(k+1)} \over k}个二分类SVM模型，最终的结果我们通过投票产生：即把预测得最多的类别作为最终分类结果。
2、one-against-rest：将k类中的某一类作为正例，其余作为负例，显然这需要训练k个二分类SVM模型，测试时若仅有一个分类器预测为正例，则该分类器对应的类别标记即为最终样本分类，若多个都预测为正类，则需比较分类器的分类置信度。或者我们直接比较各个分类器分为正例的概率，选取最高概率的那一个分类器的分类标记。
在对数几率回归中，OVR只需要训练k个分类器，而OVO需要训练k(k-1) / 2个分类器，因此OVO的存储开销和测试时间开销通常比OVR大。但是在训练中，OVR的每一个分类器均适用全部训练样例，而OVO只使用两个训练样例。因此类别很多时OVO的训练时间开销更小。
然而在SVM模型中，OVR还需要额外训练k个概率拟合模型，因此我们通常选取OVO的方式来训练多分类问题。
还有一个问题需要考虑，就是关于参数C，以及核参数的选择。显然用交叉验证集来确定这两个超参数是比较不错的选择，但是我们需要考虑的是如何选择这几个超参数：
a. all-in-one：我们直接考虑整个多分类问题，即同时选定这k(k-1) /2个分类器的超参数，然后训练，在交叉验证集上验证，选取交叉验证集上分类错误率最小的值所对应的超参数（显然这个分类错误率是整个交叉验证集上分类错误率）。
b. one-in-one：我们考虑每一个分类器，即每一次对1个分类器选定超参数，然后训练，在交叉验证集上测试，也选取交叉验证集上分类错误率最小的值所对应的超参数（这里的分类错误率仅仅是交叉验证集上这一个分类器对应的这两类的分类错误率）。
显然，当需要划分新类或者更改类的划分的时候，all-in-one需要重新选择训练集和交叉验证集，重新选择超参数，即所有k(k-1) / 2个二分类SVM都需要更改；而对于one-in-one只需要更改该类对应的k个二分类SVM所对应的训练集和交叉验证集。
然而，选择one-in-one策略的时候，基于其所划分的两个类的预测性能，而不是基于全局多分类器的预测性能。因此one-in-one的方法可能会比all-in-one的方法更容易过拟合。
总而言之，one-in-one的方法不够鲁棒但是更改分类状况的时候的花销更小；而all-in-one在更改分类状况的时候花销较大但是更鲁棒。
附录A:从线性分类器导出概率
我们的SVM模型可以根据训练样本\boldsymbol{x}生成划分这些样本的最优超平面\boldsymbol{w}^T \boldsymbol{x}-b =0（上面的SVM模型是+b但变换成-b无任何影响，因此我们可以写出训练样例\boldsymbol{x}_i到超平面的距离。
\begin{equation}
d(\boldsymbol{x}_i) = {{|\boldsymbol{w}^T \boldsymbol{x}_i -b|} \over ||\boldsymbol{w}||} = {{|f(\boldsymbol{x}_i)|} \over {||w||}}
\end{equation}
我们将距离定义为有向距离，即\boldsymbol{w}正方向为正，反方向为负，则可以去掉绝对值，将(49)写成：
\begin{equation}
d(\boldsymbol{x}_i) = {{f(\boldsymbol{x}_i)} \over {||w||}} = {{\boldsymbol{w}^T \boldsymbol{x}_i -b} \over ||\boldsymbol{w}||} = \boldsymbol{w}'\boldsymbol{x}_i - b'
\end{equation}
我们先考虑正例的情况，用\bar{d}^{+}表示各正例到最优超平面的平均距离，即\bar{d}^{+} = \boldsymbol{w}^T \boldsymbol{\mu}^{+} -b，其中\boldsymbol{\mu}^{+}为正例的均值，而\boldsymbol{w}'是单位向量。
由于中心极限定理，大量独立同分布的随机变量近似服从于正态分布。因此我们有理由认为这些正例服从某一个分布，即正态分布。因此，我们可以将d的概率密度写成
\begin{equation}\nonumber
p(d\,|\,{+}) = {1 \over {\sqrt{2\pi}\sigma}} \exp \Big( - {{(d-\bar{d}^{+})^2} \over {2\sigma^2}} \Big)
\end{equation}
类似的，可以预期所有负例到决策面的距离围绕\bar{d}^{-} = \boldsymbol{w}\boldsymbol{\mu}^{-} -b呈正态分布，且有\bar{d}^{-} <0< \bar{d}^{+}，并且我们假设这两个正态分布具有相同的方差。
我们的目标是已知\boldsymbol{x}_{new}(即该点到超平面的距离)，求该点被分到正例的概率值，即p(+ |d(\boldsymbol{x}))，利用贝叶斯定理，可以得到
\begin{equation}
p(+ \,|\, d(\boldsymbol{x})) = {{p(d(\boldsymbol{x}) |+) p(+)} \over {p(d(\boldsymbol{x}) |+)p(+) + p(d(\boldsymbol{x})|-)p(-)}} = {1 \over {1+LR {p(+) \over p(-)}}}
\end{equation}
其中LR就是似然比，我们尝试计算LR
\begin{equation}\nonumber
\begin{aligned}
LR &= {{p(d(\boldsymbol{x} |+))} \over {p(d(\boldsymbol{x}) | -)}} = {{\exp(-(d(\boldsymbol{x})- 1/2)^2 /2)} \over {\exp(-(d(\boldsymbol{x})+1/2)^2/2)}} \\
&= \exp(-(d(\boldsymbol{x}) -\bar{d}^{+})^2 / 2\sigma^2) \exp ((d(\boldsymbol{x}) - \bar{d}^{-})^2/ 2\sigma^2) \\
&=\exp(\gamma(d(\boldsymbol{x})-d_0))
\end{aligned}
\end{equation}
其中
\begin{equation}\nonumber
\begin{aligned}
& \gamma = {{\bar{d}_{+} - \bar{d}_{-}} \over {\sigma^2}} \\
& d_0 = {{\bar{d}_{+} + \bar{d}_{-}} \over {2}}
\end{aligned}
\end{equation}
又由于d(\boldsymbol{x}_i) = f(\boldsymbol{x}_i)/ ||\boldsymbol{w}||，因此可以得到
\begin{equation}\nonumber
p(+ \,|\, d(\boldsymbol{x}_i)) = {1 \over {1+\exp(Af(\boldsymbol{x}_i)+B)}}
\end{equation}