Learning Topic Models - Going beyond SVD

Introduction

Developing tools for automatic comprehension and classification of data —web pages, newspaper articles, images, genetic sequences, user ratings — is a holy grail of machine learning. Topic Modeling is an approach that has proved successful in all of the aforementioned settings, though for concreteness here we will focus on uncovering thematic structure of a corpus of documents (see e.g. , ).

In order to learn structure one has to posit the existence of structure, and in topic models one assumes a generative model for a collection of documents. Specifically, each document is represented as a vector of word-frequencies (the bag of words representation). Seminal papers in theoretical CS (Papadimitriou et al. ) and machine learning (Hofmann’s Probabilistic Latent Semantic Analysis ) suggested that documents arise as a convex combination of (i.e. distribution on) a small number of topic vectors, where each topic vector is a distribution on words (i.e. a vector of word-frequencies). Each convex combination of topics thus is itself a distribution on words, and the document is assumed to be generated by drawing $N$ independent samples from it. Subsequent work makes specific choices for the distribution used to generate topic combinations —the well-known Latent Dirichlet Allocation (LDA) model of Blei et al hypothesizes a Dirichlet distribution (see Section 4).

In machine learning, the prevailing approach is to use local search (e.g. ) or other heuristics in an attempt to find a maximum likelihood fit to the above model. For example, fitting to a corpus of newspaper articles may reveal $50$ topic vectors corresponding to, say, politics, sports, weather, entertainment etc., and a particular article could be explained as a $(1/2,1/3,1/6)$-combination of the topics politics, sports, and entertainment. Unfortunately (and not surprisingly), the maximum likelihood estimation is $NP$-hard (see Section 6) and consequently when using this paradigm, it seems necessary to rely on unproven heuristics even though these have well-known limitations (e.g. getting stuck in a local minima ).

The work of Papadimitriou et al (which also formalized the topic modeling problem) and a long line of subsequent work have attempted to give provable guarantees for the problem of learning the model parameters assuming the data is actually generated from it. This is in contrast to a maximum likelihood approach, which asks to find the closest-fit model for arbitrary data. The principal algorithmic problem is the following (see Section 1.1 for more details):

Meta Problem in Topic Modeling: There is an unknown topic matrix $A$ with nonnegative entries that is dimension $n\times r$, and a stochastically generated unknown matrix $W$ that is dimension $r\times m$. Each column of $AW$ is viewed as a probability distribution on rows, and for each column we are given $N\ll n$ i.i.d. samples from the associated distribution.

Goal: Reconstruct $A$ and parameters of the generating distribution for $W$.

The challenging aspect of this problem is that we wish to recover nonnegative matrices $A,W$ with small inner-dimension $r$. The general problem of finding nonnegative factors $A,W$ of specified dimensions when given the matrix $AW$ (or a close approximation) is called the Nonnegative Matrix Factorization (NMF) problem (see , and for a longer history) and it is NP-hard . Lacking a tool to solve such problems, theoretical work has generally relied on the Singular Value Decomposition (SVD) which given the matrix $AW$ will instead find factors $U,V$ with both positive and negative entries. SVD can be used as a tool for clustering – in which case one needs to assume that each document has only one topic. In Papadimitriou et al this is called the pure documents case and is solved under strong assumptions about the topic matrix $A$ (see also and which uses the method of moments instead). Alternatively, other papers use SVD to recover the span of the columns of $A$ (i.e. the topic vectors) , , , which suffices for some applications such as computing the inner product of two document vectors (in the space spanned by the topics) as a measure of their similarity.

These limitations of existing approaches —either restricting to one topic per document, or else learning only the span of the topics instead of the topics themselves—are quite serious. In practice documents are much more faithfully described as a distribution on topics and indeed for a wide range of applications one needs the actual topics and not just their span – such as when browsing a collection of documents without a particular query phrase in mind, or tracking how topics evolve over time (see for a survey of various applications). Here we consider what we believe to be a much weaker assumption – separability. Indeed, this property has already been identified as a natural one in the machine learning community and has been empirically observed to hold in topic matrices fitted to various types of data .

Separability requires that each topic has some near-perfect indicator word – a word that we call the anchor word for this topic— that appears with reasonable probability in that topic but with negligible probability in all other topics (e.g., “soccer” could be an anchor word for the topic “sports”). We give a formal definition in Section 1.1. This property is particularly natural in the context of topic modeling, where the number of distinct words (dictionary size) is very large compared to the number of topics. In a typical application, it is common to have a dictionary size in the thousands or tens of thousands, but the number of topics is usually somewhere in the range from $50$ to $100$. Note that separability does not mean that the anchor word always occurs (in fact, a typical document may be very likely to contain no anchor words). Instead, it dictates that when an anchor word does occur, it is a strong indicator that the corresponding topic is in the mixture used to generate the document.

Recently, we gave a polynomial time algorithm to solve NMF under the condition that the topic matrix $A$ is separable . The intuition that underlies this algorithm is that the set of anchor words can be thought of as extreme points (in a geometric sense) of the dictionary. This condition can be used to identify all of the anchor words and then also the nonnegative factors. Ideas from this algorithm are a key ingredient in our present paper, but our focus is on the question:

