Latent Semantic Indexing.ppt

Latent Semantic Indexing Introduction toArtificial Intelligence COS302 Michael L. Littman Fall 2001 Administration Example analogies… And-or Proof out(x) = g(sumk wk xk) w1=10, w2=10, w3=-10 x1 + x2 + ~x3 Sum for 110? Sum for 001? Generally? b=110, 20 -10 sumi |bi-xi| What happens if we set w0=10? w0 =-15? LSI Background Reading Landauer, Laham, Foltz (1998). Learning human-like knowledge by Singular Value Decomposition: A Progress Report. Advances in Neural Information Processing Systems 10, (pp. 44-51) /papers/nips.ps Outline Linear nets, autoassociation LSI: Cross between IR and NNs Purely Linear Network What Does It Do? out(x) = sumj (sumi xi Wij) Uj = sumi xi (sumj Wij Uj ) Can Other Layers Help? Autoassociator x1 x2 x3 x4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 Applications Autoassociators have been used for data compression, feature discovery, and many other tasks. U matrix encodes the inputs into k features How train? SVD Singular value decomposition provides another method, from linear algebra. Training data M is nxm (input features by examples) M = U S2k VT UTU = I, VTV = I, S diagonal Dimension Reduction Finds least squares best U (nxk, free k) Rows of U map input features to encoded features (instance is sum) Closely related to symm. eigenvalue decomposition, factor analysis principle component analysis Subroutine in many math packages. SVD Applications Eigenfaces Handwriting recognition Text applications… LSI/LSA Latent semantic indexing is the application of SVD to IR. Latent semantic analysis is the more general term. Features are words, examples are text passages. Latent: Not visible on the surface Semantic: Word meanings Running LSI Learns new word representations! Trained on: 20,000-60,000 words 1,000-70,000 passages Use k=100-350 hidden units Similarity between vectors computed as cosine. Step by Step Mij rows are words, columns are passages: filled w/ counts Transformation of matrix: SVD computed: M=USVT Best k