On sequences with non-learnable subsequences

Vladimir V. V'Yugin

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

The remarkable results of Foster and Vohra was a starting point for a series of papers which show that any sequence of outcomes can be learned (with no prior knowledge) using some universal randomized forecasting algorithm and forecast-dependent checking rules. We show that for the class of all computationally efficient outcome-forecast-based checking rules, this property is violated. Moreover, we present a probabilistic algorithm generating with probability close to one a sequence with a subsequence which simultaneously miscalibrates all partially weakly computable randomized forecasting algorithms. According to the Dawid's prequential framework we consider partial recursive randomized algorithms.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - Third International Computer Science Symposium in Russia, CSR 2008, Proceedings
Pages302-313
Number of pages12
DOIs
Publication statusPublished - 2008
Externally publishedYes
Event3rd International Computer Science Symposium in Russia, CSR 2008 - Moscow, Russian Federation
Duration: 7 Jun 200812 Jun 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5010 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference3rd International Computer Science Symposium in Russia, CSR 2008
Country/TerritoryRussian Federation
CityMoscow
Period7/06/0812/06/08

Fingerprint

Dive into the research topics of 'On sequences with non-learnable subsequences'. Together they form a unique fingerprint.

Cite this