网络建设方案总结_免费制作手机app软件_成都网络营销_百度点击器下载

Abstract:

This week, I focused on Support Vector Machines (SVMs), covering their core concepts, the difference between SVMs and logistic regression, and the use of kernel functions for non-linear classification. The report also provides a brief comparison and guidelines for choosing between SVMs and logistic regression based on dataset characteristics.

支持向量机(Support Vector Machines)

SVM概述

支持向量机 ( Csupport vector machines. SVM) 是一种二分类分类模型。它的基本模型是定义在特征空间上的间隔最大的线性分类器，间隔最大使它有别于感知机。

“支持向量”即距离超平面最近的几个训练样本点。支持向量可以使约束条件等式成立。

支持向量机学习的基本思想：求解能够正确划分训练数据集井且几何间隔最大的分离超平面。

样本空间中划分超平面可以用线性方程描述：$w^{\mathrm{T}}x+b=0$，其中$w$为超平面法向量

分类决策函数为：$f(x)=\mathrm{sign}\left(w^{\ast }\cdot x+b^{\ast }\right)$

样本空间中任意点到$x$到超平面$(w,b)$的距离为：$\gamma =\frac{|{\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b|}{\Vert \mathbf{w}\Vert }$两个异类支持向量到超平面的距离，即“间隔”为$\gamma =\frac{2}{\Vert w\Vert }$

支持向量机目的找到最大间隔的划分超平面，所以支持向量机的基本问题即为：
$\begin{array}{rl}& \underset{w,b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2\\ & s.t.y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)⩾1,i=1,2,\dots ,m\end{array}$

通过使用拉格朗日乘子法可以得到该问题的对偶问题：

对偶问题往往更容易求解: 是自然引入核函数，进而推广到非线性分类问题

求解出$\alpha$后再求出$w,b$即可得到最终模型：$f(\mathbf{x})={\mathbf{w}}^{\mathrm{T}}\mathbf{x}+b={\sum }_{i=1}^m{\alpha }_i{y}_i{\mathbf{x}}_i^{\mathrm{T}}\mathbf{x}+b$
通常建立模型之前还要对特征值进行标准化处理。

线性支持向量机与软间隔

对于线性不可分的数据集，通常除去数据中的一些特异点，剩下的大部分样本点组成的集合是线性可分的。
“软间隔”即允许某些样本不满足约束，示意图如下：

为了使特异点满足约束条件，我们可以对每个样本点引入一个松弛变量${\xi }_i\ge 0$，用来表征某样本不满足约束的程度。

约束条件变为:$y_i(w^{\mathrm{T}}{x}_i+b)\ge 1-{\xi }_i$
目标函数变为：$\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_{i=1}^N{\xi }_i$ ，其中 ($C>0$)

可以得到线性不可分问题的线性支持向量机（软间隔支持向量机）模型：

$C$称为惩罚项，一般由实际问题确定，显然$C$很大时$\xi$必须小，则允许有较大错误；$C$很小时，则$\xi$可以比较大，即可容许较大的错误。

所用分类决策函数与解得超平面形式同线性可分支持向量机相同。

线性支持向量机的优化目标：

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m{\ell }_{0/1}\left(y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)-1\right)$$

${\ell }_{0/1}$是“0/1损失函数”，可用一些“替代函数”代替

三种常用的替代损失函数如下：
● 合页 ( hinge ) 损失函数：${\ell }_{\text{hinge }}(z)=\max (0,1-z)$
● 指数损失 ( exponential loss )函数：${\ell }_{\exp }(z)=\exp (-z)$
● 对率损失 ( logistic loss )函数：${\ell }_{\log }(z)=\log (1+\exp (-z))$

若采用合页损失函数，则优化目标为：

$$\underset{\mathbf{w},b}{\min }\frac{1}{2}\Vert \mathbf{w}{\Vert }^2+C\sum _{i=1}^m\max \left(0,1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)\right)$$

合页损失函数与正则化

合页损失函数性能最好，所用通常使用它作为损失函数

采用合页损失函数的优化目标可改写为如下形式：

$$\underset{\mathbf{w},b}{\min }\sum _{i=1}^m\max \left(0,1-y_i\left({\mathbf{w}}^{\mathrm{T}}{\mathbf{x}}_i+b\right)\right)+\lambda \Vert \mathbf{w}{\Vert }^2$$

也就是说，当样本点$(x_i,y_i)$被正确分类且函数间隔（确信度）$y_i(w^{\mathrm{T}}{x}_i+b)>1$时，损失为0，否则损失为$1-y_i(w^{\mathrm{T}}{x}_i)$

非线性支持向量机与核函数

非线性问题往往不好求解，所以希望将非线性问题转化为线性问题。

核技巧的基本思想：将样本从原始空间映射到高维的特征空间，使得这个样本在这个特征空间内线性可分。

令$\varphi (x)$表示将$x$映射后的特征向量，则高维空间中对应超平面为：$f(x)=w^{\mathrm{T}}\varphi (x)+b$
（目标函数和其对偶问题只需将$x$替换为$\varphi (x)$即可）

目标函数的对偶问题为：

$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\varphi (x_i{)}^{\mathrm{T}}\varphi (x_j)-\sum _{i=1}^m{\alpha }_i \\ s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0{\alpha }_i⩾0,i=1,2,\cdots ,m \end{gathered}$$

由于求解涉及到计算$\varphi (x_i{)}^{\mathrm{T}}\varphi (x_j)$，即样本$x_i$与$x_j$映射到特征空间之后的内积，由于特征空间的维度可能很高，所以直接计算往往很困难，而且我们通常不知道$\varphi (\cdot )$是什么形式，所以我们引入“核函数”(kernel function) $\mathbf{\kappa }(\cdot ,\cdot )$

$x_i$与$x_j$在特征空间中的内积等于它们在原始样本空间通过核函数$\kappa (x_i,x_j)$计算的结果.

所以我们不必去计算高位空间中的内积，则目标函数可以重写为：

$$\begin{gathered} \underset{\alpha }{\min }\frac{1}{2}\sum _{i=1}^m\sum _{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j\kappa (x_i,x_j)-\sum _{i=1}^m{\alpha }_i \\ s.t.\sum _{i=1}^m{\alpha }_i{y}_i=0{\alpha }_i⩾0,i=1,2,\cdots ,m \end{gathered}$$

求解后得到：$f(x)={\sum }_{i=1}^m{\alpha }_i{y}_i\kappa \left(\mathbf{x},{\mathbf{x}}_i\right)+b$，这一结果也称为“支持向量展式”

定理：只要一个对称函数所对应的核矩阵是半正定的，它就能作为核函数使用。即对于一个半正定核矩阵，总能找到一个与之对应的映射$\varphi$

常用“高斯核函数”（Gaussian kernel function）：$\kappa \left({\mathbf{x}}_i,{\mathbf{x}}_j\right)=\exp \left(-\frac{{\Vert {\mathbf{x}}_i-{\mathbf{x}}_j\Vert }^2}{2{\sigma }^2}\right)$
其中$\sigma$为高斯核的带宽 ( width )，不使用核函数又称为“线性核函数” (linear kernel)

● $C=1/\lambda$
● $C$ 较大时，相当于$\lambda$较小，可能会导致过拟合，高方差；
● $C$ 较小时，相当于$\lambda$较大，可能会导致低拟合，高偏差；
● $\sigma$较大时，可能会导致低方差，高偏差；
● $\sigma$较小时，可能会导致低偏差，高方差。

logistic 回归和SVM的比较

相同点：

1. LR和SVM都可以处理分类问题，且一般都用于处理线性二分类问题（在改进的情况下可以处理多分类问题
2. 两个方法都可以增加不同的正则化项，如L1、L2等等。所以在很多实验中，两种算法的结果是很接近的。

不同点：

1. 从目标函数来看，区别在于logistic 回归采用的是logistical loss，SVM主要采用的是hinge loss. 这两个损失函数的目的都是增加对分类影响较大的数据点的权重，减少与分类关系较小的数据点的权重。
2. SVM的处理方法是只考虑support vectors，也就是和分类最相关的少数点，去学习分类器。而logistic 回归中所有点都会起作用，只是通过非线性映射大大减小了离分类平面较远的点的权重，相对提升了与分类最相关的数据点的权重。
3. 逻辑回归一般应用梯度下降的方法求解，支持向量机应用SMO求解拉格朗日乘子，进而求解最优划分曲线方程。
4. 线性可分支持向量机本身就是结构风险最小化，而logistic 回归需要通过正则项权衡结构风险

下面是一些普遍使用的准则：
设$n$为特征数，$m$为训练样本数。

1. 如果相较于$m$而言，$n$要大许多，即训练集数据量不够支持我们训练一个复杂的非线性模型，我们选用逻辑回归模型或者不带核函数的支持向量机。

2. 如果$n$较小，而且$m$大小中等，例如$n$在 1-1000 之间，而$m$在10-10000之间，使用高斯核函数的支持向量机。

3. 如果$n$较小，而$m$较大，例如$n$在1-1000之间，而$m$大于50000，则使用支持向量机会非常慢，解决方案是选取并增加更多的特征，然后使用逻辑回归或不带核函数的支持向量机。

神经网络在以上三种情况下都可能会有较好的表现，但是训练神经网络可能非常慢，选择支持向量机的原因主要在于它的代价函数是凸函数，不存在局部最小值。

总结

本周回顾机器学习，SVM是一个传统的分类方法，但与神经网络的逻辑回归有不同之处。两者各有特点，互为补充。