代码编织梦想

目录

支持向量机

0. 由来

Cortes与Vapnik 提出线性支持向量机.

Boser Guyon Vapnik 又引入核技巧,提出非线性支持向量机。

Vapnik:俄罗斯统计学家。

1. 核心思想

可以将数据分开的超平面有很多,SVM为了达到更好的泛化效果,寻找一个能正确划分数据且使支持向量(距离分类超平面最近的样本点)间隔最大的超平面。对于线性不可分数据,有两种处理方式:

  • 松弛处理:即允许分类器对部分样本的分类出错。

  • 引入核函数:通过核函数将输入特征空间变换到维度更高的隐特征空间,在维度更高的隐特征空间数据变得线性可分。

请添加图片描述

2. 硬间隔支持向量机

数据线性可分,寻找正确分类数据且间隔最大的超平面。

分类超平面:

w ∗ ⋅ x + b ∗ = 0 w^*\cdot x+b^*=0 wx+b=0

决策函数:

f ( x ) = s i g n ( w ∗ ⋅ x + b ∗ ) f(x)=sign(w^*\cdot x + b^*) f(x)=sign(wx+b)

2.1 间隔最大化

2.1.1 函数间隔

∣ w ⋅ x + b ∣ |w\cdot x+b| wx+b能够相对的表示样本到超平面的距离, w ⋅ x + b w\cdot x+b wx+b的符号与 y y y的符号是否一致可以表示分类是否正确,故可以定义函数间隔来表示分类的正确性和置信度:

γ ^ i = y i ( w ⋅ x i + b ) γ ^ = min ⁡ i = 1... N γ ^ i \hat \gamma_i = y_i(w\cdot x_i+b) \\ \hat \gamma = \min_{i=1...N}\hat \gamma_i γ^i=yi(wxi+b)γ^=i=1...Nminγ^i

2.1.2 几何间隔

函数间隔存在一些问题:当 w w w b b b成比例的变化时,分类超平面没有改变但函数间隔确发生了变化,因此需要对 w w w b b b进行规范化,由此得出了几何间隔:

γ i = y i ( w ∥ w ∥ 2 ⋅ x i + b ∥ w ∥ 2 ) γ = min ⁡ i = 1... N γ i \gamma_i = y_i(\frac{w}{\Vert w \Vert_2}\cdot x_i+\frac{b}{\Vert w \Vert_2}) \\ \gamma = \min_{i=1...N}\gamma_i γi=yi(w2wxi+w2b)γ=i=1...Nminγi

函数间隔和几何间隔存在如下关系:

γ i = γ ^ i ∥ w ∥ 2 γ = γ ^ ∥ w ∥ 2 \gamma_i = \frac{\hat \gamma_i}{\Vert w \Vert_2}\\ \gamma = \frac{\hat \gamma}{\Vert w \Vert_2} γi=w2γ^iγ=w2γ^

2.1.2 间隔最大化

确保分类正确的同时定义间隔最大化有:

max ⁡ w , b γ ^ ∥ w ∥ 2 s . t . y i ( w ⋅ x i + b ) ≥ γ ^ γ ^ ≥ 0 \max_{w,b} \quad \frac{\hat \gamma}{\Vert w \Vert_2} \\ s.t. \quad y_i(w\cdot x_i+b)\ge \hat \gamma\\ \hat \gamma \ge 0 w,bmaxw2γ^s.t.yi(wxi+b)γ^γ^0

函数间隔 γ ^ \hat \gamma γ^的取值并不影响最优化问题的解 事实上,假设将 w , b w,b w,b按比例改变为 λ w , λ b \lambda w,\lambda b λw,λb这时函数间隔成为 λ γ ^ \lambda \hat \gamma λγ^,不妨令 γ ^ = 1 \hat \gamma=1 γ^=1则有:

min ⁡ w , b 1 ∥ w ∥ 2 s . t . y i ( w ⋅ x i + b ) ≥ 1 \min_{w,b} \quad \frac{1}{\Vert w \Vert_2} \\ s.t. \quad y_i(w\cdot x_i+b)\ge 1 w,bminw21s.t.yi(wxi+b)1

