Non-linear inequalities between predictive and kolmogorov complexities

Michael V. Vyugin, Vladimir V. V’Yugin

Результат исследований: Глава в книге, отчете, сборнике статейМатериалы для конференциирецензирование

2 Цитирования (Scopus)

Аннотация

Predictive complexity is a generalization of Kolmogorov complexity. It corresponds to an “optimal” prediction strategy which gives a lower bound to ability of any algorithm to predict elements of a sequence of outcomes. A variety of types of loss functions makes it interesting to study relations between corresponding predictive complexities. Non-linear inequalities (with variable coefficients) between predictive complexity KG(x) of non-logarithmic type and Kolmogorov complexity K(x) (which is close to predictive complexity for logarithmic loss function) are the main subject of consideration in this paper. We deduce from these inequalities an asymptotic relation (formula presented) when n→∞, where a is a constant and l(x) is the length of a sequence x. An analogous asymptotic result holds for relative complexities K(x)/l(x) and KG(x)/l(x). To obtain these inequalities we present estimates of the cardinality of all sequences of given predictive complexity.

Язык оригиналаАнглийский
Название основной публикацииAlgorithmic Learning Theory - 12th International Conference, ALT 2001, Proceedings
РедакторыRoni Khardon, Naoki Abe, Thomas Zeugmann
ИздательSpringer Verlag
Страницы190-204
Число страниц15
ISBN (печатное издание)3540428755, 9783540428756
СостояниеОпубликовано - 2001
Опубликовано для внешнего пользованияДа
Событие12th Annual Conference on Algorithmic Learning Theory, ALT 2001 - Washington, Соединенные Штаты Америки
Продолжительность: 25 нояб. 200128 нояб. 2001

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том2225
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

Конференция

Конференция12th Annual Conference on Algorithmic Learning Theory, ALT 2001
Страна/TерриторияСоединенные Штаты Америки
ГородWashington
Период25/11/0128/11/01

Fingerprint

Подробные сведения о темах исследования «Non-linear inequalities between predictive and kolmogorov complexities». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать