Identifying Information From Observations With Uncertainty and Novelty
IEEE Transactions on Information Theory · 2026-09 · 72 (9) · 6879-6901
DOI: 10.1109/tit.2026.3706654 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Information Theory, 2026-09. Verfasst von Derek S. Prijatelj und 2 weiteren Autor:innen. Die Arbeit nennt 104 Literaturangaben. Gefördert von: National Science Foundation, Defense Advanced Research Projects Agency (DARPA) and the Army Research Office.
Abstract (Originalsprache)
A machine that learns a task from observations must encounter and process uncertainty and novelty, especially when it is to maintain performance when observing new information and to select the hypothesis that best fits the current observations. In this context, some key questions arise: what and how much information did the observations provide, how much information is required to identify the data-generating process, how many observations remain to get that information, and how does a predictor determine that it has observed novel information? We formalize identifying information to answer these questions and synthesize prior work. Identifying information are bits that verify or falsify a hypothesis as the data-generating process. We prove the information theoretic characteristics of computing hypothesis identification and the resulting sample complexity. We define hypothesis identification and sample complexity via the computation of an indicator function over a set of hypotheses, bridging algorithmic and probabilistic information. We detail the sample complexity and its properties for data-generating processes ranging from deterministic to ergodic stationary stochastic processes, which connects identifying information in finite steps with asymptotic statistics and PAC-learning. The indicator function’s computation naturally formalizes novel information and its identification from observations with respect to a hypothesis set, which detects a misspecified hypothesis set. We proved that a computable PAC-Bayes learners’ sample complexity distribution is determined by its moments in terms of the prior probability distribution over a fixed finite hypothesis set. Thus, an approximation of the sample complexity distribution is always computable within the desired precision that resources allow.
Förderung
- National Science Foundation
- Defense Advanced Research Projects Agency (DARPA) and the Army Research Office
Zitieren
APA
Prijatelj, D. S., Ireland, T. J., & Scheirer, W. J. (2026). Identifying Information From Observations With Uncertainty and Novelty. IEEE Transactions on Information Theory, 72(9), 6879-6901. https://doi.org/10.1109/tit.2026.3706654
Vancouver
Prijatelj DS, Ireland TJ, Scheirer WJ. Identifying Information From Observations With Uncertainty and Novelty. IEEE Transactions on Information Theory. 2026;72(9):6879-6901. doi:10.1109/tit.2026.3706654
BibTeX
@article{Prijatelj2026,
author = {Prijatelj, Derek S. and Ireland, Timothy J. and Scheirer, Walter J.},
title = {Identifying Information From Observations With Uncertainty and Novelty},
journal = {IEEE Transactions on Information Theory},
year = {2026},
volume = {72},
number = {9},
pages = {6879--6901},
doi = {10.1109/tit.2026.3706654}
}
EUVIMED