# Identifying Information from Observations with Uncertainty and Novelty

arXiv: https://arxiv.org/abs/2501.09331 · HTML: https://mlsanity.com/paper/2501.09331/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 126 references that are in the map.
- First posted on arXiv 16 Jan 2025.

## Builds on (most cited first, 11 of 11)

- [Auto-Encoding Variational Bayes](https://mlsanity.com/paper/1312.6114/) (2013)
- [A Unifying Review of Deep and Shallow Anomaly Detection](https://mlsanity.com/paper/2009.11732/) (2020)
- [User-friendly introduction to PAC-Bayes bounds](https://mlsanity.com/paper/2110.11216/) (2021)
- [Towards Open World Recognition](https://mlsanity.com/paper/1412.5687/) (2014)
- [A Primer on PAC-Bayesian Learning](https://mlsanity.com/paper/1901.05353/) (2019)
- [Bayesian Model Selection, the Marginal Likelihood, and Generalization](https://mlsanity.com/paper/2202.11678/) (2022)
- [Towards Robust Pattern Recognition: A Review](https://mlsanity.com/paper/2006.06976/) (2020)
- [Variational Bayes under Model Misspecification](https://mlsanity.com/paper/1905.10859/) (2019)
- [On characterizations of learnability with computable learners](https://mlsanity.com/paper/2202.05041/) (2022)
- [On Computable Online Learning](https://mlsanity.com/paper/2302.04357/) (2023)
- [Toward Defining a Domain Complexity Measure Across Domains](https://mlsanity.com/paper/2303.04141/) (2023)

## Abstract (arXiv)

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 works. Identifying information are bits that verify or falsify a hypothesis as the data-generating process. In this formalization, we prove the information theoretic characteristics of the computation of 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 processes to ergodic stationary stochastic processes, which connect the notion of 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 also 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, and thus an approximation of the sample complexity distribution is always computable within the desired precision that resources allow.