What if we are not given the true matrix $AW$, but are instead given a few samples (say, $100$ samples) from the distribution represented by each column?

The main technical challenge in adapting our earlier NMF algorithm is that each document vector is a very poor approximation to the corresponding column of $AW$ —it is too noisy in any reasonable measure of noise. Nevertheless, the core insights of our NMF algorithm still apply. Note that it is impossible to learn the matrix $W$ to within arbitrary accuracy. (Indeed, this is information theoretically impossible even if we knew the topic matrix $A$ and the distribution from which the columns of $W$ are generated.) So we cannot in general give an estimator that converges to the true matrix $W$, and yet we can give an estimator that converges to the true topic matrix $A$! (For an overview of our algorithm, see the first paragraph of Section 3.)

We hope that this application of our NMF algorithm is just a starting point and other theoretical results will start using NMF as a replacement for SVD – just as NMF has come to replace SVD in several applied settings.

Now we precisely define the topic modeling (learning) problem which was informally introduced above. There is an unknown topic matrix $A$ which is dimension $n\times r$ (i.e. $n$ is the dictionary size) and each column of $A$ is a distribution on $[n]$. There is an unknown $r\times m$ matrix $W$ whose each column is itself a distribution (aka convex combination) on $[r]$. The columns of $W$ are i.i.d. samples from a distribution $\mathcal{T}$ which belongs to a known family, e.g., Dirichlet distributions, but whose parameters are unknown. Thus each column of $AW$ (being a convex combination of distributions) is itself a distribution on $[n]$, and the algorithm’s input consists of $N$ i.i.d. samples for each column of $AW$. Here $N$ is the document size and is assumed to be a constant for simplicity. Our algorithm can be easily adapted to work when the documents have different sizes.

The algorithm’s running time will necessarily depend upon various model parameters, since distinguishing a very small parameter from imposes a lower bound on the number of samples needed. The first such parameter is a quantitative version of separability, which was presented above as a natural assumption in context of topic modeling.

An $n\times r$ matrix $A$ is $p$-separable if for each $i$ there is some row $\pi(i)$ of $A$ that has a single nonzero entry which is in the $i^{th}$ column and it is at least $p$.

The next parameter measures the lowest probability with which a topic occurs in the distribution that generates columns of $W$.

Finally, we require that topics stay identifiable despite sampling-induced noise. To formalize this, we define a matrix that will be important throughout this paper:

If $\mathcal{T}$ is the distribution that generates the columns of $W$, then $R(\mathcal{T})$ is defined as an $r\times r$ matrix whose $(i,j)$th entry is $E[X_{i}X_{j}]$ where $X_{1},X_{2},...X_{r}$ is a vector chosen from $\mathcal{T}$.

There is a polynomial time algorithm that learns the parameters of a topic model if the number of documents is at least

where the three numbers $a,p,\gamma$ are as defined above. The algorithm learns the topic-term matrix $A$ up to additive error $\epsilon$. Moreover, when the number of documents is also larger than $O\left(\frac{\log r\cdot r^{2}}{\epsilon^{2}}\right)$ the algorithm can learn the topic-topic covariance matrix $R(\mathcal{T})$ up to additive error $\epsilon$.

As noted earlier, we are able to recover the topic matrix even though we do not always recover the parameters of the column distribution $\mathcal{T}$. In some special cases we can also recover the parameters of $\mathcal{T}$, e.g. when this distribution is Dirichlet, as happens in the popular Latent Dirichlet Allocation (LDA) model . In Section 4.1 we compute a lower bound on the $\gamma$ parameter for the Dirichlet distribution, which allows us to apply our main learning algorithm, and also the parameters of $\mathcal{T}$ can be recovered from the co-variance matrix $R(\mathcal{T})$ (see Section 4.2).

Recently the basic LDA model has been refined to allow correlation among different topics, which is more realistic. See for example the Correlated Topic Model (CTM) and the Pachinko Allocation Model (PAM) . A compelling aspect of our algorithm is that it extends to these models as well: we can learn the topic matrix, even though we cannot always identify $\mathcal{T}$. (Indeed, the distribution $\mathcal{T}$ in the Pachinko is not even identifiable: two different sets of parameters can generate exactly the same distribution)

(i) We rely crucially on separability. But note that this assumption is weaker in some sense than the assumptions in all prior works that provably learn the topic matrix. They assume a single topic per document, which can be seen as a strong separability assumption about $W$ instead of $A$ —in every column of $W$ only one entry is nonzero. By contrast, separability only assumes a similar condition for a negligible fraction —namely, $r$ out of $n$— of rows of $A$. Besides, it is found to actually hold in topic matrices found using current heuristics. (ii) Needless to say, existing theoretical approaches for recovering topic matrix $A$ couldn’t handle topic correlations at all since they only allow one topic per document. (iii) We remark that prior approaches that learn the span of $A$ instead of $A$ needed strong concentration bounds on eigenvalues of random matrices, and thus require substantial document sizes (on the order of the number of words in the dictionary!). By contrast we can work with documents of $O(1)$ size.

Tools for (Noisy) Nonnegative Matrix Factorization