该问题的解具有存在性和唯一性,详细证明见李航《统计机器学习》

2.2 转换为拉格朗日对偶问题

2.2.1 拉格朗日对偶问题

对于含有不等式的约束问题:

min ⁡ f ( x ) s . t . c i ( x ) ≤ 0 h j ( j ) = 0 \begin{aligned} \min \quad f(x)&\\ s.t.\quad c_i(x)&\le 0 \\ h_j(j)&=0 \end{aligned} minf(x)s.t.ci(x)hj(j)0=0

希望找到一个无约束优化问题,使得无约束优化问题的解即为原问题的解,由此构造了拉格朗日函数:

L ( x , α , β ) = f ( x ) + ∑ i α i c i ( x ) + ∑ j β i h j ( x ) L(x,\alpha,\beta) = f(x)+\sum_i \alpha_i c_i(x)+\sum_j\beta_i h_j(x)\\ L(x,α,β)=f(x)+iαici(x)+jβihj(x)

通过对 α \alpha α加限制可以做到:

max ⁡ α ≥ 0 , β L ( x , α , β ) = f ( x ) s . t . c i ( x ) ≤ 0 h j ( j ) = 0 \begin{aligned} \quad \max_{\alpha\ge0,\beta}L(x,\alpha,\beta)&=f(x)\\ s.t.\quad c_i(x)&\le 0 \\ h_j(j)&=0 \end{aligned} α0,βmaxL(x,α,β)s.t.ci(x)hj(j)=f(x)0=0

原始问题和对偶问题具有如下关系:

max ⁡ α , β : α ≥ 0 min ⁡ x L ( x , α , β ) ≤ min ⁡ α , β : α ≥ 0 max ⁡ x L ( x , α , β ) \max_{\alpha,\beta:\alpha\ge0} \min_x L(x,\alpha,\beta) \le \min_{\alpha,\beta:\alpha\ge0}\max_x L(x,\alpha,\beta) α,β:α0maxxminL(x,α,β)α,β:α0minxmaxL(x,α,β)

则原问题变为:

max ⁡ α ≥ 0 , β min ⁡ x L ( x , α , β ) s . t . c i ( x ) ≤ 0 h j ( j ) = 0 \begin{aligned} \quad \max_{\alpha\ge0,\beta}\min_x\quad L(x,\alpha,\beta)\\ s.t.\quad c_i(x)\le 0\\ h_j(j)=0 \end{aligned} α0,βmaxxminL(x,α,β)s.t.ci(x)0hj(j)=0

某些情况下原始问题和对偶问题的最优值相等(详细证明需要对偶相关理论),不妨设满足这个最优值的解为 ( x ∗ , α ∗ , β ∗ ) (x^*,\alpha^*,\beta^*) (x,α,β),则有成立的充要条件,即KKT条件:

∇ x L ( x ∗ , α ∗ , β ∗ ) = 0 α i ≥ 0 i = 1 , 2 , . . . , k α i ∗ c i ( x ) = 0 i = 1 , 2 , . . . , k c i ( x ) ≤ 0 i = 1 , 2 , . . . , k h j ( x ) = 0 j = 1 , 2 , . . . , l \nabla_xL(x^*,\alpha^*,\beta^*)=0\\ \alpha_i \ge 0\quad i=1,2,...,k\\ \alpha^*_i c_i(x)=0 \quad i=1,2,...,k\\ c_i(x)\le0\quad i=1,2,...,k\\ h_j(x)=0 \quad j=1,2,...,l xL(x,α,β)=0αi0i=1,2,...,kαici(x)=0i=1,2,...,kci(x)0i=1,2,...,khj(x)=0j=1,2,...,l

其中 α i ∗ c i ( x ) = 0 \alpha^*_i c_i(x)=0 αici(x)=0为对偶互补条件

2.2.2 将问题转换为拉格朗日对偶问题

定义拉格朗日函数有:

