LibreTimes

Works added this month

260 results

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