NationMaster - Encyclopedia: Latent semantic analysis

Latent semantic analysis (LSA) is a technique in natural language processing, in particular in vectorial semantics, of analyzing relationships between a set of documents and the terms they contain by producing a set of concepts related to the documents and terms. Natural language processing (NLP) is a subfield of artificial intelligence and linguistics. ... The vector space model (VSM) is an algebraic model used for information filtering and information retrieval. ...

LSA was patented in 1988 [1] by Scott Deerwester, Susan Dumais, George Furnas, Richard Harshman, Thomas Landauer, Karen Lochbaum and Lynn Streeter. In the context of its application to information retrieval, it is sometimes called latent semantic indexing (LSI). Year 1988 (MCMLXXXVIII) was a leap year starting on Friday (link displays 1988 Gregorian calendar). ... Scott Deerwester is one of the inventors of Latent semantic analysis. ... Susan Dumais is a Senior Researcher in the Adaptive Systems & Interaction Group of Microsoft Research. ... Prof. ... Dr Richard A. Harshman is a professor in the Department of Psychology of the University of Western Ontario. ... Dr. Thomas K. Landauer is a professor at the Department of Psychology of the University of Colorado. ... Information retrieval (IR) is the science of searching for information in documents, searching for documents themselves, searching for metadata which describe documents, or searching within databases, whether relational stand-alone databases or hypertext networked databases such as the Internet or World Wide Web or intranets, for text, sound, images or...

Occurrence matrix

LSA can use a term-document matrix which describes the occurrences of terms in documents; it is a sparse matrix whose rows correspond to terms and whose columns correspond to documents, typically stemmed words that appear in the documents. A typical example of the weighting of the elements of the matrix is tf-idf (term frequency–inverse document frequency): the element of the matrix is proportional to the number of times the terms appear in each document, where rare terms are upweighted to reflect their relative importance. Term-document matrices, or term-by-document matrices, are used in natural language processing programs. ... In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ... Terminology is the study of terms and their use â€” of words and compound words that are used in specific contexts. ... A stemmer is a program or algorithm which determines the morphological root of a given inflected (or, sometimes, derived) word form -- generally a written word form. ... The tf-idf weight (term frequency - inverse document frequency) is a weight often used in Information Retrieval. ...

This matrix is also common to standard semantic models, though it is not necessarily explicitly expressed as a matrix, since the mathematical properties of matrices are not always used.

LSA transforms the occurrence matrix into a relation between the terms and some concepts, and a relation between those concepts and the documents. Thus the terms and documents are now indirectly related through the concepts.

Applications

Synonymy and polysemy are fundamental problems in natural language processing: Clustering is the classification of objects into different groups, or more precisely, the partitioning of a data set into subsets (clusters), so that the data in each subset (ideally) share some common trait - often proximity according to some defined distance measure. ... Document classification/categorization is a problem in information science. ... In scientific classification, synonymy is the existence of multiple systematic names to label the same organism. ... Polysemy (from the Greek Ï€Î¿Î»Ï…ÏƒÎ·Î¼ÎµÎ¯Î± = multiple meaning) is the capacity for a sign to have multiple meanings. ... Information retrieval (IR) is the science of searching for information in documents, searching for documents themselves, searching for metadata which describe documents, or searching within databases, whether relational stand-alone databases or hypertext networked databases such as the Internet or World Wide Web or intranets, for text, sound, images or... Natural language processing (NLP) is a subfield of artificial intelligence and linguistics. ...

Rank lowering

After the construction of the occurrence matrix, LSA finds a low-rank approximation to the term-document matrix. There could be various reasons for these approximations: In linear algebra, the column rank (row rank respectively) of a matrix A with entries in some field is defined to be the maximal number of columns (rows respectively) of A which are linearly independent. ... Term-document matrices, or term-by-document matrices, are used in natural language processing programs. ...

The consequence of the rank lowering is that some dimensions are combined and depend on more than one term: In the mathematical subfield of numerical analysis a sparse matrix is a matrix populated primarily with zeros. ... In scientific classification, synonymy is the existence of multiple systematic names to label the same organism. ...

This mitigates synonymy, as the rank lowering is expected to merge the dimensions associated with terms that have similar meanings. It also mitigates polysemy, since components of polysemous words that point in the "right" direction are added to the components of words that share a similar meaning. Conversely, components that point in other directions tend to either simply cancel out, or, at worst, to be smaller than components in the directions corresponding to the intended sense.

Derivation

Let

X

be a matrix where element

(i, j)

describes the occurrence of term

i

in document

j

(this can be for example the frequency).

X

will look like this:

$begin{matrix} & textbf{d}_j & downarrow textbf{t}_i^T rightarrow & begin{bmatrix} x_{1,1} & dots & x_{1,n} vdots & ddots & vdots x_{m,1} & dots & x_{m,n} end{bmatrix} end{matrix}$

Now a row in this matrix will be a vector corresponding to a term, giving its relation to each document:

Likewise, a column in this matrix will be a vector corresponding to a document, giving its relation to each term:

Now the dot product $textbf{t}_i^T textbf{t}_p$ between two term vectors gives the correlation between the terms over the documents. The matrix product

X X T

contains all these dot products. Element

(i, p)

(which is equal to element

(p, i)

) contains the dot product $textbf{t}_i^T textbf{t}_p$ ( $= textbf{t}_p^T textbf{t}_i$ ). Likewise, the matrix

X T X

contains the dot products between all the document vectors, giving their correlation over the terms: $textbf{d}_j^T textbf{d}_q = textbf{d}_q^T textbf{d}_j$ . In mathematics, the dot product, also known as the scalar product, is a binary operation which takes two vectors over the real numbers R and returns a real-valued scalar quantity. ... Positive linear correlations between 1000 pairs of numbers. ... This article gives an overview of the various ways to multiply matrices. ...

