落园 » ≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十九):SVM|专注经济视角下的互联网

≪统计学习精要(The Elements of Statistical Learning)≫课堂笔记(十九):SVM

支持向量机——最大边距方法

前言:这节课我人在北京,只能回来之后抄一下笔记,然后对着书和wiki理解一下....有什么错误还请大家及时指出。

------------------------------

1. 背景

  • 问题:两类分类问题
  • 数据:有标识、有监督\mathcal{D}=\left\{ (\mathbf{x}_{i},y_{i})\mid\mathbf{x}_{i}\in\mathbb{R}^{p},\, y_{i}\in\{-1,1\}\right\} _{i=1}^{n}
  • 模型:f(x)=sign(wx+b),线性模型
  • 准则:最大边距

先说一下个人理解的SVM的直觉。下图来自wiki。二次元中的SVM就是想找到一条直线(或者对应高维空间下的超平面)来尽可能的分割开两组数据。比如图中H3和H2这两条直线虽然都可以分开这两组数据,但是显然H3离两组数据都远一些——这就是SVM遵循的最大边距准则。

svm1

而在实践中,我们把二类分类分别作为正负1,所以两条距离该分割线平行距离1的直线就应景而生。在这两条直线上的点我们称之为支持向量(SV)。

2. 线性可分时的SVM

1) 线性可分:存在w,b使得\begin{array}{cc}y_{i}=1, & wx+b>0\\y_{i}=-1, & wx+b<0\end{array}\Rightarrow wx+b=0为分割超平面。

2) 一个点到超平面wx+b=0的距离:

d(x|w,b)=\begin{cases}\frac{wx+b}{\left\Vert w\right\Vert } & ,y=+1\\-\frac{wx+b}{\left\Vert w\right\Vert } & ,y=-1\end{cases} \Rightarrow=\frac{y(wx+b)}{\left\Vert w\right\Vert }

3) 分割超平面的正则表示

数据集到某个超平面的距离d(D|w,b)=\min d(i|w,b)=\min_{i}\frac{y_{i}(wx_{i}+b)}{\left\Vert w\right\Vert }。将y(wx+b)\geq1标准化,则\frac{y_{i}(wx_{i}+b)}{\left\Vert w\right\Vert }\geq\frac{1}{\left\Vert w\right\Vert }

4) 最大边距准则 \max_{w,b}d(D|w,b)

5) 线性可分时的SVM

\max\frac{1}{\left\Vert w\right\Vert }

s.t.\, y(wx_{i}+b)\geq1

等同于

\min\frac{1}{2}\left\Vert w\right\Vert ^{2}

s.t.\, y(wx_{i}+b)\geq1

这样就有了一个sign分类器。

6) support vector:分离超平面落在隔离带的边缘,满足y_{i}(wx_{i}+b)=1x_{i}被称为SV。

7) 优点:

  • 对测试误差错识小
  • 稀疏性
  • 自然直观
  • 有效
  • 有理论深度(这话的意思是,又可以造出来一堆论文了么?)

3.一般的(线性)SVM

不满足约束的时候,可以做一些放松——引入\xi_{i}\geq0作为松弛变量。

这样原来的最优化问题就变成

\min\frac{1}{2}\left\Vert w\right\Vert ^2+C\sum_{i}\xi_{i}

s.t.\, y_{i}(w_{i}+b)\geq1-\xi_{i}

最优的分类器则为f*(x)=w*x+b*

svm_graph

这里大概示意了\xi的应用场景。左边是上述完全可分的情况,右边是没法分开,所以我们容忍一些误差,只要误差之和在一个可以接受的范围之内。

4.非线性的SVM

这里的直觉大概是,在低维空间较为稠密的点,可以在高维空间下变得稀疏。从而可能可以找到一个高维空间的线性平面,把他们分开。

原来的数据集是:\mathcal{D}=\left\{ (\mathbf{x}_{i},y_{i})\mid\mathbf{x}_{i}\in\mathbb{R}^{p},\, y_{i}\in\{-1,1\}\right\} _{i=1}^{n}

然后定义一个从低维到高维的映射:\Phi,使得x\underrightarrow{\Phi}z。其中x原本属于\mathbb{R}^{p},此时被映射到一个高维的\mathbb{R}^{q},可为无限维Hilbert空间(这里我只是照抄笔记...)。

映射之后的\mathcal{D}'=\left\{ (\mathbf{z}_{i},y_{i})\mid\mathbf{z}_{i}\in\mathbb{R}^{q},\, y_{i}\in\{-1,1\}\right\} _{i=1}^{n},之后就是传统的寻找一个线性平面。

\Phi的例子:

\Phi(x)=(\Phi_{1}(x),\Phi_{2}(x),\Phi_{3}(x))=(x_{1}^{2},2x_{1}x_{2},x_{2}^{2}),这样就打散到一个高维的空间(圆)。

下节课是线性SVM的计算。


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *