Bounds for Learning from Evolutionary-Related Data in the Realizable Case

1 Introduction

Modeling evolutionary aspects of species correctly is crucial for many biological problems. An important challenge is that usually only the genomes and phenotypes of today's individuals can be observed, while their ancestry and the characteristics of their ancestors are uncertain. In a number of cases, e.g. for haploid species, it is a reasonable approximation to assume that evolution follows a tree, i.e. that every individual only has one parent. Such trees representing individuals and their ancestors are called phylogenetic trees. There is a large body of work studying techniques for deriving phylogenetic trees from the genomes of the leaves [Lemey, 2009; Mossel and Roch, 2006]. Similar techniques are also used in other fields, e.g. in stemmatology to reconstruct the ancestry of historic documents.

While reconstructing phylogenetic trees has been thoroughly studied, there has been much less attention to learning theory exploiting the phylogenetic tree information. In particular, consider a set of individuals for which we know the genomes and ancestry, and assume that we know for a subset of these individuals a target value (phenotype) which depends on the genome (features). The individuals are not independent as they inherit properties from common parents, and hence we can't assume they are distributed identically and independently (iid), which makes most classic generalization bounds inapplicable. Can we construct a new generalization error bound which not only depends on the number of training examples, but also on the relationship through the phylogenetic tree with the testing examples on which we want to make a prediction? An adequate answer to this question would be of significant value in a lot of bio-medical experimental research.

Example 1. Let us consider the following hypothetical scenario. A lab O (origin) cultivates a strain of bacteria in petri Jan Ramon INRIA, France/KU Leuven, Belgium jan.ramon@inria.fr dishes and then distributes samples to labs A, B, C and D. Labs A, B, C and D then search for hypotheses about gene mutations for some phenotype (e.g. resistance to antibiotics). Now, something strange happens: the hypotheses from labs A, B and C usually work well on each others data but the hypotheses from lab D do not work on data from A, B, C and vice versa. After reconstructing the phylogenetic tree of the bacteria from all four labs, it may turn out that the bacteria which lab D received is actually an almost isolated subpopulation for which generalizing to the rest of the population is difficult (as we show rigorously in this paper). A machine learning practitioner may try to explain this phenomenon by pointing out that the training and testing data is not iid. But the data is not iid for A, B and C either, even though they are mixed, so such an explanation would not be sufficient.

We derive probabilistic bounds shedding light on phenomena such as the one described in the above example. We model the task of learning from evolutionary-related data using complete binary trees and develop techniques to bound test-set errors of classifiers trained from such trees in the realizable case, i.e. when there is a hypothesis achieving zero training error. We provide both lower bounds and upper bounds. This is important because without the lower bounds, we would not have any means to check to what extent the upper bounds make sense in situations when they are much more pessimistic compared to learning from iid data (e.g. in situations where the training and testing data come from almost separated subpopulations).

Allowing ourselves to speculate a bit, the theoretical results presented in this paper may also be relevant to problems of organism immunization. For instance, it seems to be typically the case that people vaccinated against one strain of flu may be immune also against similar strains but not necessarily to the more distant ones [Carrat and Flahault, 2007]. If we think of immunization as learning of immune system to cope with germs, the analysis described in this paper may be very relevant.

2 Preliminaries

A tree is a simple, undirected, connected, acyclic graph. When a special node is designated to turn a tree into a rooted tree, it is called the root. In such a tree, each of the nodes that is one edge further away from the root than a given node is called its child (parent can be defined correspondingly). The depth of a rooted tree is the distance from the root to the farthest leaf node. If every node in a tree has at most two children, this tree is a binary tree. Every non-root node with degree 1 is a leaf of the tree. An ordered rooted binary tree is a binary tree in which children of non-leaf nodes are distinguished, called left and right child, respectively. If T is a tree, we denote by L(T) its left subtree and by R(T) its right subtree. Similarly, L(T↪ v) and R(T↪ v) denote the left and right subtree of the subtree of T rooted in v. Unless stated otherwise, when speaking of trees, we assume that they are complete, ordered and binary, and their leaves are indexed by increasing integers (from left-most to right-most). Leaves of trees may also be labeled (not to be confused with indexing of leaves which is given by ordering of the nodes in a given tree). As long as we keep working only with complete ordered binary trees, we can represent labelings of leaves of any tree T by a sequence z = (z1↪ z2↪ ▷ ▷ ▷ ↪ zm) with m = 2d where d is depth of the tree, z1 is the label of the left-most leaf, z2 is the label of the second left-most leaf and so on. For instance, the labeling of the tree from Figure 1 is z = (A↪ B↪ B↪ A). Here, A and B are just labels whose meaning is not important at this point.