L ( w , b , α ) = 1 2 ∥ w ∥ 2 2 − ∑ i N α i y i ( w ⋅ x i + b ) + ∑ i N α i L(w,b,\alpha)=\frac{1}{2}\Vert w \Vert_2^2-\sum_i^N\alpha_i y_i(w\cdot x_i+b)+\sum_i^N\alpha_i L(w,b,α)=21w22iNαiyi(wxi+b)+iNαi

max ⁡ α : α ≥ 0 min ⁡ w , b L ( w , b , α ) \max_{\alpha:\alpha\ge0} \min_{w,b} L(w,b,\alpha) α:α0maxw,bminL(w,b,α)

求解 min ⁡ w , b L ( w , b , , α ) \min_{w,b}L(w,b,,\alpha) minw,bL(w,b,,α)有:

∇ w L ( w , b , α ) = w − ∑ i N α i y i x i = 0 ∇ b L ( w , b , α ) = − ∑ i N α i y i = 0 得 : w = ∑ i N α i y i x i ∑ i N α i y i = 0 \nabla_w L(w,b,\alpha)=w-\sum_i^N\alpha_iy_ix_i=0\\ \nabla_b L(w,b,\alpha)= -\sum_i^N\alpha_iy_i=0\\ 得:\\ w=\sum_i^N\alpha_iy_ix_i\\ \sum_i^N\alpha_iy_i=0 wL(w,b,α)=wiNαiyixi=0bL(w,b,α)=iNαiyi=0w=iNαiyixiiNαiyi=0

带原拉格朗日函数整理得:

