Conditional Preference Network with Constraints and Uncertainty

1 Introduction andMotivation

For compact representation of user's conditional ceteris paribus preference statements, Boutilier et al. [2004b] proposed the CP-net model which is a directed graph, where each node (variable) is annotated with the corresponding preference table. The TCP-net [Brafman et al., 2006] accounts into user's conditional relative importance statements with the CP-net. Generally, both models induce a partial order over the outcomes. Given these models are extended with a set of hard constraints, necessary solving algorithms [Boutilier et al., 2004a; Brafman et al., 2006] have been proposed to find the set of feasible and preferentially non-dominated outcomes. In order to find this latter set (Pareto set), the algorithms require dominance testing between pairs of outcomes. In general, dominance testing is PSPACE-complete [Goldsmith et al., 2008], and therefore is very expensive especially given that the Pareto set can be of exponential size.

User's choices involve habitual behavior and genuine decision [Katona, 1951]. Habitual behavior is a form of routine behavior that is represented using preferences. In contrast, genuine decision requires to perceive and reason about a given situation, and to obtain a solution of the problem raised by the situation. Genuine decision is influenced by the environmental factors such as cost. There is no mechanism in literature to represent both habitual behavior and genuine decision in a single model, in multi-attribute case.

2 Contributions

We formally illustrate the relative importance relation between the variables, which is induced by the parent-child relation of an acyclic CP-net [Ahmed and Mouhoub, 2018b]. We show that the CP-net represents a total order of the outcomes, in particular cases, if and only if the induced variable importance order is total. This motivates us to extend the general CP-net model such that it guarantees to represent a total order over the outcomes. In this regard, after constructing an acyclic CP-net, we determine every pair of variables in which the CP-net does not induce a relative importance relation, and we ask the user to explicitly provide a variable importance order for that pair. We call the extended model - the CPR-net, that always represents a total order over the outcomes. As a result, there is a single optimal solution for the Constrained CPR-net. Then, we give an efficient algorithm to obtain this optimal solution. The main advantage is that the algorithm does not require dominance testing.

We propose a novel algorithm that we call Search-PartialCP to find the set of Pareto optimal solutions given an acyclic partial CP-net and a set of hard constraints [Ahmed and Mouhoub, 2018a]. One important property of Search-PartialCP is that, when it produces a solution, this solution is never replaced. Therefore, if one is interested to get a single solution, the algorithm can be stopped as soon as the first solution is obtained. In this case, dominance testing is not needed. However, if one wants to obtain all - or more than one - solutions, the dominance testing is needed. Therefore, the performance of the algorithm will depend on how efficiently the dominance testing can be performed.

We represent genuine decision using the notion of "comfort" with the fact that, the more comfort the environmental factors give to user, the more intent the user is to decide for the option [Ahmed and Mouhoub, 2018c; Ahmed and Mouhoub, 2018e]. As an example, given the cost of an option, the comfort will be inversely proportional to the cost, i.e., comfort = 1/cost. We explore the meaning of comfort in multi-attribute case. Then, we propose an extension of the CP-net model that we call the CP-net with Comfort (CPC-net), to represent and reason about both preferences and comfort. For an acyclic CPC-net, the outcome optimization queries can be performed in linear time on the number of variables. On the other hand, two outcomes in a CPC-net are compared using both preference and comfort. We show that two outcomes can stand in one of six possible relations.

We propose the Probabilistic TCP-net (PTCP-net) to aggregate a set of TCP-nets with a single model extending the TCP-nets with a probability for each preference and relative importance statements [Ahmed and Mouhoub, 2018d; Ahmed and Mouhoub, 2017]. After a PTCP-net is built, we answer two queries: (1) finding the most probable TCP-net for a given PTCP-net, which should most likely map onto an unknown user, and (2) finding the most probable optimal outcome that a recommender system should suggest to maximize the probability of a correct recommendation to an unknown user. Intuitively, these queries are useful in collaborative filtering type recommender systems [Ahmed, 2017].

3 OngoingWorks

We focus to develop a divide and conquer algorithm to efficiently answer the dominance query in acyclic CP-nets. We observe that the upper portion of any topological order which gives the same value to both outcomes, are not needed to consider in the search process. Given a variable in the topological order which gives two distinct values to the outcomes, we divide the problem into two sub problems - one for each value. For each sub problem, a sub CP-net is built by removing the variable and its ancestors from the original CP-net. Then, the original query is answered by answering two sub queries in the sub CP-nets. After we develop the algorithm, we plan to compare its efficiency with the existing methods.

An ordering query in an acyclic CP-net answers if an outcome is not preferred to another. These queries can be answered in linear time [Boutilier et al., 2004b]. In this area, we focus on two things. First, we develop methods to answer ordering queries in partial CP-net as this is an open question. Second, we apply the ordering query in the solving algorithm for Constrained CP-net, instead of dominance testing. In particular, a feasible solution is checked for its non-dominance with every existing solution, using ordering query. Intuitively, we get correct solutions but not necessarily all solutions. We plan to establish a compromise between efficiency and completeness of using ordering query in Constrained CP-nets.

4 Conclusion

This paper outline three aspects of the CP-net model. First, we extend the CP-net with additional relative importance statements. Constrained optimization with the new model does not require dominance testing. Second, we represent user's genuine decision using comfort. Then, we propose the CPC-net to represent both preference and comfort. Third, we extend the TCP-net with probability. The PTCP-net can aggregate a set of TCP-nets sharing the same variables but having different preference statements. Finally, we briefly describe a few in-progress works and challenges.

Acknowledgements

I sincerely thank my supervisor (Dr. Malek Mouhoub) for his valuable support and guidance.