High-Reproducibility and High-Accuracy Method for Automated Topic Classification

Much of human knowledge sits in large databases of unstructured text. Leveraging this knowledge requires algorithms that extract and record metadata on unstructured text documents. Assigning topics to documents will enable intelligent searching, statistical characterization, and meaningful classification. Latent Dirichlet allocation (LDA) is the state of the art in topic modeling. Here, we perform a systematic theoretical and numerical analysis that demonstrates that current optimization techniques for LDA often yield results that are not accurate in inferring the most suitable model parameters. Adapting approaches from community detection in networks, we propose a new algorithm that displays high reproducibility and high accuracy and also has high computational efficiency. We apply it to a large set of documents in the English Wikipedia and reveal its hierarchical structure.

Popular Summary

A significant fraction of data that are currently being generated and stored is in the form of unstructured text. Researchers use topic modeling algorithms to automatically classify text documents into topics in text recommendation systems, digital image analysis, spam filtering, and high-dimensional data mining with the goal of recording and extracting relevant data. With the goal of enabling intelligent data searches, we study synthetic and real data, whose topics are known, to evaluate the performance of state-of-the-art algorithms. We show that current optimization techniques often have trouble yielding accurate and reproducible results, particularly if the topics are heterogeneously distributed. By borrowing methods from graph clustering, we propose a novel optimization method with high accuracy and reproducibility and no computational overhead.

One state-of-the-art algorithm for classifying text-based data is latent Dirichlet allocation, a means of assigning topics to documents. We measure its performance using specific synthetic data with known topics. We find that the algorithm is not able to detect the ground-truth topics because of the roughness of the likelihood landscape. We propose a novel technique that builds a network of co-occurrent words and finds topics starting from clusters of words in that network. We show that our method is more accurate, both in synthetic cases and in a real-world case of documents from the journal Science.

We expect that our results will yield new ways of automatically classifying text documents, a process that is particularly relevant given the growth of electronic, searchable data.

Figure 1

Generative model for documents in the corpus. Documents are assumed to be a mixture of topics. The topic structure is latent, meaning that one cannot access the “true” set of topics used to generate the documents in the corpus. However, the set of topics can be estimated using a topic-model algorithm. To this end, one calculates the word frequencies in each document and models them as mixtures of different topics, math and biology in this example.

Figure 2

The language corpus. (a) We generate synthetic documents for a corpus where each document is a collection of words from one of three languages or topics: English, French, and Spanish. Even though the corpus is generated from three topics, if one of the topics (in this example, English) is much more highly represented in the corpus than the others, a typical topic-model algorithm might assign English documents to two topics, while French and Spanish documents may be assigned to a single topic. (b) Consider the case where each language has a vocabulary of 20 unique equiprobable words and each document comprises 10 words. For these parameters’ values, the alternative model has a larger log-likelihood (for PLSA or symmetric LDA) if the fraction of English documents in the corpus is greater than 0.936. (c) Performance of the symmetric LDA algorithm, assuming that $K=3$ topics are used to generate the documents in the corpus. The solid line and points indicate the median change in log-likelihood of the model inferred by the algorithm, and the shaded area delimits the 25th and 75th percentiles. Note that, in practice, the LDA algorithm does not infer the correct generative model (green curve) prior to the theoretical limit (gray shaded area). (d) Probability that symmetric LDA infers the correct generative model when setting $K=3$.

Figure 3

Performance of an algorithm on the analysis of synthetic corpora. We define accuracy as the best-match similarity (see Sec. 7) among the fitted model and the generative model. Reproducibility is the similarity among fitted models obtained in different runs.

Figure 4

Numerical evaluation of algorithm performance. We generate documents for the corpora according to a two-step process. First, we assign a language to the document. Next, we draw with replacement 100 words with the probability corresponding to their frequency in the chosen language. For simplicity, we use a vocabulary limited to the 1000 most frequently used words in the language and exclude words that are not unique to the language. When using LDA and PLSA algorithms, we assume that we already know the correct number of topics in the corpora. (a) Illustration of inferred topics using LDA standard optimization for corpora with the equally and unequally sized topics. Each “slice” in the pie charts represents the topic inferred by LDA for a set of documents. Different colors indicate the languages assigned to the documents in the generative model. In the equal-sized topics, English and Italian documents are assigned a single topic and Spanish documents are assigned to two different topics. In the unequal-sized topics, English and French documents are split into two topics each, whereas German and Finnish documents are assigned a single topic, as are Swedish and Spanish documents. (b) Reproducibility and accuracy of four topic-modeling algorithms for the language corpora. The dashed lines indicate the expected accuracy when overfitting one language and underfitting two other languages (top line) or when overfitting two languages and underfitting four (bottom line). The full lines show median values, and the shaded regions denote the 25th to 75th percentiles. LDA ($r$) and LDA ($s$) refer, respectively, to random and seeded initializations for the optimization technique.

