# 支持向量机（SVM） ## 支持向量 对线性可分的目标样本集，找到分别适合两类样本的两个互相平行的最大限度线性划分（有最多的样本点与线性划分重合），再从两个最大限度线性划分中取得一条中间夹线，即为预期拟合效果最好的线性划分。这三个平行的线性划分的方向可以看作一个支持向量。  在任意维度下有$m$个样本，则有： - 超平面分类器：$\mathbf{W}\cdot \mathbf{X} + \mathbf{b} = 0$ - 判决函数：$y_i=sgn(\mathbf{W}x_i+b),\space y_i\in\{-1,1\},\space i = 1,2,\cdots,m$ - 间距：$margin=2/||\mathbf{W}||$ > - $\mathbf{W}$实际上是该超平面的一个法向量 > - $\mathbf{W}x+b\ne 0$ 时，也就是当$x$不在该超平面上时，根据几何关系，该点在超平面一侧值为正，另一侧为负 为了使得间距最大，即求$\min||\mathbf{W}||$，可转化为$\min\frac{1}{2}||\mathbf{W}||^2$，在$n$个约束条件的情况下的条件极值，再使用拉格朗日乘数法： $$L(\mathbf{\omega}, b, \lambda) = \frac{1}{2}||\mathbf{\omega}||^2-\sum_{i=1}^m\lambda_i[y_i \cdot (\mathbf{\omega} x_i + b) - 1]$$ 可求得线性的核函数。 ## 求法：对偶问题  ### SMO  ## 核函数 若低维空间不可分，可使用核方法映射至高维线性可分空间。由于求解SVM问题只需要计算样本两两内积，因此只要在低维空间中存在函数$K(x_1,x_2) = z_1\cdot z_2,\space (x_1,x_2)\in X$，也就是将低维空间$X$的两个样本映射为某个高维空间中这两个样本的内积，则称$K$为一个核函数。常见核函数有： - 线性核函数（无核）：$K(x_i,x_j)=x_i\cdot x_j+c$ - 多项式核函数：$K(x_i,x_j)=[a\cdot x_i \cdot x_j+c]^d$ - 高斯核函数（径向基核函数）：$K(x_i,x_j)=\displaystyle\exp(-\frac{||x_i-x_j||^2}{2a^2})$