\documentclass{sig-alternate}
\usepackage{graphicx}
\usepackage{algorithmic}
\usepackage{algorithm}
\begin{document}
\title{Dimensionality Reduction and Clustering of Text Documents}
\numberofauthors{1}

\author{%
\alignauthor
Freddy Chong Tat Chua\\
\affaddr{School of Information Systems}\\
\affaddr{Singapore Management University}\\
\affaddr{80 Stamford Road}\\
\affaddr{Singapore 178902}\\
\email{freddy.chua.2009@smu.edu.sg}
}

\maketitle
\begin{abstract}
The human language is inherently unstructured. Human authors never follow the strict rules of grammar because their human readers possess cognitive abilities to interpret the semantic meaning of unstructured human written text. Since unstructured text possess ambiguities and uncertainties, using probabilities to model human language is a natural choice. The investigation of a widely used probabilistic model is the motivation of my survey here. This probabilistic model known as Latent Dirichlet Allocation (LDA), has seen widespread adoption in the field of information retrieval. As prelude to the introduction of LDA, I shall review the Latent Semantic Analysis (LSA) and Probabilistic Latent Semantic Analysis (PLSA) for historical interests. Finally, I briefly discuss Hierarchical Latent Dirichlet Allocation.
\end{abstract}

\category{H.3.3}{Information Search and Retrieval}{Clustering}
\terms{Probabilities and Statistics, Algorithms and Experimentation}
\keywords{Bayesian Models, Gibbs Sampling, Singular Value Decomposition}

\newtheorem{theorem}{Theorem}
\newdef{definition}{Definition}
\newdef{lemma}{Lemma}

\section{Introduction}
Information Retrieval (IR) as a field emerged in computer science when authors started storing their documents in digital format. IR importance increased after wide spread usage of internet. Since there are millions of webpages on the internet, users need a quick and simple way of finding web pages that are relevant to their information need. To fulfill the information need, internet search engines emerged to provide search service for users. Traditionally, these search engines were built using deterministic mathematical approaches such as set theory, logic, linear algebra and combinatorics. However, unlike computer programming languages which follows strict grammars and syntax, the common human language is unstructured with great amount of ambiguity. The unstructured nature of human language makes it difficult for search engines to understand the semantic meaning of web pages. To overcome the difficulty of understanding human languages, an IR related field, Natural Language Processing (NLP) emerged. Despite NLP progress, their scalability for understanding the huge amount of text on the web is still intractable. To make computation tractable for understanding text documents, IR researchers have treated documents using a simple approach known as bag-of-words. Using the bag-of-words approach, IR researchers have been able to cluster documents based on similarities between them.

A notable technique which uses the bag-of-words assumption for document classification of a text corpus is Latent Dirichlet Allocation (LDA) proposed by Blei et al \cite{Blei03a}. The success of LDA in the research community extends far beyond the field of Information Retrieval. LDA has also seen wide application in related fields such as data mining and multimedia classification. My survey here is motivated by the importance of LDA and the bayesian principles used in LDA. To gain a thorough understanding of LDA, it is necessary to appreciate the predecessors of LDA, namely Latent Semantic Analysis (LSA) \cite{citeulike:78280} and Probabilistic Latent Semantic Analysis (PLSA) \cite{SIGIR:1999:hofmann}.

Despite the success of these clustering techniques, it is not clear how many clusters should be assigned to for a text corpus. The naive approach performs the clustering repeatedly by varying the number of clusters and observing the scores of precision, recall and perplexity. To address the issue of variable clusters, Blei et al proposed the Hierarchical Latent Dirichlet Allocation (hLDA) based on principles of nonparametric bayesian techniques \cite{blei2009ncrp}. Besides being able to vary the number of clusters, hLDA also model subclusters which meant that documents belonging to a cluster can be further classified into specialized clusters. A close look at the the Computer Science article in Figure \ref{fig:wiki} also reflects this phenomenon.

\begin{figure}[htbp]
    \centering
    \label{fig:wiki}
    %\includegraphics[bb=0 0 441 410, scale=0.55]{cs.PNG}
    \epsfig{file=cs.eps, scale=0.45}
    \caption{Snippet of Computer Science article in Wikipedia}
\end{figure}

%To address the the issue of unbounded topics, nonparametric bayesian techniques are applied to extend LDA to hLDA. In this survey, we attempt to explain the basic principles of such techniques.

%Finally, after describing the complex models that were developed recently, we shall see an existing work done that uses LDA for improving IR search results.

The paper is organized as follows, we give a derivation of LSA and show a basic folding-in technique for answering IR queries in Section \ref{sec:lsa}. Section \ref{sec:plsa} introduces PLSA for modeling text documents. After reading PLSA, readers should be able to appreciate the extension of PLSA to LDA in Section \ref{sec:lda}. Section \ref{sec:hlda} will talk briefly about hLDA. Finally, we end the paper with a conclusion in Section \ref{sec:conclusion} and discuss what I have learned in this survey.

\section{Latent Semantic Analysis}
\label{sec:lsa}
Latent Semantic Indexing is a linear algebraic technique that uses Singular Value Decomposition(SVD) to factorize a given matrix of term-document occurrence \cite{citeulike:78280}. I will describe the factorization process of SVD, then show an example of how SVD can be used to improve retrieval results.
\subsection{Singular Value Decomposition}
\begin{definition}
Suppose we have $t$ number of terms and $d$ number of documents in our text corpus. We can form a term by document matrix $X$ of size $t \times d$. SVD decomposes $X$ into the product of three matrices $X = TSD^T$, where $T$ is a $t \times d$ matrix, $S$ is a $d \times d$ matrix and $D^T$ is a $d \times d$ matrix. $T$ and $D^T$ are orthogonal matrices while $S$ is a diagonal matrix.
\end{definition}
\begin{lemma}
Multiplying matrix $X$ by its own transpose, always yields a square matrix. $XX^T$ is a square matrix of size $t \times t$. $X^TX$ is a square matrix of size $d \times d$.
\end{lemma}
\begin{theorem}
\label{theorem:1}
The square matrices $XX^T$ and $X^TX$ can always be factorized into their corresponding eigenvectors and eigenvalues. We will not discuss the proof in detail here but interested readers might want to refer to \cite{citeulike:163522} for a detailed explanation.
\end{theorem}
We now show how to derive the matrices $T$, $S$ and $D^T$.
\begin{eqnarray}
X &=& T S D^T\nonumber\\
X^T &=& (T S D^T)^T\nonumber\\
&=& D S^T T^T\nonumber\\
XX^T &=&  (T S D^T)(D S^T T^T)\nonumber\\
&=& T S (D^T D) S^T T^T\nonumber
\end{eqnarray}
If we constrain $D$ to be orthogonal, then $D^T = D^{-1}$. Hence,
\begin{eqnarray}
X X^T &=& T S(D^T D)S^T T^T\nonumber\\
&=& T S(D^{-1} D)S^T T^T\nonumber\\
&=& T S S^T T^T\nonumber
\end{eqnarray}
If we constrain $S$ to be a diagonal matrix, then $S = S^T$. Hence,
\begin{eqnarray}
X X^T &=& T S S^T T^T\nonumber\\
&=& T S^2 T^T\nonumber
\end{eqnarray}
Doing the same manipulations for $X^TX$ and constraining $T$ to be orthogonal allow us to obtain
\begin{eqnarray}
X^T X &=& D S^T T^T T S D^T\nonumber\\
&=& D S^2 D^T\nonumber
\end{eqnarray}
From Theorem \ref{theorem:1}, obtaining the eigenvectors of $XX^T$ and $X^TX$ gives us $T$ and $D^T$ respectively. Since LSA have been mentioned in class, I will skip the examples of LSA.
%Now we shall examine how SVD can be used to improve query results in IR.

