核函数

一、核心思想

在前面我们所讨论的分类器中，基本都是线性分类器，但是当数据集不存在一个线性的决策边界时，线性分类器便无法很好得进行分类。
事实证明，有一种优雅的方法可以将非线性问题合并到大多数的线性分类器可解决的问题中，即将线性分类器非线性化，这便是核函数。

我们可以看一个经典的例子：如下图所示的数据集，显然它是不存在线性的决策边界的，但是我们可以通过函数$~\phi~$对特征向量进行特征变换使得数据线性可分。

我们不妨将特征变换函数定义为：

$\phi(x)=\phi([x_1,x_2]^T)=[x_1,x_2,|x_1\cdot x_2|]^T$

我们所添加的维度捕捉了原始特征之间的非线性交互，使得数据变为了线性可分，升维的方法较为简便，并且使得问题保持凸且表现良好，但是缺点是升维可能会导致维度过高，使得模型变得复杂，比如下面这个例子所示：

通过特征变换，维度从$~d~$维变为了$~2^d~$维，这种新的表示法$~\phi(x)~$非常有表现力，允许复杂的非线性决策边界，但维数非常高。这使得我们的算法速度慢得令人无法忍受。

二、核技巧

核技巧是一种通过在更高维空间中学习函数来绕过这一困境的方法，而无需计算单个向量$~\phi(x)~$或完整向量$~w~$。

2.1 梯度下降

我们考虑平方损失函数的梯度下降过程：

$l(w)=\sum_{i=1}^n(w^Tx_i-y_i)^2$

在梯度下降过程中，我们每次需要选择一个步长进行更新：

$w_{t+1}=w_{t}-s\cdot(\frac{\partial l(w)}{\partial w})\\ \frac{\partial l(w)}{\partial w}=2\sum_{i=1}^n(w^Tx_i-y_i)\cdot x_i$

此处我们要引入一个重要的假设：我们可以将参数$~w~$表示为特征向量$~x_i~$的线性组合：

$w=\sum_{i=1}^n\alpha_ix_i$

根据该假设我们可以得到：$~w_{t+1}~$与$~x_i~$线性相关，$~w_t~$与$~x_i~$线性相关，由此：梯度$~\frac{\partial l(w)}{\partial w}~$与$~x_i~$线性相关：

$\frac{\partial l(w)}{\partial w}=2\sum_{i=1}^n(w^Tx_i-y_i)\cdot x_i=\sum_{i=1}^n\gamma_ix_i$

由于损失函数为凸函数，最终解与初始化无关我们可以将$~w_0~$初始化为我们想要的任何值，我们不妨令：

$w_0=[0,0,...,0]^T,\alpha^0=[0,0,...,0]^T$

根据上述分析我们可以得到梯度下降的过程为：

$\begin{aligned} &w_1=w_0-s\cdot2\sum_{i=1}^n(w_0^Tx_i-y_i)x_i=\sum_{i=1}^n\alpha_i^0x_i-s\sum_{i=1}^n\gamma_i^0x_i=\sum_{i=1}^n\alpha_i^1x_i~~~~\alpha^1=\alpha^0-s\gamma^0\\ &w_2=w_1-s\cdot2\sum_{i=1}^n(w_1^Tx_i-y_i)x_i=\sum_{i=1}^n\alpha_i^1x_i-s\sum_{i=1}^n\gamma_i^1x_i=\sum_{i=1}^n\alpha_i^2x_i~~~~\alpha^2=\alpha^1-s\gamma^1\\ &w_3=w_2-s\cdot2\sum_{i=1}^n(w_2^Tx_i-y_i)x_i=\sum_{i=1}^n\alpha_i^2x_i-s\sum_{i=1}^n\gamma_i^2x_i=\sum_{i=1}^n\alpha_i^2x_i~~~~\alpha^3=\alpha^2-s\gamma^2\\ &...\\ &w_t=w_{t-1}-s\cdot2\sum_{i=1}^n(w_{t-1}^Tx_i-y_i)x_i=\sum_{i=1}^n\alpha_i^{t-1}x_i-s\sum_{i=1}^n\gamma_i^{t-1}x_i=\sum_{i=1}^n\alpha_i^tx_i~~~~\alpha^t=\alpha^{t-1}-s\gamma^{t-1}\\ \end{aligned}$