Now assume that there exists a decomposition of

X

such that

U

and

V

are orthonormal matrices and

Σ

is a diagonal matrix. This is called a singular value decomposition(SVD): In linear algebra, an orthonormal matrix is a (not necessarily square) matrix with real or complex entries whose columns, treated as vectors in Rn or Cn, are orthonormal with respect to the standard inner product of Rn or Cn. ... In linear algebra, a diagonal matrix is a square matrix in which the entries outside the main diagonal are all zero. ... In linear algebra, the singular value decomposition (SVD) is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics. ...

$begin{matrix} X X^T &=& (U Sigma V^T) (U Sigma V^T)^T = (U Sigma V^T) (V^{T^T} Sigma^T U^T) = U Sigma V^T V Sigma^T U^T = U Sigma Sigma^T U^T X^T X &=& (U Sigma V^T)^T (U Sigma V^T) = (V^{T^T} Sigma^T U^T) (U Sigma V^T) = V Sigma U^T U Sigma V^T = V Sigma^T Sigma V^T end{matrix}$

Since

ΣΣ T

and

Σ T Σ

are diagonal we see that

U

must contain the eigenvectors of

X X T

, while

V

must be the eigenvectors of

X T X

. Both products have the same non-zero eigenvalues, given by the non-zero entries of

ΣΣ T

, or equally, by the non-zero entries of

Σ T Σ

. Now the decomposition looks like this: In linear algebra, the eigenvectors (from the German eigen meaning own) of a linear operator are non-zero vectors which, when operated on by the operator, result in a scalar multiple of themselves. ...

$begin{matrix} & X & & & U & & Sigma & & V^T & (textbf{d}_j) & & & & & & & (hat textbf{d}_j) & downarrow & & & & & & & downarrow (textbf{t}_i^T) rightarrow & begin{bmatrix} x_{1,1} & dots & x_{1,n} vdots & ddots & vdots x_{m,1} & dots & x_{m,n} end{bmatrix} & = & (hat textbf{t}_i^T) rightarrow & begin{bmatrix} begin{bmatrix} , , textbf{u}_1 , ,end{bmatrix} dots begin{bmatrix} , , textbf{u}_l , , end{bmatrix} end{bmatrix} & cdot & begin{bmatrix} sigma_1 & dots & 0 vdots & ddots & vdots 0 & dots & sigma_l end{bmatrix} & cdot & begin{bmatrix} begin{bmatrix} & & textbf{v}_1 & & end{bmatrix} vdots begin{bmatrix} & & textbf{v}_l & & end{bmatrix} end{bmatrix} end{matrix}$

The values $sigma_1, dots, sigma_l$ are called the singular values, and $u_1, dots, u_l$ and $v_1, dots, v_l$ the left and right singular vectors. Notice how the only part of

U

that contributes to $textbf{t}_i$ is the

i'th

row. Let this row vector be called $hat textrm{t}_i$ . Likewise, the only part of

V T

that contributes to $textbf{d}_j$ is the

j'th

column, $hat textrm{d}_j$ . These are not the eigenvectors, but depend on all the eigenvectors.

It turns out that when you select the

k

largest singular values, and their corresponding singular vectors from

U

and

V

, you get the rank

k

approximation to X with the smallest error (Frobenius norm). The amazing thing about this approximation, is that not only does it have a minimal error, but it translates the term and document vectors into a concept space. The vector $hat textbf{t}_i$ then has

k

entries, each giving the occurrence of term

i

in one of the

k

concepts. Likewise, the vector $hat textbf{d}_j$ gives the relation between document

j

and each concept. We write this approximation as In mathematics, the term matrix norm can have two meanings: A vector norm on matrices, i. ...

To do the latter, you must first translate your query into the concept space. It is then intuitive that you must use the same transformation that you use on your documents: Vector space model (or term vector model) is an algebraic model used for information filtering, information retrieval, indexing and relevancy rankings. ...

This means that if you have a query vector

q

, you must do the translation $hat textbf{q} = Sigma_k^{-1} U_k^T textbf{q}$ before you compare it with the document vectors in the concept space. You can do the same for pseudo term vectors:

$hat textbf{t}_i^T = textbf{t}_i^T V_k^{-T} Sigma_k^{-1} = textbf{t}_i^T V_k Sigma_k^{-1}$

Implementation

The SVD is typically computed using large matrix methods (for example, Lanczos methods) but may also be computed incrementally and with greatly reduced resources via a neural network-like approach which does not require the large, full-rank matrix to be held in memory [2]. In linear algebra, the singular value decomposition (SVD) is an important factorization of a rectangular real or complex matrix, with several applications in signal processing and statistics. ... The Lanczos algorithm is a popular method to find a zero vector in the process of the quadratic sieve. ... // See also Artificial neural network. ...

Limitations

The normal distribution, also called the Gaussian distribution, is an important family of continuous probability distributions, applicable in many fields. ... The ergodic hypothesis is a postulate of thermodynamics. ... In probability theory and statistics, the Poisson distribution is a discrete probability distribution that expresses the probability of a number of events occurring in a fixed period of time if these events occur with a known average rate, and are independent of the time since the last event. ... Probabilistic Latent Semantic Analysis is a novel statistical technique for the analysis of two{mode and co-occurrence data, which has applications in information retrieval and filtering, natural language processing, machine learning from text, and in related areas. ... In probability theory, the multinomial distribution is a generalization of the binomial distribution. ...

Encyclopedia > Latent semantic analysis

Contents

Occurrence matrix

Applications

Rank lowering

Derivation

Implementation

Limitations

See also

External links

References