И.А. Ирхин, К.В. Воронцов. Сходимость алгоритма аддитивной регуляризации тематических моделей ... C. 56-68

УДК 519.853.4

MSC: 90C30, 68T50

DOI: 10.21538/0134-4889-2020-26-3-56-68

Полный текст статьи (Full text)

Работа выполнена в рамках проекта “Средства интеллектуального анализа больших массивов текстов” по Программе ЦК НТИ “Центр хранения и анализа больших данных”, поддерживаемого Министерством науки и высшего образования Российской Федерации по договору МГУ им. М.В. Ломоносова с Фондом поддержки проектов НТИ от 15.08.2019 № 7/1251/2019. Работа также частично поддержана РФФИ, проект 20-07-00936.

Задача вероятностного тематического моделирования заключается в следующем. По заданной коллекции текстовых документов требуется найти условное распределение каждого документа по темам и условное распределение каждой темы по словам (или термам). Для решения данной задачи используется принцип максимума правдоподобия. Задача имеет в общем случае бесконечное множество решений, т. е. является некорректно поставленной по Адамару. В рамках подхода ARTM — аддитивной регуляризации тематических моделей к основному критерию добавляется взвешенная сумма нескольких дополнительных критериев регуляризации. Численный метод для решения данной задачи — разновидность итерационного EM-алгоритма, который выписывается в общем виде для произвольного гладкого регуляризатора, в том числе и для линейной комбинации гладких регуляризаторов. В работе исследуется вопрос о сходимости данного итерационного процесса. Получены достаточные условия сходимости, при которых процесс сходится к стационарной точке регуляризованного логарифма правдоподобия. Полученные ограничения на регуляризатор оказались не слишком обременительными. В работе даны их интерпретации с точки зрения практической реализации алгоритма. Предложена модификация алгоритма, которая улучшает его сходимость без дополнительных затрат времени и памяти. В экспериментах на коллекции новостных текстов показано, что данная модификации позволяет не только ускорить сходимость, но и улучшить значение оптимизируемого критерия.

Ключевые слова: обработка текстов естественного языка, вероятностное тематическое моделирование, вероятностный латентный семантический анаиз (PLSA), латентное размещение Дирихле (LDA), аддитивная регуляризация тематических моделей (ARTM), EM-алгоритм, достаточные условия сходимости

СПИСОК ЛИТЕРАТУРЫ

1.   Apishev M.A., Vorontsov K.V. Learning topic models with arbitrary loss // Proc. of the 26th Conf. of FRUCT (Finnish-Russian University Cooperation in Telecommunications) Association. 2020. P. 30–37. doi: 10.23919/FRUCT48808.2020.9087559 

2.   Blei D.M., Ng A.Y., Jordan M.I. Latent Dirichlet allocation // J. Mach. Learn. Res. 2003. Vol. 3. P. 993–1022.

3.   Dempster A.P., Laird N.M., Rubin D.B. Maximum likelihood from incomplete data via the EM algorithm // J. Royal Statistical Society. Series B (methodological). 1977. Vol. 39, no. 1. P. 1–38.

4.   Frei O.I., Apishev M.A. Parallel non-blocking deterministic algorithm for online topic modeling // Analysis of Images, Social networks and Texts (AIST’2016) — Communications in Computer and Information Science (CCIS). Cham: Springer International Publ., 2016. Vol. 661. P. 132–144. doi: 10.1007/978-3-319-52920-2_13 

5.   Hofmann T. Probabilistic latent semantic indexing // Proc. of the 22nd Annual International ACM SIGIR Conf. on Research and Development in Information Retrieval. N Y: ACM, 1999. P. 50–57. doi: 10.1145/312624.312649 

6.   Kochedykov D.A., Apishev M.A., Golitsyn L.V., Vorontsov K.V. Fast and modular regularized topic modelling // Proc. of The 21st Conference of FRUCT (Finnish-Russian University Cooperation in Telecommunications) Association. The seminar on Intelligence, Social Media and Web (ISMW). (Helsinki, Finland, November 6–10, 2017). N Y: ACM, 2017. P. 182–193. doi: 10.23919/FRUCT.2017.8250181 

7.   Lang K. 20 newsgroups [e-resource]. 2008. Data retrieved from the dataset’s official website. URL: http://qwone.com/ jason/20Newsgroups/

8.   Tan Y., Ou Z. Topic-weak-correlated latent Dirichlet allocation // 7th International Symposium Chinese Spoken Language Processing (ISCSLP). 2010. P. 224–228. doi: 10.1109/ISCSLP.2010.5684906 

9.   Tikhonov A.N., Arsenin V.Y. Solution of ill-posed problems. N Y etc.: John Wiley & Sons, 1977. 258 p.

10.   Topsјe F. Some inequalities for information divergence and related measures of discrimination // Information Theory, IEEE Transactions on. 2000. Vol. 46, no. 4. P. 1602–1609. doi: 10.1109/18.850703 

11.   Vorontsov K.V. Additive regularization for topic models of text collections // Dokl. Math. 2014. Vol. 89, no. 3. P. 301–304. doi: 10.1134/S1064562414020185 

