最大间隔分类器

对线性可分的数据集而言，分类面的选择是无穷多的。希望找到一个离数据点最远的决策面，即SVM。SVM是基于向量空间的机器学习方法，从决策面到最近数据点的距离决定了分类器的间隔

SVM求解

对于一个超平面的决策边界而言

w^Tx+b=0

一个点到决策边界的欧氏距离是（ $y$ 取 $\pm1$ ）

r=y\dfrac{w^Tx+b}{||w||}

由于数据点可以放大，不妨要求所有点的函数间隔至少为1，并且至少有一个点的函数间隔为1

\min|w^Tx_i+b|=1

由于对称性，应当存在两个点 $x_a,x_b$ 使得

w^Tx_a+b=1\\ w^Tx_b+b=-1

也就是说

w^T(x_a-x_b)=2

这意味着

||x_a-x_b||=\dfrac{2}{||w||}

问题就转化为了使得 $||w||$ 最小，也即希望 $||w||^2$ 最小（去除根号），即求解一个二次函数优化问题

Note

希望找到向量 $w$ 和实数 $b$ 使得对于所有的样例点 $(x_i,y_i)$ 都有

y_i(w^Tx_i+b)\geq 1

并且使得下式取到最大值

w^Tw

求解这个问题可以使用拉格朗日对偶。对于每个不等式约束

$y_i(w^Tx_i+b)\geq1$

都引入一个拉格朗日因子 $\alpha_i$ ，构造拉格朗日函数

L(w,b,\alpha)=\dfrac12||w||^2-\sum_i\alpha_i[y_i(w^Tx_i+b)-1]

那么原问题的求解等价于求解

\max_\alpha\min_{w,b}L(w,b,\alpha)

为了求解它，将拉格朗日函数对 $w,b$ 求偏导并令其为零

\dfrac{\partial L}{\partial w}=w-\sum_i\alpha_iy_ix_i=0

\dfrac{\partial L}{\partial b}=\sum_i\alpha_iy_i=0

代入原问题，等价于求解

\max_\alpha\quad\sum_i\alpha_i-\dfrac12\sum_{i,j}\alpha_i\alpha_jy_iy_j(x_i^Tx_j)

求解得到 $\alpha$ 后，欲得到参数只需要

w=\sum_i\alpha_iy_ix_i\qquad b=y_k-w^Tx_k

其中 $(x_k,y_k)$ 是某一组使得 $y_k(w^Tx_k+b)\geq1$ 取等号的样例。分类函数就是

f(x)=sign(w^Tx+b)

或是直接用 $\alpha$ 写为

Note

f(x)=sign\left(\sum_i\alpha_iy_ix_i^Tx+b\right)

分类函数的符号决定了数据点的归属

如果由于误差的原因，训练数据并不是线性可分的，可以允许决策间隔犯一些错误。可以引入松弛变量 $\xi_i$ ，一个非零的 $\xi_i$ 表示对 $x_i$ 未满足间隔需求下的惩罚量。优化的问题变为

Note

希望找到向量 $w$ ，实数 $b$ 和非负向量 $\xi$ ，使得

y_i(w^Tx_i+b)\geq 1-\xi_i

并且使得下式最小

\sqrt{w^Tw}+C\sum_i\xi_i

其中的参数 $C$ 是用于调节过拟合的正则项

如果训练数据本身就不是线性可分的，可以考虑将数据映射到更高维的空间，并尝试使用线性分类。注意到原始的分类函数含有内积项

$f(x)=sign\left(\sum_i\alpha_iy_ix_i^Tx+b\right)$

只需要将低维的内积 $x^Tx$ 换为高维的内积即可

K(x_i,x_j)

$K$ 称为核函数，它形式上应该是映射到的高位向量的内积

K(x_i,x_j)=\varphi(x_i^T)\varphi(x_j)

不过实际上不需要真的做这个映射。有Mercer Theorem

Note

任何半正定对称函数都可以作为核函数

只需要找到一个核函数使得数据线性可分就行了