In PAC learning, error tolerance refers to the ability of an algorithm to learn when the examples received have been corrupted in some way. In fact, this is a very common and important issue since in many applications it is not possible to access noise-free data. Noise can interfere with the learning process at different levels: the algorithm may receive data that have been occasionally mislabeled, or the inputs may have some false information, or the classification of the examples may have been maliciously adulterated.
Notation and the Valiant learning model
In the following, let
X
be our
n
-dimensional input space. Let
H
be a class of functions that we wish to use in order to learn a
{
0
,
1
}
-valued target function
f
defined over
X
. Let
D
be the distribution of the inputs over
X
. The goal of a learning algorithm
A
is to choose the best function
h
∈
H
such that it minimizes
e
r
r
o
r
(
h
)
=
P
x
∼
D
(
h
(
x
)
≠
f
(
x
)
)
. Let us suppose we have a function
s
i
z
e
(
f
)
that can measure the complexity of
f
. Let
O
r
a
c
l
e
(
x
)
be an oracle that, whenever called, returns an example
x
and its correct label
f
(
x
)
.
When no noise corrupts the data, we can define learning in the Valiant setting:
Definition: We say that
f
is efficiently learnable using
H
in the Valiant setting if there exists a learning algorithm
A
that has access to
O
r
a
c
l
e
(
x
)
and a polynomial
p
(
⋅
,
⋅
,
⋅
,
⋅
)
such that for any
0
<
ε
≤
1
and
0
<
δ
≤
1
it outputs, in a number of calls to the oracle bounded by
p
(
1
ε
,
1
δ
,
n
,
s
i
z
e
(
f
)
)
, a function
h
∈
H
that satisfies with probability at least
1
−
δ
the condition
e
r
r
o
r
(
h
)
≤
ε
.
In the following we will define learnability of
f
when data have suffered some modification.
In the Classification Noise Model a noise rate
0
≤
η
<
1
2
is introduced. Then, instead of
O
r
a
c
l
e
(
x
)
that returns always the correct label of example
x
, algorithm
A
can only call a faulty oracle
O
r
a
c
l
e
(
x
,
η
)
that will flip the label of
x
with probability
η
. As in the Valiant case, the goal of a learning algorithm
A
is to choose the best function
h
∈
H
such that it minimizes
e
r
r
o
r
(
h
)
=
P
x
∼
D
(
h
(
x
)
≠
f
(
x
)
)
. In applications it is difficult to have access to the real value of
η
, but we assume we have access to its upperbound
η
B
. Note that if we allow the noise rate to be
1
/
2
, then learning becomes impossible in any amount of computation time, because every label conveys no information about the target function.
Definition: We say that
f
is efficiently learnable using
H
in the classification noise model if there exists a learning algorithm
A
that has access to
O
r
a
c
l
e
(
x
,
η
)
and a polynomial
p
(
⋅
,
⋅
,
⋅
,
⋅
)
such that for any
0
≤
η
≤
1
2
,
0
≤
ε
≤
1
and
0
≤
δ
≤
1
it outputs, in a number of calls to the oracle bounded by
p
(
1
1
−
2
η
B
,
1
ε
,
1
δ
,
n
,
s
i
z
e
(
f
)
)
, a function
h
∈
H
that satisfies with probability at least
1
−
δ
the condition
e
r
r
o
r
(
h
)
≤
ε
.
Statistical Query Learning is a kind of active learning problem in which the learning algorithm
A
can decide if to request information about the likelihood
P
f
(
x
)
that a function
f
correctly labels example
x
, and receives an answer accurate within a tolerance
α
. Formally, whenever the learning algorithm
A
calls the oracle
O
r
a
c
l
e
(
x
,
α
)
, it receives as feedback probability
Q
f
(
x
)
, such that
Q
f
(
x
)
−
α
≤
P
f
(
x
)
≤
Q
f
(
x
)
+
α
.
Definition: We say that
f
is efficiently learnable using
H
in the Statistical Query Learning Model if there exists a learning algorithm
A
that has access to
O
r
a
c
l
e
(
x
,
α
)
and polynomials
p
(
⋅
,
⋅
,
⋅
)
,
q
(
⋅
,
⋅
,
⋅
)
, and
r
(
⋅
,
⋅
,
⋅
)
such that for any
0
<
ε
≤
1
the following hold:
-
O
r
a
c
l
e
(
x
,
α
)
can evaluate
P
f
(
x
)
in time
q
(
1
ε
,
n
,
s
i
z
e
(
f
)
)
;
-
1
α
is bounded by
r
(
1
ε
,
n
,
s
i
z
e
(
f
)
)
-
A
outputs a model
h
such that
e
r
r
(
h
)
<
ε
, in a number of calls to the oracle bounded by
p
(
1
ε
,
n
,
s
i
z
e
(
f
)
)
.
Note that the confidence parameter
δ
does not appear in the definition of learning. This is because the main purpose of
δ
is to allow the learning algorithm a small probability of failure due to an unrepresentative sample. Since now
O
r
a
c
l
e
(
x
,
α
)
always guarantees to meet the approximation criterion
Q
f
(
x
)
−
α
≤
P
f
(
x
)
≤
Q
f
(
x
)
+
α
, the failure probability is no longer needed.
The statistical query model is strictly weaker than the PAC model: any efficiently SQ-learnable class is efficiently PAC learnable in the presence of classification noise, but there exist efficient PAC-learnable problems such as parity that are not efficiently SQ-learnable.
In the Malicious Classification Model an adversary generates errors to foil the learning algorithm. This setting describes situations of error burst, which may occur when for a limited time transmission equipment malfunctions repeteadly. Formally, algorithm
A
calls an oracle
O
r
a
c
l
e
(
x
,
β
)
that returns a correctly labeled example
x
drawn, as usual, from distribution
D
over the input space with probability
1
−
β
, but it returns with probability
β
an example drawn from a distribution that is not related to
D
. Moreover, this maliciously chosen example may strategically selected by an adversary who has knowledge of
f
,
β
,
D
, or the current progress of the learning algorithm.
Definition: Given a bound
β
B
<
1
2
for
0
≤
β
<
1
2
, we say that
f
is efficiently learnable using
H
in the Malicious Classification Model if there exist a learning algorithm
A
that has access to
O
r
a
c
l
e
(
x
,
β
)
and a polynomial
p
(
⋅
,
⋅
,
⋅
,
⋅
,
⋅
)
such that for any
0
<
ε
≤
1
,
0
<
δ
≤
1
it outputs, in a number of calls to the oracle bounded by
p
(
1
1
/
2
−
β
B
,
1
ε
,
1
δ
,
n
,
s
i
z
e
(
f
)
)
, a function
h
∈
H
that satisfies with probability at least
1
−
δ
the condition
e
r
r
o
r
(
h
)
≤
ε
.
In the Nonuniform Random Attribute Noise model the algorithm is learning a Boolean function, a malicious oracle
O
r
a
c
l
e
(
x
,
ν
)
may flip each
i
-th bit of example
x
=
(
x
1
,
x
2
,
…
,
x
n
)
independently with probability
ν
i
≤
ν
.
This type of error can irreparably foil the algorithm, in fact the following theorem holds:
In the Nonuniform Random Attribute Noise setting, an algorithm
A
can output a function
h
∈
H
such that
e
r
r
o
r
(
h
)
<
ε
only if
ν
<
2
ε
.
