数理解析研究所講究録1093 巻 1999 年 123-129

123

Analyzing the Average-Case Behavior of Conjunctive Learning
Algorithms
R\"UDIGER REISCHUK*THOMAS

Med.
zu
Institut f\"ur Theoretische Informatik$Un\dot{i}verSit\ddot{a}t$$Wal$

Department of Informatics
Kyushu University
Kasuga 816-8580
Japan
thomas@i.kyushu-u.ac.jp$L\tilde{u}beck$lstrafle 40

23560 L\"ubeck, Germany
reischuk@informatik.

$\mathrm{m}\mathrm{u}$-luebeck. de

Abstract. We introduce a framework to analyze the average complexity of learning problems.
Based on it we consider the problem of learningin the limit and for on-line predictions in
two variants: from positive data only, and from positive and negative examples. The Wholist algorithm
is completely anal.y , in particular its average-casebehavior with respect to the class of binomial. We consider different complexity measures: the number of mind changes, the number ofprediction errors, and the total learning time. Tightbounds are obtained implying that worst case bounds
are too pessimistic. On the average learning can beachieved exponentially faster.
$monom\dot{i}alS$$\mathrm{z}\mathrm{e}\mathrm{d}$$d_{\dot{i}}s-$$tr\dot{i}bu\iota\dot{i}onS$

Finally, we study a new learning model, stochastic
finite learning, in which some information about theunderlying distribution is given. We develop techniques to obtain good bounds for stochastic finite
learning from a precise average case analysis of algorithms learning in the limit and illustrate our approach for the case of learning monomials.

1. Introduction

Learning concepts efficiently has attracted
considerable attention during the last decade.
However, research following the traditional lines
of inductive inference has mainly considered the
update time, i.e., the effort to compute a$S\dot{i}n-$*Part of this work was performed while visiting the
Department of Informatics at Kyushu University supported by the Japan Society for the Promotion of Science
under Grant JSPS 29716102.
\dagger Supported by the Grant-in-Aid for Scientific Research in Fundamental Areas from the Japanese Ministryof Educatlion, Science, Sports, and Culture under grantno. 10558047.

$\mathrm{Z}_{\mathrm{E}\mathrm{U}\mathrm{G}\mathrm{M}\mathrm{A}\mathrm{N}}\mathrm{N}\dagger$

new hypothesis. Starting with Valiant’s paper [18], the total amount of time needed to solvea given learning problem has been investigated,too. The complexity bounds proved within the
PAC model are usually worst-case bounds. In
experimental studies large gaps have often been
observed between the time bounds obtained bya mathematical analysis and the actual runtime
of a learner on typical data. This phenomenon
can be explained easily. Data from running tests
provide information about the average-cas performance of a learner. Since algorithmic learning has a lot of practical applications it is ofgreat interest to analyze the average-case performance, and to obtain tight bounds.
Pazzani and Sarrett [14] have proposed aframework for analyzing the average-case behavior of learners. Several authors have followed
their approach (cf., e.g., [12, 13]). Their goal
is to predict the expected accuracy of the hyis produced with respect to the numberof training examples. However, the results obtained so far are not satisfactory. Typically, theprobability that a random example is misclassified by the current hypothesis is estimated by acomplicated formula. The evaluation of this formula, and the computation of the corresponding
expectation is done by Monte-Carlo simulations.
Clearly, such an approach does not provide general results about the average-case behavior forbroader classes of distributions, and it is hard
to compare these bounds with those proved for
the PAC model.
We outline a new framework to study theaverage-case behavior of learning algorithms
overcoming these drawbacks.
$gle$$\mathrm{e}$$\mathrm{p}_{\mathrm{o}\mathrm{t}\mathrm{h}}\mathrm{e}\dot{\mathrm{s}}$124

2. Preliminaries$C$

Let $\mathbb{N}=\{0,1,2, \ldots\}$ be the set of all natu. If $M$ is a set,ral numbers, and$|M|$ is used for its cardinality. For an infinite selet $d[j]$ denote the initialquence andsegment of of length . By $(0,1)$ we denote,the open real interval from to 1. For
andlearning
domainbe theletis. Every
the power set ofa concept
called a concept, andclass. is also used to denote its characteristic: $c(b)=1$ iff $b\in c$ . To
function, i.e., forconcepts
we deal with, letdefine the classes ofbe a set of litera negative one.
positiveandaliteralisals.
A conjunction of literals defines a monomial.
For a monomial $m$ let $\#(m)$ denote its length,that is the number of literals in it.
$m$ describes a concept $L(m)$ ofin the obvious way, that is $L(m):=\{b\in \mathcal{X}_{n}|m(b)=1\}$ .
The concept class we are going to learn is the setof all concepts that are describable by mono. There are two trivial concepts,
mials over
, whichitself.
the empty subset andis called “TRUE”, is represented by the empty
monomial. The concept “FALSE” has several
descriptions. To avoid ambiguity, we represent. We“FALSE” by the monomial
andidentip the set of all monomials over
. Note that $|C_{n}|=3^{n}+1$ .
the concept class
conWe also consider the subclass $MC_{n}$ ofsisting of all concepts describable by monotone$\mathrm{N}^{+}:=\mathrm{N}\backslash \{0\}$$d$$j\in \mathrm{N}^{+}$

