数理解析研究所講究録1093 巻 1999 年 130-135

130

Learning DNF by Approximating Inclusion-Exclusion Formulae
Jlln Tarui (垂井淳)

Tatsuie Tsukiji (築地立家)$*$

Probably
Correct learning algorithms
munber of examples about an ungeneralize a )known concept into a function that can predict a future
be the inobservation. More formally, let $X$ andstance and outcome spaces, respectively. Then a PAC
algorithm observes randomly drawn examples $(x, f(x))$
about an unknown concept : $X\neg Y$ . These examples are independently and identically distributed random variables governed by an arbitrary and unknown
distribution over $X$ . With and only with these training examples, the algorithm aims to find a hypothesist,hat approximales the target concept:
with respect to the same distribution. Hence it measures “goodness” of the hypothesis by the probability
called the prediction
accuracy.
Valiant introduced the PAC model in a series of
paper
which is currently one of the moststandard platfornls for invention of polynomial-timelearning algorithms. The PAC theory aims to learn
as possible, beas much general concept
simple structures, e.g. depth-one or
ginning
depth-two Boolean circuits.
Valiant proved that
Boolean conjunctions are polynomial-time learnable,
and left the learning problem of the class DNF{polynomial-size Disjunctive Normal Form formulae}
for the future research. Here, as usual, a DNF formulaof a amily of conjunctions of Boolean
is aliterals. These Boolean conjunctions are commonly
called the terms of the DNF formula. The size of a
DNF formula is the number of its (distinct) terms.
learnability
Since then, a lot of literatures haveof subclasses of DNF by specifying either structuralparameters of formulae or the distribution for the
training examplef: ([1] provides a list of literatures).
$A_{\mathrm{P}\mathrm{P}^{ra}}\dot{\alpha}mately$$\mathrm{a}\mathrm{l}\mathrm{l}$$\mathrm{s}\mathrm{n}$$\mathrm{Y}$

$f$

$f$

$Xarrow \mathrm{Y}$$h$$\mathrm{a}\mathrm{c}\mathrm{c}(h)=\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{r\in}.\mathrm{Y}\mathrm{t}l_{l}(X)=f(x)\}$$\dagger:[12,13],\cdot$$\iota\cdot \mathrm{l}\mathrm{a}\mathrm{s}\mathrm{s}\mathrm{e}\mathrm{s}$$\mathrm{h}\mathrm{o}\mathrm{m}$$=$$\mathrm{d}\mathrm{i}8\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{C}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$$\mathrm{p}_{1}\cdot \mathrm{o}\mathrm{v}e\mathrm{d}$. Department of Communicationsoforiginal
problem still remains unresolved.
time
Recently, Bshouty obtained a
PAC algorithm for learning DNF. MOIV strongly; heproved a similar upper bound in the exact non-proper
The curlearning model using equivalence queries.
understanding torent paper is devoted to give athis learning time in the PAC model: roughly speak)istime, we show that Bshouty
2,
if learnpossible and best possible to be attainedorder of theiring aigorithms search hypotheses in
However, in spite of much effort,

1. Introduction$h$Systems, University, Chofu-shi, Tokyo 182,$\mathrm{a}\mathrm{r}\iota \mathrm{d}$$\mathrm{E}\mathrm{l}\mathrm{e}\mathrm{C}\mathrm{t}\mathrm{I}^{\cdot}0\cdot \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{m}\mathrm{u}\mathrm{n}\mathrm{i}_{\mathrm{C}\mathrm{a}}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s},\mathrm{C}\mathrm{h}_{\mathrm{o}\mathrm{g}\mathrm{u}}\mathrm{g}\mathrm{a}\mathrm{o}\mathrm{k}\mathrm{a}$Japan.
. $E$-mail: jun@sw.cas.uec.ac.jp\dagger School of lnformatics and Sciences, Nagoya University,
Nagoya 464-01, Japan.

