July 2024 – Thinking

This blog collects some of my notes on classical computational learning theory, based on my reading of Kearns and Vazirani. The results are (almost) all from their book, the sloganising (and mistakes, no doubt) are mine.

The Probably Approximately Correct (PAC) Framework

Definition (Instance Space). An instance space is a set, typically denoted $X$ . It is the set of objects we are trying to learn about.

Definition (Concept). A concept $c$ over $X$ is a subset of the instance space $X$ .

Although not covered in Kearns and Vazirani, in general it is possible to generalise beyond Boolean membership to some degree of uncertainty or fuzziness – I hope to cover this in a future blog post.

Definition (Concept Class). A concept class ${\mathcal C}$ is a set of concepts, i.e. ${\mathcal C} \subset \mathcal{P}(X)$ , where $\mathcal P$ denotes power set. We will follow Kearns and Vazirani and also use $c$ to denote the corresponding indicator function $c : X \to \{0,1\}$ .

In PAC learning, we assume ${\mathcal C}$ is known, but the target class $c \in {\mathcal C}$ is not. However, it doesn’t seem a jump to allow for unknown target class, in an appropriate approximation setting – I would welcome comments on established frameworks for this.

Definition (Target Distribution). A target distribution ${\mathcal D}$ is a probability distribution over $X$ .

In PAC learning, we assume ${\mathcal D}$ is unknown.

Definition (Oracle). An oracle is a function $EX(c,{\mathcal D})$ taking a concept class and a distribution, and returning a labelled example $(x, c(x))$ where $x$ is drawn randomly and independently from ${\mathcal D}$ .

Definition (Error). The error of a hypothesis concept class $h \in {\mathcal C}$ with reference to a target concept class $c \in {\mathcal C}$ and target distribution ${\mathcal D}$ , is $\text{error}(h) = Pr_{x \in {\mathcal D}}\left\{ c(x) \neq h(x) \right\}$ , where $Pr$ denotes probability.

Definition (Representation Scheme). A representation scheme for a concept class ${\mathcal C}$ is a function ${\mathcal R} : \Sigma^* \to {\mathcal C}$ where $\Sigma$ is a finite alphabet of symbols (or – following the Real RAM model – a finite alphabet augmented with real numbers).

Definition (Representation Class). A representation class is a concept class together with a fixed representation scheme for that class.

Definition (Size). We associate a size $\text{size}(\sigma)$ with each string from a representation alphabet $\sigma \in \Sigma^*$ . We similarly associate a size with each concept $c$ via the size of its minimal representation $\text{size}(c) = \min_{R(\sigma) = c} \text{size}(\sigma)$ .

Definition (PAC Learnable). Let ${\mathcal C}$ and ${\mathcal H}$ be representation classes classes over $X$ , where ${\mathcal C} \subseteq {\mathcal H}$ . We say that concept class ${\mathcal C}$ is PAC learnable using hypothesis class ${\mathcal H}$ if there exists an algorithm that, given access to an oracle, when learning any target concept $c \in {\mathcal C}$ over any distribution ${\mathcal D}$ on $X$ , and for any given $0 < \epsilon < 1/2$ and $0 < \delta < 1/2$ , with probability at least $1-\delta$ , outputs a hypothesis $h \in {\mathcal H}$ with $\text{error}(h) \leq \epsilon$ .

Definition (Efficiently PAC Learnable). Let ${\mathcal C}_n$ and ${\mathcal H}_n$ be representation classes classes over $X_n$ , where ${\mathcal C}_n \subseteq {\mathcal H}_n$ for all $n$ . Let $X_n = \{0,1\}^n$ or $X_n = {\mathbb R}^n$ . Let $X = \cup_{n \geq 1} X_n$ , ${\mathcal C} = \cup_{n \geq 1} {\mathcal C_n}$ , and ${\mathcal H} = \cup_{n \geq 1} {\mathcal H_n}$ . We say that concept class ${\mathcal C}$ is efficiently PAC learnable using hypothesis class ${\mathcal H}$ if there exists an algorithm that, given access to a constant time oracle, when learning any target concept $c \in {\mathcal C}_n$ over any distribution ${\mathcal D}$ on $X$ , and for any given $0 < \epsilon < 1/2$ and $0 < \delta < 1/2$ :

