Active querying, version spaces, and abstention — Examples

Fix $n\ge 1$ and ordered distinct points $\mathcal{X}=\{x_1<\cdots <x_n\}$ with sigma-algebra $2^{\mathcal{X}}$. Let $D_X$ be any probability measure on $(\mathcal{X},2^{\mathcal{X}})$, let $\mathcal{H}=\{h_k:0\le k\le n\}$ with $h_k(x_j)=1$ exactly when $j>k$, take the pool $U=(x_1,\dots ,x_n)$, target $h_{k^{\ast }}$ for some $k^{\ast }\in \{0,\dots ,n\}$, and exact oracle $\mathcal{O}(x_j)=h_{k^{\ast }}(x_j)$. Consider the adaptive median selector that maintains the candidate interval $[a,b]\subseteq \{0,\dots ,n\}$, initially $[0,n]$; while $a<b$, it sets $s=b-a+1$, queries $x_j$ with $j=a+\lfloor s\mathrm{/}2\rfloor$, and retains the threshold indices matching the returned label. It stops when one candidate remains. This selector identifies $k^{\ast }$ in at most the least integer $q\ge 0$ such that $2^q\ge n+1$ queries. It is a separate median-query rule; the A-page procedure scans the fixed pool in ascending order.

Finite pool-based realizable active-learning instance: supplies the finite-class, ordered-pool, target, and exact-oracle conventions used here.

Daniel Joseph Hsu, Algorithms for Active Learning, Chapter 1 §1.2

For $n=7$, each internal node is the queried pool point, each edge is its exact binary label, and each terminal label is the remaining threshold-index interval. Thus $x_4$ splits $[0,7]$ evenly; the next median queries $x_2$ or $x_6$. The figure records only these first two levels; the proof below establishes the general branch sizes and query bound without relying on the diagram.

For any integer $m\ge 2$, let $\mathcal{X}=\{x_1,\dots ,x_m\}$ with its full sigma-algebra, let $D_X$ be any probability measure on $\mathcal{X}$, and define $h_{\ast }(x_j)=1$ for every $j$ and $h_i(x_j)=0$ exactly when $j=i$, for $1\le i,j\le m$. Let $\mathcal{H}=\{h_{\ast },h_1,\dots ,h_m\}$, pool $U=(x_1,\dots ,x_m)$, target $h_{\ast }$, exact oracle $\mathcal{O}(x_j)=1$, and query budget $b\ge m$. The fixed ascending-scan procedure queries every pool index, receives label $1$ at each query, removes exactly one alternative hypothesis per query, and ends with $V=\{h_{\ast }\}$ after $m=\mathrm{\mid }\mathcal{H}\mathrm{\mid }-1$ queries. For every integer $k\ge 2$, the subfamily $m=2^k-1$ has class size $2^k$ and query count $2^k-1$, so the query count is not bounded by any fixed constant times $\log \mathrm{\mid }\mathcal{H}\mathrm{\mid }$ as $k$ varies; $\log$ denotes the natural logarithm.

Finite pool-based realizable active-learning instance: supplies the exact-target finite-pool model.

Finite-pool version-space query procedure: specifies the ascending scan and update rule used in this example.

The natural logarithm as the inverse of the exponential function: defines the natural logarithm used in the asymptotic comparison.

Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm: supplies the product law and strict monotonicity for that comparison.

In a finite pool-based instance with finite nonempty classifier class $\mathcal{H}$, exact target $h^{\ast }\in \mathcal{H}$, ordered pool $U=(u_1,\dots ,u_m)$, and exact oracle, run the ascending-scan procedure with any query budget $b\ge 0$. If $m=0$, it returns $V=\mathcal{H}$ with no pool records and no queries. If $\mathcal{H}=\{h_0\}$ and $h^{\ast }=h_0$, it predicts every pool entry without querying, including when $b=0$. For a general $\mathcal{H}$ with $b=0$, it predicts each unanimous entry before the first disagreement, then marks that index and the remaining pool suffix as abstentions; it makes no queries.

Finite pool-based realizable active-learning instance: fixes the finite-pool, exact-target model used in the boundary cases.

Finite-pool version-space query procedure: specifies the ascending scan, unanimous-prediction priority, and zero-budget stopping behavior.