因为$~\alpha^0_i=0~$，则有：

$\begin{aligned} &\alpha^1_i=~0~-s\gamma^0_i=-s\gamma^0_i\\ &\alpha^2_i=\alpha^1_i-s\gamma^1_0=-s\gamma^0_i-s\gamma^1_i\\ &\alpha^3_i=\alpha_i^2-s\gamma^2_i=-s\gamma^0_i-s\gamma^1_i-s\gamma^2_i\\ &...\\ &\alpha^t_i=\alpha_i^{t-1}-s\gamma^{t-1}_i=-s\sum_{r=1}^{t-1}\gamma_i^r \end{aligned}$

我们用$~x_i~$的线性组合代替$~w~$，得到新的模型和损失函数：

$h(x_i)=w_t^Tx_i=\sum_{j=1}^n\alpha_j^tx_j^Tx_i\\ l(w)=\sum_{i=1}^n(w^T_tx_i-y_i)^2=\sum_{i=1}^n(\sum_{j=1}^n\alpha_j^tx_j^Tx_i-y_i)^2$

由此我们可以发现：为了学习具有平方损失的超平面分类器，我们需要的唯一信息是所有数据的特征向量对之间的内积。

2.2 计算内积

有了上述推导，我们将模型简化为只需要求解向量对之间的内积，我们回归到上述的升维操作中去：

在升维之后，内积的计算公式为：

$\phi(x)^T\phi(z)=1+x_1z_1+x_2z_2+...x_1x_2...x_dz_1z_2...z_d=\prod_{k=1}^d(1+x_kz_k)$

我们可以发现，尽管特征向量是$~2^d~$维的，但是计算其内积仅需要$~d~$次乘法运算，这极大提高了算法的速度。

我们由此即可定义核函数：

$k(x_i,x_j)=\phi(x_i)^T\phi(x_j)$

核函数计算出的结果存储在核矩阵中：

$K_{ij}=\phi(x_i)^T\phi(x_j)$

诸如$~\phi~$之类的用于升维的映射并不好找，因此我们用核函数$~k(x_i,x_j)~$去代替这样的映射，处理线性不可分问题。

则上述模型可以表示为：可以发现模型中唯一的未知参数即为$~\alpha~$，我们需要对它进行求解

$h(x_i)=w^Tx_i=\sum_{j=1}^n\alpha_jx_j^Tx_i=\sum_{j=1}^n\alpha_jk(x_j,x_i)$

同时我们也已经得到了：

$\alpha^t_i=-s\sum_{r=1}^{t-1}\gamma_i^r$

所以当下我们的求解目标变为了$~\gamma~$：

$\frac{\partial l(w)}{\partial w}=2\sum_{i=1}^n(w^Tx_i-y_i)\cdot x_i=\sum_{i=1}^n\gamma_ix_i\\ \gamma_i=2(w^Tx_i-y_i)$

在经过$~\phi~$特征变换的新的高维空间中有：

$\gamma_i=2(w^T\phi(x_i)-y_i)=2(\sum_{j=1}^n\alpha_jk(x_j,x_i)-y_i)$

则梯度下降的过程为：

$\alpha_i^{t+1}=\alpha_i^t-s\gamma_i^t=\alpha_i^t-2s(\sum_{j=1}^n\alpha_j^tk(x_j,x_i)-y_i)$

梯度下降过程中，每次更新$~\alpha~$的计算量为$~O(n^2)~$，远好于$~O(2^d)~$

三、一般核函数

3.1 常用核函数

（1）线性核函数：

$K(x,z)=x^Tz$

（2）多项式核函数：

$K(x,z)=(1+x^Tz)^d$

（3）高斯核函数（$\text{RBF}$）：

$K(x,z)=e^{-\frac{||x-z||_2^2}{\sigma^2}}$

（4）指数核函数：

$K(x,z)=e^{-\frac{||x-z||}{2\sigma^2}}$

