加载中…

加载中...

个人资料
faruto
faruto 新浪个人认证
  • 博客等级:
  • 博客积分:0
  • 博客访问:1,207,578
  • 关注人气:2,114
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
正文 字体大小:

[转载]结构风险最小和VC维理论的解释

(2012-01-12 13:41:09)
标签:

转载

分类: SVM

“支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上”

结构化风险

结构化风险 = 经验风险 + 置信风险

经验风险 =  分类器在给定样本上的误差

置信风险 = 分类器在未知文本上分类的结果的误差

置信风险因素:

  • 样本数量,给定的样本数量越大,学习结果越有可能正确,此时置信风险越小;
  • 分类函数的VC维,显然VC维越大,推广能力越差,置信风险会变大。

提高样本数量,降低VC维,降低置信风险。

以前机器学习的目标是降低经验风险,要降低经验风险,就要提高分类函数的复杂度,导致VC维很高,VC维高,置信风险就高,所以,结构风险也高。---- 这是SVM比其他机器学习具有优势的地方。

 

机器学习导论 的解释 :假定我们有一个数据集,包含N个点。这N个点可以用 种方法标记为正例和负例(属于和不属于某个类)。因此,N个数据点可以定义 种不同的学习问题。假如(,)逗号前的是属于,逗号都的是不属于。比如1个点,可以分为( a , )( , a );2个点可以分为( ab , )( , ab )  ( a , b ) ( b , a )四种;依次类推...如果对于这些问题中的任何一个,我们都能够找到一个假设h∈ 将正例和负例分开,那么我们就称 散列(shatter )N个点。也就是说,可以用N个点定义的任何的学习问题都能够用一个从中抽取的假设无误差地学习。可以被散列的点的最大数量称为 VC 维(Vapnik Cortes ),记为VC( ),它度量假设类 的学习能力(capactiy )。

 

下面是理解VC维的一个例子:

(1)平面内只能找到3个点能被直线打散:直线只能把一堆点分成两堆,对于3个点,要分成两堆加上顺序就有23种。其中A、B、C表示3个点,+1,-1表示堆的类别, {A→-1,BC→+1}表示A分在标号为-1的那堆,B和C分在标号为+1的那堆。这就是一种分发。以此类推。则有如下8种分法:
{A→-1,BC→+1},{A→+1,BC→-1}
{B→-1,AC→+1},{B→+1,BC→-1}
{C→-1,AB→+1},{C→+1,BC→-1}
{ABC→-1},{ABC→+1}
(2)找不到4个点。假设有,则应该有24=16分法,但是把四个点分成两堆有:一堆一个点另一对三个点(1,3);两两均分(2,2);一堆四个另一堆没有(0,4)三种情况。对于第一种情况,4个点可分别做一次一个一堆的,加上顺序就有8种:
{A→-1,BCD→+1},{A→+1,BCD→-1}
{B→-1,ACD→+1},{B→+1,ACD→-1}
{C→-1,ABD→+1},{C→+1,ABD→-1}
{D→-1,ABC→+1},{D→+1,ABC→-1};
对于第二种情况有4种:
{AB→-1,CD→+1},{AB→+1,CD→-1}
{AC→-1,BD→+1},{AC→+1,BD→-1}
没有一条直线能使AD在一堆,BC在一堆,因为A、D处在对角线位置,B、C处在对角线位置。(这是我直观在图上找出来的)
对于第三种情况有2种;
{ABCD→-1}
{ABCD→+1}
所以总共加起来只有8+4+2=14种分法,不满足24=16分法,所以平面找不到4个点能被直线打散。

0

  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有