CP-nets学习的复杂度  

Complexity of CP-nets Learning

作　　者：刘惊雷[1,2] 廖士中 LIU Jing-lei;LIAO Shi-zhong(School of Computer Science and Technology,Tianjin Universit;School of Computer and Control Engineering,Yantai Universit)

机构地区：[1]天津大学计算机科学与技术学院,天津300072 [2]烟台大学计算机与控制工程学院,山东烟台264005

出　　处：《计算机科学》2018年第6期211-215,共5页Computer Science

基　　金：国家自然科学基金(61673293;61572419;61773331)资助

摘　　要：CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CPnets表示的偏好公式之间的联系,将CP-nets的学习问题转化为命题的推理问题。随后,给出两类具有特殊结构的CP-nets的学习问题的计算复杂度,其中最复杂的无环CP-nets上的学习问题是NP-complete,而最简单的集合结构CP-nets上的学习问题是P。这些结论给出了CP-nets(如链结构、有界树宽)学习问题复杂度的上下界。CP-nets（Conditional Preference networks）are a kind of simple and intuitively graphical tool for representing conditional preference,three fundamental research questions of which are representation,reasoning and learning.Differently from the research point from statistical learning theory,the binary-valued CP-nets learning issues were studied based on logic theory.Firstly,an intimate relationship between satisfiability of proposition logic formula and preference assertion is given,therefore,the learning problem on CP-nets is transformed into the proposition reasoning.In the second place,the computational complexity for learning two kinds of specific CP-nets is given,the learning problem of most complicated acyclic CP-nets is NP-complete,whereas the learning problem of the simplest set-structured CP-nets is P.These interesting results establish the upper and lower bound of complexity for learning specific structured（e.g.,list-structured,bounded tree-width）CP-nets.

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

分 类 号：TP182[自动化与计算机技术—控制理论与控制工程]