Runs in time polynomial in $n$ , $\text{size}(c)$ , $1/\epsilon$ , and $1/\delta$ , and
With probability at least $1-\delta$ , outputs a hypothesis $h \in {\mathcal H}$ with $\text{error}(h) \leq \epsilon$ .

There is much of interest to unpick in these definitions. Firstly, notice that we have defined a family of classes parameterised by dimension $n$ , allowing us to talk in terms of asymptotic behaviour as dimensionality increases. Secondly, note the key parameters of PAC learnability: $\delta$ (the ‘probably’ bit) and $\epsilon$ (the ‘approximate’ bit). The first of these captures the idea that we may get really unlucky with our calls to the oracle, and get misleading training data. The second captures the idea that we are not aiming for certainty in our final classification accuracy, some pre-defined tolerance is allowable. Thirdly, note the requirements of efficiency: polynomial scaling in dimension, in size of the concept (complex concepts can be harder to learn), in error rate (the more sloppy, the easier), and in probability of algorithm failure to find a suitable hypothesis (you need to pay for more certainty). Finally, and most intricately, notice the separation of concept class from hypothesis class. We require the hypothesis class to be at least as general, so the concept we’re trying to learn is actually one of the returnable hypotheses, but it can be strictly more general. This is to avoid the case where the restricted hypothesis classes are harder to learn; Kearns and Vazirani, following Pitt and Valiant, give the example of learning the concept class 3-DNF using the hypothesis class 3-DNF is intractable, yet learning the same concept class with the more general hypothesis class 3-CNF is efficiently PAC learnable.

Occam’s Razor

Definition (Occam Algorithm). Let $\alpha \geq 0$ and $0 \leq b < 1$ be real constants. An algorithm is an $(\alpha,\beta)$ -Occam algorithm for ${\mathcal C}$ using ${\mathcal H}$ if, on an input sample $S$ of cardinality $m$ labelled by membership in $c \in {\mathcal C}_n$ , the algorithm outputs a hypothesis $h \in {\mathcal H}$ such that:

$h$ is consistent with $S$ , i.e. there is no misclassification on $S$
$\text{size}(h) \leq \left(n \cdot \text{size}(c)\right)^\alpha m^\beta$

Thus Occam algorithms produce succinct hypotheses consistent with data. Note that the size of the hypothesis is allowed to grow only mildly – if at all – with the size of the dataset (via $\beta$ ). Note, however, that there is nothing in this definition that suggests predictive power on unseen samples.

Definition (Efficient Occam Algorithm). An $(\alpha,\beta)$ -Occam algorithm is efficient iff its running time is polynomial in $n$ , $m$ , and $\text{size}(c)$ .

Theorem (Occam’s Razor). Let $A$ be an efficient $(\alpha,\beta)$ -Occam algorithm for ${\mathcal C}$ using ${\mathcal H}$ . Let ${\mathcal D}$ be the target distribution over $X$ , let $c \in {\mathcal C}_n$ be the target concept, $0 < \epsilon, \delta \leq 1$ . Then there is a constant $a > 0$ such that if $A$ is given as input a random sample $S$ of $m$ examples drawn from oracle $EX(c,{\mathcal D})$ , where $m$ satisfies $m \geq a \left( \frac{1}{\epsilon} \log \frac{1}{\delta} + \left(\frac{\left( n \cdot \text{size}(c) \right)^\alpha}{\epsilon}\right)^\frac{1}{1-\beta}\right)$ , then $A$ runs in time polynomial in $n$ , $\text{size}(c)$ , $1/\epsilon$ and $\frac{1}{\delta}$ and, with probability at least $1 - \delta$ , the output $h$ of $A$ satisfies $error(h) \leq \epsilon$ .

