AAAI Publications, Twenty-Ninth AAAI Conference on Artificial Intelligence

Font Size: 
Learning Partial Lexicographic Preference Trees over Combinatorial Domains
Xudong Liu, Miroslaw Truszczynski

Last modified: 2015-02-18


We introduce partial lexicographic preference trees (PLPtrees) as a formalism for compact representations of preferences over combinatorial domains. Our main results concern the problem of passive learning of PLP-trees. Specifically, forseveral classes of PLP-trees, we study how to learn (i) a PLP-tree consistent with a dataset of examples, possibly subject to requirements on the size of the tree, and (ii) a PLP-tree correctly ordering as many of the examples as possible in case the dataset of examples is inconsistent. We establish complexity of these problems and, in all cases where the problem is in the class P, propose polynomial time algorithms.


preference learning, knowledge representation

Full Text: PDF