%Refer to Table \ref{table:1} for the example we discuss here. Suppose we want to retrieve documents for the query $q$: \textit{Bayesian Networks}. Simple cosine similarity matching will only return documents $d_1$ while document $d_2$ and $d_3$ are also very relevant documents.
%%\begin{eqnarray}
%%\frac{q . d_1}{|q|.|d_1} &=& \frac{2}{\sqrt{2} \sqrt{3}} = 0.82\\
%%\frac{q . d_2}{|q|.|d_2} &=& 0\\
%%\frac{q . d_3}{|q|.|d_3} &=& 0
%%\end{eqnarray}
%Using SVD to factorize the Terms Documents Matrix $X$ results in,
%\begin{eqnarray}
%X &=&
%\begin{pmatrix}
%1	&	0	&	0	&	0	&	0	&	0	\\
%1	&	0	&	1	&	0	&	0	&	0	\\
%1	&	0	&	0	&	0	&	0	&	0	\\
%0	&	1	&	1	&	0	&	0	&	0	\\
%0	&	1	&	1	&	0	&	0	&	0	\\
%0	&	0	&	0	&	1	&	0	&	1	\\
%0	&	0	&	0	&	1	&	0	&	1	\\
%0	&	0	&	0	&	0	&	1	&	1	\\
%0	&	0	&	0	&	0	&	1	&	0
%\end{pmatrix}
%\nonumber\\
%T &=&
%\begin{pmatrix}
%-0.18	&	0	&	-0.53	&	0	&	-0.43	&	0	\\
%-0.52	&	0	&	-0.43	&	0	&	0.74	&	0	\\
%-0.18	&	0	&	-0.53	&	0	&	-0.43	&	0	\\
%-0.58	&	0	&	0.36	&	0	&	-0.20	&	0	\\
%-0.58	&	0	&	0.36	&	0	&	-0.20	&	0	\\
%0	&	-0.61	&	0	&	0.32	&	0	&	-0.16	\\
%0	&	-0.61	&	0	&	0.32	&	0	&	-0.16	\\
%0	&	-0.48	&	0	&	-0.63	&	0	&	0.60	\\
%0	&	-0.13	&	0	&	-0.63	&	0	&	-0.76
%\end{pmatrix}
%\nonumber\\
%S &=&
%\begin{pmatrix}
%2.21	&	0	&	0	&	0	&	0	&	0	\\
%0	&	2.19	&	0	&	0	&	0	&	0	\\
%0	&	0	&	1.68	&	0	&	0	&	0	\\
%0	&	0	&	0	&	1.41	&	0	&	0	\\
%0	&	0	&	0	&	0	&	0.54	&	0	\\
%0	&	0	&	0	&	0	&	0	&	0.46
%\end{pmatrix}
%\nonumber\\
%D^T &=&
%\begin{pmatrix}
%-0.40	&	-0.52	&	-0.76	&	0	&	0	&	0	\\
%0	&	0	&	0	&	-0.56	&	-0.28	&	-0.78	\\
%-0.89	&	0.43	&	0.17	&	0	&	0	&	0	\\
%0	&	0	&	0	&	0.45	&	-0.89	&	0	\\
%-0.23	&	-0.74	&	0.63	&	0	&	0	&	0	\\
%0	&	0	&	0	&	-0.70	&	-0.35	&	0.63
%\end{pmatrix}
%\nonumber
%\end{eqnarray}
%By reducing the dimensionality of the matrices, we can obtain the following $X_r = T_r S_r D_r^T$,
%\begin{eqnarray}
%T_r &=&
%\begin{pmatrix}
%-0.18	&	0	\\
%-0.52	&	0	\\
%-0.18	&	0	\\
%-0.58	&	0	\\
%-0.58	&	0	\\
%0	&	-0.61	\\
%0	&	-0.61	\\
%0	&	-0.48	\\
%0	&	-0.13
%\end{pmatrix}
%\nonumber\\
%S_r &=&
%\begin{pmatrix}
%2.21	&	0	\\
%0	&	2.19
%\end{pmatrix}
%\nonumber\\
%D_r^T &=&
%\begin{pmatrix}
%-0.40	&	-0.52	&	-0.76	&	0	&	0	&	0	\\
%0	&	0	&	0	&	-0.56	&	-0.28	&	-0.78
%\end{pmatrix}
%\nonumber
%\end{eqnarray}
\subsection{Folding-in}
Suppose we have a query $q$ and we want to retrieve the relevant documents in the reduced semantic space. First we have to map $q$ into the reduced semantic space $d_q$.
\begin{eqnarray}
q &=& T_r S_r d_q^T\nonumber\\
T_r^T q &=& T_r^T T_r S_r d_q^T\nonumber\\
S_r^{-1} T_r^T q &=& S_r^{-1} S_r d_q^T\nonumber\\
S_r^{-1} T_r^T q &=& d_q^T\nonumber\\
d_q &=& (S_r^{-1} T_r^T q)^T\nonumber\\
&=& q^T T_r S_r^{-1}\nonumber
%&=&
%\begin{pmatrix}
%-0.1620 & -0.0000
%\end{pmatrix}
\end{eqnarray}
%Using the new matric $X_r$, we calculate the new cosine similarities,
%\begin{eqnarray}
%\frac{d_q . d_1}{|q||d_1|} &=& 1\\
%\frac{d_q . d_2}{|q||d_2|} &=& 1\\
%\frac{d_q . d_3}{|q||d_3|} &=& 1
%\end{eqnarray}
We can also apply the same method to update the matrices without recomputing SVD. Suppose we have a updated term document matrix $X^{(t+m)\times (d+q)}$ where $q$ represents number of new documents and $m$ represents number of new terms in these documents.
%We first compute $X^{t \times q} = T^{t \times 2} S^{2 \times 2} D^{2 \times q}$. Then using $D^{2 \times q}$, we compute $X^{(t+m) \times q} = T^{(t+m) \times 2} S^{2 \times 2} D^{2 \times q}$. But these is only an approximation since we computed $D$ without knowing the new $T$. For a more detailed treatment of updating the SVD for LSA, refer to \cite{journals/csda/TougasS07}.
We can first compute the updated matrices $D_{(d+q) \times r}$ using the current $T_{t \times r}$ and $S_{r \times r}$ matrices where $r$ is the dimension of the reduced space.
\begin{eqnarray}
X_{t \times q} &=& T_{t \times r} S_{r \times r} D_{r \times q}^T\nonumber\\
D_{q \times r} &=& X_{q \times t}^T T_{t \times r} S_{r \times r}^{-1}\nonumber
\end{eqnarray}
Using the computed $D_{q \times r}$, we append it to the current $D_{d \times r}$ matrix to obtain a $D_{(d+q) \times r}$ matrix. Then we compute the new $T_{(t+m) \times r}$ matrix.
\begin{eqnarray}
X_{m\times q} &=& T_{m \times r} S_{r \times r} D_{r \times q}^T \nonumber\\
X_{m\times q} D_{q \times r}  S_{r \times r}^{-1} &=& T_{m \times r} \nonumber\\
T_{m \times r} &=& X_{m \times q} D_{q \times r}  S_{r \times r}^{-1} \nonumber
\end{eqnarray}
We also append the computed $T_{m \times r}$ to $T_{t \times r}$ and obtain a $T^{(t+m) \times r}$ matrix. Finally we have shown that the updated term document matrix $X^{(t+m)\times (d+q)}$ can be factorized in this manner, \[X^{(t+m)\times (d+q)} = T^{(t+m) \times r} S_{r \times r} D_{r \times (d+q)}^T\]

