我是靠谱客的博主 心灵美钢笔,最近开发中收集的这篇文章主要介绍机器学习--分类算法--SVM算法理论一 算法概述二 算法理论三 SMO算法,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

目录

一 算法概述

1 点到超平面的几何距离公式

2 算法核心思想

3 算法中几个重要概念

1)线性可分

2)线性不可分

3)间隔

4)划分超平面

5)支持向量

二 算法理论

1 线性可分SVM

1)硬间隔SVM算法流程

2)软间隔SVM算法流程

2 线性不可分SVM

1)线性不可分SVM的核心思想

2)核函数

3)线性不可分SVM算法流程(SVM软间隔模型)

3 SVR(不推荐使用)

三 SMO算法


一 算法概述

1 点到超平面的几何距离公式

(x_{0},y_{0})underset{distance}{rightarrow }y=w^tx+brightarrow distance=frac{|w^tx_{0}+b|}{||w||_{2}}

注意:分母为点到超平面的函数距离

2 算法核心思想

  • 第一点:在数据中找到一个超平面,让尽可能多的数据分布在超平面两侧
  • 第二点:距离超平面比较近的点近可能的远离这个超平面

注意:第一点感知器模型也可以做到,但是第二点才是SVM算法的最核心思想

3 算法中几个重要概念

1)线性可分

可以在数据中找到一个超平面将尽可能多的数据二元分开(目标属性标记+1或者-1)

2)线性不可分

无法在数据中找到一个超平面将尽可能多的数据二元分开

注意:但是可以通过低维映射高维空间,使之成为线性可分

3)间隔

样本距离超平面的距离

4)划分超平面

将数据划分开的超平面

5)支持向量

一般认为是距离超平面最近的样本(默认函数距离为1)

二 算法理论

1 线性可分SVM

1)硬间隔SVM算法流程

注意:硬间隔要求样本到分割超平面的函数距离大于等于1,对于异常数据很敏感

第一步:假定条件(超平面、支持向量、支持向量距离)

  • 第一点:超平面

y=w^{t}x+b

  • 第二点:支持向量

left { x|w^{t}x+b=pm 1 right }

  • 第三点:支持向量的间隔

frac{|w^{t}x+b|}{||w||_{2}}=frac{1}{||w||_{2}}

第二步:目标函数

left{begin{matrix} max(frac{1}{||w||_{2}})\s.t.y^{(i)}(w^{t}x^{(i)}+b)geq 1,i=1,2,...,m end{matrix}right.rightarrowleft{begin{matrix} min(frac{1}{2}||w||tfrac{2}{2})\s.t.1-y^{(i)}(w^{t}x^{(i)}+b)leq 0,i=1,2,...,m end{matrix}right.

第三步:对于有条件约束的目标函数采用泛拉格朗日乘子法进行凸优化

  • 第一点:构建泛拉格朗日函数(泛拉格朗日乘子betageq 0),并将原始问题转化为对偶问题

l(w,b,beta )=underset{w,b,beta }{arg min}left { frac{1}{2}||w||^{2}_{2}+sum_{i=1}^{m}beta_{i}(1-y^{(i)}(w^{t}x^{(i)}+b)) right }

underset{w,b,beta}{arg min}(l(w,b,beta ))leftrightarrow underset{w,b}{min}left { underset{beta}{ max}l(w,b,beta) right }leftrightarrow underset{beta}{max}left {underset{w,b}{ min}l(w,b,beta) right }

  • 第二点:l(beta )

l(beta )=underset{w,b}{min}left { l(w,b,beta) right }

frac{partial l(w,b,beta)}{partial w}=w-sum _{i=1}^{m}beta_{i}y^{(i)}x^{(i)}=0rightarrow w^{*}=sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}

frac{partial l(w,b,beta)}{partial b}=-sum _{i=1}^{m}beta_{i}y^{(i)}=0rightarrow sum _{i=1}^{m}beta_{i}y^{(i)}=0

l(beta )=underset{w,b}{min}left { l(w,b,beta) right }=underset{w,b}{min}left { frac{1}{2}w^{t}w-sum_{i=1}^{m}beta_{i}y^{(i)}w^{t}x^{(i)}-sum_{i=1}^{m}beta_{i}y^{(i)}b+sum_{i=1}^{m}beta_{i} right }

=underset{w,b}{min}left { frac{1}{2}w^{t}w-w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}-bsum_{i=1}^{m}beta_{i}y^{(i)}+sum_{i=1}^{m}beta_{i} right }

