Why spectral retrieval works

ABSTRACT

We argue that the ability to identify pairs of related terms is at the heart of what makes spectral retrieval work in practice. Schemes such as latent semantic indexing (LSI) and its descendants have this ability in the sense that they can be viewed as computing a matrix of term-term relatedness scores which is then used to expand the given documents (not the queries). For almost all existing spectral retrieval schemes, this matrix of relatedness scores depends on a fixed low-dimensional subspace of the original term space. We instead vary the dimension and study for each term pair the resultin curve of relatedness scores. We find that it is actually the shape of this curve which is indicative for the term-pair relatedness, and not any of the individual relatedness scores on the curve. We derive two simple, parameterless algorithms that detect this shape and that consistently outperform previous methods on a number of test collections. Our curves also shed light on the effectiveness of three fundamental types of variations of the basic LSI scheme.

REFERENCES

• 1: Rie Kubota Ando, Latent semantic space: iterative scaling improves precision of inter-document similarity measurement, Proceedings of the 23rd annual international ACM SIGIR conference on Research and development in information retrieval, p.216-223, July 24-28, 2000, Athens, Greece [doi>10.1145/345508.345579]
• 2: Rie Kubota Ando , Lillian Lee, Iterative residual rescaling, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.154-162, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383981]
• 3: 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]
• 4: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 5: Chris H. Q. Ding, A similarity-based probability model for latent semantic indexing, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.58-65, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312652]
• 6: Georges Dupret, Latent concepts and the number orthogonal factors in latent semantic analysis, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860477]
• 7: G. Dupret. Latent semantic indexing with a variable number of orthogonal factors. In Proceedings RIAO'04, 2004.
• 8: Miles James Efron , Gregory B. Newby, Eigenvalue-based estimators for optimal dimensionality reduction in information retrieval, 2003
• 9: G. H. Golub and C. F. Van Loan. Matrix Computations. Johns Hopkins, third edition, 1996.
• 10: William Hersh , Chris Buckley , T. J. Leone , David Hickam, OHSUMED: an interactive retrieval evaluation and new large test collection for research, Proceedings of the 17th annual international ACM SIGIR conference on Research and development in information retrieval, p.192-201, July 03-06, 1994, Dublin, Ireland
• 11: Thomas Hofmann, Unsupervised learning by probabilistic latent semantic analysis, Machine Learning, v.42 n.1/2, p.177-196, Jan. 2001 [doi>10.1023/A:1007617005950]
• 12: Parry Husbands , Horst Simon , Chris H. Q. Ding, On the use of the singular value decomposition for text retrieval, Computational information retrieval, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
• 13: S. D. Kamvar, D. Klein, and C. D. Manning. Spectral learning. In Proceedings IJCAI'03, 2003.
• 14: A. Kontostathis and W. M. Pottenger. Detecting patterns in the LSI term-term matrix. In Proceedings ICDM'02 Workshop on Foundations of Data Mining and Discovery, 2002.
• 15: D. Lewis. Reuters-21578 text categorization test collection, 1997.
• 16: A. Ng, M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm. In Proceedings NIPS'01, 2001.
• 17: 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]
• 18: G. Salton , A. Wong , C. S. Yang, A vector space model for automatic indexing, Communications of the ACM, v.18 n.11, p.613-620, Nov. 1975 [doi>10.1145/361219.361220]
• 19: Chunqiang Tang , Sandhya Dwarkadas , Zhichen Xu, On scaling latent semantic indexing for large peer-to-peer systems, Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval, July 25-29, 2004, Sheffield, United Kingdom [doi>10.1145/1008992.1009014]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Clustering

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Retrieval models

General Terms:
Algorithms, Experimentation, Performance, Theory

Keywords:
curve of relatedness scores, document expansion, latent semantic indexing, spectral analysis