本章主要讲解支持向量机算法，也是最后一个详细讲解的监督学习算法。

Optimization objective

从逻辑回归算法引入到支持向量机（SVM，support vector machine）算法，讲解了支持向量机的数学定义。

Alternative view of logistic regression

首先对逻辑回归算法进行简单回顾。

逻辑回归中，每个样本的代价如下：

如果结果\(y=1\)，我们希望\(z = \theta^Tx \gg 0\)，代价简化为\(-\log \frac{1}{1+e^{-\theta^Tx}}\)：

注意：\(cost_1(z)\)函数的斜率并不重要。

我们可以把\(-\log \frac{1}{1+e^{-\theta^Tx}}\)的曲线简化为\(cost_1(z)\)函数的折线。

如果结果\(y=0\)，我们希望\(z = \theta^Tx \ll 0\)，代价简化为\(-\log (1-\frac{1}{1+e^{-\theta^Tx}})\)：

我们可以把\(-\log (1-\frac{1}{1+e^{-\theta^Tx}})\)的曲线简化为\(cost_0(z)\)函数的折线。

函数\(cost_0(x)\)和函数\(cost_1(x)\)就是支持向量机算法分别在\(y=0\)和\(y=0\)的代价。

Support vector machine

Logistic regression的代价函数:

\[\min_\theta \frac{1}{m}\sum_{i=1}^m [y^{(i)} (-\log h_\theta(x^{(i)})) + (1-y^{(i)}) (-\log (1-h_\theta(x^{(i)})))] + \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2 \]

首先分别对逻辑回归的两种情况的代价分别进行替换，得到：

\[\min_\theta \frac{1}{m}\sum_{i=1}^m [y^{(i)} cost_1(\theta^Tx^{(i)}) + (1-y^{(i)}) cost_0(\theta^Tx^{(i)})] + \frac{\lambda}{2m} \sum_{j=1}^n \theta_j^2 \]

而由于\(\frac{1}{m}\)只是常数项，对于优化参数\(\theta\)没有影响，所以直接去掉，得到：

\[\min_\theta \sum_{i=1}^m [y^{(i)} cost_1(\theta^Tx^{(i)}) + (1-y^{(i)}) cost_0(\theta^Tx^{(i)})] + \frac{\lambda}{2} \sum_{j=1}^n \theta_j^2 \]

逻辑回归的代价函数我们可以简单等价为：

\[A + \lambda B \]

正则化参数\(\lambda\)是为了平衡前面的代价函数项以及后面的正则化项，而在SVM中习惯写为：

\[CA + B \]

这里的C起到的作用和逻辑回归中的正则化参数\(\lambda\)是一样的，可以简单将C理解为\(\frac{1}{\lambda}\)。

最终，我们得到Support vector machine的代价函数：

\[\min_\theta C\sum_{i=1}^m [y^{(i)} cost_1(\theta^Tx^{(i)}) + (1-y^{(i)}) cost_0(\theta^Tx^{(i)})] + \frac{1}{2} \sum_{j=1}^n \theta_j^2 \]

SVM hypothesis

逻辑回归假设函数输出值为一个概率值，而SVM则直接输出结果。

Hypothesis:

\[h_\theta(x) = \begin{cases} 1 &{if } \space \theta^Tx \gg 0 \\ 0 &{otherwise} \end{cases} \]

Large MarginIntuition

人们有时会将支持向量机称作大间距分类器（large margin classifier），本节课主要从直观上感受一下为何SVM会被称为大间距分类器。

Support Vector Machine

if	Logistic Regression	Support Vector Machine
\(y=1\)	want \(\theta^Tx \ge 0\)	want \(\theta^Tx \ge 1\)
\(y=0\)	want \(\theta^Tx \lt 0\)	want \(\theta^Tx \le -1\)

从上面的对比表格可以看出，SVM其实是比逻辑回归更加严格的，相当于增加了额外的安全因子。

SVM Decision Boundary

这部分没看懂，重新看视频。。。

SVM Decision Boundary: Linearly separable case

以下面的例子为例，其实是存在无穷多的直线可以把正负样本分开的，但是SVM算法最终会得到黑色的直线，也就是正负样本之间都会有比较大的间距（margin），这就是SVM具有鲁棒性的原因。

Large margin classifier in presence of outliers

