TY - JOUR AU - Liu, Xudong AU - Truszczynski, Miroslaw PY - 2015/02/18 Y2 - 2024/03/28 TI - Learning Partial Lexicographic Preference Trees over Combinatorial Domains JF - Proceedings of the AAAI Conference on Artificial Intelligence JA - AAAI VL - 29 IS - 1 SE - AAAI Technical Track: Knowledge Representation and Reasoning DO - 10.1609/aaai.v29i1.9403 UR - https://ojs.aaai.org/index.php/AAAI/article/view/9403 SP - AB - <p> 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. </p> ER -