The Next Symbol Prediction Problem: PAC-learning and its relation to Language Models

Bhattamishra et al., The Next Symbol Prediction Problem

0.1. Definition. (Deterministic finite automaton)   A deterministic finite automaton is a tuple $⟨𝑄,\mathrm{\Sigma },𝛿,{𝑞}_0,{𝐹}_{𝐴}⟩$ where—

1. $𝑄$ is a finite set of states,
2. $\mathrm{\Sigma }$ is a finite alpahbet,
3. $𝛿:𝑄\times \mathrm{\Sigma }\to 𝑄$ is a transition function, and
4. ${𝐹}_{𝐴}\subseteq 𝑄$ is a set of accepting states.

0.2. Definition.   Let ${𝑥}_{:𝑛}$ denote the prefix of $𝑛$ up to length $𝑛$, $𝜆$ the empty string, and $\text{Pref}\left(𝑥\right)=\left\{{𝑥}_{:𝑘}:0⩽𝑘⩽|𝑥|\right\}$, and likewise on a set of strings. For a state $𝑞$, $𝐹\left(𝑞\right)=1$ iff $𝑞\in {𝐹}_{𝑎}$ and 0 otherwise. ${𝑞}_{\text{dead}}$ denotes a dead state in a reject state where all symbols have a transition to the same dead state. $𝜑\left(𝑞,𝜎\right)=1$ if $𝛿\left(𝑞,𝜎\right)={𝑞}_{\text{dead}}$ and 0 otherwise.

0.3. Definition. (Next symbol prediction)   The example oracle produces only positive exaamples. However, for every prefix of an input, it provides the legal symbols for the next step, and the label $𝑐\left({𝑥}_{:𝑛}\right)$ of the prefix. Thus information about negative examples is given by the labels of prefixes and the valid symbols for the next step.

The task of a predictor $ℎ$ is to predict, for any input $𝑥$, the next set of valid symbols, and the labels for each prefix, i.e. $\left(|\mathrm{\Sigma }|+1\right)\left(𝑙+1\right)$ labels. $ℎ$ has error 1 on an input if any of the labels is incorrect, and $0$ otherwise. Then the error of $ℎ$ with respect to a target language $𝑐$ and distribution $𝐷$ is

$${\mathrm{ℒ︀}}_{\text{NSP}}\left(ℎ;𝑐,𝐷\right)={𝔼}_{𝐷\left[\text{err}\left(ℎ\left(𝑥\right),𝑐\left(𝑥\right)\right)\right]}.$$

0.4. Definition. (PAC-learning under next symbol prediction)   A concept class $𝐶$ is PAC-learnable in the next symbol prediction setting with hypothesis class $𝐻$ if there is a learning algorithm $𝐿$ such that for every $𝑐\in 𝐶$ and $𝐷$ over $𝑋$ for every $0<𝜀,𝛿<0.5$ if $𝐿$ is given access to…