$d$

$j$

$n\in \mathbb{N}^{+}$$0$$\mathcal{X}_{n}=\{0,1\}^{n}$$\wp(\mathcal{X}_{n})$$c\subseteq \mathcal{X}_{n}$$\mathcal{X}_{n}$$C\subseteq\wp(\mathcal{X}_{n})$$c$$b\in \mathcal{X}_{n}$$\mathcal{L}_{n}=\{x_{1},\overline{x}_{1}, X_{2},\overline{x}_{2\cdots,n’ n}X\overline{x}\}$$\overline{x}_{i}$$x_{i}$$\lambda_{n}^{J}$$C_{n}$$c\mathrm{Y}_{n}$$\mathcal{X}_{n}$$\mathcal{X}_{n}$$x_{11\cdot n}\overline{x}..x\overline{x}_{n}$$\mathcal{L}_{n}$$C_{n}$$C_{n}$

monomials. It holds

Definition 1. A concept class is called online predictable if there is a learner $P$ suchthat for all $c\in C$ and all
it holds: $P(d[2j-1])$ is defined for all , and$P(d[2j-1])=d_{2j}$ for all but finitely many .
For on-line prediction, the complexity measure considered is the number of prediction
errors made. We aim to minimize the numberof prediction errors when learning monomials.
Next, we define learning in the limit(cf. [5]). We distinguish between learning frominformant, and learning ffom positive data. For
a concept , let info $(c)$ be the set of those data
in datasequencesat least once. Such a secontaining each
quence is called informant. Let us pair each el. Then theementwith its classification$d_{j}:=(b_{j}, c(bj))$ .
isaninformant
entry
of
7’-th
A positive presentation of is a data sequence containing only elements of and eachare 1
one at least once. Thus all the values
and can be omitted. Hence, we denote the se.
quence simply by, and let $pos(C)$ beLetthe set of all positive presentations of . The
elements of $pos(C)$ are also called a text for .
A limit learner is an inductive inferencemachine (abbr. IIM). An IIM $M$ gets incrementally growing segments of a text (resp. of
an informant) as input. After each input, itfrom a predefined
outputs a hypothesis
refers to ahypothesis space . Each
unique element of the concept class.
Definition, 2. Let
be a concept class andis called
be a hypothesis space for it.
letlearnable in the limit from positive presentation (resp. from informant) if there is an $IIMM$
such that for every $c\in C$ and every $d\in pos(C)$(resp. $d\in info(C)$ ) $:M(d[j])$ is defined for all, and $M(d[j])=h$ for all but finitely many ,is a hypothesis referring to .
where
we choose as hypothesis space the set
Forit, whereas forof all monomials overmonotoneis the set of all
monomials.
The first complexity measure we consider isthe mind change complexity. A mind change
occurs iff $M(d[i])\neq M(d\mathrm{b}+1])$ . This measureis closely related to the number of prediction errors. Both complexity measures say little about
the total amount of data and time needed until a$|\mathcal{M}C_{n}|=2^{n}$.

$d=\langle d_{j}\rangle_{j\in \mathrm{N}^{+}}\in data(c)$

$j$

$j$

$c$

$(C)$

$\langle b_{1}, c(b_{1}), b2, c(b2), \ldots\rangle$$b\in \mathcal{X}_{n}$$c(b_{j})$$b_{j}$

$d$

$c$

$c$

$c(.b_{j})$$d=\langle d_{j}\rangle_{j\in}\mathrm{N}^{+=}\langle b_{1}, b_{2}, b_{3}, \ldots\rangle$$d\mathrm{b}]^{+}:=\{b_{i}|1\leq\dot{i}\leq j\}$

$c$

$c$

$d$

$M(d\mathrm{b}])$$h\in \mathcal{H}$$\mathcal{H}$$C$

3. Learning Models and Complexity
We start with the on-line prediction model
going back to $[1, 10]$ . Here, the learner is givena sequence of labeled examples
from , where. The
are picked arbitrarily andare assumed to be error-ffee. We callthesuch sequences data sequences and denote bydata $(c)$ th.e set of all data sequences for .
after having
A learner $P$ must predict$d=\langle d_{j}\rangle_{j\in \mathrm{N}^{+}}=$$\langle b_{1}, c(b_{1}), b_{2}, c(b_{2}), b\mathrm{s}, c(b_{3}), \ldots\rangle$$b_{j}\in \mathcal{X}_{n}$’$c$$b_{j}$$c(b_{j})$$c$$c(b_{j})$seen$d[2j-1]=\langle b_{1}, c(b_{1}), \ldots, b_{j-1}, c(bj-1), b_{j}\rangle$.

