Simple Learning Algorithms for Decision Trees and Multivariate Polynomials.
In this paper we develop a new approach for learning decision trees and multivariate polynomials via interpolation of multivariate polynomials. This new approach yields simple learning algorithms for multivariate polynomials and decision trees over finite fields under any constant bounded product distribution. The output hypothesis is a (single) multivariate polynomial that is an $\epsilon$-approximation of the target under any constant bounded product distribution.The new approach demonstrates the learnability of many classes under any constant bounded product distribution and using membership queries, such as j-disjoint disjunctive normal forms (DNFs) and multivariate polynomials with bounded degree over any field.The technique shows how to interpolate multivariate polynomials with bounded term size from membership queries only. This, in particular, gives a learning algorithm for an O(log n)-depth decision tree from membership queries only and a new learning algorithm of any multivariate polynomial over sufficiently large fields from membership queries only. We show that our results for learning from membership queries only are the best possible.
Introduction
From the start of computational learning theory, great emphasis has been put on developing
algorithmic techniques for various problems. It seems that the great progress has been made in
learning using membership queries, especially such functions as decision trees and multivariate
polynomials. Generally speaking, three different techniques were developed for those tasks:
the Fourier transform technique, the lattice based techniques and the Multiplicity Automata
technique. All the techniques use membership queries (which is also called substitution queries
for nonbinary fields).
The Fourier transform technique is based on representing functions using a basis, where a
basis function is essentially a parity of a subset of the input. Any function can be represented
as a linear combination of the basis functions. Kushilevitz and Mansour [KM93] gave a general
technique to recover the significant coefficients. They showed that this is sufficient for learning
decision trees under the uniform distribution. Jackson [J94] extended the result to learning DNF
under the uniform distribution. The output hypothesis is a majority of parities. (Also, Jackson
[J95] generalizes his DNF learning algorithm from uniform distribution to any fixed constant
bounded product distribution.)
The lattice based techniques are, at a very high level, performing a traversal of the binary
cube. Moving from one node to its neighbor, in order to reach some goal node. Angluin [A88]
gave the first lattice based algorithm for learning monotone DNF. Bshouty [Bs93] developed the
monotone theory, which gives a technique for learning decision trees under any distribution. (The
output hypothesis in that case is depth 3 formulas.) Schapire and Sellie [SS93] gave a lattice
based algorithm for learning multivariate polynomials over a finite field under any distribution.
(Their algorithm depends polynomially on the size of the monotone polynomial that describes
the function.)
Multiplicity Automata theory is a well studied field in Automata theory. Recently, some very
interesting connections where given, connecting learning such automata and learning decision
trees and multivariate polynomials. Ohnishi, Seki and Kasami [OSK94] and Bergadano and
gave an algorithm for learning Multiplicity Automata. Based
on this work Catlan and Varricchio [BCV96] show that this algorithm learns disjoint DNF.
Then Beimel et. al. [BBB+96] gave an algorithm that is based on Hankel matrices theory
for learning Multiplicity Automata and show that multivariate polynomials over any field are
learnable in polynomial time. (In all the above algorithms the output hypothesis is a Multiplicity
Automaton.)
All techniques, the Fourier Spectrum, the Lattice based and the Multiplicity Automata algorithms
give also learnability of many other classes such as learning decision trees over parities
(nodes contains parities) under constant bounded product distributions, learning CDNF (poly
size DNF that has poly size CNF) under any distribution and learning j-disjoint DNF (DNF
where the intersection of any j terms is 0).
In this paper we develop a new approach for learning decision trees and multivariate polynomials
via interpolation of multivariate polynomials over GF (2). This new approach leads to
simple learning algorithms for decision trees over the uniform and constant bounded product
distributions, where the output hypotheses is a multivariate polynomial (parity of monotone
terms).
The algorithm we develop gives a single hypothesis that approximate the target with respect
to any constant bounded product distribution. In fact the hypothesis is a good hypothesis under
any distribution that supports small terms. That is any distribution D where for a term T of size
!(log n) we have PrD Previous algorithms do not achieve this property.
It is also known that any DNF is learnable with membership queries under constant bounded
product distribution [J95], where the output hypothesis is a majority of parities. Our contribution
for j-disjoint DNF is to use an output hypothesis that is a parity of terms and to show that the
output hypothesis is an ffl approximation of the target against any constant bounded distribution.
We also study the learnability of multivariate polynomials from membership queries only. We
give a learning algorithm for multivariate polynomials over n variables with maximal degree
for each variable, where c ! 1 is constant, and with terms of size
d
log d)
using only membership queries. This result implies learning decision trees of depth O(log n) with
leaves from a field F from membership queries only.
This result is a generalization of the result in [B95b] and [RB89], where the learning algorithm
uses membership and equivalence queries in the former and only membership queries in the
latter.
The second result is a generalization of the result in [KM93] for learning boolean decision tree
from membership queries. The above result also give an algorithm for learning any multivariate
polynomial over fields of size log d)) from membership queries only.
This result is a generalization of the results in [BT88, CDG+91, Z90] for learning multivariate
polynomials under any field. Previous algorithms for learning multivariate polynomial over finite
fields F require asking membership queries with assignments in some extension of the field F
[CDG+91]. In [CDG+91] it is shown that an extension n of the field is sufficient to interpolate
any multivariate polynomial (when membership queries with assignments from an extension field
are allowed).
The organization of the paper is as follows. In section 2 we define the learning model and
the concept classes. In section 3 we give the algorithm for learning multivariate polynomial for
the boolean domain. In section 4 we give some background for multivariate interpolation. In
section 5 we show how to reduce learning multivariate polynomials to zero testing and to other
problems. Then in section 6 we give the algorithm for zero testing and also give a lower bound
for zero testing multivariate polynomials.
2 The Learning Model and Concept Classes
2.1 Learning Models
The learning criterion we consider is exact learning [A88] and PAC-learning[Val84].
In the exact learning model there is a function f called the target function f : F n ! F which
is a member of a class functions C defined over the variable set
field F . The goal of the learning algorithm is to output a formula h that is equivalent to f .
The learning algorithm performs a membership query (also called substitution query for the
nonbinary fields) by supplying an assignment a to the variables in V as input to
a membership oracle and receives in return the value of f(a). For our algorithms we will regard
this oracle as a procedure MQ f (). The procedure input is an assignment a and its output is
The learning algorithm performs an equivalence query by supplying any function h as input
to an equivalence oracle with the oracle returning either "YES", signifying that h is equivalent
to f , or a counterexample, which is an assignment b such that h(b) 6= f(b). For our algorithms
we will regard this oracle as a procedure EQ f (h). We say the hypothesis class of the learning
algorithm is H if the algorithm supplies the equivalence oracle functions from H.
We say that a class of boolean function C is exactly learnable in polynomial time if for any
there is an algorithm that runs in polynomial time, asks a polynomial number of
queries (polynomial in n and in the size of the target function) and outputs a hypothesis h that
is equivalent to f .
The PAC learning model is as follows. There is a function f called the target function which
is a member of a class of functions C defined over the variable set g. There is
a distribution D defined over the domain F n . The goal of the learning algorithm is to output a
formula h that is ffl-close to f with respect to some distribution D, that is,
Pr D
The function h is called an ffl-approximation of f with respect to the distribution D.
In the PAC or example query model, the learning algorithm asks for an example from the
example oracle, and receives an example (a; f(a)) where a is chosen from f0; 1g n according to
the distribution D.
We say that a class of boolean functions C is PAC learnable under the distribution D in
polynomial time if for any f 2 C over V n there is an algorithm that runs in polynomial time,
asks polynomial number of queries (polynomial in n, 1=ffl, 1=ffi and the size of the target function)
and with probability at least outputs a hypothesis h that is ffl-approximation of f with
respect to the distribution D.
It is known from [A88] that if a class is exactly learnable in polynomial time from equivalence
queries and membership queries then it is PAC learnable with membership queries in polynomial
time under any distribution D.
Let D be a set of distribution. We says that C is PAC learnable under D if there is a PAC-learning
algorithm for C such that for any distribution D 2 D unknown to the learner and for
any f 2 C the learning algorithm runs in polynomial time and outputs a hypothesis h that is an
ffl-approximation of f under any distribution D 0 2 D.
2.2 The Concept Classes and Distributions
A function over a field F is a function f set X. All classes considered in
this paper are classes of functions where . The elements of F n are called assignments.
We will consider the set of variables V describe the value of the
i-projection of the assignment in the domain F n of f . For an assignment a, the i-th entry of a
will be denoted by a i .
A literal is a nonconstant polynomial p(x i ). A monotone literal is x r
nonnegative
integer r. A term (monotone term) is a product of literals (monotone literals). A multivariate
polynomial is a linear combination of monotone terms. A multivariate polynomial with nonmonotone
terms is a linear combination of terms. The degree of a literal p(x i ) is the degree of the
polynomial p. The size of a term
Let MULF (n; k; t; d) be the set of all multivariate polynomials over the field F over n variables
with at most t monotone terms where each term is of size at most k and each monotone literal is
of degree at most d. For the binary field B the degree is at most so we will use MUL(n; k; t).
F (n; k; t; d) will be the set of all multivariate polynomial with nonmonotone terms with the
above properties. We use MUL ? (n; k; t) when the field is the binary field. Throughout the paper
we will assume that t - n. Since every term in MUL ?
F (n; k; t; d) can be written as multivariate
polynomial in MUL F (n; k; (d d) we have
Proposition 1
F (n; k; t; d) ' MUL F (n; k; t(d
For the boolean field (disjunctive normal form) is a disjunction of terms.
A j-disjoint DNF is a DNF where the disjunction of any j terms is 0. A k-DNF is a DNF with
terms of size at most k literals.
A decision tree (with leaves from some field F) over V n is a binary tree whose nodes are labeled
with variables from V n and whose leaves are labeled with constants from F . Each decision tree
T represents a function f To compute f T (a) we start from the root of the tree
the root is labeled with x i then f T TR (a) if a TR is the right subtree of
the root (i.e., the subtree of the right child of the root with all its descendent). Otherwise (when
a is the left subtree of the root. If T is a leaf then f T (a) is the
label of this leaf.
It is not hard to see that a boolean decision tree of depth k can be represented in MUL ? (n;
(each leaf in the decision tree defines a term and the function is the sum of all terms), and that
a j-disjoint k-DNF of size t can be represented in MUL ? (n; example
[K94].) So for constant k and d = O(log n) the number of terms is polynomial.
For a DNF and multivariate polynomial, f , we define size(f) to be the number of terms in f .
For a decision tree the size will be the number of leaves in the tree.
A product distribution is a distribution D that satisfies D(a
distributions D i on F . A product distribution is fixed constant bounded if there is a constant
1=2, that is independent of the number of variables n, such that for any variable x i ,
distribution D supports small terms if for every term of size !(log n),
we have PrD is the number of variables.
3 Simple Algorithm for the Boolean Domain
In this section we give an algorithm that PAC-learns with membership queries MUL ? (n; n; t)
under any distribution that supports small terms in polynomial time in n and t. We remind the
reader that we assume t - n. All the algorithms in the paper run in polynomial time also when
3.1 Zero test MUL(n; k; t)
We first show how to zero-test elements in MUL(n; k; t) in polynomial time in n and 2 k assuming
k is known to the learner. The algorithm will run in polynomial time for
Choose a term
of maximal size in f . Choose any
values from f0; 1g for the variables not in T . The projection will not be the zero function
because the term T will stay alive in the projection. Since the projection is a nonzero function
with variables there is at least one assignment for x
that gives value 1 for the
function. This shows that for a random and uniform assignment a, with probability at
least . So to zero test a function f 2 MUL(n; k; t) randomly and uniformly choose
polynomial number of assignments a i . If f(a i ) is zero for all the assignments then with high
probability we have f j 0. Now from the above we have
the probability that randomly chosen
elements is at most ffi.
This implies
there is a polynomial time probabilistic zero testing algo-
rithm, that succeeds with high probability.
3.2 Learning MUL(n; k; t).
We now show how to reduce zero-test to learning.
We first show how to find one term in f . If we know that
is a term in f . If Since we can zero-test we can find the minimal
This implies that f x 1
some multivariate polynomial f 1 . If f 1 we know that
is a term in f . We
continue recursively with f
1, in this case
is a term in f .
After we find a term T we define -
This removes the term T from f , and thus -
1). We continue recursively with -
f until we recover all the terms of f . Membership
queries for -
f can be simulated by memebership for f because MQ -
(a). The
complexity of the interpolation is performing nt calls to the zero testing procedure. This gives
there is an algorithm that with probability at least learns
f with
nt log nt
membership queries.
In particular this gives,
there is a polynomial time probabilistic interpolation
algorithm, that succeeds with high probability to learn f from membership queries.
3.3 Learning MUL ?
We now give a PAC-learning algorithm that learns MUL ? (n; n; t) under any distribution that
support small terms. We first give the idea of the algorithm. The formal proof is after Theorem 1.
To PAC-learn f we randomly choose an assignment a and define
a). A term in f of size k will have on average k=2 monotone literals in f 0 , and terms
with
will have with high probability \Omega\Gamma literals.
We perform a zero-restriction, i.e. for each i, with probability 1=2 we substitute x i / 0 in f 0 .
Since a term of size k in f has on average k=2 monotone literals after the first shift f(x + a), in
the second restriction this term will be zero with probability (about) This probability
is greater than Therefore with high probability all the terms
of size more than O(log t) will be removed by the second restriction. This ensures that with
high probability the projection f 00 is in MUL ? (n; O(log t); t), and therefore by Proposition 1
Now we can use the algorithm in subsection 3.2 to learn f 00 .
Notice that for multivariate polynomial h (with monotone terms) when we performed a zero
restriction, we delete some of the monotone terms from h, therefore, the monotone terms of f 00
are monotone terms of f 0 .
We continue to take zero-restrictions and collect terms of f 0 until the sum of terms that appear
in at least one restriction defines a multivariate polynomial which is a good approximation of f 0 .
We get a good approximation of f 0 with respect to any distribution that supports small terms
since we collect all the small (i.e. O(log t)) size terms.
Theorem 1 There is a polynomial time probabilistic PAC-learning algorithm with membership
queries, that learns MUL ? (n; n; t) under any distribution that support small terms.
We now prove that the algorithm sketched above PAC-learns with membership queries any
multivariate polynomial with non-monotone terms under distributions that support small terms.
For the analysis of the correctness of the algorithm we first need to formalize the notion of
distributions that support small terms. The following is one way to define this notion.
Definition 1. Let D c;t;ffl be the set of distributions that satisfy the following: For every
c;t;ffl and any DNF f with t terms of size greater than c log(t=ffl) we have
Pr
Notice that all the constant bounded product distributions D where
for all i are in D 1= log(1=d);t;ffl . In what follows we will assume that c - 2 and ffl ! 1=2. We will use
Chernoff bound (see [ASE]).
independent random variables where Pr[X
Then for any a we have
Pr
be a multivariate polynomial where T are terms and jT 1
Our algorithm starts by choosing a random assignment a and defines f 0
All terms that are of size s (in f 0 ) will contain on average s=2 monotone literals. Therefore by
Chernoff bound we have
Lemma 7 With probability at least 1=2 all the terms in f 0 of size more than ffc log(t=ffl), contain
at least (ff=4)c log(t=ffl) monotone literals, where ff - 4 and c - 1.
Proof. Let T be any term of size ffc log(t=ffl). Let P (T ) be the number of monotone literals
in T . We have
Pr
Since the number of terms of f 0 is t and ffl ! 1=2 the result follows.2
With probability at least 1=2 all the terms of size more than 4c log(t=ffl) will contain at least
c log(t=ffl) monotone literals and all terms of size 8c log(t=ffl) will contain at least 2c log(t=ffl)
monotone literals. Now we split the function f 0 into 3 functions f 1 , f 2 and f 3 . The function
will contain all terms that are of size at most 4c log(t=ffl). The function
will contain all terms of size between 4c log(t=ffl) and 8c log(t=ffl) and the
function f all terms of size more than 8c log(t=ffl).
Similarly,
Our algorithm will find all the terms in f 1 , some of the terms in f 2 and none of the terms in
f 3 . Therefore we will need the following claim.
is a multivariate polynomial that contains some of the terms
in f 2 . Then for any D 2 D c;t;ffl we have
Pr
Proof. The error is
Pr
Let
~
~
~
is the part of the term that contains monotone literals and ~
is the part
that contains the nonmonotone literals. If -
that when we change -
~
to sum of monotone terms we get
Y
q2S
So every monotone term in f 2 will contain one of the terms -
Therefore we
can
where f 2;i are multivariate polynomial with monotone
terms. Since h is a multivariate polynomial that contains some of the terms in f 2 we have
. Since j -
by the definition of distribution that support small terms we have
The algorithm will proceed as follows. We choose
zero restrictions . Recall that a zero restriction p of f 0 is a function f 0 (p) where
with probability 1=2,x i / 0 and with probability 1=2 it remains alive. We will show that with
probability at least 1=2 we have the following:
(A) For every term in f 1 there is a restriction p i such that f 1 (p i ) contains this term.
(B) For every
We will regard A and B as events. Let T 1 be the set of terms in f 1 . We know that jT 1
and every term in T 1 is of size at most 4c log(t=ffl). Let T 3 be the set of terms in f 3 . We know
that the number of terms in T 3 is at most t and every term has at least 2c log(t=ffl) monotone
literals. We have
Pr[not
and, for c - 2,
Pr[not
Therefore we have both events with probability at least 1=2.
This shows that with probability at least 1=2 all the projections f(p i ) contains terms of
size at most 8c log(t=ffl). Therefore, the algorithm proceed by learning each projection f(p i
using the previous algorithm and collecting all the terms of size
2c log(t=ffl).2
The number of membership queries of the above algorithm is O((t=ffl) k n) for some constant k.
For the uniform distribution k - 19.
The above analysis algorithm can also be used to learn functions f of the form
are terms and + is the addition of a field F . These
functions can be computed as follows. For an assignment a,
This gives the
learnability of decision trees with leaves that contain elements from the field F .
4 Multivariate Interpolation
In this section we show how to generalize the above algorithm for any multivariate polynomial
over any field.
Let
ff2I
a ff x ff 1
be a multivariate polynomial over the field F where a ff 2 F and ff are integers. We will
denote the class of all multivariate polynomials over the field F and over the variables x
by F [x The number of terms of f is denoted by jf j. We have jf all a ff are
not zero. When d be the maximal
degree of variables in f , i.e., I ' [d] n where
are d constants where is the zero of the field. A univariate polynomial
over the field F of degree at most d can be interpolated from membership queries
as follows. Suppose
where \Delta (i) (f) is the coefficient of x i in f in its polynomial representation. Then
This is a linear system of equations and can be solved for \Delta (i) (f ), as follows,
det
is the Vandermonde matrix.
If f is a multivariate polynomial then f can be written as
where \Delta (i) (f) is a multivariate polynomial over the variables x . We can still use (1) to
find \Delta (i) (f) by replacing each f(fl i ) with Notice that from the first equation in
the system, since
?From (1) a membership query for \Delta (i) can be simulated using d queries to
f . From (2), a membership query to \Delta (0) can be simulated using one membership query to f .
We now extend the \Delta operators as follows: for
Here \Delta always operates on the variable with the smallest index. So \Delta i 1 operates on x 1 in f to
give a function f 0 that depends on x operates on x 2 in f 0 and so on. We
will also write x i for the term x
k . The weight of i, denoted by wt(i), is the number of
nonzero entries in i.
The operator \Delta i (f) gives the coefficient of x i
1 in f when represented in F [x the
operator gives the coefficient of x i when f is represented in
F [x
Suppose I ' [d] k be such that
I are the k-suffixes of all terms of f . Here the k-suffix of a term x
n is x
k . Since
I if and only if x i is a k-suffix of some term in f , it is clear that jIj - jf j and we must have
i2I
We now will show how to simulate membership queries for using a
polynomial number (in n and jf j) of membership queries to f . Suppose we want to find
for some c 2 F n\Gammak using membership queries to f . We take r assignments -
ask membership queries for (-fl i ; c) for all
Now
then the above linear system of equations can be solved in time
The solution gives f)(c). The existence of -
where the above determinant is not zero will be
proven in the next section.
5 Reducing Learning to Zero-testing (for any Field)
In this section we show how to use the results from the previous section to learn multivariate
polynomials.
Let MULF (n; k; t; d) be the set of all multivariate polynomials over the field F over n variables
with t terms where each term is of size k and the maximal degree of each variable is at most d.
We would like to answer the following questions. Let f 2 MUL F (n; k; t; d).
1. Is there a polynomial time algorithm that uses membership queries to f and decides whether
2. Given i - n. Is there a polynomial time algorithm that uses membership queries to f and
decides whether f depends on x i ?
3. Given fi t. Is there an algorithm that
runs in polynomial time and finds such that
r
4. Is there a polynomial time algorithm that uses membership queries to f and identifies f?
When we say polynomial time we usually mean polynomial time in n; k; t and d but all the
results of this section hold for any time complexity T if we allow a blow up of poly(n; t) in the
complexity.
We show that 1,2 and 4 are equivalent and 1 ) 3. Obviously 2 2. We
will show
To prove 1 notice that f 2 MUL F (n; k; t; d) is independent of x i if and only if
is the coefficient of x i in f we have g 2 MUL F (n; k; t; d). Therefore
we can zero-test g in polynomial time.
To prove 1 s be a zero-test for functions in MULF (n; k; t; d), that is, run the
algorithm that zero-test for the input 0 and take all the membership queries in the algorithm
. We now have f 2 MUL F (n; k; t; d) is 0 if and only if f(fl i
Consider the s \Theta r matrix with rows [fl i 1
]. If this matrix have rank r then we choose r
linearly independent rows. If the rank is less than r then its columns are dependent and therefore
there are constants c i , r such that
r
s:
This shows that the multivariate polynomial
in MUL F (n; k; t; d) we get a contradiction.
Now we show that 1+2+3 ) 4. This will use results from the previous section. The algorithm
first checks whether f depends on x 1 , and if yes it generates a tree with a root labeled with x 1
that has d children. The ith child is the tree for \Delta i (f ). If the function is independent of x 1 it
builds a tree with one child for the root. The child is \Delta 0 (f ). We then recursively build the tree
for the children. The previous section shows how to simulate membership queries at each level
in polynomial time. This algorithm obviously works and it correctness follows immediately from
the previous section and (1)-(3).
The complexity of the algorithm is the size of the tree times the membership query simulation.
The size of the tree at each level is bounded by the number terms in f , and the depth of the
tree is bounded by n, therefore, the tree has at most O(nt) nonzero nodes. The total number of
nodes is at most a factor of d from the nonzero nodes. Thus the algorithm have complexity the
same as zero testing with a blow up of poly(n; t; d) queries and time.
Now that we have reduced the problem to zero testing we will investigate in the next section
the complexity of zero testing of MULF (n; k; t; d).
6 Zero-test of MULF (n; k; t; d)
In this section we will study the zero testing of MUL F (n; k; ?; d) when the number of terms is
unknown and might be exponentially large. The time complexity for the zero testing should be
polynomial in n and d (we have k ! n so it is also polynomial in k). We will show the following
Theorem 2. The class MUL F (n; k; ?; d), where d - cjF j, is zero testable in randomized
polynomial time in n, d and t (here t is not the number of terms in the target) for some constant
only if
d
The algorithm for the zero testing is simply to randomly and uniformly choose poly(n; d) points
a i from F n and query f at a i , and receive f(a i ). If for all the points a i , f is zero then with high
This theorem implies
Theorem 3. The class MULF (n; k; t; d) where d ! cjF j for some constant c is learnable in
randomized polynomial time (in n, d and t) from membership queries if
Proof of Theorem 2 Upper Bound. Let OE(n; k; d) the maximal possible number of roots
of a multivariate polynomial in MUL F (n; k; ?; d). We will show the following facts
1. OE(n; k; d) - jF j n\Gammak OE(k; k; d), and
2. OE(k; k; d) - jF
3. OE(1;
Both facts implies that if f 6j 0, when we randomly uniformly choose an assignment a 2 F n , we
have
Pr a
[f(a)
For d - cjF j we have that this probability is bounded by 1
poly(n;d;t) . Therefore the expected
running time to detect that f is not 0 is poly(n; d; t).
It remain to prove conditions (1) and (2). To prove (1) let f 2 MUL F (n; k; ?; d) with maximal
number of roots. Let m be a term in f with a maximal number of variables. Suppose, without
loss of generality,
k . For any substitution a of the variables x
the term m will stay alive in the projection because it is maximal in f .
Since g has at most OE(k; k; d) roots the result (1) follows.
The proof of (2) is similar to the proof of Schwartz [Sch80] and Zippel [Zip79]. Let f 2
MUL F (k; k; ?; d). Write f as polynomial in F [x
Let t be the number of roots of f d . Since f d d) we have
For assignments a for x we have f d (a) 6= 0. For those assignments we get a
polynomial in x 1 of degree d that has at most d roots for x 1 . For t assignments a for x
we have f d is zero and then the possible values of x 1 (to get a root for f) is bounded by jF j.
This implies
The theorem follows by induction on k. 2
Proof of Theorem 2 Lower Bound Let A be a randomized algorithm that zero tests
asks membership queries to f and if f 6j 0 it returns with
probability at least 2=3 the answer "NO". If all the membership queries in the algorithm returns
0 the algorithm returns the answer "YES" indicating that f j 0.
We run the algorithm for f j 0. Let D be the distributions that the
membership assignments a a l are chosen to zero test f . Notice that if all membership
queries answers are 0 while running the algorithm for f j 0 it would again choose membership
queries according to the distributions D l . Now randomly and uniformly choose fl i;j 2 F ,
Y
d
Y
otherwise. Note that for
any input a we have that
Therefore
This shows that there exists f ? 6j 0 such that running algorithm A for f ? it will answer the
wrong answer "YES" with probability more than 2=3. This is a contradiction. 2



--R

Machine Learning
The probabilistic method.
A deterministic algorithm for sparse multivariate polynomial interpolation
Exact learning of boolean functions via the monotone theory.
A Note on Learning Multivariate Polynomials under the Uniform Distri- bution
On the applications of multiplicity automata in learning.
Learning sat-k-DNF formulas from membership queries
Learning behaviors of automata from multiplicity and equivalence queries.
On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
On Learning DNF and related circuit classes from helpfull and not-so-helpful teachers
On using the Fourier transform to learn disjoint DNF.
Learning decision trees using the Fourier spectrum.
Randomized interpolation and approximation of sparse polynomials.
A polynomial time learning algorithm for recognizable series.
Interpolation and approximation of sparse multivariate polynomials over GF(2).
Fast probabilistic algorithms for verification of polynomial identities.
Learning sparse multivariate polynomial over a field with queries and counterexamples.
A theory of the learnable.
Probabilistic algorithms for sparce polynomials.
Interpolating polynomials from their values.
--TR

--CTR
Homin K. Lee , Rocco A. Servedio , Andrew Wan, DNF are teachable in the average case, Machine Learning, v.69 n.2-3, p.79-96, December  2007
decision tree learning;multivariate polynomial;learning interpolation