刘惊雷,廖士中.CP-nets学习的复杂度[J].计算机科学,2018,45(6):211-215
CP-nets学习的复杂度
Complexity of CP-nets Learning
投稿时间:2017-05-30  修订日期:2017-06-30
DOI:10.11896/j.issn.1002-137X.2018.06.038
中文关键词:  二值条件偏好网,推理与学习,命题公式的可满足性,有界树宽的 CP-nets,复杂度的上下界
英文关键词:Binary-valued conditional preference networks,Reasoning and learning,Satisfiability of propositional formula,Bounded tree-width CP-nets,Upper and lower bound of complexity
基金项目:本文受国家自然科学基金(61673293,9,61773331)资助
作者单位E-mail
刘惊雷 天津大学计算机科学与技术学院 天津300072
烟台大学计算机与控制工程学院 山东 烟台264005 
 
廖士中 天津大学计算机科学与技术学院 天津300072 shizhongliao@tju.edu.cn 
摘要点击次数: 243
全文下载次数: 180
中文摘要:
      CP-nets是一种简单且直观的图形化偏好表示工具,其表示、推理和学习是3个基本问题。不同于基于统计学习理论的研究方法,文中基于逻辑理论来研究二值CP-nets的学习问题。首先,建立命题公式的可满足性和CP-nets表示的偏好公式之间的联系,将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.Diffe-rently 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 se-cond 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.
查看全文  查看/发表评论  下载PDF阅读器