Monthly Archive for October, 2005

S. Deerwester, S. T. Doumas, T. K. Landauer, G. W. Furnas, and R. Harshman. Indexing by latent semantic analysis. Journal of the Society for Information Science, 41(6):391–407, 1990. [url]

—————————-

This is the first technical LSI paper. It offers a good background on the previous theory and on the technical choices behind the algorithm.

Essentially, the authors developed the technique to overcome the deficiency of current information retrieval methods, that is the words searchers often use are not the same as those by which the information they seek has been indexed. The two side of the issue they describe are the synonymy and the polysemy. The former is the fact that there are many ways to refer to the same concept. The latter is the fact that most words have more than one distinct meaning.

The criteria they used to distinguish between different models are: adjustable representational richness (hierarchical clustering is too restrictive; they looked for models whose power could be varied); explicit representation of both terms and documents (as in two-mode factor analysis or tree unfolding); computational tractability for large datasets.

The latent semantic structure analysis starts with a matrix of terms by documents. Then this is analyzed by Singular Value Decomposition (SVD), to derive the particular latent semantic structure model. The process divide the original matrix into three representative matrix, which contains “eigenvectors” and “eigenvalues”, and which show a breakdown of the original data into linearly indipendent components or factors.

Three particular comparisons were of interest for the authors: the comparisons of two terms; two comparisons of two documents; and a comparison of a term and a document.

Tags: information retrieval, Latent Semantic Analysis, Singular Value Decomposition

M. Ceglowski, A. Coburn, and J. Cuadrado. Semantic search of unstructured data using contextual network graphs. Preliminary white paper, National Institute for Technology and Liberal Education, Middlebury College, Middlebury, Vermont, 05753 USA, 2003. [url]

————————————

This paper describe the Contextual Network Graph, a technique that should solve some of the pitfalls of the latent semantic indexing, like the poor scalability of the singular value decomposition algorithm.

The authors offer an alternative interpretation of the term-document matrix (TDM), which is essentially a lookup table of term frequency data for the entire document collection. In LSI this is interpreted as a high-dimensional vector space. Alternatively, this can be seen as a bipartite graph of term and document nodes where each non-zero value in the TDM corresponds to an edge connecting a term node to a document node. In this way, every term is connected to all of the documents in which the term appears, and every document has a link to each term contained in the document. The authors call this a contextual network graph.

This construct correspond to the intuition that documents that share many rare tems are likely to be semantically related.

Their idea is to use this representation to search a document collection energizing a query node and allowing the energy to propagate to other nodes along the edges of the graph based on a set of simple rules.

Their results show comparable results to an LSI search engine. In a 1981 dissertation at the University of Illinois, Scott Preece describes an almost identical technique under the name spreading activation search.

Tags: Exploratory Data Analysis, information retrieval, Latent Semantic Analysis, text data mining