Sequences z = (z1↪ z2↪ ▷ ▷ ▷ ↪ zm) and z0 = (z01 ↪ z02 ↪ ▷ ▷ ▷ ↪ z0m) of labels of leaves of a complete binary tree are said to be isomorphic if there exists an automorphism ⇡ of the (unordered version of) the tree such that the label of any leaf in z is the same as the label of the image under ⇡ of that leaf in z0 . Informally, z and z0 are isomorphic if there exists a complete binary tree whose m leaves are labeled by z, and z0 is the leaf labeling sequence obtained by flipping the order of some subtrees in it (i.e. by swapping some left and right subtrees). For instance, the sequence z = (A↪B↪B↪A) from Figure 1 is isomorphic to z0 = (B↪A↪B↪A) but not to z00 = (B↪B↪A↪A). Aut(z1↪ z2↪ ▷ ▷ ▷ ↪ zm) is the set of all sequences (z01 ↪ z02 ↪ ▷ ▷ ▷ ↪ z0m) that are isomorphic to (z1↪ z2↪ ▷ ▷ ▷ ↪ zm). For instance, Aut(B↪B↪A↪A) = ¶(B↪B↪A↪A)↪ (A↪A↪B↪B)♦ We can further define an order on the sequences in Aut(z1↪ z2↪ ▷ ▷ ▷ ↪ zm), e.g. the lexicographical order. The smallest sequence in an Aut(z1↪ z2↪ ▷ ▷ ▷ ↪ zm) is then called the canonical representative of sequences in this set.

3 Evolutionary Tree Model

The evolutionary tree model considered in this paper is given by a class X of possible instances (e.g. genomes of individuals), a complete binary tree T , a conditional probability function p(x♣x0 ) : X ⇥ X ! [0↪ 1] and a probability function p0(x) : X ! [0↪ 1]. The joint probability of the individuals in the tree is given as P [X1 = x1 ^ · · · ^ Xk = xk] =

where k is the number of vertices in T, X1 corresponds to the root, X2i and X2i+1 are children of Xi (i.e. the probability factorizes according to a Bayesian network with structure corresponding to the tree with edges directed from root).

Intuitively, the model describes the following generative process. First, the common ancestor x1 is sampled according to the probability distribution p0(▷). Then two children x2 and x3 of this common ancestor are sampled according to the conditional probability distribution p(▷♣x1). In the next step, the children of these nodes are again sampled according to p(▷♣x2) and p(▷♣x3) and so on. Since we will mostly be working only with leaves of the trees, we will denote by P ⇤ (S) the marginal probability of the instances in the leaves of the given tree, i.e. P ⇤ (S) = P [Xm = x1 ^ · · · ^ X2m-1 = xm] where S = (x1↪ ▷ ▷ ▷ ↪ xm) 2 X m is called a sample (notice that samples only involve leaves of the tree). It holds that if S = (x1↪ ▷ ▷ ▷ ↪ xm) 2 X m and S 0 = (x01 ↪ ▷ ▷ ▷ ↪ x0m) 2 X m↪ satisfy S 0 2 Aut(S) then P ⇤ (S) = P ⇤ (S 0 ), i.e. the distribution is invariant with respect to symmetries which correspond to reorderings of a given ordered tree.

