PAC learning with nasty noise.
We introduce a new model for learning in the presence of noise, which we call the Nasty Noise model. This model generalizes previously considered models of learning with noise. The learning process in this model, which is a variant of the PAC model, proceeds as follows: Suppose that the learning algorithm during its execution asks for m examples. The examples that the algorithm gets are generated by a nasty adversary that works according to the following steps. First, the adversary chooses m examples (independently) according to a fixed (but unknown to the learning algorithm) distribution D as in the PAC-model. Then the powerful adversary, upon seeing the specific m examples that were chosen (and using his knowledge of the target function, the distribution D and the learning algorithm), is allowed to remove a fraction of the examples at its choice, and replace these examples by the same number of arbitrary examples of its choice; the m modified examples are then given to the learning algorithm. The only restriction on the adversary is that the number of examples that the adversary is allowed to modify should be distributed according to a binomial distribution with parameters  (the noise rate) and m.On the negative side, we prove that no algorithm can achieve accuracy of  > 2 in learning any non-trivial class of functions. We also give some lower bounds on the sample complexity required to achieve accuracy . On the positive side, we show that a polynomial (in the usual parameters, and in 1/(-2)) number of examples suffice for learning any class of finite VC-dimension with accuracy  > 2. This algorithm may not be efficient; however, we also show that a fairly wide family of concept classes can be efficiently learned in the presence of nasty noise.
Introduction
Valiant's PAC model of learning [22] is one of the most important models for learning from examples.
Although being an extremely elegant model, the PAC model has some drawbacks. In particular, it
assumes that the learning algorithm has access to a perfect source of random examples. Namely,
upon request, the learning algorithm can ask for random examples and in return gets pairs (x; c t (x))
where all the x's are points in the input space distributed identically and independently according
to some fixed probability distribution D, and c t (x) is the correct classification of x according to the
target function c t that the algorithm tries to learn.
Since Valiant's seminal work, there were several attempts to relax these assumptions, by introducing
models of noise. The first such noise model, called the Random Classification Noise model,
was introduced in [2] and was extensively studied, e.g., in [1, 6, 9, 12, 13, 16]. In this model the
adversary, before providing each example (x; c t (x)) to the learning algorithm tosses a biased coin;
whenever the coin shows "H", which happens with probability j, the classification of the example is
flipped and so the algorithm is provided with the, wrongly classified, example
(stronger) model, called the Malicious Noise model, was introduced in [23], revisited in [17], and
was further studied in [8, 10, 11, 20]. In this model the adversary, whenever the j-biased coin shows
"H", can replace the example (x; c t (x)) by some arbitrary pair any point in the
input space and b is a boolean value. (Note that this in particular gives the adversary the power to
"distort" the distribution D.)
In this work, we present a new model which we call the Nasty (Sample) Noise model. In this
model, the adversary gets to see the whole sample of examples requested by the learning algorithm
before giving it to the algorithm and then modify E of the examples, at its choice, where E is a
random variable distributed by the binomial distribution with parameters j and m, where m is the
size of the sample. This distribution makes the number of examples modified be the same as if it were
determined by m independent tosses of an j-biased coin. However, we allow the adversary's choice
to be dependent on the sample drawn. The modification applied by the adversary can be arbitrary
(as in the Malicious Noise model). 1 Intuitively speaking, the new adversary is more powerful than
the previous ones - it can examine the whole sample and then remove from it the most "informative"
examples and replace them by less useful and even misleading examples (whereas in the Malicious
Noise Model for instance, the adversary also may insert to the sample misleading examples but does
not have the freedom to choose which examples to remove). The relationships between the various
models are shown in Table 1.
Random Noise-Location Adversarial Noise-Location
Label Noise Only Random Classification Noise Nasty Classification Noise
Point and Label Noise Malicious Noise Nasty Sample Noise

Table