-mail address:$\iota_{\mathrm{S}\mathrm{u}}\mathrm{k};\mathrm{j}\mathrm{i}@\inf \mathfrak{c}\mathrm{J}.\}_{1}\mathrm{u}\mathrm{n}\mathrm{l}\mathrm{a}\mathrm{n}.\mathrm{n}\mathrm{a}\{\ddagger o\mathrm{y}\mathrm{a}-\mathrm{u}.\mathrm{a}\mathrm{C}.\mathrm{i}\iota)$$\mathrm{V}\mathrm{a}\mathrm{l}\mathrm{i}\mathrm{a}\mathrm{l}\mathrm{l}\mathrm{t}’ \mathrm{S}$$2^{o}1\sqrt{\prime}\tilde{\mathrm{t}}(\mathrm{l}\mathrm{o}\mathrm{g}\prime t\mathrm{I}^{\mathrm{z}_{)}}$$\mathrm{J}$$\mathrm{f}\mathrm{u}\iota \mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}$$2^{\mathrm{C}j(\sqrt}‘$$\mathrm{s}\mathrm{l}\mathrm{t}^{1},\mathrm{a}\iota 1\mathrm{i}\mathrm{n}\mathrm{g}$$\mathrm{i}\grave{\mathrm{n}}\mathrm{g}$$\mathrm{t}11\mathrm{G}$“succinctness”.
In more detail, we analyze upper and lower )and suffion size of Boolean conjunctions
accuracybyformulagiven
DNF
cient to approximate asize of athe(here
definewe
1/2
thanslightly better
Boolean conjunction as the number of distinct variables
on which it depends.) Such an allalysis determines tlle
perforrnance of a naive search algorithm that.
Boolean conjunctions in the order of t.heir
fact,, our analysis does not depend on kinds of symnlet,
functions to be exhausted: instead of
nlajority
paritydisjunctions,eitherfunctions, or even general symmetric functions. derives
the same learning results from similar analyses.
Naive search algorithms find only weakly
hypotheses, so they need to be boosted on accuratiy
to complete the PAC learning process. Schapire [11]and later on Reund [4] invented efficient algorithms
that boost the accuracy of a given weak algorithm (insense of [10] under a given distribution. which we rc.
fer t,o as general boosters. In this paper.
fr‘tlnein
algorittuns
performance of naive searchhdntl, ifworks of general boosters. On thetarget distribution is specified as the uniforru
bution, naive search algorithms have been
. applied to learn DNF cooperating with specific boosters.
In fact, Verbeur.p [14] showed that naively searching
Boolean conjunctions learns the class DNF in quasipolynonuial time. Linial, Mansor and Nisim [8] showed,$1$$0\iota 1\mathrm{I}\mathrm{l}\mathrm{d}\mathrm{S}$$\mathrm{n}\mathrm{e}\mathrm{c}\epsilon \mathrm{l},\mathrm{S}\mathrm{f}\{\mathrm{a}r\mathrm{y}$$1^{\mathrm{J}}\mathrm{X}\mathrm{h}\mathrm{a}\mathrm{u}\mathrm{s}\mathrm{t}\mathrm{S}$$\mathrm{s}\mathrm{i}\mathrm{z}\mathrm{e}\backslash _{\xi}’$$\mathrm{h}_{1}$$((\mathrm{n}\mathrm{j}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{c}\dagger \mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}$$\mathrm{r}\mathrm{i}\mathrm{c}$$\mathrm{f}\mathrm{u}\mathrm{n}\mathrm{c}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}_{\}$$\mathrm{c}\mathrm{o}\mathrm{u}\mathrm{n}\mathrm{t}_{l}\mathrm{i}\mathrm{n}\mathrm{g}$$\mathrm{a}((\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{e}$$)$$1^{\cdot}\mathrm{c}\grave{\mathrm{o}}\mathrm{t}J\iota_{\dot{\iota}}\mathrm{d}\mathrm{v}\mathrm{t}\iota\iota \mathrm{c}^{s}$$\mathrm{t}11(!$$\mathrm{t}_{r}11\mathrm{e}$$0\iota 1_{1\mathrm{e}\mathrm{r}}$$\mathrm{d}\mathrm{i},.\mathrm{s}.\iota_{\mathrm{t}}\cdot \mathrm{i}-$$\mathrm{W}\tilde{1}\mathrm{d}\mathrm{e}1_{\mathrm{V}}$$addre\epsilon S$$E$$\mathrm{f}$$\overline{\mathrm{l}\mathrm{A}\mathrm{n}\mathrm{g}\mathrm{l}\mathrm{u}\mathrm{i}\mathrm{n}.\mathrm{S}\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{o}\mathrm{f}[2]\mathrm{P}}\Gamma\circ \mathrm{v}\mathrm{i}\mathrm{d}\mathrm{e}\mathrm{S}$a$\mathrm{s}j\alpha\iota \mathrm{i}$.

$\mathfrak{n}\mathrm{u}\mathrm{m}\mathrm{b}\mathrm{e}\mathrm{r}\circ \mathrm{f}\rho ro\mathrm{P}^{er\mathrm{e}\mathrm{q}\mathrm{q}\mathfrak{P}}\mathrm{u}\dot{\mathrm{i}}\mathrm{v}\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{n}\mathrm{c}\{\mathrm{i}\mathrm{u}\mathrm{Q}\Gamma \mathrm{i}\mathrm{C}$$2 \overline{O}(t(n\rangle\rangle=\bigcup_{k\geq}0O(\iota(n)1o\mathrm{g}k(\iota(n\}))$.

]$\mathrm{a}\mathrm{l}\cdot \mathrm{l}_{0\backslash \mathrm{V}(\mathrm{r}}’ \mathrm{b}\mathrm{o}\mathrm{u}\mathrm{l}\downarrow(1$on$\mathrm{t}.\mathrm{h}(\mathrm{i}$131moreover, that even so does the classby searching
short parity functions.
1989, Linial and Nisan [9] showed positive andnegative results about
nating the indusionexdusion formula by a linear combination of the sizesof short intersections. Our analysis is built on some oft.heir results.
Our positive results for approximating and learning
DNF are:$\mathrm{A}\mathrm{C}^{0}$$\mathrm{h}\mathrm{l}$$\mathrm{a}\mathrm{p}\mathrm{p}\mathrm{r}\mathrm{o}.\mathrm{X}\dot{\mathrm{u}}$hypothesis class $H$ within accuracy 1and confiif for any $f\in C$ the algorithm, given acdence
cess to random examples $(x, f(x))$ , outputs $h\in H$ thatwith probability at leastachieves.
$-\dot{\tilde{\mathrm{c}}}$$\mathit{1}-\delta$$1-\delta$$\mathrm{a}\mathrm{c}\mathrm{c}(h)\geq 1-\epsilon$

The PAC model is an abstraction of practical situaraIlclQm extions where machines learn from theirperiences. Most of all, it assumes that tlle t.raining rx) .
amples are perfectly consistent with the
Empirical datum, however, involve inevit,uble(i.e. inconsistency) due to inaccuracy insystems, intervention by malicious adversaries, llncertainty of the nature, and so on. Under such practicalsituations, the training examples $(x,y)\in X\mathrm{x}Y$ are no.
more consistent with the target
andSchapire [7], and Haussler [5], ilssuIntlcl that they
governed by an unknown joint-distribntion over the obY. Thus aexarnple $(x, y)$servation space
may differ from $(x, f(X,))$ with probability
Probx, $y\{f(_{X})\neq y\}$ .
$\mathrm{o}\mathrm{w}\mathrm{u}$$\mathrm{t}_{\dot{C}}\mathrm{t}\Gamma \mathrm{g}\mathrm{t}^{1\mathrm{t}_{\mathrm{C}\mathrm{o}}\cdot.\mathrm{t}}\mathrm{n}\mathrm{C}\mathrm{c}\mathrm{t}$$‘\cdot \mathrm{r}\iota\cdot \mathrm{o}\mathrm{r}\mathrm{s}$Theorem 1.1. For any -term DNF formula . andany distribution over the instance space $X$ there exists
conjunction that satisfies
a
$f$

$s$

$h$

$\mathrm{s}\mathrm{i}_{\mathrm{Z}}\mathrm{e}\cdot o(\sqrt{n}\log s)$$|\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}x\in X\{f(X)=h(x)\}-1/2|--- 2^{-o()}\sqrt{n}\log n\log \mathit{8}$.

$\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{S}\mathrm{u}\mathrm{I}\mathrm{e}\mathrm{n}\mathrm{l}\mathrm{P},\mathrm{n}\mathrm{t}$$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{c}\cdot,1\backslash .1^{J\mathrm{t}}f$$\mathrm{I}\{_{arrow}‘\backslash \mathrm{a}\mathrm{r}\mathrm{n}\mathrm{s}$$\mathrm{a}\mathrm{I}C^{1}$

Theorem 1.2. Any naive search algorithm, cooperating with general boosters, PAC lcarns the class DNF) time with respect to any distribution.
in$2^{o(}\sqrt{n}\langle\log n)^{2}$

Note that if we arlopt Reund’s booster [4], thenfor a given DNF formula and a given distribution, theoutputs as a highly accurate hypothesis amajority-vote of Boolean conjunctions of size at most$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\iota \mathrm{n}$.
Our negative result is:$O(\sqrt{n}\log n\log s)$$X\mathrm{x}$$\mathrm{r}\mathrm{a}\iota 1(1_{\mathrm{o}\mathrm{I}11}$$\in X\mathrm{x}\mathrm{Y}$Angluin and Laird [3] introduced so-called thewhite noise into the target distribution. The joint$\leq’?\leq$
distribution has the white noise of rate ,$1/2$ , if it is the production over $x\in X$ of the identical
distributions over that satisfies$Y$

Theorem 1.3. For
Boolean conjunction $f$ ofand any constallt $0\leq\epsilon\leq 1/2$ there exlengthist
and a joint-distribution oversuch that we havefor ally Boolean
andfunction $h:\{0,1.\}^{n}arrow\{0,1\}$ that depends on at mostvariables.

$()$$\eta$$=\eta$$\mathrm{P}\iota\cdot \mathrm{o}\mathrm{b}y\in\gamma;f(x)\neq y\}$.

$\dot{\mathrm{e}}\mathrm{u}\mathrm{l}\mathrm{y}$$\ominus(n)$$X\mathrm{x}\mathrm{Y}$$k=\Omega(\sqrt{n\epsilon})$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{(\mathrm{a}\cdot,y)}\epsilon X\cross \mathrm{Y}\{f(X)=y\}\geq 1-c$

Definition 2.2. We say that a PAC illgoritllm tolerates the white noise of rate if it PAC learns under
any distribution llaving the white noisc of rate .
$\eta$$\eta$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{()\epsilon}x.y.\backslash _{\mathrm{X}}\cdot Y\{h(x)=y\}=1/2$$k$

All of the discovered

derrainover
pend on some statisticaling exalnples, rather than the point.-wise)
illto theof them. Keanls [6] bound theseAn
Queryalgorithms.
learningofnotionStatistical-algorithm asks to the query of tlle probability
for a predicate
the-oracle. The SQ-oracle
observation space to theof it wit,hin error ,tllen returns an estimation est
hence it satisfies$\mathrm{n}\mathrm{o}\mathrm{i}\mathrm{s}\mathrm{e}-\mathrm{t}\mathrm{o}\mathrm{l}\mathrm{e}\mathrm{l}\cdot \mathrm{a}l$)$\mathrm{l}\mathrm{e}i1$]$\mathrm{g}\mathrm{l}\mathrm{r}\mathrm{i}\mathrm{t}1_{1}\iota 11.\aleph$informatiol)}$\mathrm{f}1_{1}\mathrm{f}$$\mathrm{i}11\mathrm{f}\mathrm{c}_{\grave{j}\mathrm{r}}1\iota 1\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}$Therefore, under such a joint-distribution, a naive
search algorithm must enumerate at least
number of symmetric func,tions until finding adecision-rule that is better than guessing at ranPAC model, where
dom. Note that in the, any Boolean conjunctinle by searching orllytion can be learned in$2^{\Omega(\sqrt{n\xi}\mathrm{g}n\mathrm{I}}\mathrm{l}\mathrm{o}$$\mathrm{s}\mathrm{t}‘\tau \mathrm{n}\mathrm{d}\mathrm{a}\mathrm{r}\mathrm{d}$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{(\nu)X}x,\in\cross Y\{f(x)=y\}=1$$O(n1o\mathrm{g}n)$li.teralS [12].

$\mathrm{a}\mathrm{l}\mathrm{g}\mathrm{t}\Gamma \mathrm{i}\{\mathrm{l}\mathrm{m}$$\mathrm{S}\mathrm{Q}$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x},\{yX(x, y)=1\}$$\chi(\mathrm{l}\mathrm{e}\mathrm{f}\mathrm{i}\mathrm{n}\rho \mathrm{d}\mathrm{e})\backslash (\mathrm{l}\mathrm{r}$$\mathrm{S}\mathrm{Q}$$(\chi)$$\tau$$|\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x.y}\{x(x,y)=1\}-\mathrm{e}\mathrm{S}\mathrm{t}(\mathrm{x})|\leq\tau$

2. Learning Frameworks

Where $0\leq\tau\leq 1$ is a constant para.
wit.h the-oracle called the$\mathrm{S}\mathrm{Q}$A formal definition for a PAC algorithm requuires twocalled the accu racy andreal parameters
algorithm, respectively.
oftheparalllQt‘},rs
confidence
Let $C,$ $H$ be cl&‘;ses of functions kom the instance spac.
$X$ to the outcome space Y.
$0\leq\epsilon,$ $\delta\leq 1$.

$\mathrm{e}$Deflnition 2.1. A randomized algorithm is called a
PAC algorithm that learns the target class by the$C$$\mathrm{s}’$$\mathrm{o}\mathrm{r}\mathrm{a}(.\mathrm{J}\mathrm{e}$.

$\mathrm{n}1P.\mathrm{t}‘:\mathrm{r}j\iota.\backslash .\eta \mathrm{o}\mathrm{c}\mathrm{i}\dot{C}\mathrm{t}\mathrm{l}\mathrm{e}\mathrm{d}$$\mathrm{t}\mathrm{o}\mathrm{l}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{r}1(i^{1}‘$.

of$\mathrm{I}_{2}11\rho$SQ-

is defined ;its in
Deflnition 2.3. An
insteadDefinition 2.1 by given ac,cess to theof the random training exarnples.
$\mathrm{S}\mathrm{Q}- \mathrm{a}\mathrm{l}\mathrm{g}\mathrm{o}\mathrm{r}\mathrm{i}\mathrm{t}\mathrm{h}\iota \mathrm{n}$$\dot{\not\subset}\mathrm{t}‘$$\mathrm{S}\mathrm{Q}-o\mathrm{r}\mathrm{a}\mathrm{t}\cdot\iota \mathfrak{t}1$

Theorem 2.4. (Kearns [6]) If a class $C$ is SQ
ble by a class $H$ within accuracy $1-c$ and confiden$1\mathfrak{t}^{\backslash }\dot{c}n\cdot 1?-$.a.

$‘:\mathrm{e}$132

1–6 from the oracle of tolerance in $O(t)$ time, thenwithin ,curacy 1 $-\xi$ andis PAC learnable bynoise of rate inconfidence 1–6 under the$\tau$$H$$C$$(’1)$$=0_{\backslash ’1\mathrm{I}\leq} \sum_{ks}\alpha_{1}\mathrm{A}\cdot‘’ n\llcorner \mathrm{i}|||\bigcap_{i\in.9}A;||_{D}$$\mathrm{a}\mathrm{c}$$\mathrm{w}\mathrm{h}\mathrm{i}\mathrm{t}_{J}\mathrm{e}$$\eta$$O(t_{\mathcal{T}^{-\mathrm{z}}}(1/2-r’)--21o\mathrm{g}(1/\delta))$time$\iota\cdot,,1$$\mathrm{c}on\mathrm{b}\mathrm{t}_{i}\mathrm{i}\mathrm{n}\mathrm{t}_{\mathrm{S}n_{r}}$The current paper learns Boolean concepts. Thus
instance space isdimension $n=0,1,2,$
forthe -dimensional Boolean cube $X—\{0,1\}^{n}$ and theoutcome space is $\mathrm{Y}=\{0,1\}$ , so target concepts andfunctions. Learning algorithms
hypotheses areare assumed to know the paranieters so far appeared;andthe dimension of the instance space, theconfidence parameters, the rate of ) whilte noise, andthe tolerance of the SQ-oracle.
$\ldots \mathrm{t}\}_{1}\mathrm{e}$$\mathrm{e}\mathrm{a}\mathrm{c}\Lambda$

exLinial and Nisan described these
of
the
of
plicitly in terms
polyrloInial of degree . In special. t,heir description$n$$\mathrm{B}_{\mathrm{o}\mathrm{O}}1\mathrm{e}\mathrm{a}11$$\mathrm{a}\mathrm{c}:\mathrm{C}\mathrm{u}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}$$\nu\iota$$\mathrm{t}\mathrm{l}$$\mathrm{e}$$\mathrm{c}\mathrm{o}\mathrm{e}\mathrm{f}\mathrm{f}\mathrm{i}_{\mathrm{C}}\mathrm{i}\epsilon i\mathrm{n}\mathrm{t},\mathrm{s}$Form.ulae.