Learning in the evolutionary tree model. We assume that we are given an evolutionary tree model. The positions of training and testing examples in the tree are specified by dataset configurations. A dataset configuration is a sequence A = (a1↪ a2↪ ▷ ▷ ▷ ↪ am) where ai 2 ¶train↪ test♦. The leaves of the tree T with an index i such that ai = train are called train-set leaves and the remaining leaves are called test-set leaves.

Example 2. For instance, the dataset configuration (train, train, train, train, test, test, test, test) corresponds to training and testing examples forming two completely separated populations. Regarding Example 1 from Introduction, this could happen if lab O put half of the original sample of bacteria to one petri dish and the other half to another petri dish, continued cultivating the bacteria in the two dishes separately and then provided samples from one dish to one lab and samples from the other dish to the other lab. On the other hand, the dataset configuration (train, test, test, train, train, train, test, test) corresponds to training and testing examples being more mixed.

The set of indices of train-set leaves is denoted by Tr(A) and the set of indices of test-set leaves is denoted by Te(A). If S is a joint sample of leaves of a given tree then STr(S↪ A) = (S)Tr(A) and STe(S↪A) = (S)Te(A) are the samples of training and testing examples, respectively. In a sample, we not only get feature-vectors x (e.g. genomes), but also the corresponding labels l 2 ¶0↪ 1♦ given by an unknown concept.

Example 3. If we substitute A := train, B := test in the tree in Figure 1 then its dataset configuration is (train↪ test↪ test↪ train). It holds Tr(A) = (1↪ 4), Te(A) = (2↪ 3). If S = (w↪ x↪ y↪ z) then STr(S↪A) = (w↪ z) and STe(S↪A) = (x↪ y) are the training and testing samples, respectively.

Let H be some class of functions from X to ¶0↪ 1♦. The goal of learning is to find a hypothesis h 2 H which can do well in predicting labels of testing examples. In the realizable learning case, we also want the hypothesis h to correctly classify all training examples (such a hypothesis is called consistent hypothesis). A learning algorithm L may be seen as a function mapping training examples STr 2 (X ⇥ ¶0↪ 1♦)⇤ to hypotheses h 2 H such that for all training examples (xi↪ li) 2 STr it holds li = h(xi). If h is a hypothesis then err(S↪ h) = Pxi2S 1(h(xi) 6= li) is the error of the hypothesis h on S.

By error upper bounds in this model, we will understand inequalities of the form P[err(STe↪ L(STr)) ≥ k]  fA(k) where STr = STr(S↪A), STe = STe(S↪A) and S is jointly sampled from the given evolutionary tree model. Put simply in words, we are interested in bounding the probability that a hypothesis produced by a learning algorithm L which returns a hypothesis h 2 H consistent with the sample will disagree with the unknown concept c 2 H, which determines labels of training and testing examples, on k or more testing examples from the joint sample.

4 Upper Bounds

In this section we derive upper bounds on test-set error. The next theorem gives a bound on the probability that a fixed hypothesis h consistent with training examples will result in k or more errors on the test-set examples.

Theorem 1. Let us have an evolutionary tree model from which samples S are sampled. Let A = (a1↪ a2↪ ▷ ▷ ▷ ↪ am) be a dataset configuration, h be a fixed hypothesis and c be an unknown concept. Then the probability

is bounded by

where Ck denotes the set of all sequences e 2 ¶0↪ 1♦m with Pi ei ≥ k.

Not surprisingly, error bounds depend on given dataset configurations. The next example shows a dataset configuration for which one cannot really guarantee good generalization.

