在之前的课程中讨论的分类器都是线性的，而在实际问题中，很多数据并不是线性可分的，也就是说找不到这样的超平面，能完全区分不同的数据。所以，需要在分类器中引入非线性成分，使得模型更好地贴合数据，让分类更加准确。为了使模型非线性化，我们可以通过基函数将原始特征x变换到另一个空间。问题变为了原始最大裕度优化问题： min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ n = 1 N ξ n s . t . : y ( n ) ⋅ ( w T ϕ ( x ( n ) ) + b ) ≥ 1 − ξ n \min_{\bold w,b,\bold \xi}\frac12||\bold w||^2+C\sum^N_{n=1}\xi_n\\ s.t.:y^{(n)}\cdot(\bold w^T\bold \phi(\bold x^{(n)})+b)\geq1-\xi_n w,b,ξmin​21​∣∣w∣∣2+Cn=1∑N​ξn​s.t.:y(n)⋅(wTϕ(x(n))+b)≥1−ξn​ 得到的分类器为： y ^ ( x ) = s i g n ( w ∗ T ϕ ( x ( n ) ) + b ∗ ) \hat y(\bold x)=sign(\bold w^{*T}\phi(\bold x^{(n)})+b^*) y^​(x)=sign(w∗Tϕ(x(n))+b∗) 从直观上看，数据在高维空间中更容易分离。为了获得更好的性能，我们希望映射后的x到更高维的空间。然而太高的话代价也很大。使用对偶形式方法解决时会要计算映射值的转置与自身的内积，导致高开销。这个问题可以通过使用内核技巧来解决。

核函数是一个二元函数，可以表示为某些函数的内积： k ( x , x ′ ) = ϕ ( x ) T ϕ ( x ′ ) k(\bold x,\bold x')=\phi(\bold x)^T\phi(\bold x') k(x,x′)=ϕ(x)Tϕ(x′) Mercer定理：如果函数 k ( x , x ′ ) k(\bold x,\bold x') k(x,x′)是对称正定的，即： ∫ ∫ g ( x ) k ( x , y ) g ( y ) d x d y ≥ 0 ∀ g ( ⋅ ) ∈ L 2 \int\int g(\bold x)k(\bold x,\bold y)g(\bold y)d\bold xd\bold y\geq0\forall g(\cdot)\in L^2 ∫∫g(x)k(x,y)g(y)dxdy≥0∀g(⋅)∈L2 就存在函数 ϕ ( ⋅ ) \phi(\cdot) ϕ(⋅)使得 k ( x , x ′ ) = ϕ ( x ) T ϕ ( x ′ ) k(\bold x,\bold x')=\phi(\bold x)^T\phi(\bold x') k(x,x′)=ϕ(x)Tϕ(x′)。一个函数如果满足正定条件就必然是核函数。

最常用的核函数之一是高斯核，有着无限维： k ( x , x ′ ) = exp ⁡ { − 1 2 σ 2 ∣ ∣ x − x ′ ∣ ∣ 2 } k(\bold x,\bold x')=\exp\{-\frac1{2\sigma^2}||\bold x-\bold x'||^2\} k(x,x′)=exp{−2σ21​∣∣x−x′∣∣2} 利用核函数，可以将对偶最大边距分类器重写为： max ⁡ a g ( a ) s . t . : a n ≥ 0 , a n ≤ C , ∑ n = 1 N a n y ( n ) = 0 \max_{\bold a}g(\bold a)s.t.:a_n\geq0,a_n\leq C,\sum^N_{n=1}a_ny^{(n)}=0 amax​g(a)s.t.:an​≥0,an​≤C,n=1∑N​an​y(n)=0 其中， g ( a ) = ∑ n = 1 N a n − 1 2 ∑ n = 1 N ∑ m = 1 N a n a m y ( n ) y ( m ) k ( x ( n ) , x ( m ) ) g(\bold a)=\sum^N_{n=1}a_n-\frac12\sum^N_{n=1}\sum^N_{m=1}a_na_my^{(n)}y^{(m)}k(\bold x^{(n)},\bold x^{(m)}) g(a)=n=1∑N​an​−21​n=1∑N​m=1∑N​an​am​y(n)y(m)k(x(n),x(m)) 从而得到诱导分类器： y ^ ( x ) = s i g n ( ∑ n = 1 N a n ∗ y ( n ) ) k ( x ( n ) , x ( m ) ) + b ∗ ) \hat y(\bold x)=sign(\sum^N_{n=1}a_n^*y^{(n)})k(\bold x^{(n)},\bold x^{(m)})+b^*) y^​(x)=sign(n=1∑N​an∗​y(n))k(x(n),x(m))+b∗) 核技巧：将函数k代入。如果 ϕ \phi ϕ不改变 x \bold x x则为线性最大边际分类器，否则为基于基函数的有限维非线性最大边际分类器，如果为高斯核，则为无限维非线性最大边际分类器。