L ( w , b , α ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i L(w,b,\alpha)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_j y_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\\ L(w,b,α)=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαi

对偶问题有:

max ⁡ α L ( w , b , α ) = min ⁡ α − L ( w , b , α ) \max_{\alpha} L(w,b,\alpha)=\min_{\alpha}-L(w,b,\alpha) αmaxL(w,b,α)=αminL(w,b,α)

则最后需要求解得问题变为

min ⁡ α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . ∑ i = 1 N α i y i = 0 α i ≥ 0 , i = 1 , 2 , . . . , N \min_{\alpha} \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_j y_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\ s.t. \sum_{i=1}^{N}\alpha_i y_i=0 \\ \alpha_i \ge 0,\quad i=1,2,...,N αmin21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαis.t.i=1Nαiyi=0αi0,i=1,2,...,N

求解出最优的 α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T \alpha^*=(\alpha_1^*,\alpha_2^*,...,\alpha_N^*)^T α=(α1,α2,...,αN)T,后有解:

w ∗ = ∑ i = 1 N α i ∗ y i x i b ∗ = y j − ∑ i = 1 N α i ∗ y i ( x i ⋅ x j ) w^* = \sum_{i=1}^N\alpha_i^*y_ix_i\\ b^*=y_j-\sum_{i=1}^N\alpha_i^*y_i(x_i\cdot x_j) w=i=1Nαiyixib=yji=1Nαiyi(xixj)

决策函数有:

f ( x ) = s i g n ( ∑ i = 1 N α i ∗ y i ( x ⋅ x i ) + b ∗ ) f(x)=sign(\sum_{i=1}^N\alpha_i^*y_i(x\cdot x_i)+b^*) f(x)=sign(i=1Nαiyi(xxi)+b)

3. 软间隔支持向量机

对于线性不可分数据,某些样本不满足函数距离不小于1得条件,因此可以通过对每个样本引入一个松弛变量 ξ i ≥ 0 \xi_i \ge0 ξi0来松弛约束,并引入一个惩罚系数 C C C最小化所有松弛变量,则有如下软间隔得支持向量机问题:

m i n 1 2 ∥ w ∣ 2 2 + C ∑ i ξ i s . t . y i ( w ⋅ x i + b ) ≥ 1 − ξ i , i = 1 , 2 , . . . , N ξ i ≥ 0 , i = 1 , 2 , . . . , N min \quad \frac{1}{2}\Vert w \vert_2^2+C\sum_i \xi_i\\ s.t. \quad y_i(w\cdot x_i+b)\ge 1-\xi_i,\quad i=1,2,...,N\\ \xi_i\ge 0, \quad i=1,2,...,N min21w22+Ciξis.t.yi(wxi+b)1ξi,i=1,2,...,Nξi0,i=1,2,...,N

则此时拉格朗日函数有:

L ( w , b , ξ , α , μ ) = 1 2 ∥ w ∣ 2 2 + C ∑ i ξ i − ∑ i α i ( y i ( w ⋅ x i + b ) − 1 + ξ i ) − ∑ i μ i ξ i L(w,b,\xi,\alpha,\mu)=\frac{1}{2}\Vert w \vert_2^2+C\sum_i \xi_i-\sum_i\alpha_i(y_i(w\cdot x_i+b)-1+\xi_i)-\sum_i\mu_i\xi_i L(w,b,ξ,α,μ)=21w22+Ciξiiαi(yi(wxi+b)1+ξi)iμiξi

求解偏导数有:

∇ w L ( w , b , ξ , α , μ ) = w − ∑ i α i y i x i = 0 ∇ b L ( w , b , ξ , α , μ ) = − ∑ i α i y i = 0 ∇ ξ i L ( w , b , ξ , α , μ ) = C − α i − μ i = 0 \nabla_wL(w,b,\xi,\alpha,\mu)=w-\sum_i \alpha_i y_i x_i = 0\\ \nabla_bL(w,b,\xi,\alpha,\mu)= -\sum_i\alpha_iy_i=0\\ \nabla_{\xi_i} L(w,b,\xi,\alpha,\mu)= C-\alpha_i-\mu_i=0 wL(w,b,ξ,α,μ)=wiαiyixi=0bL(w,b,ξ,α,μ)=iαiyi=0ξiL(w,b,ξ,α,μ)=Cαiμi=0

解得:

w = ∑ i α i y i x i ∑ i α i y i = 0 C − α i − ξ i = 0 w=\sum_i \alpha_i y_i x_i\\ \sum_i\alpha_iy_i=0\\ C-\alpha_i-\xi_i=0 w=iαiyixiiαiyi=0Cαiξi=0

代入原问题得:

min ⁡ w , b , ξ L ( w , b , α , ξ , μ ) = − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i \min_{w,b,\xi}L(w,b,\alpha,\xi,\mu)=-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_j y_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\\ w,b,ξminL(w,b,α,ξ,μ)=21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαi

需要求解得对偶问题有:

max ⁡ α , μ : α ≥ 0 , μ ≥ 0 min ⁡ w , b , ξ L ( w , b , α , ξ , μ ) = max ⁡ α , μ : α ≥ 0 , μ ≥ 0 − 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) + ∑ i = 1 N α i s . t . ∑ i α i y i = 0 C − α i − μ i = 0 α i ≥ 0 μ i ≥ 0 \max_{\alpha,\mu:\alpha\ge0,\mu\ge0} \min_{w,b,\xi} L(w,b,\alpha,\xi,\mu)\\ = \max_{\alpha,\mu:\alpha\ge0,\mu\ge0}-\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_j y_iy_j(x_i\cdot x_j)+\sum_{i=1}^N\alpha_i\\ s.t.\quad \sum_i\alpha_iy_i=0\\ \quad C-\alpha_i-\mu_i=0\\ \quad \alpha_i\ge0\\ \quad \mu_i \ge 0 α,μ:α0,μ0maxw,b,ξminL(w,b,α,ξ,μ)=α,μ:α0,μ0max21i=1Nj=1Nαiαjyiyj(xixj)+i=1Nαis.t.iαiyi=0Cαiμi=0αi0μi0

合并约束条件,转为求最小目标,则有对偶问题:

min ⁡ α : α ≥ 0 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i ⋅ x j ) − ∑ i = 1 N α i s . t . ∑ i α i y i = 0 0 ≤ α i ≤ C \min_{\alpha:\alpha\ge0}\frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_j y_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i\\ s.t.\quad \sum_i\alpha_iy_i=0\\ \quad 0\le\alpha_i\le C α:α0min21i=1Nj=1Nαiαjyiyj(xixj)i=1Nαis.t.iαiyi=00αiC

