Learning partial lexicographic preference trees over combinatorial domains

Xudong Liu; Miroslaw Truszczynski

Learning partial lexicographic preference trees over combinatorial domains

Xudong Liu, Miroslaw Truszczynski

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

20 Scopus citations

Abstract

We introduce partial lexicographic preference trees (PLP-trees) as a formalism for compact representations of preferences over combinatorial domains. Our main results concern the problem of passive learning of PLP-trees. Specifically, for several 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.

Original language	English
Title of host publication	Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015
Pages	1539-1545
Number of pages	7
ISBN (Electronic)	9781577357001
State	Published - Jun 1 2015
Event	29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015 - Austin, United States Duration: Jan 25 2015 → Jan 30 2015

Publication series

Name	Proceedings of the National Conference on Artificial Intelligence
Volume	2

Conference

Conference	29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015
Country/Territory	United States
City	Austin
Period	1/25/15 → 1/30/15

Bibliographical note

Publisher Copyright:
Copyright © 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.

ASJC Scopus subject areas

Software
Artificial Intelligence

Cite this

Liu, X., & Truszczynski, M. (2015). Learning partial lexicographic preference trees over combinatorial domains. In Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015 (pp. 1539-1545). (Proceedings of the National Conference on Artificial Intelligence; Vol. 2).

Liu, Xudong ; Truszczynski, Miroslaw. / Learning partial lexicographic preference trees over combinatorial domains. Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015. 2015. pp. 1539-1545 (Proceedings of the National Conference on Artificial Intelligence).

@inproceedings{bb2c90e7ef6043658b6c81ce2009f574,

title = "Learning partial lexicographic preference trees over combinatorial domains",

abstract = "We introduce partial lexicographic preference trees (PLP-trees) as a formalism for compact representations of preferences over combinatorial domains. Our main results concern the problem of passive learning of PLP-trees. Specifically, for several 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.",

author = "Xudong Liu and Miroslaw Truszczynski",

note = "Publisher Copyright: Copyright {\textcopyright} 2015, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; null ; Conference date: 25-01-2015 Through 30-01-2015",

year = "2015",

month = jun,

day = "1",

language = "English",

series = "Proceedings of the National Conference on Artificial Intelligence",

pages = "1539--1545",

booktitle = "Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015",

}

Liu, X & Truszczynski, M 2015, Learning partial lexicographic preference trees over combinatorial domains. in Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015. Proceedings of the National Conference on Artificial Intelligence, vol. 2, pp. 1539-1545, 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015, Austin, United States, 1/25/15.

Learning partial lexicographic preference trees over combinatorial domains. / Liu, Xudong; Truszczynski, Miroslaw.

Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015. 2015. p. 1539-1545 (Proceedings of the National Conference on Artificial Intelligence; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Learning partial lexicographic preference trees over combinatorial domains

AU - Liu, Xudong

AU - Truszczynski, Miroslaw

PY - 2015/6/1

Y1 - 2015/6/1

N2 - We introduce partial lexicographic preference trees (PLP-trees) as a formalism for compact representations of preferences over combinatorial domains. Our main results concern the problem of passive learning of PLP-trees. Specifically, for several 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.

AB - We introduce partial lexicographic preference trees (PLP-trees) as a formalism for compact representations of preferences over combinatorial domains. Our main results concern the problem of passive learning of PLP-trees. Specifically, for several 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.

UR - http://www.scopus.com/inward/record.url?scp=84959924628&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959924628&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84959924628

T3 - Proceedings of the National Conference on Artificial Intelligence

SP - 1539

EP - 1545

BT - Proceedings of the 29th AAAI Conference on Artificial Intelligence, AAAI 2015 and the 27th Innovative Applications of Artificial Intelligence Conference, IAAI 2015

Y2 - 25 January 2015 through 30 January 2015

ER -

Learning partial lexicographic preference trees over combinatorial domains

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Other files and links

Fingerprint

Cite this