Figure 5

Illustration of the TopicMapping algorithm. Step 1: Consider a corpus comprising six documents, three in the topic biology and three in the topic math. We exclude stop words from those documents and stem words in order to denoise the data. We then build a network connecting words with weights equal to their dot-product similarity. Steps 2 and 3: We filter nonsignificant weights, using a $p$ value of 5%, and we run Infomap [44] to obtain the community structure of the network. In this case, we find two clusters and two isolated words (study and research). Step 4: We refine the word clusters using a topic model: The two isolated words are now assigned to both topics.

Figure 6

Creating synthetic corpora using the generative model. For each document, $p(\text{topic}|\text{doc})$ is sampled from a Dirichlet distribution whose hyperparameters are defined as ${\alpha }_{\text{topic}}=K\times p(\text{topic})\times \alpha$, where $K$ is the number of topics, $p(\text{topic})$ is the probability (i.e., the size) of the word topic, and $\alpha$ is a parameter that tunes how mixed documents are: Smaller values of $\alpha$ yield a simpler model where documents make use of fewer topics. We also have a parameter to fix the fraction of generic words, and we implement a similar method for deciding $p(\text{word}|\text{doc})$ for specific and generic words (see Sec. 7). Once the latent topic structure is chosen, we create a corpus drawing words with probabilities given by the mixture of topics.

Figure 7

Performance of topic-modeling algorithms on synthetic corpora. We plot the (a) reproducibility and (b) accuracy of the different algorithms. In all our tests, we generate a corpus of 1000 documents, of 50 words each, and our vocabulary is made of 2000 unique equiprobable words. We set the number of topics $K=20$, and we input this number in LDA and PLSA. “Equally sized” means all the topics have equal probability $p(\text{topic})=5\%$, while in the “unequally sized” case, four large topics have probability 15% each, while the other 16 topics have probability 2.5%. LDA ($s$) and LDA ($r$) refer to seeded and random initializations for LDA (variational inference). The plots show the median values as well as the 25th and 75th percentiles.

Figure 8

(a) Performance of topic-model algorithms on an a priori well-characterized corpus of scientific publications. We represent the topic model inferred by each algorithm as a pie diagram. Each slice of the pie indicates a single topic. Different colors correspond to different journals, and the area taken by a given journal (color) in a given topic (slice) is proportional to the probability of the corresponding journal given that topic: $p(\text{journal}|\text{topic})={\sum }_{\text{doc}}p(\text{journal}|\text{doc})\times p(\text{doc}|\text{topic})$. We identify as topic keywords the most frequent words for documents inferred to have been generated by the topic. The * symbol indicates that the word shown is the stem of a number of words [45]. The TopicMapping algorithm is nearly perfect in its ability to identify the source of the publication. The second and third pies show the performance of standard LDA when we use the number of journals as our estimate of the number of topics. As we find for the synthetic corpora, publications from large journals are split and publications from small journals are merged. The fourth pie shows the performance of the standard LDA algorithm when we estimate the number of topics using model selection. Small topics are now resolved, but big topics are split so that each topic is comparable in size. As we learned from the analysis of synthetic corpora, we find a large decrease in reproducibility. (b) Effect of adding publications from the multidisciplinary journal Science. Many of the publications in Science are assigned to the same topics as publications from the disciplinary journals. However, some of the publications in Science are assigned to new topics. The total number of topics found is 19, but only topics with probability bigger than 2% are shown in the figure (nine topics). In order to validate these results, we present both the keywords identified for each topic and the departments most highly represented for the affiliations in the author lists of the publications assigned to the topic.

Figure 9

Topic model of the English Wikipedia corpus obtained with TopicMapping. We show model estimates after one single iteration of LDA refining. Further iterations result in a much greater number of topics and low reproducibility of the results (see the Supplemental Material, Secs. 1.6 and 10 [37]). We highlight the top five topics by size, which together account for 80% of all documents. Four of the five topics are very easy to identify. However, the largest topic, which we denote as “general knowledge,” is harder to grasp. However, fitting of a (sub)topic model to the documents in the general knowledge topic yields a set of (sub)topics that are again quite straightforward to interpret.