Kao M.-Y. (ed.) Encyclopedia of Algorithms

Подождите немного. Документ загружается.

418 K Kinetic Data Structures

Kinetic Data Structures, Figure 2

Equivalent convex hull configurations (left and right), a proof that a; b; and c form the convex hull of S (center)

the failure time of a certiﬁcate can be computed as the next

largest root of an algebraic expression. An important as-

pect of kinetic data structures is their on-line character:

although the positions and motions (ﬂight plans) of the

objects are known at all times, they are not necessarily

known far in advance. In particular, any object can change

its ﬂight plan at any time. A good KDS should be able to

handle such changes in ﬂight plans eﬃciently.

A detailed introduction to kinetic data structures can

be found in Basch’s Ph. D. thesis [1] or in the surveys by

Guibas [3,4]. In the following the principles behind kinetic

data structures are illustrated by an easy example.

Consider a KDS that maintains the convex hull of a set

S of four points a; b; c; and d as depicted in Fig. 2.Asetof

four simple certiﬁcates is suﬃcient to certify that a; b; and

c form indeed the convex hull of S (see Fig. 2 center). This

implies, that the convex hull of S will not change under

any motion of the points that does not lead to a violation

of these certiﬁcates. To put it diﬀerently, if the points move

along trajectories that move them between the conﬁgura-

tions depicted in Fig. 2 without the point d ever appear-

ing on the convex hull, then the KDS in principle does not

have to process a single event.

Now consider a setting in which the points a; b; and

c are stationary and the point d moves along a linear tra-

jectory (Fig. 3 left). Here the KDS has exactly two events

to process. At time t

the certiﬁcate “d is to the left of bc”

failsasthepointd appears on the convex hull. In this easy

setting, only the failed certiﬁcate is replaced by “d is to the

right of bc” with failure time “never”, generally processing

an event would lead to the scheduling and descheduling of

several events from the event queue. Finally at time t

the

certiﬁcates “b is to the right of ad” fails as the point b ceases

Kinetic Data Structures, Figure 3

Certificate structure for points a; b; and c being stationary and

point d moving along a straight line

to be on the convex hull and is replaced by “b is to the left

of ad” with failure time “never.”

Kinetic data structures and their accompanying main-

tenance algorithms can be evaluated and compared with

respect to four desired characteristics.

Responsiveness. One of the most important performance

measures for a KDS is the time needed to update the

attribute and to repair the certiﬁcate set when a certiﬁ-

cate fails. A KDS is called responsive if this update time

is “small”, that is, polylogarithmic.

Compactness. A KDS is called compact if the number of

certiﬁcates is near-linear in the total number of objects.

Note that this is not necessarily the same as the amount

of storage the entire structure needs.

Locality. A KDS is called local if every object is involved

in only a small number of certiﬁcates (again, “small”

translates to polylogarithmic). This is important when-

ever an object changes its ﬂight plane, because one has

to recompute the failure times of all certiﬁcates this ob-

ject is involved in, and update the event queue accord-

ingly. Note that a local KDS is always compact, but that

the reverse is not necessarily true.

Eﬃciency. A certiﬁcate failure does not automatically im-

ply a change in the attribute that is being maintained, it

can also be an internal event, that is, a change in some

auxiliary structure that the KDS maintains. A KDS is

called eﬃcient if the worst-case number of events han-

dled by the data structure for a given motion is small

compared to the number of combinatorial changes of

the attribute (external events)thatmustbehandledfor

that motion.

Applications

The paper by Basch et al. [2] sparked a large amount

of research activities and over the last years kinetic data

structures have been used to solve various dynamic com-

putational geometry problems. A number of papers deal

foremost with the maintenance of discrete attributes for

sets of moving points, like the closest pair, width and di-

ameter, clusters, minimum spanning trees, or the con-

strained Delaunay triangulation. Motivated by ad hoc mo-

bile networks, there have also been a number of papers that

Knapsack K 419

show how to maintain the connected components in a set

of moving regions in the plane. Major research eﬀorts have

also been seen in the study of kinetic binary space parti-

tions (BSPs) and kinetic kd-trees for various objects. Fi-

nally, there are several papers that develop KDSs for colli-

sion detection in the plane and in three dimensions. A de-

tailed discussion and an extensive list of references can be

found in the survey by Guibas [4].

Cross References

 Fully Dynamic Minimum Spanning Trees

 Minimum Geometric Spanning Trees

Recommended Reading

