基于约束的CP-nets学习方法研究

摘要

偏好处理是人工智能中的一个重要的研究内容。CP-nets(conditional preference networks,条件偏好网)是一个带标记的有向图,它编码相关变量之间的偏好关系。作为一种简单直观的图形偏好表示工具,却很少有工作对 CP-nets的结构进行研究,尤其是无环CP-nets的结构。基于约束的CP-nets学习方法研究,是在CP-nets结构学习的基础上进行的。本文以偏好数据库(preference database)中的用户偏好为研究对象,对偏好数据库进行偏好挖掘,发现用户的偏好都是带有条件的偏好。进而采用G方检验(G2检验)的方式,学习得到有环的CP-nets结构。最后根据精确P值计算方法和Dijkstra算法原理消去CP-nets结构中的环,得到无环的CP-nets结构N*。具体工作如下：
　　首先,针对传统的推荐系统需要用户给出明确的偏好矩阵(U-I矩阵),进而使用自动化技术来获取用户偏好的问题,提出了一种从偏好数据库中挖掘Agent偏好信息的方法。从知识发现的角度,通过ceteris paribus规则(CP规则),提出了k阶偏好挖掘算法(kPreM)。在算法中,利用 k阶 CP规则对数据库中的信息进行剪枝,减少了扫描次数,提高了偏好信息的挖掘效率。随后以一种通用的图模型 CP-nets为工具,揭示了用户的偏好可近似表达为CP-nets的定性条件偏好网。实验结果表明,用户的偏好都是带有条件的偏好。另外,通过挖掘得出的CP-nets偏好模型,为设计个性化的推荐系统提供了理论基础。
　　其次,利用G2检验学习得到有环的CP-nets结构。作为一种对数似然比检验方法, G2检验特别适合于判断变量之间的因果关系。由于 CP-nets的核心概念是条件偏好无关,因此利用G2检验可有效地实现CP-nets的结构学习。通过构造G2检验的统计量,在给定的成对比较(pairwise comparisons)样本集中,执行零假设检验,从而依次求出每个顶点的父亲集,进而得到 CP-nets的结构。通过随机生成的模拟数据,验证了所提出算法的有效性。与相关 CP-nets的学习算法对比, G2检验学习方法具有被动的、离线的和基于统计学习的特征。
　　最后,采用精确P值计算和Dijkstra算法,获取无环CP-nets结构N*,即获取变量之间的因果关系。传统的算法利用不同的方式对 CP-nets的结构进行学习,但很多方法学习得到的并不是无环 CP-nets。本文采用精确 P值计算学习方法,根据Dijkstra算法原理,设计了新的算法——PALA,并通过该算法学习无环 CP-nets结构。随后证明了算法的时间复杂度是O(n3·2n)。作为一种精确学习方法, P值计算可有效衡量变量之间的依赖程度,确定变量之间的因果关系,进而学习得到无环CP-nets结构。实验结果表明,与其他算法相比, PALA算法通常能够发现高质量的、结构最优的无环CP-nets。

目录

声明

1 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 内容组织

2 相关知识

2.1 Ceteris paribus偏好

2.2 偏好数据库

2.3 CP-nets图模型

2.4 上三角矩阵法

2.5 本章小结

3 从偏好数据库中挖掘ceteris paribus偏好

3.1 Ceteris paribus偏好挖掘算法

3.2 算法的性质分析

3.3 实验结果与分析

3.4 本章小结

4 基于G2检验学习CP-nets

4.1 G2检验

4.2 CP-nets学习算法

4.3 算法的性质分析

4.4 实验结果与分析

4.5 本章小结

5 基于精确P值计算学习无环CP-nets

5.1 精确P值计算

5.2 无环CP-nets学习算法

5.3 算法的性质分析

5.4 实验结果与分析

5.5 本章小结

6 总结与展望

参考文献

致谢

个人简历

攻读学位期间发表的论文

附录一 表目录

附录二 图目录