Variance reduced stochastic variational inference algorithm for topic modeling of large-scale data

doi:10.11772/j.issn.1001-9081.2017112786

Abstract

Abstract: Stochastic Variational Inference (SVI) has been successfully applied to many types of models including topic models. Although it is extended to deal with large-scale data set with mapping the problem of reasoning to the optimization problems involving random gradient, the inherent noise of the stochastic gradient in SVI algorithm makes it produce large variance, which hinders fast convergence. In order to solve the problem, an improved Variance Reduced SVI (VR-SVI) was proposed. Firstly, the sliding window method was used to recalculate the noise term in the stochastic gradient, a new stochastic gradient was constructed, and the influence of noise on the stochastic gradient was reduced. Then, it was proved that the proposed algorithm could reduce the variance of random gradient on the basis of SVI. Finally, the influence of window size on the algorithm was discussed, and the convergence of algorithm was analyzed. The experimental results show that, the proposed VR-SVI algorithm can not only reduce the variance of stochastic gradient, but also save the computation time and achieve fast convergence.

Key words: Stochastic Variational Inference (SVI), sliding window, stochastic gradient, variance reduction, topic modeling

摘要： 随机变分推理（SVI）已被成功应用于在包括主题模型在内的众多类型的模型。虽然它将推理问题映射到涉及随机梯度的优化问题，使其扩展到处理大规模数据集，但是SVI算法中随机梯度固有的噪声使其产生较大的方差，阻碍了快速收敛。为此，对SVI作出改进，提出一种方差减小的SVI （VR-SVI）算法。首先，采取滑动窗口的方法重新计算随机梯度中的噪声项，构建新的随机梯度，减少了噪声对随机梯度的影响；然后，对提出的算法可在SVI基础上使得随机梯度的方差减小进行证明；最后，讨论窗口大小对算法的影响，并分析算法的收敛性。实验结果表明，VR-SVI算法既减小了随机梯度的方差，又节省了计算时间，可达到快速收敛的效果。

关键词: 随机变分推理, 滑动窗口, 随机梯度, 方差减小, 主题建模

CLC Number:

LIU Zhanghu, CHENG Chunling. Variance reduced stochastic variational inference algorithm for topic modeling of large-scale data[J]. Journal of Computer Applications, 2018, 38(6): 1675-1681.

刘张虎, 程春玲. 面向大规模数据主题建模的方差减小的随机变分推理算法[J]. 计算机应用, 2018, 38(6): 1675-1681.

References

[1] BLEI D M, NG A Y, JORDAN M I. Latent Dirichlet allocation[J]. Journal of Machine Learning Research, 2003, 3:993-1022.
[2] ANDRIEU C, de FREITAS N, DOUCET A, et al. An introduction to MCMC for machine learning[J]. Machine Learning, 2003, 50(1/2):5-43.
[3] GRIFFITHS T L, STEYVERS M. Finding scientific topics[J]. Proceedings of the National Academy of Sciences of the United States of America, 2004, 101(S1):5228-5235.
[4] TEH Y W, NEWMAN D, WELLING M. A collapsed variational Bayesian inference algorithm for latent Dirichlet allocation[C]//Proceedings of the 2006 Twentieth Annual Conference on Neural Information Processing Systems. Cambridge, MA:MIT Press, 2006:1353-1360.
[5] CANINI K R, SHI L, GRIFFITHS T L. Online inference of topics with latent Dirichlet allocation[EB/OL].[2017-10-16]. http://proceedings.mlr.press/v5/canini09a/canini09a.pdf.
[6] PATTERSON S, TEH Y W. Stochastic gradient Riemannian Langevin dynamics on the probability simplex[C]//Proceedings of the 201326th International Conference on Neural Information Processing Systems. New York:Curran Associates Inc., 2013:3102-3110.
[7] HOFFMAN M D, BLEI D M, BACH F R. Online learning for latent Dirichlet allocation[C]//Proceedings of the 201023rd International Conference on Neural Information Processing Systemss. New York:Curran Associates Inc., 2010:856-864.
[8] HOFFMAN M D, BLEI D M, WANG C, et al. Stochastic variational inference[J]. Journal of Machine Learning Research, 2013, 14(1):1303-1347.
[9] SONG W Z, YANG B, ZHAO X H, et al. A fast and scalable supervised topic modelusing stochastic variational inference and MapReduce[C]//Proceedings of the 2016 IEEE International Conference on Network Infrastructure and Digital Content. Piscataway, NJ:IEEE, 2016:94-98.
[10] GOPALAN P K, BLEI D M. Efficient discovery of overlapping communities in massive networks[J]. Proceedings of the National Academy of Sciences, 2013, 110(36):14534-14539.
[11] FAN K, ZHANG Y, HENAO R, et al. Triply stochastic variational inference for non-linear beta process factor analysis[C]//Proceedings of the 2016 IEEE 16th International Conference on Data Mining. Piscataway, NJ:IEEE, 2017:121-130.
[12] SENANAYAKE R, O'CALLAGHAN S, RAMOS F. Learning highly dynamic environments with stochastic variational inference[EB/OL].[2017-10-16]. DOI:10.1109/ICRA.2017.7989294.
[13] NESTEROV Y. Primal-dual subgradient methods for convex problems[J]. Mathematical Programming, 2009, 120(1):221-259.
[14] SCHMIDT M, ROUX N L, BACH F. Minimizing finite sums with the stochastic average gradient[J]. Mathematical Programming, 2017, 162(1/2):83-112.
[15] JOHNSON R, ZHANG T. Accelerating stochastic gradient descent using predictive variance reduction[C]//Proceedings of the 201326th International Conference on Neural Information Processing Systems. New York:Curran Associates Inc, 2013:315-323.
[16] XIAO L, ZHANG T. A proximal stochastic gradient method with progressive variance reduction[J]. SIAM Journal on Optimization, 2014, 24(4):2057-2075.
[17] 朱小辉,陶卿,邵言剑,等.一种减小方差求解非光滑问题的随机优化算法[J].软件学报,2015,26(11):2752-2761.(ZHU X H, TAO Q, SHAO Y J, et al. Stochastic optimization algorithm with variance reduction for solving non-smooth problems[J]. Journal of Software, 2015, 26(11):2752-2761.)
[18] REDDI S J, HEFNY A, SRA S, et al. Stochastic variance reduction for nonconvex optimization[EB/OL].[2017-10-16]. http://proceedings.mlr.press/v48/reddi16.pdf.
[19] OUYANG J H, LU Y, LI X M. Momentum online LDA for large-scale datasets[J]. Frontiers in Artificial Intelligence & Applications, 2014, 263:1075-1076.
[20] WANG C, CHEN X, SMOLA A, et al. Variance reduction for stochastic gradient optimization[C]//Proceedings of the 201326th International Conference on Neural Information Processing Systems. New York:Curran Associates Inc., 2013:181-189.
[21] RANGANATH R, WANG C, BLEI D M, et al. An adaptive learning rate for stochastic variational inference[EB/OL].[2017-10-16]. http://proceedings.mlr.press/v28/ranganath13.pdf.