间隔与支持向量
有类别的数据需要被分为两类，通过一个最优超平面将其分为两部分，推理的时候在最优超平面一边的为一类，在另一边的为另一类，最优超平面定义为$w^Tx+b=0$，模型为$f(x)=w^Tx+b$。
现在的问题是如何求得这个最优超平面，根据点到直线的距离，从支持向量到最优超平面的距离为$\frac{wx+b}{|w|}$，求最小距离时，即求支持向量到最优超平面的距离，因为对于支持向量有$wx+b=1$,目标转为$min \ w$
最优化的目标转化为：
$min\frac{1}{2}||w||^2$
$s.t. \ y_i(w^Tx_i+b)>=1, i=0, 1, 2, 3…m$ 式6.6
对偶问题
目的：利用式6.6的对偶问题得到模型$f(x)$
使用朗格朗日乘子法可以解式6.6， 对式6.6点每个约束条件加拉格朗日乘子$\alpha_i$,该问题的拉格朗日式表示为：
$L(w, b, \alpha)=\frac{1}{2}||w||^2+\sum_{i=1}^m\alpha_i(1-y_i(w^Tx_i+b))$ 式6.8
令L对$w$和b偏导为0：
$w=\sum_{i=1}^m\alpha_i y_ix_i$ 6.9
$\sum_{i=0}^m\alpha_iy_i=0$ 6.10
将这两个偏导得到的条件代入6.8式，可以消去w和b，6.9代入6.8，消去w，b由6.10整体代入消除；得到式6.6的对偶问题：
$max \ \sum_i^m\alpha_i-\frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_jx^T_ix_j$ 式6.11
$s.t. \ \sum_{i=1}^{m}\alpha_iy_i=0$
$\alpha_i>=0$
挖坑：为什么这里可以通过式6.6点对偶问题得到6.6的解？
解出式6.11中的$\alpha_i,\alpha_j$就可以得到w, 从而得到模型：
$f(x)=wx+b=\sum_{i=1}^m\alpha_iy_ix_ix+b$
利用smo算法求解6.11式
smo的思想是选取一对需要更新的参数$\alpha_i, \ a_j$其他参数固定，根据式6.11的约束条件，将一个变量用另外一个变量表示，6.11变成二次凸优化问题，解出$\alpha_i,\alpha_j$，具体的：
式6.11的约束条件重新写为：$\alpha_{i}y_{i}+\alpha_{j}y_{j}=c$
将上式$\alpha_{j}$用$\alpha_{i}$表示：$\alpha_{j}=\frac{c-\alpha_{i}y_{i}}{y_{j}}$
式6.11此时变成只有一个变量的二次函数，仅有的约束是$\alpha_{i}$大于0.
b的求解可以通过支持向量的$y_sf(x_s)=1$解出
$y_s(wx+b)=1$-> $b=\frac{1}{y_s}-wx$，更鲁棒一点的可以对所有的支持向量求均值
核函数
原先的输入空间可能是线性不可分的，将其映射到高维空间后就可以分了
$x->\phi(x)$
模型$f(x)=wx+b$变成$f(x)=w^T\phi(x)+b$
最优化问题
$min\ \frac{1}{2}||w||^2$
$s.t.\ y_i(wx_i+b)>=1$
用拉格朗日解法，其对偶问题为：
$max\ \sum_{i=1}^{m}\alpha_i+\sum_{i=1}^{m}\sum_{j=1}^{m}\alpha_i\alpha_jy_iy_j\phi(x_i)^T\phi(x_j)$
$s.t.\ \alpha_iy_i=0$
由于$\phi(x_i)\phi(x_j)$的计算量可能很大，用核函数$k(x_i, x_j)$替代