LibreTimes

Works

45 results

Convergence of the Algorithm of Additive Regularization of Topic Models

2021Journal articleI. A. Irkhin, Константин Вячеславович Воронцов

Proceedings of the Steklov Institute of Mathematics

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 generally has an infinite set of solutions and is 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 an iterative EM-algorithm written in a 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 a news text collection have shown that our modification both accelerates the convergence and improves the value of the criterion to be optimized.
0
1

Sharpness Estimation of Combinatorial Generalization Ability Bounds for Threshold Decision Rules

2021Journal articleSh. Kh. Ishkina, Константин Вячеславович Воронцов

Automation and Remote Control

This article is devoted to the problem of calculating an exact upper bound for the functionals of the generalization ability of a family of one-dimensional threshold decision rules. An algorithm is investigated that solves the stated problem and is polynomial in the total number of samples used for training and validation and in the number of training samples. A theorem is proved for calculating an estimate for the functional of expected overfitting and an estimate for the error rate of the method for minimizing empirical risk on a validation set. The exact bounds calculated using the theorem are compared with the previously known quick-to-compute upper bounds so as to estimate the orders of overestimation of the bounds and to identify the bounds that could be used in real problems.
0
3

Hierarchical Interpretable Topical Embeddings for Exploratory Search and Real-Time Document Tracking

2020Journal articleAnastasia Ianina, Константин Вячеславович Воронцов

International Journal of Embedded and Real-Time Communication Systems

Real-time monitoring of scientific papers and technological news requires fast processing of complicated search demands motivated by thematically relevant information acquisition. For this case, the authors develop an exploratory search engine based on probabilistic hierarchical topic modeling. Topic model gives a low dimensional sparse interpretable vector representation (topical embedding) of a text, which is used for ranking documents by their similarity to the query. They explore several ways of comparing topical vectors including searching with thematically homogeneous text segments. Topical hierarchies are built using the regularized EM-algorithm from BigARTM project. The topic-based search achieves better precision and recall than other approaches (TF-IDF, fastText, LSTM, BERT) and even human assessors who spend up to an hour to complete the same search task. They also discover that blending hierarchical topic vectors with neural pretrained embeddings is a promising way of enriching both models that helps to get precision and recall higher than 90
0
1

Mining Ethnic Content Online with Additively Regularized Topic Models

2016Journal articleMurat Apishev, Sergei Koltcov, Olessia Koltsova, Sergey Nikolenko +1

Computación y Sistemas

Social studies of the Internet have adopted large-scale text mining for unsupervised discovery of topics related to specific subjects. A recently developed approach to topic modeling, additive regularization of topic models (ARTM), provides fast inference and more control over the topics with a wide variety of possible regularizers than developing LDA extensions. We apply ARTM to mining ethnic-related content from Russian-language blogosphere, introduce a new combined regularizer, and compare models derived from ARTM with LDA. We show with human evaluations that ARTM is better for mining topics on specific subjects, finding more relevant topics of higher or comparable quality.
0
2

Regularization, robustness and sparsity of probabilistic topic models

2012Journal articleКонстантин Вячеславович Воронцов, Anna Alexandrovna Potapenko

Computer Research and Modeling

We propose a generalized probabilistic topic model of text corpora which can incorporate heuristics of Bayesian regularization, sampling, frequent parameters update, and robustness in any combinations. Wellknown models PLSA, LDA, CVB0, SWB, and many others can be considered as special cases of the proposed broad family of models. We propose the robust PLSA model and show that it is more sparse and performs better that regularized models like LDA.
0
4

Exact combinatorial bounds on the probability of overfitting for empirical risk minimization

2010Journal articleКонстантин Вячеславович Воронцов

Pattern Recognition and Image Analysis

Three general methods for obtaining exact bounds on the probability of overfitting are proposed within statistical learning theory: a method of generating and destroying sets, a recurrent method, and a blockwise method. Six particular cases are considered to illustrate the application of these methods. These are the following model sets of predictors: a pair of predictors, a layer of a Boolean cube, an interval of a Boolean cube, a monotonic chain, a unimodal chain, and a unit neighborhood of the best predictor. For the interval and the unimodal chain, the results of numerical experiments are presented that demonstrate the effects of splitting and similarity on the probability of overfitting.
0
4

Combinatorial Substantiation of Learning Algorithms

2009Journal articleКонстантин Вячеславович Воронцов

Abstract—Combinatorial cross-validation functionals that characterize the generalization performance of learning algorithms are considered. Upper bounds are derived that are tighter than those in the Vapnik–Chervonenkis statistical theory. The initial data set is not assumed to be independent, identically distributed, or even random. The effect of localization of an algorithm family is described, and the concept of a local growth function is introduced. The basic principles of statistical theory are revised by using the combinatorial approach. The basic causes of complexity bound overestimation are analyzed. Keywords: computational learning theory, learning method, VC-dimension, local growth function, local effective VC-dimension. In learning theory, the generalization performance of a learning algorithm is characterized by the probability of an error. Unfortunately, this hypothetical quantity cannot be calculated or sometimes even satisfactorily evaluated, for example, in the case of small data sets. At the same time, in practice, any learning system deals only with finite data sets, both training and testing. Therefore, it is reasonable to characterize the generalization performance of algorithms with respect to finite data sets. Learning performance is empirically quantified by using independent testing sets, bootstrap, or cross-validation [1]. It is shown in this paper that upper bounds for cross-validation performance functionals can be derived without resorting

0
4

Splitting and similarity phenomena in the sets of classifiers and their effect on the probability of overfitting

2009Journal articleКонстантин Вячеславович Воронцов

Pattern Recognition and Image Analysis

It is shown that computationally tight bounds for the probability of overfitting can be obtained only by simultaneous consideration of the following two properties of classifier sets: splitting into error levels and similarity of classifiers. For a set consisting of only two classifiers, an exact bound is obtained for the probability of overfitting. This is the simplest learning task that exhibits overfitting and the effects of splitting and similarity, which reduce the probability of overfitting. For a more complex case—a chain of classifiers—an experiment is carried out in which the effects of splitting and similarity are estimated separately. It is shown that reasonably low probabilities of overfitting can be obtained only for the sets that possess both properties.
0
2

Combinatorial probability and the tightness of generalization bounds

2008Journal articleКонстантин Вячеславович Воронцов

Pattern Recognition and Image Analysis

Accurate prediction of the generalization ability of a learning algorithm is an important problem in computational learning theory. The classical Vapnik-Chervonenkis (VC) generalization bounds are too general and therefore overestimate the expected error. Recently obtained data-dependent bounds are still overestimated. To find out why the bounds are loose, we reject the uniform convergence principle and apply a purely combinatorial approach that is free of any probabilistic assumptions, makes no approximations, and provides an empirical control of looseness. We introduce new data-dependent complexity measures: a local shatter coefficient and a nonscalar local shatter profile , which can give much tighter bounds than the classical VC shatter coefficient . An experiment on real datasets shows that the effective local measures may take very small values; thus, the effective local VC dimension takes values in [0, 1] and therefore is not related to the dimension of the space.

0
4