Example 4. Let us have a complete binary tree with dataset configuration (train↪ train↪ train↪ train↪ test↪ test↪ test↪ test)▷ Using Theorem 1, we obtain the same bound 12 for the probability of 1, 2, 3, and 4 errors on test-set examples. For instance, for 3 errors e maximizing the fraction in Theorem 1 is e = (0↪ 0↪ 0↪ 0↪ 1↪ 1↪ 1↪ 0) and we can check that the size of the set in the numerator is 4 and ♣Aut(e)♣ = 8 which gives the bound 12 . Intuitively, this dataset configuration is not very good for learning because, revisiting the evolutionary motivation, we have two subpopulations which evolved independently of each other but we have only training examples from one of the populations. It is not surprising that we cannot give very good guarantees for generalization when learning only from one of the sub-populations. A dataset configuration, better suited for learning and leading to much better bounds is (train↪ test↪ train↪ test↪ train↪ test↪ train↪ test)▷ In this case the bounds are 12 , 14 , 18 , and 1 16 for the probability of 1, 2, 3, and 4 errors, respectively.

The bound in Theorem 1 has two disadvantages for practical use. First, it is not expressed in terms of a very intuitive or an easy-to-compute graph parameter, and second, it does not have exponential form which is needed for obtaining analytic bounds on the expected error as done in Section 6. Therefore, next, we connect the bound from Theorem 1 with matchings in trees. A matching in an ordered tree T with dataset configuration A is a set of pairs of indices of leaves M = ¶(i1↪ j1)↪ (i2↪ j2)↪ ▷ ▷ ▷ ↪ (in↪ jn)♦ such that: (i) for every (i↪ j) 2 M, i is index of a train-set leaf and j is index of a test-set leaf, and (ii) the shortest paths connecting (i↪ j)↪ (i0 ↪ j 0 ) 2 M are disjoint if (i↪ j) 6= (i0 ↪ j 0 ).

Theorem 2. Let T be a tree, let A be its dataset-configuration and let B(A↪ k) be the upper bound from Theorem 1. Let M be a matching of a subset of train and test leaves (M is supposed to be a set of pairs of indexes). Then B(A↪ k)  2-k+♣T e(A)♣-♣M♣ ▷

Thus, matchings in trees give us simpler, albeit looser, upper bounds than the bounds from Theorem 1.

Example 5. Let us have a tree with dataset configuration A = (test↪ test↪ train↪ test↪ train↪ test↪ train↪ train) displayed in Figure 2. Then Theorem 2 gives us the upper bound 21-k on probability of getting at least k errors on test-set examples and 0 errors on train-set examples for a fixed hypothesis h.

We can use the result from Theorem 2 together with the shattering lemma (see Lemma 2.1 in [Natarajan, 1991]) and union bound to obtain the upper bound (m + 1)d · 2-k+♣Te(A)♣-♣M♣ for learning from a hypothesis class with VC dimension d [Vapnik, 1995]. We will use this bound for computing bounds for expected error in Section 6.

5 Lower Bounds

In this section, we derive a lower bound 1 corresponding to the upper bound from Theorem 1.

Theorem 3. Let A be a dataset configuration and let k  ♣Te(A)♣. Then there exists an evolutionary tree model, a hypothesis h and a concept c such that

Example 6. Let us have a dataset configuration corresponding to train and test set coming from two completely separated populations, i.e. A = (train↪ train↪ ▷ ▷ ▷ ↪ train↪ test↪ test↪ ▷ ▷ ▷ ↪ test)▷ Then the upper bound obtained using Theorem 1 is 12 for all k and the lower bound obtained using Theorem 3 is 1 22 = 14 , also for all k. So, in this case the ratio of the upper bound and the lower bound is constant. On the other hand, when we consider the case in which train and test set are perfectly mixed, such as in the case of the dataset configuration A0 = (train↪ test↪ train↪ test↪ train↪ test↪ train↪ test)↪ then one may check that the ratio of the upper bound and the lower bound grows with k.

We should note here that the lower bound presented in this section is not the tightest possible. In general, one could get tighter lower bounds for a fixed dataset configuration by viewing the tree as a Bayesian network and directly optimizing the conditional probability functions p(▷♣▷) and p0(▷). However, first, this would lead to intractable optimization problems and, second, it would not give any insight into the problem. The lower bounds provided in this section are useful especially in the cases when ♣Aut(A)♣, where A is a dataset configuration, is small, such as in cases when training and testing examples come from (almost) separated populations.

