支持向量机
优化目标
在监督学习中，重要的不是你选择的算法，而是应用这些算法时，选择的特征、正则化参数等等诸如此类。其中有一种非常强大的分类工具，称为支持向量机。（Support Vector Machine，SVM）
下面展示如何通过修改逻辑回归，来得到SVM。
首先回顾一下逻辑回归假设函数，注意y=1和y=0的情况。
进一步写出代价函数
当y=1时，此时代价函数剩左边一项$-y \log \frac{1}{1+e^{-\theta^{T} x} }$，图像为
其中的曲线为逻辑回归代价函数，两段直线为SVM的代价函数，记为$cost_{1}(z)$
同理，当y=0时，代价函数剩右边一项$(1-y) \log \left(1-\frac{1}{1+e^{-\theta^{T} x} }\right)$，图像为
其中的SVM代价函数，记为$cost_{0}(z)$。
完整的逻辑回归代价函数写成：
$\min _{\theta} \frac{1}{m}\left[\sum_{i=1}^{m} y^{(i)}\left(-\log h_{\theta}\left(x^{(i)}\right)\right)+\left(1-y^{(i)}\right)\left(\left(-\log \left(1-h_{\theta}\left(x^{(i)}\right)\right)\right)\right]+\frac{\lambda}{2 m} \sum_{j=1}^{n} \theta_{j}^{2}\right.$
可以看出由代价项和正则化项两部分组成，基本形式为$A+\lambda B$，$\lambda$可以看做是控制两部分的权重。
要写出SVM的代价函数，首先我们把逻辑回归代价函数的$\frac{1}{m}$去掉，不影响$\theta$值。然后我们把正则化项的系数$\lambda$去掉，在代价项前面添上一个系数C，效果等同于$\frac{1}{\lambda}$。
因此，最终SVM的代价函数为：
$\min _{\theta} C \sum_{i=1}^{m}\left[y^{(i)} \cos t_{1}\left(\theta^{T} x^{(i)}\right)+\left(1-y^{(i)}\right) \operatorname{cost}_{0}\left(\theta^{T} x^{(i)}\right)\right]+\frac{1}{2} \sum_{i=1}^{n} \theta_{j}^{2}$
假设函数为：
注意，和逻辑回归假设函数计算出的是概率不同，SVM假设函数直接计算结果(1/0)。
直观理解大间距
SVM又被称为大间距分类器，以下直观讲解为什么。
从图中可以看出：
y=1时，需要$\theta^{T}x\ge1$，区别于逻辑回归中$\ge0$，此时$cost_{1}(z)=0$，即SVM在正确分类的基础上还构建了一个安全距离。
y=0时，需要$\theta^{T}x\le-1$，区别于逻辑回归中$\le0$，此时$cost_{0}(z)=0$，即SVM在正确分类的基础上还构建了一个安全距离。
接下来，如果我们把代价函数中的常数C设置成一个非常大的值，例如C=100000，此时为了使代价最小，就必须让最优化函数
中蓝色框部分等于0，又根据y=1或y=0时$\theta^{T}x$的取值，可以把优化问题和约束条件改为：
当你把它最小化时，可以得到决策边界。
其中黑线为SVM的决策边界，比起粉红线和绿线，显然黑线具有更好的鲁棒性（robustness，又叫健壮性，在计算机中代表运行过程中处理错误，或是算法、输入异常时仍然正确运行的能力），距离正负样本的最小距离最大。也因此我们把SVM称为最大间距分类。
如果把C设置的非常大时，可能会出现下面的情况
由于左下角出现了一个异常点，决策边界会从黑线变为粉红线。相当于$\lambda$过小导致过拟合。如果把C值设置的小一点，则会忽略异常点的影响。因此对C的讨论，其实也是过拟合和欠拟合的问题。
大间隔分类器数学原理
本节解释了为什么SVM能够大间隔分类
- 向量内积
简单来说，就是内积等于$u^{T}v$，也等于$p\lVert u \rVert$，其中p为向量v对向量u的投影，$\lVert u \rVert$为范数（norm，意思是具有“长度”概念的函数，这里可以简单理解为向量的长度）。内积具有正负，当向量夹角大于90度，内积为负；小于90度，内积为正。
那么回到优化问题上
我们假设n=2，$\theta_{0}=0$，然后通过之前提到的内容，可以改写优化问题：$\min _{\theta} \frac{1}{2} \sum_{j=1}^{n} \theta_{j}^{2}=\frac{1}{2}|\theta|^{2}$
也可以改写约束条件，即把$\theta^{T} x^{(i)}$看成是向量相乘，最终能改写为下面的式子：
那么为什么SVM不会选择下图中的决策边界呢？
其原因是，由下图可以看出，位于一、四象限的样本$x^{(1)}$，因为和决策边界接近，当它投影到$\theta$上时得到的$p^{(1)}$非常小，因此如果要满足$p^{(i)} \cdot|\theta| \geq 1$，那么$|\theta|$就必须非常大，这跟我们的优化问题$\min _{\theta} \frac{1}{2} \sum_{j=1}^{n} \theta_{j}^{2}=\frac{1}{2}|\theta|^{2}$矛盾。
位于二、三象限样本同理。
正确的样本边界如下图
额外说明一下，这里的$\theta_{0}=0$意味着决策边界一定会经过原点，如果令其不等于0，结论也是同样成立的。
核函数1
本质上说，核函数跟SVM没有必然联系，但是在用于求非线性分类器时具有很好的效果。
考虑下图中的数据集：
这种非线性的情况，显然用原始输入的两个特征是无法表示的，因此我们需要增加多项式特征。
这里我们可以将特征重新编号为$f_{i}$：
但问题在于，如何去选取新的特征呢？之前在逻辑回归时，我们是列举出了多个不同组合方式，通过交叉验证集进行验证，挑选出最合适的。而在SVM中，我们可以通过核函数对原始输入特征进行映射进而得到新的特征。
举例说明：
假设此时原始输入x有两个特征$x_{1}$和$x_{2}$（不考虑$x_{0}$），需要得到新的特征$f_{1}$、$f_{2}$、$f_{3}$。
首先我们选取了3个点$l_{1}$、$l_{2}$、$l_{3}$，称为标记（landmark）。
从图中可以看出，$f_{i}$为x和$l^{(i)}$相似度，而这个求相似度的函数就被称为核函数（kernel），这里用到的是高斯核函数（Gaussion Kernels），${ {f}_{1} }=similarity(x,{ {l}^{ (1) } } )=e(-\frac{ { {\left| x-{ {l}^{(1)} } \right|}^{2} } }{2{ {\sigma }^{2} } } )$。
那么右边的式子究竟是什么含义？
图中可以很明显的看出，$f_{i}$的取值在0~1之间。
绘制出核函数的图像如下
图中水平面坐标代表$x_{1}$和$x_{2}$，垂直的坐标代表$f$，可以看出，只有当x和$l$重合时，$f$才具有最大值。
同时也可以看出$\sigma$对$f$改变速率的影响。$\sigma$较小时，中间凸起的部分较窄，当x远离$l$时，$f$下降的较快；当$\sigma$较大时则刚好相反。
得到新的特征值$f$之后，就可以写出假设函数$h(\theta)=\theta_{0}+\theta_{1} f_{1}+\theta_{2} f_{2}+\theta_{3} f_{3}$，进而在图像上画出决策边界如下：
可以看出，当样本位于粉红色点的位置时，x靠近$l^{(1)}$，y=1；位于绿色点时，靠近$l^{(2)}$，y=1；位于蓝色点时，靠近$l^{(3)}$，y=0。
核函数2
在上一节中，我们提到一个重要问题，那就是如何选取标记？
通常根据训练集的样本数量来选择对应地标，即如果训练集中有m个样本，就选取m个标记。并且令：$l^{(1)}=x^{(1)}, l^{(2)}=x^{(2)}, \ldots, l^{(m)}=x^{(m)}$，这样做的好处在于我们得到的新标记是基于原有特征与其他样本特征的距离。
由上图我们可以得出结论，对于一个样本$x^{(i)}$，我们可以将它的特征映射为$f^{(i)}$，从维度上看，我们也将原始输入特征从n+1维，映射为m+1维（+1为偏置项，m为标记个数也是样本个数）
下面将核函数运用到SVM中，首先我们将原始输入特征映射为新特征$f$，然后根据代价函数求出最优化的$\theta$
$min C\sum\limits_{i=1}^{m}{ [ { {y}^{ (i)} }cos { {t}_{1} } }( { {\theta }^{T} }{ {f}^{(i)} })+(1-{ {y}^{(i)} })cos { {t}_{0} }( { {\theta }^{T} }{ {f}^{(i)} })]+\frac{1}{2}\sum\limits_{j=1}^{m}{\theta _{j}^{2} }$
注意这里的最后的正则化项，$j$是从1-m而不是1-n，因为我们新特征$f \in \mathbb{R}^{m+1}$。而在实际运用中，我们还得对这一项的计算做一些修改，通常我们对正则化项的计算是用矩阵相乘$\sum_{j=1}^{n=m} \theta_{j}^{2}=\theta^{T} \theta$，但在SVM中，我们用$θ^TMθ$代替$θ^Tθ$，其中M根据我们选择的核函数来确定，这样可以简化运算。
最后再代入新的假设函数中。
使用SVM时还需要选择几个参数：
使用SVM
使用成熟的软件包来计算参数
不过还是有些问题需要你自己解决
关于内核函数的选择
1.可以使用线性内核函数，即不用内核函数，这种情况适用于n较大，m较小。因为如果样本个数少，特征多，去拟合复杂的非线性函数，容易导致过拟合。
2.也可以使用核函数（高斯核函数），适用于n较小，m较大。
以一个高斯核函数为例，输入两个特征向量，输出一个实数
注意在使用高斯核函数时，一定要对原始输入特征进行缩放：
否则会如图中那样，不同范围的特征在生成新特征时会产生不同的影响。
除此之外还可以选择其他的核函数，但是都必须满足莫塞尔定理，不过除了线性核函数和高斯核函数，其他的一般也不太常用。
多类分类问题
解决多分类问题的方法
1.可以使用封装好的模块
2.和之前逻辑回归中多分类问题类似，也可以使用把多分类问题转换成多个二分类问题，最终对新样本进行预测时，只要看它属于哪个正类的假设函数值最大，就属于哪个类别。
关于逻辑回归、核函数SVM、不含核函数SVM的选择
SVM的效果可能不如神经网络，但训练速度快，且是一个凸优化问题（即一定能得到全局最优解）。