\section{Probabilistic Latent Semantic\\Analysis}
\label{sec:plsa}
\begin{definition}
Suppose we have $M$ number of documents and $V$ number of words in the vocabulary. Let $d_m$ be the index for each document and $w_v$ be the occurence of word $v$ in the document $d_m$. We define a joint probability model $P(d_m, w_v)$ as the probability of observing word $v$ in the document $d_m$. As we have shown earlier in LSA, it is possible to represent words and documents in latent space. PLSA achieves the same effect by introducing a latent variable $z_k$ that denotes the topic of each word in a document, where $K$ is the number of topics in the corpus and $1 \leq k \leq K$. PLSA makes several assumptions to define the model.
\end{definition}
\begin{enumerate}
\item Given a document $d_m$ in the corpus, we are able to infer the topic $z_k$ of the document, $P(z_k | d_m)$.
\item Given a topic, we are able to infer which word $v$ is likely to appear, $P(w_v|z_k)$.
\end{enumerate}
With the introduction of this latent topic variable $z$, we can define the joint probability of observing a word in the document as $P(d_m, w_v, z_k)$, where
\begin{eqnarray}
P(d_m, w_v, z_k) = P(w_v|z_k) P(z_k|d_m) P(d_m)\nonumber
\end{eqnarray}
Since $z_k$ is latent and we can only observe $d_m$ and $w_v$, then we need to marginalize $z_k$ out of the equation by summing over all possible values that $z_k$ can take.
\begin{eqnarray}
P(d_m, w_v) &=& \sum_{k=1}^K P(d_m, w_v, z_k)\nonumber\\
&=& \sum_{k=1}^K P(w_v|z_k) P(z_k|d_m) P(d_m)\nonumber\\
&=& \sum_{k=1}^K P(w_v|z_k) P(z_k) P(d_m|z_k)\nonumber
\end{eqnarray}
We will like to define the probability of the entire corpus $P(d,w)$ where
\begin{eqnarray}
P(d,w) &=& \prod_{m=1}^M \prod_{v=1}^V P(d_m,w_v)\nonumber\\
&=& \prod_{m=1}^M \prod_{v=1}^V \sum_{k=1}^K P(w_v|z_k) P(z_k) P(d_m|z_k)\nonumber
\end{eqnarray}
\begin{table}[htb]
	\centering
	\caption{An example for Bayesian Networks}
	\label{table:1}
    	\begin{tabular}{l l}
	\hline \hline
    	$d_1$:      & Learning Bayesian Networks\\
	\hline
    	$d_2$:      & Probabilistic Graphical Models\\
	\hline
	$d_3$:	& Learning in Graphical Models\\
    	\hline
	$d_4$:	& Modern Information Retrieval\\
	\hline
	$d_5$:	& Introduction to Data Mining\\
	\hline
	$d_6$:	& Data Management and Information Retrieval\\
	\hline \hline
	\\
    	\end{tabular}
	Terms Documents Matrix, $X$
	\begin{tabular}{c | c c c c c c}
	\\
	Terms & \multicolumn{6}{c}{Documents}\\
	\\
				& $d_1$ & $d_2$ & $d_3$ & $d_4$ & $d_5$ & $d_6$ \\
    \hline
	networks	& 1 & 0 & 0 & 0 & 0 & 0\\
	learning	& 1 & 0 & 1 & 0 & 0 & 0\\
	bayesian	& 1 & 0 & 0 & 0 & 0 & 0\\
	graphical	& 0 & 1 & 1 & 0 & 0 & 0\\
	models		& 0 & 1 & 1 & 0 & 0 & 0\\
	information	& 0 & 0 & 0 & 1 & 0 & 1\\
	retrieval 	& 0 & 0 & 0 & 1 & 0 & 1\\
	data 		& 0 & 0 & 0 & 0 & 1 & 1\\
	mining 		& 0 & 0 & 0 & 0 & 1 & 0\\
	\end{tabular}
\end{table}

Before we proceed on, we will like to show its relation to LSA. Suppose we assume that in our corpus in Table \ref{table:1}, our documents consists of two main topics, then what we want to find is the conditional probability tables here as shown in Table \ref{table:2}. These conditional probabilities bear similarities to the LSA formulation for a semantic space of two dimension.
\begin{table}[htb]
	\centering
	\caption{The Conditional Probability Tables}
	\label{table:2}
	\begin{tabular}{c | c c c c c c}
    $P(d_i | z_k)$ & $d_1$ & $d_2$ & $d_3$ & $d_4$ & $d_5$ & $d_6$\\
    \hline
    $z_1$ & ? & ? & ? & ? & ? & ?\\
    $z_2$ & ? & ? & ? & ? & ? & ?
	\end{tabular}
	\begin{tabular}{c | c c c c c c c c c}
    $P(w_j | z_k)$ & $w_1$ & $w_2$ & $w_3$ & $w_4$ & $w_5$ & $w_6$ & $w_7$ & $w_8$ & $w_9$\\
    \hline
    $z_1$ & ? & ? & ? & ? & ? & ? & ? & ? & ?\\
    $z_2$ & ? & ? & ? & ? & ? & ? & ? & ? & ?
	\end{tabular}
    \begin{tabular}{c | c}
    $P(z_1)$ & ?\\
    $P(z_2)$ & ?
   	\end{tabular}
\end{table}
These values should be filled in to maximize the likelihood value $P(d,w)$. In statistics, it is computationally more tractable to maximize the log equivalent of likelihood values, hence, the log likelihood $\mathcal{L}$ is often expressed in this manner,
\begin{eqnarray}
\mathcal{L} &=& \log P(d,w)\nonumber\\
&=& \log \prod_{m=1}^M \prod_{v=1}^V \sum_{k=1}^K P(w_v|z_k) P(z_k) P(d_m|z_k)\nonumber\\
&=& \sum_{m=1}^M \sum_{v=1}^V n(d_m, w_v) \log \sum_{k=1}^K P(w_v|z_k) P(z_k) P(d_m|z_k)\nonumber
\end{eqnarray}
where $n(d_m, w_v)$ is the number of times word $w_v$ occur in document $d_m$. Maximizing the likelihood here by filling in the conditional probability tables is essentially an optimization problem. For maximizing likelihood, the Expectation Maximization algorithm often used for computing these value \cite{citeulike:117535}. We shall skip the full derivation here but interested readers may refer to \cite{citeulike:1147881}. We shall follow the equations as described in \cite{SIGIR:1999:hofmann} to compute these values.
In the E step of the algorithm, we first compute $P(z_k|d_m,w_v)$.
\begin{eqnarray}
P(z_k|d_m,w_v) = \frac{P(z_k)P(d_m|z_k)P(w_v|z_k)}{\sum_{l=1}^K P(z_l)P(d_m|z_l)P(w_v|z_l)}
\end{eqnarray}
In the M step of the algorithm, we compute the quantities $P(w_v|z_k), P(d_m|z_k), P(z_k)$.
\begin{eqnarray}
P(w_v|z_k) = \frac{\sum_{m=1}^M n(d_m, w_v) P(z_k|d_m,w_v)}{\sum_{m=1}^M \sum_{n=1}^N n(d_v, w_n) P(z_k|d_v,w_n)}\\
P(d_m|z_k) = \frac{\sum_{v=1}^V n(d_m, w_v) P(z_k|d_m,w_v)}{\sum_{n=1}^N \sum_{v=1}^V n(d_n, w_v) P(z_k|d_n,w_v)}\\
P(z_k) = \frac{\sum_{m=1}^M \sum_{v=1}^V n(d_m, w_v) P(z_k|d_m,w_v)}{\sum_{m=1}^M \sum_{v=1}^V n(d_m, w_v)}
\end{eqnarray}

%%\begin{figure}[htbp]
%%    \centering
%%    \epsfig{file=plsi.eps, scale=0.45}
%%    \caption{Probabilistic Latent Semantic Indexing Model}
%%    \label{fig:1}
%%\end{figure}
%%\begin{definition}

After running the EM algorithm, we get such values in Table \ref{table:3}.
\begin{table}[htb]
	\centering
	\caption{The Conditional Probability Tables}
	\label{table:3}
    \tiny
	\begin{tabular}{c | c c c c c c}
    $P(d_i | z_k)$ & $d_1$ & $d_2$ & $d_3$ & $d_4$ & $d_5$ & $d_6$\\
    \hline
    $z_1$ & 0 & 0 & 0 & 0.29 & 0.29 & 0.43\\
    $z_2$ & 0.38 & 0.25 & 0.38 & 0 & 0 & 0
	\end{tabular}
	\begin{tabular}{c | c c c c c c c c c}
    $P(w_j | z_k)$ & $w_1$ & $w_2$ & $w_3$ & $w_4$ & $w_5$ & $w_6$ & $w_7$ & $w_8$ & $w_9$\\
    \hline
    $z_1$ & 0 & 0 & 0 & 0 & 0 & 0.29 & 0.29 & 0.29 & 0.14\\
    $z_2$ & 0.13 & 0.25 & 0.13 & 0.25 & 0.25 & 0 & 0 & 0 & 0
	\end{tabular}
    \begin{tabular}{c | c}
    $P(z_1)$ & 0.47\\
    $P(z_2)$ & 0.53
   	\end{tabular}
\end{table}