活页损失hinge loss定义如下： L ( w ) = max ⁡ ( 0 , 1 − y h ) L(\bold w)=\max(0,1-yh) L(w)=max(0,1−yh) 其中 h = w T x h=\bold w^T\bold x h=wTx， y = ± 1 y=\pm1 y=±1。从公式可以直观地看出，当实际标签为1时，预测结果小于1则会产生梯度，否则梯度为0。而实际标签为-1时，预测结果大于-1时会产生梯度，否则梯度为0。也就是说，在活页损失下，该模型会自动舍弃一些预测结果正确的样本。即便这些样本也会产生误差，但它们都不是误差的主要来源。该模型下只会考虑带来更大误差的样本，这和最大边际分类器的思想是一致的。最大边际分类器的要求是找到两个类中距离超平面最近的两点，将这个距离和作为边际，并将其最大化。也就是说，只考虑离超平面最近的点来修正超平面的位置，而不考虑离超平面更远的样本。

一般的线性最大边际分类器的条件为： min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 s . t . : y ( n ) ⋅ ( w T x ( n ) + b ) ≥ 1 \min_{\bold w,b,\bold \xi}\frac12||\bold w||^2s.t.:y^{(n)}\cdot(\bold w^T\bold x^{(n)}+b)\geq1 w,b,ξmin​21​∣∣w∣∣2s.t.:y(n)⋅(wTx(n)+b)≥1 使用hinge loss的模型还可以加入松弛变量，从而弱化条件，使得非线性可分的数据具有一定的容忍性： min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ n = 1 N ξ n s . t . : y ( n ) ⋅ ( w T x ( n ) + b ) ≥ 1 − ξ n \min_{\bold w,b,\bold \xi}\frac12||\bold w||^2+C\sum^N_{n=1}\xi_ns.t.:y^{(n)}\cdot(\bold w^T\bold x^{(n)}+b)\geq1-\xi_n w,b,ξmin​21​∣∣w∣∣2+Cn=1∑N​ξn​s.t.:y(n)⋅(wTx(n)+b)≥1−ξn​ 但是即便如此，使用hinge loss的线性分类模型仍然是线性的。SVM模型在此基础上，将 x \bold x x通过一个基函数 ϕ \phi ϕ变换到另一个空间，从而真正实现了非线性成分的引入。问题变为了： min ⁡ w , b , ξ 1 2 ∣ ∣ w ∣ ∣ 2 + C ∑ n = 1 N ξ n s . t . : y ( n ) ⋅ ( w T ϕ ( x ( n ) ) + b ) ≥ 1 − ξ n \min_{\bold w,b,\bold \xi}\frac12||\bold w||^2+C\sum^N_{n=1}\xi_n\\ s.t.:y^{(n)}\cdot(\bold w^T\bold \phi(\bold x^{(n)})+b)\geq1-\xi_n w,b,ξmin​21​∣∣w∣∣2+Cn=1∑N​ξn​s.t.:y(n)⋅(wTϕ(x(n))+b)≥1−ξn​ 可以看到，使用hinge loss的线性分类模型和SVM模型的区别在于，原来hinge loss线性分类模型中的 x \bold x x的项全部被换成了 ϕ ( x ) \phi(\bold x) ϕ(x)，从而实现了 x \bold x x到高维空间的映射，使得模型获得了非线性成分。