We denote this hypothesis by $P(d[2j-1])$ . Then
. $P$ has sucand the next
it receives
cessfully learned if it eventually reaches a point
beyond which it always predicts correctly.
$c(b_{j})$$b_{j+1}$$C$$\mathcal{H}$

Measures$j$$j$$h\in \mathcal{H}$$c$$C_{n}$$\mathcal{L}_{n}$$\mathcal{M}C_{n}$125concept is guessed correctly. Thus, for learningin the limit we also measure the time complexity.
As in [3] we define the total learning time as follows. Let $M$ be any IIM learning a concept classin the limit. Then, for $c\in C$ and a text or informant for , let $C_{\mathit{0}}n(M, d)=the$ least
such that $M(d[j])=M(d[\dot{i}_{\rfloor}\rceil)$ for all
denote the stage of convergence of $M$ on(cf. [5]). By
we denote the numberof steps to compute $M(d[j])$ . We measure
as function of the length of the input and call it update time. Finally, the total learning time taken by the IIM $M$ on$:=$
a sequence
is defined as $\tau\tau(M, d)$$\sum_{j=1}^{c_{on}(d})(T_{M}dM,[j])$. Given a probability distribution $D$ on the data sequences we evaluate
the expectation of $\tau\tau(M, d)$ with respect to $D$ ,the average total learning time.
$C$

$d$

$\dot{i}\in$$c$$\mathbb{N}^{+}$$j\geq\dot{i}$$d$$T_{M}(d_{j})$$T_{M}(d_{j})$$\mathrm{a}\Gamma$

$d$

$d$

4. The Wholist Algorithm$b_{i}=b_{i}^{1}b_{i}^{2}\ldots b_{i}^{n}$$d$$\dot{i}$$d$$h_{0}:=x_{11.\cdot\cdot n}\overline{x}.\cdot x\overline{x}_{n}$$\ldots$$P’ \mathrm{s}$$b_{i;}$$c(b_{i})$$h_{i-1}(b_{i})$$b_{i}$$n$$b_{i}^{i}=1$$\overline{x}_{j}$$x_{j}$$n$

5. Best and Worst Case Analysis
For the learning models defined we estimate
the best-case complexity, the worst-case complexity, and the expectation of algorithm $P$ and. We start with the first two issues. Bothalgorithms do not make any prediction errors iff
the initial hypothesis
equals the target. For$P$ this means that the target is “FALSE”, while
for MP it is the all-l vector. These special concepts are considered as minimal in their class.
For them the best-case and the worst-case number of predictions errors coincide.
The literals in a monomial $m$ are called
relevant. All other literals in(resp. inin the monotone case) are said tobe irrelevant for $m$ . There are $2n-\#(m)$ irrelevant literals in general, and $n-\#(m)$ in themonotone case. We call bit relevant for $m$ iforis relevant for $m$ . Let $k=k(m)=$$n-\#(m)$ denote the number of irrelevant bits.
Theorem 2. Let $c=L(m)$ be a non-minimal
concept in. Then algorithm
makes
1 prediction error in the best case, and $k(m)$prediction errors in the worst-case.
If is a non-minimal concept of algorithm$P$ makes 2 prediction errors in the best case and$1+k(m)$ prediction errors in the worst-case.
As Theorem 2 shows, the gap between thebest-case and worst-case behavior can be quite
large. Thus, we ask what are the expectedbounds for the number of prediction errors on
randomly generated data sequences. Before answering this question we estimate the worst-casenumber of prediction errors averaged over the, resp.
whole concept class. Thus we
get a complexity bound with respect to the parameter , instead of $\#(m)$ as in Theorem 2.
This averaging depends on the underlying prob. ability distribution for selecting the targets (forthe corresponding data sequences we consider
the worst input). The average is.shown to be linear in if the literals are binomially distributed.
To generate the probability distributions wethe relevant positive literals to
assume forbe drawn independently at random with probability $p,$ $p\in(0,1)$ . Thus, with probability$\mathcal{M}P$$h_{0}$$\mathcal{L}_{n}$$\{x_{1}, \ldots , x_{n}\}$Next, we present Haussler’s [6] Wholist algorithm for on-line prediction of monomials. For
learning in the limit this algorithm can be modified straightforwardly. The limit learner computes a new hypothesis using only the most recent example received and his old hypothesis.
Such learners are called iterative (cf. [8]). Let$c\in C_{n}$ , let $d\in data(c)$ , and let
denote the -th Boolean vector in .
Algorithm $P$: On input do the following:.
Initialize
for $\dot{i}=1,2,$
do
letdenoteinternal hypothesis
produced before receiving
predict; read;when getting. if $h_{i-1}(b_{i})=c(b_{i})$ then $h_{i}:=h_{i-1}$
else for $j:=1$ to do.
ifthen delete
inelse deleteinletbe the resulting onomial
end.
Note that the algorithm is monotone with respect to the sequence of its internal hypotheses.
Theorem 1. Algorithm $P$ learns the set of
all monom\’ials within the prediction model.
makes at most $n+1$ prediction errors.
, algorithm
To learn the concept class$h_{0}=x_{1}x_{2\cdotsn}X$is modified by initializing
ing the loop appropriately. We
and by.
refer to the modified algorithm as to$h_{i-1}$

Theorem 1 can be restated for $MP$ with the
only difference that now the worst-case boundfor the number of prediction errors is .

$h_{i-1}$$h_{i-1;}$$h_{i}$$.\mathrm{m}$$It$$\mathcal{M}C_{n}$$\mathcal{P}$$\mathrm{s}\mathrm{i}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{i}6^{r}$$\Lambda 4P$$\dot{i}$$\overline{x}_{i}$$x_{i}$$\Lambda 4P$$\mathcal{M}C_{n}$$C_{n}$$c$$\mathcal{M}C_{n}$

$n$

$n$

$\Lambda 4C_{n}$$C_{n}$

126$1-p$ a literal is irrelevant. The length of themonomials drawn by this distribution is binomially distributed with parameter . Thus wecall such a distribution on the concept class abinomial distribution.
Theorem 3. Let the concepts inbe binomially distributed with parameter . Then the
average number of prediction errors of $MP$ for
the worst data sequences is $n(1-p)$ .
, the bound says that the maxiIn casemal number of prediction errors when uniformly
averaged over all concepts inis .
Next, we deal with the class. For comparing it to the monotone case we have toclarip what does it mean for concepts into be binomially distributed. Since there are$3^{n}+1$ many concepts infor a uniform distribution each concept must have probability$1/(3^{n}+1)$ . For each position $i=1,$
three,options are possible, i.e., we may chooseor neither of them. This suggests the formulais the prob’ whereability to takethe probability to chooseandthe probability to choose none, and$p_{1}+p_{2}+p_{3}=1$ and $k_{1}+$. $k_{2}+k_{3}=n$ .
$k_{1}+k_{2}$counts the number of relevant literals, resp. bits. However, this formula does
not include the concept “FALSE.” Thus, let
us introduce $p_{f}\in(0,1)$ for the probability tochoose “FALSE.” Then the formula becomes(call such a probability distribution a weighted multinomial
distribution with parameters $(p_{f},p_{1},p_{2},p3)$ .
Theorem 4. Let the concepts inoccur according to a weighted multinomial distribution
with parameters. Then the average number of prediction errors of $P$ for the
worst data sequences is $(1-p_{f})(1+np_{3})$ .
For the particular case that all concepts fromare equally likely, we get that on the average less than $n/3+1$ errors are to be expected given the worst data sequences. Hence,in this case the classseems to be easier tolearn thanwith respect to the complexity measure prediction errors. However, thisimpression is misleading, since the probabilities to generate an irrelevant literal are$ent$ , i.e., 1/3 for. If weand 1/2 forassume the probabilities to generate an irrelevant literal to be equal, say , and make the$p$$\mathcal{M}C_{n}$$p$$p= \frac{1}{2}$$\mathcal{M}C_{n}$$\frac{n}{2}$$C_{n}$$C_{n}$$C_{n}$$\ldots,$$n$$x_{i}$$\overline{x}_{i}$$(_{k_{1},k_{2},k\mathrm{s}}n)p^{k_{1}}1p_{2}p^{k_{3}}k2\mathrm{a}$$x_{i},$$\overline{x}_{i}$$p_{1}$$p_{2}$$p_{3}$$1-p_{f^{)}}(_{k_{1},k_{2},k_{3}}n)p_{1}pk12k_{2}p^{k_{3}}3*\mathrm{W}\mathrm{e}$$C_{n}$$(p_{f},p_{1},p_{2,p}\mathrm{a})$$\dot{C}_{n}$$C_{n}$$\mathcal{M}C_{n}$$d_{\dot{i}}ffer-$$C_{n}$$\mathcal{M}C_{n}$$q$assumption that “FALSE” has the same probability as “TRUE,” the average complexity isfor. Sinceand $nq$ for$q=1-(p_{1}+p_{2})$, and forfor
$q=1-p$ ,. This isnow
is easier to learn thaninteresting, since it shows the influence of theunderlying distribution. . In contrast, previous
work has expressed these bounds in terms of the-dimension which for both classes.
The results above directly translate to limitlearning
informant or from text for thecomplexity measure number of mind changes.
What can be said about the total learning
time? The best-case can be handled as above.
Sine the update time is linear in for both algorithms
and $P$, in the best case the total
learning time is linear. In contrast, the worstcase total learning time is unbounded for bothalgorithms. Hence, as far as learning in the limit
and the complexity measure total learning time
are concerned, there is a huge gap between thebest-case and the worst-case behavior. Since theworst-case is unbomded, it does not make sense
to ask for an analogue to Theorem 3 and 4. Instead, we continue by studying the average-case.
behavior of the limit learner $P$ and$\frac{1}{1+q^{n}}(1+nq)$$C_{n}$$\mathcal{M}C_{n}$$C_{n},$$\mathcal{M}C_{n},$$C_{n}$$\mathcal{M}C_{n}$$\mathrm{V}\mathrm{C}$$n$$\mathrm{h}\mathrm{o}\mathrm{m}$$n$$\mathrm{A}tP$$\lambda 4P$

6. Average-Case Analysis for Learningin the Limit from Text

For the following average case analysis we assume that the data sequences are generated at
random with respect to some probability distribution
taken from a class of admissible dis$D$

specified below. We ask for thetributions
average number of examples till an algorithm
has converged to a correct hypothesis. CON
denotes a random variable counting the numberof examples till convergence. Let be a text ofthe target concept that is generated at random
according to $D$ . If the concept is “FALSE”
no examples are needed, and if contains precisely
literals then one positive example suffices. Thus, for these two cases everything isclear and the probability distributions $D$ on theset of positive examples for are trivial.
For analyzing the nontrivial cases, let $c=$
$L(m)\in C_{n}$ be a concept with monomial $m=$such that $k=k(m)=n-\#(m)>0$ .
positive examples for . For the
There aresake of pre.sentation, we assume these examples
$D$

$d$

$c$

$c$

$c$

$n$

$c$

$\bigwedge_{j=1}\#(m)\ell_{i_{j}}$$2^{k}$$c$127

to be binomially distributed. That is, in arandom positive example all entries corresponding to irrelevant bits are selected independentlyof each other. With some probability
thiswill be a 1, and with probability 1 $-p$ a .
We shall consider only nontrivial distributions
where $0<p<1$ . Note that otherwise the data
sequence does not contain all positive examples.
The first example received forces $P$ to delete
precisely of the $2n$ literals in. Thus, thisexample always plays a special role. The hypothesis
depends on, but the numberof literals that remain to be deleted fromuntil convergence is independent of . Using tailbound techniques, we an show the following.
Theorem 5. Let $c=L(m)$ be a non-minimal
concept in, and let the positive examples
for be binomially distributed with parameter. Define. Then the expected number of positive examples needed by algorithm
until convergence can be bounded by
$p$

$0$

$n$

$h_{0}$$h_{1}$$k$$b_{1}$$h_{1}$$b_{1}$$c$$C_{n}$$c$$\psi:=\min\{\frac{1}{1-p}, \frac{1}{p}\}$$p$$\mathcal{P}$$E[\mathrm{C}\mathrm{o}\mathrm{N}]\leq\lceil\log_{\psi}k(m)1+3.\cdot$

A similar analysis can be given in the monotone setting for algorithm.
Corollary 6. For every binomially distributed
text with parameter $0<p<1$ the average total
learning time of algorithm $P$ for concepts inwith literals is at most $O(n(\log(n-\mu+2))$ .
The expectation alone does not provide complete information about the average case behavior of an algorithm. We also like to deduce bounds on how often the algorithm exceeds the average
erably. The Wholist
algorithm possesses two properties that simplify this derivation considerably, i.e., it is setdriven and conservative. Set-driven means$h\in pos(C)$ and allthat for all $c\in C_{n}$ all
the equality $d[i]^{+}=h[j]^{+}$ implies$P(d[\dot{i}])=P(h[j])$ .
A learner is conservative
if every mind change is caused by an inconsistency with the data seen so far. Now, the following theorem establishes exponentially shrinking
tail bounds for the expected number of examples
needed in order to achieve convergence.
Theorem 7 ([16]). Let CON be the sample complexity of a conservative and set-driven
learning algorithm.
Then
2 .
.
for all
A simple calculation shows that in case of
exponentially shrinking tail boumds the variance$\mathcal{M}P$$C_{n}$$\mu$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{s}\mathrm{i}\acute{\mathrm{d}}$$d,$$\dot{i},j\in \mathbb{N}^{+}$$\mathrm{P}\mathrm{r}[\mathrm{C}\mathrm{o}\mathrm{N}$$E[\mathrm{C}\mathrm{O}\mathrm{N}]]\leq 2^{-t}$$t\in \mathrm{N}$

$>$

$t$

is bounded by$O(E[\mathrm{c}\mathrm{o}\mathrm{N}]2)$.

7. Stochastic Finite Learning
Next we show how to convert the Wholist
algorithm into a text learner that identifies allconcepts instochastically in a bounded num$ber$
roundshigh confidence. A bit addiwithoftional knowledge concerning the underlying classof probability distributions is required. Thus, inntrast to the PAC model, the resulting learning model is not distribution-free. But withrespect to the quality of its hypotheses, it isstronger than the PAC model by requiring theoutput to be probably exactly correct rather thanprobably approximately correct. The main advantage is the usage of the additional knowledge
to reduce the sample size, and hence the total
learning time drastically. This contrasts to previous work in the area of PAC learning (cf., e.g.,[2, 4, 7, 9, 11, 17] . These papers have shown
concepts classes to be PAC learnable from polynomially many examples given a known distribution or class of distributions, while the general
PAC learnability of these concepts classes is notachievable or remains open. Note that our general approach, i.e., performing an average-caseanalysis and proving exponentially shrinking tailbounds for the expected total learning time, canalso be applied to obtain results along this line
(cf. [15, 16]).
Definition 3. Let $D$ be a set of probabdity
distributions on the learning domain,a concept class,a hypothesis space for , and$\delta\in(0,1)$ .
$(C, D)$ is said to be stochastically$C_{n}$$\cdot$$\mathrm{c}o$

$)$

$C$

$C$

$\mathcal{H}$finite learnable with -confidencewith respect to
iff there is an $IIMM$ that for every$c\in C$ and every $D\in D$ performs asfollows.
Given a random presentation for generated
according to $D,$
stops after having seen anumberexamplesand outputs a single
finiteof$\delta$$\mathcal{H}$

$d$

$c$

$M$

hypothesis. With probability at least(with respect to distribution $D$ ) has to be correct, that is $L(.h)=c$ in case of monomials.
If stochastic finite learning can be achieved with-confidence for every $\delta>0$ then we say that$(C, D)$ can be learned stochasticallyfinite withhigh confidence.
We study the case that the positive examples are binomially distributed with parameter. But we do not require precise knowledge$h\in \mathcal{H}$$1-\delta$$h$$\delta$

$p$

128

the PAC model. We ask if one can achieve an
about the underlying distribution. Instead, we
expected sample complexity for computing an
proknowledge
isreasonably assume that prior-approximation that is polynomially boundedsuch thatvided by parameters Plow and.
in $\log n$ and. Bino$Plow\leq p\leq p_{up}$ for the true parameter
Let $err_{m}(h_{j})=D(L(h_{j})\triangle L(m))$ be themial distributions fulfilling this requirement arewith respect to-admissible distributions.
callederror made by hypothesis$L(h_{j})\triangle
L(m)$ denotes the
distri$m$
of
such
set
the
denoteLetmonomial , where
and $L(m)$ , and.
symmetric difference ofbutions on$D$ the probability distribution with respect toare available, theIf bounds Plow and
Wholist algorithm can be transformed into awhich the examples are drawn. Hypothesis.
is an -approximation for $m$ ifstochastic finite learner inferring all concepts
Finally, we redefine the stage of convergence.
with high confidence.
Let $d=$info $(L(m))$ , then we
Theorem 8. Let $0<Plow$ $\leq p_{up}<1$ andthe least number such thatset
$err_{m}(P(d[i]))\leq\epsilon$.
for all
Note that once the Wholist algorithm has
fidence from positive presentations. To achieve
reached an -approximate hypothesis all further-confidence no more thanhypotheses will also be at least that close to themany examples are necessary.
target monomial. The next theorem gives an
The latter example bound can even be improved
affirmative answer to the question posed above.
Theorem 10. Let $c=L(m)\in C_{n}$ be a nontrivial concept. Assuming that examples arerithm, the confidence requirement increases thedrawn independently at random from the unionly.
sample size by an additive term
form distribution, the expected number of exLearning
Analysisfor
Average-case8.
amples needed by algorithm $P$ until converging
in the Limit from Informant
to an -approximation for can be bounded by.
Finally, we consider how the results obtained
concerning
inforknowledge
Therefore, additionalso far translate to the case of learning
the underlying probability distribution pays off
mant. First, we investigate the uniform distribucases
trivialhavetheweagain. Using Theorem 7 and modifying Sec. Again,tion overtion 7 mutatis mutandis, we achieve stochastic
that the target is “FALSE” or $m$ is a monofinite learning with high confidence for all conmial without irrelevant bits. In the first case,many examusing
cepts inno example is needed at all, while in the latples. However, the resulting learner now infers
ter one, there is only one positive example hav. Thus the expected number-approximations. Comparing this bound withing probability
the sample complexity given in the PAC modelof examples needed until successful learning is$2^{n}=2\#(m)$ .
one notes an exponential reduction.
Finally, we generalize the last results to the
Theorem 9. Let $c=L(m)\in C_{n}$ be a nontriv$ial$ concept.
case that the data sequences are binomially disIf an informant for is generated
tributed for some parameter $p\in(0,1)$ . This
from the uniform distribution by independent
means that any particular ector containing
draws the expected number of examples needed
has probability
times a 1 and $n-\nu$ a
by algorithm $P$ until convergence is bounded by$\leq
2\#(m)(\lceil\log_{2}k(m)\rceil+3)$$E$ [$p^{\nu}(1-p)^{n-\nu}$with proba1
drawn
is
a
.
since
ON]
bility and a with probability l-p. First,
Hence, . as long as $k(m)\sim=n-\mathrm{O}(1)$ , we
Theorem 9 generalizes as follows.
still achieve an expected total learning time
Theorem 11. Let $c=L(m)\in C_{n}$ be a$O(n\log n)$ . But if $\#(m)=\Omega(n)$ the expected
nontrivial concept. Let $m$ contain precisely
total learning is exponential. However, if there
negative literals. If
positive literals andmay beare many relevant literals then evenexamples.
thelabeledforapproximation
bad
for are independently
considered as a not too
andbinomially distributed with parameterbe an error parameter as inThus, let$\epsilon$$p_{up}$$1/\epsilon$$p$$(p_{lovj}, p_{\mathit{1}\iota}P)$$h_{j}$$D_{n}[P\iota \mathrm{o}w’ p\tau\iota p]$$L(/l_{j})$$r\mathrm{Y}_{n}$$p_{up}$$h_{j}$$err_{m}(h_{j})\leq\epsilon$$\epsilon$$(d_{j})_{j\in \mathrm{N}^{+}}$

$\in$

$j$

$\mathrm{C}\mathrm{O}\mathrm{N}_{\epsilon}(d)=_{df}$$\psi.\cdot=\min_{Ci_{SS}tohaSti_{C}}\{\frac{1}{1-p\iota_{\mathit{0}},all^{w}y},fielylearnablewithhighcon\frac{1}{n\dot{i}tp_{vp}}\}.Then(Cn’ D_{n}[plowpup])-$$\dot{i}\geq j$$O(\log_{2}1/\delta\cdot\log_{\psi^{n}})$$\delta$$\epsilon$$\mathrm{t}\circ\log n+\log_{\psi a}1/\delta \mathrm{C}\mathrm{a}\mathrm{r}\mathrm{r}\mathrm{e}\mathrm{f}\mathrm{u}\mathrm{l}erroranlyS\dot{i}s,+O(\mathrm{l})\mathrm{b}\mathrm{y}\mathrm{p}\mathrm{e}_{\mathrm{h}_{\mathrm{o}1}}\mathrm{r}\mathrm{f}\mathrm{o}\mathrm{r}\min_{\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{a}1-}\mathrm{g}\mathrm{a}\mathrm{i}.\mathrm{e}.,$$\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{t}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{W}\mathrm{g}\mathrm{o}$$\log_{\psi}1/\delta$$c$$\epsilon$$E[ \mathrm{C}\mathrm{o}\mathrm{N}\mathit{6}]\leq\frac{1}{\epsilon}\cdot(\lceil\log_{2}k(m)\rceil+3)$$\mathrm{h}\mathrm{o}\mathrm{m}$$\lambda_{n}’$$O( \frac{1}{\epsilon}\cdot\log\frac{1}{\delta}\cdot\log n)$$C_{n}$$2^{-n}$$\epsilon$$c$$\dot{\mathrm{v}}$

$0$

$\nu$

$\mathrm{c}_{}$$p$$h_{0}$

$\pi$

$c$

$\epsilon\in(0,1)$$0$$\tau$

$c$

$p$

129

$\psi:=\min_{eXam}\{berofs\frac{1}{ple1-p}, needed\frac{1}{p}\}ihebynthee_{\dot{i}thl}xpecalg_{\mathit{0}}rmPuntintedum-$

convergence can be bounded by$\neg^{1}p^{\pi}(1-p^{\tau}(\lceil\log_{\psi}k(m)1+3)$$E[\mathrm{C}\mathrm{O}\mathrm{N}]$$\leq$.

Theorem 10 directly translates into the settingof binomially distributed inputs.
Theorem 12. Let $c=L(m)\in C_{n}$ be a nontrivial concept. Assume that the examples are drawn
with respect to a binomial distribution with parameter , and let. Thenthe expected number of examples needed by algorithm $P$ until converging to an e-approximation
can be bounded byfor$p$$\psi=\min\{\frac{1}{1-p}, \frac{1}{p}\}$$c$$E[\mathrm{C}\mathrm{O}\mathrm{N}]$$\leq$$\frac{1}{\epsilon}$.
Finally, one can also learn e-approximations$(\mathrm{r}\log\psi k(m)1+3)$

stochastically finite with high confidence frominformant with an exponentially smaller sample
complexity.
Theorem 13. Let $0<Plow$ $\leq p_{up}<1$ and. For$e- approX\dot{i}mations$ can be learned stochasticallyfinitely with -confidence from informant for all$\delta\in(0,1)$ .
Further,,resp.
many examples suffice for this purpose.
$\psi:=\min\{\frac{1}{1-p_{low}},\frac{1}{p_{v\mathrm{p}}}\}$$(C_{n}, D_{n}\lceil p_{l}ow’ p_{u}p])$$\delta$$e,$$O( \frac{1}{\overline{\mathrm{c}}}\cdot\log_{2}1/\delta\cdot\log_{\psi)}n$$O( \frac{\dot{1}}{\epsilon}\cdot(\log_{\psi}1/\delta+\log_{\psi}n))$[7] M. Kearns, M. Li, L. Pitt and L.G. Valiant. On
the learnability of Boolean formula. “Proc. 19th
Annual ACM Symposium on Theory of Computing,” 285-295, ACM Press 1987.
[8] S. Lange and T. Zeugmann. Incremental learning from positive data. J. Comput. System Sci.
$53(1):88-103$ , 1996.

[9] M. Li and P. Vitanyi. Learning simple concepts
under simple distributions. SIAM J. Comput.,$20(5):911-935$ , 1991.

[10] N. Littlestone. Learning quickly when irrelevant

attributes are abound: A new linear thresholdalgorithm. Machine Learning 2:285-318, 1988.

[11] B. Natarajan. On learning Boolean formula.
“Proc. 19th Annual ACM Symposium on Theory of Computing,” 295-304, ACM Press, 1987.
[12] S. Okamoto and K. Satoh. An average-caseanalysis of -nearest neighbor classifier. “Proc.
$k$

1st International Conference on Case-Based
Reasoning Research and Development,” LNCS
Vol. 1010, $253-264_{i}$ Springer-Verlag, 1995.
[13] S. Okamoto and N. Yugami. Theoretical analysis of the nearest neighbor classifier in noisy. “Proc. 13th International Conference
on Machine Learning, 355-363, Morgan Kaufmann 1996.
$\mathrm{d}_{\mathrm{o}\mathrm{m}\mathrm{a}}.\mathrm{i}\mathrm{n}\mathrm{s}$[14] M.J. Pazzani and W. Sarrett, A framework foraverage case analysis oflearning algorithms. Machine Learning 9:349-372, 1992.
$\mathrm{c}\mathrm{o}\mathrm{n}.|\mathrm{u}\mathrm{n}\mathrm{C}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{e}$References[$1_{\mathrm{J}}^{\rceil}$

J.M. Barzdin, R.V. Reivald, On the prediction of general recursive functions. Soviet Math.
Doklady 13: 1224-1228, 1972.

[2] G. Benedek and A. Itai. Learnability by fixed
distributions. “Proc. 1988 Workshop on Computational Learning Theory,” 81-90, Morgan
Kaufmann, 1988.
[3] R. Daley and C.H. Smith. On the complexity of

inductive inference. Inform. Control, 69:12-40,
1986.

[15] R. Reischuk and T. Zeugmann. Learning onevariable pattern languages in linear averagetime. “Proc. 11th Annual Conference on Computational Leaming Theory,” 198-208, ACM

Press, 1998.

[16] P.

and T. Zeugmann. Learning kvariable pattern languages efficiently stochastically finite on average from positive data.
. 4th International Colloquium on Grammatical Inference,” LNAI Vol. 1433, 13-24,
Springer-Verlag, 1998.
$\mathrm{R}\mathrm{o}\mathrm{S}\mathrm{S}\mathrm{m}\mathrm{a}\iota\dot{\mathrm{u}}\mathrm{t}\mathrm{h}$$‘\zeta \mathrm{P}\mathrm{r}\mathrm{o}\mathrm{C}$[4] F. Denis and R. Gilleron. PAC learning under helpful distributions. “Proc. 8th Intemational Workshop on Algorithmic Learning Theory,” LNAI Vol. 1316, 132-145, Springer-Verlag,[17] Y. Sakai, E. Takimoto and A. Maruoka. Proper
learning algorithms for functions of k terms under smooth distributions. “Proc. 8th Annual
ACM Conference on Computational Learning
Theory,” 206-213, ACM Press, 1995.

[5] E.M. Gold, Language identification in the limit.

[18] L.G. Valiant. A theory of the learnable. Commun. ACM 27:1134-1142, 1984.

1997.

Inform. Control 10:447-474, 1967.

[6] D. Haussler. Bias, version spaces and Valiant’s
learning framework. “Proc. 8th National Conference on Artificial Intelligence, 564-569, Morgan Kaufnann, 1987.