Probable approximate correctness

1. Some formalism

1.1. Definition.   Let $𝑋$ be an instance space comprising the objects in a learner’s world. A concept $𝑐\subseteq 𝑋$ is a subset of the instance space. A concept corresponds intuitively e.g. to the set of instances of some class—e.g. the red ones, diseased ones or the ones of mass exceeding ten kilogrammes. Instances within $𝑐$ are positive examples, and otherwise are negative. A concept class $𝐶$ over $𝑋$ is a set of concepts over $𝑋$.

1.2. Definition.   A learning algorithm is given positive and negative examples from an unknown ‘target’ concept $𝑐$ from a concept class $𝐶$. The examples are instances drawn from an arbitrary target distribution $𝐷$ over $𝑋$ and take the form $⟨𝑥,𝑐\left(𝑥\right)⟩$ where $𝑐\left(𝑥\right)$ is a labelling of whether $𝑥\in 𝑐$.

1.3. Example.   The instance class of human beings contains (for instance) tall and short members. Suppose we know that that the word ‘tall’ adverts to some concept that adverts to the height of human beings. We therefore know that height’s meaning is given by a concept that is a member of the concept class of partitions over human beings by height. A learner can then be thought of as being given examples of human beings and whether they are tall or not. (This example is drawn from Kearns and Vazirani (An Introduction to Computational Learning Theory: 2).)

1.4. Definition.   Suppose that the learning algorithm formulates some hypothesis $ℎ:𝑋\to \left\{0,1\right\}$ with respect to a target concept $𝑐:𝑋\to \left\{0,1\right\}$. Then its error with respect to a target distribution $𝐷$ is

$$\text{err}\left(ℎ;𝑐,𝐷\right)={𝑃}_{𝑥\sim 𝐷}\left[ℎ\left(𝑥\right)\ne 𝑐\left(𝑥\right)\right].$$

That is, the rate at which it mislabels examples according to $𝐷$.

1.5. Assumption.   We will assume that, for each $𝑅$, there is an associated mapping size ${\mathrm{\Sigma }}^{\ast }\to 𝑁$ corresponding to a natural size $\text{size}\left(ℎ\right)$ for $ℎ\in {\mathrm{\Sigma }}^{\ast }$, within a polynomial bound of the length of a binary representation.

1.6. Remark.   The class of hypotheses a learning algorithm may generate need not be the same as the class of concepts. We can define hypothesis classes exactly as concept classes.

1.7. Definition.   A hypothesis class $𝐻$ is polynomially evaluable iff each $ℎ\in 𝐻$ is evaluable in polynomial time.

1.8. Definition.   We will assume that there is also a notion of the size of instances; in general, we restrict ourselves to inputs over ${𝑋}_{𝑛}={\left\{0,1\right\}}^{𝑛}$ or ${ℝ}^{𝑛}$.

1.9. Definition.   Let ${𝐶}_{𝑛}$ be some concept class defined over each ${𝑋}_{𝑛}$ for each $𝑛\in {\mathbb{N}}^{+}$, $𝐶={\bigcup }_{𝑛⩾1}{𝐶}_{𝑛}$, and $𝑋={\bigcup }_{𝑛⩾1}{𝑋}_{𝑛}$. $𝐶$ is polynomially approximately correctly learnable using an hypothesis class $𝐻$ if and onloy if there is a learning algorithm $𝐿$ such that for each $𝑛\in \mathbb{N}$, $𝑐\in {𝐶}_{𝑛}$, distribution $𝐷$ over ${𝑋}_{𝑛}$, and $𝛿,𝜀\in \left(0,\frac{1}{2}\right)$, $𝐿$, given access to labelled examples in constant time, and inputs $𝑛$, $\text{size}\left(𝑐\right)$, $𝜀$ and $𝛿$ outputs some $ℎ\in {𝐻}_{𝑛}$ such that, with probability over $𝐷$ of at least $1-𝛿$, $\text{err}\left(ℎ\right)⩽𝜀$, $𝐻$ is polynomiially evaluable, and the number of examples drawn is bounded by a polynomial in $𝑛$, $\text{size}\left(𝑐\right)$, $\frac{1}{𝜀}$, and $\frac{1}{𝛿}$; and it is efficiently PAC-learnable iff its running time is polymomial in those same variables.

2. PAC-learnability and language

We might attempt to take language-learning tasks to be feasible only if all the learning tasks involved are PAC-learnable. This approach was perhaps first advocated by de Wolf (‘Applications’), but it has been pursued by others (see e.g. Clark and Lappin (‘Grammar’), Clark and Lappin (‘Acquisition’)).

On these grounds, for instance, the non–pac-learnability of even regular languages (Kearns and Valiant, ‘Limitations’: theorem 5) are taken to suggest that the concept class of human languages we are tasked with learning as children is simply infeasible, absent universal grammar (?nowak2001.?)

In addition to the reasons for scepticism about the application of Cobham–Edmonds to humans adduced above, I think there is another reason to be sceptical that PAC-learnability is the appropriate régime in the first place.

What, for instance, justifies $𝛿$’s and $𝜀$’s being arbitrarily small in the definition? de Wolf (‘Applications’: § 2.4.4) offers an intuitive argument.

It seems fair to assume that giving a child more example sentences, as wella s more time to think about those sentences over, will increase the probability that it lerans an approximately correct language and will decrease the number of errors. From this I conclude that…pac learnability [is] at least right in spirit.

But this is not quite right; it might be that $𝜀=0.01-2^{-𝑛}$ after $𝑛$ data, which would meet the monotonicity requirement without converging to $0$. And this hardly shows that the polynomial bound can be justified. A polynomial bound could initially be reasonable even if reducing the rate of error becomes increasingly difficult over time—it might be easy to correctly learn regular verbs, for example, and yet rather more time-consuming to learn the more complicated rules of grammar.

We might just PAC-learnability as a criterion abductively, e.g. if arguments from universal grammar were to have been uniformly vindicated in empirical linguistics; but given the mixed record there, that argument is unconvincing.