This is a technically dense presentation, but it’s a philosophically beautiful result. Let’s unpick it a bit, so its essence is not obscured by notation. In summary, simple rules that are consistent with prior observations have predictive power! The ‘simple’ part here comes from $(\alpha,\beta)$ , and the predictive power comes from the bound on $\text{error}(h)$ . Of course, one needs sufficient observations (the complex lower bound on $m$ ) for this to hold. Notice that as $\beta$ approaches 1, and so – by the definition of an Occam algorithm – we get close to being able to memorise our entire training set – we need an arbitrarily large training set (memorisation doesn’t generalise).

Vapnik-Chervonenkis (VC) Dimension

Definition (Behaviours). The set of behaviours on $S = \{x_1, \ldots, x_m\}$ that are realised by ${\mathcal C}$ , is defined by $\Pi_{\mathcal C}(S) = \left\{ \left(c(x_1), \ldots, c(x_m)\right) | c \in {\mathcal C} \right\}$ .

Each of the points in $S$ is either included in a given concept or not. Each tuple $\left(c(x_1), \ldots, c(x_m)\right)$ then forms a kind of fingerprint of $X$ according to a particular concept. The set of behaviours is the set of all such fingerprints across the whole concept class..

Definition (Shattered). A set $S$ is shattered by ${\mathcal C}$ iff $\Pi_{\mathcal C}(S) = \{0,1\}^{|S|}$ .

Note that $\{0,1\}^{|S|}$ is the maximum cardinality that’s possible, i.e. the set of behaviours is all possible behaviours. So we can think of a set as being shattered by a concept class iff there’s no combination of inclusion/exclusion in the concepts that isn’t represented at least once in the set.

Definition (Vapnik-Chervonenkis Dimension). The VC dimension of ${\mathcal C}$ , denoted $VCD({\mathcal C})$ , is the cardinality of the largest set shattered by ${\mathcal C}$ . If arbitrarily large finite sets can be shattered by ${\mathcal C}$ , then $VDC({\mathcal C}) = \infty$ .

VC dimension in this sense captures the ability of ${\mathcal C}$ to discern between samples.

Theorem (PAC-learning in Low VC Dimension). Let ${\mathcal C}$ be any concept class. Let ${\mathcal H}$ be any representation class off of VC dimension $d$ . Let $A$ be any algorithm taking a set of $m$ labelled examples of a concept $c \in {\mathcal C}$ and producing a concept in ${\mathcal H}$ that is consistent with the examples. Then there exists a constant $c_0$ such that $A$ is a PAC learning algorithm for ${\mathcal C}$ using ${\mathcal H}$ when it is given examples from $EX(c,{\mathcal D})$ , and when $m \geq c_0 \left( \frac{1}{\epsilon} \log \frac{1}{\delta} + \frac{d}{\epsilon} \log \frac{1}{\epsilon} \right)$ .

Let’s take a look at the similarity between this theorem and Occam’s razor, presented in the last section of this blog post. Both bounds have a similar feel, but the VCD-based bound does not depend on $\text{size}(c)$ ; indeed it’s possible that the size of hypotheses is infinite and yet the VCD is still finite.

As the theorem below shows, the linear dependence on VCD achieved in the above theorem is actually the best one can do.

Theorem (PAC-learning Minimum Samples). Any algorithm for PAC-learning a concept class of VC dimension $d$ must use $\Omega(d/\epsilon)$ examples in the worst case.

Definition (Layered DAG). A layered DAG is a DAG in which each vertex is associated with a layer $\ell \in {\mathbb N}$ and in which the edges are always from some layer $\ell$ to the next layer $\ell+1$ . Vertices at layer 0 have indegree 0 and are referred to as input nodes. Vertices at other layers are referred to as internal nodes. There is a single output node of outdegree 0.

Definition ( $G$ -composition). For a layered DAG $G$ and a concept class ${\mathcal C}$ , the G-composition of ${\mathcal C}$ is the class of all concepts that can be obtained by: (i) associating a concept $c_i \in {\mathcal C}$ with each vertex $N_i$ in $G$ , (ii) applying the concept at each node to its predecessor nodes.

