支持向量机（SVM），核函数及优化 #
Date: 2015/6/12
SVM包含三种类型：线性可分支持向量机、线性支持向量机、非线性支持向量机。不论哪一种类型，其主要目标就是求出一个超平面，将数据分开在该平面两边，同时让所有数据点离该平面都尽可能远（最大化最近的距离），用以增强分析结论的可靠性。其最大的特点是，决定该平面的只有离它最近的几个点，因此可以在特征较少的时候也能拟合出较好的参数。moreSVM简介
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$函数合法呢？
直接定义矩阵
在计算SVM的对偶问题时，用到了拉格朗日算子，需要能够快速的计算出其中的变元值。通常情况下，我们会选择一个变元，固定除它以外所有变元的值，再对这个变元直接计算最优值，以此进行优化。但是，对偶问题中有一个强约束：$ \sum_{i=1}^{m}{\alpha_iy^{(i)}} = 0 $，选择单一变元进行优化一定会破坏该约束，因而有了SMO优化。
该优化的基本思想是：每次选两个变元进行优化，这样就能保证上述约束。于是，每次选择一个变元，然后从其他变元中找出他们俩合起来能够产生最大变化的一个变元，对这两个变元进行优化即可。