=underset{w,b}{min}left { frac{1}{2}w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}-w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}-bsum_{i=1}^{m}beta_{i}y^{(i)}+sum_{i=1}^{m}beta_{i} right }

=underset{w,b}{min}left { -frac{1}{2}w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}+sum_{i=1}^{m}beta_{i} right }

=underset{w,b}{min}left { -frac{1}{2}w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}w^{t}+sum_{i=1}^{m}beta_{i} right }

= -frac{1}{2}sum_{j=1}^{m}beta_{j}y^{(j)}(x^{(j)})^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}+sum_{i=1}^{m}beta_{i}

=sum_{i=1}^{m}beta_{i} -frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}(x^{(i)})^{t}x^{(j)}

l(beta)=sum_{i=1}^{m}beta_{i} -frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}(x^{(i)})^{t}x^{(j)},s.t.sum_{i=1}^{m}beta_{i}y^{(i)}=0

  • 第三点:l^{*}(w,b,beta)

l^{*}(w,b,beta)=underset{beta}{max}(l(beta))=underset{beta}{min}(-l(beta))

l^{*}(w,b,beta)= left{begin{matrix} underset{beta}{min}(-l(beta))\ s.t.sum_{i=1}^{m}beta_{i}y^{(i)}=0 end{matrix}right.rightarrowl^{*}(w,b,beta)=left{begin{matrix} minleft { frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}(x^{(i)})^{t}x^{(j)}-sum_{i=1}^{m}beta_{i} right }\ s.t.sum_{i=1}^{m}beta_{i}y^{(i)}=0 end{matrix}right.

l^{*}(w,b,beta)=left{begin{matrix} minleft { frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}(x^{(i)})^{t}x^{(j)}-sum_{i=1}^{m}beta_{i} right }\ s.t.sum_{i=1}^{m}beta_{i}y^{(i)}=0 end{matrix}right.

第四步:使用SMO算法得到最优解beta^{*}

第五步:根据w,b,beta关系以及支持向量集合(S个)left { (x^{s},y^{s})|beta_{s}> 0 right },更新w^{*},b^{*}

w^{*}=sum_{i=1}^{m}beta _{i}y^{(i)}x^{(i)}

b^{*}=frac{1}{s}sum _{s=1}^{s}(y^{(s)}-sum _{i=1}^{m}beta_{i}y^{(i)}(x^{(i)})^{t}x^{(s)})

第六步:构建最终分类器

f(x)=sign(w^{*}x+b^{*})

2)软间隔SVM算法流程

注意:软间隔要求每个样本都引入松弛因子xi,使得样本的函数距离加上松弛因子之后大于等于1,样本的函数距离要求放松了,对异常样本敏感度下降

第一步:假定条件(超平面、支持向量、支持向量距离、松弛因子、惩罚项)

  • 第一点:超平面