$\mathrm{d}\mathrm{e}\iota\cdot \mathrm{i}_{\mathrm{V}}\mathrm{e}\mathrm{s}|\alpha_{i}^{k,n}|<2^{k}$

Theorem 3.2. (Linial and Nisan [9]) For any in, whereis a certain contegers
space (X, . ) andstant, there exist a,,andcollections of sets
we have both$n\geq 1\mathrm{a}\mathrm{J}\mathrm{l}\mathrm{d}k\leq c_{2}.\sqrt{n}$$\mathrm{r}_{arrow}.\supset$$\Sigma$$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{a}\mathrm{b}\mathrm{i}\mathrm{l}\mathrm{i}\mathrm{t}_{}\mathrm{y}$$A_{1},$$\ldots$$A_{n}$$B_{1},$$D$$\mathrm{t}_{r}\mathrm{w}\mathrm{o}$$B_{\downarrow \mathrm{Q}},‘ \mathrm{u}(:\}1\mathrm{t}.\}1backslash \mathrm{t}$$\ldots$’

Approximating Inclusion-Exclusion

3.

$\mathrm{t}1_{1(}\lambda \mathrm{C}\mathrm{h}p\mathrm{b}\backslash .\mathrm{S}\mathrm{h}\mathrm{g}\mathrm{v}$$k$$\backslash ^{2)}$$\frac{||\bigcup_{\mathrm{z}1}^{n}=Ai||_{D}}{\mathfrak{l}|\bigcup_{\mathrm{i}1}^{n}=B_{i}||_{T)}}=\Omega(\frac{\gamma_{l}}{k\underline’)})$