Since PLSA is a probabilistic technique, the results of small samples may not always be consistent. Therefore, we ran experiments on a corpus of a larger size. Using text corpus from wikipedia articles for Computer science, Information theory, Cryptography, Cryptanalysis, History of cryptography, Database, Data mining and Information retrieval. We run PLSA on these articles. Then we rank the words and obtain the following sets of words for each topic. Refer to Table \ref{table:4} for the results.
\begin{table}[htb]
	\centering
	\caption{List of words by topics using PLSA and LDA}
	\label{table:4}
    \small
	\begin{tabular}{|c | c | c | c |}
    \hline
    PLSA Topic 1 & LDA Topic 1 & PLSA Topic 2 & LDA Topic 2\\
    \hline
    data 	&	data	&	cipher	&	 comput	\\
    databas 	&	   databas	&	   kei	&	 inform	\\
    mine 	&	   comput	&	   cryptographi	&	 cipher	\\
    pattern 	&	   inform	&	   inform	&	 kei	\\
    relat 	&	   mine	&	   us	&	 cryptographi	\\
    us 	&	   system	&	   encrypt	&	 us	\\
    model 	&	   model	&	   attack	&	 system	\\
    object 	&	   scienc	&	   algorithm	&	 algorithm	\\
    system 	&	   retriev	&	   secur	&	 theori	\\
    inform 	&	   pattern	&	   cryptanalysi	&	 attack	\\
    applic 	&	   us	&	   cryptograph	&	 encrypt	\\
    set 	&	   document	&	   code	&	 secur	\\
    transact 	&	   object	&	   messag	&	 cryptanalysi	\\
    lock 	&	   relat	&	   channel	&	 cryptograph	\\
    manag 	&	   program	&	   comput	&	 code	\\
    3	&	   applic	&	   system	&	 messag	\\
    program 	&	   queri	&	   theori	&	 channel	\\
    exampl 	&	3	&	   commun	&	 scienc	\\
    oper 	&	   transact	&	   entropi	&	 commun	\\
    document	&	   set	&	   develop	&	entropi	\\
	\hline
   	\end{tabular}
\end{table}

\section{Latent Dirichlet Allocation}
Because of the heavy use of probabilities and symbolic notations here, I will first like to go through the basics of probabilities. I introduce these notations here instead of the previous section because PLSA is significantly simpler than LDA. I also provide a toy example using Dice Toss to illustrate the basic principles of bayesian parameter learning. It is important to understand this section before moving on to the section on LDA model.
\subsection{Probabilities and Identities}
\begin{eqnarray}
\Gamma(x) &=& (x-1)!\nonumber\\
\int_0^1 f^{a-1} (1-f)^{b-1} ~df &=& \frac{\Gamma(a) \Gamma(b)}{\Gamma(a+b)}\nonumber\\
\int_0^1 \prod_{i=1}^N f_i^{a_i - 1} ~df &=& \frac{\prod_{i=1}^N \Gamma(a_i)}{\Gamma( \sum_{i=1}^N a_i )}\nonumber\\
B(a) &=& \frac{\prod_{i=1}^N \Gamma(a_i)}{\Gamma( \sum_{i=1}^N a_i )}\nonumber
\end{eqnarray}
\subsubsection{Dice Toss Toy Example}
Suppose I have a dice of $I$ sides. I toss the dice and the probability of landing on side $i$ is $p(s=i | f) = f_i$. I throw the dice $N$ number of times and obtain a set of results $s$ where $s=(s_1, s_2, s_3, \ldots, s_n, \ldots, s_N)$. We can specify the probability of observing this set of results in this manner,
\begin{eqnarray}
p(s|f) &=& \prod_{n=1}^N p(s_n | f)\nonumber\\
&=& f_1^{n_1} f_2^{n_2} f_3^{n_3} \ldots f_i^{n_i} \ldots f_I^{n_I}\nonumber\\
&=& \prod_{i=1}^I f_i^{n_i}
\end{eqnarray}
where $n_i$ denotes the number of times side $i$ appear. Notice that the $\prod_{n=1}^N$ has been changed to $\prod_{i=1}^I$. The $\prod_{n=1}^{\textit{trials}}$ has been expressed as $\prod_{i=1}^{\textit{states}}$.

Suppose that $f$ is a dirichlet distribution with $a$ as hyperparameters. Then we express the probability distribution of f as,
\[p(f|a) = \frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)}\prod_{i=1}^I f_i^{a_i - 1}\]
If we want to update the parameter $f$ base on the observation of $s$, then we can express $f$ in this manner.
\begin{eqnarray}
p(f|s, a) &=& \frac{p(s|f, a)p(f|a)}{\int_0^1 p(s|f, a)p(f|a)~df}\nonumber\\
&=& \frac{
\prod_{i=1}^I f_i^{n_i}
\frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)}\prod_{i=1}^I f_i^{a_i - 1}
}
{\int_0^1
\prod_{i=1}^I f_i^{n_i}
\frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)}\prod_{i=1}^I f_i^{a_i - 1}
~df}\nonumber\\
&=& \frac{
\frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)}\prod_{i=1}^I f_i^{n_i + a_i - 1}
}
{
\frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)}
\int_0^1 \prod_{i=1}^I f_i^{n_i + a_i - 1}
~df}\nonumber\\
&=& \frac{\Gamma(\sum_{i=1}^I n_i + a_i)}{\prod_{i=1}^I \Gamma(n_i + a_i)}\prod_{i=1}^I f_i^{n_i + a_i - 1}\nonumber
\end{eqnarray}
Notice that after updating $f$ base on $s$ observations, $f$ is still a dirichlet distribution. This property is known as conjugate priors. Base on this property, estimating the parameters $f_i$ after observing $n$ trials is a simple counting procedure. Suppose I want to obtain $f_x$ from $f = (f_1, f_2, \ldots, f_x, \ldots, f_i, \ldots, f_I)$,
\begin{flalign}
E&(f_x|s, a) \nonumber\\
&= \int_0^1 f_x p(f|s, a) ~df \nonumber\\
&= \int_0^1 f_x p(f|s, a) ~df \nonumber\\
&= \int_0^1 f_x \frac{\Gamma(\sum_{i=1}^I n_i + a_i)}{\prod_{i=1}^I \Gamma(n_i + a_i)}\prod_{i=1}^I f_i^{n_i + a_i - 1} ~df\nonumber\\
&= \frac{\Gamma(\sum_{i=1}^I n_i + a_i)}{\prod_{i=1}^I \Gamma(n_i + a_i)} \int_0^1 f_x^{n_x + a_x} \prod_{i=1,i\neq x}^I f_i^{n_i + a_i - 1} ~df\nonumber\\
&= \frac{\Gamma(\sum_{i=1}^I n_i + a_i)}{\prod_{i=1}^I \Gamma(n_i + a_i)}
\frac{\Gamma(n_x+a_x+1) \prod_{i=1,i\neq x}^I\Gamma(n_i+a_i)}{\Gamma(n_x+a_x+1 + \sum_{i=1,i\neq x}^I n_i+a_i )}\nonumber\\
&= \frac{\Gamma(\sum_{i=1}^I n_i + a_i)\Gamma(n_x+a_x+1)}{\Gamma(n_x+a_x)\Gamma(1 + \sum_{i=1}^I n_i+a_i )}\nonumber\\
&= \frac{n_x+a_x}{\sum_{i=1}^I n_i+a_i}
\end{flalign}
Now I show the Collapsed Gibbs Sampling for this toy example. Suppose we want to obtain $f$ but do not have the counts of occurence $n_i$. We can generate the samples $s_n$ using $f$ by deriving a markov chain, $p(s_n | s_{-n}, a)$, where $s_{-n}$ represents all samples except $s_n$.
%\begin{eqnarray}
%P(s | a) &=& \int_0^1 p(s, f|a) ~df\nonumber\\
%&=& \int_0^1 p(s|f) p(f|a) ~df\nonumber\\
%&=& \int_0^1 \prod_{i=1}^I f_i^{n_i} \frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)}\prod_{i=1}^I f_i^{a_i - 1} ~df\nonumber\\
%&=& \frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)} \int_0^1 \prod_{i=1}^I f_i^{n_i + a_i - 1} ~df\nonumber\\
%&=& \frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)} \frac{\prod_{i=1}^I \Gamma(n_i+a_i)}{\Gamma(\sum_{i=1}^I n_i+a_i)}\nonumber
%\end{eqnarray}
%\begin{eqnarray}
%s_n &=& x\nonumber\\
%P(s_{-n} | a) &=& \frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)} \frac{\Gamma(n_x + a_x - 1)\prod_{i=1,i\neq x}^I \Gamma(n_i+a_i)}{\Gamma(n_x + a_x - 1 + \sum_{i=1,i\neq x}^I n_i+a_i)}\nonumber
%\end{eqnarray}
Using the above results,
\begin{eqnarray}
p(s_n=i|s_{-n}, a) &=& E(f_i|s_{-n}, a)\nonumber\\
&=& \frac{n_i+a_i}{(\sum_{i=1}^I n_i+a_i)}
\end{eqnarray}
I will show later in Algorithm \ref{alg:1} how we adjust the parameters by excluding the results of $s_n$ in $s_{-n}$.
%\begin{eqnarray}
%p(s_n=i|s_{-n}, a) &=& \frac{p(s_n, s_{-n}|a)}{p(s_{-n}|a)}\nonumber\\
%&=& \frac{p(s|a)}{p(s_{-n}|a)}\nonumber\\
%&=& \frac{\frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)} \frac{\prod_{i=1}^I \Gamma(n_i+a_i)}{\Gamma(\sum_{i=1}^I n_i+a_i)}}{\frac{\Gamma(\sum_{i=1}^I a_i)}{\prod_{i=1}^I \Gamma(a_i)} \frac{\Gamma(n_x + a_x - 1)\prod_{i=1,i\neq x}^I \Gamma(n_i+a_i)}{\Gamma(n_x + a_x - 1 + \sum_{i=1,i\neq x}^I n_i+a_i)}} \nonumber\\
%&=& \frac{n_x + a_x - 1}{(\sum_{i=1}^I n_i + a_i) - 1}\nonumber
%\end{eqnarray}
\subsection{LDA Model}
\label{sec:lda}
%Following PLSA, David Blei argued that PLSA leads to overfitting issues and proposed the use of Dirichlet priors as conjugate parameters for the modeling of text corpora. The proposed model is known as the Latent Dirichlet Allocation (LDA) model and we try to describe it formally here.
%\begin{figure}[htbp]
%    \centering
%    \epsfig{file=lda.eps, scale=0.45}
%    \caption{Latent Dirichlet Allocation}
%    \label{fig:1}
%\end{figure}
\begin{figure}[htbp]
    \centering
    \epsfig{file=lda_with_phi.eps, scale=0.45}
    \caption{Latent Dirichlet Allocation}
    \label{fig:2}