If $B$ does not have row sums of one then $\Gamma(B)$ is equal to $\Gamma(DB)$ where $D$ is the diagonal matrix such that $DB$ has row sums of one.

For example, if the rows of $B$ have disjoint support then $\Gamma(B)=1$ and in general the quantity $\Gamma(B)$ can be thought of a measure of how close two distributions on disjoint sets of rows can be. Note that, if $x$ is an $n$-dimensional real vector, $\|x\|_{2}\leq\|x\|_{1}\leq\sqrt{n}\|x\|_{2}$ and hence (if $\sigma_{min}(B)$ is the smallest singular value of $B$), we have:

In our previous work on nonnegative matrix factorization we defined a different measure of “distance” from singular which is essential to the polynomial time algorithm for NMF:

The following claim clarifies the interrelationships of these latter condition numbers.

2 Noisy Nonnegative Matrix Factorization under Separability

Algorithm for Learning a Topic Model: Proof of Theorem 1.4

First it is important to understand why separability helps in nonnegative matrix factorization, and specifically, the exact role played by the anchor words. Suppose the NMF algorithm is given a matrix $AB$. If $A$ is $p$-separable then this means that $A$ contains a diagonal matrix (up to row permutations). Thus a scaled copy of each row of $B$ is present as a row in $AB$. In fact, if we knew the anchor words of $A$, then by looking at the corresponding rows of $AB$ we could“read off” the corresponding row of $B$ (up to scaling), and use these in turn to recover all of $A$. Thus the anchor words constitute the “key” that “unlocks” the factorization, and indeed the main step of our earlier NMF algorithm was a geometric procedure to identify the anchor words. When one is given a noisy version of $AB$, the analogous notion is “almost anchor” words, which correspond to rows of $AB$ that are “very close” to rows of $B$; see Theorem 2.7.

Now we sketch how to apply these insights to learning topic models. Let $M$ denote the provided term-by-document matrix, whose each column describes the empirical word frequencies in the documents. It is obtained from sampling $AW$ and thus is an extremely noisy approximation to $AW$. Our algorithm starts by forming the Gram matrix $MM^{T}$, which can be thought of as an empirical word-word covariance matrix. In fact as the number of documents increases $\frac{1}{m}MM^{T}$ tends to a limit $Q=\frac{1}{m}E[AWW^{T}A],$ implying $Q=AR(\mathcal{T})A^{T}$. (See Lemma 3.7.) Imagine that we are given the exact matrix $Q$ instead of a noisy approximation. Notice that $Q$ is a product of three nonnegative matrices, the first of which is $p$-separable and the last is the transpose of the first. NMF at first sight seems too weak to help find such factorizations. However, if we think of $Q$ as a product of two nonnegative matrices, $A$ and $R(\mathcal{T})A^{T}$, then our NMF algorithm can at least identify the anchor words of $A$. As noted above, these suffice to recover $R(\mathcal{T})A^{T}$, and then (using the anchor words of $A$ again) all of $A$ as well. See Section 3.1 for details.

Of course, we are not given $Q$ but merely a good approximation to it. Now our NMF algorithm allows us to recover “almost anchor” words of $A$, and the crux of the proof is Section 3.2 showing that these suffice to recover provably good estimates to $A$ and $WW^{T}$. This uses (mostly) bounds from matrix perturbation theory, and interrelationships of condition numbers mentioned in Section 2.

For simplicity we assume the following condition on the topic model, which we will see in Section 3.5 can be assumed without loss of generality:

(*) The number of words, $n$, is at most $4ar/\epsilon$.

Please see Algorithm 1: Main Algorithm for description of the algorithm. Note that $R$ is our shorthand for $\frac{1}{m}WW^{T}$, which as noted converges to $R(\mathcal{T})$ as the number of documents increases.

We first describe how the recovery procedure works in an “idealized” setting (Algorthm 2,Recover with True Anchor Words), when we are given the exact value of $ARA^{T}$ and a set of anchor words – one for each topic. We can permute the rows of $A$ so that the anchor words are exactly the first $r$ words. Therefore $A^{T}=(D,U^{T})$ where $D$ is a diagonal matrix. Note that $D$ is not necessarily the identity matrix (nor even a scaled copy of the identity matrix), but we do know that the diagonal entries are at least $p$. We apply the same permutation to the rows and columns of $Q$. As shown in Figure 1, if we look at the submatrix formed by the first $r$ rows and $r$ columns, it is exactly $DRD$. Similarly, the submatrix consisting of the first $r$ rows is exactly $DRA^{T}$. We can use these two matrices to compute $R$ and $A$, in this idealized setting (and we will use the same basic strategy in the general case, but need only be more careful about how we analyze how errors compound in our algorithm).

Our algorithm has exact knowledge of the matrices $DRD$ and $DRA^{T}$, and so the main task is to recover the diagonal matrix $D$. Given $D$, we can then compute $A$ and $R$ (for the Dirichlet Allocation we can also compute its parameters - i.e. the $\vec{\alpha}$ so that $R(\alpha)=R$). The key idea to this algorithm is that the row sums of $DR$ and $DRA^{T}$ are the same, and we can use the row sums of $DR$ to set up a system of linear constraints on the diagonal entries of $D^{-1}$.

