Evolutionary Trees Can be Learned in Polynomial Time in the Two-State General Markov Model.
The j-state general Markov model of evolution (due to Steel) is a stochastic model concerned with the evolution of strings over an alphabet of size j. In particular, the two-state general Markov model of evolution generalizes the well-known Cavender--Farris--Neyman model of evolution by removing the symmetry restriction (which requires that the probability that a "0" turns into a "1" along an edge is the same as the probability that a "1" turns into a "0" along the edge). Farach and Kannan showed how to probably approximately correct (PAC)-learn Markov evolutionary trees in the Cavender--Farris--Neyman model provided that the target tree satisfies the additional restriction that all pairs of leaves have a sufficiently high probability of being the same. We show how to remove both restrictions and thereby obtain the first polynomial-time PAC-learning algorithm (in the sense of Kearns et al. [Proceedings of the  26th Annual ACM Symposium on the Theory of Computing, 1994, pp. 273--282]) for the general class of two-state Markov evolutionary trees.
Introduction
The j-State General Markov Model of Evolution was proposed by Steel in 1994 [14]. The
model is concerned with the evolution of strings (such as DNA strings) over an alphabet of
size j . The model can be described as follows. A j-State Markov Evolutionary Tree consists
of a topology (a rooted tree, with edges directed away from the root), together with the
following parameters. The root of the tree is associated with j probabilities ae
which sum to 1, and each edge of the tree is associated with a stochastic transition matrix
whose state space is the alphabet. A probabilistic experiment can be performed using the
Markov Evolutionary Tree as follows: The root is assigned a letter from the alphabet according
to the probabilities ae (Letter i is chosen with probability ae i .) Then the letter
propagates down the edges of the tree. As the letter passes through each edge, it undergoes
a probabilistic transition according to the transition matrix associated with the edge. The
result is a string of length n which is the concatenation of the letters obtained at the n leaves
of the tree. A j-State Markov Evolutionary Tree thus defines a probability distribution on
length-n strings over an alphabet of size j . (The probabilistic experiment described above
produces a single sample from the distribution. 1 )
To avoid getting bogged down in detail, we work with a binary alphabet. Thus, we will
consider Two-State Markov Evolutionary Trees.
Following Farach and Kannan [9], Erd-os, Steel, Sz'ekely and Warnow [7, 8] and Ambainis,
Desper, Farach and Kannan [2], we are interested in the problem of learning a Markov Evolutionary
Tree, given samples from its output distribution. Following Farach and Kannan and
Ambainis et al., we consider the problem of using polynomially many samples from a Markov
Evolutionary Tree M to "learn" a Markov Evolutionary Tree M 0 whose distribution is close
to that of M . We use the variation distance metric to measure the distance between two
distributions, D and D 0 , on strings of length n. The variation distance between D and D 0
is
are n-leaf Markov Evolutionary Trees, we use the
to denote the variation distance between the distribution of M and the
distribution of M 0 .
We use the "Probably Approximately Correct" (PAC) distribution learning model of
Kearns, Mansour, Ron, Rubinfeld, Schapire and Sellie [11]. Our main result is the first
polynomial-time PAC-learning algorithm for the class of Two-State Markov Evolutionary
Trees (which we will refer to as METs):
Theorem 1 Let ffi and ffl be any positive constants. If our algorithm is given poly(n; 1=ffl; 1=ffi)
samples from any MET M with any n-leaf topology T , then with probability at least
the MET M 0 constructed by the algorithm satisfies var(M;
Interesting PAC-learning algorithms for biologically important restricted classes of METs
have been given by Farach and Kannan in [9] and by Ambainis, Desper, Farach and Kannan
in [2]. These algorithms (and their relation to our algorithm) will be discussed more fully in
Section 1.1. At this point, we simply note that these algorithms only apply to METs which
satisfy the following restrictions.
Restriction 1: All transition matrices are symmetric (the probability of a '1' turning
into a '0' along an edge is the same as the probability of a `0' turning into a '1'.)
Biologists would view the n leaves as being existing species, and the internal nodes as being hypothetical
ancestral species. Under the model, a single experiment as described above would produce a single bit position
of (for example) DNA for all of the n species.
Restriction 2: For some positive constant ff, every pair of leaves (x; y) satisfies
We will explain in Section 1.1 why the restrictions significantly simplify the problem of learning
Markov Evolutionary Trees (though they certainly do not make it easy!) The main
contribution of our paper is to remove the restrictions.
While we have used variation distance (L 1 distance) to measure the distance between the
target distribution D and our hypothesis distribution D 0 , Kearns et al. formulated the problem
of learning probability distributions in terms of the Kullback-Leibler divergence distance from
the target distribution to the hypothesis distribution. This distance is defined to be the sum
over all length-n strings s of D(s) log(D(s)=D 0 (s)). Kearns et al. point out that the KL
distance gives an upper bound on variation distance, in the sense that the KL distance from
D to D 0 is \Omega\Gamma/ ar(D; D 0 Hence if a class of distributions can be PAC-learned using KL
distance, it can be PAC-learned using variation distance. We justify our use of the variation
distance metric by showing that the reverse is true. In particular, we prove the following
lemma in the Appendix.
class of probability distributions over the domain f0; 1g n that is PAC-learnable
under the variation distance metric is PAC-learnable under the KL-distance measure.
The lemma is proved using a method related to the ffl -Bayesian shift of Abe and Warmuth [3].
Note that the result requires a discrete domain of support for the target distribution, such as
the domain f0; 1g n which we use here.
The rest of this section is organised as follows: Subsection 1.1 discusses previous work
related to the General Markov Model of Evolution, and the relationship between this work
and our work. Subsection 1.2 gives a brief synopsis of our algorithm for PAC-learning Markov
Evolutionary Trees. Subsection 1.3 discusses an interesting connection between the problem
of learning Markov Evolutionary Trees and the problem of learning mixtures of Hamming
balls, which was studied by Kearns et al. [11].
1.1 Previous Work and Its Relation to Our Work
The Two-State General Markov Model [14] which we study in this paper is a generalisation of
the Cavender-Farris-Neyman Model of Evolution [5, 10, 13]. Before describing the Cavender-
Farris-Neyman Model, let us return to the Two-State General Markov Model. We will fix
attention on the particular two-state alphabet f0; 1g. Thus, the stochastic transition matrix
associated with edge e is simply the matrix
where e 0 denotes the probability that a '0' turns into a `1' along edge e and e 1 denotes the
probability that a '1' turns into a `0' along edge e. The Cavender-Farris-Neyman Model
is simply the special case of the Two-State General Markov Model in which the transition
matrices are required to be symmetric. That is, it is the special case of the Two-State General
Markov Model in which Restriction 1 (from page 1) holds (so e
We now describe past work on learning Markov Evolutionary Trees in the General Markov
Model and in the Cavender-Farris-Neyman Model. Throughout the paper, we will define the
weight w(e) of an edge e to be
Steel [14] showed that if a j-State Markov Evolutionary Tree M satisfies (i) ae i ? 0 for
all i, and (ii) the determinant of every transition matrix is outside of f\Gamma1; 0; 1g, then the
distribution of M uniquely determines its topology. In this case, he showed how to recover
the topology, given the joint distribution of every pair of leaves. In the 2-state case, it suffices
to know the exact value of the covariances of every pair of leaves. In this case, he defined the
weight  (e) of an edge e from node v to node w to be
w(e)
w is a leaf, and
w(e)
r
(1)
Steel observed that these distances are multiplicative along a path and that the distance between
two leaves is equal to their covariance. Since the distances are multiplicative along a
path, their logarithms are additive. Therefore, methods for constructing trees from additive
distances such as the method of Bandelt and Dress [4] can be used to reconstruct the topology.
Steel's method does not show how to recover the parameters of a Markov Evolutionary Tree,
even when the exact distribution is known and 2. In particular, the quantity that he
obtains for each edge e is a one-dimensional distance rather than a two-dimensional vector
giving the two transition probabilities e 0 and e 1 . Our method shows how to recover the
parameters exactly, given the exact distribution, and how to recover the parameters approximately
(well enough to approximate the distribution), given polynomially-many samples from
M .
Farach and Kannan [9] and Ambainis, Desper, Farach and Kannan [2] worked primarily
in the special case of the Two-State General Markov Model satisfying the two restrictions
on Page 1. Farach and Kannan's paper was a breakthrough, because prior to their paper
nothing was known about the feasibility of reconstructing Markov Evolutionary Trees from
samples. For any given positive constant ff, they showed how to PAC-learn the class of
METs which satisfy the two restrictions. However, the number of samples required is a
function of 1=ff, which is taken to be a constant. Ambainis et al. improved the bounds
given by Farach and Kannan to achieve asymptotically tight upper and lower bounds on the
number of samples needed to achieve a given variation distance. These results are elegant
and important. Nevertheless, the restrictions that they place on the model do significantly
simplify the problem of learning Markov Evolutionary Trees. In order to explain why this is
true, we explain the approach of Farach et al.: Their algorithm uses samples from a MET
M , which satisfies the restrictions above, to estimate the "distance" between any two leaves.
(The distance is related to the covariance between the leaves.) The authors then relate the
distance between two leaves to the amount of evolutionary time that elapses between them.
The distances are thus turned into times. Then the algorithm of [1] is used to approximate the
evolutionary times with times which are close, but form an additive metric, which
can be fitted onto a tree. Finally, the times are turned back into transition probabilities.
The symmetry assumption is essential to this approach because it is symmetry that relates a
one-dimensional quantity (evolutionary time) to an otherwise two-dimensional quantity (the
probability of going from a '0' to a `1' and the probability of going from a '1' to a `0'). The
second restriction is also essential: If the probability that x differs from y were allowed to
approach 1=2, then the evolutionary time from x to y would tend to 1. This would mean
that in order to approximate the inter-leaf times accurately, the algorithm would have to get
the distance estimates very accurately, which would require many samples. Ambainis et al. [2]
generalised their results to a symmetric version of the j-state evolutionary model, subject to
the two restrictions above.
Erd-os, Steel, Sz'ekely and Warnow [7, 8] also considered the reconstruction of Markov
Evolutionary Trees from samples. Like Steel [14] and unlike our paper or the papers of
Farach et al. [9, 2], Erd-os et al. were only interested in reconstructing the topology of a MET
(rather than its parameters or distribution), and they were interested in using as few samples
as possible to reconstruct the topology. They showed how to reconstruct topologies in the
j-state General Markov Model when the Markov Evolutionary Trees satisfy (i) Every root
probability is bounded above 0, (ii) every transition probability is bounded above 0 and
below 1=2, and (iii) for positive quantities - and - 0 , the determinant of the transition matrix
along each edge is between - and . The number of samples required is polynomial
in the worst case, but is only polylogarithmic in certain cases including the case in which
the MET is drawn uniformly at random from one of several (specified) natural distributions.
Note that restriction (iii) of Erd-os et al. is weaker than Farach and Kannan's Restriction 2
(from Page 1). However, Erd-os et al. only show how to reconstruct the topology (thus they
work in a restricted case in which the topology can be uniquely constructed using samples).
They do not show how to reconstruct the parameters of the Markov Evolutionary Tree, or
how to approximate its distribution.
1.2 A Synopsis of our Method
In this paper, we describe the first polynomial-time PAC-learning algorithm for the class of
Two-State Markov Evolutionary Trees (METs). Our algorithm works as follows: First, using
samples from the target MET, the algorithm estimates all of the pairwise covariances between
leaves of the MET. Second, using the covariances, the leaves of the MET are partitioned into
"related sets" of leaves. Essentially, leaves in different related sets have such small covariances
between them that it is not always possible to use polynomially many samples to discover
how the related sets are connected in the target topology. Nevertheless, we show that we can
closely approximate the distribution of the target MET by approximating the distribution
of each related set closely, and then joining the related sets by "cut edges". The first step,
for each related set, is to discover an approximation to the correct topology. Since we do
not restrict the class of METs which we consider, we cannot guarantee to construct the
exact induced topology (in the target MET). Nevertheless we guarantee to construct a good
enough approximation. The topology is constructed by looking at triples of leaves. We show
how to ensure that each triple that we consider has large inter-leaf covariances. We derive
quadratic equations which allow us to approximately recover the parameters of the triple,
using estimates of inter-leaf covariances and estimates of probabilities of particular outputs.
We compare the outcomes for different triples and use the comparisons to construct the
topology. Once we have the topology, we again use our quadratic equations to discover the
parameters of the tree. As we show in Section 2.4, we are able to prevent the error in our
estimates from accumulating, so we are able to guarantee that each estimated parameter is
within a small additive error of the "real" parameter in a (normalised) target MET. From
this, we can show that the variation distance between our hypothesis and the target is small.
1.3 Markov Evolutionary Trees and Mixtures of Hamming Balls
A Hamming ball distribution [11] over binary strings of length n is defined by a center (a string
c of length n) and a corruption probability p. To generate an output from the distribution, one
starts with the center, and then flips each bit (or not) according to an independent Bernoulli
experiment with probability p. A linear mixture of j Hamming balls is a distribution defined
by j Hamming ball distributions, together with j probabilities ae which sum to 1 and
determine from which Hamming ball distribution a particular sample should be taken. For
any fixed j , Kearns et al. give a polynomial-time PAC-learning algorithm for a mixture of j
Hamming balls, provided all j Hamming balls have the same corruption probability 2 .
A pure distribution over binary strings of length n is defined by n probabilities,
To generate an output from the distribution, the i'th bit is set to `0' independently with
probability - i , and to '1' otherwise. A pure distribution is a natural generalisation of a
Hamming ball distribution. Clearly, every linear mixture of j pure distributions can be
realized by a j-state MET with a star-shaped topology. Thus, the algorithm given in this
paper shows how to learn a linear mixture of any two pure distributions. Furthermore, a
generalisation of our result to a j-ary alphabet would show how to learn any linear mixture
of any j pure distributions.
2 The Algorithm
Our description of our PAC-learning algorithm and its analysis require the following defini-
tions. For positive constants ffi and ffl , the input to the algorithm consists of poly(n; 1=ffl; 1=ffi)
samples from a MET M with an n-leaf topology T . We will let ffl
We have made no effort to
optimise these constants. However, we state them explicitly so that the reader can verify
below that the constants can be defined consistently. We define an ffl 4 -contraction of a MET
with topology T 0 to be a tree formed from T 0 by contracting some internal edges e for which
is the edge-distance of e as defined by Steel [14] (see equation 1).
If x and y are leaves of the topology T then we use the notation cov(x; y) to denote the
covariance of the indicator variables for the events "the bit at x is 1" and "the bit at y is 1".
Thus,
We will use the following observations.
Observation 3 If MET M 0 has topology T 0 and e is an internal edge of T 0 from the root r to
node v and T 00 is a topology that is the same as T 0 except that v is the root (so e goes from v to
r) then we can construct a MET with topology T 00 which has the same distribution as M 0 . To
do this, we simply set appropriately (from the distribution of M 0 ). If
we set e 0 to be (from the distribution of M 0 ). If 1 we set e 1 to be
(from the distribution of M 0 ). Otherwise, we set e
Observation 4 If MET M 0 has topology T 0 and v is a degree-2 node in T 0 with edge e leading
into v and edge f leading out of v and T 00 is a topology which is the same as T 0 except that e
2 The kind of PAC-learning that we consider in this paper is generation. Kearns et al. also show how to do
evaluation for the special case of the mixture of j Hamming balls described above. Using the observation that
the output distributions of the subtrees below a node of a MET are independent, provided the bit at that node
is fixed, we can also solve the evaluation problem for METs. In particular, we can calculate (in polynomial
time) the probability that a given string is output by the hypothesis MET.
and f have been contracted to form edge g then there is a MET with topology T 00 which has
the same distribution as M 0 . To construct it, we simply set
Observation 5 If MET M 0 has topology T 0 then there is a MET M 00 with topology T 0 which
has the same distribution on its leaves as M 0 and has every internal edge e satisfy e 0 +e 1 - 1.
Proof of Observation 5: We will say that an edge e is "good" if e 0 Starting
from the root we can make all edges along a path to a leaf good, except perhaps the last edge
in the path. If edge e from u to v is the first non-good edge in the path we simply set e 0
to This makes the edge good but it has the side effect
of interchanging the meaning of "0" and "1" at node v. As long as we interchange "0" and
"1" an even number of times along every path we will preserve the distribution at the leaves.
Thus, we can make all edges good except possibly the last one, which we use to get the parity
of the number of interchanges correct. 2
We will now describe the algorithm. In subsection 2.6, we will prove that with probability
at least 1 \Gamma ffi , the MET M 0 that it constructs satisfies var(M; M 0 ) - ffl . Thus, we will prove
Theorem 1.
Estimate the covariances of pairs of leaves
For each pair (x; y) of leaves, obtain an "observed" covariance d
cov(x; y) such that, with
probability at least 1 \Gamma ffi=3, all observed covariances satisfy
d
Lemma 6 Step 1 requires only poly(n; 1=ffl; 1=ffi) samples from M .
Proof: Consider leaves x and y and let p denote Pr(xy = 11). By a Chernoff bound
(see [12]), after k samples the observed proportion of outputs with
of p, with probability at least
For each pair (x; y) of leaves, we estimate
From these estimates, we can calculate
d
cov(x; y) within \Sigmaffl 3 using Equation 2. 2
2.2 Step 2: Partition the leaves of M into related sets
Consider the following leaf connectivity graph whose nodes are the leaves of M . Nodes x and
y are connected by a "positive" edge if d
are connected by a "negative"
edge if d cov(x; y) - \Gamma(3=4)ffl 2 . Each connected component in this graph (ignoring the signs of
edges) forms a set of "related" leaves. For each set S of related leaves, let s(S) denote the
leaf in S with smallest index. METs have the property that for leaves x, y and z , cov(y; z) is
positive iff cov(x; y) and cov(y; z) have the same sign. (To see this, use the following equation,
which can be proved by algebraic manipulation from Equation 2.)
where v is taken to be the least common ancestor of x and y and ff 0 and ff 1 are the transition
probabilities along the path from v to x and fi 0 and fi 1 are the transition probabilities along
the path from v to y. Therefore, as long as the observed covariances are as accurate as stated
in Step 1, the signs on the edges of the leaf connectivity graph partition the leaves of S into
two sets S 1 and S 2 in such a way that s(S) 2 S 1 , all covariances between pairs of leaves in
are positive, all covariances between pairs of leaves in S 2 are positive, and all covariances
between a leaf in S 1 and a leaf in S 2 are negative.
For each set S of related leaves, let T (S) denote the subtree formed from T by deleting all
leaves which are not in S , contracting all degree-2 nodes, and then rooting at the neighbour
of s(S). Let M(S) be a MET with topology T (S) which has the same distribution as M on
its leaves and satisfies the following.
ffl Every internal edge e of M(S) has e 0
ffl Every edge e to a node in S 1 has e 0
ffl Every edge e to a node in S 2 has e 0
Observations 3, 4 and 5 guarantee that M(S) exists.
Observation 7 As long as the observed covariances are as accurate as stated in Step 1 (which
happens with probability at least 1 \Gamma ffi=3), then for any related set S and any leaf x 2 S there
is a leaf y 2 S such that jcov(x; y)j - ffl 2 =2.
Observation 8 As long as the observed covariances are as accurate as stated in Step 1 (which
happens with probability at least 1 \Gamma ffi=3), then for any related set S and any edge e of T (S)
there are leaves a and b which are connected through e and have jcov(a; b)j - ffl 2 =2.
Observation 9 As long as the observed covariances are as accurate as stated in Step 1 (which
happens with probability at least 1 \Gamma ffi=3), then for any related set S , every internal node v
of M(S) has
Proof of Observation 9: Suppose to the contrary that v is an internal node of M(S)
with Using Observation 3, we can re-root M(S) at v
without changing the distribution. Let w be a child of v. By equation 3, every pair of leaves
a and b which are connected through (v; w) satisfy jcov(a; b)j -
The observation now follows from Observation 8. 2
As long as the observed covariances are as accurate as stated in Step 1
(which happens with probability at least 1 \Gamma ffi=3), then for any related set S , every edge e of
M(S) has w(e) - ffl 2 =2.
Proof of Observation 10: This follows from Observation 8 using Equation 3. (Recall
that
2.3 Step 3: For each related set S , find an ffl 4 -contraction T 0 (S) of T (S).
In this section, we will assume that the observed covariances are as accurate as stated in Step 1
(this happens with probability at least 1 \Gamma ffi=3). Let S be a related set. With probability
at least 1 \Gamma ffi=(3n) we will find an ffl 4 -contraction T 0 (S) of T (S). Since there are at most n
related sets, all ffl 4 -contractions will be constructed with probability at least 1 \Gamma ffi=3. Recall
that an ffl 4 -contraction of M(S) is a tree formed from T (S) by contracting some internal
edges e for which  (e) We start with the following observation, which will allow us
to redirect edges for convenience.
Observation 11 If e is an internal edge of T (S) then  (e) remains unchanged if e is redirected
as in Observation 3.
Proof: The observation can be proved by algebraic manipulation from Equation 1 and
Observation 3. Note (from Observation that every endpoint v of e satisfies
(0; 1). Thus, the redirection in Observation 3 is not degenerate and  (e) is defined. 2
We now describe the algorithm for constructing an ffl 4 -contraction T 0 (S) of T (S). We
will build up T 0 (S) inductively, adding leaves from S one by one. That is, when we have
an ffl 4 -contraction T 0 (S 0 ) of a subset S 0 of S , we will consider a leaf x build
an ffl 4 -contraction T 0 ;. The precise order in which
the leaves are added does not matter, but we will not add a new leaf x unless S 0 contains
a leaf y such that jd cov(x; y)j - (3=4)ffl 2 . When we add a new leaf x we will proceed as
follows. First, we will consider T use
the method in the following section (Section 2.3.1) to estimate  (e 0 ). More specifically, we
will let u and v be nodes which are adjacent in T (S 0 ) and have in the
show how to estimate  (e). Afterwards (in Section 2.3.2), we
will show how to insert x.
2.3.1 Estimating  (e)
In this section, we suppose that we have a MET M(S 0 ) on a set S 0 of leaves, all of which
form a single related set. T (S 0 ) is the topology of M(S 0 ) and T 0 (S 0 ) is an ffl 4 -contraction of
is an edge of T 0 (S 0 is the edge of T (S 0 ) for which
We wish to estimate  (e) within \Sigmaffl 4 =16. We will ensure that the overall
probability that the estimates are not in this range is at most ffi=(6n).
The proof of the following equations is straightforward. We will typically apply them in
situations in which z is the error of an approximation.
y
y
Case 1: e 0 is an internal edge
We first estimate e 0 , e 1 , of the correct values.
By Observation 9, are in [ffl 2 our estimate of
is within a factor of (1 \Sigma 2ffl 5 of the correct value. Similarly, our
estimates of are within a factor of (1 \Sigma ffl 4 2 \Gamma9 ) of the
correct values. Now using Equation 1 we can estimate  (e) within \Sigmaffl 4 =16. In particular,
our estimate of  (e) is at most
s
s
In the inequalities, we used Equation 6 and the fact that  (e) - 1. Similarly, by Equation 7,
our estimate of  (e) is at least
s
s
We now show how to estimate e 0 , e 1 , We say
that a path from node ff to node fi in a MET is strong if jcov(ff; fi)j - ffl 2 =2. It follows from
Equation 3 that if node fl is on this path then
We say that a quartet (c; b j a; d) of leaves a, b, c and d is a good estimator of the edge
is an edge of T (S 0 ) and the following hold in T (S 0 ) (see Figure 1).
1. a is a descendent of v.
2. The undirected path from c to a is strong and passes through u then v.
3. The path from u to its descendent b is strong and only intersects the (undirected) path
from c to a at node u.
4. The path from v to its descendent d is strong and only intersects the path from v to a
at node v.
We say that d) is an apparently good estimator of e 0 if the following hold in the
1. a is a descendent of v 0 .
2. The undirected path from c to a is strong and passes through u 0 then v 0 .
3. The path from u 0 to its descendent b is strong and only intersects the (undirected) path
from c to a at node u 0 .
4. The path from v 0 to its descendent d is strong and only intersects the path from v 0 to
a at node v 0 .
e
a
c
a
d

Figure

1: Finding
Observation 12 If e is an edge of T (S 0 ) and (c; b j a; d) is a good estimator of e then any
leaves
Proof: The observation follows from Equation 8 and 9 and from the definition of a good
estimator. 2
d) is a good estimator of e then it can be used (along with poly(n; 1=ffl; 1=ffi)
samples from M(S 0 )) to estimate e 0 , e 1 , use
sufficiently many samples, then the probability that any of the estimates is not within \Sigmaffl 5 of
the correct value is at most ffi=(12n 7 )).
Proof: Let q 0 and q 1 denote the transition probabilities from v to a (see Figure 1) and let
the transition probabilities from u to a. We will first show how to estimate
loss of generality (by Observation 3) we can
assume that c is a descendant of u. (Otherwise we can re-root T (S 0 ) at u without changing
the distribution on the nodes or p 0 or p 1 .) Let fi be the path from u to b and let fl be the
path from u to c. We now define
(These do not quite correspond to the conditional covariances of b and c, but they are related
to these.) We also define
cov(b; c)
The following equations can be proved by algebraic manipulation from Equation 10, Equation
2 and the definitions of F and D.
Case 1a: a 2 S 1
In this case, by Equation 4 and by Observation 10, we have
Equation 13, we have
Equations 12 and 14 imply
Also, since
From these equations, it is clear that we could find p 0 ,
exactly. We now show that with polynomially-many
samples, we can approximate the values of
sufficiently accurately so that using our approximations and the above equations, we obtain
approximations for which are within \Sigmaffl 6 . As in the proof of Lemma 6,
we can use Equations 2 and 10 to estimate
within \Sigmaffl 0 for any ffl 0 whose inverse is at most a polynomial in n and 1=ffl. Note that our
estimate of cov(b; c) will be non-zero by Observation 12 (as long as ffl 0 - (ffl 2 =2) 3 ), so we
will be able to use it to estimate F from its definition. Now, using the definition of F and
Equation 5, our estimate of 2F is at most
By Observation 12, this is at most
The error is at most ffl 00 for any ffl 00 whose is inverse is at most polynomial in n and 1=ffl. (This
is accomplished by making ffl 0 small enough with respect to ffl 2 according to equation 18.) We
can similarly bound the amount that we underestimate F . Now we use the definition of D
to estimate D. Our estimate is at most
Using Equation 5, this is at most
cov(b; c)
Once again, by Observation 12, the error can be made within \Sigmaffl 000 for any ffl 000 whose is
inverse is polynomial in n and 1=ffl (by making ffl 0 and ffl 00 sufficiently small). It follows that
our estimate of
D is at most
us an upper
bound on the value of D as a function of ffl 2 ), we can estimate
D within \Sigmaffl 0000 for any
ffl 0000 whose inverse is polynomial in n and 1=ffl. This implies that we can estimate p 0 and p 1
within \Sigmaffl 6 . Observation 12 and Equation 3 imply that w(p) - (ffl 2 =2) 3 . Thus, the estimate
for
D is non-zero. This implies that we can similarly estimate using
Equation 17.
Now that we have estimates for which are within \Sigmaffl 6 of the correct
values, we can repeat the trick to find estimates for q 0 and q 1 which are also within \Sigmaffl 6 . We
use leaf d for this. Observation 4 implies that
Using these equations, our estimate of e 0 is at most
Equation 5 and our observation above that w(p) - (ffl 2 =2) 3 imply that the error is at most
which is at most 2 7 ffl 6 =ffl 3
. Similarly, the estimate for e 0 is at least e and the
estimate for e 1 is within \Sigmaffl 5 of e 1 . We have now estimated e 0 , e 1 , and
As we explained in the beginning of this section, we can use these estimates to estimate
Case 1b: a 2 S 2
In this case, by Equation 4 and by Observation 10, we have
equation 13, we have
Equations 12 and 19 imply
Equation 17 remains unchanged. The process of estimating (from the
new equations) is the same as for Case 1a. This concludes the proof of Lemma 13. 2
Observation 14 Suppose that e 0 is an edge from u 0 to v 0 in T 0 (S 0 ) and that
is the edge in T (S 0 ) such that u 2 u 0 and v 2 v 0 . There is a good estimator (c; b j a; d)
of e. Furthermore, every good estimator of e is an apparently good estimator of e 0 . (Refer to

Figure

2.)
ae-
oe-
ae-
a
c
d

Figure

2: d) is a good estimator of and an apparently good estimator of
&%
c
&%
a ?
d

Figure

3: d) is an apparently good estimator of e good estimator of
Proof: Leaves c and a can be found to satisfy the first two criteria in the definition of
a good estimator by Observation 8. Leaf b can be found to satisfy the third criterion by
Observation 8 and Equation 8 and by the fact that the degree of u is at least 3 (see the
text just before Equation 4). Similarly, leaf d can be found to satisfy the fourth criterion.
d) is an apparently good estimator of e 0 because only internal edges of T (S 0 ) can be
contracted in the ffl 4 -contraction T 0 (S
Observation 15 Suppose that e 0 is an edge from u 0 to v 0 in T 0 (S 0 ) and that
an edge in T (S 0 ) such that u 2 u 0 and v 2 v 0 . Suppose that (c; b j a; d) is an apparently good
estimator of e 0 . Let u 00 be the meeting point of c, b and a in T (S 0 ). Let v 00 be the meeting
point of c, a and d in T (S 0 ). (Refer to Figure 3.) Then (c; b j a; d) is a good estimator of
the path p from u 00 to v 00 in T (S 0 ). Also,  (p) -  (e).
Proof: The fact that (c; b j a; d) is a good estimator of p follows from the definition of
good estimator. The fact that  (p) -  (e) follows from the fact that the distances   are
multiplicative along a path, and bounded above by 1. 2
Observations 14 and 15 imply that in order to estimate  (e) within \Sigmaffl 4 =16, we need
only estimate  (e) using each apparently good estimator of e 0 and then take the maximum.
By Lemma 13, the failure probability for any given estimator is at most ffi=(12n 7 ), so with
probability at least 1 \Gamma ffi=(12n 3 ), all estimators give estimates within \Sigmaffl 4 =16 of the correct
values. Since there are at most 2n edges e 0 in T 0 (S 0 ), and we add a new leaf x to S 0 at
most n times, all estimates are within \Sigmaffl 4 =16 with probability at least 1 \Gamma ffi=(6n).
Case 2: e 0 is not an internal edge
In this case is a leaf of T (S 0 ). We say that a pair of leaves (b; c) is a
good estimator of e if the following holds in T (S 0 The paths from leaves v, b and c meet
at u and jcov(v; b)j, jcov(v; c)j and jcov(b; c)j are all at least (ffl 2 =2) 2 . We say that (b; c) is an
apparently good estimator of e 0 if the following holds in T 0 (S 0 The paths from leaves v, b
and c meet at u 0 and jcov(v; b)j, jcov(v; c)j and jcov(b; c)j are all at least (ffl 2 =2) 2 . As in the
previous case, the result follows from the following observations.
Observation c) is a good estimator of e then it can be used (along with poly(n; 1=ffl; 1=ffi)
samples from M(S 0 )) to estimate e 0 , e 1 , and (The probability that
any of the estimates is not within \Sigmaffl 5 of the correct value is at most ffi=(12n 3 ).)
Proof: This follows from the proof of Lemma 13. 2
Observation 17 Suppose that e 0 is an edge from u 0 to leaf v in T 0 (S 0 ) and that
an edge in T (S 0 ) such that u 2 u 0 . There is a good estimator (b; c) of e. Furthermore, every
good estimator of e is an apparently good estimator of e 0 .
Proof: This follows from the proof of Observation 14 and from Equation 9. 2
Observation Suppose that e 0 is an edge from u 0 to leaf v in T 0 (S 0 ) and that
an edge in T (S 0 ) such that u 2 u 0 . Suppose that (b; c) is an apparently good estimator of e 0 .
Let u 00 be the meeting point of b, v and c in T (S 0 ). Then (b; c) is a good estimator of the
path p from u 00 to v in T (S 0 ). Also,  (p) -  (e).
Proof: This follows from the proof of Observation 15. 2
2.3.2 Using the Estimates of  (e).
We now return to the problem of showing how to add a new leaf x to T 0 (S 0 ). As we indicated
above, for every internal edge e use the method in Section 2.3.1 to
estimate  (e) where is the edge of T (S 0 ) such that u 2 u 0 and v 2 v 0 . If the
observed value of  (e) exceeds then we will contract e. The accuracy of our
estimates will guarantee that we will not contract e if  and that we definitely
contract e if  We will then add the new leaf x to T 0 (S 0 ) as follows. We will
insert a new edge We will do this by either (1) identifying x 0 with a node
already in T 0 (S 0 ), or (2) splicing x 0 into the middle of some edge of T 0 (S 0 ).
We will now show how to decide where to attach x 0 in T 0 (S 0 ). We start with the following
definitions. Let S 00 be the subset of S 0 such that for every y 2 S 00 we have jcov(x; y)j - (ffl 2 =2) 4 .
Let T 00 be the subtree of T 0 (S 0 ) induced by the leaves in S 00 . Let S 000 be the subset of S 0 such
that for every y 2 S 000 we have jd cov(x; y)j - (ffl 2 000 be the subtree of T 0 (S 0 )
induced by the leaves in S 000 .
Observation 19 If T (S 0 [ fxg) has x 0 attached to an edge is the
edge corresponding to e in T 0 (S 0 ) (that is, e
an edge of T 00 .
Proof: By Observation 14 there is a good estimator (c; b j a; d) for e. Since x is being
added to S 0 (using Equation 8), jcov(x; x 0 )j - ffl 2 =2. Thus, by Observation 12 and Equation 9,
every leaf y 2 fa; b; c; dg has jcov(x; y)j - (ffl 2 =2) 4 . Thus, a, b, c and d are all in S 00 so e 0 is
in T 00 . 2
attached to an edge
are both contained in node u 0 of T 0 (S 0 ) then u 0 is a node of T 00 .
Proof: Since u is an internal node of T (S 0 ), it has degree at least 3. By Observation 8
and Equation 8, there are three leaves a 1 , a 2 and a 3 meeting at u with jcov(u; a i )j - ffl 2 =2.
Similarly, jcov(u; v)j - ffl 2 =2. Thus, for each a i , jcov(x; a i )j - (ffl 2 =2) 3 so a 1 , a 2 , and a 3 are
in S 00 . 2
Observation
Proof: This follows from the accuracy of the covariance estimates in Step 1. 2
We will use the following algorithm to decide where to attach x 0 in T 000 . In the algorithm,
we will use the following tool. For any triple (a; b; c) of leaves in S 0 [ fxg, let u denote the
meeting point of the paths from leaves a, b and c in T (S 0 [fxg). Let M u be the MET which
has the same distribution as M(S 0 [ fxg), but is rooted at u. (M u exists, by Observation 3.)
Let   c (a; b; c) denote the weight of the path from u to c in M u . By observation 11,   c (a; b; c)
is equal to the weight of the path from u to c in M(S 0 [fxg). (This follows from the fact that
re-rooting at u only redirects internal edges.) It follows from the definition of   (Equation 1)
and from Equation 3 that
c (a; b; c) =
s
cov(a; c)cov(b; c)
If a, b and c are in S 000 [fxg, then by the accuracy of the covariance estimates and Equations 8
and 9, the absolute value of the pairwise covariance of any pair of them is at least ffl 8
As
in Section 2.3.1, we can estimate cov(a; c), cov(b; c) and cov(a; b) within a factor of (1 \Sigma ffl 0 )
of the correct values for any ffl 0 whose inverse is at most a polynomial in n, and 1=ffl. Thus,
we can estimate   c (a; b; c) within a factor of (1 \Sigma ffl 4 =16) of the correct value. We will take
sufficiently many samples to ensure that the probability that any of the estimates is outside
of the required range is at most ffi=(6n 2 ). Thus, the probability that any estimate is outside
of the range for any x is at most ffi=(6n).
We will now determine where in T 000 to attach x 0 . Choose an arbitrary internal root u 0
of T 000 . We will first see where x 0 should be placed with respect to u 0 . For each neighbour v 0
of u 0 in T 000 , each pair of leaves (a 1 ; a 2 ) on the "u each leaf b on the "v
side of perform the following two tests.

Figure

4: The setting for is an internal
node of T 000 . (If v 0 is a leaf, we perform the same tests with
a
x
f u
a 2

Figure

5: Either
The test succeeds if the observed value of   x (a
is at least 1
The test succeeds if the observed value of   b (a 1 ; a
is at most 1 \Gamma 3ffl 4 =4.
We now make the following observations.
Observation 22 If x is on the "u side" of (u; v) in T (S 000 [ fxg) and u is in u 0 in T 000 and
v is in v 0 6= u 0 in T 000 then some test fails.
Proof: Since u 0 is an internal node of T 000 , it has degree at least 3. Thus, we can construct
a test such as the one depicted in Figure 5. (If x the figure is still correct, that
would just mean that  (f Similarly, if v 0 is a leaf, we simply have  (f 0
is the edge from v to b.) Now we have(f )
However, only succeed if the left hand fraction is at least 1
Furthermore, only succeed if the right hand fraction is at most
our estimates are accurate to within a factor of (1 \Sigma ffl 4 =16), at least one of
the two tests will fail. 2
Observation 23 If x is between u and v in T (S 000 [ fxg) and the edge f from u to x 0 has
succeed for all choices
of a 1 , a 2 and b.
@
x

Figure

succeed for all choices of a 1 , a 2 and
b.
a 1
@
@
@
f
x
a 1
@
@
@
f
x

Figure

7: succeed for all choices of a 1 , a 2 and
b.
Proof: Every such test has the form depicted in Figure 6, where again g might be degen-
erate, in which case  (g) = 1. Observe that   x (a its estimate is at
least succeeds. Furthermore,
so the estimate is at most 1 \Gamma 3ffl 4 =4 and Test2 succeeds. 2
Observation 24 If x is on the "v side" of (u; v) in T (S 000 [fxg) and
from the beginning of Section 2.3.2 that  (e) is at most 1 \Gamma 7ffl 4 =8 if u and v are in different
nodes of T 000 ), then succeed for all choices of
a 1 , a 2 and b.
Proof: Note that this case only applies if v is an internal node of T (S 000 ). Thus, every
such test has one of the forms depicted in Figure 7, where some edges may be degenerate.
Observe that in both cases   x (a its estimate is at least 1
and Test1 succeeds. Also in both cases
so the estimate is at most 1 \Gamma 3ffl 4 =4 and Test2 succeeds. 2
Now note (using Observation 22) that node u 0 has at most one neighbour v 0 for which all
tests succeed. Furthermore, if there is no such imply that x 0 can
be merged with u 0 . The only case that we have not dealt with is the case in which there is
exactly one v 0 for which all tests succeed. In this case, if v 0 is a leaf, we insert x 0 in the middle
of edge Otherwise, we will either insert x 0 in the middle of edge or we will
insert it in the subtree rooted at v 0 . In order to decide which, we perform similar tests from
node v 0 , and we check whether Test1(v succeed
for all choices of a 1 , a 2 , and b. If so, we put x 0 in the middle of edge Otherwise, we
recursively place x 0 in the subtree rooted at v 0 .
2.4 Step 4: For each related set S , construct a MET M 0 (S) which is close
to M(S)
For each set S of related leaves we will construct a MET M 0 (S) with leaf-set S such that
each edge parameter of M 0 (S) is within \Sigmaffl 1 of the corresponding parameter of M(S). The
topology of M 0 (S) will be T 0 (S). We will assume without loss of generality that T (S) has
the same root as T 0 (S). The failure probability for S will be at most ffi=(3n), so the overall
failure will be at most ffi=3.
We start by observing that the problem is easy if S has only one or two leaves.
Observation then we can construct a MET M 0 (S) such that each edge parameter
of M 0 (S) is within \Sigmaffl 1 of the corresponding parameter of M(S).
We now consider the case in which S has at least three leaves. Any edge of T (S) which
is contracted in T 0 (S) can be regarded as having e 0 and e 1 set to 0. The fact that these are
within \Sigmaffl 1 of their true values follows from the following lemma.
Lemma 26 If e is an internal edge of M(S) from v to w with
Proof: First observe from Observation 9 that 1g and from Observation 10
that Using algebraic manipulation, one can see that
Thus, by Equation 1,
which proves the
observation. 2
Thus, we need only show how to label the remaining parameters within \Sigmaffl 1 . Note that
we have already shown how to do this in Section 2.3.1. Here the total failure probability is
at most ffi=(3n) because there is a failure probability of at most ffi=(6n 2 ) associated with each
of the 2n edges.
2.5 Step 5: Form M 0 from the METs M 0 (S)
Make a new root r for M 0 and set 1. For each related set S of leaves, let u
denote the root of M 0 (S), and let p denote the probability that u is 0 in the distribution
of M 0 (S). Make an edge e from r to u with e
2.6 Proof of Theorem 1
Let M 00 be a MET which is formed from M as follows.
ffl Related sets are formed as in Step 2.
ffl For each related set S , a copy M 00 (S) of M(S) is made.
ffl The METs M 00 (S) are combined as in Step 5.
Theorem 1 follows from the following lemmas.
Lemma 27 Suppose that for every set S of related leaves, every parameter of M 0 (S) is within
1 of the corresponding parameter in M(S). Then var(M
Proof: First, we observe (using a crude estimate) that there are at most 5n 2 parameters
in M 0 . (Each of the (at most n) METs M 0 (S) has one root parameter and at most 4n edge
parameters.) We will now show that changing a single parameter of a MET by at most \Sigmaffl 1
yields at MET whose variation distance from the original is at most 2ffl 1 . This implies that
ffl=2. Suppose that e is an edge from u to v and e 0 is changed. The
probability that the output has string s on the leaves below v and string s 0 on the remaining
leaves is
Thus, the variation distance between M 00 and a MET obtained by changing the value of e 0
(within is at most
s
s
s
Similarly, if ae 1 is the root parameter of a MET then the probability of having output s is
So the variation distance between the original MET and one in which ae 1 is changed within
1 is at most X
s
Before we prove Lemma 28, we provide some background material. Recall that the weight
w(e) of an edge e of a MET is define the weight w(') of a leaf ' to be the
product of the weights of the edges on the path from the root to '. We will use the following
lemma.
Lemma 29 In any MET with root r, the variation distance between the distribution on the
leaves conditioned on and the distribution on the leaves conditioned on 0 is at mostP
w('), where the sum is over all leaves '.
Proof: We proceed by induction on the number of edges in the MET. In the base case
there are no edges so r is a leaf, and the result holds. For the inductive step, let e be an edge
from r to node x. For any string s 1 on the leaves below x and any string s 2 on the other
leaves,
Algebraic manipulation of this formula shows that Pr(s 1 s
It follows that the variation distance is at most the sum over all s 1 s 2 of the absolute value of
the quantity in Equation 23, which is at most
The result follows by induction. 2
Lemma that m is a MET with n leaves and that e is an edge from node u to
node v. Let m 0 be the MET derived from m by replacing e 0 with
z is the maximum over all pairs (x; y) of leaves
which are connected via e in m of jcov(x; y)j.
Proof: By Observation 3, we can assume without loss of generality that u is the root
of m. For any string s 1 on the leaves below v and any string s 2 on the remaining leaves, we
find (via a little algebraic manipulation) that the difference between the probability that m
outputs s 1 s 2 and the probability that m 0 does is
Thus, the variation distance between m and m 0 is times the
product of the variation distance between the distribution on the leaves below v conditioned
on and the distribution on the leaves below v conditioned on and the variation
distance between the distribution on the remaining leaves conditioned on and the
distribution on the remaining leaves conditioned on this is at most
below v
other '
which by Equation 3 isX
connected via e
which is at most 4(n=2) 2
Lemma 31 If, for two different related sets, S and S 0 , an edge e from u to v is in M(S)
and in M 0 (S), then e
Proof: By the definition of the leaf connectivity graph in Step 2, there are leaves a; a 0 2 S
and b; b 0 2 S 0 such that the path from a 0 to a and the path from b 0 to b both go through
jd cov(a; a
and the remaining covariance estimates amongst leaves a, a 0 , b and b 0 are less than (3=4)ffl 2 .
Without loss of generality (using Observation 3), assume that u is the root of the MET. Let
denote the path from u to a 0 and use similar notation for the other leaves. By Equation 3
and the accuracy of the estimates in Step 1,
Thus,
By Equation 1,
The result now follows from the proof of Lemma 26. (Clearly, the bound in the statement of
Lemma 31 is weaker than we can prove, but it is all that we will need.) 2
Proof of Lemma 28: Let M   be the MET which is the same as M except that every edge e
which is contained in M(S) and M(S 0 ) for two different related sets S and S 0 is contracted.
Similarly, let M 00  be the MET which is the same as M 00 except that every such edge has
all of its copies contracted in M 00  . Clearly, var(M; M 00
is the number
of edges in M that are contracted. We now wish to bound var(M
M   (S) and M   (S 0 ) do not intersect in an edge (for any related sets S and S 0 ). Now suppose
that M   (S) and M   (S 0 ) both contain node u. We can modify M   without changing the
distribution in a way that avoids this overlap. To do this, we just replace node u with two
copies of u, and we connect the two copies by an edge e with e Note that this
change will not affect the operation of the algorithm. Thus, without loss of generality, we can
assume that for any related sets S and S 0 , M   (S) and M   (S 0 ) do not intersect. Thus, M
and M 00  are identical, except on edges which go between the sub-METs M   (S). Now, any
edge e going between two sub-METs has the property that for any pair of leaves, x and y
connected via e, jcov(x; y)j - ffl 2 . (This follows from the accuracy of our covariance estimates
in Step 1.) Thus, by Lemma 30, changing such an edge according to Step 5 adds at most n 2 ffl 2
to the variation distance. Thus, var(M  is the number of edges that
are modified according to Step 5. We conclude that var(M; M 00

Acknowledgements

We thank Mike Paterson for useful ideas and discussions.



--R

On the Approximability of Numerical Taxonomy
Nearly Tight Bounds on the Learnability of Evolution
Polynomial Learnability of Probabilistic Concepts with Respect to the Kullback-Leibler Divergence
Reconstructing the shape of a tree from observed dissimilarity data

Elements of Information Theory
A few logs suffice to build (almost) all trees (I)
"Inferring big trees from short quartets"
Efficient algorithms for inverting evolution
A probability model for inferring evolutionary trees
On the Learnability of Discrete Distributions
On the method of bounded differences
Molecular studies of evolution: a source of novel statistical problems.
Recovering a tree from the leaf colourations it generates under a Markov model
--TR

--CTR
Elchanan Mossel, Distorted Metrics on Trees and Phylogenetic Forests, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.4 n.1, p.108-116, January 2007
Elchanan Mossel , Sbastien Roch, Learning nonsingular phylogenies and hidden Markov models, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA
learning of distributions;evolutionary trees;PAC-learning;markov model;computational learning theory