\end{figure}
Refer to Figure \ref{fig:2} for a graphical description of LDA in plate notation form.
\begin{definition}
Suppose we have $M$ documents and $N$ words in document $m$. Let $\theta_m$ represent the dirichlet distribution of topics in each document $m$ and $\alpha$ are the hyper-parameters of the dirichlet distribution. Let $w_{m,n}$ be the index of the word $n$ in document $m$ and $z_{m,n}$ be the topic $k$ of each word $w_{m,n}$. Let $\phi_k$ represent the dirichlet distribution of words over topic $k$ with $\beta$ as hyper-parameters.
\end{definition}
Formally, the LDA model can be described mathematically in this manner,
%%\begin{flalign}
%p&(w_d|\alpha,\beta)\nonumber\\
%&= \int_0^1 p(\theta_d|\alpha) \Bigg( \prod_{n=1}^N \sum_{z_{dn}} p(z_{dn}|\theta_d) P(w_{dn}|z_{dn},\beta) \Bigg) d\theta_d\nonumber
%\end{flalign}
%Finally, the probability of observing the entire corpus is given by the product of all documents in the corpus.
%\begin{flalign}
%p&(D|\alpha,\beta) = \prod_{d=1}^M p(w_d | \alpha,\beta)\nonumber\\
%& = \prod_{d=1}^M \int_0^1 p(\theta_d|\alpha) \Bigg( \prod_{n=1}^N \sum_{z_{dn}} P(z_{dn}|\theta) P(w_{dn}|z_{dn},\beta) \Bigg) d\theta_d\nonumber
%\end{flalign}
%Our objective here is to find the set of parameters $\alpha$ and $\beta$ to maximize the likelihood $p(D|\alpha,\beta)$. I attempt to derive a Gibbs Sampling approach to solve this optimization problem.
\begin{eqnarray}
\alpha &=& (\alpha_1, \ldots, \alpha_k, \ldots, \alpha_K) \nonumber\\
p(\theta_m | \alpha) &=& \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})}\theta_{m,1}^{\alpha_{1} -1}\ldots\theta_{m,K}^{\alpha_{K} -1}\nonumber\\
&=& \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})}\prod_{k=1}^K \theta_{m,k}^{\alpha_{k} -1}\nonumber\\
\beta &=& (\alpha_1, \ldots, \alpha_v, \ldots, \alpha_V)\nonumber\\
p(\phi_k|\beta) &=& \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})}\phi_{k,1}^{\beta_{1} -1}\ldots\phi_{k,V}^{\beta_{V} -1}\nonumber\\
&=& \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})}\prod_{v=1}^V \phi_{k,v}^{\beta_{v} -1}\nonumber
\end{eqnarray}
The discrete values $z_{m,n}$ depends on the topic distribution of each document $m$.
\[p(z_{m,n}=k|\theta_m) = \theta_{m,k}\]
The probability of observing each word $w_{m,n}$ in document $m$ depends on the discrete topic $z_{m,n}$ and word distribution $\phi$.
\[p(w_{m,n}=v|z_{m,n}=k, \phi) = \phi_{k,v}\]
The joint probability of observing a word is,
\begin{flalign}
p&(w_{m,n}, z_{m,n}, \phi, \theta_m | \alpha, \beta)\nonumber\\
&= p(w_{m,n}|z_{m,n}, \phi) p(z_{m,n}|\theta_m) p(\phi | \beta) p(\theta_m|\alpha)\nonumber
\end{flalign}
The joint probability of observing a corpus is
\begin{flalign}
p&(w, z, \phi, \theta | \alpha, \beta) \nonumber\\
&= \prod_{m=1}^M \prod_{n=1}^N p(w_{m,n}, z_{m,n}, \phi, \theta_m | \alpha, \beta)\nonumber\\
&= \prod_{m=1}^M p(\theta_m|\alpha) \prod_{n=1}^N p(z_{m,n}|\theta_m) p(w_{m,n}|z_{m,n},\phi)\nonumber
\end{flalign}
What we want to solve for are the parameters $\theta$ and $\phi$. There are many ways of solving this model. I present a collapsed Gibbs Sampling approach to find these parameters \cite{griffiths_finding_2004, citeulike:3057616}.
\subsection{Gibbs Sampling}
Gibbs Sampling is commonly used when it is hard to derive an analytical expression of a single variable from the joint probability distribution. Our main objective is to obtain,
\begin{eqnarray}
\theta &=& (\theta_{1,1}, \theta_{1,2}, \ldots, \theta_{m,k}, \ldots, \theta_{M,K})\nonumber\\
\theta_{m,k} &=& \frac{n(m,k)+\alpha_k}{\sum_{k=1}^K n(m,k) + \alpha_k}\\
\phi &=& (\phi_{1,1}, \phi_{1,2}, \ldots, \phi_{k,v}, \ldots, \phi_{K,V})\nonumber\\
\phi_{k,v} &=& \frac{n(k,v)+\beta_v}{\sum_{v=1}^V n(k,v)+\beta_v}
\end{eqnarray}
where $n_{k,v}$ is the number of times word $v$ has been assigned topic $k$ and here $n_{m,k}$ is the number of times topic $k$ appear in document $m$. But n(m,k) and n(k,v) are unknown to us now.

%\begin{eqnarray}
%P(z_i|z_{-i}, w) &=& P(z_i|z_{-i}, w_{-i}, w_i)\\
%&=& \frac{ P(z_i, z_{-i}, w_{-i}, w_i) }{P(z_i, z_{-i}, w_{-i}, w_i)}
%\end{eqnarray}
The Gibbs Sampling algorithm allows us to reduce the parameter estimation problem to a simple counting and sampling process. We will like to derive a sampling, counting and update procedure for estimating the parameters and latent variables.

