Using mixture models for collaborative filtering. (English) Zbl 1129.68327
Summary: A collaborative filtering system at an e-commerce site or similar service uses data about aggregate user behavior to make recommendations tailored to specific user interests. We develop recommendation algorithms with provable performance guarantees in a probabilistic mixture model for collaborative filtering proposed by Hofmann and Puzicha. We identify certain novel parameters of mixture models that are closely connected with the best achievable performance of a recommendation algorithm; we show that for any system in which these parameters are bounded, it is possible to give recommendations whose quality converges to optimal as the amount of data grows.
All our bounds depend on a new measure of independence that can be viewed as an \(L_{1}\)-analogue of the smallest singular value of a matrix. Using this, we introduce a technique based on generalized pseudoinverse matrices and linear programming for handling sets of high-dimensional vectors. We also show that standard approaches based on \(L_{2}\) spectral methods are not strong enough to yield comparable results, thereby suggesting some inherent limitations of spectral analysis.
All our bounds depend on a new measure of independence that can be viewed as an \(L_{1}\)-analogue of the smallest singular value of a matrix. Using this, we introduce a technique based on generalized pseudoinverse matrices and linear programming for handling sets of high-dimensional vectors. We also show that standard approaches based on \(L_{2}\) spectral methods are not strong enough to yield comparable results, thereby suggesting some inherent limitations of spectral analysis.
MSC:
| 68M10 | Network design and communication in computer systems |
| 68T05 | Learning and adaptive systems in artificial intelligence |
| 90C05 | Linear programming |
Keywords:
mixture models; latent class models; collaborative filtering; clustering; text classification; singular value decomposition; linear programmingReferences:
| [1] | Broder, A.; Upfal, E., Existence and construction of edge disjoint paths on expander graphs, SIAM J. Comput., 23, 976-989 (1994) · Zbl 0808.05087 |
| [2] | Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia, Spectral analysis of data, in: Proc. of ACM Symposium on Theory of Computing, 2001; Y. Azar, A. Fiat, A. Karlin, F. McSherry, J. Saia, Spectral analysis of data, in: Proc. of ACM Symposium on Theory of Computing, 2001 · Zbl 1323.68426 |
| [3] | J. Breese, D. Heckerman, C. Kadie, Empirical analysis of predictive algorithms for collaborative filtering, in: Proc. of ACM Symposium on Theory of Computing, 1998; J. Breese, D. Heckerman, C. Kadie, Empirical analysis of predictive algorithms for collaborative filtering, in: Proc. of ACM Symposium on Theory of Computing, 1998 |
| [4] | P. Drineas, I. Kerendis, P. Raghavan, Competitive recommender systems, in: Proc. of ACM Symposium on Theory of Computing, 2002; P. Drineas, I. Kerendis, P. Raghavan, Competitive recommender systems, in: Proc. of ACM Symposium on Theory of Computing, 2002 |
| [5] | Golub, G. H.; Loan, C. V., Matrix Computations (1996), Johns Hopkins University Press · Zbl 0865.65009 |
| [6] | Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 301, 13-30 (1963) · Zbl 0127.10602 |
| [7] | T. Hofmann, J. Puzicha, Latent class models for collaborative filtering, in: Proc. of International Joint Conference on Artificial Intelligence, 1999; T. Hofmann, J. Puzicha, Latent class models for collaborative filtering, in: Proc. of International Joint Conference on Artificial Intelligence, 1999 |
| [8] | J. Kleinberg, M. Sandler, Convergent algorithms for collaborative filtering, in: Proc. of ACM Conference on Electronic Commerce, 2003; J. Kleinberg, M. Sandler, Convergent algorithms for collaborative filtering, in: Proc. of ACM Conference on Electronic Commerce, 2003 · Zbl 1192.68685 |
| [9] | S. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Recommendation systems: A probabilistic analysis, in: Proc. of IEEE Symposium on Foundations of Computer Science, 1998; S. Kumar, P. Raghavan, S. Rajagopalan, A. Tomkins, Recommendation systems: A probabilistic analysis, in: Proc. of IEEE Symposium on Foundations of Computer Science, 1998 · Zbl 0984.68152 |
| [10] | G. Linden, J.Y.B. Smith, Amazon.com recommendations: Item-to-item collaborative filtering, in: IEEE Internet Computing, January/February 2003; G. Linden, J.Y.B. Smith, Amazon.com recommendations: Item-to-item collaborative filtering, in: IEEE Internet Computing, January/February 2003 |
| [11] | McLachlan, G.; Peel, D., Finite Mixture Models (2000), Wiley-Interscience · Zbl 0963.62061 |
| [12] | M. O’Connor, D. Cosley, J.A. Konstan, J. Riedl, Polylens: A recommender system for groups of users, in: ECSCW, 2001, pp. 199-218; M. O’Connor, D. Cosley, J.A. Konstan, J. Riedl, Polylens: A recommender system for groups of users, in: ECSCW, 2001, pp. 199-218 |
| [13] | Resnick, P.; Varian, H., Recommender systems, introduction to a special issue on collaborative filtering, Commun. ACM, 40 (1997) |
| [14] | M. Sandler, On the use of linear programming for unsupervised text classification, in: Proc. of ACM-SIGKDD Conference on Knowledge Discovery and Data Mining, 2005; M. Sandler, On the use of linear programming for unsupervised text classification, in: Proc. of ACM-SIGKDD Conference on Knowledge Discovery and Data Mining, 2005 |
| [15] | B.M. Sarwar, G. Karypis, J.A. Konstan, J. Riedl, Analysis of recommender algorithms for e-commerce, in: Proc. of ACM Conference on Electronic Commerce, 2000; B.M. Sarwar, G. Karypis, J.A. Konstan, J. Riedl, Analysis of recommender algorithms for e-commerce, in: Proc. of ACM Conference on Electronic Commerce, 2000 |
| [16] | B.M. Sarwar, G. Karypis, J.A. Konstan, J. Riedl, Item-based collaborative filtering recommendation algorithms, in: Proc. of International World Wide Web Conference, May 2001; B.M. Sarwar, G. Karypis, J.A. Konstan, J. Riedl, Item-based collaborative filtering recommendation algorithms, in: Proc. of International World Wide Web Conference, May 2001 |
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.
