二维欧氏空间内线性凸区域概念的PAC学习算法

摘要

实例空间X的一个子集规定一个概念,表现为一个函数c:X→{0,1}。给定X上一个分布D,可能近似正确(PAC)学习算法的目的是基于独立同分布样本S,由算法产生一个近似函数hS,以高概率保证它与目标函数c的误差不超过给定误差值。如果存在这样的算法其样本复杂性及时间复杂性受多项式界,则认为目标概念可以有效PAC学习。本文讨论二维欧氏空间上有界线性凸区域定义的目标概念的学习理论和方法,证明了有界线性凸区域定义的目标概念是有效PAC可学习的,其方法可以推广到n维欧氏空间上由超平面界定的有界凸区域对应的目标概念学习。