Journal of Machine Learning Research 2 (2002) 359-395 Submitted 10/01; Published 02/02

On Using Extended Statistical Queries to Avoid Membership Queries

Nader H. Bshouty bshouty@cs.technion.ac.il Vitaly Feldman felvit@tx.technion.ac.il Department of Computer Science Technion , Israel Institute of Technology, Haifa, 32000, Israel

Editor: Dana Ron

Abstract

The Kushilevitz-Mansour (KM) algorithm is an algorithm that finds all the “large” Fourier coefficients of a Boolean function. It is the main tool for learning decision trees and DNF expressions in the PAC model with respect to the uniform distribution. The algorithm requires access to the membership query (MQ) oracle. The access is often unavailable in learning applications and thus the KM algorithm cannot be used.

We significantly weaken this requirement by producing an analogue of the KM algorithm that uses extended statistical queries (SQ) (SQs in which the expectation is taken with respect to a distribution given by a learning algorithm). We restrict a set of distributions that a learning algorithm may use for its statistical queries to be a set of product distributions with each bit being 1 with probability ρ, 1/2 or 1−ρ for a constant 1/2 > ρ > 0 (we denote the resulting model by SQ–D_{ρ}). Our analogue finds all the “large” Fourier coefficients of degree lower than c log n (we call it the Bounded Sieve (BS)). We use BS to learn decision trees and by adapting Freund’s boosting technique we give an algorithm that learns DNF in SQ–D_{ρ}. An important property of the model is that its algorithms can be simulated by MQs with persistent noise. With some modifications BS can also be simulated by MQs with product attribute noise (i.e., for a query x oracle changes every bit of x with some constant probability and calculates the value of the target function at the resulting point) and classification noise. This implies learnability of decision trees and weak learnability of DNF with this non-trivial noise.

In the second part of this paper we develop a characterization for learnability with these extended statistical queries. We show that our characterization when applied to SQ–D_{ρ} is tight in terms of learning parity functions. We extend the result given by Blum et al. by proving that there is a class learnable in the PAC model with random classification noise and not learnable in SQ–D_{ρ}.

\begin{matrix}c \\ ◯ \end{matrix}2002 Nader Bshouty and Vitaly Feldman.

Nader H. Bshouty and Vitaly Feldman

1. Introduction and Overview

The problems of learning decision trees and DNF expressions are among the most well studied problems of computational learning theory. In this paper we address learning of these classes in Valiant’s popular PAC model with respect to the uniform distribution.^{1} The first algorithm that learns decision trees in this setting was given by Kushilevitz and Mansour [KM91]. The main tool that they used is the beautiful technique due to Goldreich and Levin [GL89]. Given a black box that will answer membership queries for a Boolean function f over {0, 1}^{n}, their technique efficiently locates a subset A of the inputs of f such that the parity χ_{A} of the bits in A is a weak approximator for f with respect to the uniform (if such A exists). The correlation of the parity function χ_{A} is called the Fourier coefficient of A. Using this technique Kushilevitz and Mansour give an algorithm that finds all the Fourier coefficients of a Boolean function larger than a given threshold (it is usually referred as the KM algorithm). They prove that this algorithm can be used to efficiently learn the class of decision trees. Later Jackson [Ja94] again used the Kushilevitz-Mansour algorithm and Freund’s boosting technique to build his famous algorithm for learning DNF expressions. An important property of Freund’s boosting in this context is that it requires weak learning only with respect to distributions that are polynomially close to the uniform.

As we have mentioned the core of both algorithms utilizes membership query (MQ) oracle to find weakly approximating parity function. That is, in order to use these algorithms we need access to values of the learned function at any given point. Angluin and Kharitonov [AK91] proved, under standard cryptographic assumptions, that if DNF expressions are learnable in the distribution-independent PAC model with MQs then they are also learnable without MQs, in other words membership queries are not helpful in the distribution-independent PAC learning model. On the other hand, there is no known algorithm that learns the above-mentioned classes in the PAC model with respect to the uniform distribution without the use of MQs.

On Using Extended Statistical Queries to Avoid Membership Queries

The access to membership query oracle is not available in most of applications and thus the question of whether it is possible to avoid the use of them is of great theoretical interest and practical importance. We investigate the way to reduce the dependence on MQs for the distribution-specific PAC learning that results from the following approach. Learning in the basic PAC model (without MQs) represents learning without any control over the points in which the value of the target function will be known. On the other hand, membership queries represent the total control over these points. Both of these situations can be seen as (totally) different amount of control over the probability that the next sampled point will be some specific x. This observation suggests that we can represent any intermediate situation by allowing the learning algorithm to choose the distribution with respect to which the points will be sampled. The set of distributions D that a learning algorithm may choose from measures the amount of control that the learning algorithm has. Naturally, such an extension defines learnability with respect to a given set of distributions D or learnability in the PAC–D model with respect to D. In this paper we actually discuss SQ–D—the statistical query (SQ) analogue of the above model. The SQ model introduced by Kearns [Kea93] allows the learning algorithms to get “good” estimates of expectation of any (polynomially computable) function involving the value of f(x) with respect to the target distribution D. The major benefit of this restriction of the PAC model is that every algorithm in this model can be automatically transformed into classification noise tolerant algorithm. Analogously, the learning algorithm in SQ–D is allowed to ask SQs with respect to any distribution in D. This restriction will be sufficient for the learning algorithms that we demonstrate and possesses the property similar to that of SQ model: under some limitations on D every algorithm in SQ–D can be simulated using MQs with persistent classification noise.

1. This and all other models of learning that are mentioned further are fully defined in the following section.

Learning with respect to the uniform is applicable in the case when all the input bits (or attributes) are independent, i.e., the value of each attribute of the next randomly sampled point is chosen randomly and independently of other attributes. For this case we increase the amount of control by allowing the learning algorithm to influence the probability with which any attribute of the next sample point will be 0 or 1. Particularly, we consider the set D_{ρ} containing all the product distributions with each input bit being 1 with probability ρ, 1/2 or 1 − ρ for a constant 0 < ρ < 1/2.

Learning algorithm in SQ–D_{ρ} can ask for a statistical query with respect to product distribution with some attributes biased towards 0 or 1. Amount of this bias is given by ρ and is limited by restrictions on ρ. It is easy to see that boundary values of ρ represent the regular PAC learning with respect to the uniform distribution (ρ = 1/2) and the PAC model with membership queries (ρ = 0).

We give a weaker analogue of the KM algorithm for SQ–D_{ρ} that efficiently finds all the target function Fourier coefficients for sets with less than c log n attributes and larger than a given threshold (we call it the Bounded Sieve). We show that the Bounded Sieve (BS) by itself is, in fact, sufficient for learning the class of decision trees and weakly learning the class of DNF formulae. Then, by employing Freund’s boosting algorithm, we prove that DNF are strongly learnable in SQ–D_{ρ}. This requires an adaption of Freund’s technique to SQ–D_{ρ}. The adaptation we use is simpler and more efficient than a more general one by Aslam and Decatur [AD93] (for the regular SQ model).

As we have noted our SQ–D_{ρ} algorithms can be automatically transformed into persistent classification noise tolerant algorithms. We then show how to modify BS so that it could handle another non-trivial noise: product attribute noise in membership queries. This type of noise was previously considered as appearing in randomly sampled points, i.e., in the regular PAC model [SV88; GS95; DG95; BJT99]. We extend this noise model to learning with membership queries. Particularly, for every sample point x (randomly sampled or asked as a membership query) the oracle flips every bit i of x with probability p_{i} and returns the value of target function at the resulting point (unless classification noise is also present). This type of noise may reflect the situation when communication with the oracle is done using faulty channel or querying very specific point is difficult (or even impossible) to attain. Specifically, we show that our implementation of BS handles any known attribute noise rates bounded away from 1/2 by a constant. This implies learnability of decision trees and weak learnability of DNF in this setting. These results can also be extended to the case when the noise rate is unknown yet uniform, that is, equal for all the attributes.

In the second part of this paper we show some negative results about the newly introduced model. We start by developing a characterization of classes weakly learnable in the regular SQ model and extend it to the SQ–D model. The characterization will enable us to show that the class of all parity functions having at most k(n) variables is not weakly learnable in SQ–D_{ρ} if k(n) is ω(log n). This fact complements the Bounded Sieve which obviously learns every such class for k(n) = O(log n). Another interesting application of this characterization will help us to show that although the model we have introduced is powerful enough to learn DNF expressions, it still cannot learn a class of parity functions learnable in the PAC model with classification noise (to show this we rely on the result by Blum et al. [BKW00]). We also show that the class of all parity functions is not weakly learnable with respect to any “non-biased” distribution (i.e., not containing points with probability greater than \frac{1}{poly(n)}) even in SQ–D for D containing all “non-biased” distributions. This gives futher evidence that the class of all parity functions is hard for any statistics based learning.

1.1 Relation to Other Works

Shamir and Shwartzman [ShSh95] were first to consider extending the notion of statistical query as a way to produce (persistent) noise tolerant algorithms. Their extension is a statistical query analogue of “second-order” queries, that is, each PAC example consists of a pair (x, y) ∈ X^{2} with label ℓ = (f(x), f(y)) and examples are sampled randomly with respect to distributions over X^{2} (not necessarily product). They show that the KM algorithm can be implemented using this type of extended statistical queries and prove that this implementation can be simulated using membership queries with persistent classification noise. Using the same approach it was proven [JSS97] that DNF can be learned by noisy membership queries.

The main distinction between this approach and the SQ–D is that Jackson, Shamir and Shwartzman investigated strong extensions of the SQ model which can be simulated by noisy membership queries and then showed that DNF is learnable in an extension of this kind. On the other hand, we show relatively weak extension of the SQ model, based on regular (“first-order”) statistical queries, in which DNF is learnable. The extension we describe can as well be simulated by noisy membership queries.

Kearns in his original paper on the SQ model [Kea93] showed that the SQ model is weaker than the regular PAC model. Specifically, he proved that the class of all parity functions is not learnable in the SQ model. Subsequently, Blum et al. [BFJ^{+}94] gave a general characterization of the complexity of statistical query learning in terms of the number of uncorrelated functions in the concept class. We give a very similar characterization in terms of number of functions required to “approximate” every function in the concept class. Our characterization is not stronger as a tool for proving negative results and its main advantage is its very simple proof as well as easy extendability to learning in SQ–D.

1.2 Organization

The rest of this paper is organized as follows. In the next section we provide definitions and several well-known facts that are used later in the paper. In Section 3 we define the SQ–D model and present all the learnability results for the model. Discussion of the attribute noise and the implementation of BS for PAC learning with membership queries corrupted by product attribute noise is given in Section 4. Finally, the characterization of classes weakly learnable in SQ–D and its applications are described in Section 5.

2. Definitions and Notation

Before we start describing our results we provide all the relevant definitions. This section describes models, tools, and techniques that we are employing in our discussion.

2.1 General Notation

We consider an input space X = {0, 1}^{n}. A concept is a Boolean function on X. For convenience, when applying the Fourier transform technique, we define Boolean functions to have output in {−1, +1}, where 1 stands for true and −1 for false. A concept class F is a set of concepts. Concept class is defined together with the representation of every concept in it. The representation scheme used (e.g., DNF or decision tree) defines the mapping size(f) that measures the size of the smallest representation of f within the given representation scheme. Concept class together with a representation scheme is called representation class. We denote the representation class of DNF expressions by DNF, and the representation class of decision trees by DT.

For any vector y we denote by y_{i} the i-th element (or bit) of y and by y_{[i,j]} we denote y_{i}y_{i+1} … y_{j}. Bits of a member in our domain are usually called attributes and are referred using variables x_{1}, x_{2}, …, x_{n}. We use [a]^{k} to denote a vector of k elements each equal to a. We use U to denote the uniform distribution over X. For Boolean functions f(x) and g(x) over the domain X we say that g(x) ϵ−approximates f(x) with respect to distribution D (on X) if P r_{D}[f(x) = g(x)] ≥ 1 − ϵ. It is easy to see that this is equivalent to saying that E_{D}[fg] ≥ 1 − 2ϵ. For any real-valued function ϕ define L_{∞}(ϕ) = max_{x∈X} |ϕ(x)|.

Denote by Δ(γ) and Δ′(γ) probability distributions over {0, 1} and {−1, 1} respectively, such that the probability of 1 is γ (that is, the probability distribution of Bernoulli random variable with parameter γ).

If p(n) = O(q(n)) and q′(n) is q(n) with all the logarithmic factors removed we write p(n) = Õ(q(n)). Similarly we define Ω̃ for lower bounds. This extends to k-ary functions in an obvious way.

2.2 Learning Models

Throughout this paper we refer to several models of learning. Below we describe all the mentioned models and provide the relevant definitions.

2.2.1 The PAC Model

Most of the models we are discussing are based on Valiant’s Probably Approximately Correct (PAC) model of learnability. The basic version of this model reflects passive learning from random examples. Formally, let f be a Boolean function and D be a distribution over X. An example oracle for f with respect to D — EX(f, D), is an oracle that on request draws an instance x at random according to the probability distribution D and returns the example ⟨x, f(x)⟩. A membership oracle for f — MEM(f), is an oracle that given any point x returns the value f(x). Let ϵ and δ be positive values (called the accuracy and the confidence of learning, respectively). We say that the representation class F is (strongly) PAC-learnable if there is an algorithm A such that for any ϵ,δ, f ∈ F of size s (the target function) and any distribution D, with probability at least 1−δ, algorithm A(EX(f, D), n, s, ϵ, δ) produces an ϵ–approximation for f with respect to D in time polynomial in n, s, 1/ϵ and log (1/δ). We generally drop the “PAC” from “PAC-learnable” when the model is clear from the context.

