CP-nets学习的复杂度

摘要：

CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题.不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题.首先,建立命题公式的可满足性和CP-nets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题.随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P.这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界.

关键词：二值条件偏好网、推理与学习、命题公式的可满足性、有界树宽的CP-nets、复杂度的上下界

所属期刊栏目：45

分类号：TP182(自动化基础理论)

资助基金：国家自然科学基金61673293,61572419,61773331

在线出版日期：2018-08-30（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：211-215