When the matrix $Q$ is exactly equal to $ARA^{T}$ and we know the set of anchor words, Recover with True Anchor Words outputs $A$ and $R$ correctly.

Proof: The Lemma is straight forward from Figure 1 and the procedure. By Figure 1 we can find the exact value of $DRA^{T}$ and $DRD$ in the matrix $Q$. Step 2 of recover computes $DR\vec{1}$ by computing $DRA^{T}\vec{1}$. The two vectors are equal because $A$ is the topic-term matrix and its columns sum up to 1, in particular $A^{T}\vec{1}=\vec{1}$.

In Step 3, since $R$ is invertible by Lemma 2.2, $D$ is a diagonal matrix with entries at least $p$, the matrix $DRD$ is also invertible. Therefore there is a unique solution $\vec{z}=(DRD)^{-1}DR\vec{1}=D^{-1}\vec{1}$. Also $D\vec{z}=\vec{1}$ and hence $D\mbox{Diag}(z)=I$. Finally, using the fact that $D\mbox{Diag}(z)=I$, the output in step 4 is just $(DR)^{-1}DRA^{T}=A^{T}$, and the output in step 5 is equal to $R$. $\blacksquare$

2 Recover R𝑅R and A𝐴A with Almost Anchor Words

What if we are not given the exact anchor words, but are given words that are “close” to anchor words? As we noted, in general we cannot hope to recover the true anchor words, but even a good approximation will be enough to recover $R$ and $A$.

When we restrict $A$ to the rows corresponding to “almost” anchor words, the submatrix will not be diagonal. However, it will be close to a diagonal in the sense that the submatrix will be a diagonal matrix $D$ multiplied by $E$, and $E$ is close to the identity matrix (and the diagonal entries of $D$ are at least $\Omega(p)$). Here we analyze the same procedure as above and show that it still recovers $A$ and $R$ (approximately) even when given “almost” anchor words instead of true anchor words. For clarity we state the procedure again in Algorithm 3: Recover with Almost Anchor Words. The guarantees at each step are different than before, but the implementation of the procedure is the same. Notice that here we permute the rows of $A$ (and hence the rows and columns of $Q$) so that the “almost” anchor words returned by Theorem 2.6 appear first and the submatrix $A$ on these rows is equal to $DE$.

Here, we still assume that the matrix $Q$ is exactly equal to $ARA^{T}$ and hence the first $r$ rows of $Q$ form the submatrix $DERA^{T}$ and the first $r$ rows and columns are $DERE^{T}D$. The complication here is that $\mbox{Diag}(z)$ is not necessarily equal to $D^{-1}$, since the matrix $E$ is not necessarily the identity. However, we can show that $\mbox{Diag}(z)$ is ”close” to $D^{-1}$ if $E$ is suitably close to the identity matrix – i.e. given good enough proxies for the anchor words, we can bound the error of the above recovery procedure. We write $E=I+Z$. Intuitively when $Z$ has only small entries $E$ should behave like the identity matrix. In particular, $E^{-1}$ should have only small off-diagonal entries. We make this precise through the following lemmas:

Let $E=I+Z$ and $\sum_{i,j}|Z_{i,j}|=\epsilon<1/2$, then $E^{-1}\vec{1}$ is a vector with entries in the range $[1-2\epsilon,1+2\epsilon]$.

Proof: $E$ is clearly invertible because the spectral norm of $Z$ is at most $1/2$. Let $\vec{b}=E^{-1}\vec{1}$. Since $E=I+Z$ we multiply $E$ on both sides to get $\vec{b}+Z\vec{b}=\vec{1}$. Let $b_{max}$ be the largest absolute value of any entry of $b$ ($b_{max}=\max|b_{i}|$). Consider the entry $i$ where $b_{max}$ is achieved, we know $b_{max}=|b_{i}|\leq 1+|(Zb)_{i}|\leq 1+\sum_{j}|Z_{i,j}||b_{j}|\leq 1+\epsilon b_{max}.$ Thus $b_{max}\leq 1/(1-\epsilon)\leq 2$. Now all the entries in $Z\vec{b}$ are within $2\epsilon$ in absolute value, and we know that $\vec{b}=\vec{1}+Z\vec{b}$. Hence all the entries of $b$ are in the range $[1-2\epsilon,1+2\epsilon]$, as desired. $\blacksquare$

Proof: Without loss of generality, we can consider just the first column of $E^{-1}-I$, which is equal to $(E^{-1}-I)\vec{e_{1}}$, where $\vec{e_{1}}$ is the indicator vector that is one on the first coordinate and zero elsewhere.

The approach is similar to that in Lemma 3.2. Let $\vec{b}=(E^{-1}-I)\vec{e_{1}}$. Left multiply by $E=(I+Z)$ and we obtain $\vec{b}+Z\vec{b}=-Z\vec{e_{1}}$. Hence $\vec{b}=-Z(\vec{b}+\vec{e_{1}})$. Let $b_{max}$ be the largest absolute value of entries of $\vec{b}$ ($b_{max}=\max|b_{i}|$). Let $i$ be the entry in which $b_{max}$ is achieved. Then