（5）拉普拉斯核函数：

$K(x,z)=e^{-\frac{|x-z|}{\sigma}}$

（6）$\text{Sigmoid}$核函数：$~\tanh(x)=\frac{e^x-e^{-x}}{e^x+e^{-x}}~$

$K(x,z)=\tanh(\gamma x^Tz+r)$

3.2 良定义核函数

良定义的核函数定义如下：通过递归组合以下一个或多个规则构建的核称为定义良好的核：

$\begin{aligned} &①~k(x,z)=x^Tz\\ &②~k(x,z)=ck_1(x,z)\\ &③~k(x,z)=k_1(x,z)+k_2(x,z)\\ &④~k(x,z)=g\big(k(x,z)\big)\\ &⑤~k(x,z)=k_1(x,z)\cdot k_2(x,z)\\ &⑥~k(x,z)=f(x)k_1(x,z)f(z)\\ &⑦~k(x,z)=e^{k_1(x,z)}\\ &⑧~k(x,z)=x^TAz \end{aligned}$

上述规则中$~k_1(x,z)~$和$~k_2(x,z)~$都是良定义的核函数，$~c\ge0~$，$~g~$是一个正系数多项式函数，$~f~$是任何函数，$~A~$是半正定的

某个核函数是良定义的等价为：
①核矩阵$~K~$的特征值都是非负的
②存在实矩阵$~P~$使得：$~K=P^TP~$
③核矩阵$~K~$是半正定的，即对于任何向量$~x~$，都有：$~x^TKx\ge0~$

定理 3-1

$\text{RBF}核函数：k(x,z)=e^{-\frac{(x-z)^2}{\sigma^2}}是良定义的$

证明如下：

$\begin{aligned} &k(x,z)=e^{-\frac{(x-z)^2}{\sigma^2}}=e^{-\frac1{\sigma^2}(x^Tx-2x^Tz+z^Tz)}=e^{-\frac{x^Tx}{\sigma^2}}\cdot e^{\frac{2x^Tz}{\sigma^2}}\cdot e^{-\frac{x^Tx}{\sigma^2}} \end{aligned}$

$\begin{aligned} &根据规则⑥：f(x)=e^{-\frac{x^Tx}{\sigma^2}},k_1(x,z)=e^{\frac{2x^Tz}{\sigma^2}}\rightarrow k(x,z)=f(x)\cdot k_1(x,z)\cdot f(z)\\ &根据规则⑦：k_2(x,z)=\frac{2x^Tz}{\sigma^2}\rightarrow k_1(x,z)=e^{k_2(x,z)}\\ &根据规则②：k_3(x,z)=x^Tz,c=\frac{2x^Tz}{\sigma^2}\rightarrow k_2(x,z)=c\cdot k_3(x,z)\\ &根据规则①：k_3(x,z)\text{ is well defined}\rightarrow k_2(x,z)\text{ is well defined}\rightarrow k_1(x,z)\text{ is well defined}\\ \end{aligned}$

综上推导：

$k(x,z)\text{ is well defined}$

定理 3-2

$S_1,S_2\in \Omega,k(S_1,S_2)=e^{|S_1\cap S_2|}是良定义的$

证明如下：

将$~\Omega~$中所有可能的元素排列成一个列表，$S_1,S_2$分别用一个大小为$~|\Omega|~$的向量$~x^{S_1},x^{S_2}~$表示，如果$~\Omega~$中的第$~i~$个元素属于$~S~$，则$~x^{S}_i=1~$，反之则$~x^{S}_i=0~$，则上述核函数可以表示为：

$\begin{aligned} &k(S_1,S_2)=e^{x_{S_1}^Tx_{S_2}} \end{aligned}$

根据规则⑦和规则①，我们可以得到：$~k(S_1,S_2)~$为良定义核函数。

四、模型核化

一个算法可以通过三步实现核化：
①证明解决方案位于训练点的范围内，即对于某些$~\alpha_i~$：

$w=\sum_{i=1}^n\alpha_ix_i$

②重构算法与分类器，使得输入的特征向量仅用于内积的计算
③将内积替换为核函数：

