×

Relational networks of conditional preferences. (English) Zbl 1260.68336

Summary: Much like relational probabilistic models, the need for relational preference models naturally arises in real-world applications involving multiple, heterogeneous, and richly interconnected objects. On the one hand, relational preferences should be represented into statements which are natural for human users to express. On the other hand, relational preference models should be endowed with a structure that supports tractable forms of reasoning and learning. Based on these criteria, this paper introduces the framework of relational conditional preference networks (RCP-nets), that maintains the spirit of the popular “CP-nets” by expressing relational preferences in a natural way using the ceteris paribus semantics. We show that acyclic RCP-nets support tractable inference for optimization and ranking tasks. In addition, we show that in the online learning model, tree-structured RCP-nets (with bipartite orderings) are efficiently learnable from both optimization tasks and ranking tasks, using linear loss functions. Our results are corroborated by experiments on a large-scale movie recommendation dataset.

MSC:

68T05 Learning and adaptive systems in artificial intelligence
68T35 Theory of languages and software systems (knowledge-based systems, expert systems, etc.) for artificial intelligence

Software:

CP-nets; AdaBoost.MH
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bacchus, F.; Grove, A., Graphical models for preference and utility, Edinburgh, Scotland, Berkeley
[2] Binshtok, M., Brafman, R. I., Domshlak, C., & Shimony, S. E. (2009). Generic preferences over subsets of structured objects. The Journal of Artificial Intelligence Research, 34, 133-164. · Zbl 1182.68221
[3] Boutilier, C.; Bacchus, F.; Brafman, R., UCP-networks: a directed graphical representation of conditional utilities, Seattle, Washington, USA
[4] Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H. H., & Poole, D. (2004a). Preference-based constrained optimization with cp-nets. Computational Intelligence, 20(2), 137-157. · doi:10.1111/j.0824-7935.2004.00234.x
[5] Boutilier, C., Brafman, R. I., Domshlak, C., Hoos, H. H., & Poole, D. (2004b). CP-nets: a tool for representing and reasoning with conditional Ceteris Paribus preference statements. The Journal of Artificial Intelligence Research, 21, 135-191. · Zbl 1080.68685
[6] Boutilier, C., Patrascu, R., Poupart, P., & Schuurmans, D. (2006). Constraint-based optimization and utility elicitation using the minimax decision criterion. Artificial Intelligence, 170(8-9), 686-713. · Zbl 1131.91317 · doi:10.1016/j.artint.2006.02.003
[7] Brafman, R., & Domshlak, C. (2008). Graphically structured value-function compilation. Artificial Intelligence, 172(2-3), 325-349. · Zbl 1182.68223 · doi:10.1016/j.artint.2007.07.002
[8] Brafman, R. I., Relational preference rules for control, Sydney, Australia, Berkeley
[9] Brafman, R. I., & Domshlak, C. (2009). Preference handling—an introductory tutorial. The AI Magazine, 30(1), 58-86.
[10] Brafman, R. I., Domshlak, C., & Shimony, S. E. (2006). On graphical modeling of preference and importance. The Journal of Artificial Intelligence Research, 25, 389-424. · Zbl 1182.68325
[11] Braziunas, D.; Boutilier, C., Local utility elicitation in Gai models, Edinburgh, Scotland, Berkley
[12] Cantador, I.; Brusilovsky, P.; Kuflik, T., 2nd workshop on information heterogeneity and fusion in recommender systems (HetRec’11), Chicago, IL, USA, New York
[13] Ceci, M.; Appice, A.; Loglisci, C.; Malerba, D., Preference learning for document image analysis, Barcelona, Spain
[14] Cesa-Bianchi, N., & Lugosi, G. (2006). Prediction, learning, and games. Cambridge: Cambridge University Press. · Zbl 1114.91001 · doi:10.1017/CBO9780511546921
[15] Cohen, W., Schapire, R., & Singer, Y. (1999). Learning to order things. The Journal of Artificial Intelligence Research, 10, 243-270. · Zbl 0915.68031
[16] Colbourn, C. J., Myrvold, W. J., & Neufeld, E. (1996). Two algorithms for unranking arborescences. Journal of Algorithms, 20(2), 268-281. · Zbl 0843.68087 · doi:10.1006/jagm.1996.0014
[17] Crammer, K.; Singer, Y., Pranking with ranking, Vancouver, British Columbia, Canada, Cambridge
[18] Dechter, R. (2003). Constraint processing. San Mateo: Morgan Kaufmann. · Zbl 1057.68114
[19] Dimopoulos, Y.; Michael, L.; Athienitou, F.; Boutilier, C. (ed.), Ceteris paribus preference elicitation with predictive guarantees, Pasadena, California, USA
[20] Domshlak, C.; Joachims, T., Unstructuring user preferences: efficient non-parametric utility revelation, Edinburgh, Scotland, Berkeley
[21] Engel, Y., & Wellman, M. P. (2008). CUI networks: a graphical representation for conditional utility independence. The Journal of Artificial Intelligence Research, 31, 83-112. · Zbl 1177.90050
[22] Fishburn, P. (1967). Independence and additivity in multivariate unidimensional expected utility theory. International Economic Review, 8, 335-342. · Zbl 0153.49302 · doi:10.2307/2525541
[23] Freund, Y., & Schapire, R. E. (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences, 55(1), 119-139. · Zbl 0880.68103 · doi:10.1006/jcss.1997.1504
[24] Freund, Y., Iyer, R., Schapire, R., & Singer, Y. (2003). An efficient boosting algorithm for combining preferences. Journal of Machine Learning Research, 4, 933-969. · Zbl 1098.68652
[25] Fürnkranz, J., & Hüllermeier, E. (2011). Preference learning. Berlin: Springer. · Zbl 1201.68006 · doi:10.1007/978-3-642-14125-6
[26] Getoor, L., Friedman, N., Koller, D., & Taskar, B. (2002). Learning probabilistic models of link structure. Journal of Machine Learning Research, 3, 679-707. · Zbl 1112.68441
[27] Golbeck, J., Generating predictive movie recommendations from trust in social networks, Pisa, Italy, Berlin
[28] Goldsmith, J., Lang, J., Truszczynski, M., & Wilson, N. (2008). The computational complexity of dominance and consistency in CP-nets. The Journal of Artificial Intelligence Research, 33, 403-432. · Zbl 1182.68089
[29] Gonzales, C.; Perny, P., GAI networks for utility elicitation, Whistler, Canada, Menlo Park
[30] Gonzales, C., Perny, P., & Dubus, J. Ph. (2011). Decision making with multiple objectives using GAI networks. Artificial Intelligence, 175(7), 1153-1179. · Zbl 1231.91070 · doi:10.1016/j.artint.2010.11.020
[31] Harrington, E. F., Online ranking/collaborative filtering using the Perceptron algorithm, Washington, DC, USA, Menlo Park
[32] Herbrich, R.; Graepel, T.; Obermayer, K., Large margin rank boundaries for ordinal regression, 115-132 (2000), Cambridge
[33] Jannach, D., Zanker, M., Felfernig, A., & Friedrich, G. (2010). Recommender systems: an introduction. Cambridge: Cambridge University Press.
[34] Junker, U., Configuration, 837-873 (2006), Amsterdam · doi:10.1016/S1574-6526(06)80028-3
[35] Keeney, R. L., & Raiffa, H. (1976). Decisions with multiple objectives: preferences and value tradeoffs. New York: Wiley. · Zbl 0488.90001
[36] Kendall, M. G. (1938). A new measure of rank correlation. Biometrika, 30, 81-93. · Zbl 0019.13001
[37] Koller, D., & Friedman, N. (2009). Probabilistic graphical models. Cambridge: MIT Press. · Zbl 1183.68483
[38] Koolen, W. M.; Warmuth, M. K.; Kivinen, J., Hedging structured concepts, Haifa, Israel
[39] Koriche, F., & Zanuttini, B. (2010). Learning conditional preference networks. Artificial Intelligence, 174(11), 685-703. · Zbl 1205.68291 · doi:10.1016/j.artint.2010.04.019
[40] Kulkarni, V. G. (1990). Generating random combinatorial objects. Journal of Algorithms, 11(2), 185-207. · Zbl 0709.68038 · doi:10.1016/0196-6774(90)90002-V
[41] Melville, P.; Mooney, R. J.; Nagarajan, R., Content-boosted collaborative filtering for improved recommendations, Edmonton, Alberta, Canada, Menlo Park
[42] Newton, J.; Greiner, R., Hierarchical probabilistic relational models for collaborative filtering, Banff, Alberta, Canada
[43] Propp, J. G., & Wilson, D. B. (1998). How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph. Journal of Algorithms, 27(2), 170-217. · Zbl 0919.68092 · doi:10.1006/jagm.1997.0917
[44] Sinha, R. R.; Swearingen, K., Comparing recommendations made by online systems and friends, Dublin, Ireland
[45] Tutte, W. T. (1984). Graph theory. Cambridge. · Zbl 0554.05001
[46] Yaman, F., Walsh, T. J., Littman, M. L., & des Jardins, M. (2011). Democratic approximation of lexicographic preference models. Artificial Intelligence, 175, 1290-1307. · Zbl 1231.91087 · doi:10.1016/j.artint.2010.11.012
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.