Therefore $b_{max}\leq\epsilon/(1-\epsilon)\leq 2\epsilon$. Further, the $\|\vec{b}\|_{1}\leq\|Z\vec{e_{1}}\|_{1}+\|Z\vec{b}\|_{1}\leq\epsilon+2\epsilon^{2}\leq 2\epsilon$. $\blacksquare$

Now we are ready to show that the procedure Recover with Almost Anchor Words succeeds when given ”almost” anchor words:

Proof: Since $Q$ is exactly $ARA^{T}$, our algorithm is given $DERA^{T}$ and $DERE^{T}D$ with no error. In Step 3, since $D$, $E$ and $R$ are all invertible, we have

Ideally we would want $\mbox{Diag}(z)=D^{-1}$, and indeed $D\mbox{Diag}(z)=\mbox{Diag}((E^{T})^{-1}\vec{1})$. From Lemma 3.2, the vector $(E^{T})^{-1}\vec{1}$ has entries in the range $[1-2\epsilon,1+2\epsilon]$, thus each entry of $\mbox{Diag}(z)$ is within a $(1\pm 2\epsilon)$ multiplicative factor from the corresponding entry in $D^{-1}$.

Consider the output in Step 4. Since $D$, $E$, $R$ are invertible, the first output is

For each $j$, $\|\vec{e_{j}}^{T}(D\mbox{Diag}(z))^{-1}(E^{T})^{-1}-\vec{e_{j}}^{T}\|_{1}\leq 5\epsilon$

The last term can be bounded by $2\epsilon$. Consider the first term on the right hand side: The vector $\vec{e_{1}}^{T}(D\mbox{Diag}(z))^{-1}-\vec{e_{1}}^{T}$ has one non-zero entry (the first one) whose absolute value is at most $3\epsilon$. Hence, from Lemma 3.3 the first term can be bounded by $6\epsilon^{2}\leq 3\epsilon$, and this implies the claim. $\blacksquare$

The main idea of the proof is to write $DERE^{T}D+V$ as $DER(E^{T}+V^{\prime})D$. In this way the error $V$ can be translated to an error $V^{\prime}$ on $E$ and Lemma 3.4 can be applied. The error $U$ can be handled similarly.

Hence $DERE^{T}D+V=DER(E^{T}+V^{\prime})D$ and the additive error for $DERE^{T}D$ can be transformed into error in $E$, and we will be able to apply the analysis in Lemma 3.4.

Similarly, we can express the error term $U$ as $U=DERU^{\prime}$. Entries of $U^{\prime}$ have absolute value at most $8\epsilon_{1}r/\gamma p^{2}$. The right hand side of the equation in step 3 is equal to $DER\vec{1}+U\vec{1}$ so the error is at most $\epsilon_{1}$ per entry. Following the proof of Lemma 3.4, we know $\mbox{Diag}(z)D$ has diagonal entries within $1\pm\left(2\epsilon+16\epsilon_{2}/\gamma p^{3}+2\epsilon_{1}\right)$.

Now we consider the output. The output for $A^{T}$ is equal to

Similarly, the output of $R$ is equal to $\mbox{Diag}(z)(DERE^{T}D+V)\mbox{Diag}(z)$. Again we write $\mbox{Diag}(z)D=I+Z_{1}$ and $E=I+Z_{2}$. The extra term $\mbox{Diag}(z)V\mbox{Diag}(z)$ is small because the entries of $z$ are at most to $2/p$ (otherwise $\mbox{Diag}(z)D$ won’t be close to identity). The error can be bounded by $O(\epsilon+(ra\epsilon_{2}/p^{3}+\epsilon_{1}r/p^{2})/\gamma)$. $\blacksquare$

Now in order to prove our main theorem we just need to show that when number of documents is large enough, the matrix $Q$ is close to the $ARA^{T}$, and plug the error bounds into Lemma 3.6.

3 Error Bounds for Q𝑄Q

Here we show that the matrix $Q$ indeed converges to $\frac{1}{m}AWW^{T}A^{T}=ARA^{T}$ when $m$ is large enough.

Proof: We shall first show that the expectation of $Q$ is equal to $ARA^{T}$ where $R$ is $\frac{1}{m}WW^{T}$. Then by concentration bounds we show that entries of $Q$ are close to their expectations. Notice that we can also hope to show that $Q$ converges to $AR(\mathcal{T})A^{T}$. However in that case we will not be able to get the inverse polynomial relationship with $N$ (indeed, even if $N$ goes to infinity it is impossible to learn $R(\mathcal{T})$ with only one document). Replacing $R(\mathcal{T})$ with the empirical $R$ allows our algorithm to perform better when the number of words per document is larger.

4 Proving the Main Theorem

When $\epsilon_{Q}<\epsilon p^{3}\gamma/a^{2}r^{3}$ the error is bounded by $\epsilon$ . In this case we need

The latter constraint comes from Lemma 2.2.

To get within $\epsilon$ additive error for the parameter $\alpha$, we further need $R$ to be close enough to the variance-covariance matrix of the document-topic distribution, which means $m$ is at least

5 Reducing Dictionary Size