$x_i^Tx_j\rightarrow\phi(x_i)^T\phi(x_j)$

4.1 线性回归核化

我们回顾一下普通的最小二乘回归$~OLS~$：

$l(w)=\sum_{i=1}^n(x_i^Tw-y_i)\\ \hat{w}_{MLE}=\underset{w}{argmin}~\sum_{i=1}^n(x_i^Tw-y_i)\\ h(x)=w^Tx$

输入的训练集为$~X~$和$~Y~$，则其闭合形式为：

$w=(X^TX)^{-1}X^TY$

我们对该模型进行核化：$~X~$为$~n\times d~$维矩阵，$~Y~$为$~n\times1~$维矩阵，$~w,x_i~$为$~d\times1~$维矩阵，$~\alpha~$为$~n\times1~$维矩阵
①将$~w~$表示为$~x_i~$的线性组合：$~\alpha=[~\alpha_1,\alpha_2,...,\alpha_n~]^T~$

$\begin{aligned} &w=\sum_{i=1}^n\alpha_ix_i=X^T\alpha \end{aligned}$

②将模型修正为输入特征向量的内积：

$h(x_i)=\sum_{j=1}^n\alpha_jx_j^Tx_i=w^Tx_i=\alpha^TXx_i$

③用核函数代替内积：

$h(x_i)=\sum_{j=1}^n\alpha_jk(x_j,x_i)$

求解$~\alpha~$的闭合形式：

$\begin{aligned} &w=X^T\alpha=(X^TX)^{-1}X^TY\rightarrow X^TXX^T\alpha=X^TY\rightarrow XX^T\alpha=Y\\ &K_{ij}=k(x_i,x_j)\rightarrow K=XX^T\rightarrow K\alpha=Y\\ &\alpha=K^{-1}Y \end{aligned}$

岭回归同理，我们也可以实现同样的核化并求解$~\alpha~$的闭合形式：

模型为：

$l(w)=\sum_{i=1}^n(x_i^Tw-y_i)+\lambda||w||_2^2\\ \hat{w}_{MAP}=\underset{w}{argmin}~\sum_{i=1}^n(x_i^Tw-y_i)+\lambda||w||_2^2\\ h(x)=\sum_{j=1}^n\alpha_jk(x_j,x_i)$

$~\alpha~$的闭合形式为：

$\begin{aligned} &w=X^T\alpha=(X^TX+\lambda I)^{-1}X^TY\rightarrow (X^TX+\lambda I)X^T\alpha=X^TY\\ &\rightarrow (X^TXX^T+\lambda X^T)\alpha=X^TY\rightarrow (XX^T+\lambda I)\alpha=Y\\ &\rightarrow \alpha=(K+\lambda I)^{-1}Y \end{aligned}$

4.2 KNN核化

我们以欧拉距离的$~KNN~$模型为例：

$\text{dist}(x_i,x_j)=(x_i-x_j)^T(x_i-x_j)=x_i^Tx_i-2x_i^Tx_j+x_j^Tx_j=k(x_i,x_i)-2k(x_i,x_j)+k(x_j,x_j)$

但是上述核化的意义并不大，因此我们一般不对$~KNN~$算法进行核化。

4.3 支持向量机核化

线性支持向量机结合核函数是一个很强大的模型，我们往往求解其对偶问题，所以我们需要先了解对偶问题的定义。

4.3.1 拉格朗日乘子法与KKT条件

在求解最优化问题中，拉格朗日乘子法（Lagrange Multiplier）和KKT（Karush Kuhn Tucker）条件是两种最常用的方法。在有等式约束时使用拉格朗日乘子法，在有不等约束时使用KKT条件。

我们这里提到的最优化问题通常是指对于给定的某一函数，求其在指定作用域上的全局最小值，支持向量机模型即为该类最优化为问题。

在求解最优化问题时一般会遇到三种情况：

（1）无约束条件：
这是最简单的情况，解决方法通常是函数对变量求导，令求导函数等于0的点可能是极值点。将结果带回原函数进行验证即可。

