ora-0106

8.3 Ordinary PAC learning is the discrete case

The adjective categorical should earn its keep, but the new definition must recover the classical one exactly.

Proposition 8.3 PAC as discrete PACC

Let the objects of a discrete category \(\mathcal X\) be the elements of \(X\). Represent a classifier \(g:X\to Y\) by the corresponding functor \(g:\mathcal X\to \mathcal Y\), where \(\mathcal Y\) is discrete. For every \(x\), let \(q_x(g)=g(x)\), set \(d_{q_x}(y,y')=\mathbf1[y\neq y']\), and transport \(P\) from \(X\) to the probes \(q_x\). Then categorical probe risk is exactly \(R_P(g,f_\star )\), and Definition 8.2 is the ordinary PAC guarantee.

Proof ▼

The discrete categories contain no nonidentity composites or coherence data, so a probe asks only for the label of one object. Substitution in Equation 8.3 gives Equation 8.1; the outer sample probabilities in Equations 8.4 and 8.2 are identical.

Thus PACC is not a metaphorical use of PAC. It is a conservative extension in which the instance language can expose relations among observations. The classical case reappears when that relational structure is discarded.