Above we assumed that the number of distinct words is small. Here, we give a simple gadget that shows in the general case we can assume that this is the case at the loss of an additional additive $\epsilon$ in our accuracy:

The general case can be reduced to an instance in which there are at most $4ar/\epsilon$ words all of which (with at most one exception) occur with probability at least $\epsilon/4ar$.

Proof: In fact, we can collect all words that occur infrequently and “merge” all of these words into a aggregate word that we will call the runoff word. To this end, we call a word large if it appears more than $\epsilon mN/3ar$ times in $m=\frac{100ar\log n}{N\epsilon}$ documents, and otherwise we call it small. Indeed, with high probability all large words are words that occur with probability at least $\epsilon/4ar$ in our model. Also, all words that has a entry larger than $\epsilon$ in the corresponding row of $A$ will appear with at least $\epsilon/ar$ probability, and is thus a large word with high probability. We can merge all small words (i.e. rename all of these words to a single, new word). Hence we can apply the above algorithm (which assumed that there are not too many distinct words). After we get a result with the modified documents we can ignore the runoff words and assign weight for all the small words. The result will still be correct up to $\epsilon$ additive error. $\blacksquare$

The Dirichlet Subcase

Here we demonstrate that the parameters of a Dirichlet distribution can be (robustly) recovered from just the covariance matrix $R(\mathcal{T})$. Hence an immediate corollary is that our main learning algorithm can recover both the topic matrix $A$ and the distribution that generates columns of $W$ in a Latent Dirichlet Allocation (LDA) Model , provided that $A$ is separable. We believe that this algorithm may be of practical use, and provides the first alternative to local search and (unproven) approximation procedures for this inference problem , , .

where $\Gamma$ is the Gamma function. In particular, when all the $\alpha_{i}$’s are equal to one, the Dirichlet Distribution is just the uniform random distribution over the probability simplex.

The expectation and variance of $\theta_{i}$’s are easy to compute given the parameters $\alpha$. We denote $\alpha_{0}=\left\lVert\alpha\right\rVert_{1}=\sum_{i=1}^{r}\alpha_{i}$, then the ratio $\alpha_{i}/\alpha_{0}$ should be interpreted as the “size” of the $i$-th variable $\theta_{i}$, and $\alpha_{0}$ shows whether the distributions is concentrated in the interior (when $\alpha_{0}$ is large) or near the boundary (when $\alpha_{0}$ is small). The first two moments of Dirichlet Distribution is listed as below:

Suppose the Dirichlet distribution has $\max\alpha_{i}/\min\alpha_{i}=a$ and the sum of parameters is $\alpha_{0}$; we give an algorithm that computes close estimates to the vector of parameters $\alpha$ given a sufficiently close estimate to the co-variance matrix $R(\mathcal{T})$ (Theorem 4.3). Combining this with Theorem 1.4, we obtain the following corollary:

There is an algorithm that learns the topic matrix $A$ with high probability up to an additive error of $\epsilon$ from at most

documents sampled from the LDA model and runs in time polynomial in $n$, $m$. Furthermore, we also recover the parameters of the Dirichlet distribution to within an additive $\epsilon$.

There is a well-known meta-principle that if a matrix $W$ is chosen by picking its columns independently from a fairly diffuse distribution, then it will be far from low rank. However, our analysis will require us to prove an explicit lower bound on $\Gamma(R(\mathcal{T}))$. We now prove such a bound when the columns of $W$ are chosen from a Dirichlet distribution with parameter vector $\alpha$. We note that it is easy to establish such bounds for other types of distributions as well. Recall that we defined $R(\mathcal{T})$ in Section 1, and here we will abuse notation and throughout this section we will denote by $R(\alpha)$ the matrix $R(\mathcal{T})$ where $\mathcal{T}$ is a Dirichlet distribution with parameter $\alpha$.

Let $\alpha_{0}=\sum_{i=1}^{r}\alpha_{i}$. The mean, variance and co-variance for a Dirichlet distribution are well-known, from which we observe that $R(\alpha)_{i,j}$ is equal to $\frac{\alpha_{i}\alpha_{j}}{\alpha_{0}(\alpha_{0}+1)}$ when $i\neq j$ and is equal to $\frac{\alpha_{i}(\alpha_{i}+1)}{\alpha_{0}(\alpha_{0}+1)}$ when $i=j$.

Proof: As the entries $R(\alpha)_{i,j}$ is $\frac{\alpha_{i}\alpha_{j}}{\alpha_{0}(\alpha_{0}+1)}$ when $i\neq j$ and $\frac{\alpha_{i}(\alpha_{i}+1)}{\alpha_{0}(\alpha_{0}+1)}$ when $i=j$, after normalization $R(\alpha)$ is just the matrix $D^{\prime}=\frac{1}{\alpha_{0}+1}\left(\alpha\times(1,1,...,1)+I\right)$ where $\times$ is outer product and $I$ is the identity matrix.

Let $x$ be a vector such that $|x|_{1}=1$ and $|D^{\prime}x|_{1}$ achieves the minimum in $\Gamma(R(\alpha))$ and let $I=\{i|x_{i}\geq 0\}$ and let $J=\bar{I}$ be the complement. We can assume without loss of generality that $\sum_{i\in I}x_{i}\geq|\sum_{i\in J}x_{i}|$ (otherwise just take $-x$ instead). The product $D^{\prime}x$ is $\frac{\sum x_{i}}{\alpha_{0}+1}\alpha+\frac{1}{\alpha_{0}+1}x$. The first term is a nonnegative vector and hence for each $i\in I$, $(D^{\prime}x)^{i}\geq 0$. This implies that

2 Recovering the Parameters of a Dirichlet Distribution

Proof: The $\alpha_{i}/\alpha_{0}$’s all have error at most $\epsilon_{R}$. The value $u$ is $\frac{\alpha_{i}}{\alpha_{0}}\frac{\alpha_{i}+1}{\alpha_{0}+1}\pm\epsilon_{R}$ and the value $v$ is $\alpha_{i}/\alpha_{0}\pm\epsilon_{R}$. Since $v\geq 1/ar$ we know the error for $u/v$ is at most $2ar\epsilon_{R}$. Finally we need to bound the denominator $\frac{\alpha_{i}+1}{\alpha_{0}+1}-\frac{\alpha_{i}}{\alpha_{0}}>\frac{1}{2(\alpha_{0}+1)}$ (since $\frac{\alpha_{i}}{\alpha_{0}}\leq 1/r\leq 1/2$). Thus the final error is at most $5ar(\alpha_{0}+1)\epsilon_{R}$. $\blacksquare$

Obtaining Almost Anchor Words

In this section, we prove Theorem 2.7, which we restate here:

A point $M^{\prime j}$ is $(\delta,\epsilon)$-close to $M^{\prime i}$ if and only if

We also consider all points that a row $M^{\prime j}$ is close to, this is called the neighborhood of $M^{\prime j}$.

The $(\delta,\epsilon)$-neighborhood of $M^{\prime j}$ are the rows $M^{\prime i}$ such that $M^{\prime j}$ is $(\delta,\epsilon)$-close to $M^{\prime i}$.

For each point $M^{\prime j}$, we know its original (unperturbed) point $M_{j}$ is in a convex combination of $W^{i}$’s: $M^{j}=\sum_{i=1}^{r}A_{j,i}W^{i}$. Separability implies that for any column index $i$ there is a row $f(i)$ in $A$ whose only nonzero entry is in the $i^{th}$ column. Then $M^{f(i)}=W^{i}$ and consequently $\|M^{\prime f(i)}-W^{i}\|_{1}<\epsilon$. Let us call these rows $M^{\prime f(i)}$ for all $i$ the canonical rows. From the above description the following claim is clear.

and we can bound the right hand side by $2\epsilon$. $\blacksquare$

Our goal is to show that a row is a robust loner if and only if it is close to some row in $W$. The following lemma establishes one direction:

If $A_{j,t}$ is smaller than $1-10\epsilon/\gamma$, the point $M^{\prime j}$ cannot be $(6\epsilon/\gamma,2\epsilon)$-close to the canonical row that corresponds to $W^{t}$.

If $A_{j,t}$ is smaller than $1-10\epsilon/\gamma$ for all $t$, the row $M^{\prime j}$ cannot be a robust loner.

Proof: By the above lemma, we know the canonical rows are not in the $(6\epsilon/\gamma,2\epsilon)$ neighborhood of $M^{\prime j}$. Thus by Claim 5.4 the row is close to the convex hull of canonical rows and cannot be a robust loner. $\blacksquare$

Next we prove the other direction: a canonical row is necessarily a robust loner:

Proof: Suppose $M^{\prime i}$ is a canonical row that corresponds to $W^{t}$. We first observe that all the rows that are outside the $(6\epsilon/\gamma,2\epsilon)$ neighborhood of $M^{\prime j}$ must have $A_{j,t}<1-6\epsilon/\gamma$. This is because when $A_{j,t}\geq 1-6\epsilon/\gamma$ we have $M^{j}-\sum_{k=1}^{r}A_{j,t}W^{t}=\vec{0}$. If we replace $M^{j}$ by $M^{\prime j}$ and $W^{t}$ by the corresponding canonical row, the distance is still at most $2\epsilon$ and the coefficient on $M^{\prime i}$ is at least $1-6\epsilon/\gamma$. By definition the corresponding row $M^{\prime j}$ must be in the neighborhood of $M^{\prime i}$.

Now we can prove the main theorem of this section:

Proof: Suppose we know $\gamma$ and $100\epsilon<\gamma$.When $\gamma$ is so small we have the following claim:

If $A_{j,t}$ and $A_{i,l}$ is at least $1-10\epsilon/\gamma$, and $t\neq l$, then $M^{\prime j}$ cannot be $(10\epsilon/\gamma,2\epsilon)$-close to $M^{\prime i}$ and vice versa.

The proof is almost identical to Lemma 5.6. Also, the canonical row that corresponds to $W^{t}$ is $(10\epsilon/\gamma,2\epsilon)$ close to all rows with $A_{j,t}\geq 1-10\epsilon/\gamma$. Thus if we connect two robust loners when one is $(10\epsilon/\gamma,2\epsilon)$ close to the other, the connected component of the graph will exactly be a partition according to the row in $W$ that the robust loner is close to. We pick one robust loner in each connected component to get the almost anchor words.

