ora-0104

8.1 The PAC template

Let \(X\) be an instance space, \(Y\) a label space, \(P\) an unknown distribution on \(X\), and \(f_\star :X\to Y\) a target. For a hypothesis \(g:X\to Y\), the ordinary zero–one risk is

\begin{equation} R_P(g,f_\star ) =\Pr _{x\sim P}\{ g(x)\neq f_\star (x)\} =\sum _{x:g(x)\neq f_\star (x)}P(x) \end{equation}

8.1

in the discrete case. A PAC learner receives an independent sample \(S\sim P^m\) and, for prescribed \(0{\lt}\epsilon ,\delta {\lt}1\), returns \(g_S\) such that

\begin{equation} \Pr _{S\sim P^m}\{ R_P(g_S,f_\star )\leq \epsilon \} \geq 1-\delta . \end{equation}

8.2

The realizable theory assumes \(f_\star \) belongs to the hypothesis class. The agnostic theory instead compares the learner with the best available hypothesis. These two probability spaces must not be confused: \(P\) weights future instances, whereas \(1-\delta \) measures confidence over the sampled training transcript.

PACC retains this quantifier pattern and changes what counts as an instance, an answer, and an error. Its instances are typed questions about a candidate world. Its answers may be objects, arrows, diagrams, universal witnesses, or spaces of coherent fillers. Its loss must be invariant under the equivalence appropriate to those answers.