We will consider a number of variations on the basic PAC model. Let M be any model of learning (e.g., PAC). If F is M-learnable by an algorithm A that requires a membership oracle then F is M-learnable using membership queries (or learnable in M+MQ). If F is M-learnable for ϵ = 1/2 − p(n, s), where p(·, ·) is a fixed polynomial, then F is weakly Mlearnable. Note that in the above definitions we have placed no restriction on the example distribution D, that is they are distribution-independent. If F is M-learnable only for a specific distribution D (known to A) then F is M-learnable with respect to D (such learning is called distribution-specific and the learning model is denoted by M_{D}).

Remark 1 When we are dealing with concept classes in which all the concepts have representations of polynomial (in n) size the parameter s could be omitted from the discussion.

2.2.2 Noise Models

In the above described models it was always assumed that all the labels (i.e., values of the target function) that are received from oracles are accurate. We are now going to describe the extensions of the above models in which labels provided with the examples (random or received from membership oracle) are corrupted by random noise.^{2} This extension was first considered in the learning literature by Angluin and Laird [AL88]. Since then, in addition to being the subject of a number of theoretical studies [AL88; Lai88; Sl88], the classification noise model has become a common paradigm for experimental machine learning.

Below we will give the formal definitions that incorporate the notion of random classification noise into the PAC learning model. A new parameter η ≤ 1/2 called the noise rate is introduced and the regular example oracle EX(f, D) is replaced with the faulty oracle EX^{η}(f, D). On each call, EX^{η}(f, D) first draws an input x according to D. The oracle then chooses randomly a value ζ ∈ {−1, 1}; 1 with probability η and −1 with probability 1 − η and returns ζf(x). When η approaches 1/2 the result of the corrupted query approaches the result of the random coin flip, and therefore learning becomes more and more difficult. Thus the running time of algorithms in this model is allowed to polynomially depend on \frac{1}{1−2η}. This model of noise is not suitable for corrupting labels returned by a membership oracle MEM(f) since a learning algorithm can, with high probability, find the correct label at point x by asking the label of x polynomial (in \frac{1}{1−2η}) number of times and then returning the label that appeared in the majority of answers. An appropriate modification of the noise model is the introduction of persistent classification noise by Goldman, Kearns and Shapire [GKS94]. In this model, as before, the answer to a query at each point x is corrupted by random value ζ. But if the oracle was already queried about the value of f at some specific point x, it returns the same value it has returned in the first query (i.e, in such a case the noise persists and is not purely random). There is another subtle but important distinction of this model. We cannot require learning algorithms in this model to work for an arbitrarily small confidence parameter δ. Because with some (though negligible) probability target function can be persistently totally corrupted (for example negated) making learning absolutely infeasible. So we must impose a positive lower bound on the confidence δ that can be required from the learning algorithm in the persistent noise model, although this bound will be negligible.

2. Noise in points themselves or attribute noise is defined in Section 4.

2.2.3 The Statistical Query Learning Model

The statistical query model introduced by Kearns [Kea93] is a natural restriction of the PAC learning model in which a learning algorithm cannot see labelled examples of the target concept, but instead may only estimate probabilities involving the target concept. Formally, when learning with respect to distribution D the learning algorithm is given access to STAT(f, D) – a statistical query oracle for target concept f with respect to distribution D. A query to this oracle is a pair (ψ, r), where ψ : {0, 1}^{n} × {−1, +1} → {−1, +1} is a query function and r ∈ [0, 1] is a real number called the tolerance of the query. The oracle may respond to the query with any value v satisfying

|E_{D}[ψ(x, f(x))] − v| ≤ r .

We denote the result returned by oracle STAT(f, D) to query (ψ, r) by STAT(f, D)[ψ, r].

We say that the concept class F is (strongly) learnable from statistical queries (SQ– learnable) if there is a learning algorithm A, and polynomials p(·, ·, ·), q(·, ·, ·) and r(·, ·, ·) such that for every n, f ∈ F, distribution D and ϵ the following holds. Given n, the size s of f, ϵ and access to STAT(f, D), algorithm A produces an ϵ–approximation to f with respect to D in time bounded by p(n, s, 1/ϵ). Furthermore, algorithm A makes queries (ψ, r) in which ψ can be evaluated in time bounded^{3} by q(n, s, 1/ϵ), and in which r is lower-bounded by 1/r(n, s, 1/ϵ).

Although the “usual” randomness of PAC algorithms is incorporated in the statistical queries some applications may still need randomization. In this case we, as usual, have confidence parameter δ, i.e., get the required approximation with probability at least 1 − δ, and the running time of the algorithm is also polynomial in log (1/δ).

It is important to note that the statistical query model is indeed a restriction of the basic PAC model. This follows from the fact that a query (ψ, r) to STAT(f, D) where ψ can be computed in polynomial time and r lower-bounded by inverse of the polynomial can (with high probability) be estimated (within r) by computing ψ on polynomial number of samples and then averaging the result (see Section 2.3 for more details). Moreover, as it was shown by Kearns [Kea93], this estimation can also be made in the presence of random classification noise. This means that any SQ algorithm can be automatically transformed into noise tolerant algorithm. This important property of the model allowed Kearns to obtain noise-tolerant algorithms for practically every concept class for which an efficient learning algorithm in the original noise-free PAC model is known.

2.3 Estimating Expected Values

We will frequently need to estimate the expected value of a random variable. Although the SQ model itself provides us with such estimates, sometimes a random variable will be a result of a statistical query. In such a case we usually cannot use a statistical query to estimate the expectation of the variable. Thus we will find the expectation by sampling the variable and averaging the results. The justification for this technique is usually referred as Chernoff bounds. The Chernoff’s lemma which is concerned with 0,1 random variables was generalized by Hoeffding. Hoeffding’s lemma, presented below, allows to compute the sample size needed to ensure that with high probability the sample mean closely approximates the true mean of the random real-valued variable.

3. In most of the cases we will use simple and explicit query functions. In such cases we omit the analysis

of complexity of these functions.

Lemma 2 (Hoeffding) Let X_{i}, 1 ≤ i ≤ m, be independent random variables all with mean μ such that for all i, a ≤ X_{i} ≤ b. Then for any λ > 0,

Pr [|\frac{1}{m} ∑_{i=1}^{m} X_{i} − μ| ≥ λ] ≤ 2e^{−2λm/(b−a)^{2}} .

According to the lemma if we sample randomly and independently a random variable Y with values in [a, b] then to reach the accuracy of at least λ with confidence of at least δ it is sufficient to take

(b − a)^{2} ln (2/δ)/(2λ^{2}) = O(log (1/δ)(b − a)^{2}/λ^{2})

samples of Y. That is, Hoeffding’s lemma gives the following corollary.

Corollary 3 Let Y represent a random variable that produces values in the range [a, b]. Then there is an algorithm AMEAN(Y, b − a, λ, δ) that for any such Y and any λ > 0 produces a value μ such that |E[Y] − μ| ≤ λ with probability at least 1 − δ. Furthermore, AMEAN runs in O(log (1/δ)(b − a)^{2}/λ^{2}) time.

Remark 4 Another implication of the fact that a value of random variable is a result of a statistical query is that we get its value within some tolerance r. It is easy to see that in such a case the above execution of procedure AMEAN will return the expectation within r + λ.

In general, we say that a constant value c can be efficiently approximated if there exists an algorithm that for every τ and δ, with probability at least 1 − δ produces a value that estimates c within τ and runs in time polynomial in 1/τ and log (1/δ).

The SQ model gives the learner ability to estimate expectations of Boolean functions involving the value of the target function f(x). In further algorithms we will need to get expectations of any real-valued functions involving f(x). For this purpose we will rely on the following simple lemma.

Lemma 5 There exists a procedure RV-SQ that for every real-valued function ϕ : {0, 1}^{n} × {−1, 1} → [−b, b], tolerance r and distribution D, RV-SQ(STAT(f, D), ϕ, b, r) returns a value v satisfying

|E_{D}ϕ(x, f(x)) − v| ≤ r

Its time complexity is O(log (b/r)). The required tolerance is bounded from below by \frac{r}{4b log (b/r)} and complexity of the query functions is the complexity of computation of ϕ plus O(n).

Proof: We find the required expectation by decomposing ϕ into linear combination of Boolean functions according to its binary representation in the following way: Let k be equal to ⌈log b⌉ and l = ⌈log \frac{2}{r}⌉

ϕ(x, f(x)) = −2^{k} + 2^{k}ϕ_{k}(x, f(x)) + 2^{k−1}ϕ_{k−1}(x, f(x)) + … + ϕ_{0}(x, f(x))+

\frac{1}{2}ϕ_{−1}(x, f(x)) + … + 2^{−l}ϕ_{−l}(x, f(x)) + ψ(x, f(x))

Where all the ϕ_{i} are Boolean 0,1-valued functions representing the bits of ϕ(x, f(x)) + 2^{k} (nonnegative function). Choice of l ensures that 0 ≤ ψ(x, f(x)) ≤ r/2. Since we would like the composition to use ±1-valued functions, we can further write

ϕ(x, f(x)) = 2^{k−1}(2ϕ_{k}(x, f(x)) − 1) + 2^{k−2}(2ϕ_{k−1}(x, f(x)) − 1) + … +
2^{−l−1}(2ϕ_{−l}(x, f(x)) − 1) + (ψ(x, f(x)) − 2^{−l−1})

For every −l ≤ j ≤ k, 2ϕ_{j}(x, f(x)) − 1 is a ±1-valued Boolean function depending on x and f(x). Thus to get the required approximation, for every −l ≤ j ≤ k we approximate E_{D}[2ϕ_{j}(x, f(x)) − 1] within \frac{r}{2^{j+1}(k+l+1)} using query

(2ϕ_{j}(x, f(x)) − 1, \frac{r}{2^{j+1}(k + l + 1)}, D)

Let μ_{j} be the result of the query. The procedure returns the value ∑_{−l≤j≤k} 2^{j}μ_{j}. This value is a valid result since

|E_{D}ϕ(x, f(x)) − ∑_{−l≤j≤k} 2^{j}μ_{j}| ≤ ∑_{−l≤j≤k} 2^{j} \frac{r}{2^{j+1}(k + l + 1)} + E_{D}[|ψ(x, f(x)) − 2^{−l−1}|] ≤

∑_{−l≤j≤k} \frac{r}{2(k + l + 1)} + r/2 = r.

The complexity of this algorithm is O(log (b/r)). The required tolerance is at least

\frac{r}{2^{k+1}(k + l + 1)} ≥ \frac{r}{4b log (b/r)} .

Complexity of the query functions is the complexity of computation of ϕ plus O(n). □

2.4 The Fourier Transform

Many parts of our analysis rely heavily on the use of the well-known Fourier transform technique. This beautiful technique was introduced to the learning theory by Linial, Mansour, and Nisan [LMN89]. Below we give a short description of the technique and its notation (an extended survey of the technique and the KM algorithm was given by Mansour [Man94]).

Since all the expectations and probabilities we use when applying this technique will be with respect to the uniform distribution, we will sometimes omit U in our formulae. For every vector a ∈ {0, 1}^{n} we define χ_{a}—the parity function for the vector by

χ_{a}(x) = (−1)^{∑_{i∈{1,...,n}} a_{i}x_{i}}

A common alternative is to associate a parity function with a set A ⊆ {1, …, n} of attribute indices that influence the parity. This definition implies that χ_{a} and χ_{A} are equivalent whenever A = {i | a_{i} = 1}. Also define the inner product by ⟨f, g⟩ = E[f(x)g(x)] and define the norm as usual by ∥f∥ = \sqrt{E_{x}[f^{2}(x)]}. In this context we define w(a) to be the number of bits a_{i} equal to 1 in a and call it the weight of a. Let ⊕ denote the bit-wise XOR operation on binary vectors. Parity functions possess several important and easily verifiable properties:

1. χ_{a}(x)χ_{b}(x) = χ_{a⊕b}(x);

2. χ_{a}(x)χ_{a}(y) = χ_{a}(x ⊕ y);

3. E_{x}[χ_{a}(x)] = 0 for every a ≠ [0]^{n};

4. χ_{[0]^{n}} ≡ 1 and thus E_{x}[χ_{[0]^{n}}(x)] = 1.

By these properties, for every a, b ∈ {0, 1}^{n},

