统计学习方法 7-支持向量机

支持向量机学习方法包含构建由简至繁的模型：线性可分支持向量机（linear support vector machine in linearly separable case）、线性支持向量机（linear support vector machine）及非线性支持向量机（non-linear support vector machine）。

• 当训练数据线性可分时，通过硬间隔最大化（hard margin maximization），学习一个线性的分类器，即线性可分支持向量机，又称为硬间隔支持向量机；
• 当训练数据近似线性可分时，通过软间隔最大化（soft margin maximization），也学习一个线性的分类器，即线性支持向量机，又称为软间隔支持向量机；
• 当训练数据线性不可分时，通过使用核技巧（kernel trick）及软间隔最大化，学习非线性支持向量机。

当输入空间为欧氏空间或离散集合、特征空间为希尔伯特空间时，核函数（kernel function）表示将输入从输入空间映射到特征空间得到的特征向量之间的内积。通过使用核函数可以学习非线性支持向量机，等价于隐式地在高维的特征空间中学习线性支持向量机。这样的方法称为核技巧。

线性可分支持向量机与硬间隔最大化

线性可分支持向量机

输入空间为欧氏空间或离散集合，特征空间为欧氏空间或希尔伯特空间。线性可分支持向量机、线性支持向量机假设这两个空间的元素一一对应，并将输入空间中的输入映射为特征空间中的特征向量。学习的目标是在特征空间中找到一个分离超平面，能将实例分到不同的类。

函数间隔和几何间隔

（函数间隔）对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi，yi)的函数间隔为 γ^=yi(w⋅xi+b)
定义超平面(w,b)关于训练数据集T的函数间隔为超平面(w,b)关于T中所有样本点(xi，yi)的函数间隔之最小值，即γ^=mini=1,⋯,Nγ^i

（几何间隔）对于给定的训练数据集T和超平面(w,b)，定义超平面(w,b)关于样本点(xi，yi)的几何间隔为γi=yi(w||w||⋅xi+b||w||)
定义超平面(w,b)关于训练数据集T的几何间隔为超平面(w,b)关于T中所有样本点(xi，yi)的几何间隔之最小值，即γ=mini=1,⋯,Nγi

γi=γ^i||w||
γ=γ^||w||

间隔最大化

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

1. 最大间隔分离超平面

   

2. 最大间隔分离超平面的存在唯一性
3. 支持向量和间隔边界
   在H1和H2上的点就是支持向量,H1与H2之间的距离称为间隔 2||w||

学习的对偶算法

线性支持向量机与软间隔最大化

线性支持向量机

约束条件：yi(w⋅xi+b)≥εi
目标函数：12||w||2+C∑Ni=1εi

学习的对偶算法

支持向量

软间隔的支持向量xi或者在间隔边界上，或者在间隔边界与分离超平面之间，或者在分离超平面误分一侧。

• 若α∗i<C，则εi＝0，支持向量xi恰好落在间隔边界上；
• 若α∗i=C，0<εi<1，则分类正确，xi在间隔边界与分离超平面之间；
• 若α∗i=C，εi=1，则xi在分离超平面上；
• 若α∗i=C，εi>1，则xi位于分离超平面误分一侧。

合页损失函数

• 对于线性支持向量机学习来说，其模型为分离超平面w*·x+b*＝0及决策函数f(x)＝sign(w*·x+b*)，其学习策略为软间隔最大化，学习算法为凸二次规划。
• 最小化以下目标函数：∑Ni=1[1−yi(w⋅xi+b)]++λ||w||2
  
  [z]+={z,0,z>0z≤0
  
  

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

核技巧

1. 非线性分类问题
   对于在输入空间中线性不可分的问题做非线性变换，将非线性问题变换为线性问题，通过解变换后的线性问题的方法求解原来的非线性问题。
   用线性分类方法求解非线性分类问题分为两步：首先使用一个变换将原空间的数据映射到新空间；然后在新空间里用线性分类学习方法从训练数据中学习分类模型。核技巧就属于这样的方法。
2. 核函数的定义
   设X是输入空间（欧氏空间Rn的子集或离散集合），又设为特征空间（希尔伯特空间），如果存在一个从X到H的映射：
   ϕ(x)=x→H
   使得对所有的x,z∈X，函数K(x,z)满足条件
   K(x,z)=ϕ(x)⋅ϕ(z)
   ,则称K(x,z)为核函数，ϕ(x)为映射函数。
   核技巧的想法是，在学习与预测中只定义核函数K(x,z)，而不显式地定义映射函数ϕ。
3. 核技巧在支持向量机中的应用
   对偶问题的目标函数：
   W(α)=12∑i=1N∑j=1NαiαjyiyjK(xi,xj)−∑i=1Nαi
   
   分类决策函数:
   f(x)=sign(∑i=1Nsa∗iyiϕ(xi)⋅ϕ(x)+b∗)=sign(∑i=1Nsa∗iyiK(xi,x)+b∗)

常用核函数

1. 多项式核函数
   
   K(x,z)=(x⋅z+1)p
   
   对应的支持向量机是一个p次多项式分类器,对应分类决策函数：
   f(x)=sign(∑i=1Nsa∗iyi(xi⋅x+1)p+b∗)
2. 高斯核函数
   
   K(x,z)=exp(−||x−z||22σ2)
   
   对应的支持向量机是高斯径向基函数（radial basis function）分类器,对应分类决策函数：
   f(x)=sign(∑i=1Nsa∗iyiexp(−||x−z||22σ2)+b∗)

---

欧几里得空间：
如果通过一序列的平移和旋转可以把一个图形变换成另一个图形，平面的两个图形（也就是子集）应被认为是等价的（全等）。
https://zh.wikipedia.org/wiki/%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%A9%BA%E9%97%B4

希尔伯特空间：
希尔伯特空间是欧几里德空间的一个推广，其不再局限于有限维的情形。
https://zh.wikipedia.org/wiki/%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E7%A9%BA%E9%97%B4