Decision tree approximations of Boolean functions.
Decision trees are popular representations of Boolean functions. We show that, given an alternative representation of a Boolean function f, say as a read-once branching program, one can find a decision tree T which approximates f to any desired amount of accuracy. Moreover, the size of the decision tree is at most that of the smallest decision tree which can represent f and this construction can be obtained in quasi-polynomial time. We also extend this result to the case where one has access only to a source of random evaluations of the Boolean function f instead of a complete representation. In this case, we show that a similar approximation can be obtained with any specified amount of confidence (as opposed to the absolute certainty of the former case.) This latter result implies proper PAC-learnability of decision trees under the uniform distribution without using membership queries.
Introduction
Decision trees are popular representations of Boolean func-
tions. They form the basic inference engine in well-known
machine learning programs such as C4.5 [Q86, Q96]. Boolean
decision trees have also been used in the problem of performing
reliable computations in the presence of faulty components
[KK94] and in medical diagnosis. The popularity
of decision trees for representing Boolean functions may be
attributed to the following reasons:
Universality: Decision trees can represent all Boolean
functions.
Amenability to manipulation: Many useful operations
on Boolean functions can be performed efficiently in
time polynomial in the size of the decision tree rep-
resentation. In contrast, most such operations are intractable
under other popular representations. Table 1
gives a comparison of decision trees with DNF formulas
and read-once branching programs.
Supported by NSF grant 9820840.
The advantages of a decision tree representation motivate
the following problem:
Given an arbitrary representation of a Boolean function
f , find an equivalent representation of f as a decision tree
of as small a size as can be.
It is immediately evident that this problem is bound to be
hard as stated. Polynomial time solvability of this problem
would imply that satisfiability of CNF formulas can be decided
in polynomial time which is impossible unless P=NP.
We therefore consider a slightly different problem. Let us
say that g is an -approximation of f if the fraction of assignments
on which g and f differ in evaluation is at most
.
Given an arbitrary representation of a Boolean function
f , find an -approximation of f as a decision tree of as small
a size as can be.
In order not to fall into the same trap as before, we are
now interested in solving this problem efficiently but realis-
tically: that is, we may use time polynomial in the following
parameters:
1. The size of the given representation of f .
2. The size of the smallest decision tree representation of
f for a given .
3. The inverse of the desired error tolerance, i.e., 1=.
Such approximations would be useful in all applications
where a small amount of error can be tolerated in return for
the gains that would accrue from having a decision tree rep-
resentation. Indeed this is the case for most applications in
machine learning and data mining. For example, one could
post-process the hypothesis output of a learning program and
convert it into a decision tree while ensuring that not much
error has been introduced by choosing a suitably small .
Note here that one may use knowledge of special properties
of the representation scheme of the hypothesis in constructing
the decision tree approximation. Further note that one
may even construct a decision tree approximation for a decision
tree hypothesis! This would be useful in conjunction
with programs like C4.5 which output decision trees but do
not make special efforts to ensure that the output tree is provably
the smallest it can be for a desired error tolerance. At the
expense of sacrificing a little more error, one could achieve
the desired minimization in such cases.
Table

1: The complexity of operations in different representation schemes
Read-Once Branching Decision Trees
Programs
Universality
AND of 2 representations Polynomial time a Polynomial time a Polynomial time a
of 2 representations Polynomial time a Polynomial time a Polynomial time a
Complement of a representation Exponential time a Polynomial time a Polynomial time a
Deciding satisfiability Polynomial time a Polynomial time a Polynomial time a
Deciding unsatisfiability NP complete b Polynomial time a Polynomial time a
Deciding monotonicity co-NP complete b Open Polynomial time c
Deciding equivalence co-NP complete b co-RP d Polynomial time e
Deciding symmetry co-NP complete b Polynomial time c Polynomial time c
Deciding relevance co-NP complete b Open Polynomial time e
of variables
Counting number of #P-complete f Polynomial time c Polynomial time c
satisfying assignments
Making representation NP hard b co-RP d Polynomial time e
irredundant
Making representation NP hard b Open NP-hard g
minimum
Truth-table NP hard h Open Polynomial time i
minimization
a Straightforward from the definition of the representation scheme.
Easy reduction from CNF-SATISFIABILITY.
c Proved in this paper.
d Is a result (or follows from one) in [BCW80].
e It is a folk theorem proves that decision trees are testable for equivalence in polynomial time; the other
results follow from this.
f Proved in [S75].
Proved in [ZB98].
h A result of Masek cited in Garey and Johnson's book [GJ79].
Proved in [GLR99].
We first show that in the case of some well-known representation
schemes, small -approximating decision trees can
be obtained in quasi-polynomial time. polynomial factor
of the first parameter listed above is multiplied by a factor
which involves an exponent logarithmic in the second and
third parameters.) These schemes are:
1. Decision trees
2. Ordered Binary Decision Diagrams
3. Read-once Branching Programs
4. O(log n)-height Branching Programs
5. Sat-j DNF formulas, for constant j
6. -Boolean formulas
The third item above is a generalization of the first two, so
the result for the first two follows from the third. Our quasi-polynomial
time algorithm actually holds with more generality
than for just these classes. Roughly speaking, all representation
schemes for which the number of satisfying assignments
of the input function under "small" projections can
be computed efficiently-a property we call sat-countable
in this paper-would come under the technique employed
here. Indeed, we present the algorithm in this more general
way and then argue that the required properties hold for all
the above schemes. It is worth emphasizing here that although
the time taken by our algorithm is quasi-polynomial,
the size of the decision tree approximation is not: in fact, the
output decision tree has the smallest size that any decision
tree of its height and level of approximation can have. In this
sense, it is optimal and certainly has size no larger than that
of the smallest decision tree which can represent the boolean
function being approximated.
We also consider the situation where only some evaluations
of a Boolean function f are available. Given a sample S
of such evaluations, we show that the previous algorithm can
be modified slightly to give a quasi-polynomial time algorithm
which produces a small -approximating decision tree
over the sample S. That is, the decision tree may disagree
with f in evaluating at most   jSj assignments out of S, for
any given .
We argue that this latter result implies proper quasi-polynomial
time PAC-learnability of decision trees under the uniform
distribution. Informally, the learning result may be interpreted
8as follows. Compared to the absolute certainty of
the -approximation in the first result, the learning result says
that if we are given access only to a source of random evaluations
of f (instead of a complete representation of f ) then
the output of our algorithm will be an -approximating decision
tree with as much confidence as desired, but not absolute
certainty. This may be the only way to obtain decision tree
approximations for representation schemes like DNF formulas
for which counting the number of satisfying assignments
is #P-complete [GJ79].
A novel feature of the learning algorithm is that it is not
an Occam algorithm [BEHW87] unlike the ones known in
learning theory. This is because our algorithm may actually
make a few errors even on the training sample used. Consequently
the analysis of the sample complexity is a generalization
of the ones normally used, and may be of some
independent interest.
The learning result can be compared with similar ones
in learning theory. Bshouty's monotone theory based algorithm
[B95] can be deployed to learn decision trees under
any arbitrary but fixed distribution in polynomial time but
has the following drawbacks in comparison with our algo-
rithm: the algorithm uses membership queries and outputs
not a decision tree but a depth-3 formula. Similarly, Bshouty
and Mansour's algorithm [BM95] does not output a decision
tree. Ehrenfeucht and Haussler [EH89] show that decision
trees of rank r are learnable in time n O(r) under any distribu-
tion. The rank of a decision tree T is the height of the largest
complete binary tree that can be embedded in T . Since a decision
tree of m nodes has rank at most log m, at first glance,
this result would seem to be an improvement over the learning
result of this paper since one could learn m node decision
trees in quasi-polynomial time under any distribution! The
difference is this: in learning m node decision trees over n
variables our algorithm would always produces a decision
tree of size no larger than m using a sample of size at most
polynomial in m and the inverse of the error and confidence
parameters. In contrast, the algorithm of Ehrenfeucht and
Haussler may output a tree of size n O(log m) using a sample
of size quasi-polynomial in n; m and polynomial in the
inverse of the error and confidence parameters.
The rest of the paper is organized as follows. Section 2
contains definitions and lemmas used in the remaining sec-
tions. Section 3 has our algorithm for finding an -approx-
imating decision tree given a sat-countable representation.
Section 4 contains the results on -approximating decision
trees given only a source of random evaluations of a Boolean
function. We conclude with some open problems in Section
5.
Preliminaries
Let f be a Boolean function over a set
of n variables. A (total) assignment is obtained by setting
each of the n variables to either 0 or 1; such an assignment
may be represented by an n-bit vector in f0; 1g n in the natural
way. A satisfying assignment  for f is one for which
1. The number of satisfying assignments for f is
denoted by ]f .
A partial assignment is obtained when only a subset of
variables in V is assigned values. A partial assignment may
be represented by a vector of length n each of whose elements
is either 0, 1, or *. A vector element is * if the corresponding
variable was not assigned a value. Thus, the total
number of partial assignments is 3 n and the number of partial
assignments with k variables assigned values is n
The size of a partial vector , denoted jj, is the number
of elements in  assigned 0 or 1. The empty partial vector,
denoted , is the one in which all variables are assigned *.
The projection of f under a partial assignment , denoted
f , is the function obtained by "hardwiring" the values
of the variables included in . More precisely, given a
total assignment  and a partial assignment , let  denote
the total assignment obtained by setting each variable whose
value is not * in  to the value in  and each variable whose
value is * in  to the value in . Then, f is defined by
We are interested only in projection-closed representation
classes of Boolean functions, i.e., ones for which given
a representation for a Boolean function f and any partial vector
, the Boolean function f can also be represented in the
class and, moreover, such a representation can be computed
in polynomial time. We say that a projection-closed representation
class is (polynomial-time) sat-countable if given a
representation for f , the value of ]f can be computed in time
polynomial in the size of the representation and n, the total
number of variables. If d is a representation of the function
f , we use jdj to denote the size of d. Where the context assures
that there is no ambiguity, we treat a representation as
synonymous with the Boolean function being represented.
The error err(f; f 0 ) of f with respect to another Boolean
function f 0 defined over the same set of n variables is
the total number of assignments  such that f() 6= f 0 ();
moreover f is an -approximation of f 0 if
We consider the following projection-closed representation
classes of Boolean functions in this paper.
1. Decision Trees. A decision tree T is a binary tree where
the leaves are labeled either 0 or 1, and each internal
node is labeled with a variable. Given an assignment
evaluated by starting at the root
and iteratively applying the following rule, until a leaf is
reached: let the variable at the current node be x the
value of  at position i is 1 then branch right; otherwise
branch left. If the leaf reached is labeled 0 (resp. 1)
then 1). The size of a decision tree is
its number of nodes.
2. Branching programs (BPs). A branching program is a
directed acyclic graph with a unique node of in-degree
(called the root, and two nodes of out-degree 0 (called
leaves), one labeled 0 and the other labeled 1; each non-leaf
node of the graph contains a variable, and has out-degree
exactly two.
If every variable appears at most once on any root-leaf
path, then the branching program is called read-once
(ROBP). Note that a decision tree can effectively be
considered to be an ROBP. Assigments are evaluated
following the same rule as for decision trees. The height
of a BP is the length of the longest path from the root to
a leaf node.
An ordered binary decision diagram (OBDD) is an
ROBP with the additional property that variables appear
in the same order on any path from root to leaf.
3. SAT-j DNF formulas: DNF formulas in which every assignment
is satisfied by at most j terms of the formula.
4.  formulas: Boolean formulas in which every variable
occurs at most once.
Proposition 1 Decision trees, OBDDs, ROBPs, BPs, SAT j-
DNF formulas, and  formulas are projection-closed.
Proof. For any BP, the projection under a partial vector
can be computed as follows: redirect incoming edges for
each vertex labeled by a variable that is assigned a value in
to the left (respectively, right) child of the vertex if that
variable is assigned the value 0 (respectively, 1) in . Recursively
delete vertices with no incoming edges. By using
depth-first search, these steps can be achieved in linear time.
Note that if the BP is a decision tree, OBDD, ROBP, or a h-
height BP then the projection also belongs to the same class.
For SAT j-DNF and -formulas, the projection can be
obtained by substituting the values for each assigned variable
in . A 0 in a DNF term will result in the deletion of that
term, whereas a 1 results in the deletion of that variable from
the term. In a -formula, appropriate Boolean algebra rules
are applied to eliminate the 1's and 0's so obtained. This is
accomplished in linear time in both cases.
Proposition 2 ROBPs and O(log n)-height BPs are sat-count-
able.
Proof. The number of satisfying assignments of an ROBP
f is computed as follows.
Traverse the nodes of f in reverse topological order. Let
f(x) denote the sub-ROBP rooted at a node x consisting of
all vertices that can be reached from x and the edges joining
them. When a node x is visited the fraction  x , 0   x
1, of assignments of f(x) that are satisfying assignments is
computed as follows. If x is a leaf then  x is the same (0
or 1) as the value of the leaf node; otherwise x is an internal
node and  x is y+z, where y and z are the left and right
children of x.
A simple inductive argument shows that on completion
r , where r is the root of the ROBP, is the fraction of satisfying
assignments of f . Consequently,
n is the number of variables in f .
Next, let B be a O(log n) height BP representing a Boolean
function f . First, construct a decision tree equivalent
to f by "spreading out" B by creating a separate copy of a
node whenever needed rather than sharing subfunctions as
in a branching program. Such a decision tree may not immediately
satisfy the "read-once" property, but it is easily
converted into one by eliminating subtrees under duplicated
variables along a path. The total number of nodes in this resultant
decision tree is at most 2 O(log Finally,
compute the number of satisfying assignments for the decision
tree as described above for a ROBP.
The next two propositions are not used in the paper; they
are proved here simply in order to complete Table 1.
Proposition 3 Decision trees can be tested for monotonicity
in polynomial time.
Proof.
Let T be a given decision tree over n variables.
It is convenient to extend the partial order  defined over
the Boolean lattice to the set of partial vectors by:    if
for all i,  implies that  i 6= 0. For any partial vector
, we will say that for every
total vector   , T
Each leaf node x in T determines a partial vector p(x)
based on the assignment to variables on the path from the
root of T to the leaf node. Let us say that x is a counterexample
to monotonicity of T if there is a partial vector   p(x)
such that T and x has a value of 1. The essential
observation is that T is monotone if and only if no leaf of T
is a counterexample to its monotonicity.
It is easy to test for monotonicity of T using the above
observation: for each leaf node x assigned the value 1, let
be the partial vector obtained by setting to 1 only the
variables in p(x) assigned a 1 and leaving the remaining variables
as *. If under the projection p 0 (x) T is not identically 1,
then x is a counterexample to monotonicity as demonstrated
by any path to 0 in the projection.
A Boolean function f(v
permutation
(v 0
Proposition 4 ROBPs can be tested for symmetry in polynomial
time.
Proof.
This proof is inspired by the central idea in [BCW80].
Let f be any Boolean function over the set of variables
denote the set of assignments
that f evaluates to 1.
We first generalize f to be a real-valued function by
treating V to be a set of real variables; more precisely re-define
f by:
Y
Y
When the variables in V assume the values 0 and 1, the
value of the redefinition coincides with the value of the Boolean
so we do have a true generalization. As shown
in [BCW80], given a ROBP representation of the Boolean
function f , the value of the real function on any real vector
over V can be computed in linear time by visiting the ROBP
in topological order.
Next, let
Table

2: System of Linear Equations for calculating jR k jB
be the set of assignments in f + with precisely k ones. Then,
Y
x
Y
Now computing the values of g(0);
mentioned above by using the ROBP representation of f and
treating jR k j as variables leads to the system of linear equations
in Table 2.
It's easily shown that the rank of the coefficient matrix
therefore the system admits a unique solution for
Finally, observe that the Boolean
function f is symmetric if and only if jR k j is either 0 or n
for all values of k; 0  k  n.
From the above proof, it follows that we can decide symmetry
for OBDDs and decision trees also in polynomial time.
Proposition 5 SAT j-DNF formulas are sat-countable.
Proof. Let us say that two terms t and t 0 are conflicting if t
contains a literal l and t 0 contains a literal  l. The consensus
of two non-conflicting terms t and t 0 , denoted tt 0 is the term
obtained from the union of all the literals in t and t
t 0 are conflicting, then their consensus is 0.
The definition of a SAT-j DNF formula f implies that in
every set terms of the formula,
there must be at least two conflicting terms. Therefore, using
the principle of inclusion and exclusion,
Here, for any term t of k literals ]t is simply 2 n k . From
the comment above, this sum needs to consider at most the
consensus of j terms of f . For constant j, the total time
for the computation is a polynomial.
Proposition 6 -formulas are sat-countable.
Proof. Let f be a -formula over a set of n variables. If
f is the constant 1, then f is the constant
0, then is a term containing a single literal,
then can be written either as f 1 f 2
or are -formulas over disjoint
sets of n 1 and n 2 variables respectively. Then, it is easy
to argue that
Recursive
application of these rules ensures that ]f can be computed in
3 Finding a Decision Tree Approximation
The main result of this section is an algorithm for constructing
a decision tree -approximation of any Boolean function
f represented in a projection-closed sat-countable class.
The heart of our algorithm is a procedure FIND which is
a generalization of the dynamic programming method used
in [GLR99] for truth-table minimization of decision trees.
FIND works as follows. Given f , a Boolean function
over n variables, a height parameter h and a size parameter
m, it builds precisely one tree from the set T ;k , for each
partial vector  of size at most h and for eac h k; 0  k  m.
(Here, T ;k is the set of all decision tree representations of
the function f of size at most k and height at most h jj
that have minimum error with respect to f and among all
such trees, are of minimum size.) The desired approximation
will therefore be the tree constructed for the set T ;w , where
1g.
The algorithm employs a two-dimensional array P [; k]
to hold a tree in T ;k . A tree in the P array will be represented
by a triple of the form (root, left subtree, right sub-
tree), unless it contains a single leaf node, in which case it
will be represented by the leaf's value. For a partial vector
, the notation :v 1 (:v 0, respectively) denotes the
partial vector obtained by extending  by setting the variable
v to 1 (0, respectively).
Lemma 7 Algorithm FIND is correct, i.e., given a sat-count-
able representation of a Boolean function f , a height parameter
h, and a size parameter m, FIND outputs a decision tree
T 0 of height at most h and size at most m such that among all
such decision trees, err(T 0 , f ) is minimum; if there is more
than one decision tree with the same minimum error, then
is of minimum size among these trees.
Proof. We show by induction on l
that P [; k] is a tree in T ;k , for all 0  jj  h and
01. foreach  such that jj  h do
02. if ](f
03. else P [; 0] 0;
04.
05. for to 0 do
06. foreach  such that do
07. foreach do
08. P [;
09. foreach variable v not used in  and each k do
11. if err(P [; k]; f ) > errV then
12.
13. else if err(P [; k]; f
14. if (jP [:v 0; k
15.

Figure

1: Algorithm FIND.
mg. For any , the
tree must be a leaf with value 0 or 1, depending on which
value yields the minimum error relative to f . Lines 2 and
3 of Algorithm FIND examine the hypercube corresponding
to f and determine whether the majority of assignments are
0 or 1. This is also true for any  such that l
l
Assume that P [; k 0 ] has been correctly computed for all
such that l  < l  and all k 0 in [0; minf2 hjj
Also assume that all P [; k 0 ] have been correctly computed
for all k 0 in [0; k 1]. We show that FIND causes a tree
in T ;k to be placed in P [; k]. If the size of the trees
in T ;k is less than k, then, from the induction hypothe-
sis, P [; k] is initialized to a tree in T ;k in line 8. Lines
9-15 cannot then modify P [; k] and the algorithm is cor-
rect. Therefore, let the size of the trees in T ;k be exactly
k. Let Opt be any tree in T ;k and let v be its root.
Now v must be a variable that is not assigned a value in
. Let the sizes of Opt's left and right subtrees be k 0 and
respectively. Observe that k 0 and k 1 are one of the
examined in line 9. Let
and let  1. From the induction hypothe-
err(Right subtree of Opt; f1 ). Since
the error of a tree is the sum of the errors of its two subtrees,
the algorithm finds a tree for P [; k] which has error at most
that of Opt and size at most that of Opt. The lemma follows.
Lemma 8 Let p(jf j; n) denote the time complexity for computing
the number of satisfying assignments of an arbitrary
projection of a given sat-countable function f . The time
complexity of FIND is O(n O(h)
Proof. Since f is a sat-countable representation, the time
required by line 2 is O(p(jf j; n)n). The number of partial
vectors examined in line 1 is  h
lines 1-4 take O(p(jf j; n)n O(h) ) time. Lines 5 and 6 cause
the same O(n O(h) ) partial vectors to be examined. The variable
(line 7) takes on at most m values, there are at most n
possibilities for v and m possible combinations of k 0 and k 00
in line 9.
The complexity of lines 10-15 is dominated by O(1) error
computations between a decision tree T in P and the
sat-countable function f . Each such error computation
can be implemented as follows. For any leaf node x in
be the partial vector corresponding to the evaluation
path in T leading up to x. The contribution to the
total error of the partial vector  is then either ]((f
the leaf x has value 0 and 2 njjjj ]((f  )  ) if it has
value 1. The total error err(T obtained by summing
the errors computed in this fashion over each leaf
of T . The complexity of this computation is bounded by
O(p(jf j; n)m) and that of lines 5-15 and hence Algorithm
FIND is bounded by O(n O(h) m 3 p(jf j; n)). As is common
in dynamic programming algorithms, memoizing helps to
reduce the overall complexity. Observe that the complexity
of error computation can be reduced by maintaining a
second two-dimensional array E each of whose elements
contains the error of the corresponding element in array P .
First E[; 0] can be computed in O(p(jf j; n)) time in lines
2 and 3. Then the remaining E[; k]s are computed every
time P [; k] is updated in O(1) time by simply summing
the error of the left and right subtrees of P [; k]. With
this time-saving modification, the time complexity becomes
O((p(jf
Lemma 9 Let T be an m-node decision tree. Then there
exists a decision tree T  of height at most
and at most m nodes such that T  is an -approximation of
T .
Proof. Restrict T to height h by converting any node x
at level h to either 0 or 1 depending on whether there are
more 0's or 1's respectively in the hypercube defined by the
path leading to x. Call this tree T  . Clearly T  has no
more than m nodes and the error of T  is confined to the
hypercubes of the converted nodes x at level h in the original
tree. Since there are at most dm=2e such nodes and the
error of each node is at most 2 n h 1 , it follows that T  is a
-approximation of T . Substituting
4 now yields the desired result.
Theorem 10 Given a sat-countable Boolean function representation
f whose smallest decision tree representation has
at most m nodes and any error parameter , we can find a
decision tree T 0 of at most m nodes which -approximates f
in time polynomial in jf j and n log m= .
Proof. Given f , we use the standard doubling trick to determine
in O(log m  ) iterations of the algorithm the least value
m  such that FIND(f , m  , log((m  returns a decision
tree which -approximates f . By Lemma 9, m  is at
most m, the size of the smallest decision tree which can represent
f . The correctness and time complexity then follow
from Lemmas 7 and 8 respectively.
4 Learning Decision Trees under the Uniform
Distribution
We show that the algorithm of the previous section can be extended
to learn decision trees under the uniform distribution.
As we remarked in the introduction, this means that, given
access to a uniformly distributed sample of evaluations of
a boolean function f an error parameter  and a confidence
parameter -, our algorithm will output a a decision tree T
of at most m nodes, where m is the least number of nodes
needed to represent f as a decision tree and such that T -
approximates f with confidence at least 1 -. The algorithm
takes time polynomial in n log(m=) and log(1=-), i.e., it is
a quasi-polynomial time algorithm. However, the sample-
complexity of the algorithm is only a modest polynomial in
the parameters m, log n, log(1=-) and log(1=).
We use the following additional terminology to prove the
results of this section. Let T m;h;n denote the class of decision
trees over n variables that have height at most h and
size at most m. For any decision tree T , let T  (h) be the
tree of height h obtained from T by converting all non-leaf
nodes of depth h in T to leaf nodes with classification 0 or
1, depending on whether the majority of the assignments in
the corresponding hypercube of f are classified as 0 or 1,
respectively.
Recall that for any two Boolean functions f 1 , f 2 over n
denotes the number of assignments
for which f 1 () 6= f 2 (); by extension, if S is a sample
of classified examples of the form h; bi where  is an assignment
is the
number of examples in S of the form h; bi where f() 6= b.
We need the following well-known inequalities.
Proposition 11 (Chernoff Bounds) Let
the outcomes of r identical, independent Bernoulli trials
with Prob [X
pr and for 0
Prob[R  (p
Given a sample S of classified examples of a
boolean function of the form h; bi where  is an assignment
and b 2 f0; 1g, a height parameter h, and a size parameter
m, a decision tree D of height at most h and size at
most m can be computed such that among all such decision
trees, err(D, S) is minimum, and among all such minimum
error trees, D has minimum size. The computation requires
O(n O(h)
Proof. Let S denote the assignments in S that extend the
partial assignment . For a given , S can be computed
in O(jSjn) time. Modify the condition of Line 2 of Algorithm
FIND so that number of assignments of S whose values
are 1 and 0 are compared. The modified Line 2 takes
O(jSjn) time. All references to f (lines 10, 11, and 13)
are replaced by S . Error computations can be carried out
as described in the proof of Lemma 8. Each error computation
takes O(jSjm) time. Since the rest of the algorithm is
unchanged, the complexity is obtained by replacing p(jf j; n)
by jSj. Note that this is also true of the modified algorithm
proposed in the proof of Lemma 8. Correctness follows from
Lemma 7.
Theorem 13 Given:
A uniformly distributed sample S of size
of examples of an m-node decision tree T over n variables

An error parameter , 0 <  < 1, and
A confidence parameter -, 0 < - < 1,
we can find a decision tree D in T m;h;n with
in time O(rm 2 n O(h) ) such that with confidence at least 1 -,
the error of D in approximating T is at most , i.e.,
Proof.
We execute algorithm FIND modified to deal with a sample
S as described in Lemma 12 with the parameters m and
h as above. Let
Call a decision tree T 0 in T m;h;n bad if err(T
For any fixed bad decision tree T 0 ,
outputs
m;h;n and has least error over sample S]
2Here, the last inequality follows from Chernoff bounds
applied to the number of errors in S of the trees T 0 and
Now the probability p that FIND outputs any bad tree T 0
in T m;h;n is certainly at most jT m;h;n j  2e r 2
8 . The number
of binary trees on at most m nodes is at most 2  4 m and so
the number of decision trees of at most m nodes is at most
which also is an upper bound on T m;h;n . Con-
sequently, for our choice of r in the proposition (and after
a little bit of arithmetic), the probability p turns out to be at
most -.
Conclusions
Given a sat-countable representation of a boolean function or
a uniformly distributed sample of evaluations of a boolean
function, this paper presents a quasi-polynomial algorithm
for computing a decision tree of smallest size that approximates
this function. Is it possible to achieve this in polynomial
time? Failing this, is it possible to obtain a decision
tree whose size is within a polynomial factor of the smallest
approximating decision tree in polynomial time?
Finding a decision tree of smallest size equivalent to a
given one is NP-hard [ZB98]. This opens the question of
whether at least a polynomial approximation of the smallest
equivalent decision tree is possible in polynomial time. The
ideas in this paper do not seem enough to answer this ques-
tion, but there is some hope that combining these ideas with
the results of Ehrenfeucht and Haussler [EH89] will work.
As a matter of fact, their results can already be used to give
a quasi-polynomial approximation to the smallest decision
tree equivalent to any projection-closed representation which
allows testing for tautology and satisfiability in polynomial
time in quasi-polynomial time. This is done in the following
way.
We consider the sample S in the Ehrenfeucht and Haussler
algorithm to be all 2 n assignments. However, we avoid
using time polynomial in the sample size, by noting that the
operations on the sample in the algorithm consist only of:
1. Checking if all assignments in S evaluate to either 0 or
1, and
2. Computing a new sample S 0 obtained by projecting
given variable to 0 or 1.
Doing these operations in time polynomial in the given representation
converts their algorithm into one whose complexity
has an added factor of the form O(n O(r) ), where r is the
smallest rank of any equivalent decision tree; since r cannot
exceed O(log m), where m is the size of the smallest equivalent
decision tree, we get the desired quasi-polynomial approximation

Finally, can the ideas of this paper be combined with
those of Ehrenfeucht and Haussler to properly learn decision
trees under arbitrary distributions with or without membership
queries?
6

Acknowledgment

We thank the anonymous referee who suggested the sharper
bound on T m;h;n which led to an improvement in the sample
complexity in Theorem 13.



--R

Occam's Razor.
Equivalence of Free Boolean Graphs can be Decided Probabilistically in Polynomial Time.
Exact Learning Boolean Functions via the Monotone Theory.
Simple Learning Algorithms for Decision Trees and Multi-variate Polynomials
Learning Decision Trees from Random Examples.
Computers and Intractability
Exact Learning when Irrelevant Variables Abound.
Constructing Optimal Binary Decision Trees is NP-complete
On boolean decision trees with faulty nodes.
Induction of Decision Trees.
Learning Decision Tree Classi- fiers
On Some Central Problems in Computational Complexity.
Finding Small Equivalent Decision Trees is Hard.
--TR
Occam''s razor
Learning decision trees from random examples needed for learning
Exact learning Boolean functions via the monotone theory
Learning decision tree classifiers
Partial Occam''s razor and its applications
Exact learning when irrelevant variables abound
Computers and Intractability
Induction of Decision Trees
Simple learning algorithms for decision trees and multivariate polynomials
On some central problems in computational complexity.
representations of Boolean functions;learning theory;algorithms;decision trees