学习目标

掌握SVM的基本原理以及推导过程

---

1.SVM的基本原理：

SVM本质上是一种二分类模型，基本模型是定义在特征空间中间隔最大的分类器，他的学习/优化目的就是使得这个间隔最大化。
为什么要使间隔最大化呢？ 这是为了更准确的分类，能够容忍数据集中的一些噪声，提高模型的泛化能力

1.1 SVM的分类

SVM可以分为三类： 线性可分（硬间隔）、线性不可分（软间隔）、非线性（使用核技巧）
线性可分(通俗解释）： 两类实体可以被一条直线完全分开
线性可分（学术解释）： D 0 D0 D0 和 D 1 D1 D1是n维欧式空间的点集，存在一个n维向量w 和 实数 b，使得所有属于D0的点都满足 wx+b>0，所有属于D1的点都满足 wx+b<0，这就称其为线性可分
线性不可分（通俗解释）： 两类实体斌不能完全被一条直线分开，总存在着第一类的点被分到第二类中的情况
线性不可分（学术解释）： D 0 D0 D0和 D 1 D1 D1是n维欧式空间的点集，对于n维向量 w w w 和 实数 b b b，总存在着属于D0的点都不满足 w ∗ x + b > 0 w*x+b>0 w∗x+b>0 或 总存在着属于D1的点不满足 w ∗ x + b < 0 w*x+b<0 w∗x+b<0，这就称其为线性不可分
非线性： 即要分开两类实体，其分类器不再是线性的（不再和上图一样是一条直线），而是非线性的

1.2 最大间隔超平面

将点集D0 和 D1 正确分开的超平面(hyperplane)，记为 w ∗ x + b = 0 w*x+b=0 w∗x+b=0。最大间隔超平面应该包括以下几点：

• 两类点集分别在超平面的两侧
• 两类点集中到超平面的距离最近的样本点 到 超平面 的距离被最大化

1.3. 支持向量

指的是距离超平面最近的一些点，满足 w ∗ x + b = 1 w*x+b =1 w∗x+b=1 或者 w ∗ x + b = − 1 w*x+b =-1 w∗x+b=−1

1.4.补充：凸集、凸优化、QP

SVM 的算法就是 凸二次规划的最优化算法

凸集：集合中任何两点的连线仍在该集合中
凸优化：求解凸集中凸函数的最优解
QP(quadratic programming,二次规划)定义为:

c T x c^Tx cTx+ 1 2 x T Q x \frac{1}{2}x^TQx 21​xTQx s.t.: A x = b Ax=b Ax=b x > = 0 x>=0 x>=0

二次规划即函数为二次，并且存在约束条件
当Q>0时，即为凸优化

---

SVM的推导过程：

2.1.目标函数

前面了解到 求解最优超平面 就是 寻找间隔最大的超平面。超平面用以下的公式来表示：

w T w^T wT+b=0

以二维空间为例，空间上两点（x,y)到直线 Ax+ By +C =0的距离为

d= ∣ A x + B + C ∣ ( A 2 + B 2 ) \frac{|Ax+B+C|}{\sqrt (A^2+B^2)} ( ​A2+B2)∣Ax+B+C∣​

扩展到n 维空间之后，距离可以表示为：

d= ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ \frac{|w^Tx+b|}{||w||} ∣∣w∣∣∣wTx+b∣​

这里为了方便，记为了二范数的形式,

∣ ∣ w ∣ ∣ ||w|| ∣∣w∣∣ = ( w 1 2 + w 2 2 . . + w n 2 ) \sqrt (w1^2+w2^2..+wn^2) ( ​w12+w22..+wn2)

设支持向量到最优超平面的距离为d，那么其他点到超平面的距离必然大于d，所以得到以下公式：

∣ w T x + b ∣ ∣ ∣ w ∣ ∣ \frac{|w^Tx+b|}{||w||} ∣∣w∣∣∣wTx+b∣​>= d y = 1
∣ w T x + b ∣ ∣ ∣ w ∣ ∣ \frac{|w^Tx+b|}{||w||} ∣∣w∣∣∣wTx+b∣​<= d y= -1

