SVM
SVM的路线梳理。
内容包括SVVM学习过程中常见的各种名词概念之间的关系和逻辑线。包括线性可分，线性不可分，核函数，特征空间映射，hinge loss函数，最小序列最优化方法，希尔伯特空间，对偶问题等的各种高大上的概念。这些概念都将在本篇博文中得到串联和阐释。
首先介绍一下svm是一个很强大的分类器，在deep learning还没有一统江湖的时候，svm绝对是那个时代的机器学习的顶梁柱，即便是现在，虽然deep learning如火如荼，SVM的重量级地位依然不容小觑，而且SVM作为基本的机器学习算法，有很多学习和优化的思路值得借鉴，搞懂SVM对面试和日常工作来讲都是非常重要的。
从感知器开始讲起
在介绍SVM之前首先要提一下感知器，感知器在Hinton的coursra课程上有过讲解，在李航的统计学习方法中也有具体的描述，用一句话表达感知器就是：用于找到线性可分数据的一个分类平面的算法。 也就是说感知器本身解不唯一，如果我们对比这些解的话，哪个解是最佳的解呢？那恐怕就要从机器学习的问题本身出发来看待了。必须要认识到的问题是我们找到了一个分类平面不是我们的最终目的，学习的目的在于预测，也就是说对于不在训练数据集中的样本，分类器分类效果的优劣应该是一个分类器好还是坏的评判标准。 那么对于感知器而言，一个距离正负样本的距离都很远的分类平面就应该是一个好的分类平面，因为对比那些正确分了类但是很靠近某一类的分类平面而言，一个新的样本来了，如果它是一个稍微远离正例的正样本，它也不容易被划到负样本那一侧去，对于稍微远离负例的负样本也是如此。于是我们脑海中最优分类平面的概念就建立起来了。如下图所示，三个平面都可以讲原始训练数据分开，但是对于新来的样本点，显然中间的更加具有区分能力，而另外两个会有错分的现象。
于是我们潜意识地大约知道了什么样的分类平面是比较优的，但是如何把这个现实中的语义建模成数学的呢？，这就需要用到间隔和距离的概念了。
我们知道，当我们刻画一个平面为最优平面的时候，我们是有着远和近的概念在这里面的，对应到数学模型的概念上就是距离和间隔，于是，我们需要从距离入手，找到刻画最优平面的方式。首先要介绍的是函数间隔的概念：给定超平面，以及样本点，定义样本点到超平面的函数间隔为：
要注意的是这里面的平面是带有方向的信息在其中的，所以乘以标签的正负信息可以得到距离的概念。但是很显然，这里面的权重在进行线性的放缩的时候相应的距离也会进行相应的放缩，解决办法就是对参数进行归一化，即表示成：
上述的形式就由函数间隔变成了几何间隔，解决了线性放缩的问题。
在上述的所有的中，对于整个数据集中最小的那个值就是最终平面相对于数据集的间隔，即
上述的是训练数据集中的样本数目。于是对应于我们一开始的想法：最大化分类间隔，我们应该建立如下的数学模型：
于是上面的数学模型表达的语义就是首先每一个样本点都需要大于一个距离，然后我们通过最大化这个距离可以间接地最大化样本到平面的距离了，这个过程非常长类似于变分推断中最大化下界的过程，其中的思想也是相同的，都是通过最大化下界间接达到最大化目标的目的。于是上述的模型的现实语义也就不难理解了。
同时考虑到函数间隔和几何间隔的关系，我们可以将上述的表达等加成下面的表达：
因为函数间隔的取值\hat{\gamma}并不影响最终的优化问题的解，因为函数间隔在这里面只是一个中介，所以这个中介变量取成多少并不关键，的线性放缩不会影响上述模型的求解过程。于是，我们不妨直接将置为1，这样上式就可以表示为：
进一步地，上式可以等价为：
于是最初的问题被我们现在建模成了凸二次优化的问题，尽管关于凸二次优化问题有很多解法，但是对于我们目前的问题我们希望应用拉格朗日乘子法进行求解。
于是对于上述的问题，我们通过引入拉格朗日乘子构建拉格朗日函数：
在这里面需要注意的一个问题是必须是大于等于零的，至于原因可以查看我的另外一个博客，这篇不做分析。
于是通过构造拉格朗日的极小极大化问题我们可以构造出等价的 但是这样的问题需要搜索的空间太大，所以我们转换为求解其对偶问题，也就是极大极小化问题 ,如此，先对里面的极小化问题通过偏导数为零求解最小值：
得到：
上面第一个式子带入拉格朗日函数可以得到:
于是上述的极大极小问题就变成了:
将上式的最大通过改变符号成为求最小，就得到下述的式子：
于是原始问题就变成了现在转变过来的对偶问题，在这种情况下，我们只需要求解一个参数就可以了，所以大大简化了优化的目标，因此使得求解变得简单。