支持向量机

LR →SVM

在逻辑回归问题中，我们希望输入sigmod函数中的函数值离0越远越好，因为离0越远，我们判断的"把握"就越大。也就是说我们希望找到一个分类器使得待分类点距离分类的平面尽可能的远，换言之也是一样分类判断的把握尽可能大。这就延伸出了一种二分类模型-支持向量机
支持向量机就是一种二分类模型，其基本模型定义为特征空间上间隔最大的线性分类器,其学习策略就是间隔最大化。

The support-vector network combines 3 ideas: the solution technique from optimal hyperplanes (that allows for an expansion of the solution vector on support vectors), the idea of convolution of the dot-product (that extends the solution surfaces from linear to non-linear), and the notion of soft margins (to allow for errors on the training set).

样本比较多的时候，Boosting和RF往往能得到最好的效果，但是数据集较少的时候，SVM的效果可能会比较好。

线性可分

学习策略

最大间隔法

SVM希望找到一个最优的超平面，在将所有的点分类正确的前提下，并使得使得所有的点到超平面的距离最大化（最大化间隔）。这里我们不妨让超平面的方程为$w^Tx+b=0$，

分类正确有:

$\begin{cases}\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b > +1, & y_{i}=+1 \\ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b <-1, & y_{i}=-1\end{cases}$

进一步化简则有约束条件为:

$y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_{i}+b)>1$

距离最大有:

$\sum_x \frac{|\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_{i}+b|}{||\boldsymbol{w}||}=\sum_x \frac{y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_{i}+b)}{||\boldsymbol{w}||}$

N维空间任何一点$\left(x_{10},x_{20},\dots x_{N0}\right)$到超平面$w_1x_1+w_2x_2+\dots w_Nx_N+b=0$的欧氏距离的计算公式主要借助平面外一点和平面内一点组成的向量与平面的单位法向量作点乘计算得到，详细步骤不做赘述。

另外为了进一步简化计算，我们知道当平面的法向量$\boldsymbol{w}^\mathrm{T}$与$b$同时扩大一倍时平面的方程是没有任何改变的，因此为了进一步简化计算，在实际求解过程中我们会令$y_i(\boldsymbol{w}^\mathrm{T}\boldsymbol{x}_{i}+b)=1$这样相当于只求解$\boldsymbol{w}^\mathrm{T}$即可解得最优的超平面位置，接着在对距离函数取个倒数，然后支持向量机的学习策略变成了：

然后我们取$w^Tx+b=\pm1$的点组成支持向量，然后将两个异类支持向量到超平面的距离定义为间隔（‘margin’）

\begin{align*} \min &\hspace{5pt}\frac{||w||^2}{2}\\ s&.t.\hspace{5pt} y_i(w^Tx_i+b)\ge1 \end{align*}

这就是支持向量机( Support Vector Machine,简称SVM)的基本型。
接着我们研究这个的求解，观察发现这个规划问题是一个凸二次规划问题(目标函数和约束函数都为$R^n$上可微的凸函数，约束函数都为线性函数/仿射函数)，存在全局最优解，可以借助规划类问题的包进行求解，但我们可以利用更高效的方法来求解。

拉格朗日对偶

将有约束的原始目标函数转化为无约束的新构造的拉格朗日目标函数