andOur positive and negative results for lcarning DNF(3)$||_{is} \bigcap_{\epsilon}Ai||_{i\in}\bigcap_{S}B..i||_{p}$are built on positive and negative results for approx-

imating tlle inclusion-exclusion formula, respectively,
established by nial and NisaIl [9]. For a given family, the inclusion-exclusion formulaof sets
the union size by the sizes of theon theIuintersections of all the subfamilies.

for all the nonempty sets $S.\subseteq\{1, \ldots, n\}$ with $(!<|S|$$\mathrm{L}i$$\{A_{1}, \ldots , A_{n}\}$$n$$\mathrm{m}\mathrm{e}\mathrm{a}\mathrm{S}\mathrm{u}\mathrm{r}\mathrm{t}^{\mathrm{B}}.\mathrm{s}$$\mathrm{q}S$$\leq k$.

4. Learnability of DNF} section we show how to derive learning DNF
in subexp nential time from Theorern 3.1.
that t,heWithout loss of generality, we may
constant function is always contained ill tllet,o ttoeof a given DNF formula. Then it is)someapproximatedany DNF formula can be weakly
terms.

In$||A_{1^{\cup}}A_{2n}\cup\cdots\cup A||=$$\mathrm{t}\mathrm{h}\mathrm{i}_{\backslash }‘$$\mathit{0}$$\sum_{:}||A4:||-\sum_{<ij}||A_{i^{\cap}}\Lambda_{j}||$$\mathfrak{B}\mathrm{b}\mathrm{l}\mathrm{l}\mathrm{I}11e$$0$$\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{n}\iota \mathrm{s}$$\mathrm{f}_{}\mathrm{h}\mathrm{a}\iota$$+ \sum_{ji<<k}||.4_{i}\cap A_{j^{\cap}}A_{k}||$$\mathrm{e}\mathrm{a}\mathrm{s}_{\vee}\backslash \cdot$$|$$\mathrm{v}$-.

$..+(-1)^{n}||A_{1}\cap A2\cap\cdots \mathrm{n}A|’||$.

Linial and Nisarl asked to approximate the union sizeby using only initial terms of them, in other words, by
only the sizes of the “short” intersections. They transof approxiniating a
lated the ploblenl into acertain discrete delta function by low degree polynomials, where the sizes of the intersections correspond to
the degrees of the polynomials. We state two of
results in a general probability space (X, $D$ ) where$X$ is any set,
is a -field over $X$ and $D$ is a probability me,asure over (X, ). We denote the weight, of a

Lemma 4.1. For any size-s DNF formula andthere exists a
distribution over tlle instance spaceterm of that satisfies
$f$

$g$

$f$

$\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}\mathrm{l}\mathrm{e}\ln$$\mathrm{t}\mathrm{l}\mathrm{l}\mathrm{e}\mathrm{i}\mathrm{r}$$\Sigma,$$\Sigma$$\sigma$$\ddot{t}\iota \mathrm{n}\mathrm{y}$$-\mathrm{X}’$$|\mathrm{p}_{\mathrm{r}\circ}\mathrm{b}_{x\in}X\{f(X)=q(x)\}-1/2|>1/104\}$

Proof. We suppose that there is
will derive a contradiction. Inverting

(4)

of .
) fur derives$11\mathrm{o}_{\mathfrak{d}}\mathrm{u}\mathrm{t}j1_{1}\mathrm{t}_{1\mathrm{I}}s\cdot \mathrm{n}1$$\acute{(}4$.
$f$$j\downarrow 11\prime 1$$0$$|\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x}\{f(x)=0\}-1/2|\leq 1/10s$$\Sigma$set$A\subseteq X$

by$||A||_{\mathrm{p}}=\mathrm{P}\mathrm{l}\mathrm{o}\mathrm{b}_{x\in}x\{x\in A\}$.