Notice that this way we can think of the internal nodes as forming a Boolean circuit with a single output; the $G$ -composition is the concept class we obtain by restricting concepts to only those computable with the structure $G$ . This is a very natural way of composing concepts – so what kind of VCD arises through this composition? This theorem provides an answer:

Theorem (VCD Compositional Bound). Let $G$ be a layered DAG with $n$ input nodes and $s \geq 2$ internal nodes, each of indegree $r$ . Let ${\mathcal C}$ be a concept class over ${\mathbb R}^r$ of VC dimension $d$ , and let ${\mathcal C}_G$ be the $G$ -composition of ${\mathcal C}$ . Then $VCD({\mathcal C}_G) \leq 2ds \log(es)$ .

Weak PAC Learnability

Definition (Weak PAC Learning). Let ${\mathcal C}$ be a concept class and let $A$ be an algorithm that is given access to $EX(c,{\mathcal D})$ for target concept $c \in {\mathcal C}_n$ and distribution ${\mathcal D}$ . $A$ is a weak PAC learning algorithm for ${\mathcal C}$ using ${\mathcal H}$ if there exist polynomials $p(\cdot,\cdot)$ and $q(\cdot,\cdot)$ such that $A$ outputs a hypothesis $h \in {\mathcal H}$ that with probability at least $1/q(n,\text{size}(c))$ satisfies $\text{error}(h) \leq 1/2 - 1/p(n,\text{size}(c))$ .

Kearns and Vazirani justifiably describe weak PAC learning as “the weakest demand we could place on an algorithm in the PAC setting without trivialising the problem”: if these were exponential rather than polynomial functions in $n$ , the problem is trivial: take a fixed-size random sample of the concept and memorise it, randomly guess with probability 50% outside the memorised sample. The remarkable result is that efficient weak PAC learnability and efficient PAC learnability coincide for an appropriate PAC hypothesis class, based on ternary majority trees.

Definition (Ternary Majority Tree). A ternary majority tree with leaves from ${\mathcal H}$ is a tree where each non-leaf node computes a majority (voting) function of its three children, and each leaf is labelled with a hypothesis from ${\mathcal H}$ .

Theorem (Weak PAC learnability is PAC learnability). Let ${\mathcal C}$ be any concept class and ${\mathcal H}$ any hypothesis class. Then if ${\mathcal C}$ is efficiently weakly PAC learnable using ${\mathcal H}$ , it follows that ${\mathcal C}$ is efficiently PAC learnable using a hypothesis class of ternary majority trees with leaves from ${\mathcal H}$ .

Kearns and Varzirani provide an algorithm to learn this way. The details are described in their book, but the basic principle is based on “boosting”, as developed in the lemma to follow.

Definition (Filtered Distributions). Given a distribution ${\mathcal D}$ and a hypothesis $h_1$ we define ${\mathcal D_2}$ to be the distribution obtained by flipping a fair coin and, on a heads, drawing from $EX(c,{\mathcal D})$ until $h_1$ agrees with the label; on a tails, drawing from $EX(c,{\mathcal D})$ until $h_1$ disagrees with the label. Invoking a weak learning algorithm on data from this new distribution yields a new hypothesis $h_2$ . Similarly, we define ${\mathcal D_3}$ to be the distribution obtained by drawing examples from $EX(c,{\mathcal D})$ until we find an example on which $h_1$ and $h_2$ disagree.

What’s going on in these constructions is quite clever: $h_2$ has been constructed so that it must contain new information about $c$ , compared to $h_1$ ; $h_1$ has, by construction, no advantage over a coin flip on ${\mathcal D}_2$ . Similarly, $h_3$ contains new information about $c$ not already contained in $h_1$ and $h_2$ , namely on the points where they disagree. Thus, one would expect that hypotheses that work in these three cases could be combined to give us a better overall hypothesis. This is indeed the case, as the following lemma shows.

