Source-linked AI summary
Scalable Topical Phrase Mining from Text Corpora
Ahmed El-Kishky, Yanglei Song, Chi Wang, Clare Voss, Jiawei Han
TL;DR
The paper addresses how to discover interpretable topical phrases of mixed lengths without the poor scalability or phrase quality associated with existing approaches. ToPMine mines and segments documents into phrases, then constrains topic modeling so each phrase receives a shared topic. It reports high-quality topical phrases with negligible extra cost compared with bag-of-words topic modeling across several dataset types.
Problem
Existing unigram-based and complex n-gram topic methods do not reliably provide scalable, interpretable topical phrases of mixed lengths.
Method
ToPMine mines frequent significant phrases, segments each document into single- and multi-word phrases, and uses the induced partition as constraints in PhraseLDA.
Results
ToPMine discovers high-quality topical phrases with negligible extra cost to bag-of-words topic modeling across titles, abstracts, reviews, and news articles.
Takeaways & Limitations
Phrase-based topic assignments provide a more interpretable representation while retaining a phrase-constrained topic-modeling framework.
Takeaways & Limitations
The phrase-mining significance test assumes corpus phrase occurrences arise from independent Bernoulli trials.
Abstract
from arXiv · showhide
While most topic modeling algorithms model text corpora with unigrams, human interpretation often relies on inherent grouping of terms into phrases. As such, we consider the problem of discovering topical phrases of mixed lengths. Existing work either performs post processing to the inference results of unigram-based topic models, or utilizes complex n-gram-discovery topic models. These methods generally produce low-quality topical phrases or suffer from poor scalability on even moderately-sized datasets. We propose a different approach that is both computationally efficient and effective. Our solution combines a novel phrase mining framework to segment a document into single and multi-word phrases, and a new topic model that operates on the induced document partition. Our approach discovers high quality topical phrases with negligible extra cost to the bag-of-words topic model in a variety of datasets including research publication titles, abstracts, reviews, and news articles.
1. INTRODUCTION
ToPMine addresses the interpretability and scalability limitations of unigram-based and complex topical phrase methods by mining and segmenting phrases before topic modeling. Phrase-constrained topic modeling keeps words within each induced phrase under a shared topic assignment.
- Unigram topic descriptions can be difficult to interpret because individual words may be ambiguous across topics.Topic visualization is used to support human interpretation and qualitative validation of inferred topic models.
- Existing topical phrase methods either post-process unigram topic models or jointly infer phrases and topics with complex generative mechanisms.Post-processing methods assume phrase words share a topic, but unigram topic models do not guarantee that assignment.
- ToPMine mines phrases, segments documents into single- and multi-word phrases, and uses the segmentation constraints in topic modeling.The method combines frequent phrase mining, statistical significance ranking, and phrase-constrained topic modeling.
- The phrase-mining algorithm filters false candidates efficiently by testing merged phrase extensions, such as “frequent pattern tree,” before retaining shorter phrases.This reduces the number of significance tests needed during phrase construction.
- The induced bag-of-phrases representation reduces model complexity while maintaining conformity of topic assignments within each phrase.All constituent terms in a phrase are constrained to share the same topic.
2. PROBLEM DEFINITION
The paper defines topical phrase mining as finding contiguous, interpretable phrases that are frequent, statistically meaningful, appropriately sized, coherently topical, and efficiently modeled. It seeks a phrase-based representation whose topic assignments remain principled and comparable in complexity to LDA.
- The task is to infer corpus topics and visualize them through human-interpretable topical phrases.A topic is represented statistically by a probability distribution over vocabulary words.
- Unigrams can be ambiguous because the same word may carry different meanings in different topics.This motivates representing topic content with phrases rather than only individual words.
- Definitions: A phrase is a sequence of contiguous tokens, and a document partition is a sequence of phrases whose concatenation reproduces the document.The partition therefore preserves the original token order while grouping tokens into phrase instances.
- Desired Properties: Phrase recognition uses contiguity and collocation, where token co-occurrence is significantly higher than expected by chance.The “strong tea” versus “powerful tea” example illustrates why frequency deviations can identify informative collocations.
- Desired Properties: The overall system should produce coherent, valid, principled, computationally efficient phrases while maintaining topic-model perplexity similar to LDA.These requirements combine interpretability, topic assignment, efficiency, and predictive behavior.
- Desired Properties: Phrase construction should choose the most appropriate phrase size rather than retaining only smaller frequent subsets of longer phrases.For example, “mining frequent patterns” should be preferred over the less complete subset “mining frequent” when appropriate.
3. TOPMINE FRAMEWORK
ToPMine transforms documents from bags of words into bags of phrases, then uses the induced partitions as constraints for phrase-constrained topic modeling. Phrase mining supplies statistically guided segments, while PhraseLDA assigns one topic to all words within each phrase.
- ToPMine has two stages: phrase mining with text segmentation and phrase-constrained topic modeling.Documents are first mined for frequent phrases and segmented through agglomerative phrase construction.
- Phrase mining collects aggregate statistics and uses statistical significance, phrase context, and phrase significance to guide document segmentation.The resulting partition becomes the input to the phrase-constrained topic model.
- PhraseLDA incorporates the bag-of-phrases partition as inference constraints so tokens within a mined phrase receive the same topic assignment.This avoids introducing additional latent variables to discover phrases during topic modeling.
4. PHRASE MINING
The phrase-mining framework efficiently finds frequent contiguous candidates, then constructs interpretable phrases through context-aware, bottom-up partitioning.
- Frequent phrase mining: The algorithm first mines frequent candidate phrases and aggregate counts, then agglomeratively merges document tokens into quality phrases.Candidate generation uses contiguous patterns and minimum support; merging is guided by a statistical significance measure.
- Frequent phrase mining: Downward closure and data-antimonotonicity prune infrequent candidates and remove documents that cannot contain longer frequent phrases.These properties enable early termination during phrase mining.
- Frequent phrase mining: Minimum support controls the precision–recall trade-off: increasing it is expected to improve precision while reducing recall.The support threshold can generally grow linearly with corpus size.
- Frequent phrase mining: Splitting documents on phrase-invariant punctuation reduces worst-case phrase-mining complexity from quadratic candidates to linear corpus-scale complexity.The worst case generates O(N_d^2) candidates for a document, but smaller constant-size chunks make overall complexity O(N).
- Phrase construction: Bottom-up greedy merging maintains a document partition, implicitly filtering phrases that meet minimum support only by random chance.Only phrases induced by the partition remain valid phrase instances.
significance measure.
The method builds a bag-of-phrases through bottom-up merging, selecting contiguous phrase pairs by statistical significance under an independence-based null hypothesis. Efficient frequent-phrase counts and data structures make document-level construction scalable.
- The bottom-up process terminates by partitioning each document into single- and multi-word phrases, creating a bag-of-phrases.
- Figure 1 illustrates successive agglomerative phrase merges on a DBLP computer-science title, with each dendrogram level representing one merging iteration.
- Aggregate counts for frequent merged phrases enable efficient significance computation, while suitable data structures select and merge the best pair in O(log(N_d)) time per document.
- The null hypothesis models phrase occurrences as independent Bernoulli trials and defines the expected frequency distribution for each phrase.
- Each iteration merges the two contiguous phrases with the highest significance score, comparing observed frequency with expected frequency under the null hypothesis.
- The significance score measures how many standard deviations the observed phrase count lies from its null-model expectation and generalizes the t-statistic for dependent bigrams.
5. TOPIC MODELING
PhraseLDA extends LDA by partitioning documents into phrases and coupling the topic assignments of tokens within each phrase.
- Phrase representation: The framework represents each document as a bag-of-phrases produced by mining and segmentation before topic modeling.The induced partition supplies constraints for associating phrase constituents with topics.
- Inference: PhraseLDA uses collapsed Gibbs sampling after integrating out the document-topic and topic-word distributions.The model’s joint distribution and sampling procedure are developed from the LDA formulation.
- LDA background: LDA models documents as mixtures of topics, with each topic represented as a multinomial distribution over vocabulary words.Its bag-of-words assumption ignores word order and gives distant and nearby words equivalent document-level influence.
- PhraseLDA: Each phrase clique introduces a potential function that favors assigning all constituent tokens to the same latent topic.This constraint preserves conformity of topic assignments within phrases while avoiding additional latent variables for phrase discovery.
- PhraseLDA: PhraseLDA connects latent topic assignments within each phrase so the assignments form a clique in a chain graph.The graph combines LDA’s topic-to-token relations with undirected dependence among nearby phrase tokens.
C PLDApZ, Wq
The topic model operates on mined phrase cliques and approximates their joint topic potential by forcing all phrase constituents to share one latent topic. This reduces inference complexity while supporting phrase-based topic visualization and parameter optimization analogous to LDA.
- The model retains LDA-style hyperparameter optimization because its joint probability has the PLDA form, using the fixed-point method in the experiments.
- Because the normalizing constant requires evaluating K^s clique states, the unrestricted potential is computationally intractable for large topic counts and phrase sizes.
- The potential function forces every variable in a phrase clique to take the same latent topic, reducing its possible states from K^s to K.
- This shared-topic approximation is motivated by constrained phrase merging, which makes it highly probable that variables within a phrase possess the same topic.
- The model samples each clique from its posterior using one configuration per topic, where clique state k denotes all constituent variables taking topic k.
- Phrases inherit the shared topic of their constituents, and topical frequency ranks phrase instances for visualizing each topic.
6. RELATED WORK
Existing topical phrase methods either integrate phrase discovery into complex generative topic models or apply phrase extraction after unigram-based modeling. These approaches can be incompatible with partition-based phrase modeling, corpus-specific, or computationally difficult.
- Method categories: Topical phrase extraction methods mainly use complex joint generative models or post-process unigram topic models.Joint models infer phrases and topics simultaneously, whereas post-processing methods discover phrases after topic inference.
- Joint phrase-topic models: Bigram and n-gram topic models add hierarchical or nonparametric mechanisms to share topics across phrase words.Examples include TNG’s latent variables and word-specific multinomials, and PD-LDA’s hierarchical Pitman–Yor process.
- Post-processing methods: Post-processing methods rank extracted patterns using heuristics, back-off n-grams, or permutation tests after topic modeling.KERT mines frequent patterns within topics, while Turbo Topics tests phrase significance with a back-off n-gram model.
- Domain-specific methods: Twitter-specific phrase extraction uses retweet-network topology and therefore does not extend to other text corpora.Its phrase ranking combines a Twitter-specific topic model with an extension of topical PageRank.
- Representation constraint: Generic phrase extractors output ranked phrase lists, making them incompatible with topic modeling that requires partitioned documents.The paper distinguishes ranked-list extraction from its phrase-based topic-modeling input representation.
7. EXPERIMENTAL RESULTS
The experiments evaluate ToPMine’s interpretability, predictive behavior, runtime, and performance across datasets including titles, abstracts, news, and reviews. ToPMine achieves strong human-rated phrase quality and coherence, preserves or improves perplexity, and scales to large long-text corpora.
- Interpretability evaluation: Human evaluation measures phrase intrusion, topical coherence, and phrase quality using annotator choices and standardized expert ratings.Phrase intrusion uses four-phrase questions; coherence and phrase quality are rated on 1-to-10 scales and averaged after z-score standardization.
- User studies: ToPMine matches KERT on phrase intrusion and achieves the best topical coherence and phrase quality among evaluated methods.The authors attribute KERT’s weaker phrase quality to longer phrase rankings and appended topical unigrams, while describing TNG and PD-LDA as weaker on intrusion.
- Perplexity: 45 bits lower perplexity than LDA is reported for PhraseLDA on Yelp Reviews, while PhraseLDA has comparable perplexity to LDA on DBLP abstracts.The comparison uses held-out prediction because PhraseLDA and LDA share the same generative process.
- Scalability: PhraseLDA often runs shorter than LDA because inference samples one topic per multi-word phrase rather than one topic per word.The runtime decomposition separates phrase mining from phrase-constrained topic modeling.
- Scalability: ToPMine is the only evaluated method that runs on the full DBLP abstracts dataset with runtime in the same order as LDA.PD-LDA and Turbo Topics become intractable or run only on sampled datasets, while KERT’s pattern growth makes large long-text datasets intractable.
- Qualitative results: ToPMine yields high-quality phrases for naturally topical news and computer-science data, but lower-quality phrases for noisier Yelp reviews.The authors associate the Yelp difference with ubiquitous background and sentiment phrases such as “good,” “love,” and “great.”
8. FUTURE WORK
Future work targets broader topic modeling, further runtime reductions, similar-phrase merging, and principled filtering of ubiquitous background phrases. The paper identifies both modeling flexibility and phrase-representation issues as remaining areas for improvement.
- Topic-model extension: A nonparametric prior for PhraseLDA could estimate the number of underlying topics directly from the corpus.The paper presents this as a natural extension rather than a capability of the current model.
- Scalability: Further scalability work is needed for the topic-modeling portion because current computational savings mainly come from efficient phrase mining.Alternative topical-inference methods may reduce ToPMine’s overall time complexity.
- Phrase representation: Minimum-support and pruning strategies treat similar phrases as separate structures, which may reduce recall and topic quality.The authors note that this does not affect top-ranked phrases, whose counts are much larger than the minimum support.
- Phrase filtering: Ubiquitous background phrases such as “paper we propose” and “proposed method” can enter topical representations and require principled filtering.The paper identifies this as an issue for improving topic separation and coherence.
9. CONCLUSIONS
ToPMine combines efficient phrase mining with phrase-constrained topic modeling to discover arbitrary-length topical phrases. The framework produces coherent, interpretable topics across DBLP abstracts, AP News, and Yelp reviews, though Yelp quality is lower.
- Framework: ToPMine discovers arbitrary-length topical phrases through phrase mining followed by PhraseLDA with partition constraints.Phrase mining constructs document partitions, which PhraseLDA uses to assign latent topics to phrases.
- Framework: Separating phrase discovery from topic modeling reduces computational overhead relative to joint phrase-topic models and is more principled than LDA post-processing.The framework reports scalability on large datasets and interpretability beyond existing methods.
- Results: DBLP abstracts yield coherent topics and high-quality phrases covering search/optimization, NLP, machine learning, programming languages, and data mining.
- Results: AP News articles yield high-quality topical phrases and coherent topics involving environment, Christianity, Palestine/Israel, the Bush administration, and health care.
- Results: Yelp reviews produce lower-quality topics than the other datasets, but remain interpretable through food, hotels, grocery, and related categories.
Appendix
The appendix introduces collapsed Gibbs sampling inference for PhraseLDA and points to an external derivation for part of the equation.
- Inference: The appendix presents collapsed Gibbs sampling inference for PhraseLDA.
- Inference: The inference derivation begins from equation 5.
- Inference: The derivation of the second line is referenced to source.