Finite pool-based realizable active-learning instance

Let $(\mathcal{X},\mathrm{\Sigma })$ be a nonempty measurable space, let $D_X$ be a probability measure on it, and let $\mathcal{H}$ be a finite nonempty set of measurable classifiers $h:\mathcal{X}\to \{0,1\}$. A finite pool-based realizable active-learning instance consists of an ordered pool $U=(u_1,\dots ,u_m)\in {\mathcal{X}}^m$ for some $m\ge 0$, an unknown target $h^{\ast }\in \mathcal{H}$, and a deterministic exact label oracle $\mathcal{O}:\mathcal{X}\to \{0,1\}$ satisfying $\mathcal{O}(x)=h^{\ast }(x)$ at every queried point. A fresh feature $X\sim D_X$ has target label $h^{\ast }(X)$; the pool itself need not be sampled from $D_X$. For a set $Q\subseteq \{1,\dots ,m\}$ of queried indices with observed labels $(y_i{)}_{i\in Q}$, the version space is $V(Q,y)=\{h\in \mathcal{H}:h(u_i)=y_i\text{ for every }i\in Q\}$. For any $V\subseteq \mathcal{H}$, its disagreement region is $\mathrm{DIS}(V)=\{x\in \mathcal{X}:\mathrm{\exists }h,g\in V,h(x)\mathrm{\ne }g(x)\}$. Since $V$ is finite and every classifier is measurable, $\mathrm{DIS}(V)$ is measurable. The pointwise exact-oracle assumption is stronger than standard distributional PAC realizability: zero population risk only requires agreement almost surely under the joint law and does not prescribe oracle values at every pool point.

Supervised prediction problems: supplies the measurable instance and label spaces, measurable predictors, and joint-law framework specialized here to binary labels.

Realizable and agnostic PAC learning: defines standard PAC realizability by a finite-class member of zero population risk; that almost-sure condition alone does not prescribe pointwise labels on arbitrary pool entries.

Steve Hanneke, Theory of Active Learning, version 1.1, §§2.1–2.2 and §5.1

Daniel Joseph Hsu, Algorithms for Active Learning, Chapter 2