Learning CP-net preferences online from user queries

We present an online, heuristic algorithm for learning Conditional Preference networks (CP-nets) from user queries. This is the first efficient and resolute CP-net learning algorithm: if a preference order can be represented as a CP-net, our algorithm learns a CP-net in time n ^p, where p is a bound on the number of parents a node may have. The learned CP-net is guaranteed to be consistent with the original CP-net on all queries from the learning process. We tested the algorithm on randomly generated CP-nets; the learned CP-nets agree with the originals on a high percent of non-training preference comparisons.