1. Basch, J.: Kinetic Data Structures. Ph. D. thesis, Stanford Univer-

sity (1999)

2. Basch, J., Guibas, L., Hershberger, J.: Data structures for mobile

data.J.Algorithms31, 1–28 (1999)

3. Guibas, L.: Kinetic data structures: A state of the art report. In:

Proc. 3rd Workshop on Algorithmic Foundations of Robotics,

pp. 191–209 (1998)

4. Guibas, L.: Modeling Motion. In: Goodman, J., O’Rourke, J.: (eds),

Handbook of Discrete and Computational Geometry. CRC Press,

2nd ed. (2004)

Knapsack

1975; Ibarra, Kim

HANS KELLERER

Department of Computer Science, University of Graz,

Graz, Austria

Keywords and Synonyms

Approximation algorithm; Fully polynomial time approx-

imation scheme (FPTAS)

Problem Definition

For a given set of items N = f1;:::;ng with nonnegative

integer weights w

and proﬁts p

, j =1;:::;n, and a knap-

sack of capacity c,theknapsack problem (KP) is to se-

lect a subset of the items such that the total proﬁt of the

selected items is maximized and the corresponding total

weight does not exceed the knapsack capacity c.

Alternatively, a knapsack problem can be formulated

as a solution of the following linear integer programming

formulation:

(KP) maximize

j=1

(1)

subject to

j=1

 c ; (2)

2f0; 1g; j =1;:::;n : (3)

The knapsack problem is the simplest non-trivial inte-

ger programming model having binary variables, only

a single constraint and only positive coeﬃcients. A large

number of theoretical and practical papers has been pub-

lished on this problem and its extensions. An extensive

overview can be found in the books by Kellerer, Pferschy

and Pisinger [2] or Martello and Toth [7].

Adding the integrality condition (3) to the simple lin-

ear program (1)-(2) already puts (KP) into the class of

NP-hard problems. Thus, (KP) admits no polynomial

time algorithms unless

P = NPholds.

Therefore, this entry will focus on approximation al-

gorithms for (KP). A common method to judge the qual-

ity of an approximation algorithm is its worst-case perfor-

mance. For a given instance I deﬁne by z



(I)theoptimal

solution value of (KP) and by z

(I) the corresponding so-

lution value of a heuristic H.For" 2 [0; 1[ a heuristic H