\begin{equation} L(w,a,b)=\frac{1}{2}||w||^2+\sum_{i=1}^I \alpha_i[(1-y_i(w^T x_i+b)] \end{equation}

利用拉格朗日函数对偶性，将不易求解的优化问题转化为易求解优化问题

观察原始的目标函数我们会发现L函数有最大值$\frac{1}{2}||w||^2$,所以可以把极小值看成是极小值极大值问题：

\begin{equation} \min_{w,b}\theta(w)=\min_{w,b}\max_{\alpha_i\ge0} L(w,a,b)=p^* \end{equation}

接着根据对偶性取一个函数：

\begin{equation} \max_{\alpha_i\ge0}\min_{w,b} L(w,a,b)=d^* \end{equation}

根据KKT条件，最优解满足的条件为:

\begin{equation} \begin{gathered} \frac{\partial L(w, b, \alpha)}{\partial w}=w-\sum_{j} \alpha_{j} y_{j} x_{j}=0 \\ \frac{\partial L(w, b, \alpha)}{\partial b}=\sum_{j} \alpha_{j} y_{j}=0 \end{gathered} \end{equation}

将上述值代入式子3，原来的最优化问题也就转化为了：

\begin{equation} \begin{aligned} \min _{\alpha} & \frac{1}{2} \sum_{i=1}^{N} \sum_{j=1}^{N} \alpha_{i} \alpha_{j} y_{i} y_{j}\left(x_{i} \cdot x_{j}\right)-\sum_{i=1}^{N} \alpha_{i} \\ \text { s.t. } & \sum_{i=1}^{N} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \cdots, N \end{aligned} \end{equation}

这样的话原来的优化问题就转化成了上述的形式，而对于模型的参数学习过程也变成了求解上述优化问题的过程。假设解得的最优解为$\alpha_i^*$，根据KKT条件有：

\begin{equation} \alpha_{j}^*\left[\left({w} \cdot x_{j}+b\right) y_{j}-1\right]=0 \end{equation}

这样我们可以得到所要求的$w$为：

\begin{equation} w=\sum_{j} \alpha_{j}^* y_{j} x_{j} \end{equation}

这里的$\boldsymbol{w}^\mathrm{T}$相当于每一个权值向量的分量。通过观察上述两个式子，我们会发现，其实有很多$\alpha^*$是必须为零的，因为对于一些分类效果比较好的点来说$(w\cdot x_j)y_j>1$，因此为了满足KKT条件，他们的$\alpha^*$必须为零，而当$\alpha^*$为零时，那么与之相关的样本点其实对$w$的取值是没有影响的，**换言之，真正会影响分类超平面的点是很少的一部分点，**这些点满足：

\begin{equation} (w\cdot x+b)y-1=0 \end{equation}

即真正会影响分类超平面位置的点应该落在了分类平面上，我们把这些真正会影响到分类超平面的点叫做支持向量，接着我们也可以用这些点的坐标代入平面的方程解得对应的b为：

\begin{equation} b=y_k-w\cdot x_k(\alpha_k>0) \end{equation}

分类决策函数可以写作：

\begin{equation} f(x)=\operatorname{sign}\left(\sum_{i=1}^{N} \alpha_{i}^{*} y_{i}\left(x \cdot x_{i}\right)+b^{*}\right) \end{equation}

最大间隔分离平面的唯一性

线性可分训练数据集的最大间隔分离超平面是存在且唯一的。
存在性：最优化问题形式决定了这个问题必定是有解的（显然$\omega\ne0$)
唯一性：

软间隔最大化

硬间隔分类的一个最大的问题是把数据想象的过于理想，有的时候数据集是存在噪声的，即可能出现下图的情况：

为此，人们引入松弛变量ξ，对应数据点允许偏离的函数距离的量，使得SVM方法能够处理噪声数据。引入松弛变量$\xi$的优化问题为：

\begin{equation} \begin{array}{ll} \min\limits _{w, b, \xi} & \frac{1}{2}\|w\|^{2}+C \sum_{i=1}^{N} \xi_{i} \\ \text { s.t. } & y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}, \quad i=1,2, \cdots, N \\ & \xi_{i} \geqslant 0, \quad i=1,2, \cdots, N \end{array} \end{equation}

上述分类问题仍然可以通过最大化硬间隔的优化思路来求解（$\xi$看做变量即可）
首先取拉格朗日函数：