对于下面的正负样本，SVM可能会得到下图所示的决策边界：

如果在正样本中出现了一个异常值，并且正则化参数\(C\)设置的非常大，那么决策边界可能会变成下面的情况：

但是如果不要把参数\(C\)设置的太大，那么依然会得到第一幅图中的黑色决策边界。

The mathematics behind large margin classification (optional)（不太懂）

本节课主要讲解了SVM是大间距分类器背后的数学原理。

Vector Inner Product

为了解释这个问题，需要先介绍向量内积的基础知识。

假设有两个向量，分别是\(u = \begin{bmatrix} u_1 \\ u_2 \end{bmatrix}\)和\(v = \begin{bmatrix} v_1 \\ v_2 \end{bmatrix}\)，向量\(u\)和向量\(v\)之间的内积定义为\(u^Tv\)（或\(uv^T\)）。

\(\|u\|\)表示向量\(u\)的范数（norm），即\(u\)的长度，根据毕达哥拉斯定理（勾股定理），\(\|u\|= \sqrt{u_1^2 + u_2^2}\)。

把向量\(v\)和\(u\)画在坐标轴上，把\(v\)投影到\(u\)上面，记做\(p\)，则\(v\)和\(u\)的内积为：\(v^Tu=p \cdot \|u\|\)。

注意：这里的\(p\)是一个有符号数，如果\(v\)和\(u\)的夹角大于90度，那么\(v\)投影到\(u\)上面就变成负数，投影结果和向量\(u\)方向相反。

SVM Decision Boundary

SVM模型中代价函数的正则项为：

\[\min_\limits\theta \frac{1}{2} \sum_{j=1}^{n}{\theta_j^2} \\ \begin{cases} \theta^Tx_{(i)} \ge 1 &{if } \space y^{(i)}=1 \\ \theta^Tx_{(i)} \le -1 &{if } \space y^{(i)}=0 \end{cases} \]

为了方便讲解，对上面的式子进行简化，另\(\theta_0=0\)，\(n=2\)，则上面式子简化为：

\[\begin{aligned} \min_\limits\theta \frac{1}{2} \sum_{j=1}^{n}{\theta_j^2} &= \frac{1}{2}(\theta_1^2 + \theta_2^2) \\ &= \frac{1}{2}(\sqrt{\theta_1^2 + \theta_2^2})^2 \\ &= \frac{1}{2} \| \theta \|^2 \end{aligned} \]

根据前面讲解的内积的知识，可以得出：

\[\theta^Tx^{(i)} = \theta_1x_1^{(i)} + \theta_2x_2^{(i)} = p^{(i)} \cdot \| \theta \| \]

所以正则项变为：

\[\min_\limits\theta \frac{1}{2} \sum_{j=1}^{n}{\theta_j^2} \\ \begin{cases} p^{(i)} \cdot \| \theta \| \ge 1 &{if } \space y^{(i)}=1 \\ p^{(i)} \cdot \| \theta \| \le -1 &{if } \space y^{(i)}=0 \end{cases} \]

$ p^{(i)}\(是\) x^{(i)}\(在向量\)\theta$上的投影。

假如决策边界\(\theta\)如下图所示，在这种情况下，正样本\(x^{(1)}\)投影到上面为\(p^{(1)}\)，由于\(p^{(1)}\)很小，而我们希望\(p^{(1)} \cdot \|\theta \|\)远远大于1，所以就会使得\(\|\theta\|\)非常大；同理，负样本\(x^{(2)}\)投影到上面为\(p^{(2)}\)，由于\(p^{(2)}\)很小，而我们希望\(p^{(1)} \cdot \|\theta \|\)远远小于-1，所以就会使得\(\|\theta\|\)非常大。

但是我们的目标函数是希望找到一个参数\(\theta\)，它的范数是小的，因此这并不是一个好的参数\(\theta\)的选择。

为了使得参数\(\theta\)的范数是较小的，唯一的方式就是选择下图绿色的决策边界。（为啥绿色的决策边界对应着平行于x轴的\(\theta\)向量？？？？？？）

Kernels I

通过讲解核函数介绍SVM如何得出复杂的非线性函数决策边界。

Non-linear Decision Boundary

我们可以通过高次数的多项式模型来得到非线性的决策边界。

为例获得非线性的决策边界，我们的假设函数可能是：