Lemma (Boosting). Let $g(\beta) = 3 \beta^2 - 2 \beta^3$ . Let the distributions ${\mathcal D}$ , ${\mathcal D}_2$ , ${\mathcal D}_3$ be defined above, and let $h_1$ , $h_2$ and $h_3$ satisfy $\text{error}_{\mathcal D}(h_1) \leq \beta$ , $\text{error}_{{\mathcal D}_2}(h_2) \leq \beta$ , $\text{error}_{{\mathcal D}_3}(h_3) \leq \beta$ . Then if $h = \text{majority}(h_1, h_2, h_3)$ , it follows that $\text{error}_{\mathcal D}(h) \leq g(\beta)$ .

The function $g$ is monotone and strictly decreasing over $[0,1/2)$ . Hence by combining three hypotheses with only marginally better accuracy than flipping a coin, the boosting lemma tells us that we can obtain a strictly stronger hypothesis. The algorithm for (strong) PAC learnability therefore involves recursively calling this boosting procedure, leading to the majority tree – based hypothesis class. Of course, one needs to show that the depth of the recursion is not too large and that we can sample from the filtered distributions with not too many calls to the overall oracle $EX(c,{\mathcal D})$ , so that the polynomial complexity bound in the PAC definition is maintained. Kearns and Vazirani include these two results in the book.

Learning from Noisy Data

Up until this point, we have only dealt with correctly classified training data. The introduction of a noisy oracle allows us to move beyond this limitation.

Definition (Noisy Oracle). A noisy oracle $\hat{EX}^\eta( c, {\mathcal D})$ extends the earlier idea of an oracle with an additional noise parameter $0 \leq \eta < 1/2$ . This oracle behaves in the identical way to $EX$ except that it returns the wrong classification with probability $\eta$ .

Definition (PAC Learnable from Noisy Data). Let ${\mathcal C}$ be a concept class and let ${\mathcal H}$ be a representation class over $X$ . Then ${\mathcal C}$ is PAC learnable from noisy data using ${\mathcal H}$ if there exists and algorithm such that: for any concept $c \in {\mathcal C}$ , any distribution ${\mathcal D}$ on $X$ , any $0 \leq \eta < 1/2$ , and any $0 < \epsilon < 1$ , $0 < \delta < 1$ and $\eta_0$ with $\eta \leq \eta_0 < 1/2$ , given access to a noisy oracle $\hat{EX}^\eta( c, {\mathcal D})$ and inputs $\epsilon$ , $\delta$ , $\eta_0$ , with probability at least $1 - \delta$ the algorithm outputs a hypothesis concept $h \in {\mathcal H}$ with $\text{error}(h) \leq \epsilon$ . If the runtime of the algorithm is polynomial in $n$ , $1/\epsilon$ , $1/\delta$ and $1/(1 - 2\eta_0)$ then ${\mathcal C}$ is efficiently learnable from noisy data using ${\mathcal H}$ .

Let’s unpick this definition a bit. The main difference from the PAC definition is simply the addition of noise via the oracle and an additional parameter $\eta_0$ which bounds the error of the oracle; thus the algorithm is allowed to know in advance an upper bound on the noisiness of the data, and an efficient algorithm is allowed to take more time on more noisy data.

Kearns and Vazirani address PAC learnability from noisy data in an indirect way, via the use of a slightly different framework, introduced below.

Definition (Statistical Oracle). A statistical oracle $STAT(c, {\mathcal D})$ takes queries of the form $(\chi, \tau)$ where $\chi : X \times \{0,1\} \to \{0,1\}$ and $0 < \tau \leq 1$ , and returns a value $\hat{P}_\chi$ satisfying $P_\chi - \tau \leq \hat{P}_\chi \leq P_\chi + \tau$ where $P_\chi = Pr_{x \in {\mathcal D}}[ \chi(x, c(x)) = 1 ]$ .

