A more time-efficient gibbs sampling algorithm based on SparseLDA for latent dirichlet allocation

Abstract

As an efficient sampling algorithm for latent dirichlet allocation SparseLDA uses cache strategy to improve the time and space efficiency of its standard gibbs sampling algorithm (StdGibbs) by recycling previous computation. However, SparseLDA cannot further improve the time-efficiency of StdGibbs, since the amount of recycled computation is limited. This is because the word types of two adjacent tokens are usually different and the previous computation cannot be further recycled easily. To solve this problem, in this paper we propose a new algorithm named Efficient SparseLDA (ESparseLDA) based on SparseLDA. The main idea of ESparseLDA is to first rearrange the tokens within one text according to the word types so that the tokens of the same word type are aggregated together and then recycle more computation while making no approximation and ensuring the exactness. In this paper, we make detailed theoretical explanations and comparative experimental analyses on the correctness, exactness and time-efficiency of ESparseLDA. In detail, the statistical significance tests on perplexities strictly show that ESparseLDA is correct and exact. In addition, the running time results show that the time-efficiency of ESparseLDA is the higher than SparseLDA in varying degrees from 5.06% to 31.85% on the different datasets used in experiments.

Keywords

Latent dirichlet allocation topic model gibbs sampling topic inference

Get full access to this article

View all access options for this article.

References

Blei

D.M.

, Probabilistic topic models, Communications of the ACM 55(4) (2012), 77–84.

Blei

D.M.

Carin

and Dunson

, Probabilistic topic models, IEEE Signal Processing Magazine 27(6) (2010), 55–65.

Blei

D.M.

A.Y.

and Jordan

M.I.

, Latent dirichlet allocation, in: Advances in Neural Information Processing Systems, MIT Press, 2001, pp. 601–608.

Blei

D.M.

A.Y.

and Jordan

M.I.

, Latent dirichlet allocation, Journal of Machine Learning Research 3 (2003), 993–1022.

Cha

Hsieh

C.-C.

and Cho

, Incorporating popularity in topic models for social network analysis, in: Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 2013, pp. 223–232.

Cha

and Cho

, Social-network analysis using topic models, in: Proceedings of the 35th International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 2012, pp. 565–574.

Crain

S.P.

Zhou

Yang

S.-H.

and Zha

, Dimensionality reduction and topic modeling: From latent semantic indexing to latent dirichlet allocation and beyond, in: Mining Text Data, Springer, Boston, MA, 2012, pp. 129–161.

Das

Zaheer

and Dyer

, Gaussian lda for topic models with word embeddings, in: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, ACL, 2015, pp. 795–804.

Deepak

Hariharan

and Sinha

, Cluster based human action recognition using latent dirichlet allocation, in: 2013 International Conference on Circuits, Controls and Communications (Ccube), IEEE, 2013, pp. 1–4.

10.

Gilks

W.R.

Richardson

and Spiegelhalter

, Markov Chain Monte Carlo in Practice, CRC Press, 1995.

11.

Godin

Slavkovikj

De Neve

Schrauwen

and Van de Walle

, Using topic models for twitter hashtag recommendation, in: Proceedings of the 22nd International Conference on World Wide Web, ACM, 2013, pp. 593-596.

12.

Griffiths

T.L.

and Steyvers

, Finding scientific topics, in: Proceedings of the National Academy of Sciences, NAS, 2004, pp. 5228-5235.

13.

Hong

and Davison

B.D.

, Empirical study of topic modeling in twitter, in: Proceedings of the First Workshop on Social Media Analytics, ACM, 2010, pp. 80-88.

14.

and Oh

A.H.

, Aspect and sentiment unification model for online review analysis, in: Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, ACM, 2011, pp. 815-824.

15.

Kim

Georgiou

and Narayanan

, Supervised acoustic topic model with a consequent classifier for unstructured audio classification, in: Proceedings of the 10th International Workshop on Content-Based Multimedia Indexing (CBMI), IEEE, 2012, pp. 1-6.

16.

Kim

Georgiou

P.G.

Narayanan

and Sundaram

, Supervised acoustic topic model for unstructured audio information retrieval, in: Proceedings of Asia Pacific Signal and Information Processing Association (APSIPA) Annual Summit and Conference, IEEE, 2010, p. 3.

17.

Kim

Narayanan

and Sundaram

