We simulate first- and second-order context overlap and show that Skip-Gram with Negative Sampling is similar to Singular Value Decomposition in capturing second-order co-occurrence information, while Pointwise Mutual Information is agnostic to it. We support the results with an empirical study finding that the models react differently when provided with additional second-order information. Our findings reveal a basic property of Skip-Gram with Negative Sampling and point towards an explanation of its success on a variety of tasks.
In this thesis, we study the relation between Latent Semantic Indexing (LSI) and the co-occurrence of terms in collections. LSI is a method for automatic indexing and retrieval, which is based on the vector space model and which represents the documents and computes the relevance scores in a reduced, topic-related space. For our study, we view LSI as a document expansion method, i.e. for a pair of terms, the occurrence of one of them in a document increases or decreases the importance of the other term for the document, depending on the respective entry in the expansion matrix. We study the relation between the expansion matrix and the co-occurrence information of the pairs of terms in collections. We find out that the entries of the expansion matrix are influenced by the order of co-occurrence of the pairs of terms. We then show that the retrieval performance of LSI for the optimal choice of parameters can be obtained when the expansion matrix used is a simple linear combination of the first and the second order co-occurrences. Hiermit erklare ich an Eides Statt, diese Diplomarbeit selbststandig angefertigt, nur die angegebenen Quellen benutzt und sie noch keinem anderen Prufungsamt vorgelegt zu haben. Saarbrucken, den 31. Mai 2005 Latent Semantic Analysis (LSA) is a theory and method for extracting and representing the contextual‐usage meaning of words by statistical computations applied to a large corpus of text (Landauer & Dumais, 1997). The underlying idea is that the aggregate of all the word contexts in which a given word does and does not appear provides a set of mutual constraints that largely determines the similarity of meaning of words and sets of words to each other. The adequacy of LSA's reflection of human knowledge has been established in a variety of ways. For example, its scores overlap those of humans on standard vocabulary and subject matter tests; it mimics human word sorting and category judgments; it simulates word‐word and passage‐word lexical priming data; and, as reported in 3 following articles in this issue, it accurately estimates passage coherence, learnability of passages by individual students, and the quality and quantity of knowledge contained in an essay. Higher order co-occurrences play a key role in the effectiveness of systems used for text mining. A wide variety of applications use techniques that explicitly or implicitly employ a limited degree of transitivity in the cooccurrence relation. In this work we show use of higher orders of co-occurrence in the Singular Value Decomposition (SVD) algorithm and, by inference, on the systems that rely on SVD, such as LSI. Our empirical and mathematical studies prove that term co-occurrence plays a crucial role in LSI. This work is the first to study the values produced in the truncated term-term matrix, and we have discovered an explanation for why certain term pairs receive a high similarity value, while others receive low (and even negative) values. Thus we have discovered the basis for the claim that is frequently made for LSI: LSI emphasizes important semantic distinctions (latent semantics) while reducing noise in the data In this paper we present a theoretical model for understanding the performance of Latent Semantic Indexing (LSI) search and retrieval application. Many models for understanding LSI have been proposed. Ours is the first to study the values produced by LSI in the term by dimension vectors. The framework presented here is based on term co-occurrence data. We show a strong correlation between second-order term co-occurrence and the values produced by the Singular Value Decomposition (SVD) algorithm that forms the foundation for LSI. We also present a mathematical proof that the SVD algorithm encapsulates term co-occurrence information.