and Nisan [9]) For any inTheorem 3.1. (is a certain, whereandtegerssuch
constant,
exist constants)and every
that for every probability space (X,we havecollection of sets$\mathrm{L}\ddot{\mathrm{m}}\mathrm{a}\mathrm{l}$$n,$$\geq 1$

$k\geq c_{1}\sqrt{n}$$\alpha_{1},$$\ldots,k,n\alpha_{k}$$\Sigma.T$$A_{l},$$|\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}.\iota\{f(X)=1\}-1/2|\leq 1/10s$$c_{1}/\backslash \mathrm{o}$$\alpha_{2}knk,n,$$\mathrm{t}" \mathrm{h}\mathrm{e}\mathrm{r}\mathrm{e}$or equivalently
For any term$g$.

of $f,$ $g(x)=1$ forces $f(x\cdot)=1,$

(5)

$)$

$\mathrm{p}_{\mathrm{r}\mathrm{o}}\mathrm{b}_{x}\{\mathit{9}(X)=1\}=$$\ldots,A_{n}$$\mathrm{p}_{\mathrm{r}\circ}1)x\mathrm{f}f(x)=]\}-\mathrm{p}\mathrm{r}(\mathrm{J}\mathrm{b}_{I}.\mathrm{t}f(.\cdot r)\neq(/(_{l.\grave{)}}t.\cdot\}$$\leq 1/2+1/10\theta-(1/2-1/10s\rangle$$(1. \pm O(e^{-2}/\sqrt{\mathfrak{n}})k)||\bigcup_{i=\mathrm{J}}^{1?}Ai||_{D}$,$\leq 1/5s$.

,$\mathrm{h}e.11\mathrm{e}\cdot\epsilon\backslash$

133

However, $f(x)=1$ forces $g(x)=1$ for some term 9 of
, so we obtainso frorn (6) and

we obtain$|\mathrm{c}\mathrm{o}\mathrm{r}(f,g)|=|\mathrm{c}o\mathrm{r}(f,\overline{g})|$

$f$

.

(7)

$|\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{t}\mathrm{S}_{f}(\overline{g})|>1/10s-\gamma$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x}\mathrm{t}f(x_{J})=1\}$

Let $A_{i}=$$\underline{<_{\backslash }}$$\{((a_{1}, \ldots , a_{\mathit{7}1}), 1)\in X\cross 1’ :a_{\mathrm{i}}=1\}\mathrm{a}\mathrm{n}(1$. Let $k=$
for a constaIlt $c_{4}>0$ andtarget distribution over $X$ . Theorem 3.1
writesbias
as alinear combination over tho biases of:conjunctions$\sum_{g}\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x}\mathrm{t}g(X)=1\}$$B_{i}---\{((a_{1}, \ldots, an),0)\in X\mathrm{x}Y:a_{\mathrm{i}}=1\}$$c_{4}\sqrt{\tau\iota}\log s$$\leq$$\sum_{g}1/5s=1/5$ .

$P]_{)\mathrm{t}}\backslash \mathrm{t}1_{1\langle^{\backslash }}\mathrm{g}\mathrm{i}\iota^{\vee}\mathrm{t}11$$\mathrm{t}\iota_{1\mathrm{e}}\mathrm{I}1$$.\mathrm{s}\mathrm{l}_{\mathrm{l}\mathrm{O}}\mathrm{r}\mathrm{t}$$J(\overline{\mathit{9}})$This contracts (5).

$h_{S}= \bigwedge_{i\in s^{X_{i}}}$$\square$Due to Theorem 3.1, a conjunction thatDNF formula provides a Inuch shorter
conjunction that still approximates theto someextent.

biae$\mathrm{a}_{1^{)}\mathrm{P}^{\mathrm{r}}}o\mathrm{X}\mathrm{i}-$lYlates the$=$$f(\overline{g})$$|| \bigcup_{i=}^{n}1Ai||_{\tau},$$-||\cup^{n}j--- 1Bj||t\supset$$\mathrm{t}_{t}\tau \mathrm{r}\mathrm{g}\mathrm{e}\mathrm{t}$$0<|S| \sum_{\leq k}\alpha \mathrm{t}\mathrm{I}^{s\mathrm{I}}|’\iota|k.A_{i}\bigcap_{\mathrm{i}}\in s||D$$\mathrm{t}_{J\mathrm{a}r\mathrm{g}\mathrm{e}}\mathrm{t}$$-|| \bigcap_{t\in S}B_{i}||\mathrm{D})\pm Q(C-2k/\sqrt{?l})$$F:Xarrow Y$ aud
functi
Deflnition 4.2. For
to (with realty distribution over $X$ , the bias of) isspect to the$o\mathrm{n}\mathrm{s}f,$$\not\subset\iota\prime \mathrm{n}_{\}^{f}}$F.

$\mathrm{d}\mathrm{i}_{\mathrm{S}}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{b}\mathrm{u}\mathrm{t}\mathrm{i}_{0}\mathrm{r}|$bias $f(F)$$=$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{\mathrm{r}}$

$f$

$=$
$0<|s \sum_{k|\underline{\backslash ’}}\alpha_{\mathrm{I}\mathrm{I}}\mathrm{S}/k\dot{S}n_{\mathrm{b}\mathrm{i}\mathrm{a}}(l_{t_{\backslash }}\backslash \cdot.\rangle${ $F(x)=1$ A $f(x)=1$ }$\pm o(e-2k/\sqrt{n})$ ,$-\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x}\{F(x)=1\wedge f(x)=0\}$$\mathrm{T}\mathrm{h}\epsilon \mathrm{r}\mathrm{e}\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{e}$and the correlat,ion of $f$ and $F$ is

we obtain

if we cho$o\mathrm{s}\mathrm{e}c_{4}$large$\mathrm{e}\iota 10\iota^{\}}1$

.

then

bias

$\mathrm{c}o\mathrm{r}(f, F)=\mathrm{p}_{\mathrm{r}\mathrm{o}}\mathrm{b}_{x}\in.\mathrm{v}\{F(x)=f(x)\}-1/2$$\mathrm{f}\mathrm{r}\mathrm{o}\mathrm{l}\dot{\mathrm{l}}1\{7)$$\int(h.\mathrm{s}\rangle$$(1 \pm o(1))\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}_{f}\mathrm{t}_{\overline{\mathit{9}}})=0<|S|\sum_{\leq k}\alpha \mathrm{A}n|S\mathrm{I}$.

Lemma 4.3.
$\mathrm{b}\mathrm{i}\mathrm{a}.\mathrm{s}J(F)\backslash =\mathrm{c}o\mathrm{r}(f, F)-\mathrm{c}\mathrm{o}\mathrm{r}(f,0)$Thus (7) indicates that one of tlles
satisfies.

