这一节我们主要学习
- 支持向量机的介绍
- 铰链损失
- 线性支持向量机
- 核方法
1. 支持向量积
支持向量机(SVM)基本模型是定义在特征空间上的间隔最大的线性分类器，主要有 2 大特点: Hinge Loss 和 Kernel Method 。
SVM是一种分类模型，利用支持向量寻找超平面，可以用于解决回归和分类问题。
2. 铰链损失函数
在步骤 2中，如果我们采用 $\delta (g(x^n) \ne \hat y^n)$ ,在第三步对目标函数进行优化的时候，会出现不可微分的情况。
其中$\delta (g(x^n) \ne \hat y^n)$ 函数表示，当 $g(x^n)$ 和 $y^n$ 不相等时，函数值取 1 ；当 $g(x^n)$ 和 $y^n$ 相等时，函数值取 0 。
我们使用一个近似的函数 $l(f(x^n),\hat y^n)$ 来代替函数 $\delta (g(x^n) \ne \hat y^n)$ 来解决优化过程出现的不可微分的问题。
$\hat{y}f(x)$ 表示训练集中数据的标签值。当标签值为 +1 时，我们希望 $f(x)$ 的值越正越好；当标签值为 -1 时，我们希望 $f(x)$ 的值越负越好。
整体来看，我们希望 $\hat y^nf(x)$ 的值越大越好。 $\hat y^nf(x)$ 的值越大，损失就越小。
我们用横坐标 $\hat y^nf(x)$ 的值，纵坐标表示损失函数的值。
理想的损失函数 $\delta (g(x^n) \ne \hat y^n)$在优化过程中出现不可微分的情况，
我们使用近似的函数 $l(f(x^n),\hat y^n)$来代替，其中损失函数可以由我们自己来定义。
当 $\hat y^n=+1$ 时，我们希望 $f(x)$ 的值越接近 +1 越好；当 $\hat y^n=-1$ 时，我们希望 $f(x)$的值越接近 -1 越好。
平方损失函数（红色的线）可表示为 $l(f(x^n),\hat y^n)={(\hat y^nf(x^n)-1)}^2$。
但是该函数是不合理的：当 $\hat{y}f(x)$ 很大时，损失函数的很大，不满足我们对损失函数的要求。
当 $\hat y^n=+1$ 时，我们希望 $\delta (f(x))$ 的值越接近 +1 越好；当 $\hat y^n=-1$ 时，我们希望 $\delta (f(x))$ 的值越接近 0 越好。
平方损失函数（蓝色的线）可表示为$l(f(x^n),\hat y^n)={ (\delta (\hat y^nf(x^n))-1)}^2$ 。
但实际上在解决二分类问题，利用逻辑回归方法时，我们不会用 $square$ $loss$ 作为损失函数，而是使用$cross$ $entropy$。
利用 $ sigmoid + cross entropy$ 计算得到的损失函数表达式为$l(f(x^n),\hat y^n)=ln(1+exp(-\hat y^n f(x))$
Sigmoid + cross entropy：绿色线；图片中曲线除以ln2
Sigmoid + cross entropy：蓝色线；
绿色曲线的损失函数一侧趋于 0 ，一侧趋于无穷大，是合理的。
比较绿线和蓝线，可知道为什么在逻辑回归时要用cross entropy作为损失函数，而不用square loss：
$\hat{y}f(x)$ 从-2变到-1时，蓝色线变化很小，绿色线变化很大；
或者说绿色曲线：努力就可以有回报；而蓝色曲线：没有回报不想努力 来理解这段关系。
$\hat{y}f(x)$ 很负时，应该朝正方向调整，但对蓝色线来讲调整没有回报，而对绿色线调整有回报。
损失函数 $l(f(x^n),\hat{y}^n)=max(0,1-\hat y^nf(x))$，在图中由紫色的线表示。
当 $\hat y^nf(x)$ 的值大于 1 的时候，$loss$ 的值为 0；
当 $\hat y^nf(x)$ 的值在 0 和 1 之间的时候，$loss$ 会有一个较小的值，表示预测的结果还不足够好，需要继续优化。
函数表达式中的 “1” 可以看做是 $Ideal$ $loss$ 的上界,我们希望通过最小化铰链损失函数的值来达到最小化理想损失函数的目的。
- $Hinge$ $Loss$ 与$Sigmoid + cross entropy$ 相比，区别在于：
当 $\hat y^nf(x)$ 的值大于 1 的时候，$Hinge$ $Loss$将不再进行优化,而 $Sigmoid + cross entropy$ 会继续对目标函数进行优化；
在实践中的过程中两者的表现相差无几，当遇到 $outlier$ 的情况的时候，$Hinge$ $Loss$ 的表现要更好，具有较强的鲁棒性。
3. 线性支持向量机（Linear SVM）
- 步骤一：线性支持向量机中的 $f(x)$ 是线性的，可以表示为两个向量的内积的形式。
- 步骤二：支持向量机中的损失函数通常采用铰链损失函数,通常还会加上正则化的部分。
- 步骤三：由于损失函数中的铰链损失函数和正则化的部分都是凸函数，所以损失函数也是凸函数，可以通过梯度下降找到最优解。
忽略正则化的部分，使用梯度下降的方法最小化损失函数关键在于求解损失函数对权重 $w$ 的偏微分。
这里我们使用链式法则来求解，重点在于求解 $\frac{\partial l(f(x^n),\hat y^n)}{\partial f(x^n)}$：
当 $\hat y^nf(x^n)$ 小于 1 时，偏导值为$-\hat y^n$ ;
当$\hat y^nf(x^n)$< 大于 1 时，偏导值为 0。
图中红色方框等于$x^n_i$ , 将划红线的部分定义为$c^n(w)$（依赖于现在的参数w），红线后面的$x_i$ 应改为$x^n_i$。
我们将 $l(f(x^n),\hat{y}^n)$ 记作 $ε^n$：
上下两个红色方框里的内容是不等价的（上面可以推出下面，但是下面不能推出上面），但是加上“最小化损失函数 L”这个条件之后，二者就等价了。
下面红色方框里的式子就是我们常见的 SVM 的约束形式，$ε^n$ 称为松弛因子。
在满足上述约束条件的情况下，我们需要求解损失函数的最小值。这是一个二次规划问题，因此我们可以使用二次规划的方法求解支持向量机的问题。
针对以上两种不同形式的支持向量机，我们分别可以使用梯度下降和二次规划的方法来求解。
4. 核方法
核方法是SVM的第二大特点。核方法的主要思想是基于这样一个假设：
“在低维空间中不能线性分割的点集，通过转化为高维空间中的点集时，很有可能变为线性可分的”。
- 双重表征指的是：最小化损失函数的权重参数$w^∗$ 可以表示为数据点$x^n$ 的线性组合。
我们可以从梯度下降的角度来理解该性质：
假设 $w$ 初始化为零向量的，则得到的$w^∗$ 可以看做是 $x^n$ 的线性组合，其中的权重$c^n(w)$ 是损失函数$l(f(x^n),\hat{y}^n)$ 对 $f(x^n)$ 的偏导数。
由于损失函数采用的是 Hinge Loss，很多的 $c^n(w)$ 可能为 0，从而 $α_n^∗$ 是稀疏的的，而那些具有非零 $α_n^∗$ 的数据点 $x^n$ 称为支持向量。
这样的好处是模型具有较好的鲁棒性：
不是支持向量的数据点，就算去掉也不会对结果有影响，outlier只要不是支持向量，就不会对结果有影响。
相比于使用交叉熵作为损失函数的逻辑回归模型，它在更新参数时的权重就不稀疏的，所以每笔数据都对结果有影响。
把 w 写成 $x^n$ 的线性组合，最大的好处是可以使用核技巧将函数 f(x) 用核函数表示：
根据 $w=X \alpha$, $f(x)$ 可以写成 $f(x)=Σ_n$ $\alpha_n (x^n⋅x)$ 的形式，
由于用的损失函数是 Hinge Loss，所以 $α_n$ 是稀疏的的，只需要计算支持向量与数据点x之间的内积即可。
我们把内积 $(x^n⋅x)$ 写作 $K(x^n,x)$ 的形式，将其称为核函数。
将损失函数可以改写为上图中的样子，我们不需要知道 $x$，只需要知道核函数 $K(x,z)$ 的值即可，这种方法就叫做核技巧。
核技巧不只可用于支持向量机，也可用于逻辑回归、线性回归等模型。
【图中”project”应改为”product”】
我们处理分类问题时可能会遇到一些线性不可分的情况，此时我们需要对数据特征做一些特征变换再进行分类，
而我们可以使用核函数来达到相同的效果，而且使用核函数来进行计算会比先进行特征变换再计算内积更快。
径向基函数可以用于衡量 x, z 的相似程度：x 和 z越接近，核函数的值就越大。
将核函数展开为泰勒级数的形式，可以看出该函数等价于最高维度为无穷多维向量的向量内积的多项式形式。
使用该径向基核函数（RBF Kernel）的效果等同于将数据特征转换到无穷多维的平面上再处理问题，但是使用该核函数容易出现过拟合的问题。
当我们使用 Sigmoid 核函数的时候，我们可以将支持向量机的模型看做只有一个隐藏层的神经网络。
其中神经元的个数就是支持向量个数，而权重就是对应的支持向量。
【图中$α^n,α^1,α^2$ 应改为 $α_n,α_1,α_2$ 】
在使用核技巧构造核函数之后，我们就不需要关注输入特征的具体形式，而只需要关注 x 和 z 的内积的结果。
这种做法在处理某些结构化的数据的时候比较方便，比如声音信号；
我们使用核方法进行处理不需要关注声音信号转换成向量的具体形式，只需关注它们代入核函数得到的结果即可。
核函数是用来描述变量间相似程度的，不是所有的 $K(x,z)$ 都可以拆成$ϕ(x)⋅ϕ(z)$。
核函数的必要条件：K是有效的核函数 ==> 核函数矩阵K是对称半正定的；我们可以参考Mercer定理。
SVM related methods:
- Support Vector Regression (SVR)
- [Bishop, Chapter 7.1.4]
- Ranking SVM
- [Alpaydin, Chapter 13.11]
- One-Class SVM
- [Alpaydin, Chapter 13.11]
深度学习前几层可能就是在做特征转换，接着再一个线性分类。
在SVM同样如此，基于核函数同样能够进行特征转换，在新的特征空间中再用线性分类器进行分类。
区别在于深度学习中的“核函数”是更加强大的。
5. 总结
主要介绍了支持向量机方法的两大特点Hinge Loss和核方法（Kernel Method）。