6 Bounds on Expected Error

In this section we describe a method for obtaining upper bounds on expected error. In order to compute expected error bounds, we will utilize the following theorem which considers only the special case of dataset configurations with only one test-set leaf.

Theorem 4. Let A = (test↪ train↪ train↪ ▷ ▷ ▷ ↪ train↪ train) be a dataset configuration and H be a hypothesis class with VC dimension d. Let us suppose that the learning algorithm L selects a hypothesis from H which is consistent with training examples. Then for the test-set error we have the inequality

The bounds from the previous theorem lead to a general and straightforward method for obtaining bounds on expected errors. For every test-set leaf, we can find the largest complete binary tree embedded in the original tree T with the dataset configuration A which still contains that test-set leaf and no other test-set leaves. By summing up the bounds, using linearity of expected value, for all test-set leaves in the tree, we obtain an upper bound on the expected error when learning a consistent hypothesis from a class H with VC dimension d.

1 In Appendix we actually prove a lemma with a stronger lower bound than the one in Theorem 3 but less interpretable from which Theorem 3 follows.

Example 7. Let A be a dataset configuration of size 1024 and let A consist of interleaved blocks of 4 train-set leaves and 4 test-set leaves and let H have VC dimension d = 2. Then for every test-set leaf, we can find an embedded complete binary tree consisting of 128 leaves, in which every other leaf is a train-set leaf. Therefore we can bound the expected number of errors in this tree by

which corresponds to error rate of approximately 25%.

7 RelatedWork

In this section, we discuss related works on learning theory for learning settings violating the iid assumption. An example is learning from examples which are not independent but only exchangeable. Many classical results on iid learning can be generalized to this setting [Catoni, 2004; Pestov, 2010; Shalizi and Kontorovitch, 2013]. Although superficially similar to our work because both rely on symmetries, there are important differences between the two settings. Most notably, the structure of symmetries is more complicated in our setting because the bounds in our work must somehow reflect the dependence on symmetries of the dataset configurations.

There are also works on inductive learning from various models of dependent training examples. In [De Brabanter et al., 2011], the correlations between training errors are explicitly specified. In [Usunier et al., 2005], a setting was studied in which binary classifiers are trained with data which may be dependent but deterministically generated from a sample of independent examples. In time series analysis, training examples are usually assumed to satisfy some mixing conditions, e.g. ↵-mixing or β-mixing [Guo and Shi, 2011; Ralaivola et al., 2010], which is then used to obtain generalization guarantees. In [Wang et al., 2014], dependency structure of examples is assumed to be known and represented by hypergraphs. In all these cases, while training examples are assumed to be dependent, the test-set examples are assumed to be sampled independently from them. In contrast, in our work the train-set and test-set examples are both assumed to be sampled from the evolutionary process and, thus, not independently.

The case when training and testing examples are not mutually independent of each other, like in the present paper, has also received attention in learning theory. In [Aldous and Vazirani, 1990], a model was introduced in which training and testing examples are sampled from a random walk (Markov chain). Our work may be regarded as related to these works in that the evolutionary tree model is related to branching random walks. However, one difference is that we assume that the examples come only from leaves of the tree (which is sensible from the biological motivation because living individuals correspond to the leaves) whereas in the random walk model the examples are assumed to come from all stages of the walk. Another difference which stems from this is that there is no notion of dataset configurations in the random walk model. Several results from [Kontorovich, 2012] would be relevant for our work as well, but only if we put additional assumptions on the evolutionary process beyond those used in this paper.

The work presented in this paper is also related to transductive learning [Gammerman et al., 1998; El-Yaniv and Dmitry, 2009] in that the number of test-set examples is finite and known in advance (whereas in inductive learning, the number of test-set examples is assumed to be infinite as there we are mostly interested in bounding the probability that a hypothesis with high expected error is learned). However, unlike in transductive learning we do not assume that the test-set examples are known by the time of learning.

8 Conclusions