12.   Vorontsov K.V., Frei O.I., Apishev M.A., Romov P.A., Suvorova M.A. BigARTM: Open source library for regularized multimodal topic modeling of large collections // Analysis of Images, Social Networks and Texts (AIST’2015) — Communications in Computer and Information Science (CCIS). Cham: Springer International Publ., 2015. Vol. 542. P. 370–381. doi: 10.1007/978-3-319-26123-2_36 

13.   Vorontsov K.V., Potapenko A.A. Tutorial on probabilistic topic modeling: Additive regularization for stochastic matrix factorization // Analysis of Images, Social Networks and Texts (AIST’2014). Cham: Springer International Publ., 2014. Vol. 436. P. 29–46. doi: 10.1007/978-3-319-12580-0_3 

14.   Vorontsov K.V., Potapenko A.A. Additive regularization of topic models // Machine Learning: Special Issue on Data Analysis and Intelligent Optimization with Applications. 2015. Vol. 101, no. 1. P. 303–323. doi: 10.1007/s10994-014-5476-6 

15.   Vorontsov K.V., Potapenko A.A., Plavin A.V. Additive regularization of topic models for topic selection and sparse factorization // The Third International Symposium on Learning and Data Sciences (SLDS 2015). (April 20-22, 2015. Royal Holloway, University of London, UK.) Cham: Springer International Publ., 2015. P. 193–202. doi: 10.1007/978-3-319-17091-6_14 

16.   Wallach H.M., Mimno D.M., McCallum A. Rethinking LDA: Why priors matter // Advances in Neural Information Processing Systems. Red Hook: Curran Associates, 2009. P. 1973–1981.

17.   Wu C.J. On the convergence properties of the EM algorithm // The Annals of Statistics. 1983. Vol. 11, no. 1. P. 95–103. doi: 10.1214/aos/1176346060 

Поступила 20.07.2020

После доработки 6.08.2020

Принята к публикации 17.08.2020

Ирхин Илья Александрович
аспирант
Московский физико-технический институт
г. Москва
e-mail: ilirhin@gmail.com

Воронцов Константин Вячеславович
д.ф.-м.н., профессор РАН
зав. лаб. машинного интеллекта МФТИ
Московский физико-технический институт
г. Москва
e-mail: k.v.vorontsov@phystech.edu

Ссылка на статью: И.А. Ирхин, К.В. Воронцов. Сходимость алгоритма аддитивной регуляризации тематических моделей // Тр. Ин-та математики и механики УрО РАН. 2020. Т.26, № 3. C. 56-86

English

I.A. Irkhin, K.V. Vorontsov. Convergence of the algorithm of additive regularization of topic models

The problem of probabilistic topic modeling is as follows. Given a collection of text documents, find the conditional distribution over topics for each document and the conditional distribution over words or terms for each topic. Log-likelihood maximization is used to solve this problem. The problem has generally an infinite set of solutions, being ill-posed according to Hadamard. In the framework of Additive Regularization of Topic Models (ARTM), a weighted sum of regularization criteria is added to the main log-likelihood criterion. The numerical method for solving this optimization problem is a kind of iterative EM-algorithm. In ARTM it is inferred in a quite general form for an arbitrary smooth regularizer, as well as for a linear combination of smooth regularizers. This paper studies the problem of convergence of the EM iterative process. Sufficient conditions are obtained for the convergence to a stationary point of the regularized log-likelihood. The constraints imposed on the regularizer are not too restrictive. We give their interpretations from the point of view of the practical implementation of the algorithm. A modification of the algorithm is proposed that improves the convergence without additional time and memory costs. Experiments on the news text collection have shown that our modification both accelerates the convergence and improves the value of the criterion to which it converges.

Keywords: natural language processing, probabilistic topic modeling, probabilistic latent semantic analysis (PLSA), latent Dirichlet allocation (LDA), additive regularization of topic models (ARTM), EM-algorithm, sufficient conditions for convergence

Received July 20, 2020

Revised August 6, 2020

Accepted August 17, 2020

Funding Agency: The work was performed within the project “Text mining tools for big data” according to the program of the Competence Center of the National Technological Initiative “Center for Big Data Storage and Processing” supported by the Ministry of Science and Higher Education of the Russian Federation under the agreement between Moscow State University and the NTI Fund of August 15, 2019, no. 7/1251/2019. This work was also partially supported by the Russian Foundation for Basic Research (project no. 20-07-00936).

Konstantin Vyacheslavovich Vorontsov, Dr. Phys.-Math. Sci, Prof., Moscow Institute of Physics and Technology (State University), Dolgoprudny, 141701 Russia, e-mail: k.v.vorontsov@phystech.edu.

Il’ya Aleksandrovich Irkhin, doctoral student, Moscow Institute of Physics and Technology (State University), Dolgoprudny, 141701 Russia, e-mail: ilirhin@gmail.com

Cite this article as: I.A. Irkhin, K.V. Vorontsov. Convergence of the algorithm of additive regularization of topic models, Trudy Instituta Matematiki i Mekhaniki URO RAN, 2020, vol. 26, no. 3, pp. 56–68.

[References -> on the "English" button bottom right]