Definition (Learnable from Statistical Queries). Let ${\mathcal C}$ be a concept class and let ${\mathcal H}$ be a representation class over $X$ . Then ${\mathcal C}$ is efficiently learnable from statistical learning queries using ${\mathcal H}$ if there exists a learning algorithm $A$ and polynomials $p(\cdot, \cdot, \cdot)$ , $q(\cdot, \cdot, \cdot)$ and $r(\cdot,\cdot,\cdot)$ such that: for any $c \in {\mathcal C}$ , any distribution ${\mathcal D}$ over $X$ and any $0 < \epsilon < 1/2$ , if given access to $STAT(c,{\mathcal D})$ , the following hold. (i) For every query $(\chi,\tau)$ made by $A$ , the predicate $\chi$ can be evaluated in time $q(1/\epsilon, n, \text{size}(c))$ , and $\tau \leq r(1/\epsilon, n, \text{size}(c))$ , (ii) $A$ has execution time bounded by $p(1/\epsilon, n, \text{size}(c))$ , (iii) $A$ outputs a hypothesis $h \in {\mathcal H}$ that satisfies $\text{error}(h) \leq \epsilon$ .

So a statistical oracle can be asked about a whole predicate $\chi$ , for any given tolerance $\tau$ . The oracle must return an estimate of the probability that this predicate holds (where the probability is over the distribution over $X$ ). It is, perhaps, not entirely obvious how to relate this back to the more obvious noisy oracle used above. However, it is worth noting that one can construct a statistical oracle that works with high probability by taking enough samples from a standard oracle, and then returning the relative frequency of $\chi$ evaluating to 1 on that sample. Kearns and Vazirani provide an intricate construction to efficiently sample from a noisy oracle to produce a statistical oracle with high probability. In essence, this then allows an algorithm that can learn from statistical queries to be used to learn from noisy data, resulting in the following theorem.

Theorem (Learnable from Statistical Queries means Learnable from Noisy Data). Let ${\mathcal C}$ be a concept class and let ${\mathcal H}$ be a representation class over $X$ . Then if ${\mathcal C}$ is efficiently learnable from statistical queries using ${\mathcal H}$ , ${\mathcal C}$ is also efficiently PAC learnable using ${\mathcal H}$ in the presence of classification noise.

Hardness Results

I mentioned earlier in this post that Pitt and Valiant showed that sometimes we want more general hypothesis classes than concept classes: the concept class 3-DNF using the hypothesis class 3-DNF is intractable, yet learning the same concept class with the more general hypothesis class 3-CNF is efficiently PAC learnable. So in their chapter Inherent Unpredictability, Kearns and Vazirani turn their attention to the case where a concept class is hard to learn independent of the choice of a hypothesis class. This leads to some quite profound results for those of us interested in Boolean circuits.

We will need some kind of hardness assumption to develop hardness results for learning. In particular, note that if $P = NP$ , then by Occam’s Razor (above) polynomially evaluable hypothesis classes are also polynomially-learnable ones. So we will need to do two things: focus our attention on polynomially evaluable hypothesis classes (or we can’t hope to learn them polynomially), and make a suitable hardness assumption. The latter requires a very brief detour into some results commonly associated with cryptography.

Let ${\mathbb Z}_N^* = \{ i \; | \; 0 < i < N \; \wedge \text{gcd}(i, N) = 1 \}$ . We define the cubing function $f_N : {\mathbb Z}_N^* \to {\mathbb Z}_N^*$ by $f_N(x) = x^3 \text{ mod } N$ . Let $\varphi$ define Euler’s totient function. Then if $\varphi$ is not a multiple of three, it turns out that $f_N$ is bijective, so we can talk of a unique discrete cube root.

Definition (Discrete Cube Root Problem). Let $p$ and $q$ be two $n$ -bit primes with $\varphi(N)$ not a multiple of 3, where $N = pq$ . Given $N$ and $f_N(x)$ as input, output $x$ .

Definition (Discrete Cube Root Assumption). For every polynomial $P$ , there is no algorithm that runs in time $P(n)$ that solves the discrete cube root problem with probability at least $1/P(n)$ , where the probability is taken over randomisation of $p$ , $q$ , $x$ and any internal randomisation of the algorithm $A$ . (Where $N = pq$ ).