Proof.
bias $f(F)$$(1\pm o(1))4^{-/.\prime}!|\})\mathrm{i}\mathrm{a}\mathrm{s}_{!(\tilde{y}})|$$\geq$$|\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}_{f}(hg)|$$=$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}l\{F(x)=f(x)\}$$-\mathrm{p}\mathrm{r}\mathrm{o}\mathrm{b}_{x}\{f(x)=0\}$$2^{-\mathit{0}}(\sqrt,.\log n\log$

$=$
$=$

‘
so if we choose large enough thenthe required lower bound on the corelat.icjn of and$\mathrm{L}\mathrm{e}.\underline’ \mathrm{l}\mathrm{n}\mathrm{l}\mathrm{a}4.3\mathrm{d}$cort$f,$ $F$)$-\mathrm{C}\mathrm{o}\mathrm{r}(f,0)$$\mathrm{I}^{\cdot}\mathrm{i}\mathrm{V}l^{\}}\mathrm{S}$$c_{3}$.

$f$$h_{\mathrm{b}^{\backslash }}.$:

$2^{-o(\mathrm{l})}\sqrt{n}\mathrm{l}\mathrm{o}\mathrm{g}’ 1\mathrm{o}\mathrm{g}s-\gamma$$\square$$|\mathrm{c}\mathrm{o}\mathrm{r}(f, hs)|$$\geq$

Now we prove Theorem 1.1.
$\mathrm{p}\mathrm{r}\mathrm{o}\backslash \prime \mathrm{i}\mathrm{d}\mathrm{e}\mathrm{S}$$\mathrm{c}\mathrm{o}\mathrm{n}$

$f$

($J$

as

,

$\square$

Theorem 1.1

$f$

is SQ
Corollary 4.4. Any ize-s DNF )learnable by either a BooleaIl conjunction or a(nlog ) within accuracy 1/2
tion ofan confidence 1 from the SQ-oracle” Iog 9)) intime.
of tolerance$\mathrm{f}\mathrm{C}$$\mathrm{f}i$$|\mathrm{c}\mathrm{o}\mathrm{r}(f,g)|’\backslash 1/10s$.

(6)

We may assume without loss of generality that $g(x)=$A .
A
Iog $n\log*$ for aconstallt,.
Set
as
We may assume that is not correlated with$\overline{x}_{2}\wedge\cdots$$\overline{x}_{n}$$\gamma=2^{-c\theta^{\sqrt{n}}}$$\mathrm{p}\mathrm{o}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{V}\mathrm{e}$$c_{\theta}$$\mathrm{r}1\mathfrak{U}\dagger 11l\prime 1f$$\mathrm{d}\mathrm{i}\mathrm{s}\mathrm{j}\backslash \mathrm{u}\mathrm{l}\mathrm{c}-$$\mathrm{s}\mathrm{i}_{\mathrm{Z}\mathrm{e}-}O$$\sqrt{n}\log$

$+$

$s$

$2^{-o(\sqrt{n}0}\mathrm{l}\mathrm{g}n\log\epsilon)$$\mathrm{d}$$2^{-^{o(\sqrt{n}0}}\mathrm{l}\mathrm{g}n\log s$$2^{o(\sqrt{\iota}1_{\mathrm{t})}\mathrm{g}}$$\mathrm{t}$

$f$

$0$

$|\mathrm{c}\mathrm{o}\mathrm{r}(f,\mathrm{o})|<\gamma.$.

$2^{-o(\sqrt{n}\mathrm{o}\mathrm{g}}\mathrm{l}n10_{\mathrm{I}i^{\theta)}}$$=$aProof of Theorem 1.1. Lemma 4.1
junction that is a term of ancl correlated with$\overline{x}_{1}$,$(\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x}\{p(X)=f(x)\}-1/2)$$-(\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x}\{f(x)=0\}-1/2)$$—$.

$e\mathrm{r}_{-}\mathrm{o}11\mathrm{j}_{\mathrm{t}11}1\mathrm{t}:\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}h_{9}$LerYlIIla 4.3 then yields

Proof. For $k=O(\sqrt{n}\log s),$a size-k conjumction that satisfies$\mathrm{T}\mathrm{h}\mathrm{e}\mathrm{o}\mathrm{r}\epsilon!\mathrm{n}\mathrm{t}1.1$$h$$|\mathrm{b}\mathrm{i}\mathrm{a}\mathrm{s}_{f}(\overline{\mathit{9}})-\mathrm{C}\mathrm{o}\mathrm{r}(f,\overline{g})|$

$=$

$<$

$|\mathrm{c}\mathrm{o}\mathrm{r}(f,0)|$$\gamma$.

$h)|=2^{-o(0}\sqrt{n}\mathrm{l}\mathrm{g}’\iota\iota_{)}‘\iotarightarrow_{/}^{4}$$|\mathrm{c}\mathrm{Q}\mathrm{r}\mathrm{t}f,$.

guarantees