In this paper we studied generalization bounds for learning from examples which are sampled from an evolutionary model. We provided PAC-type upper bounds based on combinatorial arguments and also upper bounds on expected errors. To complement the upper bounds we also provided a lower bound for the number of errors of a consistent hypothesis. For some dataset configurations corresponding to training and testing examples from populations which are not very mixed with each other, the lower bounds and upper bounds are relatively tight and pessimistic, confirming the intuition that guaranteeing good generalization performance should not be possible in general for such situations - without some additional assumptions on the evolutionary process. For the cases when the training and testing examples come from similar populations, the upper bounds have exponentially decaying tails which also leads to reasonable bounds for expected errors. To our best knowledge, this is the first work providing a theoretical analysis of learning where training and testing examples are evolutionary related. Extending our analysis to the agnostic case is an interesting future direction.

Acknowledgments

This work has been supported by ERC Starting Grant 240186 MiGraNT: Mining Graphs and Networks, a Theory-based approach.

A Proofs of Theorems

We will need a little additional notation. Let S = (x1↪ ▷ ▷ ▷ ↪ xm) be a joint sample of leaves of the given tree. Let c 2 H be an unknown concept according to which training and testing examples are labeled, and h 2 H be a hypothesis. Then we let e(S) = (1(c(x1) 6= h(x1))↪ ▷ ▷ ▷ ↪ 1(c(xm) 6= h(xm))) denote a sequence which contains ones in the places of examples for which h and c disagree. We call e(y) error configuration of y.

Proof of Theorem 1. We can define PE(e) = PS2X m s.t. e=e(S) P ⇤ (S) which is the probability that we sample from the evolutionary tree model a joint sample S with error configuration equal to e.

Let us denote by ConsAut(e) the set

which is the set of all error configurations isomorphic to e with errors only on the test-set leaves. Let ISO be the set of representatives for classes of isomorphic error configurations (i.e. for for every e 2 ¶0↪ 1♦m there is e0 2 ISO such that e 2 Aut(e0 )). We are interested in bounding the probability of the event ETe ≥ k ^ ETr = 0 for which we have

which is what we needed to show.

Proof of Theorem 2. First, we define an auxiliary concept called root of pair. Let (tr↪ te) 2 M and let tr = v1↪ v2↪ ▷ ▷ ▷ ↪ vr+1↪ ▷ ▷ ▷ ↪ v2r+1 = te be the unique path connecting tr and te then vr+1 is called root of the pair (tr↪ te).

Without loss of generality, we assume that A is such that for any pair of train-set and test-set leaves (tr↪ te) 2 M, if vr is the root of the pair (tr↪ te), l is the index of the leftmost leaf of L(T↪ vr) (which is the left subtree of the subtree of T rooted in vr) and r is the index of the left-most leaf of R(T↪ vr) then either tr = l, te = r or tr = r, te = l. It is not difficult to see that for any dataset-configuration A there is an isomorphic dataset-configuration satisfying this property.

Let e 2 Ck be an error configuration. We will construct a mapping ': ConsAut(e) ! 2Aut(e)∩ConsAut(e) such that for any two different e0 , e00 it will hold '(e0 )\'(e00 ) = ; and ♣'(e0 )♣ ≥ 2k-♣T e(A)♣+♣M♣ - 1.

