8 Probably Approximately Categorically Correct Learning

From PAC prediction to approximate compositional identification

Exact identification is an austere endpoint. Even a finite category can have many presentations, and an interacting learner may never receive the probes that distinguish two worlds everywhere. For the purposes of prediction, repair, or decision, however, the learner may need only to answer most of the relevant categorical questions correctly. This chapter introduces Probably Approximately Categorically Correct (PACC) learning: a statistical relaxation of UOCL in which approximation is measured by an equivalence-invariant doctrine of categorical probes.

The phrase needs to be parsed carefully. Probably refers to the random transcript observed by the learner. Approximately refers to its risk on future probes. Categorically correct requires the hypothesis to remain a genuine object of the declared categorical hypothesis class and evaluates it through categorical structure, not through a syntactic edit distance between presentations. PACC therefore weakens identification without weakening associativity, identities, coherence, or any other axiom of the chosen hypothesis doctrine.