首先读入数据集：

我使用了python的sklearn库来实现SVM：

以线性核函数的SVM模型为例，首先创建模型：

然后进行训练：

训练时可以调整一定的超参数。对于线性分类器来说，需要确定模型训练结束的标志，可以设置模型精度和最大迭代次数。这里我选用库里的默认参数，即不设置最大迭代次数，模型精度为tol = 1e-3。模型会自适应地决定每个类所占据的权重，不同的类设置不同的惩罚参数。

训练后进行预测与结果统计：

高斯核的代码也基本一致，在创建模型时将核函数的参数改为高斯核rbf(径向基函数)即可：

高斯核中需要确定 σ \sigma σ的参数值，在sklearn的参数中为 g a m m a gamma gamma，其中 g a m m a = 1 2 σ 2 gamma=\frac1{2\sigma^2} gamma=2σ21​。我的实现中仍采用默认值，即 g a m m a gamma gamma值为特征值个数的倒数。

在读入数据后需要注意，使用合页损失hinge loss的话，要求二分类的标签为1或-1，而不是之前的1或0。所以需要更改标签：

对每个特征向量，还要增加一维1作为偏移项。在本次的实验中，处理的图像都属于图片，像素值范围为0~255，因此可以考虑将所有原有的特征值除以255进行归一化处理。即： ∀ i = 1 , 2 , . . . , N x i = x i − x m i n x m a x − x m i n \forall i=1,2,...,N\quad x_i=\frac{x_i-x_{min}}{x_{max}-x_{min}} ∀i=1,2,...,Nxi​=xmax​−xmin​xi​−xmin​​ 从而使得所有特征值的范围为 [ 0 , 1 ] [0,1] [0,1]，便于之后的梯度计算：

然后设置基本的变量和超参数：

在训练过程中，需要对损失函数求梯度。hinge loss为： L ( w ) = max ⁡ ( 0 , 1 − y h ) L(\bold w)=\max(0,1-yh) L(w)=max(0,1−yh) 其中 h = w T x h=\bold w^T\bold x h=wTx， y = ± 1 y=\pm1 y=±1。

也就是说，当 1 − y ( w T x ) 1-y(\bold w^T\bold x) 1−y(wTx)小于等于0时，梯度就为0。换言之，当前的样本对修正梯度没有任何影响，直接忽略了。否则，对合页损失函数求导得到 − h x -hx −hx，即： KaTeX parse error: Undefined control sequence: \part at position 8: \frac{\̲p̲a̲r̲t̲ ̲L(\bold w)}{\pa… 从而可以使用梯度下降法对模型进行训练：

使用交叉熵损失训练二分类模型需要用到sigmoid函数。该函数为： σ ( x ) = 1 1 + e − x \sigma(x)=\frac1{1+e^{-x}} σ(x)=1+e−x1​ e − x e^{-x} e−x将 x x x映射到 ( 0 , + ∞ ) (0,+\infin) (0,+∞)，在实际运算过程中， x x x数值过小时可能会造成溢出。因此考虑将 x x x分符号讨论，保证 − x -x −x为负，使得映射的结果为 ( 0 , 1 ] (0,1] (0,1]： σ ( x ) = { 1 1 + e − x , x ≥ 0 e x 1 + e x , x < 0 \sigma(x)=\left\{\begin{array}{}\frac1{1+e^{-x}},x\geq0\\ \frac{e^x}{1+e^x},x