First, we order the pairs of the matching M = ((tr1↪ te1)↪ (tr2↪ te2)↪ ▷ ▷ ▷ ↪ (tr♣M♣↪ te♣M♣)) as follows: if the unique path connecting tei and the root of the tree intersects the path connecting trj and tej then j  i. Now, let e = (e1↪ ▷ ▷ ▷ ↪ em) 2 ConsAut(e) \ Ck be an error configuration with exactly k0 errors and let Erre = ¶i 2 N♣ci = 1♦ be the set of indexes of the errors in the error configuration e. Let M 0 = ((tr01 ↪ te01 )↪ ▷ ▷ ▷ ↪ (tr0k0 ↪ te0k0 )) be a subsequence of M consisting of those pairs (tri↪ tei) 2 M where tei 2 Erre. Note that k0 ≥ k-♣Te(A)♣+♣M♣. Next, let B = ¶0↪ 1♦k0 ∩(0↪ 0↪ ▷ ▷ ▷ ↪ 0). For every b = (b1↪ ▷ ▷ ▷ ↪ bk0) 2 B we construct a new error configuration isomorphic to e as follows. We iterate j down from k0 to 1. If bj is 0, we do not do anything. If bj is 1 then we find the root vr of the pair (trj↪ tej), we take e[L(T↪ vr)] = (es↪ es+1 ▷ ▷ ▷ ↪ es+r) and e[R(T↪ vr)] = (es+r+1↪ es+r+2 ▷ ▷ ▷ ↪ es+2r) and swap them in e. where (s↪ s +1 ▷ ▷ ▷ ↪ s + r) and (s + r +1↪ s + r +2 ▷ ▷ ▷ ↪ s +2r) are the indices of the leaves of the left and right subtree rooted in the children of vr.

Now we need to show that the sets of error configurations produced by the above procedure have the desired properties. First, it is obvious that any error configuration produced in this way must be contained in Aut(e). Next, notice that there will always be at least one ei = 1 with i 2 TrT (A) (at least the one produced by the last swap) which implies that no error configuration e0 produced in this way can be in ConsAut(e). So ' maps elements from ConsAut(e) to subsets of Aut(e) ∩ ConsAut(e) as required. Now, given the matching and an error configuration e0 62 ConsAut(e) we can actually 'decode' the original configuration as well as the vector B from which the next two required properties follow: '(e0 ) \ '(e00 ) = ; for any e0 6= e00 and ♣'(e0 )♣ ≥ 2k-♣Te(A)♣+♣M♣ - 1. The decoding can be done as follows. We iterate j from 1 to ♣M♣. For any pair (trj↪ tej) we check if etrj = 1 or etej = 1. If so, we know that (trj↪ tej) 2 M 0 . If etrj = 1, we set bj = 1 and swap (es↪ es+1 ▷ ▷ ▷ ↪ es+r) and (es+r+1↪ es+r+2 ▷ ▷ ▷ ↪ es+2r) in e where (s↪ s + 1 ▷ ▷ ▷ ↪ s + r) and (s + r +1↪ s + r +2 ▷ ▷ ▷ ↪ s +2r) are the indices of the leaves of the left and right subtree of the tree rooted in the root of the pair (trj↪ tej). Otherwise we set bj = 0 and do not change e at all. It can be shown using induction on the length of B that this procedure correctly reconstructs both B and the original e.

Lemma 5. For an error (or dataset) configuration e, if L(e) is isomorphic to R(e) then ♣Aut(e)♣ = ♣Aut(L(e))♣ · ♣Aut(R(e))♣, else ♣Aut(e)♣ = 2 · ♣Aut(L(e))♣ · ♣Aut(R(e))♣.

Theorem 3 will follow directly from the next lemma.

Lemma 6. If A is a dataset configuration then there exists an evolutionary model, a hypothesis h and a concept c such that

Proof. For any fixed error configuration e, we have P[err(STr(S↪A)↪ h) = 0 ^ err(STe(S↪A)↪ h) ≥ k] ≥ Pe02Aut(e) PE(e0 ) · ♣ConsAut(e)♣ ♣Aut(e)♣ (because the factor Pe02Aut(e) PE(e0 ) is the probability of obtaining an error configuration isomorphic to e and the other factor ♣ConsAut(e)♣ ♣Aut(e)♣ is the fraction of these configurations with no errors on training examples). Since the second factor is fixed for any given error configuration, we can maximize the first factor independently of it for the fixed error configuration e, i.e. we can find the set X, functions p0(▷), p(▷♣▷) and a hypothesis h and concept c maximizing the probability of sampling an error configuration isomorphic to e.