（2）等式约束条件：
设目标函数为$~f(x)~$，约束条件为$~h_k(x)~$，有$~l~$个约束条件，则等式约束条件的最优化问题可以表示为：

$\begin{aligned} &求解目标：\min f(x)\\ &约束条件：h_k(x)=0,k=1,2,...l \end{aligned}$

我们要用到拉格朗日乘子法处理该最优化问题：首先定义拉格朗日函数：

$F(x.\lambda)=f(x)+\sum_{k=1}^l\lambda_kh_k(x)$

然后解变量的偏导方程：

$\frac{\partial F(x,\lambda)}{\partial x_1}=0,\frac{\partial F(x,\lambda)}{\partial x_2}=0,...,\frac{\partial F(x,\lambda)}{\partial x_d}=0\\ \frac{\partial F(x,\lambda)}{\partial \lambda_1}=0,\frac{\partial F(x,\lambda)}{\partial \lambda_2}=0,...,\frac{\partial F(x,\lambda)}{\partial \lambda_k}=0$

（3）不等式约束条件：
设目标函数为$~f(x)~$，不等式约束条件为$~g_k(x)~$，有$~q~$个不等式约束条件，等式约束条件为$~h_j(k)~$，有$~p~$个等式约束条件：

$\begin{aligned} &求解目标：\min f(x)\\ &约束条件：h_j(x)=0,j=1,2,...,p\\ &~~~~~~~~~~~~~~~~~g_k(x)\le0,k=1,2,...,q \end{aligned}$

则我们可以定义不等式约束条件下的拉格朗日函数为：

$L(x,\lambda,\mu)=f(x)+\sum_{j=1}^p\lambda_jh_j(x)+\sum_{k=1}^q\mu_kg_k(x)$

常用的方法是$~KKT~$条件：即最优值（局部最小值）必须满足以下条件：

$\begin{aligned} &①~\frac{\partial L(x,\lambda,\mu)}{\partial x}|_{x=x^*}=0\\ &②~h_j(x^*)=0\\ &③~\mu_kg_k(x^*)=0 \end{aligned}$

4.3.2 对偶问题的核化

我们首先回顾支持向量机的模型：为了便于计算我们引入一个常系数$~\frac12~$

$\begin{aligned} &求解目标：(w,b)=\underset{w,b}{argmin}~\frac12||w||^2_2\\ &约束条件：\forall i~,~y_i(w^Tx_i+b)\ge 1 \end{aligned}$

则拉格朗日函数为：

$L(w,b,\alpha)=\frac12||w||_2^2+\sum_{i=1}^n\alpha_i\big(1-y_i(w^Tx_i+b)\big)$

根据$~KKT~$条件可得：

$\begin{aligned} &\frac{\partial L(w,b,\alpha)}{\partial w}=w-\sum_{i=1}^n\alpha_iy_ix_i=0\\ &\frac{\partial L(w,b,\alpha)}{\partial b}=-\sum_{i=1}^n\alpha_i y_i=0 \end{aligned}$

我们同时也知道，在$~w,b~$取得最优值时有：$~y_i(w^Tx_i+b)=1~$满足了$~KKT~$条件

综上，我们可得：

$\begin{aligned} &w=\sum_{i=1}^n\alpha_iy_ix_i\\ &\sum_{i=1}^n\alpha_iy_i=0 \end{aligned}$

我们上述条件代入原式可得：

$\begin{aligned} &(w,b)=\underset{w,b}{argmin}~\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j+\sum_{i=1}^n\alpha_i-\sum_{i=1}^n\sum_{j=1}^n\alpha_iy_iy_jx_i^Tx_j-b\cdot\sum_{i=1}^n\alpha_iy_i\\ &\rightarrow(w,b)=\underset{w,b}{argmin}~\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j \end{aligned}$

由此我们得到了支持向量机模型的对偶问题：

$\begin{aligned} &求解目标：\alpha=\underset{\alpha}{argmax}~\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\\ &约束条件：\sum_{i=1}^n\alpha_iy_i=0 \end{aligned}$

显然我们可以对该对偶问题进行核化：

$\alpha=\underset{\alpha}{argmax}~\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jk(x_i,x_j)$

