Name
Abstract | ||
|---|---|---|
Latent Dirichlet allocation (LDA) is a popular algorithm for discovering semantic structure in large collections of text or other data. Although its complexity is linear in the data size, its use on increasingly massive collections has created considerable interest in parallel implementations. “Approximate distributed” LDA, or AD-LDA, approximates the popular collapsed Gibbs sampling algorithm for LDA models while running on a distributed architecture. Although this algorithm often appears to perform well in practice, its quality is not well understood theoretically or easily assessed on new data. In this work, we theoretically justify the approximation, and modify AD-LDA to track an error bound on performance. Specifically, we upper bound the probability of making a sampling error at each step of the algorithm (compared to an exact, sequential Gibbs sampler), given the samples drawn thus far. We show empirically that our bound is sufficiently tight to give a meaningful and intuitive measure of approximation error in AD-LDA, allowing the user to track the tradeoff between accuracy and efficiency while executing in parallel. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1109/TKDE.2011.29 | IEEE Trans. Knowl. Data Eng. |
Keywords | Field | DocType |
approximation theory,sampling methods,text analysis,Gibbs sampling algorithm,approximate distributed latent Dirichlet allocation,approximation error,distributed architecture,error understanding,linear complexity,sampling error,semantic structure discovery,text data collection,Data mining,error analysis.,parallel processing,topic model | Data mining,Latent Dirichlet allocation,Computer science,Upper and lower bounds,Theoretical computer science,Artificial intelligence,Gibbs sampling,Approximation algorithm,Approximation theory,Sampling (statistics),Topic model,Machine learning,Approximation error | Journal |
Volume | Issue | ISSN |
24 | 5 | 1041-4347 |
Citations | PageRank | References |
2 | 0.40 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexander T. Ihler | 1 | 1377 | 112.01 |
| David Newman | 2 | 1319 | 73.72 |