Conditional Preference Networks: Learning and Optimization

The last two decades have shown a great body of work in the eld of Arti cial Intelligence (AI) addressing issues related to representing, reasoning and learning preferences. One of the main models for graphical representation of preferences is that of Conditional Preference Networks (CP-nets). A CP-net de nes a partial order over the set of outcomes or alternatives by providing a concise set of small preference statements. Since their introduction, CP-nets have been intensively studied and applied in various problems involving preferences. This thesis is concerned with two main issues related to CP-nets: learning and optimization. Concerning the learning aspect, we determine the information complexity of learning acyclic CP-nets in di erent models. We also consider the problem of learning CP-nets from queries and provide query strategies that are shown to be near-optimal. With regard to the optimization part, we study the problem of solving a constrained CP-net, i.e., a CP-net where some outcomes are infeasible. Our main goal is to nd at least one outcome that is feasible but not dominated with respect to the induced order of the CP-net, i.e., a Pareto set. We study the e ect of variable ordering heuristics and constraint propagation to the problem and show that a variable ordering heuristic augmented with constraint propagation yields a saving to the solving process.

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Doctoral -- first

Discipline thesis:degree_discipline

Computer Science

Grantor dc:publisher

Faculty of Graduate Studies and Research, University of Regina

Year dc:date.issued

2016

Author dc:creator

• Alanazi, Eisa Ayed

Advisor dc:contributor.advisor

• Mouhoub, Malek

Committee members dc:contributor.committeemember

• El-Darieby, Mohamed
• Zilles, Sandra
• Butz, Cory
• Sadaoui-Mouhoub, Samira

Language dc:language.iso

en

DOI

https://doi.org/10.82465/4114

OAI identifier oai:identifier

oai:uregina.scholaris.ca:10294/7676