由于d>0，我们可以转化得到：

∣ w T x + b ∣ ∣ ∣ w ∣ ∣ d \frac{|w^Tx+b|}{||w||d} ∣∣w∣∣d∣wTx+b∣​>= 1 y = 1
∣ w T x + b ∣ ∣ ∣ w ∣ ∣ d \frac{|w^Tx+b|}{||w||d} ∣∣w∣∣d∣wTx+b∣​<= 1 y= -1

再次转化：

∣ w T x + b ∣ {|w^Tx+b|} ∣wTx+b∣>= 1 y = 1
∣ w T x + b ∣ {|w^Tx+b|} ∣wTx+b∣<= 1 y= -1

因此我们可以得到

( w T x + b ) {(w^Tx+b)} (wTx+b)* y y y >= 1 s.t. y=-1 and y=1

对于支持向量而言：

d= ∣ w T x + b ∣ ∣ ∣ w ∣ ∣ \frac{|w^Tx+b|}{||w||} ∣∣w∣∣∣wTx+b∣​ = y ∗ ( w T x + b ) ∣ ∣ w ∣ ∣ \frac{y*(w^Tx+b)}{||w||} ∣∣w∣∣y∗(wTx+b)​ = 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1​

我们的目标 就是 最大化 间隔d：

max 1 ∣ ∣ w ∣ ∣ \frac{1}{||w||} ∣∣w∣∣1​

为了方便后面求导，添加常数（不会影响后续的极值求解）：

max 2 ∣ ∣ w ∣ ∣ \frac{2}{||w||} ∣∣w∣∣2​

可以转化为：

min ∣ ∣ w ∣ ∣ 2 \frac{||w||}{2} 2∣∣w∣∣​

为了方便计算，可以转化为：

min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​

那么我们现在的目标函数就是i:

min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ s . t . s.t. s.t. ( w T x + b ) {(w^Tx+b)} (wTx+b)* y y y >= 1

2.2 拉格朗日乘数

拉格朗日法求解SVM最优平面，这个最优平面仅仅是由支持向量来决定的，点集中的其他点对于这个最优平面的选择是没有贡献的（和最小二乘法求解SVM不同），证明如下：

对于拉格朗日乘数法，定义如下：

m i n f ( x 1 , x 2... x n ) min f(x1,x2...xn) minf(x1,x2...xn) s . t . g ( k ) = 0 s.t. g(k)=0 s.t.g(k)=0 , k = 0 , 1 , 2 , 3.. n k=0,1,2,3..n k=0,1,2,3..n

L ( x , a ) L(x,a) L(x,a) = m i n f ( x 1 , x 2... x n ) min f(x1,x2...xn) minf(x1,x2...xn)+ ∑ i = 1 n a i ∗ g ( i ) \sum_{i=1}^{n} a_i*g(i) ∑i=1n​ai​∗g(i)

根据在2.1节中推出的目标函数，增加常数k使其变为等式：

min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ s . t . s.t. s.t. 1 − ( w T x + b ) 1-{(w^Tx+b)} 1−(wTx+b)* y y y + k 2 k^2 k2=0

带入拉格朗日公式：