134) sufHence choosing the tolerance
ficiently small, the naive search algorithm finds a conSQof size at most after at mostqueries that satisfies$\tau=2^{-o(\cdot\epsilon}\sqrt{\prime}\log n\log$$k$$\mathrm{j}_{\mathrm{l}\mathrm{m}\mathrm{C}\mathrm{t}}\mathrm{i}\mathrm{o}\mathrm{n}h$)andthat contain all ofdefined over $U\cup V$ . We can moreover ($B_{i},$$A_{:}$$\mathrm{t}^{\gamma}$$\epsilon^{\backslash }.\mathrm{c}\mathrm{t}\mathrm{i}\backslash ’\cdot\iota^{\backslash }$$\mathrm{r}\mathrm{e}\mathrm{s}\iota$] , and$\mathcal{E}$$\mathrm{y}$$j11(\mathrm{O}.\mathrm{q}\mathrm{e}U$

is

aig

$(_{k}^{1\mathrm{t}})2^{k}$$|\mathrm{e}\mathrm{s}\mathrm{t}(f=h)-1/2|=2^{-o(0}\sqrt{n}\log\hslash \mathrm{l}\mathrm{g}t)$so$|\mathrm{C}\mathrm{o}\mathrm{r}(f)\iota’)|=2^{-o(\sqrt{n})}\log n\log$,and adjust$h$$\overline{h}$$\iota\}_{1\mathrm{e}\mathrm{a}}\mathrm{C}(.’and$\mathcal{E}$so to satisfy.

$(^{\{}\mathrm{J})$that
We denote for any set—B and $B^{()}=$$=U-A$ . Similarly, foriIlcljlsio\iotal,$V-B$ . Rom (9) and thewe can extend (3) to$d1^{1}=-l\mathrm{a}\mathrm{n}(\downarrow.4^{0}$$A\subseteq U$$B\subseteq V,$$B^{\mathit{1}}$$1n^{t};\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{f}o\mathrm{r}\mathrm{m}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{a}$(10)\mathrm{U}\mathrm{r}\mathrm{a}\mathrm{c}\mathrm{y}$$||_{i\in s} \mathrm{n}Aia:||.\cdot\bigcap_{\epsilon s}B_{\dot{i}}a_{\mathrm{i}}||_{\mathfrak{i}}$,Theorem 4.5. (Schapre [11], Feund [4]) Givenan -algorit,hm that learns by $H$ within accuracy$1-\epsilon_{0}>1/2$ and confidence
from the SQ-oracle
time. Then for any accuracyof tolerance inconfidence parameters and , respectively, one
learns by $H$ fromc.an design an -algorithm
time polynomial-oracle of torelance
the
.
and
in
$C$

$\mathrm{S}\mathrm{Q}$$V$$||U||_{\mathcal{E}}=\cdot||\mathrm{I}^{j}||_{\xi}$.

If $f=h$ happens more certainly thall $f\neq_{-}h$ then thenaive search algolithm output,s itself, otherwise its
negation that is represented by a disjunction due tothe De-Morgan rule. ロ

Now we let a general booster improveof the naive search algorithm.

(8)$\bigcup_{i=1}^{n_{\mathrm{o}}}A_{i}=U$$1-\delta_{0}$withfor any nonempty set
and any $a:\in\{0,1\}$ with $i\in S$ .
Now we define ajoint-distribution over$0<|.\dot{‘};|\leq$$S\subseteq\{1, \ldots,n_{\mathit{0}}\}$$k$$X\mathrm{x}Y$by$O(t\grave{)}$$\tau$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x},\{y(X_{1}, \ldots, x_{n0},y)=(lJ_{1\cdots\cdot\cdot n}(,0\mathit{0}\rangle\}$$\delta$$\dot{‘}\mathrm{u}\mathrm{l}\mathrm{d}$$\epsilon$$t,$$\iota\iota,$$\tau \mathrm{w}\mathrm{i}\mathrm{t}\mathrm{I}_{\mathrm{l}\mathrm{i}\mathrm{n}}$$(1/2-\epsilon 0)-1,1/\delta_{0},1/\epsilon$$=\alpha||\mathrm{n}_{\mathrm{i}=^{0}1}^{n}A^{a_{i}}i||_{\mathcal{E}}$$C$$\mathrm{t}1_{1}\mathrm{a}\mathrm{t}$$\mathrm{S}\mathrm{Q}$$\mathrm{S}\mathrm{Q}$$\log(1/\delta)$

and$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{2},\{\nu(X_{1}, \ldots , x_{n_{\mathrm{O}}},\prime l\mathit{1})=(a_{1}, \ldots.a_{n_{\mathrm{O}}}, 1)\}$

We apply this boosting theorem to Theorem 4.4 alldobtain:$– \sim\alpha||\bigcap_{i=1}^{n_{0}}B_{i}a.||\epsilon$

is thefor any $a=$.
constant for normalizing , hence
Now we check that this distribution satisfies$(a_{1},a_{2}, \ldots , a_{n_{0}})\in\{0,1\mathrm{I}^{l0}’\cdot\backslash 4^{\cdot}1\iota \mathrm{e}\mathrm{r}\mathrm{e}$Corollary 4.6. -term DNF is SQ learnable Rom the) in time pol.v-oracle of),.
andnomial in$s$$\mathrm{t}\mathrm{o}\mathrm{l}\mathrm{e}\Gamma \mathrm{a}\mathrm{n}\mathrm{c}:\mathrm{g}2^{-o(\sqrt{n}0}\mathrm{l}\mathrm{g}n\log\epsilon$$\mathrm{S}\mathrm{Q}$$2^{o(\mathrm{l}n}\mathrm{v}^{\prime_{\overline{n}}}\mathrm{o}\mathrm{g}\log\iota$$a$$\alpha(||\mathfrak{c}^{-}||-\vdash||\iota’|\mathrm{I})=1$$\mathcal{E}$$\log(1/\delta)$$1/\epsilon$$\mathrm{P}1^{\cdot}o\mathrm{b}_{\mathrm{t}y)Y}\epsilon X\mathrm{x}\{\approx,f(X)=y\}>1-\epsilon$

Applying Theorem 2.4 then derives:,andCorollary 4.7. -term DNF is PAC learnable under the white noise of rate in time polynomial in
Iog ) $(1/2-\eta)-1,1/\epsilon$.
.
and$\mathrm{p}_{\mathrm{r}\mathrm{o}}\mathrm{b}_{()XY}x,y\in Y\{h(\mathrm{J}:)=y\}=\mathrm{I}/2$$(^{\rceil}, 1)$

(12)

$s$

$\eta$$2^{O(\sqrt{n}\mathrm{g}n}1_{t}l$$\epsilon$$1_{\mathrm{C}\supset}\mathrm{g}(1/\delta)$

Theorem 1.2 is now obtained by putting$\eta=0$ and $1/\epsilon=1/\delta=O(1)$ .

$s=\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}(n)$,for any Boolean function$h:\{0,11’1arrow\{(), 1\}\mathrm{t}\mathrm{h}\mathrm{a}_{\iota}\mathrm{d}\epsilon:-$. We begin wltll establishpends on at nlost
ing (12) for the special case that $h=0$ . From (8) and(9)$k_{\mathrm{V}\mathrm{a}}\mathrm{I}\mathrm{i}\mathrm{a}\mathrm{b}\mathrm{l}\mathrm{e}\mathrm{s}$$\mathrm{p}\mathrm{r}\circ \mathrm{b}_{l}.\{yy=0\}$.

5. Unlearnability of DNF$=|| \bigcup_{i=}^{n\mathrm{o}_{1:}}A^{a}.||_{L}$(13)$=1/2$

Finally, we show that Theorem 3.2 derives Theo-rem 1.3.

If we ch ose$\mathit{0}$$k$sufficiently small then (2)$\mathrm{i}\mathrm{t}1\mathrm{l}1)1\mathrm{i}(s_{1}\backslash$$\mathrm{P}\mathrm{r}\mathrm{o}\dot{\mathrm{b}}_{\mathrm{f}},\{yf(X)=\mathrm{t})\wedge y--^{\mathrm{o}}\cdot\}$

Proof of Theorem 1.3. We may assume without loss
for $n_{0}=$of generalitJy that
. Theorem 3.2 gives a distribution and two colthat satandlections of se,ts
isfy bothand (3). Without loss of generality, weof disjoint universal sets andmay assunie$\overline{\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x},\mathrm{t}yf(X)=0\wedge|/=1\}}$$f(x)=\overline{x}_{1}\wedge\overline{x}_{2}\wedge\cdots\wedge\overline{x}_{n_{\mathrm{O}}}$$\Omega(n)$.

$= \frac{\alpha||\bigcup_{\mathrm{i}}^{\underline{\underline{\iota 0}}_{1}}d4_{i}||_{\vee}\mathrm{t}^{\backslash }}{\alpha||\bigcup_{\mathrm{i}=}^{n0}B?|1|\grave{\mathrm{t}}\sim},.$$\mathcal{E}$$A_{1},$$\ldots.A_{n_{\mathrm{O}}}$$B_{1},$$\ldots 4B|\mathrm{t}_{0}$$>\Omega(Jl/k2)$$(2)\backslash$$\mathrm{e}\mathrm{x}\mathrm{i}_{\mathrm{S}\mathrm{t}}t\mathrm{e}\mathrm{n}\mathrm{C}.\mathrm{e}$$U$$>1/\epsilon$

.

.

135

From (8) $f(x)=1$ implies $y=1$ , hence[7] M. Kearns and R. Schapire.
learning of probabilistic concepts.
of the31 th IEBE Symposium on Foundations of Computer
Science, pages 382-391, 1990.
, and N. Nisan. Constauxt[8] N. Linial, Y.
)ilit.v. Proc
circuits, fourier transforrns andings of the 31st IEEB Symposium orl Formdations ofCornputer Science, pages 574–579, 1989.
[9] N. Linial and N. Nisan.
$10:S49- 36_{\iota}’,$ ,
exclusion.
1990.
[10] L. Pitt and L. Valiant. Computational limitatiorls 011
learning from examples. Jourteal of the ACM, .35:965,$\mathrm{E}\mathrm{f}\mathrm{f}\mathrm{i}\mathrm{c}\cdot.\mathrm{i}\mathrm{e}\mathrm{l}\mathrm{l}\mathrm{t}_{\mathrm{C}\mathrm{i}\mathrm{i}}8\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{b}\mathrm{l}\mathrm{t}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{u}-\mathrm{f}\mathrm{r}(*$$p_{oCi\mathrm{i}},.e.din_{\mathit{9}}s$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}x,1’ \mathrm{t}f(x)\neq y\}$$=\mathrm{P}\mathrm{r}\mathrm{o}1)x,y\mathrm{t}f(X)=0\wedge y=1\}$$<\epsilon$$\mathrm{M}*\mathrm{l}\mathrm{J}\mathrm{l}\mathrm{s}\mathrm{o}\mathrm{r}$.

