回顾一下上文的思路，对于线性可分问题，我们可以用超平面将训练样本分开。但是通常超平面有很多个，我们选择距离两类样本点几何间隔最大的那个，这样能够使得模型错误率的“上界”最小。而这个问题，有进一步的转化为求超平面法向量||w||的值最小的问题。好，今天就从这里开动。
【线性可分问题 之 问题转化 之 凸二次规划】
||w||表示向量w的“范数”，最常用的是二阶范数，怎么算呢？就是把向量w中的每个元素都平方，再求和，然后再开二次方根。嗯，我们从前在学习高数的时候经常算类似的东西，虽然我现在也想不起来高数到底学什么了，呵呵。那其实这个问题很简单啊，让w中的每个元素都取值为零，则计算出的结果为零，最小啊。这时候w表示原点。怎么回事？有地方不对。
是由地方不对，我们忘了要这个超平面干什么了——它是用来分隔两类训练样本的，这是他的约束条件。所以，目标函数修正如下：
min pow (||w||, 2.0) / 2
subject to y(i) ( <w * x(i)> + b ) > 0
Sorry 我用的C的语法来描述公式。把最小化||w||转化成了最小化它的平方，在数学上是等价的，形式上却有很多好处。
通常来讲，两类线性可分样本之间都有一定的间隔（想一想，如果没有这样的间隔，那么必然两类都有样本在这个分类面上，那么这些样本如何分类呢），而我们也要把这个间隔表示在上面的目标函数中。通常，这个间隔取值为1。为啥是这个值呢？0.5行不？其实啊，个人认为啊，也行！为什么这么说呢？再回顾上一篇文章中，我们之所以要优化||w||，其实我们要优化Theta，Theta表示了样本点到分类面的几何间隔。而我们优化的方法呢，一定是固定一个几何间隔，然后来优化Theta，也就是现在的||w||。这个间隔只要是一个固定的常量值就行了，以后的数学推导，直接将它带着，对优化的方法和结果不影响。但是还有个疑问，就是如果这个值非常大，例如都超过了样本集合的最大直径（集合中两个样本点之间的最远距离），那还怎么分啊？嗯，是的。不过不同的是，那个是“几何间隔”，是经过“归一化”之后得到的；而我们现在这个1，是在归一化之前，不是一个几何意义上的距离的概念。哦，我知道还有问题，先列出公式吧。总之，加上间隔之后，目标函数修正如下：
min pow (||w||, 2.0) / 2
subject to y(i) ( <w * x(i)> + b ) -1 >= 0
约束条件中可以用“=”了。
回到上面那个问题，为啥不是几何距离，就可以呢？就能确保把两类样本都间隔开呢？我是这么理解的，举个例子吧：假设是在一个二维平面上，有个点是(1, 1)，它和原点(0, 0)的距离很容易计算出是1；如果不是几何距离的概念，那我可以把(1, 1)进行缩放，例如都扩大两倍，得到(2, 2)，则和原点的距离变为4。同样，在上面的约束条件中，也可以进行类似的缩放。我要说的是，有个间隔就好，他的值本身并不重要。如果还有问题，那么好吧，我承认在这里面我也有点糊涂。
优化上面的约束条件下的目标函数，有个专有名词，很cool，叫“凸二次规划问题”。简单解释一下。首先，上面的问题是一个优化问题，而优化问题又称为规划问题；其次，上面的目标函数是二次函数，所以叫二次规划问题；最后，上述的约束条件定义了一个凸集（集合中任意取两点连成一条直线，直线上的点依然在集合内部，想象成一个圆或者椭圆内部区域），所以又称为“凸二次规划问题”。
【线性可分问题 之 问题转化 之 支持向量机】
上面，我们遇到了这么cool的一个问题，可是怎么解呢？
回想一下我们学习的高数。对于没有约束的极值问题，我们可以求导数，并令导数等于零，求得极值。对于有等式约束的极值问题，我们利用拉格朗日乘子，转换成无条件极值问题。那么上面那个呢？是不等式的条件极值问题，咋办？凉拌，呵呵。
还得继续转化。
我们跳出来想一下，我们最终获得的模型参数是什么？是w向量和b向量。而b向量可以通过w向量来获得。（你要问，如何获得？这个我没看具体的推导，我是这样想的：如果分类器描述的是二维空间的一条直线，那么w就是斜率，b就是截距。当w确定的情况下，我们看平面上的样本点，根据样本点之间的间隔，很容易就算出最优分类线与两类样本点之间的最大间隔，也就能够唯一确定最优分类线——间隔中间的那条，也就能确定b的值了。）接着上面的思路，w是根据什么获得的呢？根据的只有训练样本，即是说，w是训练样本的函数，可以表示如下：
w = a(1)y(1)x(1) + a(2)y(2)x(2) + ...... a(n)y(n)x(n)
其中a(i)是一个实数，x(i)和y(i)分别表示样本i的特征向量和分类结果。这样，寻找优化w的问题就转换成了寻找优化a的问题，a的个数与样本数量相同。我在第一次看到这个的时候会问自己，这是不是把问题搞复杂了？其实不是，这里面绝大多数的a的值都是0；而只有那些少数不为0的a，才是模型真正的参数，才是我们将来对未知样本分类的主要考虑依据。而这些不为0的a所对应的训练样本，就是支持向量。最大几何间隔的大小就由他们来决定。
回想一下上文中超平面的定义如下：
g(x) = <w * x> + b
将w的计算方式带入之后，变为
g(x) = < {a(1)y(1)x(1) + a(2)y(2)x(2) + ...... a(n)y(n)x(n)} * x > + b
= < a(1)y(1)x(1) * x > + < a(2)y(2)x(2) * x > + ...... < a(n)y(n)x(n) * x > + b
= SUM_i { a(i)y(i)<x(i) * x> } + b
上面的公式中，只有x向量是变量，x(i)表示第i个训练样本，a(i)是实数，表示x(i)。同样的，可以将w带入到上面的优化目标函数中。据Jasper说，经过上面的变换，就将原来的不等式约束变成了等式约束，就得到了解析解，至此，线性可分问题就能解了。
不过我个人是没有看明白，如何就将原来的不等式约束变换成了等式约束；即便是有了等式约束，下面的故事呢？怎么搞出解析解的？Jasper在他的软文里面都没说。这也埋下了一个伏笔，我后文还要看其他的资料来了解相关的知识，这就留到svm训练算法部分来说吧。
看到这个变换，我的收获主要有以下几点：
1. 从前知道支持向量的直观几何意义，但是从代数推到上，不知道他是怎么来的；现在知道了。
2. 了解svm对新样本的分类过程了：就是找到不为零的a(i)以及相应的训练样本，与输入向量做内积，判断内积的值即可。
3. 能初窥一点儿训练过程：在对每个a(i)进行优化的时候，至少要遍历所有训练样本；参数空间受支持向量的影响很大。
这一篇先写到这里。