Duxy's

a digged hole

支持向量机(SVM),核函数及优化

SVM包含三种类型:线性可分支持向量机、线性支持向量机、非线性支持向量机。不论哪一种类型,其主要目标就是求出一个超平面,将数据分开在该平面两边,同时让所有数据点离该平面都尽可能远(最大化最近的距离),用以增强分析结论的可靠性。其最大的特点是,决定该平面的只有离它最近的几个点,因此可以在特征较少的时候也能拟合出较好的参数。

SVM简介

SVM源于计算最小距离。最小距离有两类定义,一类比较直观,叫做几何距离,就是假定要找的超平面就是\(w^Tx+b\),那么对于数据\((x^{(i)},y^{(i)})\),它离超平面的距离即为\(w^Tx^{(i)}+b\),在平面同一侧的正负相同。\( y^{(i)}\in\{1,-1\} \),标记了两种分类。对于\(\gamma=y^{(i)}(w^Tx^{(i)}+b)\),若为正,则可表示分类正确,若为负,则表示分类有误,需要再次尝试查找超平面。

在该定义下,我们需要查找一个超平面,使其具有\(maxmin \gamma\)值,该超平面则为所求向量机。但是,由于\(w\)可以无限放大,所以在计算过程中,可以约定\(||w|| = 1\)。求解该问题使用拉格朗日算子,计算得到SVM原始优化问题的对偶问题后,快速求解。

对于线性不可分数据集,始终有\(\gamma \lt 0\)的存在,所以线性支持向量机就提供了容错机制。对于一些非线性分割,就需要使用一些机制将其数据映射到线性空间上,转化为线性分割,即可获得结果,这就是非线性支持向量。数据映射函数通常不容易获得,因此在支持向量机中,有着核函数机制,可以隐式的应用映射函数,而不需要具体的求解映射函数。

核函数的使用

核函数的实质是,将低维的数据集隐式的映射到高维空间乃至无穷维空间中,使其在高维空间获得线性可分特性,从而实现分类。由于是隐式映射,避免了高维空间和无穷维空间的表示,运算复杂度并未增加,甚至还会被简化,因而在计算复杂性上也有较好的体现。

核函数可按如下方式定义:
定义\(\phi(x)\),将\( \lt x^{(i)}, y^{(i)}> \)转为\( K=<\phi(x^{(i)}),\phi(y^{(i)})> \),其中K就为核函数。显然,K依赖于\(\phi\)的定义。

但是,K的设定并不需要确切的知道\(\phi\)。举个例子:定义\(K(x,z) = {(x^Tz)}^2\),当\(x = (x_1,x_2,x_3)\)时,
\[
\phi(x) = \left[\begin{matrix}
x_1x_1\\
x_1x_2\\
x_1x_3\\
x_2x_1\\
x_2x_2\\
x_2x_3\\
x_3x_1\\
x_3x_2\\
x_3x_3\\
\end{matrix}\right]
\]
显然,计算\(\phi(x)\)需要9次,而直接计算\(K\)仅需3次。同理,当\(x=(x_1,x_2,...x_n)\)时,计算\(\phi(x)\)需要\(n^2\)次,而计算\(K\)仅需要\(n\)次。这就是核函数的魅力所在了。

但是,在没有定义\(\phi(x)\)时,如何确定\(K\)函数合法呢?
直接定义矩阵
\[
\overline{K} = \left(\begin{matrix}
\overline{K}_{11} \overline{K}_{12} \overline{K}_{13} ... \overline{K}_{1n}\\
\overline{K}_{21} \overline{K}_{22} \overline{K}_{23} ... \overline{K}_{2n}\\
\overline{K}_{31} \overline{K}_{32} \overline{K}_{33} ... \overline{K}_{3n}\\
...\\
\overline{K}_{n1} \overline{K}_{n2} \overline{K}_{n3} ... \overline{K}_{nn}\\
\end{matrix}\right)
\]
其中,\(\overline{K}_{ij} = K(x^{(i)},x^{(j)})\)。可以证明,若\(\overline{K}\)是正定的,等价于\(K\)函数合法。

SMO优化

在计算SVM的对偶问题时,用到了拉格朗日算子,需要能够快速的计算出其中的变元值。通常情况下,我们会选择一个变元,固定除它以外所有变元的值,再对这个变元直接计算最优值,以此进行优化。但是,对偶问题中有一个强约束:\( \sum_{i=1}^{m}{\alpha_iy^{(i)}} = 0 \),选择单一变元进行优化一定会破坏该约束,因而有了SMO优化。

该优化的基本思想是:每次选两个变元进行优化,这样就能保证上述约束。于是,每次选择一个变元,然后从其他变元中找出他们俩合起来能够产生最大变化的一个变元,对这两个变元进行优化即可。