%Since we do not observe the latent variables $z_{m,n}$, $\theta_m$ and $\phi$, we have to marginalize these latent variables out by summing over all possible values of $z_{m,n}$ and integrating $\theta_m, \phi$ since $\theta_m, \phi$ is a continuous variable.
%p(\theta_m, \phi, z_m, w_m|\alpha, \beta) &=& p(\theta_m|\alpha) \prod_{n=1}^N p(z_{mn}|\theta_m) p(w_{mn}|z_{mn},\phi)\nonumber
\subsubsection{Collapsed Gibbs Sampling}
Following the approach in \cite{griffiths_finding_2004, citeulike:3057616}, we integrate the $\phi$ and $\theta$ parameters to obtain the following,
\begin{equation}
p(z, w|\alpha, \beta) = p(w|z,\beta)p(z|\alpha)\nonumber
\end{equation}
\begin{eqnarray}
p(w|z, \beta) &=& \int p(w, \phi |z, \beta)~d\phi\nonumber\\
&=& \int p(w|z, \phi, \beta) p(\phi|z, \beta) ~d\phi\nonumber\\
&=& \int p(w|z, \phi) p(\phi|\beta) ~d\phi\nonumber\\
&=& \int \prod_{k=1}^{K} \Bigg( \prod_{v=1}^V \phi_{k,v}^{n_{k,v}} \Bigg) \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})} \Bigg( \prod_{v=1}^V \phi_{k,v}^{\beta_{v} -1} \Bigg)d\phi\nonumber\\
&=& \int \prod_{k=1}^{K} \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})}\prod_{v=1}^V \phi_{k,v}^{n_{k,v} + \beta_{v} -1} ~d\phi\nonumber\\
&=& \prod_{k=1}^{K} \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})} \int \prod_{v=1}^V \phi_{k,v}^{n_{k,v} + \beta_{v} -1} ~d\phi\nonumber\\
&=& \prod_{k=1}^{K} \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})} \frac{\prod_{v=1}^V \Gamma(\beta_{v} + n_{k,v})}{\Gamma(\sum_{v=1}^V \beta_{v} + n_{k,v})}\nonumber
%&=& \prod_{k=1}^{K} \frac{B(\beta + n_k)}{B(\beta)}\nonumber
\end{eqnarray}
\begin{eqnarray}
p(z|\alpha) &=& \int p(z, \theta|\alpha) ~d\theta\nonumber\\
&=& \int p(z|\theta, \alpha) p(\theta|\alpha) ~d\theta\nonumber\\
&=& \int p(z|\theta) p(\theta|\alpha) ~d\theta\nonumber\\
&=& \int \prod_{m=1}^{M} \Bigg( \prod_{k=1}^K \theta_{m,k}^{n_{m,k}} \Bigg) \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})} \Bigg( \prod_{k=1}^K \theta_{m,k}^{\alpha_{k} -1} \Bigg) d\theta\nonumber\\
&=& \int \prod_{m=1}^{M} \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})}\prod_{k=1}^K \theta_{m,k}^{n_{m,k} + \alpha_{k} -1} ~d\theta\nonumber\\
&=& \prod_{m=1}^{M} \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})} \int \prod_{k=1}^K \theta_{m,k}^{n_{m,k} + \alpha_{k} -1} ~d\theta\nonumber\\
&=& \prod_{m=1}^{M} \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})} \frac{\prod_{k=1}^K \Gamma(\alpha_{k} + n_{m,k})}{\Gamma(\sum_{k=1}^K \alpha_{k} + n_{m,k} )}\nonumber
%&=& \prod_{m=1}^{M} \frac{B(\alpha + n_m)}{B(\alpha)}\nonumber
\end{eqnarray}
%\begin{eqnarray}
%p(z, w|\alpha, \beta) &=& p(w|z,\beta)p(z|\alpha)\nonumber\\
%&=& \prod_{k=1}^{K} \frac{B(\beta + n_k)}{B(\beta)} \prod_{m=1}^{M} \frac{B(\alpha + n_m)}{B(\alpha)}\nonumber
%\end{eqnarray}
%%\begin{flalign}
%%&p(z, w|\alpha, \beta) = \nonumber\\
%%&\prod_{k=1}^{K} \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})} \frac{\prod_{v=1}^V \Gamma(\beta_{v} + n_{k,v})}{\Gamma(\sum_{v=1}^V \beta_{v} + n_{k,v})}
%%\prod_{m=1}^{M} \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})} \frac{\prod_{k=1}^K \Gamma(\alpha_{k} + n_{m,k})}{\Gamma(\sum_{k=1}^K \alpha_{k} + n_{m,k} )}\nonumber\\
%%&p(z_{-i}, w_{-i}|\alpha, \beta) = \nonumber\\
%%&\prod_{k=1}^{K} \frac{\Gamma(\sum_{v=1}^V \beta_{v})}{\prod_{v=1}^V \Gamma(\beta_{v})} \frac{\prod_{v=1}^V \Gamma(\beta_{v} + n_{k,v})}{\Gamma(\sum_{v=1}^V \beta_{v} + n_{k,v})}
%%\prod_{m=1}^{M} \frac{\Gamma(\sum_{k=1}^K \alpha_{k})}{\prod_{k=1}^K \Gamma(\alpha_{k})} \frac{\prod_{k=1}^K \Gamma(\alpha_{k} + n_{m,k})}{\Gamma(\sum_{k=1}^K \alpha_{k} + n_{m,k} )}\nonumber
%%\end{flalign}
At this point, we can observe that the form of $p(z, w|\alpha, \beta)$ is similar to the Dice Toss toy example discussed earlier. The derivation of the markov chain updates will be summarized and simplified since we have already seen the dice toss example. Hence, deriving the chain updates.
\begin{eqnarray}
p(z_i=k|z_{-i}, w, \alpha, \beta) &=& \frac{p(w, z|\alpha, \beta)}{p(z_{-i}, w|\alpha, \beta)}\nonumber\\
&=& \frac{p(w, z|\alpha, \beta)}{p(z_{-i}, w|\alpha, \beta)}\nonumber\\
&=& \frac{p(w|z, \beta) p(z|\alpha)}{p(z_{-i}, w_{-i}|\alpha, \beta)p(w_i|\alpha, \beta)}\nonumber\\
&=& \frac{p(w|z, \beta) p(z|\alpha)}{p(w_{-i}|z_{-i}, \beta) p(z_{-i}|\alpha) p(w_i|\alpha, \beta)}\nonumber\\
&\propto& \frac{p(w|z, \beta) p(z|\alpha)}{p(w_{-i}|z_{-i}, \beta) p(z_{-i}|\alpha)}\nonumber
%&\propto& \frac{\prod_{k=1}^{K} \frac{B(\beta + n_k)}{B(\beta)} \prod_{m=1}^{M} \frac{B(\alpha + n_m)}{B(\alpha)}}{\prod_{k=1}^{K} \frac{B(\beta + n_{k}^{-i})}{B(\beta)} \prod_{m=1}^{M} \frac{B(\alpha + n_{m}^{-i})}{B(\alpha)}}\nonumber\\
%&\propto& \frac{\prod_{k=1}^{K} B(\beta + n_k) \prod_{m=1}^{M} B(\alpha + n_m)}{\prod_{k=1}^{K} B(\beta + n_{k}^{-i}) \prod_{m=1}^{M} B(\alpha + n_{m}^{-i})}\nonumber
\end{eqnarray}
\begin{equation}
\label{eqn:update}
\propto \frac{\beta_v + n_{k,v}}{\sum_{v=1}^V \beta_v + n_{k,v}}.\frac{\alpha_k + n_{m,k}}{\sum_{k=1}^K \alpha_k + n_{m,k}}
\end{equation}
Equation \ref{eqn:update} follows Equation 6 and 7 earlier in the dice toss example. Now with Equation 8, 9 and 10, we are ready to look at Algorithm \ref{alg:1}. Algorithm \ref{alg:1} outputs the parameters that tells us the topic distribution in documents and topic distribution in words. Refer to Table \ref{table:4} for a summarize comparison with PLSA.
%\begin{eqnarray}
%\frac{\prod_{k=1}^{K} B(\beta + n_k)}{\prod_{k=1}^{K} B(\beta + n_{k,-i})} &=& \prod_{k=1}^{K} \frac{B(\beta + n_k)}{B(\beta + n_{k,-i})}\nonumber\\
%\prod_{k=1}^{K} \frac{B(\beta + n_k)}{B(\beta + n_{k,-i})} &=& \prod_{k=1}^{K} \frac{\prod_{v=1}^V \Gamma(\beta_v + n_{k,v}) \Gamma(\sum_{v=1}^V \beta_v + n_{k,v}^{-i})}{\Gamma(\sum_{v=1}^V \beta_v + n_{k,v})\prod_{v=1}^V \Gamma(\beta_v + n_{k,v}^{-i})}\nonumber\\
%&=& \prod_{k=1}^{K} \frac{\prod_{v=1}^V \Gamma(\beta_v + n_{k,v}) \Gamma(\sum_{v=1}^V \beta_v + n_{k,v}^{-i})}{\prod_{v=1}^V \Gamma(\beta_v + n_{k,v}^{-i})\Gamma(\sum_{v=1}^V \beta_v + n_{k,v})}\nonumber
%\end{eqnarray}
%\subsection{PLSA vs LDA}
%Despite Blei's claim that LDA performs better by showing a lower perplexity language model than PLSA, it is difficult to understand the differences between PLSA and LDA. \cite{SIGIR:2003:girolami} shows the main difference between PLSA and LDA is the technique used to search for the optimized parameters. In other words, PLSA and LDA achieves the same effect of optimizing similar objective function using different optimization technique.
\begin{algorithm}[htbp]
\caption{LDA}
\label{alg:1}
\begin{algorithmic}
\STATE Initialize $z[M][N]$, $nkv[K,V]$ and $nmk[M,K]$ arrays to 0
\STATE Initialize $\beta[V]$ and $\alpha[K]$ to 1
\STATE $docs[M][N] \leftarrow$ read in documents
\FOR{$m \leftarrow 1$ to $M$}
    \FOR{$n \leftarrow 1$ to $N$}
        \STATE $k \leftarrow$ a random number between $1$ and $K$
        \STATE $v \leftarrow docs[m][n]$
        \STATE $nkv[k, v] \leftarrow nkv[k, v] + 1$
        \STATE $nmk[m, k] \leftarrow nmk[m, k] + 1$
        \STATE $z[m][n] \leftarrow k$
    \ENDFOR