最终的模型为：

$h(x)=\text{sign}(w^Tx+b)=\text{sign}\big(\sum_{i=1}^n\alpha_iy_ik(x_i,x)+b\big)$

从支持向量的角度对对偶问题有一个很好的解释：对于原始公式，我们知道只有支持向量满足等式约束：

$y_i\big(w^T\phi(x_i)+b\big)=1$

在对偶问题中我们可以使得支持向量所对应的$~\alpha_i>0~$，而其他的输入向量对应的$~\alpha_i=0~$，在测试时我们只需要计算支持向量上$~h(x)~$的和，并在训练后丢弃所有$~\alpha_i=0~$的特征向量。

对偶有一个明显的问题，就是$~b~$不再是优化的一部分了，但是我们需要它来进行分类，在对偶中支持向量是那些$~α_i>0~$的向量，因此我们可以推导出$~b~$：

$\begin{aligned} &y_i(w^T\phi(x_i)+b)=1,y_i\in\{-1,+1\}\rightarrow b=y_i-w^T\phi(x_i)\\ &\rightarrow b=y_i-\sum_{j=1}^n\alpha_jy_jk(x_j,x_i) \end{aligned}$

同时如果使用软间隔模型，则仅需添加一个新的约束：

$0\le\alpha_i\le C$

五、模型实现

我们本次要手动实现核化的软间隔支持向量机，主要运用其对偶问题求解最优化问题。

5.1 数据集

我们本次要生成线性不可分的数据集，因为这样才能体现出核函数的优势所在，生成线性不可分数据集的代码如下所示：我们主要用到的是sklearn所提供的make_moons生成双半月环数据集，这是一个经典的线性不可分数据集。

'''屏蔽warning'''
import warnings
warnings.filterwarnings("ignore")
'''导入重要库'''
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from sklearn.datasets import make_moons

'''生成数据'''
data,target=make_moons(n_samples=1000,noise=0.1)
'''可视化'''
ax=plt.figure(figsize=(7,4),dpi=100).add_subplot()#初始化画板
plt.scatter(data[:,0],data[:,1],c=target)
plt.show()
'''存储数据集'''
df=pd.DataFrame(data=data,columns=["feature1","feature2"])
df['label']=target
df.to_csv("data/moons_data.csv",index=False)

生成的数据集如下图所示：

5.2 手动实现模型

5.2.1 模型阐述

求解思路来自：支持向量机（SVM）——对偶问题

我们首先要了解对于对偶形式的支持向量机模型的求解方法，考虑到软约束，我们的模型为：

$\begin{aligned} &求解目标：\alpha=\underset{\alpha}{argmax}~\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\\ &约束条件：\sum_{i=1}^n\alpha_iy_i=0,0\le\alpha_i\le C \end{aligned}$

我们最后求解出的模型为：

$h(x_i)=\sum_{j=1}^n\alpha_jy_jx_j^Tx_i+b$

我们首先实现该模型的代码：

'''模型计算值h(xi)'''
def _h(self,i):
    r=self.b
    for j in range(self.n):
        r+=self.alpha[j]*self.Y[j]*self.kernel(self.X[j],self.X[i])
    return r

基于原始模型以及我们作出的假设，$~KKT~$条件为：