4. 泛函基础

泛函分析形成于20世纪30年代,从变分问题、积分方程和理论物理得研究中发展而来,主要研究:

  • 无限维向量空间上的函数、算子和极限理论;

  • 拓扑线性空间到拓扑线性空间之间,满足各种拓扑和代数条件的映射。

算子:把无限维空间到无限维空间的变换。

4.1 度量(距离)空间

4.1.1 定义

设X是非空集合,对于 X X X中的任意两元素 x x x y y y,按某一法则都对应唯一的实数 ρ ( x , y ) \rho(x,y) ρ(x,y),并满足以下三条公理(距离公理):

  1. 非负性: ρ ( x , y ) ≥ 0 \rho(x,y)\ge 0 ρ(x,y)0 ρ ( x , y ) = 0 \rho(x,y)=0 ρ(x,y)=0当且仅当 x = y x=y x=y

  2. 对称性: ρ ( x , y ) = ρ ( y , x ) \rho(x,y) = \rho(y,x) ρ(x,y)=ρ(y,x)

  3. 三角不等式: 对任意的 x , y , z x,y,z x,y,z有: ρ ( x , y ) ≤ ρ ( x , z ) + ρ ( z , y ) \rho(x,y)\le \rho(x,z) + \rho(z,y) ρ(x,y)ρ(x,z)+ρ(z,y)

则称:

ρ ( x , y ) \rho(x,y) ρ(x,y) x x x y y y间的距离(或度量);

X X X是以 ρ \rho ρ为距离的距离空间(或度量空间),记成 ( X , ρ ) (X,\rho) (X,ρ),或简记为 X X X X X X中的元素称为 X X X中的点。

  • 点(元素)包含:真正意义下得点、数列和函数。

  • 泛函分析是研究一个空间中点与点之间的关系,以及空间中符合一定条件的点组成的该空间子集的一些性质。

4.1.2 ρ \rho ρ次幂可积函数空间

L p [ a , b ] L^p[a,b] Lp[a,b]表示区间 [ a , b ] [a,b] [a,b]绝对值的 ρ \rho ρ次幂 L L L可积函数的全体,并把几乎处处相等的函数看成是同一个函数,对于 x , y ∈ L p [ a , b ] x,y\in L^p[a,b] x,yLp[a,b],规定:

ρ ( x , y ) = [ ∫ a b ∣ x ( t ) − y ( t ) ∣ d t ] 1 p , p ≥ 1 \rho(x,y)=\bigg[\int_a^b\big|x(t)-y(t)\big|dt\bigg]^\frac{1}{p},p\ge1 ρ(x,y)=[abx(t)y(t)dt]p1,p1

L p [ a , b ] L^p[a,b] Lp[a,b]构成一个距离空间,称之为 ρ \rho ρ次幂可积函数空间。

4.1.3 完备性概念

( X , ρ ) (X,\rho) (X,ρ)为度量空间:

  • { x n } n = 1 ∞ \{x_n\}_{n=1}^\infty {xn}n=1 X X X中的点列,如果对于任一正数 ϵ \epsilon ϵ,存在正数 N N N,使得当自然数 n , m ≥ N n,m\ge N n,mN时:

    ρ ( x n , x m ) < ϵ \rho(x_n,x_m)<\epsilon ρ(xn,xm)<ϵ

    就称 { x n } n = 1 ∞ \{x_n\}_{n=1}^\infty {xn}n=1 X X X中的基本点列,或者称为 C a u c h y Cauchy Cauchy点列。

  • 如果度量空间$ X
    中 每 个 基 本 点 列 都 收 敛 , 称 中每个基本点列都收敛,称 X$是完备度量空间。

4.2 线性空间

空间中的任意两点可以做加法或与数相乘,运算的结果仍未该空间的点,并且该空间中的每个点可以定义长度,这个长度称为该点的范数,范数可以视为欧式空间中向量长度概念的推广。

