Learning functions represented as multiplicity automata.
We study the learnability of multiplicity automata in Angluin's exact learning model, and we investigate its applications. Our starting point is a known theorem from automata theory relating the number of states in a minimal multiplicity automaton for a function to the rank of its Hankel matrix. With this theorem in hand, we present a new simple algorithm for learning multiplicity automata with improved time and query complexity, and we prove the learnability of various concept classes. These include (among others): -The class of disjoint DNF, and more generally -The class of polynomials over finite fields. -The class of bounded-degree polynomials over infinite fields. -The class of XOR of terms. -Certain classes of boxes in high dimensions. In addition, we obtain the best query complexity for several classes known to be learnable by other methods such as decision trees and polynomials over GF(2). While multiplicity automata are shown to be useful to prove the learnability of some subclasses of DNF formulae and various other classes, we study the limitations of this method. We prove that this method cannot be used to resolve the learnability of some other open problems such as the learnability of general DNF formulas or even k-term DNF for These results are proven by exhibiting functions in the above classes that require multiplicity automata    with super-polynomial number of states.
Introduction
The exact learning model was introduced by Angluin [5] and since then attracted a lot of
attention. In particular, the following classes were shown to be learnable in this model:
deterministic automata [4], various types of DNF formulae [1, 2, 3, 6, 16, 17, 18, 20, 29,
33] and multi-linear polynomials over GF(2) [44]. Learnability in this model also implies
learnability in the "PAC" model with membership queries [46, 5].
One of the classes that was shown to be learnable in this model is the class of multiplicity
automata [12] 1 and [40]. Multiplicity automata are essentially nondeterministic automata
with weights from a field K on the edges. Such an automaton computes a function as follows:
For every path in the automaton assign a weight which is the product of the weights on the
edges of this path. The function computed by the automaton is essentially the sum of the
weights of the paths consistent with the input string (this sum is a value in K). 2 Multiplicity
automata are a generalization of deterministic automata, and the algorithms that learn this
class [12, 13, 40] are generalizations of Angluin's algorithm for deterministic automata [4].
We use an algebraic approach for learning multiplicity automata, similar to [40]. This
approach is based on a fundamental theorem in the theory of multiplicity automata. The
theorem relates the size of a smallest automaton for a function f to the rank (over K) of
the so-called Hankel matrix of f [22, 26] (see also [25, 15] for background on multiplicity
1 A full description of this work appears in [13]
These automata are known in the literature under various names. In this paper we refer to them as
multiplicity automata. The functions computed by these automata are usually referred to as recognizable
series.
automata). Using this theorem, and ideas from the algorithm of [42] (for learning deterministic
automata), we develop a new algorithm for learning multiplicity automata which
is more efficient than the algorithms of [12, 13, 40]. In particular we give a more refined
analysis for the complexity of our algorithm when learning functions f with finite domain.
A different algorithm with similar complexity to ours was found by [21]. 3
In this work we show that the learnability of multiplicity automata implies the learnability
of many other important classes of functions. 4 First, it is shown that the learnability of
multiplicity automata implies the learnability of the class of Satisfy-s DNF formulae, for
in which each assignment satisfies at most s terms). This
class includes as a special case the class of disjoint DNF which by itself includes the class
of decision trees. These results improve over previous results of [18, 2, 16]. More generally,
we consider boxes over a discrete domain of points (i.e., Such boxes were
considered in many works (e.g., [37, 38, 23, 7, 27, 31, 39]). We prove the learnability of any
union of O(log n) boxes in time poly(n; '), and the learnability of any union of t disjoint boxes
(and more generality, any t boxes such that each point is contained in at most
of them) in time poly(n; t; '). 5 The special case of these results where implies the
learnability of the corresponding classes of DNF formulae.
We further show the learnability of the class of XOR of terms, which is an open problem
in [44], the class of polynomials over finite fields, which is an open problem in [44, 19], and the
class of bounded-degree polynomials over infinite fields (as well as other classes of functions
over finite and infinite fields). We also prove the learnability of a certain class of decision
trees whose learnability is an open problem in [18].
While multiplicity automata are proved to be useful to solve many open problems regarding
the learnability of DNF formulae and other classes of polynomials and decision trees,
we study the limitations of this method. We prove that this method cannot be used to
resolve the learnability of some other open problems such as the learnability of general DNF
formulae or even k-term DNF for
(these results are tight in the sense that O(log n)-term DNF formulae and satisfy-O(1) DNF
are learnable using multiplicity automata). These impossibility results are proven
by exhibiting functions in the above classes that require multiplicity automata with super-polynomial
number of states. For proving these results we use, again, the relation between
multiplicity automata and Hankel matrices.
3 In fact, [21] show that the algorithm can be generalized to K which is not necessarily a field but rather
a certain type of ring.
In [33] it is shown how the learnability of deterministic automata can be used to learn certain (much
more restricted) classes of functions.
5 In [9], using additional machinery, the dependency on ' was improved.
Organization: In Section 2 we present some background on multiplicity automata, as
well as the definition of the learning model. In Section 3 we present a learning algorithm
for multiplicity automata. In Section 4 we present applications of the algorithm for learning
various classes of functions. Finally, in Section 5, we study the limitations of this method.
Background
2.1 Multiplicity Automata
In this section we present some definitions and a basic result concerning multiplicity au-
tomata. Let K be a field, \Sigma be an alphabet, and f : \Sigma   ! K be a function. Associate with f
an infinite matrix F each of its rows is indexed by a string x 2 \Sigma   and each of its columns is
indexed by a string y 2 \Sigma   . The (x; y) entry of F contains the value f(xffiy), where ffi denotes
concatenation. (In the automata literature such a function f is often referred to as a formal
series and F as its Hankel Matrix.) We use F x to denote the x-th row of F . The (x; y) entry
of F may be therefore denoted as F x (y) and as F x;y . The same notation is adapted to other
matrices used in the sequel.
Next we define the automaton representation (over the field K) of functions. An automaton
A of size r consists of j\Sigmaj matrices f- oe : oe 2 \Sigmag each of which is an r \Theta r matrix of
elements from K and an r-tuple . The automaton A defines a function
First, we associate with every string in \Sigma   an r \Theta r matrix over K by
defining -(ffl) 4
ID, where ID denotes the identity matrix 6 , and for a string
let -(w)
(a simple but useful property of - is that
denotes the first row of the matrix -(w)). In words,
A is an automaton with r states where the transition from state q i to state q j with letter
oe has weight [- oe ] i;j . The weight of a path whose last state is q ' is the product of weights
along the path multiplied by fl ' , and the function computed on a string w is just the sum of
weights over all paths corresponding to w.
The following is a fundamental theorem from the theory of formal series. It relates the
size of the minimal automaton for f to the rank of F [22, 26].
Theorem 2.1 Let f : \Sigma   ! K and let F be the corresponding Hankel matrix. Then, the
size r of the smallest automaton A such that fA j f satisfies (over the field K).
Although this theorem is very basic, we provide its proof here as it sheds light on the
way the algorithm of Section 3 works.
6 That is, a matrix with 1's on the main diagonal and 0's elsewhere.
Direction I: Given an automaton A for f of size r, we prove that rank(F ) - r. Define
two matrices: R whose rows are indexed by \Sigma   and its columns are indexed by
C whose columns are indexed by \Sigma   and its rows are indexed by r. The (x; i) entry
of R contains the value [-(x)] 1;i and the (i; y) entry of C contains the value [-(y)] i \Delta ~fl . We
show that This follows from the following sequence of simple equalities:
r
where C y denotes the y-th column of C. Obviously the rank of both R and C is bounded by
r. By linear algebra, rank(F ) is at most minfrank(R); rank(C)g and therefore rank(F
as needed.
Direction II: Given a function f such that the corresponding matrix F has rank r, we show
how to construct an automaton A of size r that computes this function. Let F x
be r independent rows of F (i.e., a basis) corresponding to strings x To
define A, we first define Next, for every oe, define the i-th row of the
matrix - oe as the (unique) coefficients of the row F x i ffioe when expressed as a linear combination
of F x 1
That is,
r
We will prove, by induction on jwj (the length of the string w), that [-(w)] i
for all i. It follows that fA (as we choose x
The induction base is ffl). In this case we have
needed. For the induction step using Equation (1) we
r
then by induction hypothesis this equals
r
as needed.
2.2 The Learning Model
The learning model we use is the exact learning model [5]: Let f be a target function.
A learning algorithm may propose, in each step, a hypothesis function h by making an
equivalence query (EQ) to an oracle. If h is logically equivalent to f then the answer to
the query is YES and the learning algorithm succeeds and halts. Otherwise, the answer to
the equivalence query is NO and the algorithm receives a counterexample - an assignment
z such that f(z) 6= h(z). The learning algorithm may also query an oracle for the value
of the function f on a particular assignment z by making a membership query (MQ) on z.
The response to such a query is the value f(z). 7 We say that the learner learns a class of
functions C, if for every function f 2 C the learner outputs a hypothesis h that is logically
equivalent to f and does so in time polynomial in the "size" of a shortest representation of
f .
3 The Algorithm
In this section we describe an exact learning algorithm for multiplicity automata. The
"size" parameter in the case of multiplicity automata is the number of states in a minimal
automaton for f . The algorithm will be efficient in this number and the length of the longest
counterexample provided to it.
K be the target function. All algebraic operations in the algorithm are done
in the field K. 8 The algorithm learns a function f using its Hankel matrix representation,
F . The difficulty is that F is infinite (and is very large even when restricting the inputs to
some length n). However, Theorem 2.1 (Direction II) implies that it is sufficient to maintain
independent rows from F ; in fact, r \Theta r submatrix of F of full rank
suffices. Therefore, the learning algorithm can be viewed as a search for appropriate r rows
and r columns.
The algorithm works in iterations. At the beginning of the '-th iteration, the algorithm
holds a set of rows X ae \Sigma   and a set of columns Y ae \Sigma
fy
F z denote the restriction of the row F z to the ' coordinates in Y , i.e.
F z
Note that given z and Y the vector b
F z is computed using
queries. It will hold that b
are ' linearly independent vectors.
Using these vectors the algorithm constructs a hypothesis h, in a manner similar to the proof
of Direction II of Theorem 2.1, and asks an equivalence query. A counterexample to h leads
to adding a new element to each of X and Y in a way that preserves the above properties.
7 If f is boolean this is the standard membership query.
8 We assume that every arithmetic operation in the field takes one time unit.
This immediately implies that the number of iterations is bounded by r. We assume without
loss of generality that f(ffl) 6= 0. 9 The algorithm works as follows:
1. X / fx
2. Define a hypothesis h (following Direction II of Theorem 2.1):
)). For every oe, define a matrix b
- oe by letting its i-th row
be the coefficients of the vector b
expressed as a linear combination of the
vectors b
(such coefficients exist as b
are ' independent '-tuples).
That is, b
For define an ' \Theta ' matrix b
-(w) as follows: Let b
ID and for a string
. Finally, h is defined as
3. Ask an equivalence query EQ(h).
If the answer is YES halt with output h.
Otherwise the answer is NO and z is a counterexample.
Find (using MQs for f) a string wffioe which is a prefix of z such that:
(a) b
but
(b) there exists y 2 Y such that
Fwffioe (y) 6=
GO TO 2.
The following two claims are used in the proof of correctness. They show that in every
iteration of the algorithm, a prefix as required in Step 3 is found, and that as a result the
number of independent rows that we have grows by 1.
3.1 Let z be a counterexample to h found in Step 3 (i.e., f(z) 6= h(z)). Then, there
exists a prefix wffioe satisfying (a) and (b).
Proof: Assume towards a contradiction that no prefix satisfies both (a) and (b). We prove
(by induction on the length) that, for every prefix w of z, Condition (a) is satisfied. That is,
9 To check the value of f(ffl) we ask a membership query. If then we learn f 0 which is identical
to f except that at ffl it gets some value different than 0. Note that the matrix F 0 is identical to F in all
entries except one and so the rank of F 0 differs from the rank of F by at most 1. The only change this
makes on the algorithm is that before asking EQ we modify the hypothesis h so that its value in ffl will be
Alternatively, we can find a string z such that f(z) 6= 0 (by asking EQ(0)) and start the algorithm with
which gives a 2 \Theta 2 matrix of full rank.
By the proof of Theorem 2.1, it follows that if . However, we do not need this fact for
analyzing the algorithm, and the algorithm does not know r in advance.
. The induction base is trivial since b
ffl). For the
induction step consider a prefix wffioe. By the induction hypothesis, b
which implies (by the assumption that no prefix satisfies both (a) and (b)) that (b) is not
satisfied with respect to the prefix wffioe. That is, b
. By the
definition of b
- and by the definition of matrix multiplication
All together, b
which completes the proof of the induction.
Now, by the induction claim, we get that b
In particular, b
F z
However, the left-hand side of this equality is just f(z)
while the right-hand side is h(z). Thus, we get which is a contradiction (since
z is a counterexample).
3.2 Whenever Step 2 starts the vectors b
(defined by the current X and
Y ) are linearly independent.
Proof: The proof is by induction. In the first time that Step 2 starts ffflg. By
the assumption that f(ffl) 6= 0, we have a single vector b
F ffl which is not a zero vector, hence
the claim holds.
For the induction, assume that the claim holds when Step 2 starts and show that it also
holds when Step 3 ends (note that in Step 3 a new vector b
Fw is added and that all vectors have
a new coordinate corresponding to oe ffiy). By the induction hypothesis, when Step 2 starts,
F x ' are ' linearly independent '-tuples. In particular this implies that when Step 2
starts b
Fw has a unique representation as a linear combination of b
. Since w satisfies
(a) this linear combination is given by b
remain linearly independent (with respect to the new Y ). However, at this time,
Fw becomes linearly independent of b
(with respect to the new Y ). Otherwise,
the linear combination must be given by b
However, as wffioe satisfies
(b) we get that b
Fw (oe
Fwffioe (y) 6=
(oe ffiy) which
eliminates this linear combination. (Note that oe ffiy was added to Y so b
F is defined in all
the coordinates which we refer to.) To conclude, when Step 3 ends b
F x '+1 =w are
linearly independent.
We summarize the analysis of the algorithm by the following theorem. Let m denote the
size of the longest counterexample z obtained during the execution of the algorithm. Denote
by the complexity of multiplying two r \Theta r matrices.
Theorem 3.3 Let K be a field, and f : \Sigma   ! K be a function such that
K). Then, f is learnable by the above algorithm in time O(j\Sigmaj using r
equivalence queries and O((j\Sigmaj queries.
Proof: Claim 3.1 guarantees that the algorithm always proceeds. Since the algorithm
halts only if EQ(h) returns YES the correctness follows.
As for the complexity, Claim 3.2 implies that the number of iterations, and therefore the
number of equivalence queries, is at most r (in fact, Theorem 2.1 implies that the number
of iterations is exactly r).
The number of MQs asked in Step 2 over the whole algorithm is (j\Sigmaj since for
every x 2 X and y 2 Y we need to ask for the value of f(xy) and the values f(xoey), for
all oe 2 \Sigma. To analyze the number of MQs asked in Step 3, we first need to specify the
way that the appropriate prefix is found. The naive way is to go over all prefixes of z until
finding one satisfying (a) and (b). A more efficient search can be based upon the following
generalization of Claim 3.1: suppose that for some v, a prefix of z, Condition (a) holds.
That is, b
F x i . Then, there exists wffioe a prefix of z that extends v and
satisfies (a) and (b) (the proof is identical to the proof of Claim 3.1 except that for the base
of induction we use v instead of ffl). Using the generalized claim, the desired prefix wffioe can
be found using a binary search in log jzj - log m steps as follows: at the middle prefix v
check whether (a) holds. If so make v the left border for the search. If (a) does not hold for
then by Equation (2) condition (b) holds for v and so v becomes the right border
for the search. In each step of the binary search 2' - 2r membership queries are asked (note
that the values of b
are known from Step 2). All together the number of MQs
asked during the execution of the algorithm is O((log m+ j\Sigmaj)r 2 ).
As for the running time, to compute each of the matrices b
- oe observe that the matrix whose
rows are b
F x ' ffioe is the product of b
- oe with the matrix whose rows are b
Therefore, finding b
- oe can be done with one matrix inversion (whose cost is also O(M(r)))
and one matrix multiplication. Hence the complexity of Step 2 is O(j\Sigmaj \Delta M(r)). In Step 3
the difficult part is to compute the value of b
-(w) for prefixes of z. A simple way to do
it is by computing m matrix multiplications for each such z. A better way of doing the
computation of Step 3 is by observing that all we need to compute is actually the first row
of the matrix b
-wm . The first row of this matrix can simply be written as
-(w). Thus, to compute this row, we first compute (1;
then multiply the result by b
and so on. Therefore, this computation can be done by m
vector-matrix multiplications, which requires O(m \Delta r 2 ) time. All together, the running time
is at most O(j\Sigmaj
The complexity of our algorithm should be compared to the complexity of the algorithm
of [12, 13] which uses r equivalence queries, O(j\Sigmajmr 2 ) membership queries, and runs in time
The algorithm of [40] uses r+1 equivalence queries, O((j\Sigmaj +m)r 2 ) membership
queries, and runs in time O((j\Sigmaj +m)r 4 ).
3.1 The Case of Functions
In many cases of interest the domain of the target function f is not \Sigma   but rather \Sigma n for
some value n. We view f as a function on \Sigma   whose value is 0 for all strings whose length is
different than n. We show that in this case the complexity analysis of our algorithm can be
further improved. The reason is that in this case the matrix F has a simpler structure. Each
row and column is indexed by a string whose length is at most n (alternatively, rows and
columns corresponding to longer strings contain only 0 entries). Moreover, for any string x
of length 0 - d - n the only non-zero entries in the row F x correspond to y's of length
Denote by F d the submatrix of F whose rows are strings in \Sigma d and its columns are strings
in \Sigma n\Gammad (see Fig. 1). Observe that by the structure of F ,
Now, to learn such a function f we use the above algorithm but ask membership queries
only on strings of length exactly n (for all other strings we return 0 without actually asking
the query) and for the equivalence queries we view the hypothesis h as restricted to \Sigma n . The
length of counterexamples, in this case, is always n and so
Looking closely at what the algorithm does it follows that since b
F is a submatrix of F , not
only b
F x ' are always independent vectors (and so ' - rank(F )) but that for every d,
the number of x i 's in X whose length is d is bounded by rank(F d ). We denote r d
and r max
d=0 r d . The number of equivalence queries remains r as before. The number
of membership queries however becomes smaller due to the fact that many entries of F are
known to be 0. In Step 2, over the whole execution, we ask for every x 2 X of length d
and every y 2 Y of length one MQ on f(xy) and for every y 2 Y of length
and every oe 2 \Sigma we ask MQ on f(xoey). All together, in Step 2 the algorithm asks for
every x at most r queries and total of O(r \Delta r max j\Sigmaj) membership
queries. In Step 3, in each of the r iterations and each of the log n search steps we ask
at most 2r max membership queries (again, because most of the entries in each row contain
0's). All together O(rr max log n) membership queries in Step 3 and over the whole algorithm
O(r log n)).
F d
F

Figure

1: The Hankel matrix F
As for the running time, note that the matrices b
- oe also have a very special structure:
the only entries (i; j) which are not 0 are those corresponding to vectors x
that jx multiplication of such matrices can be done in
Therefore, each invocation of Step 2 requires time of O(j\Sigmajn \Delta M(r max )).
Similarly, in [ b
-(w)] 1 the only entries which are not 0 are those corresponding to strings
by a column of b
units. Furthermore, we need to multiply only for at most r max columns, for the non-zero
coordinates in [ b
Therefore, Step 3 takes at most nr 2
for each counterexample z.
All together, the running time is at most O(nrr 2
Corollary 3.4 Let K be a field, and f : \Sigma n ! K such that
d=0 rank(F d ) (where rank is taken over K). Then, f is learnable by the above algorithm in
using O(r) equivalence queries and O((j\Sigmaj+log n)r \Delta r
queries.
4 Positive Results
In this section we show the learnability of various classes of functions by our algorithm.
This is done by proving that for every function f in the class in question, the corresponding
Hankel matrix F has low rank. By Theorem 3.3 this implies the learnability of the class by
our algorithm.
First, we observe that it is possible to associate a multiplicity automaton with every non-deterministic
automaton, such that on every string w the multiplicity automaton "counts"
the number of accepting paths of the nondeterministic automaton on w. To see this, define
the (i; j) entry of the matrix - oe as 1 if the given automaton can move, on letter oe, from
state i to state j (otherwise, this entry is 0). In addition, define fl i to be 1 if i is an accepting
state and 0 otherwise. Thus, if the automaton is deterministic or unambiguous 11 then the
associated multiplicity automaton defines the characteristic function of the language. By
[33] the class of deterministic automata contains the class of O(log n)-term DNF and in fact
the class of all boolean functions over O(log n)-terms. Hence, all these classes can be learned
by our algorithm. We note that if general nondeterministic automata can be learned then
this implies the learnability of DNF.
4.1 Classes of Polynomials
Our first results use the learnability of multiplicity automata to learn various classes of
multivariate polynomials. We start with the following claim:
Theorem 4.1 Let p i;j (z arbitrary functions of a single variable (1
K be defined by
Finally, let f : \Sigma n ! K be defined
by
F be the Hankel matrix corresponding to f , and F d the sub-matrices
defined in Section 3.1. Then, for every 0 - d - n, t.
Proof: Recall the definition of F d . Every string z 2 \Sigma n is viewed as partitioned into two
substrings Every row of F d is indexed by
hence it can be written as a function
F d
x
Y
Y
Now, for every x and i, the term
just a constant ff i;x 2 K. This means, that
every function F d
x
(y) is a linear combination of the t functions
for each value of i). This implies that rank(F d ) - t, as needed.
Corollary 4.2 The class of functions that can be expressed as functions over GF(p) with t
summands, where each summand T i is a product of the form p i;1
are arbitrary functions) is learnable in time poly(n; t; p).
11 A nondeterministic automata is unambiguous if for every w 2 \Sigma   there is at most one accepting path.
The above corollary implies as a special case the learnability of polynomials over GF(p).
This extends the result of [44] from multi-linear polynomials to arbitrary polynomials. Our
algorithm (see Corollary 3.4), for polynomials with n variables and t terms, uses O(nt)
equivalence queries and O(t 2 n log n) membership queries. The special case of the above class
- the class of multi-linear polynomials over GF(2) - was known to be learnable before [44].
Their algorithm uses O(nt) equivalence queries and O(t 3 n) membership queries (which is
worse than ours for "most" values of t).
Corollary 4.2 discusses the learnability of a certain class of functions (that includes the
class of polynomials) over finite fields (the complexity of the algorithm depends on the size
of the field). The following theorem extends this result to infinite fields, assuming that the
functions p i;j are bounded-degree polynomials. It also improves the complexity for learning
polynomials over finite fields, when the degree of the polynomials is significantly smaller
than the size of the field.
Theorem 4.3 The class of functions over a field K that can be expressed as t summands,
where each summand T i is of the form p i;1 are polynomials
of degree at most k, is learnable in time poly(n; t; k). Furthermore, if jKj - nk
class is learnable from membership queries only in time poly(n; t; (with small probability
of error).
Proof: We show that although the field K may be very large, we can run the algorithm
using an alphabet of k elements from the field, g. For this, all we
need to show is how the queries are asked and answered. The membership queries are asked
by the algorithm, so it will only present queries which are taken from the domain \Sigma n . For
the equivalence queries we do the following: instead of representing the hypothesis with j\Sigmaj
matrices b
-(oe k+1 ) we will represent it with a single matrix H(x) each of its entries
is a degree k polynomial (over K), such that for every oe 2 \Sigma,
-(oe). (To find this
use interpolation in each of its entries. Also, in this terminology, for
the hypothesis is it is easy to see that both the target
function and the hypothesis are degree-k polynomials in each of the n variables. Therefore,
given a counterexample w 2 K n , we can modify it to be in \Sigma n as follows: in the i-th step
fix z doing so, both the hypothesis and the target function become
degree k polynomials in the variable z i . Hence, there exists oe 2 \Sigma, for which these two
polynomials disagree. We set w We end up with a new counterexample w 2 \Sigma n , as
desired.
Assume that K contains at least nk be a
subset of K. By Schwartz Lemma [45], two different polynomials in z
(in each variable) can agree on at most knjLj n\Gamma1 assignments in L n . Therefore, by picking
at random poly(n; random elements in L n we can obtain, with very high probability, a
counterexample to our hypothesis (if such a counterexample exists). We then proceed as
before (i.e., modify the counterexample to the domain \Sigma n etc.)
An algorithm which learns multivariate polynomials using only membership queries is
called an interpolation algorithm (e.g. [10, 28, 47, 24, 43, 30]; for more background and
references see [48]). In [10] it is shown how to interpolate polynomials over infinite fields
using only 2t membership queries. In [47] it is shown how to interpolate polynomials over
finite fields
elements. If the number of elements in the field is less than
k then every efficient algorithm must use equivalence queries [24, 43]. In Theorem 4.3 the
polynomials we interpolate have a more general form than in standard interpolation and we
only require that the number of elements in the field is at least kn + 1.
4.2 Classes of Boxes
In this section we consider unions of n-dimensional boxes in ['] n (where ['] denotes the set
Formally, a box in ['] n is defined by two corners (a
(in
We view such a box as a boolean function that gives 1 for every point in ['] n which is inside
the box and 0 to each point outside the box. We start with a more general claim.
Theorem 4.4 Let p i;j (z arbitrary functions of a single variable (1
be defined by
Assume that there is no point
which satisfies more than s functions g i . Finally, let f : \Sigma n ! f0; 1g be defined by
F be the Hankel matrix corresponding to f . Then, for every field K and for
every
Proof: The function f can be expressed as:
Y
jSj=t
jSj=s
where the last equality is by the assumption that no point satisfies more than s functions.
Note that, every function of the form
i2S g i is a product of at most n functions, each one
is a function of a single variable. Therefore, applying Theorem 4.1 complete the proof.
Corollary 4.5 The class of unions of disjoint boxes can be learned in time poly(n; t; ') (where
t is the number of boxes in the target function). The class of unions of O(log n) boxes can
be learned in time poly(n; ').
Proof: Let B be any box and denote the two corners of B by (a
functions (of a single 1g to be 1 if a j - z
be defined by
belongs to the box B. Therefore, Corollary 3.4 and Theorem 4.4 imply this corollary.
4.3 Classes of DNF formulae
In this section we present several results for classes of DNF formulae and some related classes.
We first consider the following special case of Corollary 4.2 that solves an open problem of
[44]:
Corollary 4.6 The class of functions that can be expressed as exclusive-OR of t (not necessarily
monotone) monomials is learnable in time poly(n; t).
While Corollary 4.6 does not refer to a subclass of DNF, it already implies the learnability
of Disjoint (i.e., Satisfy-1) DNF. Also, since DNF is a special case of union of boxes (with
2), we can get the learnability of disjoint DNF from Corollary 4.5. Next we discuss positive
results for Satisfy-s DNF with larger values of s. The following two important corollaries
follow from Theorem 4.4. Note that Theorem 4.4 holds in any field. For convenience (and
efficiency), we will use
Corollary 4.7 The class of Satisfy-s DNF formulae, for
Corollary 4.8 The class of Satisfy-s, t-term DNF formulae is learnable for the following
choices of s and t: (1) log log n); (3)
log log n ) and
4.4 Classes of Decision Trees
As mentioned above, our algorithm efficiently learns the class of Disjoint DNF formulae.
This in particular includes the class of Decision-trees. By using our algorithm, decision
trees of size t on n variables are learnable using O(tn) equivalence queries and O(t 2 n log n)
membership queries. This is better than the best known algorithm for decision trees [18]
(which uses O(t 2 ) equivalence queries and O(t 2 In what follows we
consider more general classes of decision trees.
Corollary 4.9 Consider the class of decision trees that compute functions f
GF(p) as follows: each node v contains a query of the form "x i 2 S v ?", for some S v ' GF(p).
then the computation proceeds to the left child of v and if x
the computation
proceeds to the right child. Each leaf ' of the tree is marked by a value
is the output on all assignments which reach this leaf. Then, this class is learnable in time
poly(n; jLj; p), where L is the set of all leaves.
Proof: Each such tree can be written as
' is a function
whose value is 1 if the assignment reaches the leaf ' and 0 otherwise (note that
in a decision tree each assignment reaches a single leaf). Consider a specific leaf '. The
assignments that reach ' can be expressed by n sets S ';n such that the assignment
reaches the leaf ' if and only if x j 2 S ';j for all j. Define p ';j to be 1 if
. By Corollary 4.2 the result follows.
The above result implies as a special case the learnability of decision trees with "greater-
than" queries in the nodes. This is an open problem of [18]. Note that every decision tree
with "greater-than" queries that computes a boolean function can be expressed as the union
of disjoint boxes. Hence, this case can also be derived from Corollary 4.5.
The next theorem will be used to learn more classes of decision trees.
Theorem 4.10 Let
defined
F be the Hankel matrix corresponding to f , and G i be the Hankel
matrix corresponding to g i . Then, rank(F d
Proof: For two matrices A and B of the same dimension, the Hadamard product
A fi B is defined by C . It is well known that rank(C) - rank(A) \Delta rank(B).
Note that F
hence the theorem follows.
This theorem has some interesting applications, such as:
Corollary 4.11 Let C be the class of functions that can be expressed in the following way:
arbitrary functions of a single variable (1
be defined by \Sigma n
Finally,
be defined by
learnable in time poly(n; j\Sigmaj).
Corollary 4.12 Consider the class of decision trees of depth s, where the query at each node
v is a boolean function f v with r (as defined in Section 3.1) such that (t+1)
Then, this class is learnable in time poly(n; j\Sigmaj).
Proof: For each leaf ' we write a function g ' as a product of s functions as follows: for
each node v along the path to ' if we use the edge labeled 1 we take f v to the product
while if we use the edge labeled 0 we take to the product (note that the value r max
corresponding to (1 \Gamma f v ) is at most t 1). By Theorem 4.10, if G ' is the Hankel matrix
corresponding to g ' then rank(G d
' ) is at most (t+1) s . As
it follows that rank(F d )
is at most 2 s (this is because jLj - 2 s and rank(B)). The
corollary follows.
The above class contain for example all the decision trees of depth O(log n) that contain
in each node a term or XOR of a subset of variables (as defined in [34]).
5 Negative Results
The purpose of this section is to study some limitation of the learnability via the automaton
representation. We show that our algorithm, as well as any algorithm whose complexity is
polynomial in the size of the automaton (such as the algorithms in [12, 13, 40]), does not
efficiently learn several important classes of functions. More precisely, we show that these
classes contain functions f that have no "small" automaton. By Theorem 2.1, it is enough
to prove that the rank of the corresponding Hankel matrix F is "large" over every field K.
We define a function f exists
such that z 1. The function f n;k can be expressed as a DNF formula by:
Note that this formula is read-once, monotone and has k terms.
First, observe that the rank of the Hankel matrix corresponding to f n;k equals the rank
of F , the Hankel matrix corresponding to f 2k;k . It is also clear that rank(F ) - rank(F k ).
We now prove that rank(F k 1. To do so, we consider the complement matrix D k
(obtained from F k by switching 0's and 1's), and prove by induction on k that rank(D k
Note that
This implies that rank(D 1
It follows that rank(F k (where J is the all-1 matrix). 12
Using the functions f n;k we can now prove the main theorem of this section:
In fact, the function f 0
z n\Gammak+1 has similar properties to f n;k and can be shown
to have
rank\Omega\Gamman k \Delta n) hence slightly improving the results below.
Theorem 5.1 The following classes are not learnable as multiplicity automata (over any
field K):
1. DNF.
2. Monotone DNF.
3. 2-DNF.
4. Read-once DNF.
5. k-term DNF, for
6. Satisfy-s DNF, for
7. Read-j Satisfy-s DNF, for
n).
Some of these classes are known to be learnable by other methods (monotone DNF
[5], read-once DNF [6, 1, 41] and 2-DNF [46]), some are natural generalizations of classes
known to be learnable as automata (log n-term DNF [17, 18, 20, 33], and Satisfy-s DNF for
or by other methods (Read-j Satisfy-s for log log n) [16]), and
the learnability of some of the others is still an open problem.
Proof: Observe that f n;n=2 belongs to each of the classes DNF, Monotone DNF, 2-DNF,
Read-once DNF and that by the above argument every automaton for it has size 2 n=2 . This
shows
For every n), the function f n;k has exactly k-terms and every automaton for it
has size 2 n) which is super-polynomial. This proves 5.
For consider the function f n;s log n . Every automaton for it has size 2 s log
which is super-polynomial. We now show that the function f n;s log n has a small Satisfy-
s DNF representation. For this, partition the indices sets of log n
indices. For each set S there is a formula on 2 log n variables which is 1 iff there exists i 2 S
such that z 1. Moreover, there is such a formula which is Satisfy-1 (i.e., disjoint)
DNF, and it has n 2 terms (this is the standard DNF representation). The disjunction of
these s formulas gives a Satisfy-s DNF with sn 2 terms. This proves 6.
Finally, for
As before, the function
f n;k requires an automaton of super-polynomial size. On the other hand, by partitioning
the variables into s sets of log j variables as above (and observe that in the standard DNF
representation each variable appears 2 log this function is a Read-j Satisfy-s
DNF. This proves 7.
In what follows we wish to strengthen the previous negative results. The motivation is
that in the context of automata there is a fixed order on the characters of the string. However,
in general (and in particular for functions over \Sigma n ) there is no such "natural" order. Indeed,
there are important functions such as Disjoint DNF which are learnable as automata using
any order of the variables. On the other hand, there are functions for which certain orders
are much better than others. For example, the function f n;k requires automaton of size
exponential in k when the standard order is considered, but if instead we read the variables
in the order there is a small (even deterministic) automaton
for it (of size O(n)). As an additional example, every read-once formula has a "good" order
(the order of leaves in a tree representing the formula).
Our goal is to show that even if we had an oracle that could give us a "good" (not
necessarily the best) order of the variables (or if we could somehow learn such an order) then
still some of the above classes cannot be learned as automata. This is shown by exhibiting
a function that has no "small" automaton in every order of the variables. To show this,
we define a function n) as follows. Denote the input
variables for g n;k as w k. The function g n;k outputs
1 iff there exists t such that w
Intuitively, g n;k is similar to f n;k but instead of comparing the first k variables to the next k
variables we first "shift" the first k variables by t. 13
First, we show how to express g n;k as a DNF formula. For a fixed t, define a function
to be 1 iff ( ) holds. Observe that g n 0 ;k;t is isomorphic to f n 0 ;k and
so it is representable by a DNF formula (with k terms of size 2). Now, we write g
Therefore, g n;k can be written as a monotone, read-k, DNF of k 2 terms
each of size 3.
We now show that, for every order - on the variables, the rank of the matrix corresponding
to g n;k is large. For this, it is sufficient to prove that for some value t the rank of the matrix
corresponding to g n 0 ;k;t is large, since this is a submatrix of the matrix corresponding to g n;k
(to see this fix w As before, it is sufficient to prove that for
some t the rank of g 2k;k;t is large. The main technical issue is to choose the value of t. For this,
look at the order that - induces on z (ignoring w Look at the first
k indices in this order and assume, without loss of generality, that at least half of them are
from (hence out of the last k indices at least half are from
13 The rank method used to prove that every automaton for f n;k is "large" is similar to the rank method of
communication complexity. The technique we use next is also similar to methods used in variable partition
communication complexity. For background see, e.g., [36, 35].
Denote by A the set of indices from that appear among the first k indices
under the order -. Denote by B the set of indices i such that appears among the
last k indices under the order -. Both A and B are subsets of and by the
assumption, jAj; jBj - k=2. Define A Ag. We now show that for some t
the size of A t " B is \Omega\Gamma k). For this, write
Let t 0 be such that
" B has size jSj - k=4. Denote by G the matrix corresponding
to g 2k;k;t 0
. In particular let G 0 be the submatrix of G with rows that are all strings x of
length k (according to the order -) whose bits out of S are fixed to 0's and with columns
that are all strings y of length k whose bits which are not of the
are fixed to 0's. This matrix is the same matrix obtained in the proof for f k;k=2 whose rank
is therefore 2 k=2 \Gamma 1.
Corollary 5.2 The following classes are not learnable as automata (over any field K) even
if the best order is known:
1. DNF.
2. Monotone DNF.
3. 3-DNF.
4. k-term DNF, for
5. Satisfy-s DNF, for



--R

Exact learning of read-twice DNF formulas
Exact learning of read-k disjoint DNF and not-so-disjoint DNF
Learning k-term DNF formulas using queries and counterexamples
Learning regular sets from queries and counterexamples.
Machine Learning
Learning read-once formulas with queries

On the applications of multiplicity automata in learning.
Learning boxes in high dimension.
A deterministic algorithm for sparse multivariate polynomial interpolation.
Learning sat-k-DNF formulas from membership queries
Learning behaviors of automata from multiplicity and equivalence queries.
Learning behaviors of automata from multiplicity and equivalence queries.
Learning behaviors of automata from shortest coun- terexamples
Rational Series and Their Languages
On learning read-k-satisfy- j DNF
Fast learning of k-term DNF formulas with queries
Exact learning via the monotone theory.
A note on learning multivariate polynomials under the uniform distribu- tion
Simple learning algorithms using divide and conquer.
Learning matrix functions over rings.
Realization by stochastic finite automaton.

On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields

Matrices de Hankel.
Learning unions of boxes with membership and equivalence queries.
Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields.
Learning 2- DNF formulas and k- decision trees
Interpolation of sparse multivariate polynomials over large finite fields with applications.
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
An Introduction to Computational Learning Theory.
A simple algorithm for learning O(log n)-term DNF
Learning decision trees using the Fourier spectrum.
Communication Complexity.
VLSI theory.
On the complexity of learning from counterexamples.
Algorithms and lower bounds for on-line learning of geometrical concepts
Efficient learning with virtual threshold gates.
A polynomial time learning algorithm for recognizable series.

Inference of finite automata using homing sequences.
Interpolation and approximation of sparse multivariate polynomials over GF (2).
Learning sparse multivariate polynomials over a field with queries and counterexamples.
Fast probabilistic algorithms for verification of polynomial identities.
A theory of the learnable.
Interpolating polynomials from their values.
Efficient Polynomial Computation.
--TR
A theory of the learnable
Learning regular sets from queries and counterexamples
Rational series and their languages
A deterministic algorithm for sparse multivariate polynomial interpolation
Interpolating polynomials from their values
Introduction to algorithms
Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields
Interpolation and approximation of sparse multivariate polynomials over GF(2)
Learning 2u DNF formulas and <italic>ku</italic> decision trees
VLSI theory
On zero-testing and interpolation of <inline-equation> <f> k</f> </inline-equation>-sparse multivariate polynomials over finite fields
Exact learning of read-twice DNF formulas (extended abstract)
On-line learning of rectangles
Random DFA''s can be approximately learned from sparse uniform examples
Exact learning of read-<italic>k</italic> disjoint DNF and not-so-disjoint DNF
Learning read-once formulas with queries
C4.5: programs for machine learning
Learning decision trees using the Fourier spectrum
Cryptographic hardness of distribution-specific learning
On-line learning of rectangles in noisy environments
Cryptographic limitations on learning Boolean formulae and finite automata
Inference of finite automata using homing sequences
On learning Read-<italic>k</italic>-Satisfy-<italic>j</italic> DNF
Learning unions of boxes with membership and equivalence queries
Algorithms and Lower Bounds for On-Line Learning of Geometrical Concepts
An introduction to computational learning theory
Read-twice DNF formulas are properly learnable
Fast learning of <italic>k</italic>-term DNF formulas with queries
Exact learning Boolean functions via the monotone theory
A note on learning multivariate polynomials under the uniform distribution (extended abstract)
Learning sparse multivariate polynomials over a field with queries and counterexamples
Learning Sat-<italic>k</italic>-DNF formulas from membership queries
Learning Behaviors of Automata from Multiplicity and Equivalence Queries
Simple learning algorithms using divide and conquer
A simple algorithm for learning O (log <italic>n</italic>)-term DNF
Communication complexity
An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
The art of computer programming, volume 2 (3rd ed.)
Efficient learning with virtual threshold gates
Interpolation of sparse multivariate polynomials over large finite fields with applications
Fast Probabilistic Algorithms for Verification of Polynomial Identities
Automata, Languages, and Machines
Induction of Decision Trees
Queries and Concept Learning
Probabilistic algorithms for sparse polynomials
Learning behaviors of automata from shortest counterexamples
Simple learning algorithms for decision trees and multivariate polynomials
On the applications of multiplicity automata in learning

--CTR
Amir Shpilka, Interpolation of depth-3 arithmetic circuits with two multiplication gates, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA
Nader H. Bshouty , Lynn Burroughs, On the proper learning of axis-parallel concepts, The Journal of Machine Learning Research, 4, p.157-176, 12/1/2003
Lane A. Hemaspaandra, SIGACT News complexity theory column 32, ACM SIGACT News, v.32 n.2, June 2001
Ricard Gavald , Pascal Tesson , Denis Thrien, Learning expressions and programs over monoids, Information and Computation, v.204 n.2, p.177-209, February 2006
DNF;learning disjoint;multiplicity automata;computational learning;learning polynomials