Tell me who I am: an interactive recommendation system

ABSTRACT

We consider a model of recommendation systems, where each member from a given set of players has a binary preference to each element in a given set of objects: intuitively, each player either likes or dislikes each object. However, the players do not know their preferences. To find his preference of an object, a player may probe it, but each probe incurs unit cost. The goal of the players is to learn their complete preference vector (approximately) while incurring minimal cost. This is possible if many players have similar preference vectors: such a set of players with similar "taste" may split the cost of probing all objects among them, and share the results of their probes by posting them on a public billboard. The problem is that players do not know a priori whose taste is close to theirs. In this paper we present a distributed randomized peer-to-peer algorithm in which each player outputs a vector which is close to the best possible approximation of the player's real preference vector after a polylogarithmic number of rounds. The algorithm works under adversarial preferences. Previous algorithms either made severely limiting assumptions on the structure of the preference vectors, or had polynomial overhead.

REFERENCES

• 1: Ittai Abraham , Yair Bartal , T-H. Hubert Chan , Kedar Dhamdhere Dhamdhere , Anupam Gupta , Jon Kleinberg , Ofer Neiman , Aleksandrs Slivkins, Metric Embeddings with Relaxed Guarantees, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.83-100, October 23-25, 2005 [doi>10.1109/SFCS.2005.51]
• 2: N. Alon and J. H. Spencer. The Probabilistic Method. Wiley, second edition, 2000.
• 3: Baruch Awerbuch , Yossi Azar , Zvi Lotker , Boaz Patt-Shamir , Mark R. Tuttle, Collaborate with strangers to find own preferences, Proceedings of the seventeenth annual ACM symposium on Parallelism in algorithms and architectures, July 18-20, 2005, Las Vegas, Nevada, USA [doi>10.1145/1073970.1074014]
• 4: Baruch Awerbuch , Boaz Patt-Shamir , David Peleg , Mark Tuttle, Improved recommendation systems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 5: Yossi Azar , Amos Fiat , Anna Karlin , Frank McSherry , Jared Saia, Spectral analysis of data, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.619-626, July 2001, Hersonissos, Greece [doi>10.1145/380752.380859]
• 6: Petros Drineas , Iordanis Kerenidis , Prabhakar Raghavan, Competitive recommendation systems, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509922]
• 7: Ken Goldberg , Theresa Roeder , Dhruv Gupta , Chris Perkins, Eigentaste: A Constant Time Collaborative Filtering Algorithm, Information Retrieval, v.4 n.2, p.133-151, July 2001 [doi>10.1023/A:1011419012209]
• 8: Sally A. Goldman , Ronald L. Rivest , Robert E. Schapire, Learning binary relations and total orders, SIAM Journal on Computing, v.22 n.5, p.1006-1034, Oct. 1993 [doi>10.1137/0222062]
• 9: Sally A. Goldman , Manfred K. Warmuth, Learning Binary Relations Using Weighted Majority Voting, Machine Learning, v.20 n.3, p.245-271, Sept. 1995 [doi>10.1023/A:1022675327341]
• 10: J. Hu and M. P. Wellman. Self-fulfilling bias in multiagent learning. In V. Lesser, editor, Proceedings of the First International Conference on Multi--Agent Systems. MIT Press, 1995.
• 11: Jon Kleinberg , Mark Sandler, Convergent algorithms for collaborative filtering, Proceedings of the 4th ACM conference on Electronic commerce, p.1-10, June 09-12, 2003, San Diego, CA, USA [doi>10.1145/779928.779929]
• 12: Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins, Recommendation Systems: A Probabilistic Analysis, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.664, November 08-11, 1998
• 13: M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In Proc. 11th Int. Conference on Machine Learning (ML-94). Morgan Kaufmann.
• 14: Christos H. Papadimitriou , Hisao Tamaki , Prabhakar Raghavan , Santosh Vempala, Latent semantic indexing: a probabilistic analysis, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.159-168, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275505]
• 15: Badrul Sarwar , George Karypis , Joseph Konstan , John Riedl, Analysis of recommendation algorithms for e-commerce, Proceedings of the 2nd ACM conference on Electronic commerce, p.158-167, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352887]
• 16: G. Wei. Learning to coordinate actions in multi-agent systems. In R. Bajcsy, editor, Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence (IJCAI-93). MIT Press, 1993.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

General Terms:
Algorithms, Theory

Keywords:
billboard, collaborative filtering, electronic commerce, probes, randomized algorithms, recommendation systems