Predictive complexity and information

Michael V. Vyugin, Vladimir V. V'yugin

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

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

Аннотация

A new notion of predictive complexity and corresponding amount of information are considered. Predictive complexity is a generalization of Kolmogorov complexity which bounds the ability of any algorithm to predict elements of a sequence of outcomes. We consider predictive complexity for a wide class of bounded loss functions which are generalizations of square-loss function. Relations between unconditional KG(x) and conditional KG(x|y) predictive complexities are studied. We define an algorithm which has some "expanding property". It transforms with positive probability sequences of given predictive complexity into sequences of essentially bigger predictive complexity. A concept of amount of predictive information IG(y : x) is studied. We show that this information is non-commutative in a very strong sense and present asymptotic relations between values IG(y : x), IG(x : y), KG(x) and KG(y).

Язык оригиналаАнглийский
Название основной публикацииComputational Learning Theory - 15th Annual Conference on Computational Learning Theory, COLT 2002, Proceedings
РедакторыJyrki Kivinen, Robert H. Sloan
ИздательSpringer Verlag
Страницы90-105
Число страниц16
ISBN (электронное издание)354043836X, 9783540438366
СостояниеОпубликовано - 2002
Опубликовано для внешнего пользованияДа
Событие15th Annual Conference on Computational Learning Theory, COLT 2002 - Sydney, Австралия
Продолжительность: 8 июл. 200210 июл. 2002

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

НазваниеLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
Том2375
ISSN (печатное издание)0302-9743

Конференция

Конференция15th Annual Conference on Computational Learning Theory, COLT 2002
Страна/TерриторияАвстралия
ГородSydney
Период8/07/0210/07/02

Fingerprint

Подробные сведения о темах исследования «Predictive complexity and information». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать