支持向量机(Support Vector Machines)
这章的内容是SVM。它是一种监督式学习模型，既可以用于分类也可以用于回归。这里的视频内容只讲分类。
从逻辑回归到SVM
首先回顾一下逻辑回归中的代价函数，对于某个样例，代价为 \[
J(\theta, x, y) = -ylog\frac{1}{1+e^{-\theta^Tx}} + (1-y)log(1-\frac{1}{1+e^{-\theta^Tx}})
\] 其中当\(y\)分别为\(1\)和\(0\)时，代价关于\(z\)(\(z=\theta^Tx\))的关系如下所示：
在SVM中，不同的是，图形从弧线变成了两段线段：一段值为0，另一段是一段斜线段。这是SVM中常见的替代损失函数中的一种：hinge损失，但视频中没有提及，具体讲解可看西瓜书。
接下来看整体的代价函数优化目标： \[ \min_\theta\frac1m[\sum_{i=1}^my^{(i)}(-logh_\theta(x^{(i)})) + (1-y^{(i)})((-log(1-h_\theta(x^{(i)})))] + \frac{\lambda}{2m}\sum_{j=1}^n\theta^2_j \] 根据上面在单个样例中的改变，再在最后的式子中做一些等价变换，我们可以得出SVM的优化目标为： \[ \min_\theta C[\sum_{i=1}^my^{(i)}cost_1(\theta^Tx^{(i)}) + (1-y^{(i)})cost_0(\theta^Tx^{(i)})] + \frac12\sum_{j=1}^n\theta^2_j \]
最大化类间间隔分类器
SVM在进行分类时，能够最大化分类之间的间隔。我们来看一个二分类的例子，具体地了解一下。上一节说到，SVM中代价随\(\theta^Tx\)的变化情况是两段线段。因此在最小化代价函数时，我们希望能取到值为\(0\)的那一段，也就是：
- 对于\(y=1\)，我们希望\(\theta^Tx\ge1\)(而不是0)
- 对于\(y=0\)，我们希望\(\theta^Tx\le-1\)(而不是0)
这样的取值就相当于把要求设得更加严苛了：我们不仅希望能把不同的类别分隔开来，还希望类间的间距能够越大越好。比如说这里两种分类的分布情况如图所示：
这里的绿色、粉色以及黑色的线都能表示决策边界，也都能够把两种类别分割开，但通常情况下，我们认为黑色的决策边界线最好：在这种情况下，两个类到边界的距离都较大(两条蓝线分别到黑线的距离)，两个类之间的距离也就会比较大。而SVM则能找到这条黑线。这里蓝线上的点也就是每个类中到分界线距离在同类中最短的点，而因为每个样本点对应一个特征向量，这些蓝线上的点对应的特征向量则被称为支持向量(support vector)。
以上的例子只讨论了理想的分类情况，而如果样本中有一些离群点(outlier)，SVM同样能够正确处理：因为在SVM的优化目标中的\(C\)相当于逻辑回归中的\(\lambda\)，是正则化参数。正确处理这些离群点的方法是称为软间隔(soft margin)的概念。对\(C\)的取值，我们做如下讨论：
- 当\(C\)较大时，相当于\(\lambda\)较小，可能会导致过拟合，高方差。
- 当\(C\)较小时，相当于\(\lambda\)较大，可能会导致欠拟合，高偏差。
所以在有个别离群点的情况下，只要我们不把\(C\)设得非常大，就不会有过拟合，也就是说SVM仍能够给出一条合理的决策边界。
核函数 (Kernel)
上一节假设我们的数据是线性可分的。而在现实任务中，数据的分类情况可能不是线性可分的。在这种情况下，可以把样本映射到更高维的特征空间中，使得样本在此新的特征空间中线性可分。但在高维的特征空间上的计算通常很难，所以我们希望存在一个函数，使得我们在原始样本空间中通过该函数计算出的值等于特征空间上所要求的值。这个函数就是核函数(kernel function)。
使用核函数的构造新特征的过程大致为：
- 选出一些标记点，记为\(l^{(i)}\)，其维度和一个样本\(x^{(i)}\)相同。
- 对于每个样例\(x\)中的所有标记点\(l^{(i)}\)，都使用核函数求出其对应的新特征\(f_i = similarity(x,l^{(i)}) = exp(-\frac{||x-l^{(i)}||^2}{2\sigma^2})\).
- 当\(\theta^Tf=\theta_0f_0+\dots+\theta_mf_m\ge0\)时，我们预测\(y=1\)。其中\(f_0\)是新加的常数项，相当于\(x_0\)的作用，值为1.
其中第二步能够使用的核函数有很多种，其中高斯核(Gaussian Kernel)和另一种核函数线性核(Linear Kernel)是最常用的两种核函数，它们分别适用于样本多特征少以及样本少特征多的情况。这里使用的是高斯核。
高斯核
使用高斯核可以用来表示两个向量\(x\)和\(l^{(i)}\)之间的距离，当两者越接近时，\(f_i\)约接近\(exp(0)\)也就是1；当两者无穷远时，\(f_i\)趋近于\(exp(-\infty)\)也就是0。另外，上式中的参数\(\sigma\)对于\(f\)随\(x\)和\(l^{(i)}\)距离的变化情况也有影响：\(\sigma\)较大时，\(f\)下降较平缓，如果太大则可能会产生高偏差；而\(\sigma\)较小则会产生较陡的下降趋势，太小会有高方差、过拟合。
需要注意的是，由于原特征之间可能跨度较大，在使用高斯核前需要进行Feature Scaling，否则值很大的特征维度上的距离会在求新特征时起到主导作用。
那么所谓的标记点要怎么选取呢？通常，我们可以对于每个样本点\(x^{(i)}\)，都取一个和它完全相等的点作为标记点\(l^{(i)}\)。也就是说，经过如此转换，我们可以得出\(m\)个新特征\(f^{(i)}\)，其中\(m\)是样本个数。而对于每个特征，总有一维是等于1的。
得出新特征后，我们在计算参数\(\theta\)时的优化目标就是 \[ \min_\theta C[\sum_{i=1}^my^{(i)}cost_1(\theta^Tf^{(i)}) + (1-y^{(i)})cost_0(\theta^Tf^{(i)})] + \frac12\sum_{j=1}^n\theta^2_j \] 这个式子和上面的很像，只不过把特征\(x^{(i)}\)改成了\(f^{(i)}\)；最后的正则项的\(n\)等于\(m\)，且正则化还是老样子不考虑常数项\(\theta_0\)。
逻辑回归 VS SVM
- 如果\(n\)相对于\(m\)很大，通常用逻辑回归（或是线性核的SVM）
- 如果\(n\)较小，而\(m\)也不很大，则用高斯核的SVM
- 如果很\(n\)小而\(m\)很大，那么添加特征，然后用逻辑回归或线性核的SVM