Coursera ML(13)-SVM(Support Vector Machines)

本节笔记对应第七周课程和西瓜书第六章 支持向量机，主要讲解了支持向量机。

---

SVM介绍

这一部分Coursera上的内容我并没有听懂，一头雾水。

数学上的定义

逻辑回归模型

从最简单的逻辑回国模型说起

$$\begin{align*}& h_\theta (x) = g ( \theta^T x ) \newline \newline& z = \theta^T x \newline& g(z) = \dfrac{1}{1 + e^{-z} }\end{align*}$$

简单点，也就是

$$h_\theta (x) = \dfrac{1}{1 + e^{-\theta^T x} }$$

其图像为：

我们期望的的是底下那两行，而实际给我们的这个sigmoid函数，好像并没有那么完美，这是我们进行少许的处理。

将模型进行抽象

原本的 $h\theta (x) = log \dfrac{1}{1 + e^{-\theta^T x} }$或者$h\theta (x) = log(1-\dfrac{1}{1 + e^{-\theta^T x} })$的图像应该是底下的黑线。

这里，我们定义一个新的新的符号cost，就是上边那个紫色的两条直线组成的东西。
为什幺这么做，食屎啦，我怎么知道为什么这么做，先留着这个问题。

改造一番之后，我们得到了

这个就是支持向量机的数学定义，去他妈的，什么鬼东西，干什么了嘛，SVM就被定义出来了。

直观化的定义

给定这样一个样本集$D={X_1,y_1},{X_2,y_2},{X_3,y_3}……{X_m,y_m},y_i \in(-1,+1)$

我们可以找到很多条直线分割这两个区域

那么我们应该努力去找到哪一个呢？直观上看，那个正中间的黑线看起来很不错。

因为该划分超平面对训练样本的局部扰动容忍度最好。

• 划分超平面可以定义为如下线性方程组： $$w^Tx+b=0$$ 其中$w=(w_1;w_2…;w_d;)$为法向量，决定平面的方向，$b$是位移量。
  将其标记为：$(w,b)$，样本中任一点到超平面$(w,b)$的距离可以表示为： $$r= \dfrac{|w^T+b|}{||w||}$$
• 假定成功分类，那：

• 两个异类支持向量到超平面的距离之和(间隔)为：

  $$\gamma= \dfrac 2{||w||}$$

  那么如果我们可以找到最大的间隔，是不是就可以使这个分割线处于最中间的位置。

• 使距离最小化
  我们换一个表达方式

这就是支持向量机的基本型

万能的拉格朗日－对偶问题

又有周boss的“简单”的数学推导了：这一次是和拉格朗日一起。基本SVM的优化目标本身是一个凸二次规划问题，可以利用优化计算包求解，但是据说拉格朗日有更高效的解法：
对上一节最后式子使用拉格朗日乘子法就可以得到它的对偶问题 （dual problem），对偶问题出现在线性规划中，每一个求极小的线性规划问题都有一个求极大的线性规划问题互称对偶问题，解决了一个就对应解决了其对偶问题。具体到这里，对式子的每条约束添加非负拉格朗日乘子$\alpha_i$，拉格朗日函数是

$$L(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^2+\sum_{i=1}^m{\alpha_i(1-y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b))}$$

对其去$\boldsymbol{w}$和$b$的偏导为0可得到对偶问题：

$$max_\boldsymbol{\alpha}\ \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j$$$$s.t.\ \sum_{i=1}^m{\alpha_iy_i}=0,\ \alpha_i\geq0,\ i=1,2,…,m$$

这又是一个二次规划问题，但通用解法规模正比于样本数，在大规模数据上开销很大，可以考虑其它高效算法如SMO (Sequential Minimal Optimization)。SMO的简单描述是其不断重复以下两个步骤直至收敛：

选取一对需更新的变量$\alpha_i$和$\alpha_j$
固定$\alpha_i$和$\alpha_j$以外的参数，求解对偶问题更新后的$\alpha_i$和$\alpha_j$。

SMO算法在一时间也不能得到完整的理解，希望能作为学习二次规划问题的一个复杂例子在之后研究。

核函数－核函数

为什么要使用核函数

原始样本空间也许并不存在一个可以正确划分两类样本的超平面，一个比较好的解决办法，试讲当前原始空间映射到一个高维空间去。根据某些大佬的研究，如果原始样本空间是有限的，那么总可以找到一个高维特性空间使样本可分。

其实这个问题在西瓜书上说的非常清楚，但是笔记却无法做，主要是相关的图我找不出来，好气哦。

详细介绍

取映射函数$\phi$，特征空间划分超平面模型表示为：

$$f(x)=\boldsymbol{w}^T\phi(x)+b$$

类似的有问题变为了：

$$min_{\boldsymbol{w},b} \frac{1}{2}\|\boldsymbol{w}\|^2$$$$s.t.\ y_i(\boldsymbol{w}^T\phi(\boldsymbol{x}_i)+b)\geq1,\ i=1,2,…,m$$

其对偶问题是：

$$max_\boldsymbol{\alpha}\ \sum_{i=1}^m\alpha_i-\frac{1}{2}\sum_{i=1}^m\sum_{j=1}^m\alpha_i\alpha_jy_iy_j\phi(\boldsymbol{x}_i^T)\phi(\boldsymbol{x}_j)$$$$s.t.\ \sum_{i=1}^m{\alpha_iy_i}=0,\ \alpha_i\geq0,\ i=1,2,…,m$$

这中间涉及了$\phi(\boldsymbol{x}_i^T)\phi(\boldsymbol{x}_j)$，是样本映射到高维空间后的内积，由于维数可能很高甚至无穷，其计算很困难。此时我们就需要找一个函数，使得：

