1 优化目标

左下是正样本情况下逻辑回归的代价函数与假设函数的图像，右下为负样本的情况

• 在逻辑回归中如果有一个 \(y=1\)的样本，训练的目标则是希望 \({{h}_{\theta }}\left( x \right)\) 趋近1，对应的 \(\theta^Tx\) 应当远大于0。

• 相反地，另一个样本即 \(y=0\)。则希望假设函数的输出值将趋近于0，这对应于 \(\theta^Tx\) 会远小于0。

• 将逻辑回归的代价函数用分段直线代替如紫色直线所示

左边的函数，记为 \({\cos}t_1{(z)}\)，右边函数记为\({\cos}t_0{(z)}\)。下标对应是 \(y=1\) 和 \(y=0\) 的情况

下面是逻辑回归的正则化代价函数

\[\underbrace{\frac{1}{m}\left[\sum_{i=1}^{m} y^{(i)} \underbrace{\left(-\log h_{\theta}\left(x^{(i)}\right)\right)}_{cost _{1}\left(\theta^{\top} x^{(i)}\right)}+\left(1-y^{(i)}\right) \underbrace{\left(\left(-\log \left(1-h_{\theta}\left(x^{(i)}\right)\right)\right)\right.}_{cost _{0}\left(\theta^{\top} x^{(n}\right)}\right]}_{A} + \lambda \times \underbrace{\frac{1}{2m}\sum_{j=1}^{n} \theta_{j}^{2}}_{B} \]

A 是训练样本的代价，B 是正则化项。

相当于最小化\(A\)加上 \(\lambda\) 乘以\(B\) ，通过设置不同正则参数 \(\lambda\) 达到优化目的。即最小化 \(A\)。还是保证正则参数足够小，也即是对于 B 项而言，

支持向量机使用一个不同的参数替换这里使用的 \(\lambda\) 来权衡这两项。你知道，就是第一项和第二项我们依照惯例使用一个不同的参数称为 \(C\)，同时改为优化目标，\(C×A+B\)。

对于支持向量机，我们得到了这里的最小化问题，即:

\[\min _{\theta} C \sum_{i=1}^{m}\left[y^{(i)} \operatorname{cost}_{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} \]

将逻辑回归中的常来那个参数 \(\frac{1}{m}\) 更换为变量 \(C\)

逻辑回归的代价函数中如果给定 \(\lambda\)，一个非常大的值，意味着给予 \(B\) 更大的权重。对应于将 \(C\) 设定为非常小的值，即 \(B\) 比 \(A\) 权重更大

即用参数来决定是更关心第一项的优化，还是更关心第二项的优化。

下面是 SVM 的假设函数

\[h_{\theta}(x)\left\{\begin{array}{ll}1 & \text { if } \theta^{\top} x \geqslant 0 \\ 0 & \text { othervie }\end{array}\right. \]

支持向量机直接预测 \(y\) 的值等于 1，还是等于 0。学习参数 \({{\theta }}\) 就是支持向量机假设函数的形式。

2 大边界分类器

这是支持向量机模型的代价函数

• 左边关于 \(z\) 的代价函数 \({\cos}t_1{(z)}\)，用于正样本，
• 右边关于 \(z\) 的代价函数 \({\cos}t_0{(z)}\)，用于负样本横轴

那么最小化这些代价函数的必要条件是什么。如果有一个正样本，\(y=1\)，则只有在 \(z>=1\) 时，代价函数 \({\cos}t_1{(z)}\) 才等于 0。

• 对于正样本，调整判定边界为 \(\theta^Tx>=1\)
• 对于负样本调整为 \(z\leq-1\) 的区间里函数值为0。

即不仅仅要求 \(\theta^Tx\)>0，还要 0 值大很多，比如大于等于1，小于等于 -1，这就相当于在支持向量机中嵌入安全间距因子。

将这个常数 \(C\) 设置成一个非常大的值。比如假设 \(C\) 的值为 100000 或者其它非常大的数，观察支持向量机结果

如果 \(C\) 非常大，则最小化代价函数的时候，将倾向于到一个使第一项为0的最优解

\[\min_\limits{\theta}C\sum_\limits{i=1}^{m}\left[y^{(i)}{\cos}t_{1}\left(\theta^{T}x^{(i)}\right)+\left(1-y^{(i)}\right){\cos}t\left(\theta^{T}x^{(i)}\right)\right]+\frac{1}{2}\sum_\limits{i=1}^{n}\theta^{2}_{j} \]

• 训练样本标签为 \(y=1\)，想令第一项为0，需要找到一个 \({{\theta }}\)，使得\(\theta^Tx \geq 1\)

• 训练样本标签为\(y=0\)，为了使\({\cos}t_0{(z)}\) 函数的值为0，需要 \(\theta^Tx\leq-1\)。

对于上图这个线性可分的训练集合使用上面定义的具有安全因子的代价模型，结果如黑线的分界线所示，蓝色是间距对应安全因子设置的间距

黑色的决策界和训练样本之间有更大的最短距离。然而粉线和蓝线离训练样本就非常近，在分离样本的时候就会比黑线表现差。因此，这个距离叫做支持向量机的间距，而这是支持向量机具有鲁棒性的原因，它用一个带有最大间距的分类边界来分离样本。因此支持向量机有时被称为大间距分类器

将常数 \(C\) 设置的非常大，对这样的一个数据集得到黑色的决策界，从而最大间距地分离开正样本和负样本。那么在让代价函数最小化的过程中，希望找出在 \(y=1\) 和 \(y=0\) 两种情况下都使得代价函数中左边的这一项尽量为零的参数。如果我们找到了这样的参数，则我们的最小化问题便转变成：

\[\min \frac{1}{2} \sum_{j=1}^{n} \theta_{j}^{2} \text { s.t }\left\{\begin{array}{c}\theta^{T} x^{(i)} \geq 1 \text { if } y^{(i)}=1 \\ \theta^{T} x^{(i)} \leq-1 \text { if } y^{(i)}=0\end{array}\right. $$) 当大间距分类器的时候，学习算法会受异常点(outlier) 的影响。如下图所示  最终得到图中粉色的决策界，仅仅基于一个异常值，就将我的决策界从这条黑线变到这条粉线，这样类似于过拟合。将 C 设置的小一点，最终会得到这条黑线。 如果数据不是线性可分的，如果你在这里有一些正样本或者你在这里有一些负样本，则支持向量机也会将它们恰当分开。 **当$C$不是非常非常大的时候，它可以忽略掉一些异常点的影响，得到更好的决策界。**甚至当你的数据不是线性可分的时候，支持向量机也可以给出好的结果。 $C=1/\lambda$， + $C$ 较大时，相当于 $\lambda$ 较小，可能会导致过拟合，高方差。 + $C$ 较小时，相当于$\lambda$较大，可能会导致低拟合，高偏差。 ## 3 大边界分类数学原理 忽略截距，令${{\theta }_{0}}=0$，这样更容易画示意图。假设特征数 $n$ 为2，因此我们仅有两个特征${{x}_{1}},{{x}_{2}}$ 优化目标可以写作：$\frac{1}{2}\left({\theta_1^2+\theta_2^2}\right)=\frac{1}{2}\left(\sqrt{\theta_1^2+\theta_2^2}\right)^2$，我们只有两个参数${{\theta }_{1}},{{\theta }_{2}}$。括号里面的这一项是向量 ${{\theta }}$ 的范数。 目标函数等于$\frac{1}{2}\left\| \theta \right\|^2$。支持向量机做的事，就是**极小化参数向量 **${{\theta }}$ **范数的平方**。 对于一个训练样本，叉表示正样本 $x^{(i)}$，水平轴上取值为$x_1^{(i)}$，竖直轴上取值为$x_2^{(i)}$。和参数向量一起如上图 $θ^Tx^{(i)}$ 等于$x^{(i)}$ 在 $\theta$ 向量方向上的投影 $p^{(i)}$ 乘 $||\theta||$ 那么 $θ^Tx^{(i)}>=1$ 或 $θ^Tx^{(i)}<-1$ 可以被$p^{(i)}\cdot{x}$ 代替。因为 $θ^Tx^{(i)}=p^{(i)}\cdot{\left\| \theta \right\|}$ 假设支持向量机决策边界是下面绿色边界。它的间距很小。决策界离训练样本的距离很近。支持向量机的结果不会选择它。 对于这个边界的参数${{\theta }}$，参数向量 ${{\theta }}$ 事实上是和决策界是 90 度正交的，所以绿色的决策界对应着一个参数向量 ${{\theta }}$ 这个方向, ${{\theta }_{0}}=0$ 表示决策界必须通过原点$(0,0)$。 一个样本$x^{(1)}$，如果这个样本到参数 ${{\theta }}$ 的投影是这个短的红线段，就等于$p^{(1)}$，对于样本 $x^{(2)}$，它到${{\theta }}$的投影是粉色线段 $p^{(2)}$。$p^{(2)}$ 是一个负值，是在相反的方向 $p^{(i)}$ 都是非常小的数，因此优化目标函数时，对正样本而言，需满足 $p^{(i)}\cdot{\left\| \theta \right\|}>=1$, 如果 $p^{(i)}$ 非常小, 意味 ${{\theta }}$ 范数要非常大.对于负样本同理。但优化目标是 $min.\frac{1}{2}\left\| \theta \right\|^2$  对于一个不同的决策边界如右图绿色线段表示。参数${{\theta }}$ 与横轴正向同向，这个决策界之下，垂直线是决策界。将 $x^{(1)}$ 投影到 ${{\theta }}$ 上，就会得到这样$p^{(1)}$。样本是$x^{(2)}$ 的投影 $p^{(2)}$ 是负值。 $p^{(1)}$ 和 $p^{(2)}$ 这些投影长度比之前的决策边界的投影要长很多。对应的 ${{\theta }}$ 的范数就变小了。这就是支持向量机如何能有效地产生大间距分类的原因。 支持向量机试图极大化这些$p^{(i)}$的范数最终会找到大间距分类器。 ## 4 高斯核函数 对于非线性可分问题例如下面的数据集  为了获得上图所示的判定边界，我们的模型可能是 ${{\theta }_{0}}+{{\theta }_{1}}{{x}_{1}}+{{\theta }_{2}}{{x}_{2}}+{{\theta }_{3}}{{x}_{1}}{{x}_{2}}+{{\theta }_{4}}x_{1}^{2}+{{\theta }_{5}}x_{2}^{2}+\cdots $ 的形式。 用新的特征 $f$ 来替换模型中的每一项。例如令： \]

{{f}{1}}={{x}{1}},{{f}{2}}={{x}{2}},{{f}{3}}={{x}{1}}{{x}{2}},{{f}{4}}=x_{1}^{{2},{{f}_{5}}=x_{2}}{2}，\cdots

\[那么函数变为 \]

h_θ(x)={{\theta }{1}}f_1+{{\theta }{2}}f_2+...+{{\theta }_{n}}f_n

\[除了对原有的特征进行组合这个方式以外，可以利用核函数来计算出新的特征。 给定训练样本 $x$，利用 $x$ 的各个特征与我们预先选定的**地标**(**landmarks**) $l^{(1)},l^{(2)},l^{(3)}$ 的近似程度来选取新的特征$f_1,f_2,f_3$。  例如： \]

{{f}_{1}}=\kappa(x,{{l}^{(1)}})=exp\left({-\frac{{{\left| x-{{l}^{(1)}} \right|}^{2}}}{2{{\sigma }^{2}}}}\right)

\[其中： \]

{{\left| x-{{l}^{(1)}} \right|}^{{2}}=\sum{_{j=1}}{n}}{{({{x}{j}}-l{j}^{(1)})}{2}}

\[表示实例 $x$ 中所有特征与地标 $l^{(1)}$ 之间的距离平方的和。 $similarity(x,{{l}^{(1)}})$ 就是核函数，这里是一个**高斯核函数**(**Gaussian Kernel**)。 **注：这个函数与正态分布没什么实际上的关系，只是看上去像而已。** + 如果一个训练样本 $x$ 与地标 $l$ 之间的距离近似于 0，则新特征 $f$ 近似于$e^{-0}=1$ + 如果训练样本 $x$ 与地标 $l$ 之间距离较远，则 $f$ 近似于 $e^{-(一个较大的数)}\approx0$ 假设训练样本含有两个特征 [$x_{1}$ $x{_2}$]，给定地标 $l^{(1)}$ 与不同的 $\sigma$ 值，见下图：  图中水平面的坐标为 $x_{1}$、$x_{2}$，垂直坐标轴代表 $f$。 从上图看出，只有当 $x$ 与 $l^{(1)}$ 重合时 $f$ 才具有最大值。随着 $x$ 的改变 $f$ 值改变的速率受到 $\sigma^2$ 的控制。 + 下图中，当样本处于粉色点位置处，其离 $l^{(1)}$ 更近，离 $l^{(2)}$ 和 $l^{(3)}$ 较远，因此 $f_1$ 接近1，而$f_2$, $f_3$ 接近0。$h_θ(x)=θ_0+θ_1f_1+θ_2f_2+θ_1f_3>0$，因此预测$y=1$。 + 同理，对于离 $l^{(2)}$ 较近的绿色点，也预测 $y=1$，但是对于蓝绿色的点，因为其离三个地标都较远，预测 $y=0$。  图中红色的封闭曲线所表示的范围，便是依据一个单一的训练样本和选取的地标所得出的判定边界，预测时，采用的特征是通过核函数计算出的新特征 $f_1,f_2,\cdots,f_n$。 ## 5 地标选择 如何选择地标？ 通常根据训练集的数量选择地标的数量，即如果训练集中有 $m$ 个样本，则选取 $m$ 个地标，并令: \]

l^{(1)}=x{(1)},l^{(2)}=x{(2)},.....,l^{(m)}=x{(m)}

\[这样做的表示新特征是建立在原有特征与训练集中所有其他特征之间距离的基础之上的，即： \]

f^{{(i)}=\left[\begin{array}{c}f_{0}}{(i)}=1 \ f_{1}^{{(i)}=\operatorname{\kappa}\left(x}{(i)}, l^{(1)}\right) \ f_{2}^{{(i)}=\operatorname{\kappa}\left(x}{(i)}, l^{(2)}\right) \ f_{i}^{{(i)}=\operatorname{\kappa}\left(x}{(i)}, l^{{(i)}\right)=e}{0}=1 \ \vdots \ f_{m}^{{(i)}=\operatorname{\kappa}\left(x}{(i)}, l^{(m)}\right)\end{array}\right]

\[ 下面我们将核函数运用到支持向量机中，修改我们的支持向量机假设为： \]

h_{\theta}(f)\left{\begin{array}{ll}1 & \text { if } \theta^{\top} f \geqslant 0 \ 0 & \text { othervie }\end{array}\right.

\[相应修改代价函数为： \]

\sum{_{j=1}^{n=m}}\theta _{j}^{{2}={{\theta}}{T}}\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}^{n=m}{\theta _{j}^{2}}

\[在运行中，还需对正则化项进行微调整，在计算 $\sum{_{j=1}^{n=m}}\theta _{j}^{2}={{\theta}^{T}}\theta $ 时，用 $θ^TMθ$ 代替 $θ^Tθ$，其中 $M$ 是根据我们选择的核函数而不同的一个矩阵。 最小化支持向量机的代价函数的方法，可以使用现有的软件包（如**liblinear**,**libsvm**等）。 这些软件包需要编写核函数，如果使用高斯核函数，使用前进行特征缩放是非常必要的。 另外，支持向量机也可以不使用核函数，不使用核函数又称为**线性核函数**(**linear kernel**)，当我们不采用非常复杂的函数，或者我们的训练集特征非常多而样本非常少的时候，可以采用这种不带核函数的支持向量机。 下面是支持向量机的两个参数$C$和$\sigma$的影响： + $C$ 较大时，相当于$\lambda$较小，可能会导致过拟合，高方差； + $C$ 较小时，相当于$\lambda$较大，可能会导致低拟合，高偏差； + $\sigma$ 较大时，可能会导致低方差，高偏差； + $\sigma$ 较小时，可能会导致低偏差，高方差。 ## 6 使用 SVM 在高斯核函数之外我们还有其他一些选择，如： + **多项式核函数（Polynomial Kernel）** \]

\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\left(\boldsymbol{x}{i}^{\mathbf{T}} \boldsymbol{x}{j}\right)^{d}，d\geq 1\text{为多项式的次数}

\[ + 卡方核函数（ **chi-square kernel**, $\chi^{2}$ **kernel**） \]

\kappa(\mathbf{x}, \mathbf{y})=1-\sum_{i=1}^{n} \frac{\left(x_{i}-y_{i}\right)^{2}}{\frac{1}{2}\left(x_{i}+y_{i}\right)}, \text { for } \mathbf{x},\quad \mathbf{y} \in \mathbb{R}^{n}

\[ + **拉普拉斯核函数** \]

\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\exp \left(-\frac{\left|\boldsymbol{x}{i}-\boldsymbol{x}{j}\right|}{\sigma}\right) , \quad\sigma>0

\[ + **Sigmoid 核函数** \]

\kappa\left(\boldsymbol{x}{i}, \boldsymbol{x}{j}\right)=\tanh \left(\beta \boldsymbol{x}{i}^{\mathrm{T}} \boldsymbol{x}{j}+\theta\right) \quad \tanh \text { 为双曲正切函数, } \beta>0, \theta<0

\[ 这些核函数的目标也都是根据训练集和地标之间的距离来构建新特征，这些核函数需要满足 Mercer's 定理，才能被支持向量机的优化软件正确处理。 多类分类问题 假设我们利用之前介绍的一对多方法来解决一个多类分类问题。如果一共有 $k$ 个类，则我们需要 $k$ 个模型，以及 $k$ 个参数向量 ${{\theta }}$。我们同样也可以训练 $k$ 个支持向量机来解决多类分类问题。但是大多数支持向量机软件包都有内置的多类分类功能，我们只要直接使用即可。 参数 $C$ 依然需要自己确定。 **选择机器学习模型** $n$ 为特征数，$m$ 为样本数。 (1) 相较于 $m$，$n$要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，选用逻辑回归模型或者不带核函数的支持向量机。 (2) 如果 $n$ 较小，而且 $m$ 大小中等，例如$n$在 1-1000 之间，而$m$在10-10000之间，使用高斯核函数的支持向量机。 (3) 如果 $n$ 较小，而 $m$ 较大，例如 $n$ 在 1-1000 之间，而 $m$ 大于 50000，则使用支持向量机会非常慢，解决方案是创造、增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。 神经网络在以上三种情况下都可能会有较好的表现，但训练神经网络可能非常慢，选择支持向量机优势在于它的代价函数是凸函数，不存在局部最小值。\]