简介

SVM标准算法在应用中存在着超平面参数选择，以及QP问题求解中矩阵规模受训练样本数目的影响很大，导致求解规模过大的问题。

Suykens等人提出的最小二乘支持向量机（Least Squares Support Vector Machines,LS-SVM）从机器学习损失函数着手，在其优化问题的目标函数中使用二范数，并利用等式约束条件代替SVM标准算法中的不等式约束条件，使得LS-SVM方法的优化问题的求解变为通过Kuhn-Tucker条件得到的一组线性方程组的求解。

SVM与LS-SVM的比较

（1）优化问题的构造

从前述对SVM与LS-SVM方法在样本分类与回归估计的分析中可以看出，两种方法的优化问题的构造上，目标函数分别采用了误差因子的一次项与二次项，同时约束条件分别采用了不等式约束与等式约束形式。这两方面的差别也导致了两种方法在求解过程中的差异。

（2）优化问题的求解

SVM求解QP问题中，变量维数等于训练样本的个数，从而使其中矩阵元素的个数是训练样本个数的平方。当数据规模达到一定程度时，SVM算法的求解规模就会使一些传统办法难以适应。针对SVM的求解困难的问题，也产生了一些相应的解决办法，如选块算法和SMO算法等。这些算法在一定程度上简化了SVM优化问题的求解，促进了SVM的应用发展。而LS-SVM方法通过求解线性方程组实现最终的决策函数，在一定程度上降低了求解难度，提高了求解速度，使之更能适合于求解大规模问题，更能适应于一般的实际应用。虽然并不一定能获得全局最优解，但是仍可以获得较高精度的识别率。

（3）解的稀疏性

SVM标准算法中，需要求解复杂的QP问题，可以获得理论上的全局最优解，并且，大部分的Lagrange乘子均为零，使得最终的决策函数只依赖于少部分样本数据，即支持向量。使SVM方法中解显示出稀疏性的特点。在LS-SVM方法中，由于其优化问题的目标函数使用了误差平方项以及等式约束条件，将SVM的QP问题转化为一组线性方程组求解，使得Lagrange乘子与误差项成比例关系，直接的后果就使得最终决策函数与所有样本都相关，也就失去了SVM方法中解的稀疏性的特点。但是LS-SVM方法通过对最终求解得到的Lagrange乘子进行排序，并使用“修剪”算法，仍然可以在一定程度上实现解的稀疏性的。

LSSVM公式推导

分类问题

对于SVM问题，约束条件是不等式约束：
$\begin{aligned} &min_{w,b,\xi}J\left(w,\xi\right)=\dfrac{1}{2}w^{T}w+c\sum^{N}_{k=1}\xi_{k}\\ s.t. &\qquad y_{k}\left[w^T\varphi\left(x_{k}\right)+b\right]\geq 1-\xi_{k},\ \ \ k=1,\ldots,N\\ &\xi_{k}\geq 0,k=1,\ldots,N \end{aligned}$s.t.​minw,b,ξ​J(w,ξ)=21​wTw+ck=1∑N​ξk​yk​[wTφ(xk​)+b]≥1−ξk​,   k=1,…,Nξk​≥0,k=1,…,N​
对于LSSVM，原问题变为等式约束：
$\begin{aligned} min_{w,b,e}J\left(w,e\right) &=\dfrac{1}{2}w^{T}w+\dfrac{1}{2}\gamma\sum^{N}_{k=1}e^2_{k}\\s.t. \qquad y_{k}\left[w^T\varphi\left(x_{k}\right)+b\right]&= 1-e_{k},\ \ \ k=1,\ldots,N \end{aligned}$minw,b,e​J(w,e)s.t.yk​[wTφ(xk​)+b]​=21​wTw+21​γk=1∑N​ek2​=1−ek​,   k=1,…,N​

原SVM问题中的 ξ 是一个松弛变量，它的意义在于在支持向量中引入离群点。而对于LSSVM的等式约束，等式右侧的 e 和SVM的 ξ 的意义是类似的，最后的优化目标中也包含了 e 。

所有的训练样本均作为支持向量，这也是最小二乘支持向量机的缺点之一，而误差 e 是我们的优化目标之一。

注释：
SVM模型有两个非常重要的参数c与$\gamma$γ。其中 c是惩罚系数，即对误差的宽容度。c越高，说明越不能容忍出现误差,容易过拟合。c越小，容易欠拟合。c过大或过小，泛化能力变差

另外，在LSSVM中 γ 和SVM中 c 的意义是一样的，一个权重，用于平衡寻找最优超平面和偏差量最小。

接下来，和SVM类似，采用 Lagrange 乘数法把原问题转化为对单一参数，也就是 α 的求极大值问题。新问题如下
$L\left(w,b,e;\alpha \right)=J\left(w,e\right)-\sum^{N}_{k=1}\alpha_{k}\left\{y_{k}\left[w^{T}\varphi(x_{k})+b\right]-1+e_k\right\}$L(w,b,e;α)=J(w,e)−∑k=1N​αk​{yk​[wTφ(xk​)+b]−1+ek​}