y=w^{t}x+b

  • 第二点:支持向量(松弛因子xi=0

left { x|w^{t}x+b=pm 1 right }

  • 第三点:支持向量的间隔

frac{|w^{t}x+b|}{||w||_{2}}=frac{1}{||w||_{2}}

  • 第四点:松弛因子xi(xigeq 0)

松弛因子xi越大,意味者样本的函数距离越小(越接近超平面,甚至越过超平面),但是过大的松弛因子xi会导致分类错误可能性上升,松弛因子的引入是有代价的,需要对其进行惩罚

  • 第五点:惩罚项
  • 对松弛因子xi进行L1惩罚,加入惩罚系数C(超参C>0)
  • 惩罚系数越小,意味者松弛因子越大,分类准确性越低,反之,松弛因子越小,分类准确性越高

第二步:目标函数

left{begin{matrix} max(frac{1}{||w||_{2}})+csum_{i=1}^{m}xi _{i}\s.t.y^{(i)}(w^{t}x^{(i)}+b)+xi geq 1,i=1,2,...,m\s.t.xi _{i}geq 0,i=1,2,...,m end{matrix}right.rightarrowleft{begin{matrix} min(frac{1}{2}||w||tfrac{2}{2})+csum_{i=1}^{m}xi _{i}\s.t.1-xi-y^{(i)}(w^{t}x^{(i)}+b)leq 0 ,i=1,2,...,m\s.t.-xi _{i}leq 0 end{matrix}right.

第三步:对于有条件约束的目标函数采用泛拉格朗日乘子法进行凸优化

  • 第一点:构建泛拉格朗日函数(泛拉格朗日乘子betageq 0,mu geq 0),并将原始问题转化为对偶问题

l(w,b,xi ,beta,mu )=underset{w,b,xi ,beta,mu }{arg min}left { frac{1}{2}||w||^{2}_{2}+csum_{i=1}^{m}xi _{i}+sum_{i=1}^{m}beta_{i}(1-xi _{i}-y^{(i)}(w^{t}x^{(i)}+b))-sum_{i=1}^{m}mu _{i}xi _{i} right }

underset{w,b,xi ,beta,mu }{arg min}(l(w,b,xi ,beta,mu ))leftrightarrow underset{w,b,xi }{min}left { underset{beta,mu}{ max}l(w,b,beta) right }leftrightarrow underset{beta,mu}{max}left {underset{w,b,xi }{ min}l(w,b,beta) right }

  • 第二点:l(beta,mu )

l(beta,mu )=underset{w,b,xi}{min}left { l(w,b,xi ,beta,mu ) right }

frac{partial l(w,b,xi ,beta,mu )}{partial w}=w-sum _{i=1}^{m}beta_{i}y^{(i)}x^{(i)}=0rightarrow w^{*}=sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}

frac{partial l(w,b,xi ,beta,mu )}{partial b}=-sum _{i=1}^{m}beta_{i}y^{(i)}=0rightarrow sum _{i=1}^{m}beta_{i}y^{(i)}=0

frac{partial l(w,b,xi ,beta,mu )}{partial xi_{i} }=c-beta _{i}-mu _{i}=0rightarrow c-beta _{i}-mu _{i}=0,i=1,2,...,m

l(beta,mu )=underset{w,b,xi }{min}left { l(w,b,xi ,beta,mu ) right }

=underset{w,b,xi}{min}left { frac{1}{2}w^{t}w+csum_{i=1}^{m}xi _{i}-sum_{i=1}^{m}beta_{i}xi _{i}-sum_{i=1}^{m}beta_{i}y^{(i)}w^{t}x^{(i)}-sum_{i=1}^{m}beta_{i}y^{(i)}b+sum_{i=1}^{m}beta_{i} -sum_{i=1}^{m}mu _{i}xi _{i}right }

=underset{w,b,xi}{min}left { frac{1}{2}w^{t}w-sum_{i=1}^{m}beta_{i}xi _{i}-sum_{i=1}^{m}beta_{i}y^{(i)}w^{t}x^{(i)}-sum_{i=1}^{m}beta_{i}y^{(i)}b+sum_{i=1}^{m}beta_{i} +sum_{i=1}^{m}(c-mu _{i})xi _{i}right }

=underset{w,b,xi}{min}left { frac{1}{2}w^{t}w-sum_{i=1}^{m}beta_{i}xi _{i}-sum_{i=1}^{m}beta_{i}y^{(i)}w^{t}x^{(i)}-sum_{i=1}^{m}beta_{i}y^{(i)}b+sum_{i=1}^{m}beta_{i} +sum_{i=1}^{m}beta _{i}xi _{i}right }

=underset{w,b,xi}{min}left { frac{1}{2}w^{t}w-sum_{i=1}^{m}beta_{i}y^{(i)}w^{t}x^{(i)}-sum_{i=1}^{m}beta_{i}y^{(i)}b+sum_{i=1}^{m}beta_{i} right }

=underset{w,b,xi }{min}left { frac{1}{2}w^{t}w-w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}-bsum_{i=1}^{m}beta_{i}y^{(i)}+sum_{i=1}^{m}beta_{i} right }

=underset{w,b,xi }{min}left { frac{1}{2}w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}-w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}-bsum_{i=1}^{m}beta_{i}y^{(i)}+sum_{i=1}^{m}beta_{i} right }

=underset{w,b,xi }{min}left { -frac{1}{2}w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}+sum_{i=1}^{m}beta_{i} right }

=underset{w,b,xi }{min}left { -frac{1}{2}w^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}w^{t}+sum_{i=1}^{m}beta_{i} right }