Let X = ¶-1↪ 0↪ 1↪ 2↪ ▷ ▷ ▷ ↪ ♣A♣-1♦. Let h(x) = 0 for every x 2 X and let c(x) = 1 for x = -1 and c(x) = 0 otherwise. We prove using induction on depth d of the tree T that for any error configuration e there are functions p0(▷) and p(▷♣▷) such that: p0(x0) = 1 for some x 2 X, p(x0♣▷) = 0 and p(x♣y) is non-zero only for x's from a set Xd ✓ X of cardinality at most 2d-1 +1, and Pe02Aut(e) PE(e0 ) ≥ 1 ♣Aut(e)♣ .

(Base case, d = 1). In this case the tree consists of just the root (which is at the same time also either a train-set leaf or a test-set leaf). If e = (1) (i.e. e is the configuration ('error')) then we set p0(-1) = 1 and p0(x) = 0 for x 2 X ∩ ¶-1♦. Otherwise, if e = (0), we set p0(0) = 1 and p0(x) = 0 for x 2 X ∩ ¶0♦. Therefore we have Pe02Aut(e) PE(e0 ) = 1 ≥ 1 ♣Aut(e)♣ so the base case holds.

(Inductive step, depth of the tree T is d = n). We consider two cases according to symmetry of e. (i) If L(e) and R(e) are isomorphic then we can select the same p00 (▷), p0 (▷♣▷) and X 0 maximizing the probability P 0E (L(e)) for both the left and right subtree of the tree T. Let x00 be the only element from X 0 for which p00 (x00 ) = 1. Let us set p0(x0) = 1 for an arbitrary x0 2 X ∩ X 0 . Let us set p(x00 ♣x0) = 1 and p(x♣y) = p0 (x♣y) for all x↪ y 2 X 0 and p0(x) = 0 for the rest of x 2 X ∩ ¶x0♦. By the induction hypothesis: PE(e) = P 0E (L(e)) · P 0E (R(e)) ≥ 1 ♣Aut(L(e))♣ · 1 ♣Aut(R(e))♣ = 1 ♣Aut(e)♣ (where the last equality follows from Lemma 5). (ii) If L(e) and R(e) are not isomorphic, let pL0 (▷), pL(▷♣▷), pR0 (▷), pR(▷♣▷), XL, XR maximize P L E (L(e)) and P R E (R(e)), respectively. We can assume w.l.o.g. that there is no x 2 X ∩ ¶-1↪ 0♦ for which both pL(x♣▷) 6= 0 and pR(x♣▷) 6= 0. Let xL0 and xR0 be the only elements for which pL0 (xL0 ) = 1 and pR0 (xR0 ) = 1, respectively. Let us set p0(x0) = 1 for an arbitrary x0 2 X ∩ (XL [ XR) and p0(x) = 0 for the rest of x 2 X ∩ ¶x0♦. Let us set p(xL0 ♣x0) = 0▷5, p(xR0 ♣x0) = 0▷5 and p(x♣y) = pL(x♣y) for all x↪ y 2 XL, and p(x♣y) = pR(x♣y) for all x↪ y 2 XR. By the induction hypothesis, we get

(where the last equality follows from Lemma 5) which finishes the proof.

Lemma 7. Let A = (test↪ train↪ test↪ train↪ ▷ ▷ ▷ ↪ test↪ train) be a dataset configuration and H, d and L be as in Theorem 4. Then for the expected test-set error we have the inequality

Proof. We have

Now setting u := log2 (♣A♣ + 1)d (since the above inequalities hold for any real number u ≥ 0), we get

Proof of Theorem 4. We can 'pretend' that the dataset configuration is (test↪ train↪ test↪ train↪ ▷ ▷ ▷ ↪ test↪ train) by ignoring (♣A♣ - 1)◁2 train-set leaves (this never decreases the probability of selecting a 'bad' hypothesis from H which produces an error on the test-set leaf). Then we can use the bound on expected error from Lemma 7. It follows from the symmetry of the problem that we can obtain the bound on expected error from the statement of this theorem.