1、简介
vc理论(Vapnik–Chervonenkis theory )是由 Vladimir Vapnik 和 Alexey Chervonenkis发明的。该理论试图从统计学的角度解释学习的过程。而VC维是VC理论中一个很重要的部分。
2、定义
定义:对一个指示函数集,如果存在h个样本能够被函数集中的函数按所有可能的 种形式分开,则称函数集能够把h个样本打散;函数集的VC维就是它能打散的最大样本数目h.若对任意数目的样本都有函数能将它们打散,则函数集的VC维是无穷大.
VC维反映了函数集的学习能力,VC维越大则学习机器越复杂(容量越大).学习能力越强。
故有这样的结论,平面内只能找到3个点能被直线打散而不找到第4个。
对于这个结论可以按如下方式理解:
(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个点能被直线打散。
分享到:
相关推荐
此后在二十世纪70-80年代,随着模式识别中最大边距决策边界的理论研究 [10] 、基于松弛变量(slack variable)的规划问题求解技术的出现 [11] ,和VC维(Vapnik-Chervonenkis dimension, VC dimension)的提出 [12] ...
支持向量机是Cortes和Vapnik于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中
支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷,...
《support vector machine for histogram-based image classification》介绍的是用HSV颜色空间的颜色直方图来提取特征进行SVM图像分类。 另一篇是讲在核选择时参数选择的方法
V.Vapnik Statistical Learning Theory John Wiley&Sons,1988
Vapnik V.N. The nature of statistical learning theory.pdf
统计学习理论大师Vapnik的 The Nature Of Statistical Learning第二版。这个版本是可以复制的,很完美。
统计学习理论大师Vapnik的 The Nature Of Statistical Learning第二版
Statistical Learning Theory - Vapnik - 1998 统计学习理论经典教程 高清 可复制
本文来源于csdn,介绍了SVM,线性分类器,线性分类器的...支持向量机方法是建立在统计学习理论的VC维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,Accuracy)和
支持向量机方法是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性(即对特定训练样本的学习精度,Accuracy)和学习能力(即无错误地识别任意样本的能力)之间寻求最佳折衷...
Chervonenkis 在1963年提出,目前的版本(soft margin)是由 Corinna Cortes 和 Vapnik 在1993年提出,并在1995年发表。深度学习(2012)出现之前,SVM 被认为机器学习中近十几年来最成功,表现最好的算法。
统计、模式识别方面的大牛Vapnik的经典作品:Estimation of Dependences Based on Empirical Data 2nd Edition(基于经验数据的依赖性估计 第二版)。 2006年重印,这里的文件是新加入的内容。
《The nature of statistical learning theory》 统计学习的经典
统计学习理论的基本内容诞生于20世纪60~70年代,到90年代中期发展到比较成熟并受到世界机器学习界的广泛重视,其核心内容反映在Vapnik的两部重要著作中,本书即是其中一部,另一部是“The Nature of Statistical ...
支持向量机(Support Vector Machine)是Cortes和Vapnik于...它是建立在统计学习理论的VC 维理论和结构风险最小原理基础上的,根据有限的样本信息在模型的复杂性和学习能力之间寻求最佳折衷,以期获得最好的推广能力。
支持向量机(Support Vector Machine, SVM)是由Cortes(科尔特斯)和Vapnik(瓦普尼克)于1995年首先提出。 SVM在解决小样本、非线性等分类问题中表现出许多特有的优势,并能够推广到函数拟合等有关数据预测的应用中。
支持向量机(Support Vector Machine,SVM)是Corinna Cortes和Vapnik等于1995年首先提出的,它在解决小样本、非线性及高维模式识别中表现出许多特有的优势,并能够推广应用到函数拟合等其他机器学习问题中。...