$\mathrm{c}1e_{1^{)}}\{.\mathrm{h}$$1\mathrm{i}^{1}.\mathrm{a}1^{\cdot}\mathrm{h}\mathrm{a}\iota$

Finally we check (12). To any Boolean function
associate its bias as

$h$

we

$e\{:d\sim$$\mathrm{A}_{\mathrm{P}1^{J\mathrm{r}}}\mathrm{o}\mathrm{x}\mathrm{i}_{\mathrm{D}\mathrm{t}\mathrm{a}\mathrm{t}}\mathrm{e}\mathrm{i}\mathrm{u}.\mathrm{c}\mathrm{l}\mathrm{u}\dagger;\mathrm{i}\mathrm{o}\mathrm{n}-$$Combinato’\dot{\mathrm{B}}ca,$$=$$\mathrm{b}\mathrm{i}\mathrm{a}\iota 9(h)$$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}x,y\{h(x)=1, y=1\}$$-\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{x},\{yh(x)=1, y=0\}$

.

1988.

If is a Boolean function tllat depends on a setofforat most variables then letting
call be written
where
and .
$h=
\sum_{A}c_{A}h_{A}$for some integers , so t,he linearlity
asof bias and (10) derive$h$$S_{0}$$k$$A$$h_{A},= \prod_{x.\in S\mathrm{o}i}XA$$x_{i}^{1}=x_{i}$$\in \mathrm{t}^{\mathrm{o},1}\}^{k}$$x_{1}^{0}$$=\tilde{x}_{i},$$h$$\mathrm{c}_{A}$bias $(h)!=$$\sum_{A}r_{A},\mathrm{b}\mathrm{i}\mathrm{a}S(h_{A})=0$,[11] R. Schapire. The strength of weak learnability. f.fa.
chine Leaming, $5(2),.1990$ .
[12] L. Valiant. A theory of the learnable. Communicationsof the ACM, $27(11):1134-1142$ , 1984.
. Pro[13] L. Valiant. Learning disjunctions of
ceedings of the gth lntemational Joint Conference on
Anificid Intelligence, pages 560-566. 1985.
thc uniform dis[14] . Verbeurgt. Learning DNF-polynomial time. Proceedings of thetribution in
Third Annual Workshop on Comp utationd Learning
Theory, pages 314-326, 1990.
$\mathrm{c}\mathrm{o}\mathrm{n}\mathrm{j}\mathrm{l}\mathrm{l}\mathrm{l}\mathrm{l}(\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{S}$$\dot{\mathrm{K}}$$\mathrm{u}\mathrm{l}\downarrow \mathrm{d}\iota 1^{\cdot}$$\mathrm{q}\mathrm{l}\mathrm{l}\mathrm{a}\mathrm{s}\mathrm{i}$hence combining it with (13) yields that$\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{D}\{h(x)=y\}$ロ Thcorem

$=$

bias

$=$

1/2.

$(h)+\mathrm{P}\mathrm{r}\mathrm{o}\mathrm{b}_{\mathcal{D}}\{y=0\}$

1.3

Acknowledgments
to Professor Osam
We would like to
abe for his helpful discussions in the early stage of thisresearch.
$\mathrm{t}\}_{1\mathrm{a}\mathrm{n}}\mathrm{k}$$\Re^{r_{\mathrm{a}\mathrm{t},}}\mathrm{a}11-$

References[1] H. Aizenstein and L. Pitt. On the learnability of disjunctive normal &om forulul\mbox{\boldmath $\delta$}s. Machine earning,
19:183-208, 1995.
[ D. Angluin. Negat,ive results for equivalence quelies.
Machine Lea\prime ni\prime g, 5:121-150, 1990.
[3] D. Angluin and P. Laird. Learning from noisy exarnples. Mach,ine $L\epsilon amin\mathit{9}.\prime 2(4):343-370$, 1988.
[4] Y. Reund. Boosting a weak learning algorithm by,majority. Inforrnation and Computation. 121

Ll$2_{\mathrm{J}}^{\rceil}$$(2\rangle:2^{r}\theta 6$

1995.
[5] D. Haussler. Decision theoretic generalizations of the
PAC model for neural net ‘lIld other learning appliand Computation, 100:78-150,
cations.
1992.
[6] M. Kearns. Efficient noise-tolerant learning ffom stamtistical queries. Proceedings of the 25th
)1,
posiu\prime\prime t on f.he The0\prime y of Computiny, pages
1993.
$Inf_{oma}t.\mathrm{t}:on$$AC_{\mathit{1}}lfS\mathrm{r}j$$392-\cdot 4\mathrm{t}$