MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF TECHNOLOGY -------------------------------------------- THÂN QUANG KHOÁT TOPIC MODELING AND ITS APPLICATIONS MAJOR: INFORMATION TECHNOLOGY THESIS FOR THE DEGREE OF MASTER OF SCIENCE SUPERVISOR: Prof. HỒ TÚ BẢO HANOI, 2009 17057205189431000000 MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF TECHNOLOGY -------------------------------- THESIS FOR THE DEGREE OF MASTER OF SCIENCE MAJOR: INFORMATION TECHNOLOGY TOPIC MODELING AND ITS APPLICATIONS THAN QUANG KHOAT HANOI, 2009 MINISTRY OF EDUCATION AND TRAINING HANOI UNIVERSITY OF TECHNOLOGY -------------------------------------------- THÂN QUANG KHOÁT TOPIC MODELING AND ITS APPLICATIONS MAJOR: INFORMATION TECHNOLOGY THESIS FOR THE DEGREE OF MASTER OF SCIENCE SUPERVISOR: Prof. HỒ TÚ BẢO HANOI, 2009 PLEDGE I promise that the content of this thesis was written solely by me. Any of the content was written based on the reliable references such as published papers in distinguished international conferences and journals, and books published by widely-known publishers.
Many parts and discussions of the thesis are new, not previously published by any other authors. 2 ACKNOWLEDGEMENT First and foremost, I would like to present my gratitude to my supervisor, Professor Ho Tu Bao, for introducing me to this attractive research area, for his willingness to promptly support me to complete the thesis, and for many invaluable advices from the starting point of my thesis. I would like to sincerely thank Nguyen Phuong Thai and Nguyen Cam Tu for sharing some data sets and for pointing me to some sources on the network where I can find the implementations of some topic models. Thanks are also to Phung Trung Nghia for spending his valuable days on helping me to load the data for my experiments.
Finally, I would like to thank David Blei and Thomas Griffiths for their insightful discussions on Topic Modeling and for providing the C implementation of one of their topic models. 3 TABLE OF CONTENTS List of Phrases. 4 List of Tables .5 List of Figures.7 Chapter 2 MODERN PROGRESS IN TOPIC MODELING .1 Linear algebra based models.2 Statistical topic models .3 Discussion and notes.18 Chapter 3 LINEAR ALGEBRA BASED TOPIC MODELS .2 Latent Semantic Analysis .35 Chapter 4 PROBABILISTIC TOPIC MODELS .2 Probabilistic Latent Semantic Analysis .3 Latent Dirichlet Allocation .4 Hierarchical Latent Dirichlet Allocation .5 Bigram Topic Model.60 Chapter 5 SOME APPLICATIONS OF TOPIC MODELS .2 Analyzing research trends over times.6 Experimenting with some topic models.75 4 LIST OF PHRASES Abbreviation Full name AI Artificial Intelligence ART Author-Recipient-Topic Model AT Author-Topic Model BTM Bigram Topic Model cDTM Continuous Dynamic Topic Model CTM Correlated Topic Model dDTM Discrete Dynamic Topic Model DELSA Dirichlet Enhanced LSA DiscLDA Discriminative LDA EM Expectation Maximization HDP Hierarchical Dirichlet Processes HDP-RE Hierarchical Dirichlet Processes with random effects hLDA Hierarchical Latent Dirichlet Allocation HMM-LDA Hidden Markov Model LDA HTMM Hidden Topic Markov Model IG-LDA Incremental Gibbs LDA IR Information Retrieval LDA Latent Dirichlet Allocation LSA Latent Semantic Analysis MBTM Memory Bounded Topic Model MCMC Markov Chain Monte Carlo nCRP Nested Chinese restaurant process NetSTM Network Regularized Statistical Topic Model PF-LDA Particle Filter LDA pLSA Probabilistic Latent Semantic Analysis PLSV Probabilistic Latent Semantic Visualization sLDA Supervised Latent Dirichlet Allocation Spatial LDA Spatial Latent Dirichlet Allocation STM Syntactic Topic Model SVD Singular Value Decomposition TEM Tempered EM algorithm 5 LIST OF TABLES Table 2. Some selected Probabilistic topic models.
DiscLDA for Classification. Comparison of query likelihood retrieval (QL), cluster-based retrieval (CBDM) and retrieval with the LDA-based document models (LBDM). The most probable topics from NIPS and VnExpress collections. Finding the topics of a document.
Finding topics of a report. Selected topics found by HMM-LDA. Classes of function words found by HMM-LDA.73 6 LIST OF FIGURES Figure 1. Some approaches to representing knowledge.
A general view on Topic Modeling. Probabilistic topic models in view of the bag-of-words assumption. Viewing generative models in terms of Topics. A parametric view on generative models.
A corpus consisting of 8 documents. An illustration of finding topics by LSA using cosine. A geometric illustration of representing items in 2-dimensional space. Finding relevant documents using QR-based method.
Graphical model representation of pLSA. A geometric interpretation of pLSA. Graphical model representation of LDA. A geometric interpretation of LDA.
A variational inference algorithm for LDA. A geometric illustration of document generation process. An example of hierarchy of topics [8]. A graphical model representation of BTM.
LDA for Classification. The dynamics of the three hottest and three coldest topics. Evolution of topics through decades.66 7 Chapter 1 INTRODUCTION Information Retrieval (IR) has been being a very active area and has a long history. The development of IR often associates with increasingly huge corpora such as collections of Web pages, collections of scientific papers over years.
Therefore, it poses many hard questions that have received much attention from researchers. One of the most famous questions that seem to be never ended is how to automatically index the documents of a given corpus or database. Another substantial question is how to find the most relevant documents in the semantic manner from the Internet or a given corpus to a given user’s query. Finding and ranking are usually important tasks in IR.
Many tools for supporting these tasks are available now, for example, Google and Yahoo. However most of these available tools are only able to search for documents via words matching instead of semantic matching. Semantics is well-known to be complicated, so finding and ranking documents in the presence of semantics are extremely hard. Despite of this fact, these tasks however potentially have many important applications, which in my opinion are future web service technologies, for instance, semantic searching, semantic advertising, academic recommending, and intelligent controlling.
Semantics is a hot topic not only in the IR community but also in the Artificial Intelligence (AI) community. In particular, in the field of knowledge representation it is crucial to know how to effectively represent natural knowledge gathered from the environment around so that reusing it or integrating new knowledge are easy and efficient. To obtain a good knowledge database, semantics cannot be absent since any word has its own meanings and has semantic relations to some other words. As we know, a word may have multiple senses and play different roles in 8 different contexts.
So taking these facts into account in representing knowledge is extremely complicated and seems to be never-ending debate. One can easily point out a real application of knowledge representation. Let us see an example often arisen from Robotics. Imagine we want to make an intelligent robot to be able to classify rubbish into different kinds.
To make such a robot, we must be able to efficiently represent the information that describe many types of rubbish so that the robot can immediately interpret to which types a given piece of garbage belongs, and can classify which things are reusable. Furthermore, the robot should be able to recognize which is rubbish among many things placed closely together. Thus the amount of information for describing real things is very large to make sure the robot has enough knowledge. If the information were organized unsuitably, the robot could do its works prohibitively slowly and could not learn new knowledge from the environment around.
This example illustrates that knowledge representation is very important in artificial intelligence. Many approaches to representing knowledge have been proposed so far. One direction for this task is based on high-dimensional semantic spaces, where each word is a vector in those spaces; see [20], [39], [58], and [27]. Another one is based on probabilistic topic models which represent the latent structure of words using topics [58], [27], and [11].
Also we can use semantic networks to represent knowledge by placing words in nodes and using edges to connect pairs of related words. For more discussions about these and other approaches, we refer to the surveys in [27] and [58].1 illustrates some of the mentioned approaches. Some approaches to representing knowledge. 9 Automatically discovering the needed information and interpreting a given conversation or document are also challenging tasks in AI.
In fact, these tasks play crucial roles in the problem of finding and ranking the gathered information as mentioned earlier. These tasks are so important that a large number of researches have been launched for either finding efficient methods or applying existing methods to specific real applications. To support this argument, we can easily check by using Google tool1 that the work of Deerwester et al. in [20] receives more than 4200 citations, the work of Blei et al.
in [11] receives more than 1200 citations, and the work of Landauer and Dumais in [39] receives more than 1800 citations. One preferred direction for discovering latent structures hidden in a document or collections of documents and interpreting them clearly is based on the approaches in Topic Modeling. The main contributions of topic modeling to IR are many methods for extracting the gist of a given document, conversation, or collection of documents. Many Topic Models have been shown their wide ranges of applications, some of which are Latent Semantic Analysis (LSA) [20], Probabilistic Latent Semantic Analysis (pLSA) [31], [30], Latent Dirichlet Allocation (LDA) [11], Hierarchical Latent Dirichlet Allocation (hLDA) [8], CorrLDA2 [53].
Due to the ability to uncover latent structures (e. topics), topic models have been successfully applied to automatically index the documents of a given corpus [20], [11], [72], to find topical communities from collections of scientific papers [45], to support spam filtering task [7], to reveal the development of Science over years [10], to discover hot and cold topics in the research community [25], to identify function and content words from text corpora [26], to discover different groups with their corresponding roles only by using text corpora [70], [44], to explain statistically the inference process in human memory [58], [63], [50]. For other attractive applications, we refer to [5], [12], [14], [15], [18], [19], [21], [22], [23], [35], [39], [41], [43], [46], [50], [52], [65], [69], [73], [75], [49], and [29]. From many amazing and potential applications of Topic Modeling, this thesis 1 Http://www.vn 10 is devoted to surveying the modern development of the field.
Since the number of researches relating to topic models constantly and quickly increases, we should not hope the thesis to uncover all, but instead do focus on the most appealing characteristics and the main directions from which new topic models were or will be developed. The thesis also attempts to reveal advantages and disadvantages of each considered model. Possible extensions of some models will be discussed in details after presenting them. Finally, the thesis reports some important applications in AI and some experiments of the author on a collection of papers from NIPS conferences 2 up to volume 12 and a collection of reports of VnExpress 3 – an electronic Vietnamese newspaper.
ORGANIZATION OF THE THESIS: Chapter 2 presents an extensive survey on the recent progress of Topic Modeling. We shall see a general picture and many partial views of the field up to now. In the two subsequent chapters, we go into details of some topic models which are the most typical for each view on topic modeling. Extensive discussions about the (dis)advantages and possible extensions shall be pointed out after presenting a model.
Some interesting applications of topic modeling shall be discussed in Chapter 5. In addition, Chapter 5 also contains some reports about the author’s experiments on some corpora. 2 Advances in Neural Information Processing Systems (NIPS): http://books.cc/ 3 Http://vnexpress.net 11 Chapter 2 MODERN PROGRESS IN TOPIC MODELING The wide range of potential applications of Topic Modeling has motivated many researches including the one of this thesis. While many other subfields of IR have been intensively studied and thus have their solid foundations, such as Relational Database, Topic Modeling has been receiving remarkable considerations from researchers only within the last two decades, especially in the last decade.
Loosely speaking, it can be regarded as the point that Topic Modeling was born when Deerwester et al. [20] first proposed an efficient and reliable method for automatically indexing the documents of a certain collection.