, Acoustic topic model for audio information retrieval, in: 2009 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics, IEEE, 2009, pp. 37-40.

18.

Lacoste-Julien

Sha

and Jordan

M.I.

, Disclda: Discriminative learning for dimensionality reduction and classification, in: Advances in Neural Information Processing Systems, MIT Press, 2009, pp. 897-904.

19.

Lau

J.H.

Cook

McCarthy

Gella

and Baldwin

, Learning word sense distributions, detecting unattested senses and identifying novel senses using topic models, in: Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, ACL, 2014, pp. 259-270.

20.

A.Q.

Ahmed

Ravi

and Smola

A.J.

, Reducing the sampling complexity of topic models, in: Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2014, pp. 891-900.

21.

Lin

and He

, Joint sentiment/topic model for sentiment analysis, in: Proceedings of the 18th ACM Conference on Information and Knowledge Management, ACM, 2009, pp. 375-384.

22.

Lin

Everson

and Ruger

, Weakly supervised joint sentiment-topic detection from text, IEEE Transactions on Knowledge and Data Engineering 24(6) (2012), 1134–1145.

23.

Mehrotra

Sanner

Buntine

and Xie

, Improving lda topic models for microblogs via tweet pooling and automatic labeling, in: Proceedings of the 36th International ACM SIGIR Conference on Research and Development in Information Retrieval, ACM, 2013, pp. 889–892.

24.

Mimno

Hoffman

and Blei

D.M.

, Sparse stochastic inference for latent dirichlet allocation, in: Proceedings of the 29th International Coference on International Conference on Machine Learning, ACM, 2012, pp. 1515–1522.

25.

Moens

M.-F.

and Vulié

, Multilingual probabilistic topic modeling and its applications in web mining and search, in: Proceedings of the 7th ACM International Conference on Web Search and Data Mining, ACM, 2014, pp. 681–682.

26.

Nguyen

V.-A.

Boyd-Graber

Resnik

and Miler

, Tea party in the house: A hierarchical ideal point topic model and its application to republican legislators in the 112th congress, in: Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, ACL, 2015, pp. 1438–1448.

27.

Niu

Hua

Gao

and Tian

, Context aware topic model for scene recognition, in: 2012 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), IEEE, 2012, pp. 2743–2750.

28.

Niu

Hua

Gao

and Tian

, Semi-supervised relational topic model for weakly annotated image recognition in social media, in: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, IEEE, 2014, pp. 4233–4240.

29.

Porteous

Newman

Ihler

Asuncion

Smyth

and Welling

, Fast collapsed gibbs sampling for latent dirichlet allocation, in: Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2008, pp. 569–577.

30.

Rabinovich

and Blei

, The inverse regression topic model, in: Proceedings of the 31st International Conference on Machine Learning, ACM, 2014, pp. 199–207.

31.

Ranganath

Wang

David

and Xing

, An adaptive learning rate for stochastic variational inference, in: Proceedings of the 30th International Conference on Machine Learning, ACM, 2013, pp. 298–306.

32.

Steyvers

and Griffiths

, Probabilistic topic models, in: Handbook of Latent Semantic Analysis, 2007, pp. 424–440.

33.

Titov

and McDonald

, Modeling online reviews with multi-grain topic models, in: Proceedings of the 17th International Conference on World Wide Web, ACM, 2008, pp. 111–120.

34.

Titov

and McDonald

R.T.

, A joint model of text and aspect ratings for sentiment summarization, in: Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics, ACL, 2008, pp. 308–316.

35.

Xiao

and Stibor

, Efficient collapsed gibbs sampling for latent dirichlet allocation, in: Proceedings of 2nd Asian Conference on Machine Learning, JMLR, 2010, pp. 63–78.

36.

Yang

Zhang

Wang

and Li

, Scene and place recognition using a hierarchical latent topic model, Neurocomputing 148 (2015), 578–586.

37.

Yang

Boyd-Graber

and Resnik

, A discriminative topic model using document network structure, in: Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics, ACL, 2016, pp. 686–696.

38.

Yao

Mimno

and McCallum

, Efficient methods for topic model inference on streaming document collections, in: Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, 2009, pp. 937–946.

39.

Yuan

Gao

Dai

Wei

Zheng

et al., Lightlda: Big topic models on modest computer clusters, in: Proceedings of the 24th International Conference on World Wide Web, ACM, 2015, pp. 1351–1361.