引子
线性支持向量机(LSVM)用来处理二分类问题。
拿二维平面来说，一个二维平面上有一堆白色和黑色的点，线性支持向量机求这样一条直线：该直线能够将二者分开——直线的一边全是白色的点，另一边全是黑色的点。
支持向量机的关键是“支持向量”，试看下图：
假设我们已经求取出了这样一条直线，那么支持向量就是离这条直线最近的样本点向量，就是图中落在虚线上的点。我们的目标是，求取出一条直线（超平面），使得超平面和支持向量之间的距离尽可能大。为什么？因为距离越大，表示两类样本点越泾渭分明。
0. 前置知识
点到直线的距离
假设我们有一个点$A(x_1,x_2,\cdots,x_n)$和一条直线$Y=k^TX+b$，那么该点到直线的距离为：
$$
d_{A-Y}=\frac{|k^TA+b|}{||k||}
$$
约束问题简化的拉格朗日方法
对于如下的约束问题：
$$
minf(x)\ s.t.\ \ g(x,y)<0
$$
则可简化为无约束问题：
$$
L(x,y,\lambda)=f(x)-\lambda (g(x,y)+k)
$$
这里，我们首先添加松弛变量$k$，令约束问题化为等式约束问题，接着构造上面的函数，通过下面式子求解：
$$
\frac{\partial L}{\partial x}=0,\frac{\partial L}{\partial y}=0,\frac{\partial L}{\partial \lambda}=0
$$
1. 初始问题的化简
根据引子里提到的内容，我们的问题可以记为：
求这样一条直线$Y=k^TX+b$，使得下列式子：
$$
\frac{k^TA+b}{||k||}\geq d,y=1
$$
$$
\frac{k^TA+b}{||k||}\leq -d,y = -1
$$
中的$d$尽可能大，由于我们只采用支持向量，所以取等号即可。这里的$y$用于表示样本点的类别，根据样本点的类别判断距离的正负。那么：
$$
d=\frac{y(k^TA+b)}{||k||}
$$
我们的问题等价于:
$$
max\frac{y(k^TA+b)}{||k||}
$$
不妨设分子为1，分子完全是一个尺度，表示支持向量到超平面的距离，假设为任意数不影响结果。那么我们的问题等价于:
$$
max\frac{1}{||k||}
$$
做个转换，方便后面求导：
$$
min\frac{1}{2}||k||^2\ s.t.\ \ \forall x_i\in D,y_i(k^Tx_i+b)= 1
$$
应用拉格朗日方法，和强对偶性，这里我略去了关于强对偶性的推导，转化为：
$$
\min_{w,b}\max_{\lambda}L(k, \lambda_i,b)=\frac{1}{2}||k||^2+\sum_{i=1}^n\lambda_i(1-y_i(k^Tx_i+b))
$$
记：
$$
f(k)=\frac{1}{2}||k||^2
$$
$$
g_i(k)=1-y_i(k^Tx_i+b)
$$
接着，求解：
$$
\frac{\partial L}{\partial k}=k-\sum y_i\lambda_ix_i=0
$$
$$
\frac{\partial L}{\partial b}=-\sum\lambda_iy_i=0
$$
$$
\frac{\partial L}{\partial \lambda_i}=g_i(k)=0
$$
代入回原来的式子，得到：
$$
\max_{\lambda_i}L(\lambda_i)=\sum \lambda_i-\frac{1}{2}\sum_{i,j=1}\lambda_i\lambda_jy_iy_jx_i^Tx_j
$$
带上约束条件：
$$
\max_{\lambda_i}L(\lambda_i)=\sum \lambda_i-\frac{1}{2}\sum_{i,j=1}\lambda_i\lambda_jy_iy_jx_i^Tx_j\ s.t.\ \ \sum\lambda_i y_i=0
$$
应用相应算法求解出$\lambda_i$之后，通过下面的式子，权重和bias都可求：
$$
k=\sum y_i\lambda_ix_i
$$
$$
y_i(k^Tx_i+b)=1
$$