4.3 赋范空间

X X X是实(或复)线性空间,如果对于 X X X中每个元素 x x x,按照一定的法则对应于实数 ∥ x ∥ \Vert x\Vert x,且满足:

  • ∥ x ∥ ≥ 0 \Vert x\Vert \ge 0 x0 ∥ x ∥ = 0 \Vert x\Vert =0 x=0当且仅当 X X X等于零元

  • ∥ a x ∥ = ∣ a ∣ ∥ x ∥ \Vert ax\Vert = |a|\Vert x\Vert ax=ax a a a是实(或复)数

  • ∥ x + y ∥ ≤ ∥ x ∥ + ∥ y ∥ \Vert x+y\Vert\le\Vert x\Vert+\Vert y\Vert x+yx+y

则称 ∥ X ∥ \Vert X\Vert X是实(或复)赋范线性空间, ∥ x ∥ \Vert x\Vert x称为 x x x的范数

  • 赋范线性空间必然是距离空间:定义
    ρ ( x , y ) = ∥ x − y ∥ \rho(x,y)=\Vert x-y\Vert ρ(x,y)=xy

  • 与度量空间不同:

    • 平移不变性: d ( x + a , y + a ) = d ( x , y ) d(x+a,y+a)=d(x,y) d(x+a,y+a)=d(x,y), x , y , a x,y,a x,y,a属于 X X X

    • 齐次性: d ( a x , a y ) = ∣ a ∣ d ( x , y ) d(ax,ay)=|a|d(x,y) d(ax,ay)=ad(x,y), x , y x,y x,y属于 X X X a a a属于 K K K

4.4 巴拿赫(Banach)空间

如果赋范线性空间 ( X , ∣ ∣ . ∣ ∣ ) (X, ||.||) (X,.)是完备的,则称(X, ||.||)是Banach空间。

例子:

  • n n n维Euclid空间 R n R^n Rn是Banach空间

  • L p [ a , b ] ( p ≥ 1 ) L^p[a,b](p\ge1) Lp[a,b](p1)是Banach空间

算子 T T T是由赋范线性空间 X X X中的某个子集 D D D到赋范线性空间中的一个映射,则称 T T T是算子, D D D T T T的定义域,记为 D ( T ) D(T) D(T),像集 { y ∣ y = T x , x ∈ D } \{y|y=Tx,x\in D\} {yy=Tx,xD} T T T的值域,记为 T ( D ) T(D) T(D)

线性算子: T T T满足可加性和齐次性

  • 可加性: T ( x + y ) = T x + T y T(x+y)=Tx+Ty T(x+y)=Tx+Ty

  • 齐次性: T ( a x ) = a T ( x ) T(ax)=aT(x) T(ax)=aT(x)

**有界算子:**存在正数 M M M使得对于一切 x ∈ D ( T ) x\in D(T) xD(T),有 ∥ T x ∥ ≤ M ∥ x ∥ \Vert Tx\Vert \le M\Vert x\Vert TxMx

4.5 内积空间

设X 是定义在实(或复)数域 K K K上的线性空间,若对于 X X X任意一对有序元素 x , y x,y x,y, 恒对应数域 K K K的值 ( x , y ) (x,y) (x,y),且满足:

  • ( a x , y ) = a ( x , y ) (ax,y)=a(x,y) (ax,y)=a(x,y)

  • ( x + y , z ) = ( x , z ) + ( y , z ) (x+y,z)=(x,z)+(y,z) (x+y,z)=(x,z)+(y,z)

  • ( x , y ) = ( y , z ) (x,y)=(y,z) (x,y)=(y,z)

  • ( x , x ) ≥ 0 (x,x)\ge0 (x,x)0 ,且 ( x , x ) = 0 (x,x)=0 (x,x)=0的充要条件是 x = 0 x=0 x=0

则称 X X X为内积空间, ( x , y ) (x,y) (x,y)称为 x , y x,y x,y的内积。

4.6 希尔伯特(Hibert)空间