\[h_\theta(x) = \begin{cases} 1 &{if} \space \theta_0 + \theta_1x_1 + \theta_2x_2 + \theta_3x_1 x_2 + \theta_4x_1^2 + \theta_5x_2^2 + \cdots \ge 0 \\ 0 &{otherwise} \end{cases} \]

我们用一系列新的特征\(f\)替换模型中的特征，令：\(f_1=x_1, f_2=x_2, f_3=x_1x_2, f_4=x_1^2, f_5=x_2^2\)，上面的模型就简化成：

\[h_\theta(x) = \begin{cases} 1 &{if} \space \theta_0 + \theta_1f_1 + \theta_2f_2 + \theta_3f_3 + \theta_4f_4 + \theta_5f_5 + \cdots \ge 0 \\ 0 &{otherwise} \end{cases} \]

除了对原来的特征进行组合之外，有没有更好的方法来获得特征\(f\) ？——我们可以通过核函数来计算出新的特征。

Kernel

我们首先在坐标轴上预先选定3个地标（landmark）\(l^{(1)},l^{(2)},l^{(3)}\)，对于给定的训练实例\(x\)，计算出来的新特征取决于\(x\)与选定地标的近似程度。

例如：

\[f_1 = similarity(x, l^{(1)}) = \exp(-\frac{\|x-l^{(1)}\|^2}{2\sigma^2}) \\ f_2 = similarity(x, l^{(2)}) = \exp(-\frac{\|x-l^{(2)}\|^2}{2\sigma^2}) \\ f_3 = similarity(x, l^{(3)}) = \exp(-\frac{\|x-l^{(3)}\|^2}{2\sigma^2}) \\ \]

\(\|x-l^{(1)}\| = \sum_{j=1}^n{x_j-l_j^{(1)}}\)，表示\(x\)和\(l^{(1)}\)之间的欧式距离(范数)。

上例的\(similarity(x, l^{(1)})\)就是核函数（kernel），这里具体为高斯核函数（Gaussian Kernel）。

Kernels and Similarity

地标的作用是什么？

\[f_1 = similarity(x, l^{(1)}) = \exp(-\frac{\|x-l^{(1)}\|^2}{2\sigma^2}) \]

如果一个训练实例\(x\)与地标之间的距离近似为0，即\(x \approx l^{(1)}\)，则：

\[f_1 \approx \exp(-0) \approx 1 \]

如果训练实例\(x\)与地标之间距离较远，则：

\[f_1 \approx \exp(-\frac{(large \space number)^2}{2\sigma^2}) \approx 0 \]

这样就根据实例\(x\)与地标\(l\)之间的距离构造出了不同的特征\(f\)。

Example

假如\(l^{(1)} = \begin{bmatrix} 3 \\ 5 \end{bmatrix}\)，\(f_1=\exp(-\frac{\|x - l^{(1)} \|^2}{2\sigma^2})\)，对于不同的\(\sigma\)，特征值\(f\)和训练实例\((x_1,x_2)\)之间的关系如下：

图中水平面的坐标为\(x_1,x_2\)，垂直坐标代表\(f\)。

可以看出，当\(x\)与\(l^{(1)}\)重合时\(f\)具有最大值，随着\(x\)的改变，\(f\)的改变速率受到\(\sigma^2\)的控制，\(\sigma^2\)越小，改变速率越大。

在下图中，当实例\(x\)处于粉红色点时，因为其离\(l^{(1)}\)较近，而离\(l^{(2)}\)和\(l^{(3)}\)较远，因此\(f_1 \approx 1\)，而\(f_2 \approx f_3 \approx 0\)，因此\(-0.5 + 1 = 0.5 \ge 0\)，即预测\(y=1\)。同理可以求出离\(l^{(2)}\)比较近的绿色点也预测\(y=1\)。而蓝色点离3个地标都比较远，即\(f_1 \approx f_2 \approx f_3 \approx 0\)，所以\(-0.5 \lt 0\)，预测\(y=0\)。

这样图中红色封闭曲线的范围，就是依据一个个训练实例以及预先选定的地标所得出的判定边界。

Kernels II

主要讲解了核函数的一些细节问题。

Choosing the landmarks

之前没有讨论的一个细节问题就是如何选择地标？

