Variable latent semantic indexing

ABSTRACT

Latent Semantic Indexing is a classical method to produce optimal low-rank approximations of a term-document matrix. However, in the context of a particular query distribution, the approximation thus produced need not be optimal. We propose VLSI, a new query-dependent (or "variable") low-rank approximation that minimizes approximation error for any specified query distribution. With this tool, it is possible to tailor the LSI technique to particular settings, often resulting in vastly improved approximations at much lower dimensionality. We validate this method via a series of experiments on classical corpora, showing that VLSI typically performs similarly to LSI with an order of magnitude fewer dimensions.

REFERENCES

• 1: R. Baeza-Yates. Web usage mining in search engines. In A. Scime, editor, Web Mining: Applications and Techniques, chapter XIV. Idea Group, 2004.
• 2: Michael Berry , Theresa Do , Gavin O''Brien , Vijay K %A , Sowmini Varadhan, SVDPACKC (Version 1.0) User''s Guide, University of Tennessee, Knoxville, TN, 1993
• 3: S. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the Society for Information Science, 41(6):391--407, 1990.
• 4: S. T. Dumais. LSI meets TREC: A status report. In The First Text REtrieval Conference (TREC1), National Institute of Standards and Technology, pages 137--152, 1992.
• 5: S. T. Dumais. Latent semantic indexing (LSI) and TREC-2. In The Second Text REtrieval Conference (TREC2), National Institute of Standards and Technology, pages 105--116, 1993.
• 6: S. T. Dumais. Latent semantic indexing (LSI): TREC-3 report. In The Third Text REtrieval Conference (TREC3), National Institute of Standards and Technology, pages 105--115, 1994.
• 7: S. T. Dumais , G. W. Furnas , T. K. Landauer , S. Deerwester , R. Harshman, Using latent semantic analysis to improve access to textual information, Proceedings of the SIGCHI conference on Human factors in computing systems, p.281-285, May 15-19, 1988, Washington, D.C., United States [doi>10.1145/57167.57214]
• 8: C. Eckart and G. Young. The approximation of a matrix by another of lower rank. Psychometrika, 1:211--218, 1936.
• 9: G. H. Golub and C. F. V. Loan. Matrix Computation. John Hopkins University Press, 1991. Second Edition.
• 10: T. Hoffmann. Matrix decomposition techniques in machine learning and information retrieval. http://www.mpi-sb.mpg.de/~adfocs/adfocs04.slides-hofmann.pdf, 2004.
• 11: Thomas Hofmann, Probabilistic latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.50-57, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312649]
• 12: Thomas Hofmann, Latent semantic models for collaborative filtering, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.89-115, January 2004 [doi>10.1145/963770.963774]
• 13: I. T. Jolliffe. Principal Component Analysis. Springer, 2002.
• 14: D. D. Lee and H. S. Seung. Learning the parts of objects by non-negative matrix factorization. Nature, 401:788--791, 1999.
• 15: Ronny Lempel , Shlomo Moran, Predictive caching and prefetching of query results in search engines, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775156]
• 16: D. D. Lewis. http://www.daviddlewis.com/resources/testcollections/reuters21578/.
• 17: Sebastian Mika , Bernhard Schölkopf , Alex Smola , Klaus-Robert Müller , Matthias Scholz , Gunnar Rätsch, Kernel PCA and de-noising in feature spaces, Proceedings of the 1998 conference on Advances in neural information processing systems II, p.536-542, July 1999
• 18: B. Moghaddam and A. Pentland. Face recognition using view-based and modular eigenspaces. In Automatic Systems for the Identification and Inspection of Humans, SPIE,, volume 2277, pages 12--21, 1994.
• 19: S. E. Robertson and S. Walker. Okapi/Keenbow at TREC-8. In The Eighth Text REtrieval Conference (TREC8), National Institute of Standards and Technology, 1999.
• 20: Paricia Correia Saraiva , Edleno Silva de Moura , Novio Ziviani , Wagner Meira , Rodrigo Fonseca , Berthier Riberio-Neto, Rank-preserving two-level caching for scalable search engines, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.51-58, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383959]
• 21: A. Singhal. Modern information retrieval: A brief overview. IEEE Data Engineering Bulletin, 24(4):35--43, 2001.
• 22: P. K. C. Singitham, M. S. Mahabhashyam, and P. Raghavan. Efficiency-quality tradeoffs for vector score aggregation. In Proceedings of the 30th International Conference on Very Large Data Bases (VLDB), pages 624--635, 2004.
• 23: N. Srebro and T. Jaakkola. Weighted low-rank approximations. In Proceedings of the 20th International Conference on Machine Learning (ICML), pages 720--727, 2003.
• 24: M. Tipping and C. Bishop. Probabilistic principal component analysis. Journal of the Royal Statistical Society, Series B, 61(3):611--622, 1999.
• 25: Jieping Ye, Generalized low rank approximations of matrices, Proceedings of the twenty-first international conference on Machine learning, p.112, July 04-08, 2004, Banff, Alberta, Canada [doi>10.1145/1015330.1015347]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Singular value decomposition

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Sparse, structured, and very large systems (direct and iterative methods)

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

General Terms:
Algorithms, Experimentation, Measurement, Theory

Keywords:
LSI, SVD, VLSI, linear algebra, matrix approximation