week 7

1.supported vector machine：optimization objective
SVM在针对复杂的非线性方程时，提供了一个更为清晰和强大的方法来选择和优化模型，也是一个强大的supervised learning。
现提出一个我们熟悉的逻辑回归模型：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000856)
我们用z来代替$\theta^Tx$,在逻辑回归中，我们想要的就是当y=1时，我们希望拟合后的$h_\theta(x)$也接近1，由于我们希望正确的进行分类，所以当$h_\theta(x)$趋近于1时，z应该远大于0；同理，当y=0时，z会远小于0。
通过观察逻辑回归的代价方程，我们可以发现任何一项的样本都会是整个代价函数，而且影响前置的1/m项，现在忽略掉这一项：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace00084f)
以如图的2条直线来分别近似的代替当y=1和y=0时的2中代价函数的图形，并且重定义为$cost_1(z)和cost_0(z)$，现在来构造支持向量机：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000857)
首先给出SVM的方程，和之前的逻辑回归看起来不同的是将括号外的符号移到了里面，并且忽略掉了正则化项的关于m的系数，因为它并不影响整体取最优解的结果。
在逻辑回归中我们采用正则化系数的形式来权衡代价，也就是$A+\lambda B$的形式，这样我们就能通过权衡后一项的值来最小化A。但是在SVM中我们采用C*A+B的形式。在逻辑回归中，通过将正则化系数设为一个较大的值，就可以削弱A的值，给B一个较大的权重；在SVM中通过将C设为一个较小的值也会起到同样的效果，所以可以近似的把C看做$\frac 1 \lambda$。

2.large margin intuition
支持向量机有时被认为是大间距分类器，首先我们给出SVM的hypothesis和模型：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000859)
可以看出来，当y=1时，只有当z大于或等于1时，代价函数$cost_1(z)$才等于0，换句话说，如果你有一个正样本，我们会希望$\theta^Tx$大于或等于1，也就是说SVM不仅可以将正负区分开，而且会以正负1作为分界，这就相当于在SVM中嵌入了一个额外的安全间距因子。
当我们将常数C设为一个非常大的值时，我们就很希望找到一项能使第一项为0的最优解，如果 我们找到了这样的参数，那么我们的问题就会变成一个大间距分类器，如下所示：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000852)
如果我们将C设置的很大，我们得到的边界会较容易受到偏差数据的影响，会得到下图这条粉线：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace00085a)
但是如果C设置的不太大的话我们最终会得到这条黑线，也就是说可以忽略掉一些干扰的样本，这样，当C较大时相当于$\lambda$较小，造成过拟合，高方差；当C较小时相当于$\lambda$较大，造成欠拟合，高偏差。

3.kernels
我们之前讨论过可以使用高次数的多项式模型来解决无法用直线分类的逻辑回归问题：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000854)
为了解决上述问题，我们的多项式可能是$\theta_0+\theta_1x_1+\theta_2x_2+\theta_3x_1x_2+\theta_4x_1^2...$的形式，我们可以采用一系列新特征的对应的f来替换上述模型中的每一项，如：$f_1=\theta_0，f_2=\theta_1x_1，f_3=\theta_3x_1x_2，f_4=\theta_4x_1^2，...$得到$h_\theta(x)=f_1+f_2+f_3+...+f_n$，除了这种对原有的特征进行组合的方法，我们可以采用一种更好的方法：
给定一个training sample，我们利用x的各个特征与我们预先选定的landmark$l^{(i)}$的近似程度来选取新的特征$f_n$。
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000850)
例如：
$$f_1=similarity(x,l^{(1)})=exp({-\frac {||x-l^{(1)}||^2}{2\sigma^2}})$$
其中:${||x-l^{(1)}||^2}=\sum \limits _{j=1} ^n(x_j-l_j^{(1)})^2$，为实例x中所有特征与landmark之间距离的平方和，具体而言，这是一个高斯核函数，虽然看上去和正态分布很像，但是并没有实质的关系。
这些landmark的作用在于筛选样本：如果一个training sample距离x很近，则$e^{-0}=1$；反之，距离很远的话，$e^{-large}=0$。
假设我们只有2个training sample，给定landmark与不同的$\sigma$的值，如下图所示：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000853)
图中水平轴分别为$x_1和x_2$，纵轴为f，可以看出来只有当x与l重合时f才会取到最大值，并且随着x改变的f值得变化速率受到$\sigma$的影响。
例如在下图中：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000851)
当实例位于红色的点时，其距离$l^{(1)}$较近，但是距离其余两个landmark较远，所以$h_\theta(x)=\theta_0+\theta_1f_1+\theta_2f_2+\theta_3f_3>0$，因此预测y=1，这里将$\theta_0$设为-0.5，但是对于蓝色的点时，其距离3者都很远，所以预测其y=0。这样我们通过设定landmark和实例进行比较得出判定边界，在预测时我们采用的不是原始的特征，而是通过核函数计算出的新特征f。
关于landmark的选择方面，我们通常是根据training sample的数量来选择landmark的数量，并且令：$l^{(1)}=x^{(1)}，l^{(2)}=x^{(2)}，l^{(3)}=x^{(3)}$这样做的好处在于：现在我们得到的新特征是建立在原有特征与training set中其它特征之间距离的基础之上的，即：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000858)
下面我们将kernel运用到SVM中：
首先修改我们SVM的hypothesis，即给定x，计算新特征f，当$\theta^Tf>=0$时，预测y=1，否则反之，相应的修改代价函数为：
![](https://leanote.com/api/file/getImage?fileId=5c9c0307ab64416ace000855)
再具体实施的过程中，我们还需要对最后的regularization进行一下处理，在计算$\sum \limits ^{n=m} _{j=1}\theta_j^2=\theta^T\theta$时，我们用$\theta^TM\theta$来代替$\theta^T\theta$，其中M是根据不同的kernel而选择的一个矩阵，其目的是为了简化运算。
另外，SVM也可以不使用kernel，这种方式被称为linear kernel，当我们不采用非常复杂的函数或者我们training set中特征非常多而数量非常少的时候我们可以采用这种方式。
下面是SVM中2个参数的影响：
C较大时，相当于$\lambda$较小，造成高方差；
C较小时，相当于$\lambda$较大，造成高偏差；
$\lambda$较大时，造成高方差；
$\lambda$较小时，造成高偏差；

4.using an SVM
在优化SVM求解$\theta$时最好不要自己编写相应的代码，而是使用现有的已经写好的代码，比较好的软件库有liblinear和libsvm。下面是一些使用SVM时的准则：
n为特征数，m为样本数
① 如果相对于m而言，n大得多，即训练数据量不够我们拟合出一个复杂的非线性模型，我们可以选用逻辑回归模型或linear kernel。
② 如果n较小，m大小中等，例如n在1-1000之间，m在10-10000之间，选用高斯函数为核函数的向量机。
③ 如果n较小，m非常大，例如n在1-1000之间，m大于50000，使用SVM会非常慢，应该选取更多的特征，然后采用逻辑回归或者linear kernel。
SVM相对于神经网络的一个优点在于它的优化问题是凸化的，所以在使用软件选取其全局最优解的时候往往会找到，或者近似的解，不需要考虑局部最优的问题。