\begin{equation} \begin{aligned} \mathcal{L}(w,b,\alpha,\gamma)&=\min_{w,b}\max_{\alpha,\gamma}\\ &=\frac{1}{2}w^2+C\sum \xi_i+\sum_{i}\alpha_i(1-\xi_i-y_i(w\cdot x_i+b))-\sum_{j}\gamma_j\xi_j\\ &(\alpha_i,\gamma_j\ge0) \end{aligned} \end{equation}

对偶问题为：

\begin{equation} \begin{aligned} &\max _{\alpha, \gamma} \min _{\mathrm{w}, \mathrm{b}} L(w, b, \xi, \alpha, \gamma) \\ &=\frac{1}{2} w^{T} w+C \sum_{j} \xi_{j}-\sum_{j} \alpha_{j}\left(\left(w^{T} x_{j}+b\right) y_{j}-1+\xi_{j}\right)-\sum_{j} \gamma_{j} \xi_{j} \\ \end{aligned} \end{equation}

最优解

\begin{equation} \begin{gathered} \frac{\partial L(w, b, \alpha)}{\partial b}=\sum_{j} \alpha_{j} y_{j}=0 \\ \frac{\partial L(w, b, \alpha)}{\partial w}=w-\sum_{j} \alpha_{j} y_{j} x_{j}=0 \\ \frac{\partial L(w, b, \alpha)}{\partial \xi_{j}}=C-\alpha_{j}-\gamma_{j}=0 \end{gathered} \end{equation}

消去不需要的变量：

\begin{equation} \begin{aligned} &\max _{\alpha, \gamma} L(\alpha, \gamma) \\ &=\frac{1}{2} \sum_{i} \sum_{j} \alpha_{i} y_{i} \alpha_{j} y_{j} x_{i}^{T} x_{j}+C \sum_{j} \xi_{j}-\sum_{i} \sum_{j} \alpha_{i} y_{i} \alpha_{j} y_{j} x_{i}^{T} x_{j} \\ &-\sum_{j} \alpha_{j} y_{j} b+\sum_{j} \alpha_{j}-\sum_{j} \alpha_{j} \xi_{j}-\sum_{j} \gamma_{j} \xi_{j}\\ \quad \text { s.t. } &\sum_{j} \alpha_{j} y_{j}=0, \alpha_{j} \geq 0, \gamma_{j} \geq 0, C-\alpha_{j}-\gamma_{j}=0 \end{aligned} \end{equation}

根据对$\xi$的偏导的取值(式4)，可以对上述优化问题做一个简化：

\begin{equation*} \begin{aligned} \max _{\alpha, \gamma} L(\alpha, \gamma) &=-\frac{1}{2} \sum_{i} \sum_{j} \alpha_{i} y_{i} \alpha_{j} y_{j} x_{i}^{T} x_{j}+\sum_{j} \alpha_{j} \\ &=\frac{1}{2} \sum_{i} \sum_{j} \alpha_{i} y_{i} \alpha_{j} y_{j} x_{i}^{T} x_{j}-\sum_{j} \alpha_{j} \\ \quad \text { s.t. } &\sum_{j} \alpha_{j} y_{j}=0, 0\le\alpha_{j}\leq C, \gamma_{j} \geq 0, \end{aligned} \end{equation*}

然后同样的回过头来看一下对w的取值：

\begin{equation} w=\sum_{j} \alpha_{j}^* y_{j} x_{j} \end{equation}

可以发现其实w的取值是没有改变的，这也意味着软间隔情况下也是只有一部分点起作用，接下来我们找出起作用的那一部分点：

\begin{equation} \begin{aligned} &\alpha_i(1-\xi_i-y_i(w\cdot x_i+b))=0\\ &\gamma_i\xi_i=0\\ &C-\alpha_i-\gamma_i=0\\ &0\le\alpha_{j}\leq C \end{aligned} \end{equation}

通过分情况讨论我们发现：

• 欲使$\alpha\ne 0\text{应该有}1-y_i(w\cdot x_i+b)=\xi_i$
  • $1-y_i(w\cdot x_i+b)$=0则有$\gamma_i\ne0,\alpha_i=c$，进而求得b
  • $1-y_i(w\cdot x_i+b)>0,\gamma_i\ne0,0\le\alpha_{j}\leq C$

