Learning conditional preference network from noisy samples using hypothesis testing

The problem of learning Conditional Preference Networks (CP-nets) from a set of pairwise comparisons between outcomes has received great attention recently. However, because of the randomicity of the users' behaviors or the observation errors, there exists some noise (errors) in the training samples. Most existing methods neglect to handle the case with noisy samples. In this work, we introduce a new model of learning CP-nets from noisy samples. Based on chi-squared testing, we propose an algorithm to solve this problem in polynomial time. We prove that the obtained CP-net converges in mean to initial CP-net as sample size increases. The proposed method is verified on both simulated data and real data. Compared with the previous methods, our method achieves more accurate results on noisy sample sets. Crown Copyright (C) 2012 Published by Elsevier B.V. All rights reserved.