On the equivalence of Occam algorithms

It is worth pausing before the next section to explicitly list the algorithmic models we will be discussing in the remainder of this paper. We will distinguish between four models: $\delta,s$-known functional algorithms, $\delta,s$-unknown functional algorithms, $\delta$-dependent Occam algorithms, and $\delta$-independent Occam algorithms.

The $\delta,s$-unknown functional algorithm is the standard definition of a functional algorithm used by Blumer et al. and Haussler et al. [5, 10], given in Definition2. The $\delta,s$-known functional algorithm is a version used only by Board and Pitt [6]. We will need to show an equivalence between these two models, as the $\delta,s$-known functional algorithm is not one of the models contained in the equivalence class provided by Haussler et al. in Theorem 5. This result will be Lemma 6.

The $\delta$-dependent Occam algorithms and $\delta$-independent Occam algorithms, on the other hand, refer not to whether $\delta$ is an explicit input, but whether the VC dimension of the hypothesis space is polynomially dependent on $\frac{1}{\delta}$ or not. The $\delta$-independent version is used by Blumer et al. [5] while Board and Pitt [6] use a $\delta$-dependent version. The main result of our paper will be extending the analysis conducted by Board and Pitt to apply to $\delta$-independent Occam algorithms as well, resulting in Theorem 7.

Let $X$ be a stratified learning domain (i.e. we can write it as $X=\cup_{n\geq 1}X_{n}$ where each $X_{n}$ has dimension $n$). A concept is a subset of $X$; we can consider it as labelling all elements of $X$ with either a 1 or a 0, depending on whether the element is in the concept or not.

Then let $C\subseteq 2^{X}$ be a well-behaved¹¹1in a measure-theoretic sense made explicit in Blumer et al’s work [5]. class of concepts on $X$ and let the concept complexity measure $\textbf{size}:C\rightarrow\mathbb{Z^{+}}$. Let there also be associated with $C$ a set of representations for concepts in $C$ given in some representation language $\Gamma$. We assume there is a function $\sigma$ from the set of representations in $\Gamma$ onto $C$, that $\sigma$ is in $\mathbf{P}$ (or in $\mathbf{RP}$), and that given $x\in X$ and a string in $\Gamma$, we can decide in polynomial time if $x$ is in the concept represented by the string (i.e. $C$ is polynomially evaluable). Finally, we say that $C$ is stratified, i.e. $C=\cup_{n\geq 1}C_{n}$.

By $\mathcal{C}$ we denote $\left(X,C\right)$ along with their function size, $\sigma$ and $\Gamma$, so $\mathcal{C}=\left(X,C,\Gamma,\sigma,\textbf{size}\right)$. We include $\Gamma$ because learnability may in fact be a property of the representation of a set of concepts, not just the concepts themselves [6]. We use the term concept class to refer to $\mathcal{C}$ as well as to $C$. We say a concept $c$ is in $\mathcal{C}$ if $c\in C$.

We define a hypothesis class $\mathcal{H}$ where, as with $\mathcal{C}$, $\mathcal{H}=\left(X,H,\Gamma,\sigma,\textbf{size}\right)$, where $H\subseteq 2^{X}$ is also a class of concepts on $X$ but need not be related to $C$.

We use $\mathcal{P}$ to represent probability distributions on the domain $X$. A sample set taken according to $\mathcal{P}$ on $X$ is denoted $M$ and contains $m$ tuples (or points) $(x,c(x))$; we say $M$ has cardinality $m$. Denote the set of $x$-values in $M$ by the set $Z$. The error, or accuracy parameter, $\epsilon$ of a hypothesis $h$ with respect to a concept $c$ is $\epsilon=\mathcal{P}(h\triangle c)$ where $\triangle$ denotes symmetric difference. In words, $\epsilon$ is the probability due to $\mathcal{P}$ of the symmetric difference of the hypothesis and the concept.

We cannot directly measure $\epsilon$ as it is a property over the entire domain, and the concept $c$ is unknown. Therefore, it is useful to define a training error $\epsilon^{\prime}=\ell(h(Z)\triangle c(Z))$ for some loss function $\ell$. We say a hypothesis is consistent if $\epsilon^{\prime}$ is zero on a sample. Then $\delta$ is the probability that the algorithm fails to return a consistent hypothesis.

Finally, we assume that $\mathbf{RP}\neq\mathbf{NP}$; otherwise the learnability of any concept class would be trivial.

We have in Section 2.1 roughly stated the existence of a concept complexity measure, size, but we have not described any of its properties other than its domain and range. For the arguments presented in this paper we do not require any specific concept complexity measure function for size; it can be semantic (measuring breadth of explanatory power) or syntactic (e.g. the length of the description of a hypothesis in $\Gamma$), or something else entirely. We do make use of the (assumed) property that an algorithm cannot output a hypothesis with size greater than its runtime [6]. What will primarily matter, though, is how we can map from size to a combinatorial semantic complexity measure called the Vapnik-Chervonenkis (VC) Dimension [6, 5].

Definitions similar to the following can be found in papers by Blumer et al., Valiant, and others [5, 10, 12].

Functional polynomial learning algorithms receive only the sample of size $m$; it has no access to $\epsilon,\delta,$ or $s$ [10]. It can always determine $n$ from the dimension of the data points it is given [5]. However, in the oracle model, the algorithm receives at least $\epsilon$ and $\delta$ as input and has access to an oracle $EX()$ that with each call returns a point in $X$ along with a label $0$ or $1$ indicating whether or not the point is in a fixed target concept $c\in C_{n}$ with $\textbf{size}\left(c\right)\leq s$. Each oracle call takes unit time. If $A$ is probabilistic, each call to a fair coin flip also takes unit time. After some time, $A$ halts and outputs a hypothesis in $C$ [5, 10].

These models of learnability can easily be extended to situations in which we are learning $\mathcal{C}$ by $\mathcal{H}$ as opposed to just $\mathcal{C}$ by itself [5, 10]. The following theorem, due to Haussler et al. [10], shows the equivalence between the different models of polynomial learnability. The property “usually halts” refers to probabilistic oracle algorithms that use fair coin tosses to decide whether to call the oracle again or halt.

The following definition is used by Blumer et al. in their paper introducing VC-dimension-based Occam algorithms [5]. Note that this is clearly a functional algorithm, matching definition 2.

Board and Pitt [6], on the other hand, define their algorithm as follows (some notation has been altered to match the rest of this paper, but the definition itself is equivalent):

This is a functional Occam algorithm which takes $s$ and $\delta$ as explicit inputs and has a VC dimension that depends polynomially on $\frac{1}{\delta}$. Each of these factors makes it distinct from the algorithms analysed by Blumer et al. [5]. We will first show that if we have a functional algorithm dependent on $s$ and $\delta$ as explicit inputs, we can construct a functional algorithm that does not require these inputs explicitly. We will then show that we can construct a $\delta$-independent Occam algorithm from the resulting functional algorithm.

Our analysis will apply only to concept classes which are closed under exception lists.

In words, the ExList algorithm will output a concept $c_{E}$ that agrees with $c$ on all but a finite set of points in $X$, with that finite set being given by $E$. Classes that are closed under exception lists include decision lists, decision trees, arbitrary programs, Boolean circuits, Boolean formulas, and Deterministic Finite Automata (DFAs) over any fixed alphabet, among others [6]. Many of the above classes happen to be ones where finding a minimal consistent hypothesis is NP-hard, which was the original motivation for developing Occam algorithms [4].