- 海之寻趣
- Ranler
- 2014-01-06 14:35
- CC NC-BY-SC
1. 最优超平面
对于线性可分问题，可以画出多个超平面把样本分成两类。 虽然这多个超平面都是分类器候选的解，但是当面对真实的测试样本时， 总有一些解表现比其它的解更好。
因此定义：一个超平面，如果它能够将训练样本没有错误地分开， 并且两类训练样本中离超平面最近的样本与超平面之间的距离是最大的， 则把这个超平面称为最优分类超平面(optimal seperating hyperplane), 简称最优超平面(optimal hyperplane)。 两类样本中离分类面最近的样本到分类面的距离称作分类间隔(margin)， 最优超平面也称作最大间隔超平面。
分类超平面公式为：
$g(x) = (w \bullet x) + b = 0$
对于不同的分类超平面，有不同的w和b。 记y为类别标号，则对于xi:
$\left\{\begin{matrix} (w \bullet x_i) + b >0 & y_i = +1\\ (w \bullet x_i) + b <0 & y_i = -1 \end{matrix}\right.$
然后调整尺度，把上式变成
$\left\{\begin{matrix} (w \bullet x_i) + b \geq 1 & y_i = +1\\ (w \bullet x_i) + b \leq -1 & y_i = -1 \end{matrix}\right.$
这样即可写成统一的形式：
$y_i[(w \bullet x_i) + b] \geq 1, i = 1,2,...,N$
这就叫做规范化的分类超平面。 其中g(x)=1和g(x)=-1就是过两类中各自离分类面最近的样本且与分类面平行的两个边界超平面。
样本x到超平面g(x)=0的距离是$\frac{|g(x)|}{\parallel x \parallel}$, 其中权向量的模$\parallel x \parallel = (w \bullet w)^{1/2}$。 因此，规范化之后，离分类面g(x)=0的最近的样本分别等于1和-1，那么分类间隔就是： $M=\frac{2}{\parallel w \parallel}$。 求分类间隔M最大，也就是求||w||最小，这样就表示成：
$\min \limits_{w,b} \frac{1}{2} \parallel w \parallel ^2$
$s.t. y_i[(w \bullet x_i) + b] - 1 \geq 0, i = 1,2,...,N$
这样，求最优超平面就是求分类超平面中$\parallel w \parallel^2$最小的分类超平面。
这是一个在不等式约束下的优化问题，可以通过拉格朗日法求解。 这需要对每个样本引入一个拉格朗日系数$a_i \gep 0, i = 1,...,N$。 通过一些方法（略去），最后可求得最优分类面的w为$w^ = \sum_{i=1}^{N}a_i^ y_i x_i$。
原本最优超平面定义的分类决策函数为：
$f(x) = sgn(g(x)) = sgn((w \bullet x) + b)$
再把w*代入上式，得：
$f(x) = sgn(g(x)) = sgn((w^* \bullet x) + b) = sgn(\sum_{i=1}^{N} a_i^* y_i (x_i \bullet x) + b^*)$
这中间还涉及到b的求解。 b通过把w*代入
$y_i[(w^* \bullet x_i) + b^*] - 1 = 0$
求得，在这里就不详细讨论了。
2. 线性支持向量机
在前一节可以看出，决定最优超平面位置的是由离分类面最近的那些样本。 这些样本被称为支持向量(support vectors)，它们往往只是训练样本中的一部分。 采用支持向量寻找最优超平面的方法叫做支持向量机(SVM, support vector machine)，简称SVM或SV机。
3. 非线性支持向量机
对于非线性问题，支持向量机采用引入特征变换将原低维空间中的非线性问题转化为新高维空间中的线性问题。 但是，支持向量机并不直接计算这种变换，而是采用了一种迂回的方法。
对x进行非线性变换得到的新特征z=p(x)。代入原决策函数：
$f(x) = sgn(g(x)) = sgn((w^* \bullet x) + b) = sgn(\sum_{i=1}^{N} a_i^* y_i (x_i \bullet x) + b^*)$
得到新特征空间的支持向量机决策函数：
$f(x) = sgn(w^p \bullet z + b) = sgn(\sum_{i=1}^n a_i y_i (p(x_i) \bullet p(x)) + b)$
此时，决定支持向量的等式是：
$y_i(\sum_{i=1}^n a_i (p(x_i) \bullet p(x)) + b) - 1 = 0$
由此可以看出，变换只是把原特征空间中的内积(x.x)变成了新空间中的内积(p(x).p(x))。 因此，新空间中的内积也是原特征空间的函数，可记作：
$K(x_i,x_j) = (p(x_i) \bullet p(x_j))$
这就称作核函数。
4. 常用的核函数
采用不同的核函数就得到不同形式的非线性支持向量机。 目前常用的的核函数主要有三种类型：
- 多项式核函数$K(x,x^{'}) = ((x \bullet x^{'}) + 1) ^ q$
- 径向基(RBF)核函数$K(x,x^{'}) = \textrm{exp}(-\frac{\parallel x - x^{'} \parallel ^2}{\sigma ^2})$
- Sigmoid函数$K(x,x^{'}) = \textrm{tanh}(v(x \bullet x^{'}) + c)$