也就是说短间隔下的支持向量的点在分离超平面误分离一侧。

决策函数

与硬间隔下的决策函数一致

合页损失函数

\begin{equation} \begin{aligned} &\alpha_i(1-\xi_i-y_i(w\cdot x_i+b))=0\\ &\gamma_i\xi_i=0\\ &C-\alpha_i-\gamma_i=0\\ &0\le\alpha_{j}\leq C \end{aligned} \end{equation}

接着上述的条件约束对$\xi_i$进行分析：

• $y_i(w\cdot x_i+b)>1,\text{分类正确},\xi_i=0$
• $y_i(w\cdot x_i+b)=1,\xi_i=1-y_i(w\cdot x_i+b)=0$
• $y_i(w\cdot x_i+b)<1,\xi_i=1-y_i(w\cdot x_i+b)$

于是我们可以设一个函数$\xi_i=[1-y_{i}\left(w \cdot x_{i}+b\right)]_{+}$，其中$+$表示正例，$-$表示负例，这样就可以得到一个合页损失函数：

\begin{equation} [z]_{+}= \begin{cases}z, & z>0 \\ 0, & z \leqslant 0\end{cases} \end{equation}

通过上述的分析我们发现，虽然开始时给定的约束条件为$y_{i}\left(w \cdot x_{i}+b\right) \geqslant 1-\xi_{i}$
，但在求解最优解的时候其实最后取的都是$[1-y_i\left(w \cdot x_i+b\right)]_{+}$。我们又把这种损失函数叫做合页损失函数（形状像一个合页）

合页损失函数与感知机损失函数相比可以看出SVM分类要求更高，因为该函数不仅要求分类正确，还要求确信度足够高。

命中注定

软间隔最大化,也可以看成下述目标函数的最小化:

\begin{equation} \sum_{i=1}^{N}\left[1-y_{i}\left(w \cdot x_{i}+b\right)\right]_{+}+\lambda\|w\|^{2} \end{equation}

其中$\lambda$是惩罚函数，控制目标函数中两项（“寻找间隔最大的超平面”和“数据点偏差量最小”）之间的权重，是一个事先确定的常量.
于是软间隔下的性能度量函数也可以写成：

\begin{equation} \sum_{i=1}^{N}\left[1-y_{i}\left(w \cdot x_{i}+b\right)\right]_{+}+\lambda p(w) \end{equation}

拟合项+正则化项。一个衡量泛化能力，一个衡量模型的训练误差。

所有的一切在我们定义那个简单的优化问题时所有东西都已经注定了，后来的推导只是在发现它们罢了

线性不可分

非线性问题的分类往往不好求解，我们希望采取一个非线性变换，把非线性问题变成线性问题，然后通过解变换后的线性问题来解决原来的非线性问题。

• 使用变换将数据映射到高维空间
• 在新空间里用线性分类学习方法学习模型

核技巧就属于这样的方法

生活中一个常见的例子是桌子上混放着两种重量不同的小球，用力拍打桌子。小球弹在空中，重的球弹得低，轻的球弹得高，这使得本来不可分的小球变得可分。

这种类似拍桌子的方法我们叫做核函数，它的作用是将样本映射到高维空间。

在学习与预测的过程中，只定义核函数$K(x,z)$而不显式地定义映射函数。在线性分类中，我们也可以利用相同的办法来定义$K(x,z)$来定义内积，然后如果核函数给定的话，就可以利用线性分类问题的解决方法来解决问题了。学习是隐式地在特征空间进行的，不需要显式地定义特征空间和映射函数。这样的技巧称为核技巧，它是巧妙地利用线性分类学习方法与核函数解决非线性问题的技术。在实际应用中，往往依赖领域知识直接选择核函数，核函数选择的有效性需要通过实验验证。

