Universal probability-free prediction
We construct universal prediction systems in the spirit of Popper's falsifiability and Kolmogorov complexity and randomness. These prediction systems do not depend on any statistical assumptions (but under the IID assumption they dominate, to within the usual accuracy, conformal prediction). Our constructions give rise to a theory of algorithmic complexity and randomness of time containing analogues of several notions and results of the classical theory of Kolmogorov complexity and randomness.
Code (0)
등록된 구현이 없습니다.
Tasks
Conformal PredictionPredictionSimilar Papers 제목 키워드 기반
Online Prediction of Stochastic Sequences with High Probability Regret Bounds
We revisit the classical problem of universal prediction of stochastic sequences with a finite time horizon $T$ known to the learner. The question we investigate is whether it is possible to derive vanishing regret bound…
Universal Discrete Filtering with Lookahead or Delay
We consider the universal discrete filtering problem, where an input sequence generated by an unknown source passes through a discrete memoryless channel, and the goal is to estimate its components based on the output se…
Batch Universal Prediction
Large language models (LLMs) have recently gained much popularity due to their surprising ability at generating human-like English sentences. LLMs are essentially predictors, estimating the probability of a sequence of w…
PredictionUnveiling Class-Labeling Structure for Universal Domain Adaptation
As a more practical setting for unsupervised domain adaptation, Universal Domain Adaptation (UDA) is recently introduced, where the target label set is unknown. One of the big challenges in UDA is how to determine the co…
Domain AdaptationUniversal Domain AdaptationUnsupervised Domain AdaptationA Data-free Universal Prior over Syntactic Structures
Probability is fundamental to theories of language comprehension, production, acquisition, and evolution, as well as to large language models. Existing theories estimate the probability of syntactic structures from langu…