论文部分内容阅读
贝叶斯网起源于20世纪80年代中期对人工智能中不确定性问题的研究,它是概率论和图论相结合的产物.近几十年来贝叶斯网已经逐渐成为把概率和统计运用于复杂系统的不确定性推理和数据分析的一种有效方法.贝叶斯分类算法可以用来处理各种类型的数据(离散或连续),它在现实生活中有着十分广泛的应用,如在多标记分类、垃圾信息过滤、网络异常检测、文本分类、数据预测、自动答疑系统、入侵检测和认知诊断分类中. 本文主要研究贝叶斯网诱导的概念类的复杂性问题.Vapnik-Chervonenkis(VC)维是刻化一类函数复杂性的一种度量,也可以用来衡量分类器的泛化能力.欧氏维数是函数类复杂程度的另一种度量.VC维和欧氏维数是用来评价贝叶斯网分类能力的两个常用的指标,自然地,两个维数之间的关系是该研究分支的一个重要问题. 我们重点讨论一类贝叶斯网诱导的概念类的VC维和欧氏维数,该类贝叶斯网中任意一个有向无圈图只包含一个V-结构,并且忽略它的边的方向得到的无向图是一个环,每个节点对应一个二值随机变量.借助前人给出的用矩阵表示无向离散图模型的方法,我们给出了有向离散图模型的矩阵表示.考虑有(4)n n≥个节点的贝叶斯网,它对应一个(4n+2)×2n的矩阵,矩阵中的元素是0或1.经计算,该矩阵的秩是2n+3. 针对有两分类任务的上述一类贝叶斯网,我们讨论了当有(4)n n≥个节点且每个节点对应一个二值随机变量时,该贝叶斯网诱导的概念类的VC维和欧氏维数之间的数量关系.基于前人的理论结果,可知该贝叶斯网诱导的概念类的欧氏维数小于等于2n+3,我们证明了该贝叶斯网诱导的概念类的VC维大于等于2n+3.由于有限概念类的VC维总是不超过欧氏维数,故该贝叶斯网诱导的概念类的VC维和欧氏维数相同,均为2n+3.