基础知识

线性可分

D0 和 D1 是 n 维欧氏空间中的两个点集（点的集合）。如果存在 n 维向量 w 和实数 b，使得所有属于 D0 的点 xi 都有 wxi+b>0，而对于所有属于 D1 的点 xj 则有 wxj+b<0。则我们称 D0 和 D1 线性可分

超平面

n 维欧氏空间中维度等于 n-1 的线性子空间

线性分类模型（线性分类器）

将线性可分的样本用超平面分隔开的分类模型

最佳超平面（最大间隔超平面）

1. 两类样本分别分隔在该超平面的两侧；
2. 两侧距离超平面最近的样本点到超平面的距离被最大化了。

对偶性

弱对偶性

$minmaxf\geq maxminf$

强对偶性

$minmaxf=maxminf$

如果f是凸优化问题，强对偶性成立

KKT条件

KKT条件是非线性规划最佳解的必要条件，将Lagrange乘数法所处理涉及等式的约束优化问题推广至不等式。在实际应用上，KKT条件(方程组)一般不存在代数解。

等式约束优化问题

$minf(\overrightarrow{x}), s.t. g(\overrightarrow{x})=0$

假设$f(x),g(x)$为连续可导函数，定义拉格朗日函数$L(\overrightarrow{x},\lambda)=f(\overrightarrow{x})+\lambda g(\overrightarrow{x})$，将原本的约束优化问题转换成等价的无约束优化问题$min_{\overrightarrow{x},\lambda}L(\overrightarrow{x},\lambda)$，求偏导，得最优解的必要条件：

$\nabla_xL=\nabla f+\lambda \nabla g\space定常方程式\\\nabla_\lambda L=\nabla g\space约束条件$

不等式约束优化问题

$minf(\overrightarrow{x}),s.t.g(\overrightarrow{x})\leq0$

设$x^*$为满足条件的最优解，分两种情况讨论

1. $g(x^*)<0$，最佳解位于可行域内部，称为内部解，此时约束条件无效，问题退化成无约束优化问题，则$\nabla f=0,\lambda=0$

2. $g(x^)=0$，最佳解位于可行域边界，称为边界解，此时约束条件有效，我们可以证明驻点$x^$发生于$\nabla f\in span\nabla g$，即存在$\lambda$使得$\nabla f=-\lambda\nabla g$，由于我们希望最小化f，所以此时$\nabla f$（函数在点的最陡上升方向）应该指向可行域的内部，然而$\nabla g$指向可行域的外部（即$g(x)>0$的区域），因此$\lambda\geq0$，这个结论称为对偶可行性

   综上，$\lambda g(x)=0$恒成立，称为互补松弛性

综上，最佳解的必要条件包括Lagrangian函数的定常方程式、原始可行性、对偶可行性，以及互补松弛性，这些条件合称为Karush-Kuhn-Tucker (KKT)条件，在使用KKT条件时，约束条件有一定的限制，这里我们简单的将其视为仿射函数（实际上有很多，但我毕竟不是学数学的）

KKT条件是强对偶性的充要条件

支持向量机

目的

找出线性可分的样本在特征空间中的最大间隔超平面

直观操作

我们可以先找到两个平行的，能够分离正负例的辅助超平面，然后将它们分别推向正负例两侧，使得它们之间的距离尽可能大，一直到有至少一个正样本或者负样本通过对应的辅助超平面为止——推到无法再推，再推就“过界”为止。这两个超平面互相平行，它们范围内的区域称为“间隔”，最大间隔超平面位于这两个辅助超平面正中的位置与它们平行的超平面

三个超平面分别为

1. wx+b=1
2. wx+b=0（最佳超平面）
3. wx+b=-1

具体操作

通过几何易知两个超平面距离为$\frac{2}{||x||_2}$，因此我们只需最小化$||x||_2$

同时，由两个超平面的定义我们可知，我们需要满足约束$(y=1 \& wx+b>=1)|(y=-1 \& wx+b<=-1)$，化简得$y(wx+b)>=1$

这里为方便计算，我们选择最小化$||x||_2^2$

将约束转化为$g_i(w)=1-y_i(w^Tx_i+b)\leq0$，

故我们可以将最优化问题转换为$min_wmax_\lambda L(w,\lambda)$

SVM优化

首先构建拉格朗日函数，后利用强对偶性将问题转化，对w，b求偏导，带回函数，得到：

$max_\lambda[\sum_{j=1}^n\lambda_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_j(x_ix_j)],s.t.\sum_{i=1}^n\lambda_iy_i=0(\lambda_i\geq0)$

这是个二次规划问题，我们一般用SMO（序列最小优化算法）求解，其核心思想非常简单：每次只优化一个参数，其他参数先固定住，仅求当前这个优化参数的极值，但我们的优化目标有约束条件，因此具体步骤为：

1. 选择两个需要更新的参数$\lambda_i$和$\lambda_j$，固定其他参数
2. 用带$\lambda_i$的表达式替换$\lambda_j$，求偏导，令导数为0
3. 多次迭代直至收敛

由此得到$w=\sum_{i=1}^m\lambda_iy_ix_i,b=\frac{\sum_{s\in S}(y_s-wx_s)}{|S|}$

构造最大分割超平面：$w^Tx+b=0$

软间隔

如果遇到不能完全线性可分的样本，我们引入松弛变量$\xi_i$，此时约束为$g(x)=1-y_i(w^Tx_i+b)-\xi_i\leq0$

优化目标为：$min\frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i$

构造拉格朗日函数：$min_{w,b,\xi}max_{\lambda,\mu}L(w,b,\xi,\lambda,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^m\xi_i+\sum_{i=1}^n\lambda_i[1-\xi_i-y_i(w^Tx_i+b)]-\sum_{i=1}^n\mu_i\xi_i$

同上步骤，得到$max_\lambda[\sum_{j=1}^n\lambda_i-\frac{1}{2}\sum_{i=1}^n\sum_{j=1}^n\lambda_i\lambda_jy_iy_j(x_ix_j)],s.t.\sum_{i=1}^n\lambda_iy_i=0(\lambda_i\geq0),C-\lambda_i-\mu_i=0$

利用SMO算法求解

w，b同上

线性不可分

对于线性完全不可分的样本，我们使用核函数映射到更高维的向量空间再求解，具体可见核函数