分别对$w，b，e_k，\alpha_k$w，b，ek​，αk​求导等于0:
$\begin{aligned} \dfrac {\partial L}{\partial \omega}&=0 \rightarrow w=\sum^N_{k=1}\alpha_ky_k\varphi\left(x_k\right)\\ \dfrac {\partial L}{\partial b}&=0 \rightarrow \sum^N_{k=1}\alpha_ky_k=0\\\dfrac {\partial L}{\partial e_k}&=0 \rightarrow \alpha_k=\gamma e_k, \ \ \ k=1,...,N\\ \dfrac {\partial L}{\partial \alpha _k}&=0 \rightarrow y_k\left[w^T\varphi (x_k)+b\right]-1+e_k=0, \ \ \ k=1,...,N \end{aligned}$∂ω∂L​∂b∂L​∂ek​∂L​∂αk​∂L​​=0→w=k=1∑N​αk​yk​φ(xk​)=0→k=1∑N​αk​yk​=0=0→αk​=γek​,   k=1,...,N=0→yk​[wTφ(xk​)+b]−1+ek​=0,   k=1,...,N​
接下来，根据这四个条件可以列出一个关于 α 和 b 的线性方程组:
$\begin{bmatrix} 0 & y^T\\ y & \Omega+I/y \\ \end{bmatrix} \begin{bmatrix} b\\ \alpha \\ \end{bmatrix}= \begin{bmatrix} 0\\ 1_v\\ \end{bmatrix}$[0y​yTΩ+I/y​][bα​]=[01v​​]
其中 Ω 被称作核矩阵
$\begin{aligned} \Omega _{kl}&=y_ky_l\varphi(x_k)^T\varphi(x_l)\\&=y_ky_lK(x_k,x_l),\ \ \ k,l=1,...,N \end{aligned}$Ωkl​​=yk​yl​φ(xk​)Tφ(xl​)=yk​yl​K(xk​,xl​),   k,l=1,...,N​
解上述方程组可以得到一组 α 和 b 。
最后得到LSSVM分类表达式：
$y(x)=sign\left[ \sum^N_{k=1}\alpha_k y_kK(x,x_k)+b\right]$y(x)=sign[∑k=1N​αk​yk​K(x,xk​)+b]

对比SVM，LSSVM的预测能力究竟怎么样呢，简单说来，由于是解线性方程组，LSSVM的求解显然更快，但标准基本形式的LSSVM的预测精准度比SVM稍差一些。

回归

如果说分类是用一个超平面将两组数据分开的话，LSSVM回归就是用一个超平面对已知数据进行拟合，问题如下：
$\begin{aligned} min_{w,b,e}J\left(w,e\right) &=\dfrac{1}{2}w^{T}w+\dfrac{1}{2}\gamma\sum^{N}_{k=1}e^2_{k}\\ s.t. \qquad y_{k}&=w^T\varphi\left(x_{k}\right)+b+e_k,\ \ \ k=1,\ldots,N \end{aligned}$minw,b,e​J(w,e)s.t.yk​​=21​wTw+21​γk=1∑N​ek2​=wTφ(xk​)+b+ek​,   k=1,…,N​

这里的 $y_k$yk​ 不再是表明类别的标签，而是我们需要估计函数中 y=f(x) 中的 y ，同样的，首先采用 Lagrange 乘数法：

$L\left(w,b,e;\alpha \right)=J\left(w,e\right)-\sum^{N}_{k=1}\alpha_{k}\left\{w^{T}\varphi(x_{k})-b+e_k-y_k\right\}$L(w,b,e;α)=J(w,e)−∑k=1N​αk​{wTφ(xk​)−b+ek​−yk​}

求导等于0：
$\begin{aligned} \dfrac {\partial L}{\partial \omega}&=0 \rightarrow w=\sum^N_{k=1}\alpha_k\varphi(x_k)\\ \dfrac {\partial L}{\partial b}&=0 \rightarrow \sum^N_{k=1}\alpha_k=0\\ \dfrac {\partial L}{\partial e_k}&=0 \rightarrow \alpha_k=\gamma e_k,\ \ \ k=1,...,N\\ \dfrac {\partial L}{\partial \alpha _k}&=0 \rightarrow w^T\varphi (x_k)+b+e_k-y_k=0, \ \ \ k=1,...,N \end{aligned}$∂ω∂L​∂b∂L​∂ek​∂L​∂αk​∂L​​=0→w=k=1∑N​αk​φ(xk​)=0→k=1∑N​αk​=0=0→αk​=γek​,   k=1,...,N=0→wTφ(xk​)+b+ek​−yk​=0,   k=1,...,N​
最后化为解下列线性方程组：
$\begin{bmatrix} 0 & 1_v^T\\ 1_v & \Omega+I/y \\ \end{bmatrix} \begin{bmatrix} b\\ \alpha \\ \end{bmatrix}= \begin{bmatrix} 0\\ y\\ \end{bmatrix}$[01v​​1vT​Ω+I/y​][bα​]=[0y​]
有核矩阵如下：
$\begin{aligned} \Omega _{kl}&=\varphi(x_k)^T\varphi(x_l)\\&=K(x_k,x_l),\ \ \ k,l=1,...,N \end{aligned}$Ωkl​​=φ(xk​)Tφ(xl​)=K(xk​,xl​),   k,l=1,...,N​
解上述方程组得到LSSVM回归函数：

$y(x)=\sum^N_{k=1}\alpha_k K(x,x_k)+b$y(x)=∑k=1N​αk​K(x,xk​)+b