Now suppose we don’t know $\gamma$. In this case the problem is we don’t know what is the right size of neighborhood to look at. However, since we know $\gamma>100\epsilon$, we shall first run the algorithm with $\gamma=100\epsilon$ to get $r$ rows $W^{\prime}$ that are very close to the true rows in $W$. It is not hard to show that these rows are at least $\gamma/2$ robustly simplicial and at most $\gamma+2\epsilon$ robustly simplicial. Therefore we can compute the $\gamma(W^{\prime})$ parameter for this set of rows and use $\gamma(W^{\prime})-2\epsilon$ as the $\gamma$ parameter. $\blacksquare$

Maximum Likelihood Estimation is Hard

Here we prove that computing the Maximum Likelihood Estimate (MLE) of the parameters of a topic model is $NP$-hard. We call this problem the Topic Model Maximum Likelihoood Estimation (TM-MLE) problem:

Given $m$ documents and a target of $r$ topics, the TM-MLE problem asks to compute the topic matrix $A$ that has the largest probability of generating the observed documents (when the columns of $W$ are generated by a uniform Dirichlet distribution).

Surprisingly, this appears to be the first proof that computing the MLE estimate in a topic model is indeed computationally hard, although its hardness is certainly to be expected. On a related note, Sontag and Roy recently proved that given the topic matrix and a document, computing the Maximum A Posteriori (MAP) estimate for the distribution on topics that generated this document is $NP$-hard. Here we will establish that TM-MLE is $NP$-hard via a reduction from the MIN-BISECTION problem: In MIN-BISECTION the input is a graph with $n$ vertices ($n$ is an even integer), and the goal is to partition the vertices into two equal sized sets of $n/2$ vertices each so as to minimize the number of edges crossing the cut.

There is a polynomial time reduction from MIN-BISECTION to TM-MLE ($r=2$).

Proof: Suppose we are given an instance $G$ of the MIN-BISECTION problem with $n$ vertices and $m$ edges. We will now define an instance of the TM-MLE problem. First, we set the number of words to be $n$. For each word $i$, we construct $N=\lceil 200m^{3}\log n\rceil$ documents each of which contain the word $i$ twice and no other words. For each edge in the graph $G$, we construct a document whose two words correspond to the endpoints of the edge.

Suppose that $x=(x_{1},x_{2})^{T}$ is generated by the Dirichlet distribution $Dir(1,1)$. Consequently the probability that words $i$ and $j$ appear in a document with only two words is exactly $(A^{i}x)\cdot(A^{j}x)$. We can take the expectation of this term over the Dirichlet distribution $Dir(1,1)$ and hence the probability that a document (with exactly two words) contains the words $i$ and $j$ is

In the TM-MLE problem, our goal is to maximize the following objective function (which is the $\log$ of the probability of generating the collection of documents):

For any bisection, we define a canonical solution: the first topic is uniform on all words on one side of the bisection and the second topic is uniform on all words on the other side of the bisection.To prove the correctness of our reduction, a key step is to show that any candidate solution to the MLE problem must be close to a canonical solution. In particular, we show the following:

In each row $A^{i}$, almost all of the weight will be in one of the two topics.

Indeed, canonical solutions have large objective value. Any canonical solution has objective value at least $-Nn\log 3n^{2}/4-m\log 3n^{2}/2$ (this is because documents with same words contribute $-\log 3n^{2}/4$ and documents with different words contribute at least $-\log 3n^{2}/2$).

Now we claim that among canonical solutions, the one with largest objective value corresponds to a minimum bisection. The proof follows from the observation that the value of the objective function is $-Nn\log 3n^{2}/4-k\log 3n^{2}/2-(m-k)\log 3n^{2}/4$ for canonical solutions, where $k$ is the number of edges cut by the bisection. In particular, the objective function of the minimum bisection will be at least an additive $\log 2$ larger than the objective function of a non-minimum bisection.

However, even if the canonical solution is perturbed by $1/20nm$, the objective function will only change by at most $m\cdot 1/10m=1/10$, which is much smaller than $\frac{\log 2}{2}$. And this completes our reduction. $\blacksquare$

We remark that the canonical solutions in our reduction are all separable, and hence this reduction applies even when the topic matrix $A$ is known (and required) to be separable. So, even in the case of a separable topic matrix, it is $NP$-hard to compute the MLE.

Conclusions

We expect that versions of our algorithm may indeed be practical, and are investigating this possibility. Our machine learning colleagues suggest that real-life topic matrices satisfy even stronger separability assumptions, e.g., the presence of many anchor words per topic instead of a single one. This is a promising suggestion, but leveraging it in our algorithm is an open problem.

Is separability necessary for allowing polynomial-time algorithms for the learning problems considered here? In other words, is the problem difficult if the topic matrix $A$ is not separable? Average-case intractability seems more plausible here than NP-completeness.

Acknowledgements

We thank Dave Blei, Ravi Kannan, David Minmo, Sham Kakade, David Sontag for many helpful discussions throughout various stages of this work.

References