This Discrete Cube Root Assumption is widely known and studied, and forms the basis of the learning complexity results presented by Kearns and Vazirani.

Theorem (Concepts Computed by Small, Shallow Boolean Circuits are Hard to Learn). Under the Discrete Cube Root Assumption, the representation class of polynomial-size, log-depth Boolean circuits is not efficiently PAC learnable (using any polynomially evaluable hypothesis class).

The result also holds if one removes the log-depth requirement, but this result shows that even by restricting ourselves to only log-depth circuits, hardness remains.

In case any of my blog readers knows: please contact me directly if you’re aware of any resource of positive results on learnability of any compositionally closed non-trivial restricted classes of Boolean circuits.

The construction used to provide the result above for Boolean circuits can be generalised to neural networks:

Theorem (Concepts Computed by Neural Networks are Hard to Learn). Under the Discrete Cube Root Assumption, there is a polynomial $p$ and an infinite family of directed acyclic graphs (neural network architectures) $G = \{G_{n^2}\}_{n \geq 1}$ such that each $G_{n^2}$ has $n^2$ Boolean inputs and at most $p(n)$ nodes, the depth of $G_{n^2}$ is a constant independent of $n$ , but the representation class ${\mathcal C}_G = \cup_{n \geq 1} {\mathcal C}_{G_{n^2}}$ is not efficiently PAC learnable (using any polynomially evaluable hypothesis class), and even if the weights are restricted to be binary.

Through an appropriate natural definition of reduction in PAC learning, Kearns and Vazirani show that the PAC-learnability of all these classes reduce to functions computed by deterministic finite automata. So, in particular:

Theorem (Concepts Computed by Deterministic Finite Automata are Hard to Learn). Under the Discrete Cube Root Assumption, the representation class of Deterministic Finite Automata is not efficiently PAC learnable (using any polynomially evaluable hypothesis class).

It is this result that motivates the final chapter of the book.

Experimentation in Learning

As discussed above, PAC model utilises an oracle that returns labelled samples $(x, c(x))$ . An interesting question is whether more learning power arises if we allow the algorithms to be able to select $x$ themselves, with the oracle returning $c(x)$ , i.e. not just to be shown randomly selected examples but take charge and test their understanding of the concept.

Definition (Membership Query). A membership query oracle takes any instance $x$ and returns its classification $c(x)$ .

Definition (Equivalence Query). An equivalence query oracle takes a hypothesis concept $h \in {\mathcal C}$ and determines whether there is an instance $x$ on which $c(x) \neq h(x)$ , returning this counterexample if so.

Definition (Learnable From Membership and Equivalence Queries). The representation class ${\mathcal C}$ is efficiently exactly learnable from membership and equivalence queries if there is a polynomial $p(\cdot,\cdot)$ and an algorithm with access to membership and equivalence oracles such that for any target concept $c \in {\mathcal C}_n$ , the algorithm outputs the concept $c$ in time $p(\text{size}(c),n)$ .

There are a couple of things to note about this definition. It appears to be a much stronger requirement than PAC learning, as the concept must be exactly learnt. On the other hand, the existence of these more sophisticated oracles, especially the equivalence query oracle, appears to narrow the scope. Kearns and Vazirani encourage the reader to prove that the true strengthening over PAC-learnability is in the membership queries:

Theorem (Exact Learnability from Membership and Equivalence means PAC-learnable with only Membership). For any representation class ${\mathcal C}$ , if ${\mathcal C}$ is efficiently exactly learnable from membership and equivalence queries, then ${\mathcal C}$ is also efficiently learnable in the PAC model with membership queries.

They then provide an explicit algorithm, based on these two new oracles, to efficiently exactly learn deterministic finite automata.

Theorem (Experiments Make Deterministic Finite Automata Efficiently Learnable). The representation class of Deterministic Finite Automata is efficiently exactly learnable from membership and equivalence queries.

Note the contrast with the hardness result of the previous section: through the addition of experimentation, we have gone from infeasible learnability to efficient learnability. Another very philosophically pleasing result.

Month: July 2024

Notes on Computational Learning Theory