\ENDFOR
\WHILE{run for 1000 iterations}
    \FOR{$m \leftarrow 1$ to $M$}
        \FOR{$n \leftarrow 1$ to $N$}
            \STATE $k \leftarrow z[m][n]$
            \STATE $v \leftarrow docs[m][n]$
            \STATE \COMMENT{The subtraction here corresponds to $z_{-i}$}
            \STATE $nkv[k, v] \leftarrow nkv[k, v] - 1$
            \STATE $nmk[m, k] \leftarrow nmk[m, k] - 1$
            \FOR{$k \leftarrow 1$ to $K$}
                \STATE $p[k] \leftarrow
                    \frac{\beta[v] * nkv[k,v]}{\sum_{v=1}^V \beta[v] + nkv[k,v]} *
                    \frac{\alpha[k] + nmk[m,k]}{\sum_{k=1}^K \alpha[k] + nmk[m,k]}$
            \ENDFOR
            \FOR{$k \leftarrow 2$ to $K$}
                \STATE $p[k] \leftarrow p[k] + p[k-1]$
            \ENDFOR
            \STATE $u \leftarrow$ a random number between $0$ and $1$
            \STATE $u \leftarrow u*p[K]$
            \FOR{$k \leftarrow 1$ to $K$}
                \IF{p[k] > u}
                    \STATE break and use current $k$
                \ENDIF
            \ENDFOR
            \STATE $nkv[k, v] \leftarrow nkv[k, v] + 1$
            \STATE $nmk[m, k] \leftarrow nmk[m, k] + 1$
            \STATE $z[m][n] \leftarrow k$
        \ENDFOR
    \ENDFOR
\ENDWHILE
\STATE Initialize $\phi[K,V]$ and $\theta[M,K]$
\FOR{$k \leftarrow 1$ to $K$}
    \FOR{$v \leftarrow 1$ to $V$}
        \STATE $\phi[k,v] \leftarrow \frac{nkv[k,v] + \beta[v]}{\sum_{v=1}^V nkv[k,v] + \beta[v]}$
    \ENDFOR
    \FOR{$m \leftarrow 1$ to $M$}
        \STATE $\theta[m,k] \leftarrow \frac{nmk[m,k] + \alpha[k]}{\sum_{k=1}^K nmk[m,k] + \alpha[k]}$
    \ENDFOR
\ENDFOR
\RETURN $\phi[K,V]$ and $\theta[M,K]$.
\end{algorithmic}
\end{algorithm}
\section{Hierarchical Latent Dirichlet Allocation}
\label{sec:hlda}
The LDA presented in previous section fails to address one issue: how many topics to use for a text corpus. Blei proposed a Hierarchical Latent Dirichlet Allocation (hLDA) based on nonparametric Bayesian statistics \cite{blei2009ncrp}. In nonparametric Bayesian statistics, the probability of observing a word in a document follows the probability distribution of stochastic processes instead of dirichlet distributions. The stochastic processes proposed in hLDA is a combination of two classical stochastic processes. The first stochastic process known as the Chinese restaurant process allows the number of topics to grow infinitely as many as required. The second stochastic process known as the stick breaking process allows for the division of topics into specialized topics to form a hierarchy of topics. Putting this two stochastic processes together, Blei call it the nested Chinese restaurant process \cite{blei2009ncrp}. Figure \ref{fig:3} shows an example of the words associated with the hierarchical topics of hLDA. I took this example from \cite{citeulike:432492}.
\begin{figure}[htbp]
    \centering
    \epsfig{file=hlda.eps, scale=0.65}
    \caption{Hierarchical Latent Dirichlet Allocation}
    \label{fig:3}
\end{figure}
\section{Conclusion}
\label{sec:conclusion}
I have presented in detail, the formulation of LDA and the derivation of the Gibbs Sampling technique for solving LDA. The derivation is necessary because the math equations are hard to understand without working through it ourselves. I believe my derivation of LDA Gibbs Sampling is much more thorough than \cite{griffiths_finding_2004} and \cite{citeulike:3057616}. This will be useful for other researchers who are relatively new to Bayesian parameter learning.

In earlier section, LSA and PLSA was presented because of their incremental advances leading to the invention of LDA. Then I have briefly discussed hLDA. Although the mathematical formulation of LSA, PLSA and LDA are different, they are fundamentally performing the same task, grouping similar terms and documents together. Whether is it algebraic method or probabilistic method, all mathematical techniques aim to achieve the similar objective of representing unstructured data into structured and well organized knowledge. The semantics of linear algebra is significantly much simpler than PLSA and LDA. PLSA also is much simpler than LDA. However, probabilistic representation is much simpler to understand when we want to interpret the results. Having prior knowledge of the text corpus and using the bayesian formalism in PLSA and LDA allow us to process the text corpus quickly. One notable difference between LSA and LDA is that LDA allows the number of topics to exceed the number of documents which expands the semantic space rather than reducing it. However, the results of expanding semantic space requires further validation.