$$\kappa(\boldsymbol{x_i},\boldsymbol{x_j})=\phi(\boldsymbol{x}_i^T)\phi(\boldsymbol{x}_j)$$

称作核函数 (kernal function)。
有定理表明：只要一个对称函数对应的核矩阵半正定，它就能作为核函数使用。几种常用的核函数有：

名称	表达式	参数
线性核	$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\boldsymbol{x}_i^T\boldsymbol{x}_j$
多项式核	$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=(\boldsymbol{x}_i^T\boldsymbol{x}_j)^d$	$d \geq 1$为多项式的次数
高斯核	$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\exp(-\frac{∥\boldsymbol{x}_i-\boldsymbol{x}_j∥^2}{2\sigma^2})$	$\sigma \geq 0$为高斯核的带宽
拉普拉斯核	$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\exp(-\frac{∥\boldsymbol{x}_i-\boldsymbol{x}_j∥}{\sigma})$	$\sigma \geq 0$
Sigmoid核	$\kappa(\boldsymbol{x}_i,\boldsymbol{x}_j)=\tanh(\beta\boldsymbol{x}_i^T\boldsymbol{x}_j+\theta)$	$\tanh$为双曲正切函数，$\beta>0,\theta<0$

多个核函数的线性组合，两个核函数的直积均为核函数，以及若$\kappa_1$为核函数，对于任意函数$g(\boldsymbol{x})$有：$\kappa(\boldsymbol{x},\boldsymbol{z})=g(\boldsymbol{x})\kappa_1(\boldsymbol{x},\boldsymbol{z})g(\boldsymbol{z})$也是核函数
如何选择核函数将样本映射到真正显示其分布规律的高维空间非常重要。

软间隔与正则化

实际上很多问题并不能简单地归结为线性可分线性不可分，一些问题的样本空间看来是线性可分的，但总有几个样本跑到了敌对阵营，就为此强行升高维度显然得不偿失。于是引入了软间隔 (soft margin)：允许有若干个样本被线性空间划分错误。此时的优化目标变为：

$$min_{\boldsymbol{w},b}\ \frac{1}{2}\|\boldsymbol{w}\|^2+C\sum_{i=1}^m\ell_{0/1}(y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1)$$

其中$C$是一个常数，可以理解问允许多少个样本被分错，而$\ell_{0/1}$是0/1损失函数，当样本被分错时，它的取值为1，否则为0。这个函数直观，简单，然而非凸，非连续，常用一些替代函数：

hinge损失：$\ell{hinge}(z)=\max(0,1,1-z)$
指数损失 (exponential loss)：$\ell{exp}(z)=\exp(-z)$
对率损失 (logistic loss)：$\ell_{log}(z)=\log(1+\exp(-z))$

• 红色为：hinge损失
• 蓝色为：指数损失
• 黑色为：对率损失
  这个地方跟最开始的时候提到的图像好像，只不过Andrew直接就把结果说出来了，并没有解释为什么罢了。

代入优化目标后同样可以找到它们的对偶问题进行求解。实际上此时的优化目标可以看作两部分：第一项描述划分超平面的间隔大小，第二项描述数据集上的误差。对于误差还有更一般的形式：$min_{f}\ \Omega(f)+C\sum_{i=1}^m\ell(f(\boldsymbol{x}_i),y_i)$其中$\Omega(f)$称为结构风险，后一项称为经验风险，$C$用于对二者进行折中。结构风险方便引入领域知识和用户意图：用户希望得到何种性质的模型，同时它也有助于削减假设空间。这个式子称为正则化 (regularization)。

回归问题－支持向量回归

普通的回归问题计算损失为函数预测值与真实值的差，而使用支持向量回归 (Support Vector Regression, SVR)，我们容忍$\epsilon$的误差，那就相当于在预测函数两端建立了一个宽为$2\epsilon$的隔离带，在此间隔带种的样本被默认为预测正确，而在此间隔带外的样本计算它的真实值与预测函数得到值的差作为损失，就此SVR问题可形式化为：

$$min_{\boldsymbol{w},b}\ \frac{1}{2}\|\boldsymbol{w}\|^2+C\sum_{i=1}^m\ell_{\epsilon}(f(\boldsymbol{x}_i)-y_i)$$

其中$C>0$是一个常数,$l_{0/1}$是”0/1”损失函数

常见的损失函数有hinge损失,指数损失,对率损失(见P130).

采用hinge损失,引入”松弛变量”(slack variables),上式可重写为

对偶问题推导以及解稀疏性证明见P132.

支持向量引申到回归问题上即可得到支持向量回归(Support Vector Regression, SVR)。
SVR假设我们能容忍$f(\mathbf x)$与$y$之间最多有$\epsilon$的偏差，即仅当$f(\mathbf x)$与$y$之间的差别绝对值大于$\epsilon$时才计算损失。SVR问题可化为

其中 $ C $为正则化常数,$l_\epsilon$为$\epsilon$-不敏感损失函数

对偶问题推导以及KKT条件证明见P135-137.

核(nuclear)方法

给定训练样本,不考虑偏移项$b$,则无论SVM还是SVR,学得的模型总能表示成核函数$\kappa(\mathbf{x_i,x_j})$的线性组合.因此有更一般的”表示定理”(representer theorem).P137。

由此人们发展了一系列基于核函数的学习方法，统称为核方法 (kernel methods)。最常见的就是引入核函数来将线性学习器拓展为非线性学习器，从而得到核线性判别分析 (Kernelized Linear Discriminant Analysis)。