is called a (1  ")–approximation algorithm for (KP) if for

any instance I

(I)  (1  ")z



(I)

holds. Given a parameter ",aheuristicH is called a fully

polynomial approximation scheme,oranFTPAS,ifH

is a (1  ")–approximation algorithm for (KP) for any

" 2 [0; 1[, and its running time is polynomial both in the

length of the encoded input n and 1/".TheﬁrstFTPASfor

(KP) was suggested by Ibarra and Kim [1] in 1975. It was

among the early FPTASes for discrete optimization prob-

lems. It will be described in detail in the following.

Key Results

(KP) can be solved in pseudopolynomial time by a sim-

ple dynamic programming algorithm. One possible vari-

ant is the so-called dynamic programming by proﬁts (DP-

Proﬁts). The main idea of DP-Proﬁts is to reach every pos-

sible total proﬁt value with a subset of items of minimal

total weight. Clearly, the highest total proﬁt value, which

can be reached by a subset of weight not greater than the

capacity c, will be an optimal solution.

Let y

(q) denote the minimal weight of a subset of

items from f1;:::; jgwith total proﬁt equal to q.Tobound

the length of every array y

an upper bound u on the opti-

mal solution value has to be computed. An obvious pos-

sibility would be to use the upper bound U



from the solution z

of the LP-relaxation of (KP) and set

420 K Knapsack

U := U

.ItcanbeshownthatU

is at most twice as large

as the optimal solution value z

. Initializing y

(0) := 0

and y

(q):=c +1forq =1;:::;U, all other values can be

computed for j =1;:::;n and q =0;:::;U by using the

recursion

(q):=

(

j1

(q)ifq < p

;

minfy

j1

(q); y

j1

(q  p

)+w

g if q  p

The optimal solution value is given by maxfq j y

(q)  cg

and the running time of DP-Proﬁts is bounded by O(nU).

Theorem 1 (Ibarra, Kim) There is an FTPAS for (KP)

which runs in O(n log n + n/"

) time.

Proof The FTPAS is based on appropriate scaling of

the proﬁt values p

and then running DP-Proﬁts with the

scaled proﬁt values. Scaling means here that the given

proﬁt values p

are replaced by new proﬁts

such that

foranappropriatechosenconstantK.

This scaling can be seen as a partitioning of the

proﬁt range into intervals of length K with starting points

0; K; 2K;:::. Naturally, for every proﬁt value p

there is

some integer value i  0suchthatp

falls into the inter-

val [iK; (i +1)K[. The scaling procedure generates for ev-

ery p

the value

as the corresponding index i of the lower

interval bound iK.

Running DP-Proﬁts yields a solution set

X for the

scaled items which will usually be diﬀerent from the origi-

nal optimal solution set X

. Evaluating the original proﬁts

of item set

X yieldstheapproximatesolutionvaluez

.The

diﬀerence between z

and the optimal solution value can

be bounded as follows.









j2X









j2X





 1



= z



jX



jK:

To get the desired performance guarantee of 1 " it is suf-

ﬁcient to have



z







 ":

To ensure this K has to be choosen such that

K 



: (4)

Since n jX



j and U

/2  z



choosing K :=

satisﬁes condition (4) and thus guarantees the perfor-

mance ratio of 1  ". Substituting U in the O(nU)bound

for DP-Proﬁts by U/K yields an overall running time of

O(n

").

A further improvement in the running time is ob-

tained in the following way. Separate the items into small

items (having proﬁt 

)andlarge items (having

proﬁt >

). Then, perform DP-Proﬁts for the scaled

large items only. To each entry q of the obtained dynamic

programming array with corresponding weight y(q)the

small items are added to a knapsack with residual capacity

c  y(q) in a greedy way. The small items shall be sorted

in non-increasing order of their proﬁt to weight ratio. Out

of the resulting combined proﬁt values, the highest one is

selected. Since every optimal solution contains at most 2/"

large items, jX



jcan be replaced in (4)by2/" which results

in an overall running time O(n log n + n/"

). The memory

requirement of the algorithm is O(n +1/"

). 

Two important approximation schemes with advanced

treatment of items and algorithmic ﬁne tuning were pre-

sented some years later. The classical paper by Lawler [5]

gives a reﬁned scaling resp. partitioning of the items

and several other algorithmic improvements which re-

sults in a running time O(n log(1/")+1/"

). A second pa-

per by Magazine and Oguz [6] contains among other fea-

tures a partitioning and recombination technique to re-

duce the space requirements of the dynamic programming

procedure. The fastest algorithm is due to Kellerer and

Pferschy [3,4] with running time O(n minflog n; log(1/")g

+1/"

log(1/")  minfn; 1/" log(1/")g)andspacerequire-

ment O(n +1/"

Applications

(KP) is one the classical problems in combinatorial opti-

mization. Since (KP) has this simple structure and since

there are eﬃcient algorithms for solving it, many solution

methods of more complex problems employ the knapsack

problem (sometimes iteratively) as a subproblem.

A straightforward interpretation of (KP) is an invest-

ment problem. A wealthy individual or institutional in-

vestor has a certain amount of money c available which

he wants to put into proﬁtable business projects. As a ba-

sis for his decisions he compiles a long list of possible

investments including for every investment the required

amount w

and the expected net return p

over a ﬁxed pe-

riod. The aspect of risk is not explicitly taken into account

here. Obviously, the combination of the binary decisions

for every investment such that the overall return on in-

vestment is as large as possible can be formulated by (KP).

One may also view the (KP) as a “cutting” problem.

Assume that a sawmill has to cut a log into shorter pieces.

The pieces must however be cut into some predeﬁned

standard-lengths w

, where each length has an associated

selling price p

. In order to maximize the proﬁt of the log,

the sawmill can formulate the problem as a (KP) where the

length of the log deﬁnes the capacity c.

Knapsack K 421

Among the wide range of “real world” applications

shall be mentioned two-dimensional cutting problems,

column generation, separation of cover inequalities, ﬁ-

nancial decision problems, asset-backed securitization,

scheduling problems, knapsack cryptosystems and most

recent combinatorial auctions. For a survey on applica-

tions of knapsack problems the reader is referred to [2].

Recommended Reading

1. Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the

knapsack and sum of subset problem. J. ACM 22, 463–468

(1975)

2. Kellerer, H., Pisinger, D., Pferschy U.: Knapsack Problems.

Springer, Berlin (2004)

3. Kellerer, H., Pferschy, U.: A new fully polynomial time approxi-

mation scheme for the knapsack problem. J. Comb. Optim. 3,

59–71 (1999)

4. Kellerer, H., Pferschy, U.: Improved dynamic programming in

connection with an FPTAS for the knapsack problem. J. Comb.

Optim. 8, 5-11 (2004)

5. Lawler, E.L.: Fast approximation algorithms for knapsack prob-

lems. Math. Oper. Res. 4, 339–356 (1979)

6. Magazine, M.J., Oguz, O.: A fully polynomial approximation al-

gorithm for the 0–1 knapsack problem. Eur. J. Oper. Res. 8, 270–

273 (1981)

7. Martello, S., Toth, P. Knapsack Problems: Algorithms and Com-

puter Implementations. Wiley, Chichester (1990)

Learning with the Aid of an Oracle L 423

Learning with the Aid of an Oracle

1996; Bshouty, Cleve, Gavaldà, Kannan, Tamon

CHRISTINO TAMON

Department of Mathematics and Computer Science,

Clarkson University,

Potsdam, NY, USA

Keywords and Synonyms

Oracles and queries that are suﬃcient for exact learning

Problem Definition

In the exact learning model of Angluin [1], a learning algo-

rithm A must discover an unknown function f: f0; 1g

f0; 1gthat is a member of a known class C of Boolean func-

tions. The learning algorithm can make at least one of the

following types of queries about f:

 Equivalence query EQ

(g), for a candidate function g:

The reply is either “yes”, if g , f,oracounterexample

a with g(a) ¤ f(a), otherwise.

 Membership query MQ

(a), for some a 2f0; 1g

:The

reply is the Boolean value f(a).

 Subset query SubQ

(g), for a candidate function g:The

reply is “yes”, if g ) f,oracounterexamplea with

f(a) < g(a), otherwise.

 Superset query SupQ

(g), for a candidate function g:

The reply is “yes”, if f ) g,oracounterexamplea with

g(a) < f(a), otherwise.

A Disjunctive Normal Formula (DNF)isadepth-2OR-

AND circuit whose size is given by the number of its AND

gates. Likewise, a Conjunctive Normal Formula (CNF)is

adepth-2AND-OR circuit whose size is given by the num-

ber of its OR gates. Any Boolean function can be repre-

sented as both a DNF or a CNF formula. A k-DNF is a DNF

where each AND gate has a fan-in of at most k; similarly, it

is possible to deﬁne k-CNF.

Problem

For a given class C of Boolean functions, such as poly-

nomial-size Boolean circuits or Disjunctive Normal Form

(DNF) formulas, the goal is to design polynomial-time

learning algorithms for any unknown f 2 C and ask a poly-

nomial number of queries. The output of the learning al-

gorithm should be a function g of polynomial size satisfy-

ing g , f . The polynomial functions bounding the run-

ning time, query complexity, and output size are deﬁned in

terms of the number of inputs n and the size of the smallest

representation (Boolean circuit or DNF) of the unknown

function f

Key Results

One of the main results proved in [4] is that Boolean cir-

cuits and Disjunctive Normal Formulas are exactly learn-

able using equivalence queries and access to an NP oracle.

Theorem 1 The following tasks can be accomplished with

probabilistic polynomial-time algorithms that have access

to an NP oracle and make polynomially many equivalence

queries:

 Learning DNF formulas of size s using equivalence

queries that are depth-3 AND-OR-AND formulas of size

O(sn

/log

n).

 Learning Boolean circuits of size s using equivalence

queries that are circuits of size O(sn + n log n).

The idea behind this result is simple. Any class C of

Boolean functions is exactly learnable with equivalence

queries using the Halving algorithm of Littlestone [10].

This algorithm asks equivalence queries that are the ma-

jority of candidate functions from C.Thesearefunctions

in C that are consistent with the counterexamples obtained

so far by the learning algorithm. Since each such major-

ity query eliminates at least half of the candidate func-

tions, log

jCj equivalence queries are suﬃcient to learn

any function in C. A problem with using the Halving al-

424 L Learning with the Aid of an Oracle

gorithm here is that the majority query has exponential

size. But, it can be shown that a majority of a polyno-

mial number of uniformly random candidate functions

is a good enough approximator to the majority of all

candidate functions. Moreover, with access to an NP or-

acle, there is a randomized polynomial time algorithm

for generating random uniform candidate functions due

to Jerrum, Valiant, and Vazirani [6]. This yields the re-

sult.

The next observation is that subset and superset

queries are apparently powerful enough to simulate both

equivalence queries and the NP oracle. This is easy

to see since the tautology test g , 1isequivalentto

SubQ

(g) ^ SubQ

(g), for any unknown function f;and,

(g)isequivalenttoSubQ

(g) ^ SupQ

(g). Thus, the

following generalization of Theorem 1 is obtained.

Theorem 2 The following tasks can be accomplished with

probabilistic polynomial-time algorithms that make poly-

nomially many subset and superset queries:

 Learning DNF formulas of size s using equivalence

queries that are depth-3 AND-OR-AND formulas of size

O(sn

/log

n).

 Learning Boolean circuits of size s using equivalence

queries that are circuits of size O(sn + n log n).

Stronger deterministic results are obtained by allowing

more powerful complexity-theoretic oracles. The ﬁrst of

these results employ techniques developed by Sipser and

Stockmeyer [11,12].

Theorem 3 The following tasks can be accomplished with

deterministic polynomial-time algorithms that have access

to an ˙

oracle and make polynomially many equivalence

queries:

 Learning DNF formulas of size s using equivalence

queries that are depth-3 AND-OR-AND formulas of size

O(sn

/log

n).

 Learning Boolean circuits of size s using equivalence

queries that are circuits of size O(sn + n log n).

In the following result, C is an inﬁnite class of functions

containing functions of the form f : f0; 1g

!f0; 1g.The

class C is p-evaluatable if the following tasks can be per-

formed in polynomial time:

 Given y,isy a valid representation for any function

2 C?

 Given a valid representation y and x 2f0; 1g

,is

(x)=1?

Theorem 4 Let C be any p-evaluatable class. The following

statements are equivalent:

 C is learnable from polynomially many equivalence

queries of polynomial size (and unlimited computa-

tional power).

 C is learnable in deterministic polynomial time with

equivalence queries and access to a ˙

oracle.

For exact learning with membership queries, the following

results are proved.

Theorem 5 The following tasks can be accomplished with

deterministic polynomial-time algorithms that have access

to an NP oracle and make polynomially many membership

queries (in n, DNF and CNF sizes of f,wheref is the un-

known function):

 Learning monotone Boolean functions.

 Learning O(log n)  CNF

O(log n)  DNF.

Theideasbehindtheaboveresultusetechniques

from [1,3]. For a monotone Boolean function f,thestan-

dard closure algorithm uses both equivalence and mem-

bership queries to learn f using candidate functions g sat-

isfying g ) f. The need for membership can be removed

using the following observation. Viewing :f as a mono-

tone function on the inverted lattice, it is possible to learn

f and :f simultaneously using candidate functions g,h,re-

spectively, that satisfy g ) h.TheNP oracle is used to ob-

tain an example a that either helps in learning f or in learn-

ing :f;whennosuchexamplecanbefound,f was learned.

Theorem 6 Any class C of Boolean functions that is ex-

actly learnable using a polynomial number of member-

ship queries (and unlimited computational power) is exactly

learnable in expected polynomial time using a polynomial

number of membership queries and access to an NP oracle.

Moreover, any p-evaluatable class C that is exactly

learnable from a polynomially number membership queries

(and unlimited computational power), is also learnable in

deterministic polynomial time using a polynomial number

of membership queries and access to a ˙

oracle.

Theorems 4 and 6 showed that information-theoretic

learnability using equivalence and membership queries

can be transformed into computational learnability at the

expense of using the ˙

and NP oracles, respectively.

Applications

The learning algorithm for Boolean circuits using equiv-

alence queries and access to an NP oracle has found

an application in complexity theory. Watanabe (see [9])

showed an improvement on a known theorem of Karp

Learning Automata L 425

and Lipton [7]: if NP has polynomial-size circuits, then the

polynomial-time hierarchy PH collapses to ZPP

Some techniques developed in Theorem 5 for exact

learning using membership queries of monotone Boolean

functions have found applications in data mining [5].

Open Problems

It is unknown if there are polynomial-time learning algo-

rithms for Boolean circuits and DNF formulas using equiv-

alence queries (without complexity-theoretic oracles).

There are strong cryptographic evidence that Boolean cir-

cuits are not learnable in polynomial-time (see [2]and

the references therein). The best running time for learn-

ing DNF formulas is 2

O(n

1/3

)

as given by Klivans and Serve-

dio [8]. It is unclear if membership queries help in this

case.

Cross References

For related learning results, see  Learning DNF Formulas

and  Learning Automata in this encyclopedia.

Recommended Reading

1. Angluin, D.: Queries and Concept Learning. Mach. Learn. 2,

319–342 (1988)

2. Angluin, D., Kharitonov, M.: When Won’t Membership Queries

Help?J.Comput.Syst.Sci.50, 336–355 (1995)

3. Bshouty, N.H.: Exact Learning Boolean Function via the Mono-

tone Theory. Inform. Comput. 123, 146–153 (1995)

4. Bshouty, N.H., Cleve, R., Gavaldà, R., Kannan, S., Tamon, C.: Ora-

cles and Queries That Are Sufficient for Exact Learning. J. Com-

put. Syst. Sci. 52(3), 421–433 (1996)

5. Gunopolous, D., Khardon, R., Mannila, H., Saluja, S., Toivonen,

H., Sharma, R.S.: Discovering All Most Specific Sentences. ACM

Trans. Database Syst. 28, 140–174 (2003)

6. Jerrum, M.R., Valiant, L.G., Vazirani, V.V.: Random Generation of

Combinatorial Structures from a Uniform Distribution. Theor.

Comput. Sci. 43, 169–188 (1986)

7. Karp, R.M., Lipton, R.J.: Some Connections Between Nonuni-

form and Uniform Complexity Classes. In: Proc. 12th Ann. ACM

Symposium on Theory of Computing, 1980, pp. 302–309

8. Klivans, A.R., Servedio, R.A.: Learning DNF in Time 2

O(n

1/3

)

J. Comput. Syst. Sci. 68, 303–318 (2004)

9. Köbler, J., Watanabe, O.: New Collapse Consequences of NP

Having Small Circuits. SIAM J. Comput. 28, 311–324 (1998)

10. Littlestone, N.: Learning Quickly When Irrelevant Attributes

Abound: A New Linear-Threshold Algorithm. Mach. Learn. 2 ,

285–318 (1987)

11. Sipser, M.: A complexity theoretic approach to randomness. In:

Proc. 15th Annual ACM Symposium on Theory of Computing,

1983, pp. 330–334

12. Stockmeyer, L.J.: On approximation algorithms for #P.SIAMJ.

Comput. 14, 849–861 (1985)

Learning Automata

2000; Beimel, Bergadano, Bshouty, Kushilevitz,

Varricchio

AMOS BEIMEL

,FRANCESCO BERGADANO

ADER H. BSHOUTY

,EYAL KUSHILEVITZ

TEFANO VARRICCHIO

Ben-Gurion University, Beer Sheva, Israel

University of Torino, Torino, Italy

Technion, Haifa, Israel

Department of Computer Science, University of Roma,

Rome, Italy

Keywords and Synonyms

Computational learning; Machine learning; Multiplicity

automata; Formal series; Boolean formulas; Multivariate

polynomials

Problem Definition

This problem is concerned with the learnability of mul-

tiplicity automata in Angluin’s exact learning model and

applications to the learnability of functions represented by

small multiplicity automata.

The Learning Model It is the exact learning model [2]:

Let f be a target function. A learning algorithm may pro-

pose to an oracle, in each step, two kinds of queries: mem-

bership queries (MQ) and equivalence queries (EQ). In

a MQ it may query for the value of the function f on

a particular assignment z. The response to such a query

is the value f (z).

In a EQ it may propose to the oracle

ahypothesisfunctionh.Ifh is equivalent to f on all in-

put assignments 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, i. e., an assignment z such that

f (z) ¤ h(z). One says that the learner learns aclassof

functions

C, if for every function f 2 C the learner outputs

ahypothesish that is equivalent to f and does so in time

polynomial in the “size” of a shortest representation of f

and the length of the longest counterexample. The exact

learning model is strictly related to the Probably Approx-

imately Correct (PAC) model of Valiant [19]. In fact, ev-

ery equivalence query can be easily simulated by a sample

of random examples. Therefore, learnability in the exact

learning model also implies learnability in the PAC model

with membership queries [2,19].

If f is boolean this is the standard membership query.

426 L Learning Automata

Multiplicity Automata Let K be a ﬁeld, ˙ be an al-

phabet,  be the empty string. A multiplicity automaton

(MA) A of size r consists of j˙j matrices f



:  2 ˙g

each of which is an r  r matrix of elements from

and an r-tuple E =(

;:::;

) 2 K

. The automaton A

deﬁnes a function f

: ˙



! K as follows. First, deﬁne

a mapping , which associates with every string in ˙



an r  r matrix over K,by() , ID, where ID denotes

the identity matrix, and for a string w = 



:::

,let

(w) , 











. A simple property of  is that

(x ı y)=(x)  (y), where ı denotes concatenation.

Now, f

(w) , [(w)]

E (where [(w)]

denotes the ith

row of the matrix (w)). Let f : ˙



! K be a function.

Associate with f an inﬁnite matrix F, where each of its rows

is indexed by a string x 2 ˙



and each of its columns is in-

dexed by a string y 2 ˙



.The(x, y)entryofF contains the

value f (x ı y). The matrix F is called the Hankel Matrix of

f .Thexth row of F is denoted by F

.The(x, y)entryofF

may be therefore denoted as F

(y)andasF

x;y

. The follow-

ing result relates the size of the minimal MA for f to the

rank of F (cf. [4] and references therein).

Theorem 1 Let f : ˙



! K such that f 6 0 and let F

be its Hankel matrix. Then, the size r of the smallest multi-

plicity automaton A such that f

 fsatisﬁesr=rank(F)

(over the ﬁeld

K).

Key Results

The learnability of multiplicity automata has been proved

in [7] and, independently, in [17]. In what follows let

K be

aﬁeld,f : ˙



! K be a function and F its Hankel matrix

such that r =rank(F) (over

K).

Theorem 2 ([4]) The function f is learnable by an algo-

rithm in time O(j˙jr  M(r)+m  r

) using r equivalence

queries and O((j˙j+logm)r

) membership queries, where

m is the size of the longest counterexample obtained during

the execution of the algorithm, and M(r) is the complexity

of multiplying two r  rmatrices.

Some extensions of the above result can be found

in [8,13,16]. In many cases of interest the domain of the

target function f is not ˙



but rather ˙

for some value n,

i. e., f : ˙

! K. The length of counterexamples, in this

case, is always n and so m = n.DenotebyF

the subma-

trix of F whose rows are strings in ˙

and its columns are

strings in ˙

nd

and let r

max

=max

d=0

rank(F

)(where

rank is taken over

K).

Theorem 3 ([4]) The function f is learnable by an algo-

rithm in time O(j˙jrn  M(r

max

)) using O(r) equivalence

queries and O((j˙j +logn)r  r

max

) membership queries.

The time complexity of the two above results has been re-

cently further improved [9].

Applications

The results of this section can be found in [3,4,5,6]. They

show the learnability of various classes of functions as

a consequence of Theorems 2 and 3. This can be done by

proving that for every function f in the class in question,

the corresponding Hankel matrix F haslowrank.Asiswell

known, any nondeterministic automaton can be regarded

as a multiplicity automaton, whose associated function re-

turns the number of accepting paths of the nondetermin-

istic automaton on w. Therefore, the learnability of mul-

tiplicity automata gives a new algorithm for learning de-

terministic automata and unambiguous automata

.The

learnability of deterministic automata has been proved

in [1]. By [14], the class of deterministic automata con-

tains the class of O(log n)-term DNF, i. e., DNF formulae

over n boolean variables with O(log n)numberofterms.

Hence, this class can be learned using multiplicity au-

tomata.

Classes of Polynomials

Theorem 4 Let p

i;j

: ˙ ! K be arbitrary functions of

a single variable (1  i  t, 1  j  n). Let g

: ˙

! K

be deﬁned by

j=1

i;j

). Finally, let f : ˙

! K be de-

ﬁned by f =

i=1

. Let F be the Hankel matrix corre-

sponding to f , and F

the sub-matrices deﬁned in the previ-

ous section. Then, for every 0  d  n, rank(F

)  t.

Corollary 5 The class of functions that can be expressed as

functions over GF(p) with t summands, where each sum-

mand T

is a product of the form p

i;1

) p

i;n

) (and

i;j

:GF(p) ! GF(p) are arbitrary functions) is learnable

in time poly(n; t; p).

The above corollary implies as a special case the learn-

ability of polynomials over GF(p). This extends the re-

sult of [18] from multi-linear polynomials to arbitrary

polynomials. The algorithm of Theorem 3, for polynomi-

als with n variables and t terms, uses O(nt)equivalence

queries and O(t

n log n) membership queries. The spe-

cial case of the above class – the class of polynomials over

GF(2) – was known to be learnable before [18]. Their al-

gorithm uses O(nt) equivalence queries and O(t

n)mem-

bership queries. The following theorem extends the latter

result to inﬁnite ﬁelds, assuming that the functions p

i;j

are

bounded-degree polynomials.

A nondeterministic automata is unambiguous if for every

w 2 ˙



thereisatmostoneacceptingpath.

Learning Automata L 427

Theorem 6 The class of functions over a ﬁeld K that

can be expressed as t summands, where each summand T

is of the form p

i;1

) p

i;n

),andp

i;j

: K ! K are

univariate polynomials of degree at most k, is learnable in

time poly(n; t; k). Furthermore, if j

Kjnk +1then this

class is learnable from membership queries only in time

poly(n; t; k) (with small probability of error).

Classes of Boxes

Let [`] denotes the set f0; 1;:::;` 1g.Aboxin[`]

deﬁned by two corners (a

;:::;a

)and(b

;:::;b

)(in

[`]

) as follows:

;:::;a

;:::;b

= f(x

;:::;x

): 8i; a

 x

 b

g :

A box can be represented by its characteristic function in

[`]

. The following result concerns a more general class of

functions.

Theorem 7 Let p

i;j

: ˙ !f0; 1g be arbitrary func-

tions of a single variable (1  i  t, 1  j  n). Let

: ˙

!f0; 1g be deﬁned by

j=1

i;j

). Assume that

there is no point x 2 ˙

such that g

(x)=1 for more

than s functions g

. Finally, let f : ˙

!f0; 1g be deﬁned

by f =

i=1

. Let F be the Hankel matrix correspond-

ing to f . Then, for every ﬁeld

K and for every 0  d  n,

rank(F

) 

i=1





Corollary 8 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;`).

Classes of DNF Formulae

The learnability of DNF formulae has been widely investi-

gated. The following special case of Corollary 5 solves an

open problem of [18]:

Corollary 9 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 9 does not refer to a subclass of DNF, it

already implies the learnability of disjoint (i. e., satisfy-1)

DNF. Since DNF is a special case of union of boxes (with

` = 2), one obtains also the learnability of disjoint DNF

from Corollary 8. Positive results for satisfy-s DNF (i. e.,

DNF formulae in which each assignment satisﬁes at most

s terms) can be obtained, with larger values of s.Thefol-

lowing two important corollaries follow from Theorem 7.

Note that Theorem 7 holds in any ﬁeld. For convenience

(and eﬃciency), let

K =GF(2).

Theorem 10 Let f = T

_ T

__T

be a satisfy-s

DNF (that is, each T

is a monomial). Let F be the Han-

kel matrix corresponding to f . Then, rank(F

) 

i=1





 t

Corollary 11 The class of satisfy-s DNF formulae, for

s = O(1),islearnableintimepoly(n; t).

Corollary 12 The class of satisfy-s, t-term DNF for-

mulae is learnable in time poly(n) for the following

choices of s and t: (1) t = O(log n);(2)t= polylog(n)

and s = O(log n/loglogn);(3)t=2

O(log n/loglogn)

and

s = O(log log n).

Classes of Decision Trees

The algorithm of Theorem 3 eﬃciently learns the class

of disjoint DNF formulae. This includes the class of

decision trees. Therefore, decision trees of size t on n

variables are learnable using O(tn) equivalence queries

and O(t

n log n) membership queries. This is better than

the best known algorithm for decision trees [11](which

uses O(t

) equivalence queries and O(t

)member-

ship queries). The following results concern more general

classes of decision trees.

Corollary 13 Consider the class of decision trees that

compute functions f :GF(p)

! GF(p) as follows: each

node v contains a query of the form “x

2 S

?”, for some

 GF(p).Ifx

2 S

then the computation proceeds to

the left child of v and if x

… S

the computation proceeds

to the right child. Each leaf ` ofthetreeismarkedby

avalue

2 GF(p) which is the output on all the assign-

ments which reach this leaf. Then, this class is learnable in

time poly(n; jLj; p), where L is the set of leaves.

The above result implies the learnability of decision trees

with “greater-than” queries in the nodes, solving a prob-

lem of [11]. 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 de-

rived from Corollary 8. The next theorem will be used to

learn more classes of decision trees.

Theorem 14 Let g

: ˙

! K be arbitrary functions

(1  i  `). Let f : ˙

! K be deﬁned by f =

i=1

Let F be the Hankel matrix corresponding to f , and

be the Hankel matrix corresponding to g

.Then,

rank(F

) 

i=1

rank(G

This theorem has some interesting applications. The ﬁrst

application states that arithmetic circuits of depth two with

multiplication gate of fan-in O(log n) at the top level and

addition gates with unbounded fan-in in the bottom level

are learnable.