One question remains in my mind. Since the mathematics of LDA is so much harder, what makes it different from PLSA? The difference is not obvious since both techniques uses probabilities for defining the topics of documents and words. Girolami addressed this issue in \cite{SIGIR:2003:girolami} and explained that LDA introduces dirichlet priors which avoids an overfitting problem in the text corpus. Another issue that I have not addressed is how does such document classification improve IR results? Wei and Croft have shown that LDA does improve IR results \cite{citeulike:1109893}. Finally, I have not give an in-depth explanation of hLDA. hLDA builds on the field of nonparametric Bayesian statistics which requires a thorough theoretical foundation in this area. hLDA was proposed a year later after LDA but the research community have readily adopted LDA instead of hLDA. This is because the research community have not fully understood how to interpret the topics discovered by LDA, hence, the usefulness of hLDA is still limited by our understanding of text.
\bibliographystyle{abbrv}
\bibliography{ir}
\appendix
I wrote these programs myself.
\section{Running Programs}
\subsection{PLSA for Toy Example}
\begin{enumerate}
\item Run Matlab.
\item Run the script EM from the directory $\backslash$matlab$\backslash$.
\item Run the script a few times to observe the random results generated.
\end{enumerate}
This random results obtained motivated me to use a larger text corpus in the next section.
\subsection{PLSA for wikipedia articles}
\begin{enumerate}
\item Run Matlab.
\item Run the script PLSA from the directory $\backslash$matlab$\backslash$.
\item This will take some time.
\end{enumerate}
\subsection{LDA}
I wrote LDA with reference to an existing C++ implementation of Gibbs Sampling from \cite{citeulike:3057616}.
\begin{enumerate}
\item Run TopicModel\textbackslash LDAGibbsSampling\textbackslash bin\textbackslash Release\\
\textbackslash LDAGibbsSampling.exe
\item This is quite fast.
\end{enumerate}
\subsection{LDA Gutenberg corpus}
\begin{enumerate}
\item Run TopicModel\textbackslash Gutenberg\textbackslash bin\textbackslash Release\\
\textbackslash Gutenberg.exe <no. of topics>
\item This is will take some time.
\item results store in results.<no. of topics>.topics.txt
\end{enumerate}
The results are shown here.
\begin{table}[htbp]
\tiny
\begin{tabular}{|p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|p{1.5cm}|}
\hline
	Topic 1 & Topic 2 & Topic 3 & Topic 4 &	Topic 5\\
    (Nature) & (Western Lifestyle) & (Politics \& History) & (Casual) &	(Biology)\\
\hline
	species	&	coffee	&	great	&	said	&	bone	\\
	water	&	co	&	king	&	man	&	disease	\\
	great	&	house	&	war	&	time	&	tissue	\\
	light	&	pounds	&	government	&	know	&	skin	\\
	found	&	de	&	states	&	see	&	blood	\\
	time	&	trade	&	century	&	good	&	treatment	\\
	see	&	states	&	made	&	come	&	infection	\\
	body	&	united	&	sidenote	&	mr	&	joint	\\
	work	&	illustration	&	time	&	day	&	patient	\\
	man	&	york	&	france	&	made	&	cases	\\
	illustration	&	tea	&	england	&	go	&	form	\\
	form	&	cafe	&	state	&	old	&	nerve	\\
	feet	&	roasting	&	church	&	say	&	met	\\
	part	&	years	&	years	&	where	&	fig	\\
	thus	&	made	&	people	&	thought	&	tissues	\\
	animals	&	water	&	french	&	eyes	&	glands	\\
	made	&	london	&	part	&	hand	&	bones	\\
	life	&	cup	&	work	&	room	&	pain	\\
	where	&	green	&	german	&	went	&	result	\\
	seen	&	time	&	general	&	came	&	wound	\\
\hline
\end{tabular}
\\
\begin{tabular}{|p{3.1cm}|p{0.8cm}|p{0.8cm}|p{0.8cm}|p{0.8cm}|p{0.8cm}|}
\hline
Title & Nature & Western Lifestyle & Politics \& History & Casual & Biology\\
\hline
A Book of Natural History	&	87.91\%	&	0.05\%	&	0.05\%	&	11.97\%	&	0.02\%	\\
\hline
A Tale of Two Cities	&	0.02\%	&	0.00\%	&	0.04\%	&	99.94\%	&	0.00\%	\\
\hline
Adventures of Tom Sawyer	&	0.03\%	&	0.01\%	&	0.06\%	&	99.90\%	&	0.01\%	\\
\hline
Alice In Wonderland	&	0.11\%	&	0.01\%	&	0.07\%	&	99.79\%	&	0.02\%	\\
\hline
All About Coffee	&	3.83\%	&	85.06\%	&	5.46\%	&	5.65\%	&	0.00\%	\\
\hline
An Introduction to the History of Western Europe	&	0.00\%	&	0.00\%	&	99.93\%	&	0.07\%	&	0.00\%	\\
\hline
Current History, A Monthly Magazine	&	0.02\%	&	0.01\%	&	79.42\%	&	20.55\%	&	0.00\%	\\
\hline
Discourse on the method of rightly conducting the reason and seeking truth in the sciences	&	53.25\%	&	0.02\%	&	 13.23\%	&	32.75\%	&	0.74\%	\\
\hline
Dracula	&	0.00\%	&	0.01\%	&	0.00\%	&	99.98\%	&	0.00\%	\\
\hline
Emma	&	0.00\%	&	0.00\%	&	0.00\%	&	99.99\%	&	0.00\%	\\
\hline
Encyclopaedia Britannica, 11th Edition	&	19.66\%	&	0.23\%	&	80.08\%	&	0.00\%	&	0.02\%	\\
\hline
Frankenstein	&	5.52\%	&	0.01\%	&	1.16\%	&	93.29\%	&	0.02\%	\\
\hline
General Science	&	98.53\%	&	1.42\%	&	0.04\%	&	0.00\%	&	0.01\%	\\
\hline
History of the United States	&	0.01\%	&	0.00\%	&	99.90\%	&	0.09\%	&	0.00\%	\\
\hline
Jane Eyre	&	0.21\%	&	0.02\%	&	0.00\%	&	99.77\%	&	0.00\%	\\
\hline
Les Miserables	&	0.65\%	&	0.00\%	&	1.69\%	&	97.65\%	&	0.01\%	\\
\hline
Manners, Custom and Dress During the Middle Ages and During the Renaissance Period	&	4.12\%	&	0.00\%	&	86.17\%	 &	9.71\%	&	0.01\%	\\
\hline
Manual of Surgery	&	8.76\%	&	0.00\%	&	0.01\%	&	0.01\%	&	91.21\%	\\
\hline
Metamorphosis	&	0.04\%	&	0.02\%	&	0.19\%	&	99.73\%	&	0.02\%	\\
\hline
Music Notation and Terminology	&	99.88\%	&	0.01\%	&	0.05\%	&	0.05\%	&	0.01\%	\\
\hline
Natural History of the Mammalia of India and Ceylon	&	99.93\%	&	0.01\%	&	0.00\%	&	0.06\%	&	0.00\%	\\
\hline
On the origin of species	&	99.99\%	&	0.00\%	&	0.00\%	&	0.01\%	&	0.00\%	\\
\hline
Romeo and Juliet	&	0.03\%	&	0.03\%	&	0.01\%	&	99.90\%	&	0.02\%	\\
\hline
The Adventures of Sherlock Holmes	&	2.30\%	&	0.20\%	&	0.56\%	&	96.93\%	&	0.00\%	\\
\hline
The Art of War	&	9.85\%	&	0.02\%	&	76.20\%	&	13.93\%	&	0.01\%	\\
\hline
The Communist Manifesto	&	6.98\%	&	0.07\%	&	92.75\%	&	0.14\%	&	0.06\%	\\
\hline
The Kama Sutra of Vatsyayana	&	24.90\%	&	0.01\%	&	13.44\%	&	61.62\%	&	0.03\%	\\
\hline
The Last Supper	&	20.30\%	&	0.11\%	&	72.47\%	&	7.02\%	&	0.11\%	\\
\hline
The Notebooks of Leonardo Da Vinci	&	92.85\%	&	0.00\%	&	0.80\%	&	6.35\%	&	0.00\%	\\
\hline
The Outline of Science	&	98.24\%	&	0.02\%	&	0.04\%	&	1.67\%	&	0.03\%	\\
\hline
The Practice and Science Of Drawing	&	92.31\%	&	0.00\%	&	0.06\%	&	7.61\%	&	0.01\%	\\
\hline
The Prehistoric World	&	89.38\%	&	0.00\%	&	10.55\%	&	0.06\%	&	0.01\%	\\
\hline
The Romance of Lust	&	0.00\%	&	0.00\%	&	0.00\%	&	99.99\%	&	0.00\%	\\
\hline
The Tempest	&	1.79\%	&	0.07\%	&	10.96\%	&	87.10\%	&	0.08\%	\\
\hline
War and Peace	&	0.00\%	&	0.00\%	&	0.00\%	&	99.99\%	&	0.00\%	\\
\hline
Woman as Decoration	&	40.24\%	&	0.01\%	&	22.98\%	&	36.74\%	&	0.02\%	\\
\hline
\end{tabular}
\end{table}
\end{document}
