Conditional preference networks: efficient dominance testing and learning

Modelling and reasoning about preference is necessary for applications such as recommendation and decision support systems. Such systems are becoming increasingly prevalent in all aspects of our daily lives as technology advances. Thus, preference representation is a wide area of interest within the Artificial Intelligence community. Conditional preference networks, or CP-nets, are one of the most popular models for representing a person's preference structure. In this thesis, we address two issues with this model that make it difficult to utilise in practice. First, answering dominance queries efficiently. Dominance queries ask for the relative preference between a given pair of outcomes. Such queries are natural and essential for effectively reasoning about a person's preferences. However, they are complex to answer given a CP-net representation of preference. Second, learning a person's CP-net from observational data. In order to utilise a CP-net representation of a person's preferences, we must first determine the correct model. As direct elicitation is not always possible or practical, we must be able to learn CP-nets passively from the data we can observe. We provide two distinct methods of improving dominance testing efficiency for CP-nets. The first utilises a quantitative representation of preference in order to prune the associated search tree. The second reduces the size of a dominance testing problem by preprocessing the CP-net. Both methods are shown experimentally to significantly improve dominance testing efficiency. Furthermore, both are shown to outperform existing methods. These techniques can be combined with one another, and with the existing methods, in order to further improve efficiency. We also introduce a new, score-based learning technique for CP-nets. Most existing work on CP-net learning uses pairwise outcome preferences as data. However, such preferences are often impossible to observe passively from user actions, particularly in online settings, where users typically choose from a variety of options. Contrastingly, our method assumes a history of user choices as data, which is observable in a wide variety of contexts. Experimental evaluation of this method finds that the learned CP-nets show high levels of agreement with the true preference structures and with previously unseen (future) data.