编程作业放到了github上：coursera_machine_learning
支持向量机的目的，是将线性可分的数据集用一个超平面分开，而且让两个类的数据集都距离这个超平面尽可能的远。
将线性可分的数据集分开的超平面可以有无数个，这个用Perceptron就可以做到，但是让所有的点距离这个超平面尽可能的远，这样的解就是唯一的，使用SVM来求解。
接下来将分别从cost function、intuition和kernel来介绍SVM。
本节将从Logistic Regression来类比SVM。
先看Logistic Regression的“分类决策函数 h(x) ”以及“损失函数 J(θ) ”：
h(x)=11+e−θTx
J(θ)=−ylogh(x)−(1−y)log(1−h(x))
损失函数随着 z=θTx 的变化如下图。
当 y=1 时， J(θ)=−logh(x)=−log11+e−θTx
当 y=0 时， J(θ)=−log(1−h(x))=−log(1−11+e−θTx)
现在对上面的 J(θ) 做一些改变。
当 y=1 时， J(θ) 为下图中的紫色线：
当 y=0 时， J(θ) 为下图中的紫色线：
从上面的图中，可以知道，这个损失函数是希望，所有的负样例( y=0 )的 θTx<−1 的，所有的正样例( y=1 )的 θTx>1 的。
θTx 的含义其实是样例点到超平面的距离矢量。也就是说，损失函数希望所有的样例到超平面的距离都大于1，正负号代表方向(在超平面之上或者之下)。至于为什么是“1”，下面会详细讲到。
在SVM中，分类决策函数 h(x) 定义如下：
h(x)={1if θTx>00 otherwise
h(x) 的目的很简单，就是用一个超平面把正负样例分开。
损失函数 J(θ) 定义如下：
J(θ)=C∑i=1m[y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))]+12∑j=1nθ2j
cost1(θTx)={0if y=1, θTx>1some value y=1, otherwise
cost0(θTx)={0if y=0, θTx<−1some value y=0, otherwise
J(θ) 的目的是让正负样例尽可能地分开，距离超平面有一定的距离。希望： y=1 时， θTx>1 ； y=0 时， θTx<−1 。
SVM有如下optimization objective：
minθC∑i=1m[y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))]+12∑j=1nθ2j
其中 C 是一个类似于λ的权衡因子，可以理解为 C=1λ 。
现在来看数据集线性可分的情况下，SVM选择超平面的策略，来看看SVM的intuition。
当数据集线性可分的时候，SVM挑选的超平面必须能够满足：
对所有的正样例有 θTx>1 ，所有的负样例有 θTx<−1 。
也就是说，所有的样例距离超平面都有一定的距离，就像下图中的蓝线所示：
如此一来，所有的 cost1=0 ，所有的 cost0=0 ，则优化目标变成如下形式：
minθ12∑j=1nθ2js.t. θTx>1 if y=1
θTx<−1if y=0
接下来看看SVM会选择怎样的超平面， θ 是超平面的法向量。
样例点 x 到超平面的距离p：
p=θTx∥θ∥
则
θTx=p∥θ∥优化目标改写成：
minθ12∑j=1nθ2j
s.t. p∥θ∥>1 if y=1
p∥θ∥<−1if y=0
第一种，margin非常小的时候：
0<p(1)≪1 的时候，为了使 p(1)∥θ∥>1 ，则 ∥θ∥ 需要很大；
−1≪p(2)<0 的时候，为了使 p(2)∥θ∥<−1 ，则 ∥θ∥ 需要很大；
这样一来，就违背了 minθ12∑nj=1θ2j ，所以，SVM不会选择这样的超平面。
第二种，margin比较大的时候：
p(1)>1 的时候， ∥θ∥ 不用很大，也能使 p(2)∥θ∥>1 ；
p(2)<−1 的时候， ∥θ∥ 不用很大，也能使 p(2)∥θ∥<−1 ；
这种情况符合 minθ12∑nj=1θ2j ，所以，SVM会选择这样的超平面。
上面Ng将的intuition没有解释为什么 θTx>1 ，这里的1究竟是怎么选择出来的。接下来结合李航的讲解来说明一下。
首先，定义几个术语。
定义1 (关于样例点的几何间隔)：样例点到超平面的距离矢量 p(i) ，即:
p(i)=y(i)θTx(i)∥θ∥定义2 (关于训练集的几何间隔)：训练集中所有样例点的几何间隔的最小值，即：
p=minip(i)SVM的目的就是找到使 p 最大的超平面。所以其optimization objective又可以写成如下形式：
maxθp
s.t. y(i)θTx(i)∥θ∥⩾p
明显地， p 取值的变化，并不会影响到不等式的成立，只要∥θ∥随之等比例变动即可，而 ∥θ∥ 的等比例变动也不会改变超平面。
所以不如就令 p=1∥θ∥ ，如此一来，optimization objective被改写成如下形式：
maxθ1∥θ∥
s.t. y(i)(θTx(i))⩾1
又因为 maxθ1∥θ∥ 等价与 minθ12∥θ∥2 ，所以最终优化目为：
minθ12∥θ∥2
s.t. y(i)(θTx(i))⩾1
与上面Ng的optimization objective吻合。
需要注意的是：正如intuition1中所言，这个优化目标的使用是有约束条件的，其约束条件就是任意的 y(i)(θTx(i))⩾1 都要成立，也就是说，一定能够有一个超平面完美地分开数据集，即这个数据集是线性可分的。
总结一下，对于线性可分的数据集：
其分类决策函数 h(x) 定义如下：
h(x)={1if θTx>00 otherwise
其优化目标／损失函数为：
minθ12∥θ∥2
s.t.y(i)(θTx(i))⩾1
上面讨论的都是数据集是线性可分的情况，实际上这种数据集太少了，实际操作中的数据集多多少少都有特异值(outlier)的干扰，除去这些outlier，剩下大部分样例点组成的数据是线性可分的。
那么对于这种存在少数的样例点不满足 y(i)(θTx(i))⩾1 的情况，SVM应该如何处理呢？
解决方法就是给每个样例点 x(i) 加上一个松弛变量 ε(i) ，使得约束条件变成：
y(i)(θTx(i))⩾1−ε(i)
对于每一个松弛变量，都要支付一个代价，于是优化目标变成：
minθ12∥θ∥2+C∑i=1mε(i)
再回过来看Ng在最开始给出的损失函数 J(θ) :
J(θ)=C∑i=1m[y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))]+12∑j=1nθ2j
可以认为：
ε(i)=y(i)×cost1(θTx(i))+(1−y(i))×cost0(θTx(i))
但实际求解中，不需要这样代换，因为 cost1 和 cost0 在 y(i)(θTx(i))<1 情况下的值是未知的，所以还不如直接将这个整体看成一个未知数，然后用其他的求最优解的算法来求得最优解即可。
总结一下，对于有outlier的数据集：
其分类决策函数 h(x) 定义如下：
h(x)={1if θTx>00 otherwise
其优化目标／损失函数为：
minθ12∥θ∥2+C∑i=1mε(i)
s.t.y(i)(θTx(i))⩾1−ε(i)
上面的数据集都是基本上线性可分的，但是有些数据集，就是线性不可分的，比如像这样的：
之前讲Linear Regression的时候也出现过这种例子，那时候的处理方法也可以用在这里。
假设分类决策函数 h(x) 如下：
h(x)=θ0+θ1x1+θ2x2+θ3x1x2+θ4x21+θ5x22+...
令 f1=x1 ， f2=x2 ， f3=x1x2 ， f4=x21 ， f5=x22 ，则：
h(x)=θ0+θ1f1+θ2f2+θ3f3+θ4f4+θ5f5+...
这就又转化成了线性的。
把这些个 f1,f2,f3,f4,f5.... 称为新生成的特征，也就是说，需要生成一系列新的特征，把非线性的问题拉回到线性问题上来。
那么怎么生成这些新的特征？
在SVM中，使用核函数(kernel)来基于“现有特征”生成“新的特征”。
令:
l(1)=x(1)
l(2)=x(2)
...
l(m)=x(m)
然后对于第i个数据，其新的特征计算如下：
f1=kernel(x,l(1))
f2=kernel(x,l(2))
...
fm=kernel(x,l(m))
这里的 kernel() 是一个核函数，常用的核函数有“Guassian Kernel”，定义如下：
kernel(x,l)=exp(−∥x−l∥22σ2)
这样就将数据集由原来的 n 维特征空间映射到了新的m维特征空间中。如果，训练集大小 m 比较大的话，就相当于引入了更多的新特征。
接下来的步骤就和上面处理线性可分数据集一样咯，只不过，现在SVM的输入不是x，而是 f 了。
这里还有一个不确定的参数σ， σ 越大， fi 的变化就越平缓，反之。
一般使用SMO算法来快速求解SVM。
详细过程涉及到数学相关的知识点，如“拉格朗日算子”、“对偶问题”。目前还没有弄得特别清楚，迷迷糊糊的。
实际操作中，这一步不需要自己去实现，套用现有的框架就可以实现了。