= -frac{1}{2}sum_{j=1}^{m}beta_{j}y^{(j)}(x^{(j)})^{t}sum_{i=1}^{m}beta_{i}y^{(i)}x^{(i)}+sum_{i=1}^{m}beta_{i}

=sum_{i=1}^{m}beta_{i} -frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}(x^{(i)})^{t}x^{(j)}

l(beta,mu )=l(beta)=sum_{i=1}^{m}beta_{i} -frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}(x^{(i)})^{t}x^{(j)},s.t.left{begin{matrix} sum_{i=1}^{m}beta_{i}y^{(i)}=0\c-beta_{i}-mu_{i} =0,i=1,2,...,mend{matrix}right.

  • 第三点:l^{*}(w,b,xi ,beta,mu )

l^{*}(w,b,xi ,beta,mu )=underset{beta,mu }{max}(l(beta,mu ))=underset{beta}{max}(l(beta))=underset{beta}{min}(-l(beta))

l^{*}(w,b,xi ,beta,mu )= left{begin{matrix} underset{beta}{min}(-l(beta))\ s.t.sum_{i=1}^{m}beta_{i}y^{(i)}=0\s.t.c-beta _{i}-mu _{i}=0,i=1,2,...,m end{matrix}right.rightarrow l^{*}(w,b,xi ,beta,mu )=left{begin{matrix} minleft { frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}(x^{(i)})^{t}x^{(j)}-sum_{i=1}^{m}beta_{i} right }\ s.t.sum_{i=1}^{m}beta_{i}y^{(i)}=0\s.t.0leq beta _{i}leq c,i=1,2,...,m end{matrix}right.

第四步:使用SMO算法得到最优解beta^{*}

第五步:根据w,b,xi ,beta,mu关系以及支持向量集合(S个)left { (x^{s},y^{s})|�<beta_{s}< c right },更新w^{*},b^{*}

注意:支持向量满足如下关系推导

rightarrow xi _{i}=0rightarrow left{begin{matrix} mu _{i}> 0rightarrow beta _{i}< c\ 1-xi _{i}-y^{(i)}(w^{t}x+b)=0rightarrow beta _{i}> 0 end{matrix}right.rightarrow 0< beta _{i}< c

w^{*}=sum_{i=1}^{m}beta _{i}y^{(i)}x^{(i)}

b^{*}=frac{1}{s}sum _{s=1}^{s}(y^{(s)}-sum _{i=1}^{m}beta_{i}y^{(i)}(x^{(i)})^{t}x^{(s)})

第六步:构建最终分类器

f(x)=sign(w^{*}x+b^{*})

2 线性不可分SVM

1)线性不可分SVM的核心思想

无法找到超平面将数据尽可能多分布在超平面两侧,引入核函数可以将低维度特征映射到高维度空间中,以实现线性可分,从而使用硬间隔或者软间隔SVM模型

2)核函数

第一点:常用的核函数k(x,z)=phi (x)phi (z)

  • 线性核函数(不推荐使用)

k(x,z)=xz

  • 多项式核函数(gamma ,r,d属于超参,不推荐使用)

k(x,z)=(gamma xz+r)^{d}

  • 高斯核函数(gamma(gamma > 0)属于超参,推荐使用)

k(x,z)=e^{-gamma ||x-z||tfrac{2}{2}}

  • Sigmoid核函数(gamma ,r属于超参,不推荐使用)

k(x,z)=tanh(gamma xz+r)

第二点:核函数的优势k(x,z)=phi (x)phi (z)

  • 低维度特征映射到高维度空间中
  • 避免高维度恐怖的内积运算,变成低维度的内积运算
  • 核函数重要性质:k(x,z)=k(z,x)

第三点:证明高斯核函数,把低维度特征映射到高维度特征(令:z=x

k(x,z)=e^{-gamma ||x-z||tfrac{2}{2}}=e^{-gamma (x-z)^{t}(x-z)}=e^{-gamma (x^{t}x-x^{t}z-z^{t}x+z^{t}z)}

=e^{-gamma (||x||_{2}^{2}+||z||_{2}^{2}-x^{t}z-z^{t}x)}=e^{-gamma (||x||_{2}^{2}+||z||_{2}^{2}-2x^{t}z)}=e^{-gamma ||x||_{2}^{2}}e^{-gamma ||z||_{2}^{2}}e^{2gamma x^{t}z}

=e^{-gamma ||x||_{2}^{2}}e^{-gamma ||z||_{2}^{2}}sum_{i=1}^{+infty }frac{(2gamma x^{t}z)^{i}}{i!}(使用泰勒公式)

=sum_{i=1}^{+infty }e^{-gamma ||x||_{2}^{2}}e^{-gamma ||z||_{2}^{2}}sqrt{frac{(2gamma)^{i}}{i!}}sqrt{frac{(2gamma)^{i}}{i!}}||x||_{2}^{i}||z||_{2}^{i}

=sum_{i=1}^{+infty }e^{-gamma ||x||_{2}^{2}}sqrt{frac{(2gamma)^{i}}{i!}}||x||_{2}^{i}*e^{-gamma ||z||_{2}^{2}}sqrt{frac{(2gamma)^{i}}{i!}}||z||_{2}^{i}

=phi (x)phi (z)

注意:phi (x)x从低维度特征转换为高维度特征

phi (x)=sum_{i=1}^{+infty }e^{-gamma ||x||_{2}^{2}}sqrt{frac{(2gamma)^{i}}{i!}}||x||_{2}^{i}=e^{-gamma ||x||_{2}^{2}}(1,sqrt{frac{2gamma }{i}}||x||_{2},sqrt{frac{2gamma }{i}}||x||_{2}^{2},....,sqrt{frac{2gamma }{i}}||x||_{2}^{+infty })

第四点:核函数可以自定义,但是需要满足条件

核函数必须是正定核函数,换言之,gram矩阵(格拉姆矩阵)为半正定矩阵

gram=begin{bmatrix} k(x_{1}z_{1}),k(x_{1}z_{2}),k(x_{1}z_{3}),...,k(x_{1}z_{n})\ k(x_{2}z_{1}),k(x_{2}z_{2}),k(x_{2}z_{3}),...,k(x_{2}z_{n}) \ ... \ k(x_{n}z_{1}),k(x_{n}z_{2}),k(x_{n}z_{3}),...,k(x_{n}z_{n}) end{bmatrix}

3)线性不可分SVM算法流程(SVM软间隔模型)

第一步:引入核函数k (x),将低维度特征映射到高维度空间中

第二步:需要优化的目标函数l^{*}(w,b,xi ,beta,mu )(直接使用软间隔模型中需要优化的目标函数)

l^{*}(w,b,xi ,beta,mu )=left{begin{matrix} minleft { frac{1}{2}sum_{i=1}^{m}sum_{j=1}^{m}beta_{i}beta_{j}y^{(i)}y^{(j)}k(x^{(i)},x^{(j)})-sum_{i=1}^{m}beta_{i} right }\ s.t.sum_{i=1}^{m}beta_{i}y^{(i)}=0\s.t.0leq beta _{i}leq c,i=1,2,...,m end{matrix}right.

第三步:使用SMO算法得到最优解beta^{*}

第五步:根据w,b,xi ,beta,mu关系以及支持向量集合(S个)left { (x^{s},y^{s})|�<beta_{s}< c right },更新w^{*},b^{*}

注意:支持向量满足如下关系推导

rightarrow xi _{i}=0rightarrow left{begin{matrix} mu _{i}> 0rightarrow beta _{i}< c\ 1-xi _{i}-y^{(i)}(w^{t}x+b)=0rightarrow beta _{i}> 0 end{matrix}right.rightarrow 0< beta _{i}< c

w^{*}=sum_{i=1}^{m}beta _{i}y^{(i)}x^{(i)}

b^{*}=frac{1}{s}sum _{s=1}^{s}(y^{(s)}-sum _{i=1}^{m}beta_{i}y^{(i)}(x^{(i)})^{t}x^{(s)})

第六步:构建最终分类器

f(x)=sign(w^{*}x+b^{*})

3 SVR(不推荐使用)

有时间更新

三 SMO算法

有时间更新

最后

以上就是心灵美钢笔为你收集整理的机器学习--分类算法--SVM算法理论一 算法概述二 算法理论三 SMO算法的全部内容,希望文章能够帮你解决机器学习--分类算法--SVM算法理论一 算法概述二 算法理论三 SMO算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(32)

评论列表共有 0 条评论

立即
投稿
返回
顶部