通常的作法是直接把数据集的\(m\)个实例作为\(m\)个地标，即令\(l^{(1)}=x^{(1)}, l^{(2)}=x^{(2)}, \cdots, l^{(m)}=x^{(m)}\)。

这样我们新得到的特征值都是建立在原有实例与其他数据点之间的距离的基础之上的，即：

最终得到特征\(f=\begin{bmatrix} f_0 \\ f_1 \\ f_2 \\ \vdots \\ f_m \end{bmatrix}\)，其中\(f_0=1\)。

对于训练数据\((x^{(i)}, y^{(i)})\)，我们计算出对应的特征值\(f^{(i)} = \begin{bmatrix} f^{(i)}_0 \\ f^{(i)}_1 \\ \vdots \\ f^{(i)}_m \end{bmatrix}\)，其中\(f^{(i)}_0=1\)。

SVM with Kernels

Hypothesis: 给定\(x\)，计算新的特征\(f\)，当\(\theta^Tf \ge 0\)时，预测\(y=1\)，否则反之。

Training: 代价函数把\(\theta^Tx^{(i)}\)替换为\(\theta^Tf^{(i)}\)，

\[\min_\theta C\sum_{i=1}^m [y^{(i)} cost_1(\theta^Tf^{(i)}) + (1-y^{(i)}) cost_0(\theta^Tf^{(i)})] + \frac{1}{2} \sum_{j=1}^n \theta_j^2 \]

由于正则项里的\(n\)在这里等于\(m\)，所以修改为：

\[\min_\theta C\sum_{i=1}^m [y^{(i)} cost_1(\theta^Tf^{(i)}) + (1-y^{(i)}) cost_0(\theta^Tf^{(i)})] + \frac{1}{2} \sum_{j=1}^m \theta_j^2 \]

SVM parameters

下面是SVM中参数\(C\)和\(\sigma^2\)对于方差和偏差的影响：

Using an SVM

目前为止，已经讨论了许多SVM抽象层面的东西，这节课主要讨论运行SVM中需要的一些东西。

建议直接通过SVM软件包来实现求解参数\(\theta\)，不建议自己实现。

不过在使用SVM算法时，我们需要：

• 选择参数\(C\)；

• 选择核函数（相似性函数）：

  

Kernel (similarity) functions

高斯核函数：

注意：在使用高斯核函数之前，如果不同特征之间数量级相差非常大，一定要先进行特征缩放。

Other choices of kernel

除了最常用的"linear kernel"和"gaussian kernel"，还有其他核函数的选择。但是注意并非所有的相似度函数都是有效的核函数。相似度函数必须满足“Mercer’s Theorem”，才能确保SVM优化软件正确工作，因为SVM算法进行了很多数值计算上的优化，这些优化的前提就是假设核函数满足“Mercer's Theorem”。

其他可用的核函数：

• 多项式核函数（Polynomial kernel）: \(k(x,l) = (x^Tl + constance)^{degree}\)，E.g. \(k(x,l) = (x^Tl + 1)^{4}\)
• 字符串核函数（String kernel）
• 卡方核函数（chi-square kernel）
• 直方图交集核函数（histogram intersection kernel）
• 等等...

但是最常用的还是线性核函数以及高斯核函数，其他核函数都是在特定领域范围内使用。

Multi-class classification

对于多元分类问题，许多SVM软件包已经内置了多元分类的函数，或者我们可以使用“one-vs-all”方法。

Logistic regression vs. SVMs

在逻辑回归和SVM模型之间应该选择哪一个？

• 如果n远大于m，即训练集不足够支持我们训练一个复杂的非线性模型，那么选用逻辑回归模型或者线性核函数的SVM。
• 如果n较小，且m大小适中，E.g. \(n=1-1000, m=10-10000\)，选用高斯核函数的支持向量机。
• 如果n较小，而m较大，E.g. \(n=1-1000, m \gt 50000\)，则创造/增加更多的特征，然后使用逻辑回归或线性核函数的SVM。

\(n\)为特征数，\(m\)为训练样本数。

神经网络在上面3种情况下都可能会有较好的表现，但是训练神经网络可能会非常慢。选择SVM的原因主要是它的代价函数是凸函数，不存在局部最小值。

上面的选择仅仅只是一个模糊的参考，因为机器学习问题通常更重要的是你有多少数据、是否擅长做误差分析等，而不是选择具体哪个算法。