如果原始空间维数是有限的，即特征的数量是有限的，那么一定存在一个高维特征空间，将原始样本映射到高维空间后线性化，从而找到一个分类超平面将样本进行分类。

正定核的充要条件

常用核函数

线性核函数

$K(x_1,x_2)=x_1\cdot x_2$
线性核主要用于线性可分的情况，实际就是原始空间中的内积。这个核存在的主要目的是使得“映射后空间中的问题”和“映射前空间中的问题”两者在形式上统一起来了。这样统一的目的是为了在编写代码或写公式时，能够使用通用表达式，然后再代入不同的核，在形式上统一起来。

多项式核函数

$K(x_1,x_2)=(x_1\cdot x_2+1)^p$
多项式核函数可以实现将低维的输入空间映射到高维的特征空间。
但是多项式核函数的参数多，当多项式的阶数比较高的时候，核矩阵的元素值将趋于无穷大或者无穷小，计算复杂度会大到无法计算。

高斯（RBF）核函数

高斯核函数又称径向基核函数:

$K(x_1,x_2)=\exp\left(-\frac{||x_1-x_2||^2}{\sigma^2}\right)$
高斯径向基函数是一种局部性强的核函数，它可以将一个样本映射到一个更高维的空间内。
该核函数是应用最广的一个，无论大样本还是小样本都有比较好的性能，而且其相对于多项式核函数参数要少**。因此大多数情况下在不知道用什么核函数的时候，优先使用高斯核函数**。

sigmod核函数

$k<x_1,x_2>=tanh(<\eta<x_1,x_2>+\theta>)$
采用sigmoid核函数，支持向量机实现的是一种多层神经网络。
总结：在处理分类问题时，如果对数据有一定的先验知识，就利用先验知识选择核函数。
如果没有，通常使用交叉验证的方法来试用不同的核函数，误差最小的即为效果最好的核函数。也可以将多个核函数结合起来形成混合核函数。

非线性支持向量机

高效实现SVM学习（SMO）

实际应用过程中对于数据量较大的样本的学习非常低效，人们提出了许多快速实现实现算法，序列最小最优化算法（Sequential minimal optimization）是其中的一种。

SMO算法是支持向量机学习的一种快速算法，其特点是不断地将原二次规划问题分解为只有两个变量的二次规划子问题，并对子问题进行解析求解，直到所有变量满足KKT条件为止（可以认为如果两个变量的规划问题满足该条件，则说明在将其余变量固定时求得的解是最优解）。这样通过启发式的方法得到原二次规划问题的最优解。因为子问题有解析解，所以每次计算子问题都很快，虽然计算子问题次数很多，但在总体上还是高效的。

多分类的支持向量机

支持向量机本身是一种二分类模型，多分类的支持向量机一般是采取本质上还是二分类，通过不同的划分方式将多个种类的样本转化为两类的样本来实现分类，比较常见的两种划分方式：

• One aginst one:从总的n类中选两类构造一个分类器，然后不同的分类器对输入样本的判断值进行投票
• one-vs-the-rest：丛总的样本中选取一个样本为一类，其余样本为另一类

总结

支持向量机出现最重要的一点是表现出了人们对于模型泛化能力的要求，在支持向量机之前，其实我们更关注的是模型的训练误差，支持向量机要做的，其实是在**分类精度不改变的前提下，**增强模型对那些未知数据的预测能力（最小化有到最大化无的转变）
LR引入了正则化项，LR引入l2范数就是拉索回归。

感想

下午听了孟德宇老师讲SVM，整理课堂讲的内容整了3个小时，虽然之前也或多或少接触了一点SVM，但是感觉并没有真正地看到这些模型背后的奇妙之处，虽然说已经不敢苛求自己把什么都看懂，但是当听到老师讲的如此丝滑之后或多或少觉得之前读的有些过于敷衍。或许大概自己在机器学习的道路上还有很长的路要走。
03-24孟德宇.rar