支持向量机（SVM），核函数及优化 #
Date: 2015/6/12
SVM包含三种类型：线性可分支持向量机、线性支持向量机、非线性支持向量机。不论哪一种类型，其主要目标就是求出一个超平面，将数据分开在该平面两边，同时让所有数据点离该平面都尽可能远（最大化最近的距离），用以增强分析结论的可靠性。其最大的特点是，决定该平面的只有离它最近的几个点，因此可以在特征较少的时候也能拟合出较好的参数。moreSVM简介
SVM源于计算最小距离。最小距离有两类定义，一类比较直观，叫做几何距离，就是假定要找的超平面就是wTx+b，那么对于数据(x(i),y(i))，它离超平面的距离即为wTx(i)+b，在平面同一侧的正负相同。y(i)∈1,−1，标记了两种分类。对于γ=y(i)(wTx(i)+b)，若为正，则可表示分类正确，若为负，则表示分类有误，需要再次尝试查找超平面。
在该定义下，我们需要查找一个超平面，使其具有maxminγ值，该超平面则为所求向量机。但是，由于w可以无限放大，所以在计算过程中，可以约定||w||=1。求解该问题使用拉格朗日算子，计算得到SVM原始优化问题的对偶问题后，快速求解。
对于线性不可分数据集，始终有γ<0的存在，所以线性支持向量机就提供了容错机制。对于一些非线性分割，就需要使用一些机制将其数据映射到线性空间上，转化为线性分割，即可获得结果，这就是非线性支持向量。数据映射函数通常不容易获得，因此在支持向量机中，有着核函数机制，可以隐式的应用映射函数，而不需要具体的求解映射函数。核函数的使用
核函数的实质是，将低维的数据集隐式的映射到高维空间乃至无穷维空间中，使其在高维空间获得线性可分特性，从而实现分类。由于是隐式映射，避免了高维空间和无穷维空间的表示，运算复杂度并未增加，甚至还会被简化，因而在计算复杂性上也有较好的体现。
核函数可按如下方式定义：
定义ϕ(x)，将<x(i),y(i)>转为K=<ϕ(x(i)),ϕ(y(i))>，其中K就为核函数。显然，K依赖于ϕ的定义。
但是，K的设定并不需要确切的知道ϕ。举个例子：定义K(x,z)=(xTz)2，当x=(x1,x2,x3)时，
ϕ(x)=[x1x1x1x2x1x3x2x1x2x2x2x3x3x1x3x2x3x3]
显然，计算ϕ(x)需要9次，而直接计算K仅需3次。同理，当x=(x1,x2,…xn)时，计算ϕ(x)需要n2次，而计算K仅需要n次。这就是核函数的魅力所在了。
但是，在没有定义ϕ(x)时，如何确定K函数合法呢？
直接定义矩阵
在计算SVM的对偶问题时，用到了拉格朗日算子，需要能够快速的计算出其中的变元值。通常情况下，我们会选择一个变元，固定除它以外所有变元的值，再对这个变元直接计算最优值，以此进行优化。但是，对偶问题中有一个强约束：∑mi=1αiy(i)=0，选择单一变元进行优化一定会破坏该约束，因而有了SMO优化。
该优化的基本思想是：每次选两个变元进行优化，这样就能保证上述约束。于是，每次选择一个变元，然后从其他变元中找出他们俩合起来能够产生最大变化的一个变元，对这两个变元进行优化即可。