⟨χ_{a}, χ_{b}⟩ = E_{x}[χ_{a}(x)χ_{b}(x)] = E_{x}[χ_{a⊕b}(x)] = \{ \begin{matrix}0 & a ≠ b \\ 1 & a = b \end{matrix}

Thus the set {χ_{a}}_{a∈{0,1}^{n}} is orthonormal. Its size is 2^{n} which is also the dimension of the vector space of real-valued functions on {0, 1}^{n}, i.e., the set forms the basis for the vector space. That is, every function g : {0, 1}^{n} → ℝ can be uniquely expressed as a linear combination of parity functions:

g(x) = ∑_{a∈{0,1}^{n}} ĝ(a)χ_{a}(x) .

The coefficients ĝ(a) are called Fourier coefficients and vector of coefficients ĝ the Fourier transform of g. The degree of the coefficient ĝ(a) is the weight of a.^{4} Because of the orthonormality of the parity functions, ĝ(a) = E[g(x)χ_{a}(x)]. Thus ĝ(a) represents the correlation of g with the parity function χ_{a}.

Parseval’s identity states that for every function g, ∥g∥^{2} = E[g^{2}] = ∑_{a} ĝ^{2}(a). For Boolean g this implies that ∑_{a} ĝ^{2}(a) = 1.

The Fourier transform technique is usually used in the following way. Given some access to the target function f we try to find its Fourier coefficients or at least the “largest” among them (here and in further discussion we refer to the absolute value of the coefficient). These coefficients define a real-valued function g. We then produce hypothesis by taking h = sign(g). Justification for this method is provided by the following well-known lemma.

Lemma 6 Let f be a Boolean function and g be any real-valued function then

Pr[f(x) ≠ sign(g)(x)] ≤ E[(f(x) − g(x))^{2}] = ∑_{a∈{0,1}^{n}}(f̂(a) − ĝ(a))^{2} .

4. For a parity function defined using a set of indices the degree of the corresponding coefficient is the size

of the set.

2.5 The KM Algorithm

One of the most fundamental application of the Fourier analysis is the Kushilevitz-Mansour algorithm [KM91]. This randomized algorithm uses membership queries to find all the Fourier coefficients of the target function larger than some threshold θ in time polynomial in n, log (1/δ) and θ^{−1}. The algorithm is based on an ingenious way to estimate the sum of squares of all the Fourier coefficients for vectors starting with some given prefix. Formally for 0 ≤ k ≤ n and α ∈ {0, 1}^{k} denote

C_{α} = ∑_{b∈{0,1}^{n−k}} f̂^{2}(αb) .

As it has been proved by Kushilevitz and Mansour

C_{α} = E_{x} [E_{y}[f(yx)χ_{α}(y)]]^{2} ,

where the expectation is uniform over x ∈ {0, 1}^{n−k}, y ∈ {0, 1}^{k}. This formula means that C_{α} can be efficiently approximated by random sampling (see Section 2.3). If there exists at least one Fourier coefficient for a vector starting with α and larger (by absolute value) than θ then C_{α} ≥ θ^{2}. Using this simple observation Kushilevitz and Mansour wrote a recursive procedure (named Coef) that given α finds all the Fourier coefficient for vectors starting with α and larger than θ as follows. For α being a vector of length n Coef(α) returns the vector if its Fourier coefficient is larger than θ. For shorter prefixes the procedure checks whether C_{α} ≥ θ^{2}. If so executes itself for prefixes α · 0 and α · 1 and returns the union of the results. Otherwise (C_{α} < θ^{2}), returns the empty set. When executed on an empty prefix this procedure should return all the Fourier coefficients that are larger than θ. Effectiveness of this algorithm follows from the fact that for any given length of prefix k

∑_{α∈{0,1}^{k}} C_{α} = ∑_{a∈{0,1}^{n}} f̂(a)^{2} = ∥f∥^{2} = 1 .

This means that for any given length of prefix Coef will be called at most 1/θ^{2} times, i.e., the resulting algorithm is polynomial in n, log (1/δ) and 1/θ.

In this description we have neglected the fact that C_{α} is not known exactly but only estimated. Minor modifications required to solve this problem can be found in the original description of the algorithm [KM91] or in the similar analysis of our analogue to this algorithm described in Section 3.2.

Remark 7 It can be easily seen that the algorithm can be applied to any real-valued function ϕ(x) (and not only to Boolean). In such a case for any given length of prefix the procedure Coef will be called at most ∥ϕ∥^{2}/θ^{2} and thus running time of the KM algorithm becomes polynomial in ∥ϕ∥. Moreover, we do not need to know the value of ϕ(x) exactly. An ability to efficiently estimate the value of ϕ(x) with any desired accuracy is sufficient since the value of ϕ(x) is used only for estimating C_{α}’s and Fourier coefficients of ϕ.

3. Learning by Extended Statistical Queries

In this section we introduce a new model of learning. The model (or actually a collection of models) we define is at least as strong as the basic PAC model and is weaker (or equivalent) to the use of membership queries. For all of our applications a restriction of the new model to statistical queries is sufficient. Moreover, as we will demonstrate, the SQ version of the new model has a few important advantages. Thus we almost immediately start discussing the restricted version.

We begin by defining the SQ–D model and discussing its properties. Then we apply these general ideas to learning of decision trees and DNF expressions with respect to the uniform distribution. In particular, we implement the Bounded Sieve algorithm which has the functionality of the KM algorithm with an additional restriction. The Bounded Sieve by itself is sufficient for learning of DT and weak learning of DNF. By adapting Freund’s boosting technique to our model we show that DNF expressions are also strongly learnable.

3.1 Extending the SQ Model

We are now going to give a detailed description of the extension of the basic PAC model and the SQ model. In this new model we allow the learning algorithm to supply a distribution with respect to which the next point will be sampled. Formally, let D be a distribution over X and D be a set of distributions over X containing distribution D. The new example oracle EX(f, D) is defined as follows. A query to this oracle is a distribution D′ ∈ D. To such a query the oracle EX(f, D) responds with example ⟨x, f(x)⟩, where x is sampled randomly and independently according to distribution D′. In other words, access to EX(f, D) is equivalent to access to all the oracles of the form EX(f, D′), where D′ ∈ D. Learning with access to the newly-defined oracle is referred as learning in the PAC–D model. Learnability (with respect to D) in this new model is defined as in the regular PAC model with the regular example oracle EX(f, D) replaced by EX(f, D).

The extension of the PAC learning model obviously possesses the following properties:

• PAC–D is equivalent to the regular PAC model for D = {D};

• We can simulate the PAC–D model using membership queries;

• If we do not restrict D we might be able to simulate membership queries (e.g., using distributions with all the weight concentrated in one point).

Our next step is restricting the PAC–D model to statistical queries, or extending Kearns’ SQ model in the similar fashion. That is, instead of the regular STAT(f, D) oracle a learning algorithm in the SQ–D model is provided with access to all the oracles STAT(f, D′) where D′ ∈ D. More formally, learning algorithm in the SQ–D model is supplied with the STAT(f, D) oracle, where f is the target concept. A query to this oracle is a triple (ψ, r, D′) where ψ : {0, 1}^{n} × {−1, +1} → {−1, +1} is a query function, r ∈ [0, 1] is a tolerance (as in the SQ model) and D′ is a distribution from D. To such a query the oracle responds with the value v satisfying |E_{D′}[ψ(x, f(x))] − v| ≤ r. Respectively, we say that the concept class F is learnable in the SQ–D model with respect to D if it is learnable by a polynomial algorithm (as defined in the regular SQ model) with access to the newly-defined oracle.

An important property of the model that results from the fact that it is statisticalquery-based is that STAT(f, D) can be simulated by membership queries in the presence of random classification noise. The simulation is done by offsetting the effect of the noise on a query [Kea93]. Since we are simulating using membership queries we are actually interested in learning with persistent classification noise. Offsetting noise in this model can be a more complicated task. However, if all the sample points in the sample that was used for simulating statistical queries are different then the persistent noise in the sample is equivalent to usual random classification noise and therefore we can offset the effect of noise in the same way as before. In the following theorem we show that under certain simple restriction on set D the probability to get two equal points in the sample will be negligible and therefore we will be able to use Kearns’ noise offsetting procedure.^{5} Denote by L_{∞}(D) = max_{D′∈D}{L_{∞}(D′)}.

Theorem 8 Let F be a concept class and D be a set of distributions with sampling oracle available for every D′ ∈ D. If F is learnable in SQ–D with respect to D and L_{∞}(D) < τ^{n} for a constant 0 < τ < 1, then F is learnable with respect to D using membership queries corrupted by random persistent classification noise.

Proof: Let A be an algorithm that learns F in SQ–D. Let us examine the execution of A for a particular f ∈ F. We can assume that the learning parameters s and ϵ are subexponential^{6} in n (otherwise a trivial exponential learning algorithm will solve the problem). The number of queries that A asks during its execution is bounded by a fixed polynomial in n, s, and ϵ (denote it by p_{1}(n, s, ϵ^{−1}) ). Let 1/p_{2}(n, s, ϵ^{−1}) denote the inverse-polynomial bound on the required accuracy of every query. Let σ = \frac{τ^{n/2}}{2p_{1}(n,s,ϵ^{−1})}. According to Corollary 3, in order to estimate all the A’s queries with accuracy of 1/p_{2}(n, s, ϵ^{−1}) and with confidence of σ polynomial number of sample points is required (the polynomial depends on n, s, ϵ^{−1}, and \frac{1}{1−η} since the estimation is done in the presence of noise). Denote this polynomial bound by p_{3}(n, s, ϵ^{−1}, \frac{1}{1−η}). Assuming that the noise is random, all the estimations will succeed with probability at least 1 − σp_{1}(n, s, ϵ^{−1}) = 1 − τ^{n/2}/2. The probability to see a point more than once in the above sample is less than

p_{3}^{2}(n, s, ϵ^{−1}, \frac{1}{1 − η})L_{∞}(D) ≤ p_{3}^{2}(n, s, ϵ^{−1}, \frac{1}{1 − η})τ^{n} < τ^{n/2}/2 .  (1)

Therefore, with probability at least 1−τ^{n/2}/2, the noise in the generated sample is truly random. This means that the simulation with succeed with probability at least 1 − τ^{n/2}.

Now, if we impose a lower bound of τ^{n/2} on confidence δ that can be required from the learning algorithm (as is allowed when the noise is persistent), then the above-described procedure gives the algorithm that learns F by using membership queries with persistent classification noise. □

3.2 Learning with Respect to the Uniform Distribution Using Product Distributions

In this section we will examine set D that contains product distributions such that every input bit is 1 with probability ρ , 1/2 or 1−ρ, that is, for every input bit x_{i}, Pr[x_{i} = 1] = p_{i} independently of all the other inputs and p_{i} ∈ {ρ, 1/2, 1 − ρ} (we call p = p_{1}p_{2} … p_{n} a probability vector). We assume that ρ is a constant satisfying 1/2 > ρ > 0. For every p ∈ {ρ, 1/2, 1 − ρ}^{n} denote by D_{p} the product distribution defined by this probability vector. Denote by

5. Proof of this theorem can be easily extracted from [JSS97].

6. A more accurate restriction on these parameters can be deduced from equation (1).

D_{ρ} = {D_{p} | p ∈ {ρ, 1/2, 1 − ρ}^{n}} .

This distribution class will be used to learn with respect to the uniform distribution which itself is contained in D_{ρ} for any ρ.

For a probability vector p and x ∈ {0, 1}^{n} denote by p ⊕ x probability vector for which (p ⊕ x)_{i} = p_{i} if x_{i} = 0 and (p ⊕ x)_{i} = 1 − p_{i} if x_{i} = 1. Since p ∈ {ρ, 1/2, 1 − ρ}^{n} we also have p ⊕ x ∈ {ρ, 1/2, 1 − ρ}^{n}.

According to the discussion in Section 1, we call this ρ the degree of control that a learning algorithm in SQ–D_{ρ} has. Intuitively, smaller values of ρ represent larger degree of control (with 0 giving the equivalent of membership queries). This is proven in the next lemma.

Lemma 9 If 1/2 ≥ ρ_{1} ≥ ρ_{2} > 0 then any algorithm in SQ–D_{ρ_{1}} can be simulated by a randomized algorithm in SQ–D_{ρ_{2}}.

Proof: We show that a result of any statistical query in SQ–D_{ρ_{1}} can be efficiently approximated in SQ–D_{ρ_{2}}. Let (ϕ, r, D_{p}) be a query to STAT(f, D_{ρ_{1}}). For π ∈ [0, 1] we define q = [π]^{n} (i.e., vector with every element equal to π). Let x_{1} and x_{2} be chosen randomly according to Δ(π) and Δ(ρ). It is easy to verify that x_{1} ⊕ y_{1} is distributed according to Δ(π + ρ − 2πρ). When sampling with respect to a product distribution D_{p}, bit i is sampled randomly and independently according to distribution Δ(p_{i}). Therefore,

E_{y∼D_{p}}[ϕ(y, f(y))] = E_{x∼D_{q}} [E_{y∼D_{s⊕x}}[ϕ(y, f(y))]] ,  (2)

where s is a probability vector such that p_{i} = π + s_{i} − 2πs_{i} or s_{i} = \frac{p_{i}−π}{1−2π}. For π = \frac{ρ_{1}−ρ_{2}}{1−2ρ_{2}} (π ∈ [0, 1] since 1/2 ≥ ρ_{1} ≥ ρ_{2} > 0) we get that

s_{i} = \{ \begin{matrix}ρ_{2} & p_{i} = ρ_{1} \\ 1 − ρ_{2} & p_{i} = 1 − ρ_{1} \\ 1/2 & p_{i} = 1/2 \end{matrix}

Thus D_{s} ∈ D_{ρ_{2}} and for every x, D_{s⊕x} ∈ D_{ρ_{2}}, i.e., E_{y∼D_{s⊕x}}[ϕ(y, f(y))] can be estimated by a query in SQ–D_{ρ_{2}}. Equation (2) means that the result of query (ϕ, r, D_{p}) can be efficiently approximated by sampling in SQ–D_{ρ_{2}}. □

Remark 10 For the simplicity of the exposition we have chosen the degree of control to be uniform over all the attributes (and equal to ρ). Alternatively, we can consider classes of distributions for which this degree is different for each attribute. It can be easily shown (by slightly modifying the proof of Lemma 9) that if D is a class of distributions giving a learning algorithm degrees of control in range [ρ_{1}, ρ_{2}] then the SQ–D model is not stronger than SQ–D_{ρ_{1}} and not weaker than SQ–D_{ρ_{2}}.

It is important to note that according to Theorem 8 learning in SQ–D_{ρ} implies learning with persistent noise since L_{∞}(D_{ρ}) = (1 − ρ)^{n}.

3.3 An Analogue to the KM Algorithm

Our purpose is to give an algorithm in the SQ–D_{ρ} model that could find “large” Fourier coefficients of the target function. When membership queries are available this task can be performed using the KM algorithm. As we will show in the characterization section this task cannot be performed in the SQ–D_{ρ} model. Instead we will give a weaker analogue of the KM algorithm implemented in the SQ–D_{ρ} model. It will find all the “large” Fourier coefficients of degree lower than ℓ in time polynomial in 2^{ℓ} thus allowing only the Fourier coefficients with degree bounded by c log n to be found efficiently. Particularly, for the target function f, given parameters n, θ, ℓ and δ it will, with probability at least 1−δ, find a set S ⊆ {0, 1}^{n} with the following properties:

• for all a, if |f̂(a)| ≥ θ and w(a) ≤ ℓ then a ∈ S;

• for all a ∈ S, |f̂(a)| ≥ θ/2.

We say that such a set possesses the large Fourier coefficient property for function f, threshold θ and degree ℓ (this property can be defined for any real-valued function).

The KM algorithm is based on a subroutine that estimates the sum of squares of all the coefficients for vectors starting with given prefix. In the same fashion our algorithm will be based on ability to estimate weighted sum of squares of all the coefficients for vectors starting with a given prefix. In particular, for 0 ≤ k ≤ n and α ∈ {0, 1}^{k} denote

S_{α}^{ρ}(f) = ∑_{b∈{0,1}^{n−k}} f̂^{2}(αb)(1 − 2ρ)^{2w(b)}.

Lemma 11 There exists an SQ–D_{ρ} randomized algorithm P1 that for any target function f, prefix vector α of length k, confidence δ and accuracy τ, P1(n, k, α, τ, δ) returns, with probability at least 1 − δ, a value estimating S_{α}^{ρ}(f) within τ. It runs in O(τ^{−2} log (1/δ)) time and tolerance of its queries is bounded from below by τ/4.

Proof: Let p = [\frac{1}{2}]^{k}[ρ]^{n−k} and α_{0} = α[0]^{n−k}. The ability to estimate S_{α}^{ρ}(f) is based on the following equation

S_{α}^{ρ}(f) = E_{x∼U} [E_{y∼D_{p⊕x}}[f(y)χ_{α_{0}}(x ⊕ y)]]^{2} .

To prove it denote

f_{α}^{ρ}(x) ≜ E_{y∼D_{p⊕x}}[f(y)χ_{α_{0}}(x ⊕ y)] .

Since by Parseval’s identity for every function f, E_{x∼U}[f^{2}(x)] = ∑_{a∈{0,1}^{n}} f̂^{2}(a), it is enough to prove that

f_{α}^{ρ}(x) = ∑_{b∈{0,1}^{n−k}} f̂(αb)(1 − 2ρ)^{w(b)}χ_{αb}(x) .  (3)

As follows from the definition of p⊕x (see Section 3.2), D_{p⊕x}(y) = D_{p}(x⊕y). Thus equation (3) can be proved as follows

\begin{aligned}f_{α}^{ρ}(x) = E_{y∼D_{p⊕x}}[f(y)χ_{α_{0}}(x ⊕ y)] & = ∑_{y∈\{0,1\}^{n}} f(y)χ_{α_{0}}(x ⊕ y)D_{p⊕x}(y) \\ & = ∑_{y∈\{0,1\}^{n}} f(y)χ_{α_{0}}(x ⊕ y)D_{p}(x ⊕ y) \\ & = ∑_{z∈\{0,1\}^{n}} f(x ⊕ z)χ_{α_{0}}(z)D_{p}(z) \\ & = E_{z∼D_{p}}[f(x ⊕ z)χ_{α_{0}}(z)] \\ & = E_{z∼D_{p}} [ ∑_{a∈\{0,1\}^{n}} f̂(a)χ_{a}(x ⊕ z)χ_{α_{0}}(z)] \\ & = E_{z∼D_{p}} [ ∑_{a∈\{0,1\}^{n}} f̂(a)χ_{a}(x)χ_{a⊕α_{0}}(z)] \\ & = ∑_{a∈\{0,1\}^{n}} f̂(a)χ_{a}(x)E_{z∼D_{p}}[χ_{a⊕α_{0}}(z)]. \end{aligned}  (4)

But since p = [\frac{1}{2}]^{k}[ρ]^{n−k} and α_{0} = α[0]^{n−k},

E_{z∼D_{p}}[χ_{a⊕α_{0}}(z)] = ∏_{i∈{1,...,n}} [1 − p_{i} + p_{i}(−1)^{a_{i}⊕α_{0,i}}] = ∏_{i∈{1,...,n},a_{i}⊕α_{0,i}=1}(1 − 2p_{i})

= (  ∏_{i∈{1,...,k},a_{i}≠α_{i}} 0) (  ∏_{i∈{k+1,...,n},a_{i}=1}(1 − 2ρ)) , (5)

that is, if a = αb then E_{z∼D_{p}}[χ_{a⊕α_{0}}(z)] = (1 − 2ρ)^{w(b)}, otherwise E_{z∼D_{p}}[χ_{a⊕α_{0}}(z)] = 0. This result substituted to the last term of equation (4) gives precisely the required identity.

Our goal is to estimate S_{α}^{ρ}(f) = E_{x∼U}[(f_{α}^{ρ}(x))^{2}]. By the definition of f_{α}^{ρ}, for every z, we can estimate f_{α}^{ρ}(z) within τ/4 using statistical query (f(x)χ_{α_{0}}(z ⊕ x), τ/4, D_{p⊕α_{0}}) and we can assume that the estimate has an absolute value of at most 1. It is easy to see that the square of this estimate is an estimate for (f_{α}^{ρ}(z))^{2} within τ/2. Therefore (f_{α}^{ρ}(z))^{2} is a random variable whose value we are able to estimate within τ/2. Denote it by Y. By Corollary 3 with Remark 4 we get that the call to AMEAN(Y, τ/2, 1, δ) will give us the estimate for S_{α}^{ρ}(f) within τ/2 + τ/2 = τ. Figure 1 summarizes the description of procedure P1. Since computing the value of Y takes O(1) time, the complexity of the algorithm is O(τ^{−2} log (1/δ)). □

With algorithm P1 we are now ready to describe the Bounded Sieve. We define c_{0} ≜ −2 log (1 − 2ρ) (it is a positive constant).

Theorem 12 There exists an SQ–D_{ρ} randomized algorithm BS_{ρ} that for any target concept f, threshold θ > 0, confidence δ > 0 and degree bound 0 ≤ ℓ ≤ n, BS_{ρ}(n, θ, ℓ, δ) returns, Input: Access to ST AT (f, D_{ρ}); 0 ≤ k ≤ n; α ∈ {0, 1}^{k}; ℓ ≤ n; θ > 0; τ > 0; δ > 0 Output: Value v such that, with probability at least 1 − δ, |S_{α}^{ρ}(f) − v| ≤ τ.

1. p ← [\frac{1}{2}]^{k}[ρ]^{n−k}

2. α_{0} ← α[0]^{n−k}

3. Y ≡ draw z w.r.t. U and compute (STAT(f, D_{ρ})[f(x)χ_{α_{0}}(z ⊕ x), τ/6, D_{p⊕α_{0}}])^{2}

4. v ← AMEAN(Y, b − a = 1, τ/2, δ)

5. return v

Figure 1: Procedure P1

with probability at least 1 − δ, a set with the large Fourier coefficient property for function f, threshold θ and degree ℓ. Its running time is polynomial in n, 2^{ℓ}, log (1/δ) and θ^{−1}, particularly Õ(n2^{3c_{0}ℓ}θ^{−6} log (1/δ)). Tolerance of queries is bounded from below by an inverse of a polynomial in 2^{ℓ} and θ^{−1}, specifically 2^{−c_{0}ℓ}θ^{2}/16.

Proof: If there is at least one coefficient greater than θ with degree lower than ℓ for the parity function of vector starting with α then S_{α}^{ρ}(f) is at least (1−2ρ)^{2ℓ}θ^{2} = 2^{2 log (1−2ρ)ℓ}θ^{2} = 2^{−c_{0}ℓ}θ^{2}. All the coefficients for the vectors starting with α can be separated into two disjoint sets—those for the vectors that start with α0 and those for the vectors that start with α1. With these observations and the procedure P1 for estimating S_{α}^{ρ}(f) we can write a recursive subroutine P2 that for every α outputs the set W_{α} that satisfies the following conditions:

• for all a ∈ W_{α},α is a prefix of a;

• for all a ∈ {0, 1}^{n}, if |f̂(a)| ≥ θ and w(a) ≤ ℓ then a ∈ W_{α};

• for all a ∈ W_{α}, |f̂(a)| ≥ θ/2.

That is, W_{α} has the large Fourier coefficient property for function f, threshold θ, and degree ℓ; and is restricted to prefix α.

To find all the required coefficients (i.e., to implement the BS_{ρ}) we invoke P2 on the empty prefix. The implementation of the procedure P2 is given in Figure 2.

If P1 succeeds then P2 is called recursively only when

S_{α}^{ρ}(f) ≥ (3/4 − 1/4)2^{−c_{0}ℓ}θ^{2} = 2^{−c_{0}ℓ}θ^{2}/2 .

Since ∑_{α∈{0,1}^{k}} S_{α}^{ρ}(f) ≤ ∑_{a} f̂^{2}(a) = 1, P2 will be invoked at most 2 · 2^{c_{0}ℓ}θ^{−2} times for each length of α, and therefore there will be at most 2n2^{c_{0}ℓ}θ^{−2} calls to P1. This means that total probability of failure of the algorithm is at most 2n2^{c_{0}ℓ}θ^{−2} · δ2^{−c_{0}ℓ}θ^{2}/(2n) = δ. According to Lemma 11, each call to P1 in P2 takes

O(2^{2c_{0}ℓ}θ^{−4} log (2n2^{c_{0}ℓ}θ^{−2}δ^{−1})) = Õ(2^{2c_{0}ℓ}θ^{−4} log (1/δ)) .

This gives a bound on total running time of Õ(n2^{3c_{0}ℓ}θ^{−6} log (1/δ)). By the same lemma, tolerance of all the queries is bounded from below by 2^{−c_{0}ℓ}θ^{2}/16. It is important to note Input: Access to STAT(f, D_{ρ}); 0 ≤ k ≤ n; α ∈ {0, 1}^{k}; ℓ ≤ n; θ > 0; δ > 0 Output: The set W_{α} that, with probability at least 1 − δ, has the large Fourier coefficient property for function f, threshold θ and degree ℓ; and is restricted to prefix α.

1. if k = n then

2. v ← STAT(f, D_{ρ})[fχ_{α}, θ/4, U]

3. if v ≥ \frac{3}{4}θ then output(α)

4. else

5. b ← 2^{−c_{0}ℓ}θ^{2}

6. s ← P1(n, α, b/4, δb/(2n))

7. if s ≥ 3b/4 then

8. P2(k + 1, α0, ℓ, θ, δ)

9. P2(k + 1, α1, ℓ, θ, δ)

10. endif

11. endif

Figure 2: Procedure P2

that if the estimations fail the running time of the algorithm may exceed this bound. This can be easily prevented by adding a time counter that terminates the execution of the algorithm whenever it exceeds this time bound. □

In our future applications we will need to find the Fourier coefficients not only of a Boolean target f but also of any real-valued function involving f(x). Thus we extend the BS algorithm as follows.

Theorem 13 Let ϕ : {0, 1}^{n} × {−1, 1} → [−β, β] be any real-valued function (β > 0). There exists an SQ–D_{ρ} randomized algorithm RV-BS_{ρ} that for every target concept f, positive threshold θ, confidence δ > 0 and degree bound 0 ≤ ℓ ≤ n RV-BS_{ρ}(n, ϕ, β, θ, ℓ, δ) returns, with probability at least 1−δ, a set with the large Fourier coefficient property for function ϕ, threshold θ and degree ℓ. It runs in Õ(n2^{3c_{0}ℓ}θ^{−6}β^{2} log (1/δ)) time and tolerance of queries is bounded from below by Ω̃(β^{−2}2^{−c_{0}ℓ}θ^{2}). Complexity of query functions is bounded by O(τ) + O(n), where τ is the complexity of computation of ϕ.

Proof: Let us look back into the proof of Theorem 12. Its idea is obviously applicable in the new setting. All we have to check is the details of the implementation. Let us substitute π(x) ≜ ϕ(x, f(x)) for f(x) in all the places in the proof. In the second line of P2 we need an estimate of ϕ̂_{f}(α). This cannot be done using one statistical query but instead we can use the procedure RV-SQ(STAT(f, U), ϕχ_{α}(x), θ/4). Now, given that P1 will estimate correctly S_{α}^{ρ}(π), the algorithm will work correctly. The only thing that will change is the bound on the number of calls to P2 since it is based on the fact that: E[f^{2}] = 1. Now we have that: E[π^{2}] ≤ L_{∞}^{2}(π) ≤ β^{2} and hence P2 will be invoked at most β^{2}2n2^{c_{0}ℓ}θ^{−2} times. Due to the increase in the number of calls to P1 the confidence of each call has to be increased (it has to be divided by β^{2}). Now we should get a modified version of P1 that will produce estimations of S_{α}^{ρ}(π). If we substitute π for f in Lemma 11 we see that all the properties will hold but now the estimation of π_{α}^{ρ}(z) = E_{x∼D_{p⊕z}}[π(x)χ_{α_{0}}(z ⊕ x)] (line 3 in P1 cannot be done using one query. Moreover, since we want (π_{α}^{ρ}(z))^{2} to be approximated within τ/2, π_{α}^{ρ}(z) has to be approximated within \frac{τ}{4|π_{α}^{ρ}(z)|}. Since

|π_{α}^{ρ}(z)| ≤ E_{x∼D_{p⊕z}}[|π(x)χ_{α_{0}}(z ⊕ y)|] ≤ L_{∞}(ϕ) ≤ β

it will suffice to approximate π_{α}^{ρ}(z) within τ′ = \frac{τ}{4β}. To make this approximation we call

RV-SQ(STAT(f, D_{p⊕z}), ϕ(x, f(x))χ_{α_{0}}(z ⊕ x), β, τ′) .

By Lemma 5, we get the required value. The time complexity of the call to RV-SQ is O(log (β/τ′)) = O(log (β/τ)). The required tolerance is at least \frac{τ′}{4β log (β/τ′)} = Ω̃(\frac{τ}{β^{2}} ). Complexity of the query functions is the complexity of computation of ϕ plus O(n). These new bounds on the complexity of P1 render the total running time of the algorithm to be Õ(n2^{3c_{0}ℓ}θ^{−6}β^{2} log (1/δ)). The required tolerance is Ω̃(β^{−2}2^{−c_{0}ℓ}θ^{2}). Thus all the bounds satisfy the required conditions. □

3.4 Learning Decision Trees

Below we give the first application of the BS_{ρ} algorithm. We prove that the representation class of decision trees is learnable in the SQ–D_{ρ} model. For this and further applications we take ρ = \frac{1}{4}. This makes c_{0} = 2 log (1 − 2ρ) to be 2. Our idea is to show that in order to learn DT it is sufficient to consider only “large” Fourier coefficients of “low” degree (we add a restriction on degree over the original proof by Kushilevitz and Mansour). To achieve this we rely on several well-known properties of Fourier transform of decision trees. The properties are described in the following lemmas (we provide their proofs for completeness).

Lemma 14 Let T be a decision tree of depth d. All the Fourier coefficients of T of degree larger than d are 0 and all the non-zero coefficients of T are larger than 2^{−d}.

Proof: We start by examining the Fourier transform of a single term. Let t be a term of length l and let i_{1}, …, i_{l} be the indices of variables appearing as literals in t. For every 1 ≤ j ≤ l let b_{j} be 1 if x_{i_{j}} appears negated in t and 0 otherwise. Let t^{+} = \frac{t+1}{2} (the \{0, 1\} version of term t). It is easy to verify that

t^{+} = ∏_{j=1}^{l} (\frac{1 + (−1)^{b_{j}}χ_{\{i_{j}\}}}{2} )  (6)

For every two disjoint sets of indices A and B, χ_{A}χ_{B} = χ_{A∪B}. Thus by developing the equation (6) we obtain that all the non-zero Fourier coefficients of t^{+} are for sets not larger than l and are by their absolute value equal to 2^{−l}.

Let m be the number of leaves labelled by 1 in T and t_{1}, …, t_{m} be the terms corresponding to each of these leaves. Let T^{+}, t_{1}^{+}, …, t_{m}^{+} be {0, 1} versions of the decision tree and the terms. Every input value satisfies at most one term of T and thus T^{+} = ∑_{i=1}^{m} t_{i}^{+}, that is, every Fourier coefficient of T^{+} is a sum of corresponding Fourier coefficients of terms t_{1}^{+}, …, t_{m}^{+}. Length of every term t_{i} is at most d and thus all the non-zero Fourier coefficients of T^{+} are for sets not larger than d and their absolute value is greater or equal to 2^{−d}. By the definition of T^{+}, T = 2T^{+} − 1 and therefore the above property of the Fourier transform of T^{+} holds for T as well. □

The size of decision tree is the number of leaves in it. Let DT-size(f) denote the size of a minimal DT representation of f.

Lemma 15 Let T be a decision tree of size m. There exists a function h such that all the Fourier coefficients of h of degree larger than t are 0, where t = log (4m/τ), all non-zero coefficients of h are larger than τ/(4m) and E[(T − h)^{2}] ≤ τ.

Proof: Let h be the decision tree that results from truncating T at depth t. At the truncated places we add a leaf with value 1. The probability that uniformly chosen assignment will reach some specific leaf at depth greater or equal to t is at most 2^{−t}. Therefore the probability of reaching one of the leaves we added (instead of the truncated parts) is at most m2^{−t} = τ/4, therefore Pr_{U}[T ≠ h] ≤ τ/4. For Boolean functions h and T this implies that

E_{U}[(T − h)^{2}] = 4 Pr_{U}[T ≠ h] ≤ τ .

By Lemma 14, we get that the Fourier transform of h has the required properties. We are now ready to prove that BS can be used to learn DT.

Theorem 16 There exists an SQ–D_{\frac{1}{4}} randomized algorithm DT-learn such that for any target concept f, s = DT-size(f), ϵ > 0 and δ > 0, DT-learn(n, s, ϵ, δ) returns, with probability at least 1 − δ, an ϵ–approximation of f. The algorithm runs in Õ(ns^{12}ϵ^{−12} log (1/δ)) time. Tolerance of its queries is Ω(ϵ^{4}s^{−4}).

Proof: Given its input DT-learn gets H = BS_{\frac{1}{4}} (n, \frac{ϵ}{8s}, log \frac{8s}{ϵ}, δ). Denote g = ∑_{a∈H} f̃(a),

where f̃(a) is an estimate of f̂(a) satisfying |f̃(a)−f̂(a)| ≤ \sqrt{\frac{ϵ}{2}} \frac{ϵ}{16s} (such an estimate can be obtained using query (fχ_{a}, \sqrt{\frac{ϵ}{2}} \frac{ϵ}{2s}, U)). Then the algorithm returns h = sign(g). We need to prove that (given that BS succeeds) h calculated in this fashion is an ϵ−approximation of f. By Fact 6, Pr[h ≠ f] ≤ E[(f − g)^{2}], thus it is sufficient to prove that

E[(f − g)^{2}] = ∑_{a∈{0,1}^{n}}(f̂(a) − ĝ(a))^{2} ≤ ϵ .

Denote

V = \{a | f̂(a) ≤ \frac{ϵ}{8s} ∨ w(a) ≥ \frac{8s}{ϵ}\} .

Clearly, H ∪ V = {0, 1}^{n}. Thus

Pr[h ≠ f] ≤ E[(f − g)^{2}] = ∑_{a∈{0,1}^{n}}(f̂(a) − ĝ(a))^{2} =

∑_{a∈H}(f̂(a) − f̃(a))^{2} + ∑_{a∉H} f̂^{2}(a) ≤ ∑_{a∈H}(f̂(a) − f̃(a))^{2} + ∑_{a∈V} f̂^{2}(a)  (7)

Since every coefficient in H is at least \frac{ϵ}{16s}, |H| is at most (\frac{16s}{ϵ})^{2} and therefore the defined g satisfies :

∑_{a∈H}(f̂(a) − ĝ(a))^{2} = ∑_{a∈H}(f̂(a) − f̃(a))^{2} ≤ ϵ/2 ,

that is, the first term of equation (7) is at most ϵ/2. As is proved in Lemma 15 (for m = s and τ = ϵ/2), there exists a function f′ such that all the Fourier coefficients of f′ for vectors in V are 0 and E[(f − f′)^{2}] ≤ ϵ/2. That is,

ϵ/2 ≥ E[(f − f′)^{2}] = ∑_{a∈{0,1}^{n}}(f̂(a) − f̂′(a))^{2} ≥ ∑_{a∈V} f̂^{2}(a) .

Altogether, Pr[h ≠ f] ≤ ϵ. By properties of BS_{\frac{1}{4}} (see Theorem 12), the running time of the

algorithm is Õ(ns^{12}ϵ^{−12} log (1/δ)) and tolerance of its queries is Ω(ϵ^{4}s^{−4}). □

Remark 17 It can be easily seen that the size parameter is used only for “bounding” purposes and therefore if the parameter is not supplied to DT-learn we can use the standard guess-and-double technique instead. This remark is applicable to the rest of our algorithms as well.

3.5 Weak DNF Learning

Another simple application of the Bounded Sieve algorithm is weak DNF learning in SQ– D_{\frac{1}{4}} . It is based on the fact that every DNF expression has a “large” Fourier coefficient of “low” degree [BFJ^{+}94; Ja97]. Below we prove a generalization of this fact that will also be required for our future application. Let DNF-size(f) denote the size (number of terms) of a minimal DNF representation of f.

Lemma 18 Let f be a Boolean function, s = DNF-size(f) and D be a distribution over X. There exists a parity function χ_{a} such that E_{D}[fχ_{a}] ≥ \frac{1}{2s+1} and w(a) ≤ log ((2s + 1)L_{∞}(2^{n}D)).

Proof: As it was proved by Jackson [Ja97, Fact 8], there exists a parity function χ_{a} such that E_{D}[fχ_{a}] ≥ \frac{1}{2s+1}. Let A = \{i | a_{i} = 1\}. As it can be seen from the proof of the fact, A ⊆ T, where T is a term of f (a set of literals and a Boolean function it represents) and Pr_{D}[T = 1] ≥ \frac{1}{2s+1}. On the other hand,

Pr_{D}[T = 1] = ∑_{x,T (x)=1} D(x) < 2^{−|T |}2^{n}L_{∞}(D) .

Thus

w(a) = |A| ≤ |T | ≤ log ((2s + 1)L_{∞}(2^{n}D)) .
□

Theorem 19 There exists an SQ–D_{\frac{1}{4}} randomized algorithm UWDNF such that for any target concept f, s = DNF-size(f), ϵ > 0 and δ ≥ 0, UWDNF(n, s, δ) returns, with probability at least 1 − δ, a (\frac{1}{2} − \frac{1}{4s+4})–approximation to f. The algorithm runs in Õ(ns^{1}2 log (1/δ)) time. Tolerance of its queries is Ω(s^{−4}). The weak hypothesis is a parity function (possibly negated).

Proof: By Lemma 18, a call to BS_{\frac{1}{4}} (n, θ = \frac{1}{2s+1}, ℓ = log (2s + 1), δ) returns, with probability at least 1 − δ, a set containing at least one vector. We estimate every coefficient in the returned set with tolerance r = \frac{1}{(2s+1)(2s+2)} and choose the vector with the maximal Fourier coefficient (it will be larger than \frac{1}{2s+1} − r = \frac{1}{2s+2}). Parity function for this vector (or its negation) will give a (\frac{1}{2} − \frac{1}{4s+4})–approximation to the target. By Theorem 12 the running time of this invocation will be Õ(ns^{12} log (1/δ)) and tolerance of queries is Ω(s^{−4}).

3.6 Boosting the Weak DNF Learner

Certainly, the next interesting question is whether we can strongly learn DNF in SQ–D_{\frac{1}{4}} . We answer this question positively by following the way used by Jackson in his proof of DNF learnability. The proof consists of two components. The first one is weak DNF learning with respect to any given distribution (although efficient only on distributions that are polynomially close to uniform). The second one is Freund’s boosting technique that boosts the weak learner to a strong learner.

First we present the required weak learner.

Theorem 20 Let f be a Boolean function, s = DNF-size(f) and let D_{f} be a computable probability distribution over the sample space. The computation of D_{f}(x) may involve the value of f(x). There exists a randomized SQ–D_{\frac{1}{4}} algorithm WDNF_{\frac{1}{4}} such that for the target function f, confidence δ > 0 and β that bounds L_{∞}(2^{n}D_{f}), WDNF_{\frac{1}{4}} (n, s, D_{f}, β, δ) finds, with probability at least 1 − δ, a Boolean function h that (\frac{1}{2} − \frac{1}{4s+4})–approximates f. The algorithm runs in Õ(nβ^{8}s^{12} log (1/δ)) time. The tolerance of its queries is lower bounded by Ω̃(β^{−4}s^{−4}). Complexity of its query functions is the time complexity of D_{f} plus O(n). The weak hypothesis is a parity function(possibly negated).

Proof: As is proved in Lemma, 18 for every DNF expression f, there exists a parity function χ_{b} such that |E_{D_{f}} [fχ_{b}]| ≥ \frac{1}{2s+1} and

w(b) ≤ log ((2s + 1)L_{∞}(2^{n}D_{f})) ≤ log ((2s + 1)β) .

E_{D_{f}} [fχ_{b}] = E_{U}[2^{n}D_{f}fχ_{b}] thus in order to find a parity function that weakly approximates f with respect to D_{f} we can find the “large” Fourier coefficients of function 2^{n}D_{f}f. This means that by invoking

RV-BS_{\frac{1}{4}} (n, ϕ = 2^{n}D_{f}f, β, θ = \frac{1}{2s + 1}, ℓ = log ((2s + 1)β), δ)

and then proceeding as in UWDNF we can find the required weak approximator. By Theorem 13, we get that all the complexities are as stated. □

The next step is adapting Freund’s boosting technique to the SQ–D_{ρ} model. The main advantage of Freund’s booster F1 utilized by Jackson is that it requires only weak learning with respect to polynomially computable distributions that are polynomially close to the uniform distribution (i.e., L_{∞}(2^{n}D) ≤ p(n, s, ϵ) for some polynomial p). Freund’s boosting algorithm is not the only boosting algorithm possessing this advantage and is not the most efficient one (see discussion below). But its presentation is relatively simple and is sufficient for demonstrating the idea of adaptation.

Below we are going to give a brief account of Freund’s boosting technique [Fr90] and in particular his F1 algorithm for the PAC learning model with respect to distribution D.

As input, F1 is given positive ϵ, δ, and γ, a weak learner WL that produces (\frac{1}{2} − γ)–approximate hypotheses for functions in a function class F, and an example oracle EX(f, D) for some f ∈ F. The WL is assumed to take the example oracle for some distribution D′ and confidence parameter δ′ as inputs and produce (\frac{1}{2} − γ)–approximate hypothesis with probability at least 1−δ′. Given these inputs, F1 steps sequentially through k stages (k is given in Figure 3). At each stage i, 0 ≤ i ≤ k − 1 F1 generates distribution function D_{i}, runs WL on simulated oracle EX(f, D_{i}) and (with high probability) gets a (\frac{1}{2} − γ)–approximate hypothesis w_{i}. Simulation of the example oracle is done by filtering. Probability of acceptance of the next example is estimated before the simulation (to E_{α}). If the probability is “too low” the algorithm does not produce any more weak hypotheses. Finally, F1 generates its hypothesis using majority function MAJ of all the w_{i} it has received.

In Figure 3 we give the original implementation of Freund’s boosting algorithm F1.

Theorem 21 DNF is strongly learnable in the SQ–D_{ρ} model.

Proof: The first and simple step towards the adaptation of Freund’s algorithm to SQ–D_{\frac{1}{4}} is estimation of E_{α} using the procedure RV-SQ instead AMEAN (since we do not have access to EX(f, D)). This is possible since the value of α_{r_{i}(x)}^{i} can be found using f(x) and previous hypotheses. Next, we show how to provide our weak learner with distribution D_{i}. By the

definition, D_{i}(x) ≡ \frac{D(x)α_{r_{i}(x)}^{i}}{∑_{y} D(y)α_{r_{i}(y)}^{i}}. It is easy to see that given f(x) the value of D(x)α_{r_{i}(x)}^{i} can

be evaluated straightforwardly. On the other hand, the value of ∑_{y} D(y)α_{r_{i}(y)}^{i} (independent of x), which is the probability of accepting a sample from D, cannot be computed exactly. Instead, we can estimate this value. In fact, we already have the estimate: the value E_{α} used for termination condition (lines 12–14). The condition ensures that E_{α} ≥ \frac{2}{3}θ (otherwise we terminate) and E_{α} is an estimate of ∑_{y} D(y)α_{r_{i}(y)}^{i} within 1/3θ (line 11). Thus

1/2E_{α} ≤ ∑_{y} D(y)α_{r_{i}(y)}^{i} ≤ 3/2E_{α} .

This means that if we define D′_{i}(x) ≡ U(x)α_{r_{i}(x)}^{i}/E_{α} then we get that there is a constant c_{i} ∈ [1/2, 3/2] such that for all x, D′_{i}(x) = c_{i}D_{i}(x). Now consider the functional impact of supplying this approximate distribution rather than true distribution to WDNF_{\frac{1}{4}} . WDNF_{\frac{1}{4}} uses its given distribution for exactly one purpose: to find the “large” Fourier coefficients of function 2^{n}D_{f}f. Since the Fourier transform is a linear operator (i.e., ĉg(a) = cĝ(a)) we can be certain that 2^{n}D′_{i}f has a Fourier coefficient with absolute value of at least c_{i} \frac{1}{2s+1} ≥ \frac{1}{4s+2}. Moreover, since the largest Fourier coefficient of 2^{n}D′_{i}f corresponds to the largest Fourier coefficient of 2^{n}D_{i}f, the parity function corresponding to that coefficient (or its negation)

Input: Example oracle EX(f, D) ; 0 < γ ≤ \frac{1}{2}; (\frac{1}{2} − γ)–approximate weak learner WL(EX, δ) which succeeds with probability at least 1 − δ; ϵ > 0; δ > 0 Output: h such that, with probability at least 1 − δ, Pr_{D}[f = h] ≥ 1 − ϵ

1. γ̂ ≡ min (γ, 0.39)

2. k ← \frac{1}{2}γ^{−2} ln (4/ϵ)

3. w_{0} ← W L(EX(f, D), δ/2k)

4. for i ← 1, …, k − 1 do

5. r_{i}(x) ≡ |{0 ≤ j < i|w_{j}(x) = f(x)}|

6. B(j; n, p) ≡ \binom{n}{j}p^{j}(1 − p)^{n−j}

7. α̃_{r}^{i} ≡ B(⌊k/2⌋ − r; k − i − 1, 1/2 + γ̂) if i − k/2 < r ≤ k/2, α̃_{r}^{i} ≡ 0 otherwise

8. α_{r}^{i} ≡ α̃_{r}^{i}/ max_{r′=0,...,i−1}{α̃_{r′}^{i}}

9. θ ≡ ϵ^{3}/57

10. Y ≡draw example ⟨x, f(x)⟩ from EX(f, D) and compute α_{r_{i}(x)}^{i}

11. E_{α} ← AMEAN(Y, b − a = 1, \frac{1}{3}θ, \frac{δ}{2k})

12. if E_{α} ≤ \frac{2}{3}θ then

13. k ← i

14. break do

15. endif

16. D_{i}(x) ≡ \frac{D(x)α_{r_{i}(x)}^{i}}{∑_{y} D(y)α_{r_{i}(y)}^{i}}

17. w_{i} ← W L(EX(f, D_{i}), \frac{δ}{2k})

18. enddo

19. h(x) ≡ MAJ(w_{0}(x), w_{1}(x), ..., w_{k−1}(x)

20. return h

Figure 3: Freund’s algorithm for boosting a weak learner in the PAC model. EX(D_{i}, f) is a simulated example oracle.

(\frac{1}{2} − \frac{1}{4s+2})–approximates target function with respect to D_{i}. Thus by slightly modifying ^{7} WDNF_{\frac{1}{4}} we can handle this problem. These modifications may increase the running time of weak learner only by a small constant and thus do not affect our analysis.

Input: Access to ST AT (f, D_{\frac{1}{4}} ); s = DNF-size(f); ϵ > 0; δ > 0 Output: h such that, with probability at least 1 − δ, Pr_{U}[f = h] ≥ 1 − ϵ

1. γ ← \frac{1}{4s+4};

2. k ← \frac{1}{2}γ^{−2} ln (4/ϵ)

3. w_{0} ←UWDNF_{\frac{1}{4}} (n, s, δ/k)

4. for i ← 1, …, k − 1 do

5. r_{i}(x) ≡ |{0 ≤ j < i|w_{j}(x) = f(x)}|

6. B(j; n, p) ≡ \binom{n}{j}p^{j}(1 − p)^{n−j}

7. α̃_{r}^{i} ≡ B(⌊k/2⌋ − r; k − i − 1, 1/2 + γ̂) if i − k/2 < r ≤ k/2, α̃_{r}^{i} ≡ 0 otherwise

8. α_{r}^{i} ≡ α̃_{r}^{i}/ max_{r′=0,...,i−1}{α̃_{r′}^{i}}

9. θ ← ϵ^{3}/57

10. E_{α} ←RV-SQ(STAT(f, U), α_{r_{i}(x)}^{i}, 1, θ/3)

11. if E_{α} ≤ \frac{2}{3}θ then

12. k ← i

13. break do

14. endif

15. D′_{i}(x) ≡ U(x)α_{r_{i}(x)}^{i}/E_{α}

16. w_{i} ←WDNF_{\frac{1}{4}} (n, s, D′_{i}, 3/(2θ), δ/k)

17. enddo

18. h(x) ≡ MAJ(w_{0}(x), w_{1}(x), ..., w_{k−1}(x))

19. return h

Figure 4: Learning DNF in the SQ–D_{\frac{1}{4}} model

In Figure 4 we give a straightforward implementation of the discussed adaptation.

Our last concern is the complexity of this algorithm. The total number of phases executed will be O(s^{2} log ϵ^{−1}). Clearly the “heaviest” part of each phase is the execution of the weak learner. By Theorem 20, the running time of each call to WDNF_{\frac{1}{4}} is Õ(ns^{12}ϵ^{−24} log (1/δ)). Thus the total running time of the algorithm is Õ(ns^{14}ϵ^{−24} log (1/δ)). The tolerance of queries is Ω̃(s^{−4}ϵ^{12}). The complexity of query functions is as complexity of evaluation of α_{r_{i}(x)}^{i} plus O(n). All the O(k^{2}) = Õ(s^{4}) possible values of α_{r_{i}(x)}^{i} can be evaluated in advance, that is complexity of query functions will be O(n). □

The adaptation of boosting algorithm that we obtained is not suitable for boosting weak learners which will fail when supplied with distributions D′_{i} as above instead of D_{i}. Except for this limitation we, in fact, described the general way to boost weak learners in the SQ–D model.

7. Lower bound θ has to be modified to \frac{1}{4s+2} .

Recently, two new boosting algorithms have appeared that use only distributions that are polynomially close to the uniform. The first one is by Klivans and Servedio [KS99] and the second one is by Bshouty and Gavinsky [BG01]. Distributions produced by these boosting algorithms are optimally “flat”, that is, the L_{∞} norm of distributions they produce is Õ(ϵ)2^{−n}. They also require the same order of phases as F1. Both algorithms are more complicated than F1, but nevertheless can be adapted to SQ–D in a very similar way. These algorithms were used to improve the running time of Jackson’s original algorithm and can be substituted for F1 in our algorithm as well. This would significantly decrease the dependence on ϵ. In particular, L_{∞}(D_{i}) = Õ(ϵ^{−1}) and k = O(γ^{−2} log (1/ϵ)) gives the running time of Õ(ns^{14}ϵ^{−8} log (1/δ)) and tolerance becomes lower-bounded by Ω̃(s^{−4}ϵ^{4}).

4. Learning with Attribute Noise in Membership Queries

We now turn our attention to another type of noise in membership queries: the noise that corrupts the attributes of a sample point. That is, as an answer to a membership query at point x the learner gets the value of f(x′), where x′ might differ from x. This type of noise was previously considered as appearing in the example oracle EX(f, D), that is the learner gets random labelled samples (x, f(x′)) [SV88; GS95; BJT99]. We define the noise model formally and then focus our attention on the product attribute noise with known noise rate (which is the most commonly referred type of attribute noise). We prove that membership queries corrupted by such a noise are weaker than extended statistical queries discussed in the previous chapter. Nevertheless, the Bounded Sieve can be implemented in this model. This implies that DT is learnable and DNF is weakly learnable in this “weak” model. We prove that these learning results can also be achieved for the uniform product attribute noise of unknown rate.

4.1 The Noise Model and Its Properties

The attribute noise is usually described as returning the value f(x ⊕ b) where b is sampled randomly with respect to some noise distribution D′. The simplest and the most well studied noise distribution is the product distribution, i.e., independence of all the attributes is assumed.^{8} If every attribute is changed with the same probability the noise is called uniform. The resulting model represents the situation in which the learner cannot ask the membership query in the desired point since the attributes it supplies change their state randomly and independently in the process of the query. Examples of situations of this kind are:

• sending the point x to the oracle via a faulty communication channel^{9}

• “material” representing the attributes is unstable.

8. This assumption certainly agrees with assumptions of learning with respect to the uniform.

9. For this case the attribute noise is uniform and random classification noise has to be added if the answer

is also sent via a faulty channel.

Formally, the noise model is defined in the following way. For a constant probability vector p ∈ (0, 1)^{n} and D_{p} the product distribution defined by p, we define noisy membership oracle MEM^{p}(f) as follows. For a query x, MEM^{p}(f) chooses randomly (and independently of any previous queries) b according to the distribution D_{p} and returns f(x ⊕ b). We can assume that for all i, p_{i} ≤ 1/2 since inverting the i-th attribute of the query is equivalent to changing p_{i} to 1 − p_{i}.

We may also add classification noise to the oracle and define MEM^{p,η}(f). This classification noise does not have to be persistent as the learner cannot get a label of the same point twice (with any non-negligible probability).

The use of membership queries with product attribute noise can be related to the SQ–D_{ρ} model in the following way.

Theorem 22 For p ∈ [ρ, 1/2]^{n} MEM^{p} can be efficiently simulated in SQ–D_{ρ}.

Proof: The result of query at point x to oracle MEM^{p} is a Bernoulli random variable (or a coin flip) such that e ∈ {1, −1} is returned with probability Pr_{y∼D_{p}}[f(x ⊕ y) = e]. Given these probabilities for every x, MEM^{p} can be replaced by an appropriate coin flip. Moreover, the exact values of probabilities are not required, since the ability to approximate them efficiently will suffice to simulate the MEM^{p} oracle. But

Pr_{y∼D_{p}}[f(x ⊕ y) = e] = Pr_{y∼D_{p⊕x}}[f(y) = e] ,

i.e., this probability can be estimated in SQ–D whenever D_{p⊕x} ∈ D. Thus for D = {D_{p⊕x} | x ∈ {0, 1}^{n}} MEM^{p} can be simulated in SQ–D. Such D is included in the class of probability distributions which for every i, gives a learning algorithm a degree of control p_{i} over attribute i (see Remark 10 for details about the definition). For every i, p_{i} ∈ [ρ, 1/2] and thus by Lemma 9 and Remark 10, MEM^{p} can be simulated in SQ–D_{ρ}. □

4.2 Offsetting Attribute Noise in the Bounded Sieve

Let τ > 0 be a constant and p ∈ [0, 1/2 − τ]^{n} be a probability vector. We are now going to show that we can implement the Bounded Sieve using access to MEM^{p} oracle (we call the resulting algorithm AN-BS where AN stands for attribute noise).

Theorem 23 There exists a randomized algorithm AN-BS that for any target concept f, threshold θ > 0 , degree bound 0 ≤ ℓ ≤ n, confidence δ > 0 and probability vector p (with restrictions as above), AN-BS(MEM^{p}, n, θ, ℓ, δ, p) returns, with probability at least 1 − δ, a set with the large Fourier coefficient property for function f, threshold θ and degree ℓ. Its running time is polynomial in n, θ^{−1}, 2^{ℓ} and log (1/δ).

Proof: A query to the oracle MEM^{p}(f) at point y returns f(y ⊕ b) where b is chosen randomly according to the distribution D_{p}. Thus by Hoeffding’s formula we can efficiently approximate f^{p}(y) ≜ E_{b∼D_{p}}f(y ⊕ b). Obviously, for every x, |f^{p}(x)| ≤ 1 and thus ∥f^{p}∥ ≤ 1. Now, by using the real-valued version of the KM algorithm (see Remark 7 in Section 2.5) we can find a set with the large Fourier coefficients property for function f^{p} and threshold ϑ in time polynomial in n, ϑ^{−1} and log (1/δ). But

f^{p}(y) = E_{b∼D_{p}}[f(y⊕b)] = ∑_{a∈{0,1}^{n}} f̂(a)E_{b∼D_{p}}[χ_{a}(y⊕b)] = ∑_{a∈{0,1}^{n}} (f̂(a)E_{b∼D_{p}}[χ_{a}(b)]) χ_{a}(y),

i.e., we have that for all a, f̂^{p}(a) = f̂(a)E_{b∼D_{p}}χ_{a}(b). We can easily calculate the value c_{a} ≜ E_{b∼D_{p}}χ_{a}(b) = ∏_{a_{i}=1}(1 − 2p_{i}). By the properties of p, |c_{a}| ≥ (2τ)^{w(a)}. Thus if we run the above algorithm for the threshold ϑ = (2τ)^{ℓ}θ we will get the set S′ that includes a set with the large Fourier coefficient property for the function f and threshold θ. Size of S′ is bounded by (2τ)^{−2ℓ}θ^{−2}. In order to estimate the values of the coefficient f̂(a) with accuracy σ we estimate the coefficient f̂^{p}(a) with accuracy σc_{a} ≥ (2τ)^{ℓ}σ and return c_{a}^{−1}f̂^{p}(a). Thus we can refine the set S′ and return a set with the large Fourier coefficient property for the function f, threshold θ and degree ℓ. All the parts of the described algorithm run in time polynomial in n, (2τ)^{−ℓ}θ^{−1} and log (1/δ), that is, for a constant τ the time is polynomial in n, θ^{−1}, 2^{ℓ}, and log (1/δ) □

Remark 24 It is easy to note that knowing the noise rates exactly is not necessary. That is, the result will hold when the learning algorithm is supplied with “good” estimates of the noise rates. Particularly, estimates within inverse of a polynomial (in learning parameters) will suffice.

Remark 25 When using MEM^{p,η}(f) oracle instead of MEM^{p}(f) in the above algorithm we can immediately offset the classification noise by using the fact: f^{p,η}(y) = (1 − 2η)f^{p}(y), where f^{p,η}(y) is the expectation of the query in point y to the oracle MEM^{p,η}(f). This will require increasing the accuracy of the estimation by \frac{1}{1−2η} and make the running time of the algorithm polynomially dependent on \frac{1}{1−2η}.

By sole use of AN-BS we can efficiently learn DT and weakly learn DNF as described in Theorems 16 and 19.

4.3 Coping with Attribute Noise of Unknown Rate

As was shown by Goldman and Sloan [GS95], coping with attribute noise becomes much more difficult when the noise rates are unknown.^{10} The reason for this is that the usual way of handling the unknown noise rate—choosing the hypotheses with the minimum disagreement on samples—does not work for this type of noise. Nevertheless, several simple classes (e.g., k−DNF and monomials) are learnable when the attribute noise is uniform [GS95; DG95]. The following two theorems show that our learnability results hold in this setting as well.

Theorem 26 DT is learnable by membership queries with uniform attribute noise of fixed unknown rate ν < 1/2.

10. In fact, no PAC learning algorithm exists that can tolerate a noise rate higher than 2ϵ, where ϵ is the

required accuracy parameter.

Sketch of proof: Learning algorithm has access to MEM^{p} oracle for p = [ν]^{n}. For the ease of presentation let us assume that all estimations we do by sampling produce the exact result. In particular, our AN-BS algorithm returns all the vectors with Fourier coefficients larger than the bound that was given to it(and only them) and we can estimate exactly coefficients of the function f^{p} defined in the proof of Theorem 23. For positive ν′ < 1/2 we look at the execution of AN-BS for learning DT supplied with noise rate ν′ (equal for all the attributes) instead of the actual noise rate, i.e.,

AN-BS(δ, MEM^{p}, n, \frac{ϵ}{8s}, log \frac{8s}{ϵ}, [ν′]^{n})

We then find all the Fourier coefficients for returned vectors and offset the effect of noise by multiplying every coefficient f̂^{p}(a) by (1 − 2ν′)^{−w(a)} (as if ν′ is a correct noise rate). We denote the function defined by coefficients we have found by f_{ν′}^{p} (with the assumptions we made this function is well-defined). If ν′ = ν then the algorithm we have just described will find all the required vectors and calculate their Fourier coefficients correctly. Thus, as follows from Lemma 15, 1 − ϵ < ∥f_{ν}^{p}∥^{2} ≤ 1. It is easy to note that the larger the supplied noise rate ν′ is, the more vectors the execution of AN-BS returns (since the threshold gets lower) and the larger is the value by which we multiply every Fourier coefficient of f^{p} that was found by AN-BS. That is, for every a ∈ {0, 1}^{n}, |f̂_{ν′}^{p}(a)| and ∥f_{ν′}^{p}∥^{2} are monotonous in ν′. Thus by using a binary search we can efficiently find a value ν′ for which 1 − ϵ ≤ ∥f_{ν′}^{p}∥^{2} ≤ 1 + ϵ (∗) (the search will be efficient since values which are “close” to ν will satisfy this criterion). Denote the value we have found by ν_{1}. As we have noted, for every vector a, |f̂_{ν′}^{p}(a)| is monotonous in ν′ thus the criterion (∗) that ν_{1} satisfies ensures that

|∥f_{ν}^{p}∥^{2} − ∥f_{ν′}^{p}∥^{2}| = |∑_{a} (f̂_{ν}^{p}^{2}(a) − f̂_{ν′}^{p}^{2}(a))| ≤ 2ϵ  (8)

On the other hand, as it was shown in the proof of Theorem 16, sign(f_{ν}^{p}) ϵ–approximates f and therefore

∑_{a} (f̂_{ν}^{p}(a) − f̂(a))^{2} ≤ ϵ  (9)

By combining equations 8 and 9 we can easily obtain that

∑_{a} (f̂_{ν_{1}}^{p}(a) − f̂(a))^{2} ≤ 3ϵ  (10)

That is, sign(f_{ν_{1}}^{p}) 3ϵ–approximates f. □

Remark 27 Without the “exactness” assumption we made in this proof we will need to improve the tolerance of all the queries so that the overall error in computation of f_{ν′}^{p} be smaller than ϵ/8 (and substitute ϵ/4 for ϵ in other bounds).

Theorem 28 DNF is weakly learnable by membership queries with uniform attribute noise of fixed unknown rate ν < 1/2.

Sketch of proof: We define f_{ν′}^{p} as in the previous proof. We denote by λ(ν′) the absolute value of the maximal Fourier coefficient of f_{ν′}^{p} and by α(ν′) its corresponding vector. It is easy to see that λ(ν′) is monotonous in ν′ (by the same argument as in the previous proof). It is also given by the properties of DNF expressions that λ(ν) ≥ \frac{1}{2s+1}, where s is number of terms in the target function. Thus we can find the minimal ν′ for which λ(ν′) ≥ \frac{1}{2s+1} (as usual, an estimate for this value is sufficient). We denote this error rate by ν_{m}. By the definition of ν_{m}, ν ≥ ν_{m} and therefore

λ(ν) = |f̂(α(ν_{m}))| ≥ λ(ν_{m}) ≥ \frac{1}{2s + 1} ,

i.e., χ_{α(ν_{m})} (or its negation) (\frac{1}{2} − \frac{1}{4s+2})–approximates the target. □

Remark 29 Both algorithms provided above can also be modified to tolerate the classification noise of the same (unknown) rate ν.

5. Limitations of the SQ-D Model

So far we have been showing, so called, positive results about the models that we have introduced. The other side of understanding a model is proving that certain classes are not learnable in the model (or so called negative results). Non-trivial results of this kind are usually very hard to achieve. Fortunately for us, the statistical query model is the most tractable (non-trivial) learning model. In this chapter we extend this “tractability” to the SQ–D model. This will be done by showing a new and simple way to characterize weakly SQ–learnable concept classes. This characterization will then be extended to SQ–D and applied to classes of parity functions.

5.1 Properties of Statistical Queries

We start by showing a simple property of statistical queries which simplifies the analysis of the SQ model. According to the definition of statistical query, the query function ψ is a Boolean function of two parameters. The first one is denoted by x and the second one is denoted by f(x) according to the values substituted when estimating the expectation of the query function. We distinguish two types of statistical queries (either regular or extended) based on their query function. We say that a query is independent of the target if it is based on ψ which is a function of x alone (and does not depend on the value of the second parameter – f(x)) and we say that a query is correlational if ϕ(x, f(x)) ≡ g(x)f(x) for a Boolean function g(x).

Lemma 30 Any statistical query (regular or extended) can be substituted by two statistical queries that are independent of the target and two correlational queries.^{11}

Proof: We denote the distribution of the query by D. The following equation proves the statement:

E_{D}[ψ(x, f(x))] = E_{D} [ψ(x, −1)\frac{1 − f(x)}{2} + ψ(x, 1)\frac{1 + f(x)}{2}] =

11. This decomposition appears implicitly in [BFJ^{+}94].

\frac{1}{2}E_{D}[ψ(x, 1)f(x)] − \frac{1}{2}E_{D}[ψ(x, −1)f(x)] + \frac{1}{2}E_{D}[ψ(x, 1)] + \frac{1}{2}E_{D}[ψ(x, −1)] .

□

A query that is independent of the target is estimation of the expectation of random variable which is independent of f and therefore such a query can be substituted by a call to procedure AMEAN (we assume that the learning algorithm is able to sample randomly with respect to the distribution of the query). Thus we may assume that learning algorithms in the statistical query based models use only the correlational statistical queries.

5.2 The Characterization

We are now going to present the characterization of classes weakly learnable in statistical query based models. Let F be the concept class and A be an algorithm that weakly learns F in the SQ model (and uses only correlational queries). The characterization is based on the following observation: for every (but, probably, one) function in F there exists a correlational query for which A gets a reply which differs “noticeably” from 0. This is true because there could not exist two different functions in F for which the results of all the queries are “almost” equal. For every f ∈ F denote by g_{f} the function for which |E_{D}[fg_{f}]| differs “noticeably” from 0, that is, g_{f} (or its negation) weakly approximates f. This means that the set of queries of A weakly “approximates” all (but, probably, one) functions in F. This argument is formalized in the following way. Let V and W be sets of Boolean functions. We say that W ϵ–approximates V with respect to distribution D if for every f ∈ V there exists g ∈ W such that g ϵ–approximates f with respect to distribution D. For a concept class F denote by F^{s} the set of all the functions in F of size s.

Theorem 31 Let F be a concept class weakly SQ–learnable with respect to D, particularly, there exists an algorithm A that for every f ∈ F^{s}, uses at most p(n, s) queries of tolerance lower-bounded by \frac{1}{r(n,s)} to produce (\frac{1}{2} − \frac{1}{q(n,s)})–approximation to f. Let r′(n, s) ≜ max{2r(n, s), q(n, s)}. There exists a collection of sets {W_{i}}_{i=1}^{∞} such that |W_{s}| ≤ p(n, s)+1 and W_{s} (\frac{1}{2} − \frac{1}{r′(n,s)})–approximates F^{s} with respect to D.

Proof: According to the above discussion, we may assume that A uses only correlational queries. We build the set W_{s} as follows. We simulate algorithm A(n, s) and for every query (fg_{i}, ρ) we add g_{i} to W_{s} and return the value 0 as a result of the query. We continue the simulation till it violates any of the complexity bounds of A or A stops and returns final hypothesis h. In the later case we also add h to W_{s}. First, by the definition of W_{s}, |W_{s}| ≤ p(n, s) + 1. Now, assume that W_{s} does not (\frac{1}{2} − \frac{1}{r′(n,s)})–approximate F^{s}, i.e., there exists f ∈ F^{s} such that for every g ∈ W_{s}, |E_{D}[fg]| < \frac{2}{r′(n,s)}. This means that in our simulation for building W_{s}, zeros that we gave as answers are valid answers to the queries. Therefore, by the definition of A, it returns hypothesis h that (\frac{1}{2} − \frac{1}{q(n,s)})–approximates f, that is, h ∈ W_{s}. This contradicts the assumption that |E_{D}[fh]| < \frac{2}{r′(n,s)} ≤ \frac{2}{q(n,s)}. □

In the above proof we assumed that A is a deterministic algorithm. On the other hand, the proof does not rely on the uniformity of the algorithm A (our only restriction is the polynomial number of queries). As is well known, any randomized algorithm can be transformed into non-uniform (deterministic) algorithm (in the context of languages this result is referred as BPP ⊂ P/poly). Therefore, Theorem 31 is also true for classes weakly learnable by randomized algorithms.

This characterization can be easily extended to SQ–D in the following way. Every query (fg, ρ, D′) to STAT(f, D) has its own distribution D′ ∈ D. Thus the fact that results of a query differ “noticeably” from 0 means that f is weakly approximated with respect to some distribution from D. Distinct queries may use distinct distributions from D and therefore along with every function in the approximating collection of sets we need to record the distribution with respect to which function in F is approximated. Formally, we say that a set W ⊆ {−1, 1}^{X} × D ϵ–approximates the set V of Boolean functions with respect to D if for every f ∈ V there exists a pair (g, D′) ∈ W such that g ϵ–approximates f with respect to D′. Theorem 31 is generalized to SQ–D as follows.

Theorem 32 Let F be a class learnable in SQ–D. For p and r′ defined as in Theorem 31 there exists a collection of sets {W_{i}}_{i=1}^{∞} such that W_{s} ⊆ {−1, 1}^{X} × D, |W_{s}| ≤ p(n, s) + 1 and W_{s} (\frac{1}{2} − \frac{1}{r′(n,s)})–approximates F^{s} with respect to D.

5.3 Applications

Although the characterization we gave for the SQ model is not equivalent to characterization by SQ–DIM [BFJ^{+}94] (see Section 1.1 for more details) it is applied in a very similar way. To demonstrate this we give a new proof for the main result obtained using the SQ–DIM characterization.

Theorem 33 Any concept class containing superpolynomial number of parity functions is not weakly SQ–learnable with respect to the uniform distribution.

Proof: Since the size of representation of any parity function is bounded by a fixed polynomial (e.g., c_{0}n) by Theorem 31 (with Remark 1) we have that there exist polynomials r(n) and p(n) such that F has a (\frac{1}{2} − \frac{1}{r(n)})–approximating set W of size bounded by p(n). For any g ∈ W approximating a parity function χ_{a} means that |E[g(x)χ_{a}]| = |ĝ(a)| ≥ 2/r(n). But from Parseval’s identity we know that ∑_{a∈{0,1}^{n}} ĝ^{2}(a) = 1. This means that at most r^{2}(n)/4 Fourier coefficients of g could be greater than 2/r(n), i.e., every g ∈ W could be correlated with at most r^{2}(n)/4 different parity functions. On the other hand, |W | ≤ p(n), that is, W can approximate at most p(n)r^{2}(n)/4 parity functions. Thus, any F containing a superpolynomial number of parity functions is not weakly SQ–learnable with respect to the uniform distribution. □

Our characterization of SQ–D learnable classes can be used to show the limitations of the SQ–D_{ρ} model. BS_{ρ} can be straightforwardly used to learn the class of all parity function containing at most O(log n) variables (with respect to U). On the other hand, we will show that the class of all the parity functions containing at most c(n) log n variables for unbounded c(n) cannot be learned in SQ–D_{ρ}. For this purpose we denote by A^{k} = {0, 1}^{k}[0]^{n−k}, and let PAR^{k} denote the class of all parity functions for vectors in A^{k}, i.e., all parity functions based on the first k variables. In fact, we give somewhat stronger result.

Theorem 34 PAR^{k} is not weakly learnable in SQ–D_{ρ} for k(n) = ω(log n).

Proof: Assume that the theorem is not true. By Theorem 32 (with Remark 1) there exist polynomials p(n) and r(n) and set of pairs W = {(g_{1}, D_{1}), (g_{2}, D_{2}), …, (g_{m}, D_{m})} such that |W | = m ≤ p(n) and for every χ_{a} ∈ PAR^{k} there exists (g_{i}, D_{i}) ∈ W, where D_{i} ∈ D_{ρ}, such that E_{D_{i}}[g_{i}χ_{a}] ≥ 1/r(n). This means that ∑_{1≤i≤m} E_{D_{i}}^{2}[g_{i}χ_{a}] ≥ 1/r^{2}(n). Thus

∑_{a∈A^{k}} ∑_{1≤i≤m} E_{D_{i}}^{2}[g_{i}χ_{a}] ≥ |A^{k}|/r^{2}(n)

This means that there exists i such that

∑_{a∈A^{k}} E_{D_{i}}^{2}[g_{i}χ_{a}] ≥ |A^{k}|/(|W |r^{2}(n)) ≥ |A^{k}|/(p(n)r^{2}(n)).

Or, if we denote by U^{k} a uniform distribution over A^{k}, then we get that

I ≜ E_{a∼U^{k}} [E_{D_{i}}^{2}[g_{i}χ_{a}]] ≥ 1/(p(n)r^{2}(n)).  (11)

On the other hand,

I = E_{a∼U^{k}} [E_{D_{i}}^{2}[g_{i}χ_{a}]] = E_{a∼U^{k}} [E_{x∼D_{i}} [E_{y∼D_{i}}[g_{i}(x)χ_{a}(x)g_{i}(y)χ_{a}(y)]]] = E_{x∼D_{i}}[E_{y∼D_{i}}[g_{i}(x)g_{i}(y)E_{a∼U^{k}}[χ_{a}(x ⊕ y)]]] . (12)

But

λ(z) ≜ E_{a∼U^{k}}[χ_{a}(z)] = E_{a∼U^{k}}[χ_{z_{[1,k]}}(a_{[1,k]})] = \{ \begin{matrix}0 & z_{[1,k]} ≠ [0]^{k} \\ 1 & z_{[1,k]} = [0]^{k} \end{matrix}

Since λ(x ⊕ y) is non-negative and |g_{i}(x)g_{i}(y)| = 1, equation (12) yields that

I ≤ E_{x∼D_{i}} [E_{y∼D_{i}}[λ(x ⊕ y)]] = E_{x∼D_{i}} [Pr_{y∼D_{i}}[λ(x ⊕ y) = 1]]

= E_{x∼D_{i}}[Pr_{y∼D_{i}}[y_{[1,k]} = x_{[1,k]}]] ≤ E_{x∼D_{i}}[(1 − ρ)^{k}] ≤ (1 − ρ)^{k} . (13)

For k = ω(log n), (1 − ρ)^{k} cannot be lower-bounded by inverse of a polynomial and thus equation (11) contradicts equation (13). □

The last theorem may also be used to prove that the set of concept classes learnable in the PAC model with classification noise of constant rate is not contained in the set of concept classes weakly learnable in SQ–D_{\frac{1}{4}} . This result can be obtained by combining our result with the following theorem for k = log n log log n [BKW00, Theorem 2].

Theorem 35 PAR^{k} for noise rate η equal to any constant less than \frac{1}{2}, can be learned with respect to the uniform distribution using number of samples and total computation time 2^{O(k/ log k)}.

Another interesting application of our characterization is to demonstrate that PAR, the class of all parity functions, possesses some inherent hardness for any statistics based learning. For this purpose we give the following definition. We say that a distribution class D is biased if there exist a polynomial p(n) such that L_{∞}(D) ≥ \frac{1}{p(n)}. We may notice that if a distribution class D is biased then a non-uniform learning algorithm may get the value of the target function at the “biased” point. Use of attributes of specific point together with its label contradicts the idea of statistical learning and, on the other hand, is the main element of all the known algorithms for learning of parity functions.

Theorem 36 Let D be a class of distributions. If D is not biased then for every D ∈ D, PAR is not weakly learnable in the SQ–D model with respect to D.

Proof: By assuming that PAR is weakly learnable in SQ–D with respect to some distribution D ∈ D and then proceeding as in the proof of the previous theorem we get that there exists set W and (g_{i}, D_{i}) ∈ W (D_{i} ∈ D) such that

E_{a∼U} [E_{D_{i}}^{2}[g_{i}χ_{a}]] ≥ 1/(p(n)r^{2}(n)).

On the other hand,

E_{a∼U} [E_{D_{i}}^{2}[g_{i}χ_{a}]] = E_{a∼U} [E_{x∼D_{i}}[E_{y∼D_{i}}[g_{i}(x)χ_{a}(x)g_{i}(y)χ_{a}(y)]]] = E_{x∼D_{i}}[E_{y∼D_{i}}[g_{i}(x)g_{i}(y)E_{a∼U}[χ_{a}(x ⊕ y)]]] (14)

By the properties of parity functions, if x ≠ y then E_{a∼U}[χ_{a}(x ⊕ y)] = E_{a∼U}[χ_{x⊕y}(a)] = 0. Otherwise, E_{a∼U}[χ_{a}(0^{n})] = 1. So the expression we are evaluating is equal to

E_{x∼D_{i}}[D_{i}(x)g_{i}^{2}(x)] = E_{x∼D_{i}}[D_{i}(x)]

Thus we got that E_{x∼D_{i}}[D_{i}(x)] ≥ 1/(p(n)r^{2}(n)), in particular there exists x such that D_{i}(x) ≥ 1/(p(n)r^{2}(n)), that is, D is biased. This contradiction finishes the proof. □

6. Conclusions and Open Problems

In this work we have shown that DNF is learnable in an extension of the PAC model (PAC-D_{ρ}) that seems to be weaker than the use of membership queries. While it seems to be very difficult to say anything about the exact strength of the PAC-D_{ρ} model, we can show that the statistical query analogue of PAC-D_{ρ} (SQ–D_{ρ}) is sufficient for our DNF learning algorithm. This fact combined with characterization of SQ–D_{ρ} learnable classes was used to show that, in terms of learning parity functions, SQ–D_{ρ} has just enough power to be able to learn parity functions that can be expressed as polynomial-size DNF expressions. Another useful property of the SQ–D_{ρ} model used is that it can be simulated using membership queries with persistent classification noise.

We have introduced an extension of attribute noise to membership queries. It turns out that the use of membership queries with product attribute noise is interestingly related to the SQ–D_{ρ} model. We have shown that decision trees are learnable and DNF expressions are weakly learnable by membership queries with product attribute noise.

The introduction of new model between PAC_{U} and PAC_{U}+MQ poses interesting and apparently difficult questions about the relation between the strengths of these models. Another interesting question of similar nature is whether there exists a class learnable in SQ– D_{ρ} and not learnable by membership queries with product attribute noise, and particularly (in case the answer is positive) whether DNF is such a class. As we have proved, the power of SQ–D_{ρ} does not decrease when we decrease ρ. But it remains unclear to us whether the power is strictly increasing or the models are equally strong (for a constant 0 < ρ < 1/2).

Acknowledgments

This research was supported by the fund for the promotion of research at the Technion. Part of research was done at the University of Calgary, Calgary, Alberta, Canada.

We would like to thank Dmitry Gavinsky, Jeff Jackson and Eyal Kushilevitz for useful discussions about this research, and to anonymous referees of COLT/EuroCOLT 2001 conference and Journal of Machine Learning Research for their careful reading, corrections, and insightful comments on this work.

References

[AD93] Javed Aslam, Scott Decatur. General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Boosting. In Proceedings of 34-th Annual Symposium on Foundations of Computer Science, pp. 282–291, 1993.

[AL88] Dana Angluin, Philip Laird. Learning From Noisy Examples. In Machine Learning, 2(4) pp.343–370, 1988.

[AK91] Dana Angluin, Michael Kharitonov. When Won’t Membership Queries Help? In Proceedings of the 23-rd Annual ACM Symposium on Theory of Computing, 1991, pp. 454–454.

[Bs93] Nader Bshouty. Exact Learning via the Monotone Theory. In Proceedings of 34-th Annual Symposium on Foundations of Computer Science, pp. 302–311, 1993.

[BFJ^{+}94] Avrim Blum, Merrick Furst, Jeffrey Jackson, Michael Kearns, Yishay Mansour, Steven Rudich. Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis. In Proceedings of the 26-th Annual ACM Symposium on the Theory of Computing, pp. 253–262, 1994.

[BF01] Nader Bshouty, Vitaly Feldman. On Using Extended Statistical Queries to Avoid Membership Queries. In Proceedings of the 14-th Annual Conference on COLT/EuroCOLT, pp. 529–545, 2001.

[BG01] Nader Bshouty, Dmitry Gavinsky. On Boosting With Optimal Poly-Bounded Distributions. In Proceedings of the 14-th Annual Conference on COLT/EuroCOLT, pp. 490–506, 2001.

[BJT99] Nader Bshouty, Jeffrey Jackson, Christino Tamon. Uniform-Distribution Attribute Noise Learnability. In Proceedings of the 12-th Annual Conference on COLT, pp. 75–80, 1999.

[BKW00] Avrim Blum, Adam Kalai, Hal Wasserman. Noise-Tolerant Learning, the Parity Problem and the Statistical Query Model. In Proceedings of the 32-th Annual ACM Symposium on Theory of Computing, pp. 435–440, 2000.

[DG95] Scott Decatur, Rosario Gennaro. In Proceedings of the Eighth Annual ACM Workshop on Computational Learning Theory, pp.353–360, 1995.

[Fr90] Yoav Freund. Boosting a Weak Learning Algorithm by Majority. In Proceedings of the Third Annual Workshop on COLT, pp. 202–216, 1990.

[FS94] Yoav Freund, Robert Schapire. A Decision-theoretic Generalization of On-line Learning and an Application to Boosting. In Proceedings of the Second Annual European Conference on Computational Learning Theory, 1994.

[GKS94] Sally Goldman, Michael Kearns, Robert Shapire. Exact Identification of Circuits Using Fixed Points of Amplification Functions, In SIAM Journal on Computing, 22 (1993), pp. 705–726.

[GL89] Oded Goldreich, Leonid A. Levin. A Hard-Core Predicate for all One-Way Functions. In Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, pp. 25–32, 1989.

[GS95] Sally Goldman, Robert Sloan. Can PAC Learning Algorithms Tolerate Random Attribute Noise? In Algorithmica, 14(1) pp. 70–84, 1995.

[Ja94] Jeffrey Jackson. An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. In Proceedings of the 35th Annual Symposion on Foundations of Computer Science, pp. 42–53, 1994.

[Ja97] Jeffrey Jackson. An Efficient Membership-Query Algorithm for Learning DNF with Respect to the Uniform Distribution. In Journal of Computer and System Sciences, 55(3), 1997

[JSS97] Jeffrey Jackson, Eli Shamir, Clara Shwartzman. Learning with Queries Corrupted by Classification Noise. In Proceedings of Fifth Israel Symposium on Theory of Computing and Systems, pp. 45–53, 1997.

[Kea93] Michael Kearns. Efficient Noise-Tolerant Learning from Statistical Queries. In Proceedings of the Forth Annual Workshop on COLT, pp. 392–401, 1993.

[KM91] Eyal Kushilevitz, Yishay Mansour. Learning Decision Trees Using the Fourier Spectrum. In Proceedings of the 23-rd Annual Symposium on Theory of Computing, pages 455–464.

[KS99] Adam Klivans, Rocco Servedio. Boosting and Hard-Core Sets. In Proceedings of 40-th Annual Symposium on Foundations of Computer Science, pp. 624–633, 1999.

[KSS92] Michael Kearns, Robert Shapire, Linda Sellie. Toward Efficient Agnostic Learning. In Proceedings of the Fifth Annual Workshop on COLT, pp. 341–352, 1992.

[Lai88] Phillip D. Laird. Learning From Good and Bad Data. Kluwer Academic Publishers, Boston, 1988.

[LMN89] Nathan Linial, Yishay Mansour, Noam Nisan. Constant Depth Circuits, Fourier Transform, and Learnability. In Proceedings of the 31-st Symposium on the Foundations of Computer Science, pp. 574–579, 1989.

[Man94] Yishay Mansour. Learning Boolean Functions via the Fourier Transform. In Theoretical Advances in Neural Computation and Learning, (V.P. Roychodhury and K-Y. Siu and A. Orlitsky, ed.), 391–424, 1994.

[ShSh95] Eli Shamir, Clara Shwartzman. Learning by Extended Statistical Queries and Its Relation to PAC Learning. In Proceedings of Second European Conference, EuroCOLT ’95, pp. 357–366, 1995.

[Sch90] Robert Shapire. The Strength of Weak Learnability. In Machine Learning, 5, pp. 197–227, 1990.

[Sl88] Robert Sloan. Types of Noise in Data for Concept Learning. In Proceedings of the 1988 Workshop on Computational Learning Theory, pp. 91–96, MIT, ACM Press, 1988.

[SV88] George Shakelford, Dennis Volper. Learning k−DNF with Noise in the Attributes. In Proceedings of the 1988 Workshop on COLT, pp. 97–103, 1988.

[V84] Leslie Valiant. A Theory of the Learnable. In Commmunications of the ACM, 27(11) pp. 1134–1142, 1984.