可由内积导出范数: ∥ x ∥ = ( x , x ) \Vert x\Vert = \sqrt{(x,x)} x=(x,x)

完备的内积空间称为希尔伯特空间。

5. 核支持向量机

通过一个非线性变换将输入空间(欧氏空间 R R R或离散集合)对应于一个特征空间(希尔伯特空间),使得在输入空间中的超曲面模型对应于特征空间中的超平面模型(支持向量机)。

K ( x , z ) = ϕ ( x ) ⋅ ϕ ( z ) K(x,z)=\phi(x)\cdot\phi(z) K(x,z)=ϕ(x)ϕ(z)

其中 K ( x , z ) K(x,z) K(x,z)为核函数, ϕ ( x ) \phi(x) ϕ(x)为映射函数。

  • 在学习与预测中只定义核函数 K ( x , z ) K(x,z) K(x,z),而不显式地定义映射函数。

则核支持向量机的目标函数有:

W ( α ) = 1 2 ∑ i ∑ j α i α j y i y j K ( x i , x j ) − ∑ i α i W(\alpha)=\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_i\alpha_i\\ W(α)=21ijαiαjyiyjK(xi,xj)iαi

核支持向量机要求解的问题:

min ⁡ α 1 2 ∑ i ∑ j α i α j y i y j K ( x i , x j ) − ∑ i α i s . t . ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N \min_\alpha\quad\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_i\alpha_i\\ s.t. \quad \sum_{i=1}^N\alpha_iy_i=0\\ \quad 0\le\alpha_i \le C,\quad i=1,2,...,N αmin21ijαiαjyiyjK(xi,xj)iαis.t.i=1Nαiyi=00αiC,i=1,2,...,N

决策函数:

f ( x ) = s i g n ( ∑ i α i ∗ y i K ( x i , x ) + b ∗ ) f(x)=sign\bigg(\sum_i\alpha_i^*y_iK(x_i,x)+b^*\bigg) f(x)=sign(iαiyiK(xi,x)+b)

5.1 正定核

5.2 常用核函数

5.2.1 多项式核函数

K ( x , z ) = ( x ⋅ z + 1 ) p K(x,z)=(x\cdot z+1)^p K(x,z)=(xz+1)p

对应的支持向量机为P次多项式分类器

5.2.2 高斯核函数

K ( x , z ) = e x p ( − ∥ x − z ∥ 2 2 σ ) K(x,z)=exp(-\frac{\Vert x-z\Vert^2}{2\sigma}) K(x,z)=exp(2σxz2)

高斯核函数对应的映射函数可以将数据映射到无限维

5.2.3 字符串核函数

6. SMO算法

序列最小优化算法

求解如下问题:

min ⁡ α 1 2 ∑ i ∑ j α i α j y i y j K ( x i , x j ) − ∑ i α i s . t . ∑ i = 1 N α i y i = 0 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N \min_\alpha\quad\frac{1}{2}\sum_i\sum_j\alpha_i\alpha_jy_iy_jK(x_i,x_j)-\sum_i\alpha_i\\ s.t. \quad \sum_{i=1}^N\alpha_iy_i=0\\ \quad 0\le\alpha_i \le C,\quad i=1,2,...,N αmin21ijαiαjyiyjK(xi,xj)iαis.t.i=1Nαiyi=00αiC,i=1,2,...,N

是一种启发式算法,加快求解多变量约束问题

  • 如果所有变量的解都满足此最优化问题的KKT条件,那么得到解;

  • 否则,选择两个变量,固定其它变量,针对这两个变量构建一个二次规划问题,称为子问题,可通过解析方法求解,提高了计算速度。子问题的两个变量:一个是违反KKT条件最严重的那个,另一个由约束条件自动确定。

步骤:

  1. 求解两个变量的子问题二次规划问题

  2. 启发式寻找子问题的两个变量

  3. 继续执行1

参考资料

《统计机器学习》李航

https://baike.baidu.com/item/弗拉基米尔·万普尼克?fr=aladdin

https://blog.pluskid.org/archives/702

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/The_Only_God/article/details/128007827