L ( x , a ) L(x,a) L(x,a) = m i n min min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ + ∑ i = 1 n a i ∗ ( 1 − ( w T x i + b ) \sum_{i=1}^{n} a_i*(1-{(w^Tx_i+b)} ∑i=1n​ai​∗(1−(wTxi​+b)* y i y_i yi​ + k i 2 k_i^2 ki2​) s.t. a>=0

求导可得：

对w求导： ∣ ∣ w ∣ ∣ {||w||} ∣∣w∣∣- ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​ =0
对a求导： 1 − ( w T x i + b ) 1-{(w^Tx_i+b)} 1−(wTxi​+b) y i y_i yi​ + k i 2 k_i^2 ki2​ =0
对k求导：2 k i k_i ki​ a i a_i ai​=0
s.t. a>=0

设 1 − ( w T x i + b ) 1-{(w^Tx_i+b)} 1−(wTxi​+b)* y i y_i yi​ = g i g_i gi​，上式存在着两种情况：

1. a i a_i ai​不等于0， k i k_i ki​=0：此时 g i g_i gi​=0
2. a i a_i ai​=0， k i k_i ki​不等于0：此时 g i g_i gi​<0

因此，可以得出结论：当点为支持向量时，拉格朗日乘子不为0，而当点不是支持向量时，拉格朗日乘子等于0。所以说 d是由支持向量来决定的，并非所有的点都对求解最佳超平面有贡献

2.3 SVM优化

L ( w , b , a ) L(w,b,a) L(w,b,a) = m i n min min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ + ∑ i = 1 n a i ∗ ( 1 − ( w T x i + b ) \sum_{i=1}^{n} a_i*(1-{(w^Tx_i+b)} ∑i=1n​ai​∗(1−(wTxi​+b)* y i y_i yi​ ) s.t. a i a_i ai​>=0

对其进行强对偶转换（见2.4)：

m a x ( a ) m i n ( w , b ) max(a)min(w,b) max(a)min(w,b) ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ + ∑ i = 1 n a i ∗ ( 1 − ( w T x i + b ) \sum_{i=1}^{n} a_i*(1-{(w^Tx_i+b)} ∑i=1n​ai​∗(1−(wTxi​+b)* y i y_i yi​ ) s.t. a i > = 0 a_i>=0 ai​>=0

求导：

对w求导： ∣ ∣ w ∣ ∣ {||w||} ∣∣w∣∣- ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​ =0
对b求导： ∑ i = 1 n a i ∗ y i \sum_{i=1}^{n}a_i*y_i ∑i=1n​ai​∗yi​=0

得到:

∣ ∣ w ∣ ∣ {||w||} ∣∣w∣∣= ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​
∑ i = 1 n a i ∗ y i \sum_{i=1}^{n}a_i*y_i ∑i=1n​ai​∗yi​=0

带入原式可得：

1 2 \frac{1}{2} 21​ ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​ * ∑ j = 1 n a j ∗ x j ∗ y j \sum_{j=1}^{n}a_j*x_j*y_j ∑j=1n​aj​∗xj​∗yj​ + ∑ i = 1 n a i \sum_{i=1}^{n} a_i ∑i=1n​ai​- ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​ * ∑ j = 1 n a j ∗ x j ∗ y j \sum_{j=1}^{n}a_j*x_j*y_j ∑j=1n​aj​∗xj​∗yj​

= ∑ i = 1 n a i \sum_{i=1}^{n} a_i ∑i=1n​ai​- 1 2 \frac{1}{2} 21​ ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​ * ∑ j = 1 n a j ∗ x j ∗ y j \sum_{j=1}^{n}a_j*x_j*y_j ∑j=1n​aj​∗xj​∗yj​

min(b,w)求完了，再求解max(a):

∑ i = 1 n a i \sum_{i=1}^{n} a_i ∑i=1n​ai​- 1 2 \frac{1}{2} 21​ ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​ * ∑ j = 1 n a j ∗ x j ∗ y j \sum_{j=1}^{n}a_j*x_j*y_j ∑j=1n​aj​∗xj​∗yj​
s.t. ∑ i = 1 n a i ∗ y i \sum_{i=1}^{n}a_i*y_i ∑i=1n​ai​∗yi​=0 , a i a_i ai​>=0

利用SMO算法求解最优的a

根据a的值求解 w：

w {w} w= ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​

带入支持向量，b= y s y_s ys​-w* x s x_s xs​

或者为了求得更准确的b，可以用支持向量的均值来表示：

b= 1 ∣ S ∣ \frac{1}{|S|} ∣S∣1​ ∑ i n \sum_i^{n} ∑in​ y s y_s ys​-w x s x_s xs​

求出了w 和 b就可以得到 w*x+b=0 这个超平面，利用sign()函数的特性构造分类器：

f ( x ) = f ( w ∗ x + b ) f(x)=f(w*x+b) f(x)=f(w∗x+b)

当 w ∗ x + b > 0 w*x+b>0 w∗x+b>0 f = 1 f=1 f=1
当 w ∗ x + b = 0 w*x+b=0 w∗x+b=0 f = 0 f=0 f=0
当 w ∗ x + b < 0 w*x+b<0 w∗x+b<0 f = − 1 f=-1 f=−1

2.4 对偶转化

存在着以下的公式：
m a x m i n f ( x ) maxminf(x) maxminf(x)<= m i n m a x f ( x ) minmaxf(x) minmaxf(x)

对偶转化是指，在一定条件下
m i n m a x f ( x ) minmaxf(x) minmaxf(x)可以近似转化为 m a x m i n f ( x ) maxminf(x) maxminf(x)

进行了对偶转化之后，可以更为方便的求解，若先求a的偏导，没有办法得到有用的条件

2.5 软间隔

2.2-2.3求解的是线性可分的情况，现在来求解线性不可分，现在条件不再像之前一样苛刻，允许有的点不满足

( w T x + b ) {(w^Tx+b)} (wTx+b)* y y y >= 1

即存在点使得 ( w T x + b ) {(w^Tx+b)} (wTx+b)* y y y <= 1 ， 位于间隔内部

因此引入松弛变量 δ \delta δ.（ δ \delta δ.>=0)，使得 ( w T x + b ) {(w^Tx+b)} (wTx+b)* y y y+ δ \delta δ >= 1

优化函数变成了

m i n min min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ +C ∑ i n δ i \sum_i^{n}\delta_i ∑in​δi​
s.t. ( w T x + b ) {(w^Tx+b)} (wTx+b)* y y y+ δ \delta δ >= 1 , δ \delta δ.>=0

这里的 C可以理解为错误样本的惩罚程度，若 C 为无穷大， δ \delta δ 就无穷小，线性 SVM 就又变成了线性可分 SVM

构造拉格朗日函数：

L(w,a,b,u, δ \delta δ)= ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ +C ∑ i n δ i \sum_i^{n}\delta_i ∑in​δi​+ ∑ i n a i ∗ ( 1 − ( w i T x i + b ) \sum_i^{n}a_i*(1-(w_i^Tx_i+b) ∑in​ai​∗(1−(wiT​xi​+b)* y i y_i yi​- δ i \delta_i δi​)- ∑ i n u i \sum_i^{n}u_i ∑in​ui​ δ i \delta_i δi​
s.t. a i a_i ai​>=0 u i u_i ui​>=0

求导（求minL(w,b, δ \delta δ)：

对w进行求导:w= ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​

对b进行求导： ∑ i = 1 n a i ∗ y i \sum_{i=1}^{n}a_i*y_i ∑i=1n​ai​∗yi​=0

对 δ \delta δ求导：C= a i a_i ai​+ u i u_i ui​

带入原式：

= ∑ i = 1 n a i \sum_{i=1}^{n} a_i ∑i=1n​ai​- 1 2 \frac{1}{2} 21​ ∑ i = 1 n a i ∗ x i ∗ y i \sum_{i=1}^{n}a_i*x_i*y_i ∑i=1n​ai​∗xi​∗yi​ * ∑ j = 1 n a j ∗ x j ∗ y j \sum_{j=1}^{n}a_j*x_j*y_j ∑j=1n​aj​∗xj​∗yj​
s.t. ∑ i = 1 n a i ∗ y i \sum_{i=1}^{n}a_i*y_i ∑i=1n​ai​∗yi​=0， a i a_i ai​>=0 u i u_i ui​>=0

其实和线性可分的求解结果是相同的

2.6（非线性SVM）核函数

对于一些情况，存在着非线性的超平面（图源知乎）

这时候应该将其映射到更高维的空间上去
这时候的超平面可以表示成 w T ∗ ϕ ( x ) + b w^T*\phi(x)+b wT∗ϕ(x)+b， ϕ ( x ) \phi(x) ϕ(x)为x映射到高维空间后的结果

此时 ，原式可以表示为 ：

= ∑ i = 1 n a i \sum_{i=1}^{n} a_i ∑i=1n​ai​- 1 2 \frac{1}{2} 21​ ∑ i = 1 n a i ∗ ϕ ( x i ) ∗ y i \sum_{i=1}^{n}a_i*\phi(x_i)*y_i ∑i=1n​ai​∗ϕ(xi​)∗yi​ * ∑ j = 1 n a j ∗ ϕ ( x j ) ∗ y j \sum_{j=1}^{n}a_j*\phi(x_j)*y_j ∑j=1n​aj​∗ϕ(xj​)∗yj​

因为映射到高维空间后再进行相乘，计算量很大，这里引入了核函数来减少计算量

核函数的作用是： x i x_i xi​与 x j x_j xj​在原始空间内，通过核函数计算的结果=其在高维空间内的乘积，这样求乘积的时候就不必在高维空间内计算了，极大地提高了计算效率

常见的核函数有：线性核函数、多项式核函数、高斯核函数

线性核函数:
k ( x i , y i ) k(x_i,y_i) k(xi​,yi​)= x i T x j x_i^Tx_j xiT​xj​

多项式核函数:
k ( x i , y i ) k(x_i,y_i) k(xi​,yi​)= ( x i T x j + 1 ) d (x_i^Tx_j+1)^d (xiT​xj​+1)d

高斯核函数(需要进行调参）
k ( x i , y i ) k(x_i,y_i) k(xi​,yi​)=exp( − ( x i − x j ) 2 2 0 2 ) -\frac{(x_i-x_j)^2}{20^2}) −202(xi​−xj​)2​)

SVM的一些优缺点：

优点：
1.计算的复杂性仅取决于支持向量的大小，而不是空间的维度，避免了维度灾难

缺点：
1.存储核矩阵需要额外的空间，空间复杂度为 O(N^2)
2.运行时间很长，复杂度与支持向量成正比

3.基于最小二乘法的SVM

上述的拉格朗日求解法本质上是一个二次规划（quadratic programming ,QP）问题，其最大间隔超平面仅仅和支持向量有关，其他的点对于最优平面的选择没有贡献。因此J.A.K. SUYKENS等人提出了基于最小二乘法思想的SVM求解方法，采用求线性解的方法，提高了求解效率，并且使得所有的点对最优平面都是有贡献的

目标函数为：
L ( w , b , a ) L(w,b,a) L(w,b,a) = m i n min min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ + 1 2 γ ∑ i n e i 2 \frac{1}{2}\gamma\sum_i^{n}e_i^2 21​γ∑in​ei2​
s.t. y i ( w i T ϕ ( x i ) + b ) = 1 − e i y_i(w_i^T\phi(x_i)+b)=1-e_i yi​(wiT​ϕ(xi​)+b)=1−ei​

因此它的 d 为
d= ∣ w T x i + b ∣ ∣ ∣ w ∣ ∣ \frac{|w^Tx_i+b|}{||w||} ∣∣w∣∣∣wTxi​+b∣​= ( 1 − e i ) ∣ ∣ w ∣ ∣ \frac{(1-e_i)}{||w||} ∣∣w∣∣(1−ei​)​

转化为：
L(w,b, a a a, e e e)= m i n min min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ + 1 2 γ ∑ i n e i 2 \frac{1}{2}\gamma\sum_i^{n}e_i^2 21​γ∑in​ei2​+ ∑ i n a i ∗ ( 1 − e i − y i ( w i T ϕ ( x i ) + b ) \sum_i^{n}a_i*(1-e_i-y_i(w_i^T\phi(x_i)+b) ∑in​ai​∗(1−ei​−yi​(wiT​ϕ(xi​)+b)

求导：
对w求导：
w= ∑ i n a i y i ϕ ( x i ) \sum_i^na_iy_i\phi(x_i) ∑in​ai​yi​ϕ(xi​)

对b求导：
∑ i n a i y i \sum_i^{n}a_iy_i ∑in​ai​yi​=0

对e求导：
γ ∑ i n e i = \gamma\sum_i^{n}e_i= γ∑in​ei​= ∑ i n a i \sum_i^{n}a_i ∑in​ai​
即： γ \gamma γ e i e_i ei​= a i a_i ai​

对 b b b求导：
∑ i n a i y i = 0 \sum_i^{n}a_iy_i=0 ∑in​ai​yi​=0

带入原式可得(按照拉格朗日求法）：

L(w,b, a a a, e e e)= m i n min min ∣ ∣ w ∣ ∣ 2 2 \frac{||w||^2}{2} 2∣∣w∣∣2​ + 1 2 γ ∑ i n e i 2 \frac{1}{2}\gamma\sum_i^{n}e_i^2 21​γ∑in​ei2​+ ∑ i n a i ∗ ( 1 − e i − y i ( w i T ϕ ( x i ) + b ) \sum_i^{n}a_i*(1-e_i-y_i(w_i^T\phi(x_i)+b) ∑in​ai​∗(1−ei​−yi​(wiT​ϕ(xi​)+b)

L(w,b, a a a, e e e)= 1 2 ∑ i n a i y i ϕ ( x i ) ∗ ∑ j n a j y j ϕ ( x j ) \frac{1}{2}\sum_i^{n}a_iy_i\phi(x_i)*\sum_j^{n}a_jy_j\phi(x_j) 21​∑in​ai​yi​ϕ(xi​)∗∑jn​aj​yj​ϕ(xj​)+ 1 2 γ ∑ i n e i 2 \frac{1}{2}\gamma\sum_i^{n}e_i^2 21​γ∑in​ei2​+ ∑ i n γ e i ( 1 − e i − y i ( w i T ϕ ( x i ) + b ) ) \sum_i^{n}\gamma e_i(1-e_i-y_i(w_i^T\phi(x_i)+b)) ∑in​γei​(1−ei​−yi​(wiT​ϕ(xi​)+b))

= 1 2 ∑ i n a i y i ϕ ( x i ) ∗ ∑ j n a j y j ϕ ( x j ) \frac{1}{2}\sum_i^{n}a_iy_i\phi(x_i)*\sum_j^{n}a_jy_j\phi(x_j) 21​∑in​ai​yi​ϕ(xi​)∗∑jn​aj​yj​ϕ(xj​)+ 1 2 γ ∑ i n e i 2 \frac{1}{2}\gamma\sum_i^{n}e_i^2 21​γ∑in​ei2​+ ∑ i n γ e i \sum_i^{n}\gamma e_i ∑in​γei​- ∑ i n γ e i 2 \sum_i^{n}\gamma e_i^2 ∑in​γei2​- ∑ i n a i y i ∑ j n a j y j ϕ ( x j ) ϕ ( x i ) \sum_i^{n}a_iy_i\sum_j^{n}a_jy_j\phi (x_j)\phi(x_i) ∑in​ai​yi​∑jn​aj​yj​ϕ(xj​)ϕ(xi​)

= ∑ i n a i \sum_i^{n}a_i ∑in​ai​- 1 2 ∑ i n a i y i ϕ ( x i ) ∗ ∑ j n a j y j ϕ ( x j ) \frac{1}{2}\sum_i^{n}a_iy_i\phi(x_i)*\sum_j^{n}a_jy_j\phi(x_j) 21​∑in​ai​yi​ϕ(xi​)∗∑jn​aj​yj​ϕ(xj​)- 1 2 ∑ i n γ e i 2 \frac{1}{2}\sum_i^{n}\gamma e_i^2 21​∑in​γei2​
仍然是一个二次问题

按照论文思路，J.A.K. SUYKENS等将其写为（Latex的手麻了，这里截个图…)：


这就将问题转化成了求解线性问题
有、类似于机器学习中求梯度的问题…，
γ \gamma γ e i e_i ei​= a i a_i ai​，这也可以看出support value a 并非只有支持向量才有。

最后可以得到LSSVM的表达式为：

y ( x ) y(x) y(x)= s i g n sign sign[ ∑ i n a i y i K ( x , x i ) + b ] \sum_i^{n} a_iy_iK(x,x_i)+b] ∑in​ai​yi​K(x,xi​)+b]

文中通过实验证明了最小二乘SVM have excellent
generalization performance and low computational cost

---

参考文献：

1. https://zhuanlan.zhihu.com/p/77750026
2. 《机器学习》周志华
3. J.A.K. Suykens,J. Vandewalle. Least Squares Support Vector Machine Classifiers[J]. Neural Processing Letters,1999,9(3).