LATENT SEMANTIC INDEXING
BY
SINGULAR VALUE DECOMPOSITION
Problems in Lexical Matching
• Ambiguity and association in natural language
• Synonymy
• Different terms may have an identical or a similar
meaning
-decrease recall.
• Polysemy
• Words often have a multitude of meanings and different
types of usage
- retrieval of irrelevant documents
- poor precision
• Noise
- Boolean search on specific words
- Retrieval of contently unrelated documents
Motivation for LSI
• LSI deals with Polysemy and Synonymy problems by
identifying the statistical association of terms.
• To find and fit a useful model of the relationships between
terms and documents.
• To find out what terms "really" are implied by a query .
• LSI allow the user to search for concepts rather than specific
words.
• LSI can retrieve documents related to a user's query even
when the query and the documents do not share any common
terms.
Some Applications
• Information Retrieval
• Information Filtering
• Relevance Feedback
• Cross-language retrieval
How LSI Works?
• Assumes that there is some underlying latent sematic
structure in the data that is hidden by the randomness in the
word choice present in the query.
• uses multidimensional vector space to place all documents
and terms.
• Each dimension in that space corresponds to a concept
existing in the collection.
• The underlying topics of the document is encoded in a vector.
• Common related terms in a document and query will pull
document and query vector close to each other.
SVD
• The key to working with SVD of any rectangular
matrix C is to consider CCT and CTC.
• The columns of U, that is t by t, are eigenvectors
of CCT,
• The columns of V, that is d by d, are
eigenvectors of CTC
• The singular values on the diagonal of S, that is t
by d, are the positive square roots of the
nonzero eigenvalues of both CCT and CTC.
SVD
• Eigenvalue-eigenvector factorization
• C = USVT
- UUT=I
-VVT=I
-S singular values
Introduction to Information
Retrieval
LSA Example
• A simple example term-document matrix (binary)
37
Introduction to Information
Retrieval
LSA Example
• Example of C = USVT
• The matrix U
38
LSA Example
• Example of C = US VT :
• The matrix S
39
LSA Example
• Example of C = USVT:
• The matrix VT
40
LSA Example: Reducing the
dimension by truncation
41
Original matrix C vs. reduced C2 =
UΣV T
42
Why the reduced dimension
matrix is better
• Similarity of d2 and d3 in the original space: 0.
• Similarity of d2 and d3 in the reduced space: 0.52 ∗ 0.28 +
0.36 ∗ 0.16 + 0.72 ∗ 0.36 + 0.12 ∗ 0.20 + −0.39 ∗ −0.08 ≈
0.52
43
LSI-Procedure
• Obtain term-document matrix.
• Compute the SVD.
• Truncate-SVD into reduced-k LSI space.
-k-dimensional semantic structure
-similarity on reduced-space:
-term-term
-term-document
-document-document
Drawback!
• The complexity of the LSI model obtained from truncated SVD is
costly = O(m2 n), m is the number of terms and n is the no: of
documents
• Another drawback is that the concept space is not interpretable as
its description consists of all numbers with little semantic meaning.
• Determining the optimal number of dimensions k of the concept
space is also a major difficulty
• In practice, the value of k needs to be determined based on the
specific document collection via trial and error, which is a very time
consuming process due to the high time complexity of the SVD.
• Due to the efficiency problem, latent semantic indexing is probably
not used in Web search yet.
• Current search algorithms are still mainly based on the vector space
model and term matching.
Web search
• A search engine starts with the crawling of pages on the Web.
• The crawled pages are then parsed, indexed, and stored.
• At the query time, the index is used for efficient retrieval
• Parsing: A parser is used to parse the input HTML page, which
produces a stream of tokens or terms to be indexed. The parser can
be constructed using a lexical analyzer generator such as YACC and
Flex (Some pre-processing tasks may also be performed before or
after parsing.
• Indexing: This step produces an inverted index, which can be done
using any of the methods discussed. For retrieval efficiency, a search
engine may build multiple inverted indices. For example, since the
titles and anchor texts are often very accurate descriptions of the
pages, a small inverted index may be constructed based on the
terms appeared in them alone. A full index may be built on anchor
texts.
Searching and Ranking
• Given a user query, searching involves the following steps:
1. pre-processing the query terms using some of the methods
stopword removal and stemming;
2. finding pages that contain all (or most of) the query terms in
the inverted index
3. ranking the pages and returning them to the user.
Ranking process
• Similarity based – Cosine similarity
• number of votes or links pointing to a page is called called in-
links
• Hyperlink based - It makes use of the link structure of Web
pages to compute a quality or reputation score for each page
• In links
• Authoritative information
• Web page can be evaluated based on both its content
factors and its reputation.