Question? Leave a message!




Latent Semantic Indexing

Latent Semantic Indexing
RyanCanon Profile Pic
RyanCanon,United Arab Emirates,Teacher
Published Date:20-07-2017
Website URL
Comment
Introduction to Information Retrieval Introduction to Information Retrieval Latent Semantic IndexingIntroduction to Information Retrieval Ch. 18 Today’s topic Latent Semantic Indexing  Term-document matrices are very large  But the number of topics that people talk about is small (in some sense)  Clothes, movies, politics, …  Can we represent the term-document space by a lower dimensional latent space?Introduction to Information Retrieval Linear Algebra BackgroundIntroduction to Information Retrieval Sec. 18.1 Eigenvalues & Eigenvectors  Eigenvectors (for a square mm matrix S) Example (right) eigenvector eigenvalue  How many eigenvalues are there at most? only has a non-zero solution if This is a mth order equation in λ which can have at most m distinct solutions (roots of the characteristic polynomial) – can be complex even though S is real.Introduction to Information Retrieval Sec. 18.1 Matrix-vector multiplication has eigenvalues 30, 20, 1 with corresponding eigenvectors On each eigenvector, S acts as a multiple of the identity matrix: but as a different multiple on each. Any vector (say x= ) can be viewed as a combination of the eigenvectors: x = 2v + 4v + 6v 1 2 3Introduction to Information Retrieval Sec. 18.1 Matrix-vector multiplication  Thus a matrix-vector multiplication such as Sx (S, x as in the previous slide) can be rewritten in terms of the eigenvalues/vectors:  Even though x is an arbitrary vector, the action of S on x is determined by the eigenvalues/vectors.Introduction to Information Retrieval Sec. 18.1 Matrix-vector multiplication  Suggestion: the effect of ―small‖ eigenvalues is small.  If we ignored the smallest eigenvalue (1), then instead of we would get  These vectors are similar (in cosine similarity, etc.)Introduction to Information Retrieval Sec. 18.1 Eigenvalues & Eigenvectors For symmetric matrices, eigenvectors for distinct eigenvalues are orthogonal All eigenvalues of a real symmetric matrix are real. All eigenvalues of a positive semidefinite matrix are non-negativeIntroduction to Information Retrieval Sec. 18.1 Example  Let Real, symmetric.  Then  The eigenvalues are 1 and 3 (nonnegative, real).  The eigenvectors are orthogonal (and real): Plug in these values and solve for eigenvectors.Introduction to Information Retrieval Sec. 18.1 Eigen/diagonal Decomposition  Let be a square matrix with m linearly independent eigenvectors (a ―non- defective‖ matrix) Unique diagonal for  Theorem: Exists an eigen decomposition distinct eigen- values  (cf. matrix diagonalization theorem)  Columns of U are the eigenvectors of S  Diagonal elements of are eigenvalues of Introduction to Information Retrieval Sec. 18.1 Diagonal decomposition: why/how Let U have the eigenvectors as columns: Then, SU can be written –1 Thus SU=U, or U SU= –1 And S=UU .Introduction to Information Retrieval Sec. 18.1 Diagonal decomposition - example Recall The eigenvectors and form Recall Inverting, we have –1 UU =1. –1 Then, S=UU =Introduction to Information Retrieval Sec. 18.1 Example continued –1 Let’s divide U (and multiply U ) by Then, S= -1 T Q (Q = Q ) Why? Stay tuned …Introduction to Information Retrieval Sec. 18.1 Symmetric Eigen Decomposition  If is a symmetric matrix:  Theorem: There exists a (unique) eigen decomposition  where Q is orthogonal: -1 T  Q = Q  Columns of Q are normalized eigenvectors  Columns are orthogonal.  (everything is real)Introduction to Information Retrieval Sec. 18.1 Exercise  Examine the symmetric eigen decomposition, if any, for each of the following matrices:Introduction to Information Retrieval Time out  I came to this class to learn about text retrieval and mining, not to have my linear algebra past dredged up again …  But if you want to dredge, Strang’s Applied Mathematics is a good place to start.  What do these matrices have to do with text?  Recall M  N term-document matrices …  But everything so far needs square matrices – so …Introduction to Information Retrieval Similarity  Clustering  We can compute the similarity between two document vector representations x and x by i j T xx i j  Let X = x … x 1 N T  Then XX is a matrix of similarities  X is symmetric ij T T  So XX = QΛQ  So we can decompose this similarity space into a set of orthonormal basis vectors (given in Q) scaled by the eigenvalues in Λ 17  This leads to PCA (Principal Components Analysis)Introduction to Information Retrieval Sec. 18.2 Singular Value Decomposition For an M  N matrix A of rank r there exists a factorization (Singular Value Decomposition = SVD) as follows: MM MN V is NN (Not proven here.)Introduction to Information Retrieval Sec. 18.2 Singular Value Decomposition MM MN V is NN T T  AA = QΛQ T T T T T T 2 T  AA = (UΣV )(UΣV ) = (UΣV )(VΣU ) = UΣ U T The columns of U are orthogonal eigenvectors of AA . T The columns of V are orthogonal eigenvectors of A A. T T Eigenvalues  …  of AA are the eigenvalues of A A. 1 r Singular valuesIntroduction to Information Retrieval Sec. 18.2 Singular Value Decomposition  Illustration of SVD dimensions and sparseness