1: Summary of models for PAC-learning from noisy data
We argue that the newly introduced model, not only generalizes the previous noise models,
including variants such as Decatur's CAM model [11] and CPCN model [12], but also, that in many
real-world situations, the assumptions previous models made about the noise seem unjustified. For
example, when training data is the result of some physical experiment, noise may tend to be stronger
in boundary areas rather than being uniformly distributed over all inputs. While special models were
We also consider a weaker variant of this model, called the Nasty Classification Noise model, where the adversary
may modify only the classification of the chosen points (as in the Random Classification Noise model).
devised to describe this situation in the exact-learning setting (for example, the incomplete boundary
query model of Blum et al., [5]), it may be regarded as a special case of Nasty Noise, where the
adversary chooses to provide unreliable answers on sample points that are near the boundary of the
target concept (or to remove such points from the sample). Another situation to which our model is
related is the setting of Agnostic Learning. In this model, a concept class is not given. Instead, the
learning algorithm needs to minimize the empirical error while using a hypothesis from a predefined
hypotheses class (see, for example, [18] for a definition of the model). Assuming the best hypothesis
classifies the input up to an j fraction, we may alternatively see the problem as that of learning
the hypotheses class under nasty noise of rate j. However, we note that the success criterion in the
agnostic learning literature is different from the one used in our PAC-based setting.
We show two types of results. Sections 3 and 4 show information theoretic results, and Sect. 5
shows algorithmic results. The first result, presented in Section 3, is a lower bound on the quality of
learning possible with a nasty adversary. This result shows that any learning algorithm cannot learn
any non-trivial concept class with accuracy better than 2j when the sample contains nasty noise of
rate j. We further show that learning a concept class of VC dimension d with accuracy
requires
examples. It is complemented by a matching positive result in Section 4
that shows that any class of finite VC-dimension can be learned by using a sample of polynomial
size, with any accuracy ffl ? 2j. The size of the sample required is polynomial in the usual PAC
parameters and in 1=\Delta where is the margin between the requested accuracy ffl and the
above mentioned lower bound.
The main, quite surprising, result (presented in Section 5) is another positive result showing that
efficient learning algorithms are still possible in spite of the powerful adversary. More specifically, we
present a composition theorem (analogous to [3, 8] but for the nasty-noise learning model) that shows
that any concept class that is constructed by composing concept classes that are PAC-learnable from
a hypothesis class of fixed VC-dimension, is efficiently learnable when using a sample subject to
nasty noise. This includes, for instance, the class of all concepts formed by any boolean combination
of half-spaces in a constant dimension Euclidean space. The complexity here is, again, polynomial
in the usual parameters and in 1=\Delta. The algorithm used in the proof of this result is an adaptation
to our model of the PAC algorithm presented in [8].
Our results may be compared to similar results available for the Malicious Noise model. For
this model, Cesa-Bianchi et al. [10] show that the accuracy of learning with malicious noise is lower
bounded by matching algorithm for learning classes similar to those presented here
with malicious noise is presented in [8]. As for the Random Classification Noise model, learning
with arbitrary small accuracy, even when the noise rate is close to a half, is possible. Again, the
techniques presented in [8] may be used to learn the same type of classes we examine in this work
with Random Classification Noise.
Preliminaries
In this section we provide basic definitions related to learning in the PAC model, with and without
noise. A learning task is specified using a concept class, denoted C, of boolean concepts defined over
an instance space, denoted X . A boolean concept c is a function c : X 7! f0; 1g: The concept class
C is a set of boolean concepts: C ' f0; 1g X .
Throughout this paper we sometimes treat a concept as a set of points instead of as a boolean
function. The set that corresponds to a concept c is simply 1g. We use c to denote both
the function and the corresponding set interchangeably. Specifically, when a probability distribution
D is defined over X , we use the notation D(c) to refer to the probability that a point x drawn from
X according to D will have
2.1 The Classical PAC Model
The Probably Approximately Correct (PAC) model was originally presented by Valiant [22]. In this
model, the learning algorithm has access to an oracle PAC that returns on each call a labeled example
according to a fixed distribution D over X , unknown
to the learning algorithm, and c t 2 C is the target function the learning algorithm should "learn".
Definition 1: A class C of boolean functions is PAC-learnable using hypothesis class H in polynomial
time if there exists an algorithm that, for any c t 2 C, any input parameters
and any distribution D on X , when given access to the PAC oracle, runs in time polynomial in log jX j,
1=ffi, 1=ffl and with probability at least outputs a function h 2 H for
Pr
2.2 Models for Learning in the Presence of Noise
Next, we define the model of PAC-learning in the presence of Nasty Sample Noise (NSN for short).
In this model, a learning algorithm for the concept class C is given access to an (adversarial) oracle
NSN C;j (m). The learning algorithm is allowed to call this oracle once during a single run. The
learning algorithm passes a single natural number m to the oracle, specifying the size of the sample
it needs, and gets in return a labeled sample S 2 (X \Theta f0; 1g) m . (It is assumed, for simplicity, that
the algorithm knows in advance the number of examples it needs; the extension of the model for
scenarios where such a bound is not available in advance is given in Section 6.)
The sample required by the learning algorithm is constructed as follows: As in the PAC model,
a distribution D over the instance space X is defined, and a target concept c t 2 C is chosen. The
adversary then draws a sample S g of m points from X according to the distribution D. Having
full knowledge of the learning algorithm, the target function c t , the distribution D, and the sample
drawn, the adversary chooses points from the sample, where E(S g ) is a random variable.
The E points chosen by the adversary are removed from the sample and replaced by any other
point-and-label pairs by the adversary. The not chosen by the adversary remain
unchanged and are labeled by their correct labels according to c t . The modified sample of m points,
denoted S, is then given to the learning algorithm. The only limitation that the adversary has on
the number of examples that it may modify is that it should be distributed according to the binomial
distribution with parameters m and j, namely:
where the probability is taken by first choosing S g 2 D m and then choosing E according to the
corresponding random variable E(S g ).
Definition 2: An algorithm A is said to learn a class C with nasty sample noise of rate j - 0 with
accuracy parameter ffl ? 0 and confidence parameter access to any oracle NSN C;j (m),
for any distribution D and any target c t 2 C it outputs a hypothesis h : X 7! f0; 1g such that, with
probability at least
Pr
We are also interested in a restriction of this model, which we call the Nasty Classification Noise
learning model (NCN for short). The only difference between the NCN and NSN models is that the
NCN adversary is only allowed to modify the labels of the E chosen sample-points, but it cannot
modify the E points themselves. Previous models of learning in the presence of noise can also
be readily shown to be restrictions of the Nasty Sample Noise model: The Malicious Noise model
corresponds to the Nasty Noise model with the adversary restricted to introducing noise into points
that are chosen uniformly at random, with probability j, from the original sample. The Random
Classification Noise model corresponds to the Nasty Classification Noise model with the adversary
restricted so that noise is introduced into points chosen uniformly at random, with probability j,
from the original sample, and each point that is chosen gets its label flipped.
2.3 VC Theory Basics
The VC-dimension [24], is widely used in learning theory to measure the complexity of concept
classes. The VC-dimension of a class C, denoted VCdim(C), is the maximal integer d such that there
exists a subset Y ' X of size d for which all 2 d possible behaviors are present in the class C, and
if such a subset exists for any natural d. It is well known (e.g., [4]) that, for any two
classes C and H (over X ), the class of negations fcjX n c 2 Cg has the same VC-dimension as the class
C, and the class of unions fc [ hjc 2 C; h 2 Hg has VC-dimension at most VCdim(C)+VCdim(H)+1.
Following [3] we define the dual of a concept class:
Definition 3: The dual H ? ' f0; 1g H of a class H ' f0; 1g X is defined to be the set
defined by x ?
If we view a concept class H as a boolean matrix where each row represents a concept and each
column a point from the instance space, X , then the matrix corresponding to H ? is the transpose
of the matrix corresponding to H. The following claim, from [3], gives a tight bound on the VC
dimension of the dual class:
1: For every class H,
log
In the following discussion we limit ourselves to instance spaces X of finite cardinality. The main
use we make of the VC-dimension is in constructing ff-nets. The following definition and theorem
are from [7]:
Definition 4: A set of points Y ' X is an ff-net for the concept class H ' f0; 1g X under the
distribution D over X , if for every h 2 H such that D(h) - ff, Y " h 6= ;.
Theorem 1: For any class H ' f0; 1g X of VC-dimension d, any distribution D over X , and any
ae 4
ff
log 2
ff
log 13
ff
oe
examples are drawn i.i.d. from X according to the distribution D, they constitute an ff-net for H
with probability at least 1 \Gamma ffi.
In [21], Talagrand proved a similar result:
Definition 5: A set of points Y ' X is an ff-sample for the concept class H ' f0; 1g X under the
distribution D over X , if it holds that for every h 2 H:
Theorem 2: There is a constant c 1 , such that for any class H ' f0; 1g X of VC-dimension d, and
distribution D over X , and any ff ? 0,
examples are drawn i.i.d. from X according to the distribution D, they constitute an ff-sample for
H with probability at least
2.4 Consistency Algorithms
Let P and N be subsets of points from X . We say that a function h : X 7! f0; 1g is consistent on
"positive point" x 2 P and "negative point" x 2 N .
A consistency algorithm (see [8]) for a pair of classes (C; H) (both over the same instance space X ,
with C ' H), receives as input two subsets of the instance space, runs in time t(jP [ N j),
and satisfies the following. If there is a function in C that is consistent with (P; N ), the algorithm
outputs "YES" and some h 2 H that is consistent with (P; N ); the algorithm outputs "NO" if no
consistent exist (there is no restriction on the output in the case that there is a consistent
function in H but not in C).
Given a subset of points of the instance space Q ' X , we will be interested in the set of all
possible partitions of Q into positive and negative examples, such that there is a function h 2 H
and a function c 2 C that are both consistent with this partition. This may be formulated as:
CON is a consistency algorithm for (C; H).
The following is based on Sauer's Lemma [19]:
Lemma 1: For any set of points Q,
Furthermore, an efficient algorithm for generating this set of partitions (along with the corresponding
functions h presented, assuming that C is PAC-learnable from H of constant VC dimension.
The algorithm's output is denoted
h is consistent with
Information Theoretic Lower Bound
In this section we show that no learning algorithm (not even inefficient ones) can learn a "non-
trivial" concept class with accuracy ffl better than 2j under the NSN model; in fact, we prove that
this impossibility result holds even for the NCN model. We also give some results on the size of
samples required to learn in the NSN model with accuracy ffl ? 2j.
Definition class C over an instance space X is called non-trivial if there exist two
points
Theorem 3: Let C be a non-trivial concept class, j be a noise rate and ffl ! 2j be an accuracy
parameter. Then, there is no algorithm that learns the concept class C with accuracy ffl under the
NCN model (with rate j).
Proof: We base our proof on the method of induced distributions introduced in [17, Theorem
1]. We show that there are two concepts distribution D such that
and an adversary can force the labeled examples shown to the learning algorithm
to be distributed identically both when c 1 is the target and when c 2 is the target.
Let c 1 and c 2 be the two concepts whose existence is guaranteed by the fact that C is a non-trivial
class, and let x be the two points that satisfy c 1
define the probability distribution D to be D(x 1
g. Clearly, we indeed have PrD [c 1
Now, we define the nasty adversary strategy (with respect to the above probability distribution
D). Let m be the size of the sample asked by the learning algorithm. The adversary starts by drawing
a sample S g of m points according to the above distribution. Then, for each occurrence of x 1 in the
sample, the adversary labels it correctly according to c t , while for each occurrence of x 2 the adversary
tosses a coin and with probability 1=2 it labels the point correctly (i.e., c t
it flips the label (to )). The resulted sample of m examples is given by the adversary
to the learning algorithm. First, we argue that the number of examples modified by the adversary
is indeed distributed according to the binomial distribution with parameters j and m. For this, we
view the above adversary as if it picks independently m points and for each of them decides (as
above) whether to flip its label. Hence, it suffices to show that each example is labeled incorrectly
with probability j independently of other examples. Indeed, for each example independently, its
probability of being labeled incorrectly equals the probability of choosing x 2 according to D times
the probability that the adversary chooses to flip the label on an x 2 example; i.e. 2j \Delta
as needed. (We emphasize that the binomial distribution is obtained because D is known to the
adversary.)
Next observe that, no matter whether the target is c 1 or c 2 , the examples given to the learning
algorithm (after being modified by the above nasty adversary) are distributed according to the
following probability distribution:
Therefore, according to the sample that the learning algorithm sees, it is impossible to differentiate
between the case where the target function is c 1 and the case where the target function is c 2 .
Note that in the above proof we indeed take advantage of the "nastiness" of the adversary. Unlike
the malicious adversary, our adversary can focus all its "power" on just the point x 2 , causing it to
suffer a relatively high error rate, while examples in which the point is x 1 do not suffer any noise. We
also took advantage of the fact that E (the number of modified examples) is allowed to depend on
the sample (in our case, it depends on the number of times x 2 appears in the original sample). This
allows the adversary to further focus its destructive power on samples which were otherwise "good"
for the learning algorithm. Finally, since any NCN adversary is also a NSN adversary, Theorem 3
implies the following:
Corollary 4: Let C be a non-trivial concept class, j ? 0 be the noise rate, and ffl ! 2j be an
accuracy parameter. There is no algorithm that learns the concept class C with accuracy ffl under
the NSN model, with noise rate j.
Once we have settled 2j as the lower bound on the accuracy possible with a nasty adversary with
error rate j, we turn to the question of the number of examples that are necessary to learn a concept
class with some accuracy Again, in this section we are only considering
information-theoretic issues. These results are similar to those presented by Cesa-Bianchi et al. [10]
for the Malicious Noise model. Note, however, that the definition of the margin \Delta used here is
relative to a lower bound different than the one used in [10]. In the proofs of these results, we use
the following claim (see [10]) that provides a lower bound on the probability that a random variable
of binomial distribution deviates from its expectation by more than the standard deviation:
2: [10, Fact 3.2] Let SN;p be a random variable distributed by the binomial distribution with
parameters N and p, and let p. For all N ? 37=(pq):
Pr
ki
19 (1)
Pr
ki
19 (2)
Theorem 5: For any nontrivial concept class C, any noise rate j ? 0, confidence parameter
the sample size needed for PAC learning C with accuracy
and confidence tolerating nasty classification noise of rate j is at least
=\Omega
Proof: Let c 1 and c 2 be the two concepts whose existence is guaranteed by the fact that C is a non-trivial
class, and let x be the two points that satisfy c 1
Let us define a distribution D that gives weight ffl to the point x 2 and weight 1 \Gamma ffl to x 1 , making
by f the target function (either c 1 or c 2 ).
The Nasty Classification Adversary will use the following strategy: for each pair of the form
in the sample, with probability j=ffl reverse the label (i.e., present to the learning algorithm
the pair instead). The rest of the sample (all the pairs of the form
unmodified. Note that for each of the m examples the probability that its classification is changed is
therefore exactly ffl \Delta j
so the number of points that suffer noise is indeed distributed according
to the binomial distribution with parameters j and m. The induced probability distribution on the
sample that the learning algorithm sees is:
For contradiction, let A be a (possibly randomized) algorithm that learns C with accuracy ffl using
a sample generated by the above oracle and whose size is m
by p A (m) the error of the hypothesis h that A outputs when using m examples. Let B be the
Bayes strategy of outputting c 1 if the majority instances of x 2 are labeled c 1
Clearly, this strategy minimizes the probability of choosing the wrong hypothesis. This implies
Define the following two events over runs of B on samples of size m: Let N denote the number
of examples in m showing the point x 2 . BAD 1 is the event that at least dN=2e are
corrupted, and BAD 2 is the event that N - 36j(j
answer incorrectly, as there will be more examples showing x 2 with the wrong label than there will
be examples showing x 2 with the correct label.
Examine now the probability that BAD 2 will occur. Note that N is a random variable distributed
by the binomial distribution with parameters m and ffl (and recall that \Delta). We are interested
in:
Since the probability that N is large is higher when m is larger, and m is upper bounded by (17j(1 \Gamma
But this may be bounded, using Hoeffding's inequality to be at least
We therefore have:
On the other hand, if we assume that BAD 2 holds, namely that N - 36j(j+
additionally assume that N - 37(2j+ \Delta) 2 =(j(j+ \Delta)) then, by Claim 2 (with
and using the following inequality
$s
it follows that Pr[BAD 1 To see that the inequality of Equation (3) indeed holds
when BAD 2 holds, note that (3) is implied by:
s
which is, in turn, implied by the two conditions:2
s
s
It can be verified that these two conditions hold if we take N to be in the range we assume: 2
is an optimal strategy, and hence no
worse than a strategy that ignores some of the sample points, its error can only decrease if more
points are shown for x 2 . Therefore, the same results will hold if we remove the lower bound on N .
We thus have that Pr[BAD 1
A second type of a lower bound on the number of required examples is based on the VC dimension
of the class to be learned, and is similar to the results (and the proof techniques) of [7] for the standard
PAC model:
2 By our conditions on \Delta there must be at least one integer in the range we assume for N .
Theorem 6: For any concept class C with VC-dimension d - 3, and for any 0 ! ffl - 1=8,
1=12, the sample size required to learn C with accuracy ffl and confidence ffi when using
samples generated by a nasty classification adversary with error rate \Delta) is greater than
=\Omega
be a set of d points shattered by C. Define a probability
distribution D as follows:
Assume for contradiction that at most (d \Gamma 2)=32\Delta examples are used by the learning algorithm. We
let the nasty adversary behave as follows: it reverses the label on each example x d\Gamma1 with probability
1=2 (independent of any other sample points), making the labels of x d\Gamma1 appear as if they are just
random noise (also note that the probability of each example to be corrupted by the adversary is
exactly 2j \Delta j). Thus, with probability 1=2 the point x d\Gamma1 is misclassified by the learner's
hypothesis. The rest of the sample is left unmodified. Denote by BAD 1 the event that at least
half of the points x are not seen by the learning algorithm. Given BAD 1 , we denote
UP the set of (d \Gamma 2)=2 unseen points with lowest indices, and define BAD 2 as the event that the
algorithm's hypothesis misclassifies at least (d \Gamma 2)=8 points from UP. Finally, let BAD 3 denote
the event that x d\Gamma1 is misclassified. It is easy to see that BAD 1 - BAD 2 - BAD 3 imply that the
hypothesis has error of at least ffl, as it implies that the hypothesis errs on (d \Gamma 2)=8 points where
each of these points has weight 8\Delta=(d \Gamma 2) and on the point x whose weight is 2j, making the
total error at least \Delta Therefore, if an algorithm A can learn the class with confidence ffi ,
it must hold that Pr[BAD 1 - BAD 2 - BAD 3 As noted before, x d\Gamma1 appears to be labeled by
random noise, and hence Pr[BAD 3
is independent of BAD 1 and BAD 2 , thus
.
As for the other events, since at most (d \Gamma 2)=32\Delta examples are seen, the expected number of
points from x that the learning algorithm sees is at most (d \Gamma 2)=4. From the Markov
inequality it follows that, with probability at least 1
2 , no more than (d \Gamma 2)=2 points are seen. Hence,
2 . Every unseen point will be misclassified by the learning algorithm with probability
at least half (since for each such point, the adversary may set the target to label the point with
the label that has lower probability to be given by the algorithm). Thus Pr[BAD 2 jBAD 1 ] is the
probability that a fair coin flipped (d \Gamma 2)=2 times shows heads at least (d \Gamma 2)=8 times. Using [10,
Fact 3.3] this probability can be shown to be at least 1=3. We thus have:
This completes the proof.
Since learning with Nasty Sample Noise is not easier than learning with Nasty Classification
Noise, the results of Theorems 5 and 6 also hold for learning from a Nasty Sample Noise oracle.
Information Theoretic Upper Bound
In this section we provide a positive result that complements the negative result of Section 3. This
result shows that, given a sufficiently large sample, any hypothesis that performs sufficiently well on
the sample (even when this sample is subject to nasty noise) satisfies the PAC learning condition.
Formally, we analyze the following generic algorithm for learning any class C of VC-dimension d,
whose inputs are a certainty parameter ffi ? 0, the nasty error rate parameter
2 and the required
Algorithm NastyConsistent:
1. Request a sample
2. Output any h 2 C such that
(if no such h exists, choose any h 2 C arbitrarily).
Theorem 7: Let C be any class of VC-dimension d. Then, (for some constant c) algorithm Nasty-
Consistent is a PAC learning algorithm under nasty sample noise of rate j.
In our proof of this theorem (as well as in the analysis of the algorithm in the next section), we
use, for convenience, a slightly weaker definition of PAC learnability than the one used in Definition
1. We require the algorithm to output, with probability at least
Pr
(rather than a strict inequality). However, if we use the same algorithm but give it a slightly smaller
accuracy parameter (e.g., ffl ffl), we will get an algorithm that learns using the original
criterion of Definition 1.
Proof: First, we argue that with "high probability" the number of sample points that are modified
by the adversary is at most m(j \Delta=4). As the random variable E is distributed according to the
binomial distribution with expectation jm, we may use Hoeffding's inequality [14] to get:
Pr
(by the choice of c), this event happens with probability of at most ffi=2.
Now, we note that the target function c t , errs on at most E points of the sample shown to
the learning algorithm (as it is completely accurate on the non-modified sample S g ). Thus, with
probability at least NastyConsistent will be able to choose a function h 2 C that
errs on no more that (j + \Delta=4)m points of the sample shown to it. However, in the worst case, these
errors of the function h occur in points that were not modified by the adversary. In addition, h may
be erroneous for all the points that the adversary did modify. Therefore, all we are guaranteed in
this case, is that the hypothesis h errs on no more that 2E points of the original sample S g . By
Theorem 2, there exists a constant c such that, with probability by taking S g to be of size
at least c
the resulting sample S g is a \Delta
-sample for the class of symmetric differences
between functions from C. By the union bound we therefore have that, with probability at least
\Delta=4)m, meaning that jS \Delta=2)m, and that S g is a \Delta=2-sample
for the class of symmetric differences, and so:
Pr
as required.
5 Composition Theorem for Learning with Nasty Noise
Following [3] and [8], we define the notion of "composition class": Let C be a class of boolean
functions . Define the class C ? to be the set of all boolean functions F (x) that can
be represented as f(g 1 boolean function, and g i 2 C for
We define the size of f(g to be k. Given a vector of hypotheses
following [8], the set W(h to be the set of sub-domains W a ag for
all possible vectors a 2 f0; 1g t .
We now show a variation of the algorithm presented in [8] that can learn the class C ? with a
nasty sample adversary, assuming that the class C is PAC-learnable from a class H of constant VC
dimension d. Our algorithm builds on the fact that a consistency algorithm CON for (C; H) can be
constructed, given an algorithm that PAC learns C from H [8]. This algorithm can learn the concept
class C ? with any confidence parameter ffi and with accuracy ffl that is arbitrarily close to the lower
bound of 2j, proved in the previous section. Its sample complexity and computational complexity
are both polynomial in k, 1=ffi and 1=\Delta, where
Our algorithm is based on the following idea: Request a large sample from the oracle. Randomly
pick a smaller sub-sample from the sample retrieved. By randomly picking this sub-sample, the
algorithm neutralize some of the power the adversary has, since the adversary cannot know which
examples are the ones that will be most "informative" for us. Then use the consistency algorithm
for (C; H) to find one representative from H for any possible behavior on the smaller sub-sample.
These hypotheses from H now define a division of the instance space into "cells", where each cell
is characterized by a specific behavior of all the hypotheses picked. The final hypotheses is simply
based on taking a majority vote among the complete sample inside each such cell.
To demonstrate the algorithm, let us consider (informally) the specific, relatively simple, case
where the class to be learned is the class of k intervals on the straight line (see Figure 1). The
algorithm, given a sample as input, proceeds as follows:
1. The algorithm uses a relatively small, random sub-sample to divide the line into sub-intervals.
Each two adjacent points in the sub-sample define such a sub-interval.
2. For each such sub-interval the algorithm calculates a majority vote on the complete sample.
The result is our hypothesis.
The number of points (which in this specific case is the number of sub-intervals) that the algorithm
chooses in the first step depends on k. Intuitively, we want the total weight of the sub-intervals
containing the target's end-points to be relatively small (this is what is called the ``bad part'' in the
formal analysis that follows). Naturally, there will be 2k such "bad" sub-intervals, so the larger k
Target Concept:
Sub-sample and intervals:
"Bad" "Bad" "Bad" "Bad"
Algorithm's hypothesis:

Figure

1: Example of NastyLearn for intervals.
is, the larger the sub-sample needed. Except for these "bad" sub-intervals, all other subintervals on
which the algorithm errs have to have at least half of their points modified by the adversary. Thus
the total error will be roughly 2j, plus the weight of the "bad" sub-intervals.
Now, we proceed to a formal description of the learning algorithm. Given the constant d, the size
k of the target function, the bound on the error rate j, the parameters ffi and \Delta, and two additional
parameters M;N (to be specified below), the algorithm proceeds as follows:
Algorithm NastyLearn:
1. Request a sample S of size N .
2. Choose uniformly at random a sub-sample R ' S of size M .
3. Use the consistency algorithm for (C; H) to compute
4. Output the hypotheses H(h computed as follows: For any W a 2 W(h
is not empty, set H to be the majority of labels in S " W a . If W a is empty, set H to be 0 on
any x 2 W a .
Theorem 8: Let
log 8
log 78k
are constants. Then, Algorithm NastyLearn learns the class C ? with accuracy
confidence ffi in time polynomial in k, 1
As in Theorem 7, this Theorem refers to the modified PAC criterion that require the algorithm
to output, with probability at least 1 \Gamma ffi, a function h for
Pr
The same technique we mentioned for Algorithm NastyConsistent may be used to modify this algorithm
to be a PAC learning algorithm in the sense of Definition 1.
Before commencing with the actual proof, we present a technical lemma:
Lemma 2: Assuming N is set as in the statement of Theorem 8, with probability at least
4 the
number of points in which errors are introduced, E, is at most (j + \Delta=12)N .
Proof of Lemma 2: Note that, by the definition of the model, E is distributed according to a
binomial distribution with parameters j and N . Thus, E behaves as the number of successes in
independent Bernoulli experiments, and the Hoeffding inequality [14] may be used to bound its
value:
Pr
Therefore, if we take N ? 72
ln(4=ffi) we have, with probability at least
4 , that E is at most
(j \Delta=12)N . Note that the value we have chosen for N in the statement of Theorem 8 is clearly
large enough.
We are now ready to present the proof of Theorem 8:
Proof: To analyze the error made by the hypothesis that the algorithm generates, let us denote
the adversary's strategy as follows:
1. Generate a sample of the requested size N according to the distribution D, and label it by the
target concept F . Denote this sample by S g .
2. Choose a subset S out ' S g of size is a random variable (as defined in
Section 2.2).
3. Choose (maliciously) some other set of points S in ' X \Theta f0; 1g of size E.
4. Hand to the learning algorithm the sample in .
Assume the target function F is of the form
the hypothesis that the algorithm have chosen in step 3 that exhibits the
same behavior g i has over the points of R (from the definition of -
SCON we are guaranteed that such
a hypothesis exists). By definition, there are no points from R in h j i
As the VC-dimension of both the class C of all g i 's and the class H of all h i 's is d, the class of
all their possible symmetric differences also has VC-dimension O(d) (see Section 2.3). By applying
Theorem 1, when viewing R as a sample taken from S according to the uniform distribution, and
by choosing M to be as in the statement of the theorem, R will be an ff-net (with respect to the
uniform distribution over S) for the class of symmetric differences, with
at least 1 \Gamma ffi=4. Note that there may still be points in S which are in h j i 4g i . Hence, we let
using (4) we get:
with probability at least 1 \Gamma ffi=4, simultaneously for all i.
For every sub-domain B 2 W(h
N in
B= jS in " Bj
In words, NB and N in
simply stand for the size of the restriction of the original (noise-free) sample
S g and the noisy examples S in introduced by the adversary to the sub-domain B. As for the rest
of the definitions, they are based on the distinction between the "good" part of B, where the g i s
and the h j i s behave the same, and the "bad" part, which is present due to the fact that the g i s and
the h j i s exhibit the same behavior only on the smaller sub-sample R, rather than on the complete
sample S. We use N ff
B to denote the number of sample points in the bad part of B, and N out,g
B to denote the number of sample points that were removed by the adversary from the good
and bad parts of B, respectively.
Since our learning algorithm decides on the classification in each sub-domain by a majority vote,
the hypothesis will err on the domain
of B) if the number of
examples left untouched in B is less than the number of examples in B that were modified by the
adversary, plus those that were misclassified by the h j i s (with respect to the g i s). This may be
formulated as the following condition: N in
Therefore, the total error the algorithm may experience is at most:
B: NB-N in
We now calculate a bound for each of the two terms above separately. To bound the second term,
note that by Theorem 2 our choice of N guarantees S g to be a \Delta
-sample for our domain
with probability at least 1 \Gamma ffi=4. Note that from the definition of W(h and from the Sauer
Lemma [19] we have that jW(h
Our choice of N indeed guarantees, with probability at least
B: NB-N in
B: NB-N in
N in
?From the above choice of N , it follows that S g is also a \Delta
-sample for the class of
symmetric differences of the form h j i
4g i . Thus, with probability at least 1 \Gamma ffi=4, we have:
The total error made by the hypothesis (assuming that none of the four bad events happen) is
therefore bounded by:
Pr
N in
as required. This bound holds with certainty at least 1 \Gamma ffi.
6 Conclusion
We have presented the model of PAC learning with nasty noise, generalizing on previous models. We
have proved a negative information-theoretic result, showing that there is no learning algorithm that
can learn any non-trivial class with accuracy better than 2j, paired with a positive result showing this
bound to be tight. We complemented these results with lower bounds on the sample size required for
learning with accuracy 2j \Delta. We have also shown that for a wide variety of "interesting" concept
classes, an efficient learning algorithm in this model exists. Our negative result can be generalized
for the case where the learning algorithm uses randomized hypotheses, or coin rules (as defined in
[10]); in such a case we get an information theoretic lower bound of j for the achievable accuracy,
compared to a lower bound of j=2(1 proved in [10] for learning with Malicious Noise of rate j.
While the partition into two separate variants: the NSN and the NCN models seem intuitive and
well-motivated, it remains an open problem to come up with any results that actually separate the
two models. Both the negative and positive results we presented in this work apply equally to both
the NSN and the NCN models.
Finally, note that the definition of the nasty noise model requires the learning algorithm to know
in advance the sample size m (or an upper bound on it). The model however can be extended so as
to deal with scenarios where no such bound is known to the learning algorithm. There are several
scenarios of this kind. For example, the sample complexity may depend on certain parameters (such
as the "size" of the target function) which are not known to the algorithm 3 . The adversary, who knows
the learning algorithm and knows the target function (and in general can know all the parameters
hidden from the learning algorithm) can thus "plan ahead" and draw in advance a sample S g of size
which is sufficiently large to satisfy, with high probability, all the requests the learning algorithm will
make. It then modifies S g as defined above and reorders the resulted sample S randomly 4 . Now, the
learning algorithm simply asks for one example at a time (as in the PAC model) and the adversary
supplies the next example in its (randomly-ordered) set S. If the sample is exhausted (which may
happen in those cases where we have only an expected sample-complexity guarantee), we say that
the learning algorithm has failed; however, when using a large enough sample (with respect to 1=ffi),
this will happen with sufficiently small probability.



--R

"General Bounds on Statistical Query Learning and PAC Learning with Noise via Hypothesis Boosting"
"Learning from Noisy Examples"
"A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes"
"Combinatorial Variability of Vapnik-Chervonenkis Classes with Applications to Sample Compression Schemes"
"Learning with Unreliable Boundary Queries"
"Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis"
"Learnability and the Vapnik-Chervonenkis dimension"
"A New Composition Theorem for Learning Algorithms"
"Noise-Tolerant Distribution-Free Learning of General Geometric Concepts"
"Sample-efficient strategies for learning in the presence of noise"
"Learning in Hybrid Noise Environments Using Statistical Queries"
"PAC Learning with Constant-Partition Classification Noise and Applications to Decision Tree Induction"
"On Learning from Noisy and Incomplete Examples"
"Probability Inequalities for Sums of Bounded Random Variables"

"Efficient Noise-Tolerant Learning from Statistical Queries"
"Learning in the Presence of Malicious
"Toward Efficient Agnostic Learning"
"On the Density of Families of sets"
"The Design and Analysis of Efficient Learning Algorithms"
"Sharper Bounds for Gaussian and Empirical Processes"
"A Theory of the Learnable"
"Learning Disjunctions of Conjunctions"
"On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities"
--TR
A theory of the learnable
Learnability and the Vapnik-Chervonenkis dimension
The design and analysis of efficient learning algorithms
Learning in the presence of malicious errors
Efficient noise-tolerant learning from statistical queries
Weakly learning DNF and characterizing statistical query learning using Fourier analysis
Toward Efficient Agnostic Learning
Learning with unreliable boundary queries
On learning from noisy and incomplete examples
Noise-tolerant distribution-free learning of general geometric concepts
A composition theorem for learning algorithms with applications to geometric concept classes
A new composition theorem for learning algorithms
Combinatorial variability of Vapnik-Chervonenkis classes with applications to sample compression schemes
Sample-efficient strategies for learning in the presence of noise
Learning From Noisy Examples

--CTR
Marco Barreno , Blaine Nelson , Russell Sears , Anthony D. Joseph , J. D. Tygar, Can machine learning be secure?, Proceedings of the 2006 ACM Symposium on Information, computer and communications security, March 21-24, 2006, Taipei, Taiwan
nasty noise;PAC learning;learning with noise