$\begin{aligned} \left\{ \begin{aligned} &0\le\alpha_i\le C\\ &y_i\cdot h(x_i)-1\ge 0\\ &\alpha_i(y_i\cdot h(x_i)-1)=0 \end{aligned} \right. \end{aligned}$

因为我们有：支持向量所对应的$~\alpha_i>0~$，而其他的输入向量对应的$~\alpha_i=0~$的设定，支持向量是那些满足$y_ih(x_i)=1$的点，所以有：

$\alpha_i(y_i\cdot h(x_i)-1)=0$

接着我们需要求解核心问题：

$\alpha=\underset{\alpha}{argmax}~\sum_{i=1}^n\alpha_i-\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j\\$

5.2.2 求解思路

这是一个二次规划问题，我们用到$~SMO~$算法对其进行求解，算法思路来自：SMO算法详解

我们不妨先将问题作一个变形：

$\alpha=\underset{\alpha}{argmin}~\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^n\alpha_i\\$

我们要寻找一个满足约束条件的$~\alpha=[~\alpha_1,\alpha_2,...,\alpha_n~]~$，假设我们已经找到了这样的一个$~\alpha~$，即最终的超平面已经确定：

$h(x_i)=w^Tx_i+b$

那么该超平面是满足$~KKT~$条件的，则有：

$\begin{aligned} &\left\{ \begin{aligned} &y_i\cdot h(x_i)\ge1\rightarrow ~~~~\alpha_i=0~~~~,x_i在边界内，正确分类\\ &y_i\cdot h(x_i)=1\rightarrow 0<\alpha_i< C,x_i在边界上，是支持向量，正确分类\\ &y_i\cdot h(x_i)\le1\rightarrow ~~~~\alpha_i=C~~~~,x_i在两条边界之间 \end{aligned} \right. \end{aligned}$

反过来想，我们求解出来的$~\alpha_i~$和$~x_i~$也要满足上述关系。

综上我们的求解过程便是初始化一个$~\alpha~$并不断得对其进行优化，直到找到最优的那个$~\alpha~$，$~SMO~$算法每次选择两个$~\alpha_i,\alpha_j~$进行更新。
根据我们的约束，显然这两个$~\alpha_i,\alpha_j~$满足：

$\alpha_iy_i+\alpha_jy_j=-\sum_{k=1,k\not=i,j}^n\alpha_ky_k=\xi$

因此有：

$\alpha_i=\frac{\xi-\alpha_jy_j}{y_i}=(\xi-\alpha_jy_j)y_i~,~y_i\in\{-1,+1\}$

因此我们只需要找到一个$~\alpha_j~$进行优化，并且求出优化后的值，那么我们的$~\alpha_i~$也完成了优化，为了便于表示，后面我们将挑选出的两个$~\alpha_i,\alpha_j~$记作$~\alpha_1,\alpha_2~$

从效果上考虑我们应该优化那些最不满足目标条件的$~\alpha_i~$，而在我们优化过后它不满足目标条件的程度应该减小，而我们为了衡量一个$~\alpha_i~$满足目标条件的程度，引入一个指标：我们首先定义一个误差：

$E_i=h(x_i)-y_i$

我们发现$~|E_1-E_2|~$越大，优化后的$~\alpha_1,\alpha_2~$满足目标条件的程度就越大。

计算$~E_i~$的代码如下所示：

'''计算Ei'''
def _E(self,i):
	return self._h(i)-self.Y[i]

接着我们思考一个问题：我们该怎样确定优化后的$~\alpha~$是朝着不满足目标条件程度减小的方向移动的呢？
我们回归到原始的问题：

$\begin{aligned} &求解目标：\alpha=\underset{\alpha}{argmin}~\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jx_i^Tx_j-\sum_{i=1}^n\alpha_i\\ &约束条件：\sum_{i=1}^n\alpha_iy_i=0,0\le\alpha_i\le C \end{aligned}$

我们求解目标是求解目标函数的局部最小值，那么我们不妨将$~\alpha_1,\alpha_2~$看作变量，其他$~\alpha_i~$看作常量，则：

$\alpha=\underset{\alpha}{argmin}~W(\alpha_1,\alpha_2)\\ W(\alpha_1,\alpha_2)=A\alpha_1^2+B\alpha_2^2+C\alpha_1\alpha_2+D\alpha_1+E\alpha_2+F$

代入$~\alpha_1=(\xi-\alpha_2y_2)y_1~$可得：

$\begin{aligned} &W(\alpha_2)=A\big[(\xi-\alpha_2y_2)y_1\big]^2+B\alpha_2^2+C(\xi-\alpha_2y_2)y_1\alpha_2+D(\xi-\alpha_2y_2)y_1+E\alpha_2+F\\ &~~~~~~~~~~~~~=(A+B-Cy_1y_2)\alpha_2^2+(E-2Ay_2-Dy_1y_2)\alpha_2+A\xi^2+(C+D)\xi+F \end{aligned}$

那么求$~W~$的极小值，只需要简单得令$~\frac{\partial W(\alpha_2)}{\partial \alpha_2}=0~$即可，即：

$2(A+B-Cy_1y_2)\alpha_2+(E-2Ay_2-Dy_1y_2)=0$

最终我们只需要保证我们优化后得$~\alpha~$是使得目标函数变小的，就可以确定优化后的$~\alpha~$是朝着不满足目标条件程度减小的方向移动。

5.2.3 SMO算法

$~\alpha_1,\alpha_2~$的更新

为了处理线性不可分的数据，我们引入了核函数：

$\begin{aligned} &求解目标：\alpha=\underset{\alpha}{argmin}~\frac12\sum_{i=1}^n\sum_{j=1}^n\alpha_i\alpha_jy_iy_jk(x_i,x_j)-\sum_{i=1}^n\alpha_i\\ &约束条件：\sum_{i=1}^n\alpha_iy_i=0,0\le\alpha_i\le C \end{aligned}$

核函数的实现代码如下所示，我们有多样的选择：

'''核函数'''
def kernel(self,xi,xj):
    if self._kernel=="linear":  #线性核函数
        return np.dot(xi,xj)
    if self._kernel=="poly":    #多项式核函数
        return (1+np.dot(xi,xj))**self.d
    if self._kernel=="gauss":   #高斯核函数
        return np.exp(-((xi-xj)**2).sum()/self.sigma**2)

优化前后$~\alpha~$都必须满足$~\sum_{i=1}^n\alpha_iy_i=0~$，即：

$\alpha_1^{new}y_1+\alpha_2^{new}y_2=\alpha_1^{old}y_1+\alpha_2^{old}y_2=\xi$

在更新$~\alpha_1,\alpha_2~$时，有：

$\alpha_1=(\xi-\alpha_2y_2)y_1\\ 0\le\alpha_1\le C,0\le\alpha_2\le C$

将上述两个信息结合我们可以进一步得缩小$~\alpha_2~$的范围：我们将$~\alpha_2~$的上界与下界定义为$~H,L~$

$\begin{aligned} &L\le\alpha_2\le H \end{aligned}$

将$~\alpha_1y_1+\alpha_2y_2=\xi~$看作一个方程，显然几何上这是一条直线，结合取值范围我们可以绘制出图像：

（1）$~y_1\not=y_2~$时：有两种情况：$~\alpha_1-\alpha_2=\xi~$，$~\alpha_1-\alpha_2=-\xi~$

$\begin{aligned} &0\le\alpha_2\le C\\ &0\le\alpha_1=\alpha_2+\xi\le C\rightarrow -\xi\le\alpha_2\le C-\xi\\ &0\le \alpha_1=\alpha_2-\xi\le C\rightarrow ~~~\xi\le\alpha_2\le C+\xi\\ \end{aligned}$

①$~\alpha_1-\alpha_2=\xi~$时：

$\begin{aligned} &~L=\max(0,-\xi)=\max(0,\alpha_2-\alpha_1)\\ &~H=\min(C,C-\xi)=\min(C,C+\alpha_2-\alpha_1) \end{aligned}$

②$~\alpha_1-\alpha_2=-\xi~$时：

$\begin{aligned} &L=\max(0,\xi)=\max(0,\alpha_2-\alpha_1)\\ &H=\min(C,C+\xi)=\min(C,C+\alpha_2-\alpha_1) \end{aligned}$

可以发现两种情况所得的上下界求解公式相同。

（2）$~y_1=y_2~$时，有两种情况：$~\alpha_1+\alpha_2=\xi~$，$~\alpha_1+\alpha_2=-\xi~$，推导过程与$~y_1\not=y_2~$时的完全相同：

$\begin{aligned} &0\le\alpha_2\le C\\ &0\le\alpha_1=~~\xi-\alpha_2\le C~\rightarrow ~~~\xi-C\le\alpha_2\le\xi\\ &0\le\alpha_1=-\xi-\alpha_2\le C\rightarrow-\xi-C\le\alpha_2\le-\xi \end{aligned}$