Kolmogorov’s Structure Functions with an Application to the Foundations of Model Selection

Авторы: Vereshchagin Nikolai K., Vitányi Paul M.B.
Сборник: 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings
Год издания: 2002
Место издания: IEEE Computer Society
Первая страница: 751
Последняя страница: 760
DOI: 10.1109/SFCS.2002.1182000
Аннотация: Kolmogorov (1974) proposed a non-probabilistic approach to statistics, an individual combinatorial relation between the data and its model. We vindicate, for the first time, the rightness of the original "structure function", proposed by Kolmogorov: minimizing the data-to-model code length (finding the ML estimator or MDL estimator), in a class of contemplated models of prescribed maximal (Kolmogorov) complexity, always results in a model of best fit (expressed as minimal randomness deficiency). We show that both the structure function and the minimum randomness deficiency function can assume all shapes over their full domain (improving an old result of L.A. Levin and both an old and a recent one of VV Vyugin). We determine the (un)computability properties of the various functions and "algorithmic sufficient statistic".
Добавил в систему: Верещагин Николай Константинович

	ИСТИНА	Войти в систему Регистрация
	ИСТИНА ИНХС РАН
	Главная Поиск Статистика О проекте Помощь

ИСТИНА