Speculate-Correct Error Bounds for k-Nearest Neighbor
Classifiers

arXiv:1410.2500v6 [cs.LG] 15 Sep 2017

Eric Baxa , Lingjie Wengb , Xu Tianc
a

Verizon (baxhome@yahoo.com)
LinkedIn (lingjieweng@gmail.com)
c
Sorin Capital Management (tianxu03@gmail.com)
b

Abstract
We introduce the speculate-correct method to derive error bounds for local
classifiers. Using it, we show that k-nearest neighbor classifiers, in spite of
their famously
fractured decision boundaries, have exponential error bounds
p
with O
(k + ln n)/n error bound range for n in-sample examples.
Keywords: nearest neighbors, statistical learning, supervised learning,
error bounds, generalization
2000 MSC: 62G99,
2000 MSC: 68Q32,
2000 MSC: 62M99
1. Introduction
Local classifiers use only a small subset of their examples to classify each
input. The best-known local classifier is the nearest neighbor classifier. To
classify an example, a k-nearest neighbor (k-nn) classifier uses a majority
vote over the k in-sample examples closest to the example. We assume k is
odd, and we assume binary classification. For general information on k-nn
classifiers, see the books by Devroe et al. [12], Duda et al. [13], and Hastie
et al. [14]. Deriving error bounds for k-nn classifiers is a challenge, because
they can have extremely fractured decision boundaries, making approaches
based on hypothesis class size ineffective.
The error bounds in this paper are probably approximately correct (PAC)
bounds, consisting of a range of error rates and a bound on the probability
that the actual out-of-sample error rate is outside the range. An effective
Preprint submitted to Pattern Recognition

September 19, 2017

PAC bound has a small range and a small bound failure probability. PAC
error bounds include bounds based on Vapnik-Chervonenkis (VC) dimension
[1], bounds for concept learning by Valiant [2], compression-based bounds by
Littlestone and Warmuth [3], Floyd and Warmth [4], Blum and Langford [5],
and Bax [6], and bounds based on worst likely assignments [7]. Langford [8]
gives an overview and comparison of some types of PAC bounds.
A previous method by Devroe and Wagner [16] (also presented in Devroe
et al. [12] p. 415, Theorem
24.5) produces a k-nn exponential error bound

1/3
with range O (k/n)
. Another method [20] has expected error bound

2/5
range O (k/n)
. (Exponential error bounds have range proportional to
ln(1/δ) as bound failure probability δ → 0.)
The great conundrum of classifier validation is that we want to use data
that are independent of the classifier to estimate its error rate, but we also
want to use all available data for the classifier. At each step, speculatecorrect assumes that this problem does not exist, at least for some of the
in-sample data. In subsequent steps, it corrects for its sometimes-false earlier
assumptions. As it does this, the number of corrections grows, but the size
of each correction shrinks.
To illustrate, suppose we use two withheld data sets: V1 and V2 . Let g
be the full classifier; our goal is to bound its error rate: P r {g}. (Use P r {}
to indicate probability over out-of-sample examples, and use a bar on top to
indicate classifier error.) Let g−S be the classifier formed by withholding the
data sets indexed by S. For example, g−{1} is all in-sample examples except
those in V1 . Then the speculate-correct process is:
1. Speculate that withholding
V1 does not affect classification: ∀x : g =

g−{1} . Compute P rV1 g−{1} as our initial estimate of P r {g}. (Use
P rVi {} to indicate empirical rate over examples in Vi – also called an
empirical mean.) When our speculation is false (g 6= g−{1} ), there is
bias, because then we have estimated P r g−{1} instead of P r {g}:



P r g−{1} = P r g = g−{1} ∧ g−{1} + P r g 6= g−{1} ∧ g−{1} , (1)
and



P r {g} = P r g = g−{1} ∧ g + P r g 6= g−{1} ∧ g .

(2)

The first terms are the same, since (g = g−{1} ) =⇒ (g = g−{1} ), but
not the second ones. To correct the bias, we need to:

(a) Subtract an estimate of P r g 6= g−{1} ∧ g−{1} .
2


(b) Add an estimate of P r g 6= g−{1} ∧ g .
2. Now speculate that ∀x : g = g−{2} and g−{1} = g−{1,2} . Then use V2 to
correct according to (a) and (b) from Step 1:

(a) Subtract PrV2 g−{2} 6= g−{1,2} ∧ g−{1,2} .
(b) Add P rV2 g−{2} 6= g−{1,2} ∧ g−{2} .
When the speculation for this step holds, withholding V2 does not affect
the corrections:


P rV2 g−{2} 6= g−{1,2} ∧ g−{1,2} = P rV2 g 6= g−{1} ∧ g−{1} ,
(3)
and



P rV2 g−{2} 6= g−{1,2} ∧ g−{2} = P rV2 g 6= g−{1} ∧ g .

(4)

The remaining bias terms require Step 1 and 2 speculations to fail
simultaneously. For (a), the bias terms are:

− P r g 6= g−{1} ∧ g−{1} 6= g−{1,2} ∧ g−{1,2}
(5)

+ P r g 6= g−{1} ∧ g−{1} 6= g−{1,2} ∧ g−{1}
(6)

For (b), they are:


− P r g 6= g−{1} ∧ g 6= g−{2} ∧ g−{2}

+ P r g 6= g−{1} ∧ g 6= g−{2} ∧ g

(7)
(8)

Continuing this for r steps, with r withheld data sets, produces a sum
of 2r − 1 estimates. All remaining bias depends on simultaneous failure of
r speculations, but there are 2r bias terms. For k-nn, speculation can only
fail for Step i if Vi has a nearer neighbor to x than its k th nearest neighbor
among the in-sample examples not in any validation set. So the bias is at
most 2r times the probability that x has a nearer neighbor in every validation
set than the k th nearest neighbor among the other in-sample examples.
To produce effective error bounds, we must use withheld data sets small
enough to make the probability of r simultaneous speculation failures small,
and yet large enough that the sum of 2r − 1 estimates is likely to have a small
deviation from the sum that it estimates. (Using Hoeffding bounds [18], the
range for the difference between each estimate P rVi {} and its corresponding
3

out-of-sample probability P r {} is O



√1
|Vi |


.) We show that an appropriate

choice of withheld data set size gives error bound range:


r √
− 2r+1
k+r ,
O n

and, for a choice of r based on n, the range is
p

O
(k + ln n)/n .

(9)

(10)

The next section formally introduces the speculate-correct method to
produce error bounds for local classifiers. Section 3 applies the method to
k-nn classifiers. Section 4 shows how to compute the bounds. Section 5
concludes with potential directions for future work.
2. Speculate-Correct

Let F be the full set of n in-sample examples (x, y), drawn i.i.d. from
a joint input-output distribution D. Inputs x are drawn from an arbitrary
domain, and outputs y are drawn from {0, 1} (binary classification). Assume
there is some ordering of the examples in F , so that we may refer to examples
1 to n in F , treating F as a sequence.
Select r > 0 and m > 0 such that rm ≤ n − k. For each i ∈ 1, . . . , r, let
validation subset Vi be the ith subset of m examples in F . For example, if
r = 2 and m = 1000, then V1 is the first thousand examples in F and V2 is
the second thousand. Let validation set V = V1 ∪ . . . ∪ Vr . For convenience,
define R ≡ {1, . . . , r}. For S ⊆ R, let VS be the union of validation subsets
indexed by S.
Our PAC error bounds have probability of bound failure over draws of F .
Let the subscript F ∼ D n denote a probability or expectation over draws of
F . We use no subscript for probabilities or expectations over out-of-sample
examples (x, y) ∼ D. For example,
p∗ ≡ P r {g}

(11)

denotes the out-of-sample error rate of g, and it is the quantity we wish
to bound. (It is sometimes called the conditional error rate, because it is
the error rate conditioned on a set of in-sample examples F rather than the
expected error rate over draws of F .)
4

Let Ai = {1, . . . , i}. Let a1 , . . . , ar be any series of conditions such that
ai (x) =⇒ ∀S ⊆ Ai−1 : g−(S∪{i}) (x) = g−S (x),

(12)

i.e., ai (x) implies that for any classifier formed by withholding any subset of
{V1 , . . . , Vi−1 }, withholding Vi too does not alter the classification of x.
Let bi = ¬a1 ∧ . . . ∧ ¬ai . Define b0 to be true. The following theorem
generalizes the speculate-correct formula for r = 2 that we developed in the
previous section.
Theorem 1.
∗

∀r ≥ 0 : p =

r
X
X

i=1 S⊆Ai−1

X

(−1)|S| P r bi−1 ∧ g−(S∪{i}) +
(−1)|S| P r {br ∧ g−S } .
S⊆R

(13)

Proof. Use induction. The base case is r = 0:
X
(−1)|S| P r {b0 ∧ g−S } = P r {b0 ∧ g−∅ } = P r {g} = p∗ .

(14)

S⊆∅

Next, to show that the result for r:
p∗ =

r
X
X

i=1 S⊆Ai−1

X

(−1)|S| P r bi−1 ∧ g−(S∪{i}) +
(−1)|S| P r {br ∧ g−S } , (15)
S⊆R

implies the result for r + 1:
∗

p =

r+1 X
X

i=1 S⊆Ai−1

X

(−1)|S| P r bi−1 ∧ g−(S∪{i}) +
(−1)|S| P r {br+1 ∧ g−S } ,
S⊆Ar+1

(16)

subtract the result for r from the result for r + 1. The difference is
X
X

(−1)|S| P r br ∧ g−(S∪{r+1}) +
(−1)|S| P r {br+1 ∧ g−S }
S⊆Ar

(17)

S⊆Ar+1

−

X

(−1)|S| P r {br ∧ g−S } .

S⊆R

We will show that this difference is zero.
5

(18)

Since Ar = R, the first and third sums are over the same indices, so
combine them:
X


(−1)|S| P r br ∧ g−(S∪{r+1}) − P r {br ∧ g−S }
=
(19)
S⊆Ar

+

X

S⊆Ar+1

(−1)|S| P r {br+1 ∧ g−S } .

Expand the first sum’s probabilities around ar+1 values:

P r br ∧ g−(S∪{r+1}) − P r {br ∧ g−S }


= P r br ∧ ar+1 ∧ g−(S∪{r+1}) + P r br ∧ ¬ar+1 ∧ g−(S∪{r+1})
− P r {br ∧ ar+1 ∧ g−S } − P r {br ∧ ¬ar+1 ∧ g−S } .

(20)

(21)
(22)
(23)

The first and third terms cancel, because ar+1 =⇒ g−(S∪{r+1}) = g−S . The
other terms have br+1 , since br ∧ ¬ar+1 = br+1 . So the difference is:
X


(24)
(−1)|S| P r br+1 ∧ g−(S∪{r+1}) − P r {br+1 ∧ g−S }
=
S⊆Ar

+

X

S⊆Ar+1

(−1)|S| P r {br+1 ∧ g−S } .

(25)

The first sum cancels the second: for each S in the first sum, the first term
cancels the term for S ∪ {r + 1} in the second sum, and the second term
cancels the term for S in the second sum.
The formulation of the error rate in Theorem 1 is useful because the
examples in each validation subset Vi are independent of the conditions in
term i in the first sum. So the rates of the conditions over the validation
subsets are unbiased estimates of the probabilities of those conditions over
out-of-sample examples. There are no such validation data for the second
sum. Instead of estimating the second sum, our error bounds bound each of
its terms by P r {br }. We select validation subset sizes to mediate a tradeoff:
large validation subsets give tight bounds on terms in the first sum, but small
validation subsets make P r {br } small.

6

3. Error Bounds for k-NN Classifiers
Before introducing k-nn error bounds, we need a brief aside about tiebreaking. Break ties using the method from Devroe and Wagner [16]: assign
each example i in F a real value Zi drawn uniformly at random from [0, 1]
and do the same for each other draw x from the input space to give it a
value Z. If the distance from example i in F to an x is the same as the
distance from example j in F to x, then declare i to be the closer example
if |Zi − Z| < |Zj − Z| or if |Zi − Z| = |Zj − Z| and i < j. Otherwise declare
example j to be the closer example. This method returns the same ranking
of distances to examples in F for the same input x every time the distances
are measured, and it uses position within F to break a tie with probability
zero.
Apply the speculate-correct concept to k-nn:
Corollary 2. Let ai (x) be the condition that Vi does not have an example
closer to x than the kth nearest neighbor to x in F − V . Let
X

∀1 ≤ i ≤ r : fi (x, y) = I(bi−1 )
(−1)|S| I g−(S∪{i})
(26)
S⊆Ai−1

and
fr+1 (x, y) = I(bi−1 )

X

S⊆Ar

(−1)|S| I (g−S ) ,

(27)

where I() is the indicator function: one if its argument is true and zero
otherwise. Then
r+1
X
∗
E {fi } .
(28)
p =
i=1

Proof. Our ai for k-nn meet the conditions of Theorem 1.
Next, we show that p∗ is the average of the RHS of Equation 28 from
Corollary 2 over all permutations of the in-sample examples. Permuting the
examples places different examples into the validation subsets because the ith
validation subset is the ith m examples. We will use permutations to ensure
that b1 , . . . , br are rare enough to provide small error bound ranges.
Without permutations, even br may not be rare. For example, in-sample
examples m, 2m, . . . , rm may all be close to much of the input distribution,
and the other in-sample examples may be far. Without permutations, we can
7

develop a bound, but we can only show that it has a small error bound range
in expectation. Permutations guarantee that the expectation is realized.
In the next section, we show how to compute permutation-based bounds
efficiently.
Lemma 3. Let P be the set of permutations of 1, . . . , n. For each σ ∈ P ,
let σF be F permuted according to σ: example j of σF is the example of F
indexed by element j of σ. Let fi,σ be fi , but with F replaced by σF , so that
for i ∈ R, Vi consists of the ith m examples in σF . Then
( r+1
)
X
∗
p = Eσ∈P
E {fi,σ } .
(29)
i=1

Proof. Corollary 2 holds for each partition of F into r size-m subsets V1 , . . . , Vr
and F − V . Each permutation of F uses one of these partitions to define fi,σ .
So the outer expectation is over quantities that are each p∗ .
Separate the RHS of Equation 29 into terms with i ∈ R and a term with
i = r + 1:
!
r
X
p∗ =
Eσ∈P {E {fi,σ }} + Eσ∈P {E {fr+1,σ }}
(30)
i=1

= pI + pII .

(31)

∀(x, y) : |fr+1,σ | ≤ 2r I(br |σ),

(32)

To bound pII , notice that

using ·|σ to denote a condition or set with σF in place of F . So, since
pII = Eσ∈P {E {fr+1,σ }}

(33)

X

(34)

and
fr+1,σ = I (br )

S⊆Ar

(−1)|S| I (g−S ) ,

|pII | ≤ 2r Eσ∈P {E {I(br |σ)}} .

(35)

Exchange the order of expectations:
|pII | ≤ 2r E {Eσ∈P {I(br |σ)}} .
8

(36)

For each (x, y) and F , the inner expectation is the same with probability one.
It is the probability that a random permutation places at least one example
in each of V1 , . . . , Vr that is closer to (x, y) than the k th closest example to
(x, y) in F − V . Since determining positions in a permutation is equivalent
to drawing positions at random without replacement, it is the same as the
probability of drawing at least one element from each set {1, . . . , m}, . . . {(r−
1)m + 1, . . . , rm} before drawing k elements from {rm + 1, . . . , n}, when
drawing uniformly at random without replacement from {1, . . . , n}.
The probability of drawing k elements from {rm + 1, . . . , n} before drawing any from one specific set in {1, . . . , m}, . . . {(r − 1)m + 1, . . . , rm} is





n − rm
n − rm − 1
n − rm − (k − 1)
···
. (37)
n − rm + m
n − rm + m − 1
n − rm + m − (k − 1)
Similarly, the probability of drawing k elements from {rm + 1, . . . , n} before
drawing any elements from any of i specific sets in {1, . . . , m}, . . . {(r −1)m+
1, . . . , rm} is





n − rm
n − rm − 1
n − rm − (k − 1)
···
.
n − rm + im
n − rm + im − 1
n − rm + im − (k − 1)
(38)
So, by inclusion and exclusion, the probability of drawing at least one element
from every set in {1, . . . , m}, . . . {(r − 1)m + 1, . . . , rm} before drawing k
examples from {rm + 1, . . . , n} is:
P rσ∈P



  k−1
n − rm − j
r Y
.
{br |σ} =
(−1)
n
−
rm
+
im
−
j
i
j=0
i=0
r
X

i

(39)

The following lemma bounds this probability:
Lemma 4.
∀x : P rσ∈P {br |σ} ≤



e(k + r − 1)m
n

r

.

(40)

Proof. Define dR (x)|σ to be the condition that the k +r −1 nearest neighbors
to x in F include at least r examples from the validation set V |σ. Condition
dR |σ is a necessary condition for br |σ.
∀x : P rσ∈P {dR |σ} ≥ P rσ∈P {br |σ} .
9

(41)

The probability of dR |σ over σ ∈ P is the same as the probability of drawing
k + r − 1 samples from 1, . . . , n uniformly without replacement and having at
least r of those samples have values rm or less. (The samples are the indices
in σF of the k + r − 1 nearest neighbors to x.) So the probability of dR is
the tail of a hypergeometric distribution:
 n−(k+r−1)
k+r−1
X k+r−1
i
rm−i
∀x : P rσ∈P {dR |σ} =
.
(42)
n
i=r

rm

Using a hypergeometric tail bound from Chvátal [21] (see also Skala
this is
r 

(m−1)r

1
k+r−1
(k + r − 1)m
1+
1−
≤
n
m−1
n
r "
m−1 #r

1
(k + r − 1)m
1+
≤
n
m−1
r

(k + r − 1)m
er .
≤
n
Let
ǫII =



2e(k + r − 1)m
n

Then, using Lemma 4 and Inequality 36,

r

.

|pII | ≤ ǫII .
Now consider pI :
pI =

r
X
i=1

Eσ∈P {E {fi,σ }} .

[22]),

(43)

(44)
(45)

(46)

(47)

(48)

For each σ ∈ P and i ∈ R, the examples in Vi |σ are independent of the
function fi,σ , so we can use empirical means over (x, y) ∈ Vi |σ to estimate
means over (x, y) ∼ D. The following two lemmas give a bound for pI based
on this approach.

10

Lemma 5. ∀i ∈ R, let |Vi | = m. Let M be the set of size-m subsets of F :
M = {Q|Q ⊆ F ∧|Q| = m}. Let P (Q, i) be the set of permutations of 1, . . . , n
that have set Q as validation set Vi in σF : P (Q, i) = {σ|(Vi |σ) = Q}. Then
( r
)
X
pI = EQ∈M
Eσ∈P (Q,i) {E {fi,σ }}
(49)
i=1

Proof. Compare Equations 48 and 49. Equation 48 averages over permutations in P and i ∈ R. In Equation 49, the expectation over Q ∈ M,
i ∈ R, and P (Q, i) covers all permutations P and i ∈ R, each with equal
frequency.
Lemma 6. Let
p̂Q = E(x,y)∈Q

( r
X
i=1

)

Eσ∈P (Q,i) {fi,σ } ,

(50)

and let
p̂I = EQ∈M {p̂Q } .

(51)

∀δ > 0 : P rF ∼Dn {|pI − p̂I | ≥ ǫI } ≤ δ,

(52)

Then
where

1
ǫI ≤ √
m

1
1−

2e(k+r−2)m
n

!

1
√
2

!
2
1.06 ln + 3.22 .
δ
r

(53)

Proof. Let
pQ = E

( r
X
i=1

Then

)

Eσ∈P (Q,i) {fi,σ } .

pI = EQ∈M {pQ } ,

(54)

(55)

since this is Inequality 49 from Lemma 5, with a different order of expectations.
For each Q ∈ M, we will use each p̂Q to bound each pQ , using the fact
the examples in Q are independent of pQ . First, we need to bound the range
of terms in the expectations pQ and p̂Q :
r
X
i=1

Eσ∈P (Q,i) {fi,σ } .
11

(56)

Recall that
fi,σ = I(bi−1 |σ)

X

S⊆Ai−1


(−1)|S| I g−S∪{i} |σ ,

(57)

So for each (x, y) and i ∈ R, in the expectation
Eσ∈P (Q,i) {fi,σ } ,

(58)

the fraction of σ ∈ P (Q, i) for which bi−1 |σ is the same as the probability of
drawing at least one element from each of the first m, second m, ..., (i−1)st m
before drawing k elements from the last n−rm when drawing a sequence uniformly at random without replacement from {1, . . . , (i − 1)m, rm + 1, . . . , n}.
This is less than the probability of drawing i − 1 elements from {1, . . . , (i −
1)m} before drawing k elements from {rm + 1, . . . , n}. Using the proof of
Lemma 4, with i − 1 in place of r, this probability is at most

i−1
e(k + i − 2)m
.
(59)
n
So at most this fraction of σ ∈ P (Q, i) produce nonzero fi,σ .
If bi−1 |σ, then fi,σ sums over 2i−1 terms, and half are zero or one and half
are zero or negative one, so
fi,σ ∈ [−2i−2 , 2i−2 ].

(60)

Multiplying the fraction of nonzero terms by their range bounds:
"

i−1

i−1 #
1 2e(k + i − 2)m
1 2e(k + i − 2)m
.
,
Eσ∈P (Q,i) {fi,σ } ∈ −
2
n
2
n
(61)
Now sum the range upper bound over i ∈ R:

i−1
r
X
1 2e(k + i − 2)m
(62)
2
n
i=1
Since k + i − 2 ≤ k + r − 2, this is
i−1
r 
1 X 2e(k + r − 2)m
.
≤
2 i=1
n
12

(63)

Use the identity 1 + x + x2 + . . . + xr−1 = 1−x
, with x = 2e(k+r−2)m
(with x
1−x
n
as a number, not the input of an example as in the rest of this paper):
!
1
1
.
(64)
≤
2 1 − 2e(k+r−2)m
r

n

So
r
X
i=1

"

1
Eσ∈P (Q,i) {fi,σ } ∈ −
2

1
1−

2e(k+r−2)m
n

!

1
,
2

1
1−

2e(k+r−2)m
n

!#

. (65)

Based on this range, we can apply Hoeffding bounds [18]:


!s

2
ln δ
1
≤ δ.
∀Q ∈ M, δ > 0 : P rF ∼Dn |pQ − p̂Q | ≥
2e(k+r−2)m

2m 
1−
n

(66)

Since

|pI − p̂I | = |EQ∈M {pQ } − EQ∈M {p̂Q } |,

(67)

to bound pI using p̂I , we need to bound the difference between the average of
pQ values and the average of corresponding empirical means p̂Q . According
to [23] (Expression 12 page 8), the bound range for the difference in averages
is not much larger than the average of the Hoeffding bound ranges for the
individual differences over Q. Applying that result:
∀c > 0, δ > 0 : P rF ∼Dn {|pI − p̂I | ≥ ǫ} ≤ δ,

(68)

where
1
ǫ≤ √
2m

1
1−

2e(k+r−2)m
n

(We have 2δ in place of the
c = 3 to prove the lemma.

1
δ

! "r

2
ln
δ



ec
ec − 1



+

√

ec
c+1 c
e −1


2

+1

#

(69)
in [23], because we have two-sided bounds.) Set

Combine this bound on pI with the bound on |pII | to bound p∗ :
Lemma 7.
∀δ > 0 : P rF ∼Dn {|p∗ − p̂I | ≥ ǫI + ǫII } ≤ δ.
13

(70)

Proof. Since p∗ = pI + pII ,
|p∗ − p̂I | = |(pI + pII ) − p̂I | ≤ |pI − p̂I | + |pII |.

(71)

By Inequality 47, |pII | ≤ ǫII . From the definition of ǫI (Lemma 6),
∀δ > 0 : P rF ∼Dn {|pI − p̂I | ≥ ǫI } ≤ δ.

(72)

∀δ > 0 : P rF ∼Dn {|pI − p̂I | + |pII | ≥ ǫI + ǫII } ≤ δ.

(73)

So

The following Theorem and Corollary are the main results for k-nn classifiers. The theorem allows r, k, and δ to depend on the number of in-sample
examples, n. The corollary uses the bound from the theorem with an appropriate growth rate for r as n increases (r ∈ O(ln n)).
Theorem 8.
∀δ > 0 : P rF ∼Dn {|p∗ − p̂I | ≤ ǫr } ≤ δ,

(74)



r p
ǫr ∈ O n− 2r+1 (k + r) .

(75)

with

Proof. Select validation set sizes m to balance ǫI and ǫII :
r
1

n r+ 2
m=⌈
⌉.
2e(k + r − 1)
Then
ǫII =
and
r
− 2r+1

ǫI ≤ n





2e(k + r − 1)m
n

1
1

1 − n− 2r+1



p

r

(76)



r
∈ O n− 2r+1 ,

1
2e(k + r − 1) √
2

!
2
1.06 ln + 3.22 . (78)
δ
r

If we allow for the possibility of k and r growing with n, then


r √
− 2r+1
k+r .
ǫr = ǫI + ǫII ∈ O n
14

(77)

(79)

Corollary 9. For a choice of r based on n,
∀δ > 0 : P rF ∼Dn {|p∗ − p̂I | ≤ ǫ∗ } ≤ δ,
with
ǫ∗ ∈ O

p


(k + ln n)/n .

(80)
(81)

Proof. If we set r = ⌈ 41 (ln n − 2)⌉, then
r

1

1

1

1

1

n− 2r+1 = n 4r+2 n− 2 ≤ n ln n n− 2 = en− 2 .

(82)



(83)

So

− 21

ǫ∗ = ǫI + ǫII ∈ O n

p



(k + ln n) .

An alternative proof of Corollary 9 uses a different value for m:
Alternative Proof of Corollary 9. Let
m=⌊
Then
ǫII =
For ǫI , note that
m≥



2e2 (k

n
⌋.
+ r − 1)

2e(k + r − 1)m
n

r

≤

(84)
1
.
er

n
n − 2e2 (k + r − 1)
−
1
=
.
2e2 (k + r − 1)
2e2 (k + r − 1)

Substitute the RHS for m in Inequality 53:
!
r
 p 2

2e (k + r − 1)
2
1
1
p
√
1.06 ln + 3.22 .
ǫI ≤
δ
1 − 1e
n − 2e2 (k + r − 1) 2
√
Let r = ⌈ln n⌉. Then
1
1
ǫII ≤ ln √n = √ ,
n
e
and
p

ǫI ∈ O
(k + ln n)/n .
15

(85)

(86)

(87)

(88)
(89)

4. Computation
It would be infeasible to compute the error bounds developed in this paper
directly from their definitions. Instead, we can sample the bound terms to
produce a bound. In this section, we outline a sampling procedure that
requires O(n(ln n)2 ) computation (in addition to identifying up to k + r − 1
nearest neighbors
in F for
p
 each example in F ) and produces a bound with
range O
(k + ln n)/n .
Note that


p̂I = Eσ∈P rEi∈R E(x,y)∈Vi |σ {fi,σ } .
(90)
(For reference, p̂I is defined in Equations 50 and 51 of Lemma 6.) Let
P ((x, y), i) = {σ|(x, y) ∈ (Vi |σ))}. Reordering expectations,


p̂I = E(x,y)∈F rEi∈R Eσ∈P ((x,y),i) {fi,σ } .
(91)

Rewrite fi,σ as the expectation of its terms:

fi,σ = I(bi−1 )2i−1 ES⊆Ai−1 (−1)|S| I(g−(S∪{i}) |σ) .

(92)

Estimate p̂I as defined in the previous two equations by taking an empirical mean over s random samples:
((x, y), i, σ, S) ,

(93)

with (x, y) drawn uniformly at random from F , i uniformly at random from
R, σ uniformly at random from P ((x, y), i), and S uniformly at random from
the power set of Ai−1 . Each sample value is
rI(bi−1 )2i−1 (−1)|S| I(g−(S∪{i}) |σ).

(94)

Let p′I be the empirical mean of these samples.
To bound the difference between p̂I and its estimate p′I , we will use a twosided version of an Inequality from Maurer and Pontil [24], that is derived
from Bennett’s Inequality [25]:


s

2
2
r
2v ln δ
r2 ln δ
∀δ > 0 : P rF ∼Dn |p̂I − p′I | ≥
≤ δ,
(95)
+

s
3s 
where v is the variance of samples for the empirical mean. (The term r2r
accounts for the range of our samples: [−r2i−1 , r2i−1].) We use this inequality
16

instead of Hoeffding’s Inequality in order to take advantage of the small
variance of our samples relative to their range.
To bound v, note that bi−1 has probability at most

i−1
e(k + i − 2)m
.
(96)
n
So each sample has at most that probability of being nonzero. Sample range
is [−r2i−1 , r2i−1 ]. Since variance is at most the expectation of the square:

i−1
i−1


4e(k + i − 2)m
e(k + i − 2)m
i−1 2 2
2
r =
v≤
r2 .
(97)
n
n
So set

m<

n
4e(k + r − 2)

(98)

to ensure v ≤ r 2 . (The value for m in the alternative proof of Corollary 9
meets this condition.) Then select a number of samples s to achieve a desired
balance between computation and accuracy.
Computing values for samples in p′I need not involve drawing complete
permutations σ. Instead, randomly determine set membership in F − V |σ,
Vi |σ, ..., or Vr |σ for neighbors of the sample (x, y) and tabulate votes to
determine I(g−(S∪{i}) |σ), proceeding one neighbor at a time until the kth
neighbor from F − V |σ is identified, as follows.
Let N0 (x) = (x, y). Let Nj (x) be (x, y) and the j nearest neighbors to
(x, y) in F . At each step, let f = |(F − V |σ) ∩ Nj (x)|. For each i ∈ R, let
vi = |Vi ∩ Nj (x)|. Let b be the number of voting neighbors (b for “ballots”)
among the j nearest neighbors to (x, y): b = |((F − Vi ) − ∪h∈S Vh |σ) ∩ Nj (x)|.
Let d be the number of those voters that have different labels than y.
Initially, j = 0, f = 0, vi = 1, ∀h 6= i : vh = 0, b = 0, and d = 0. Then,
for each j starting with j = 1, select a set for the j th nearest neighbor at
random and increment its counter:
n−f −

F − V |σ with probability
1
V1 |σ with probability m−v
:
n−j
..
.
Vr |σ with probability

m−vr
n−j

:

P

h∈R (m−vh )

n−j

: f := f + 1
v1 := v1 + 1
..
.

(99)

vr := vr + 1

If b < k (fewer than k votes cast) and the set is F − V |σ or Vh |σ for h 6= i
and h 6∈ S, then b := b + 1 (another ballot is cast) and if the label of the
17

j th nearest neighbor is not equal to y, then d := d + 1 (another disagreeing
vote). Stop when f = k, and return the sample value:
rI(∀h < i : vh > 0)2i−1 (−1)|S| I(d ≥

k+1
).
2

(100)

This method may require up to O(rm + k) computation per sample,
because it is possible (though extremely unlikely) for an example to have all
validation examples in V |σ as nearer neighbors than the k th nearest neighbor
from F − V |σ. To reduce worst-case computation, stop computation for a
sample if r neighbors are assigned to validation sets before the k th neighbor
is assigned to F − V |σ (that is, if f < k and v1 + . . . + vr = r), and return
zero as the value for the sample.
Recall that dR (x)|σ (defined in Lemma 4) is the condition that there are
at least r nearer neighbors to x in V |σ than the k th nearest neighbor in
F − V |σ. Instead of sampling p̂I , the modified procedure samples a modified
p̂I that sets terms to zero if they meet condition dR |σ. (Define p̃I to be this
modified p̂I .) To account for the lost terms, apply Lemma 4. (It applies to
our x from (x, y) ∈ Vi |σ as well as to random (x, y) ∼ D, because having our
(x, y) in a validation set only decreases the probability of dR |σ.) So

r
e(k + r − 1)m
∀i ∈ R : P rσ∈P ((x,y),i) {dR |σ} ≤
.
(101)
n
Since the maximum absolute value of each of these terms is 2i−1 , the sum of
the lost terms is at most
r
r


r
X
e(k + r − 1)m
e(k + r − 1)m
r
i−1
<2
= ǫII .
(102)
2
n
n
i=1
So add another ǫII to bounds to account for the lost terms.
The modified procedure requires only O(k + r) computation for each
sample, beyond any computation required to find the k + r − 1 nearest neighbors from F − {(x, y)} to the sample’s example (x, y). Using s = rn samples, if r + k ∈ O(ln n), then the modified sample value procedure requires
O(n(ln n)2 ) computation in addition to neighbor-finding.
Now combine sampling, the modified sample value computation procedure, and Corollary 9 to form an error bound that can be computed efficiently. Let s = rn. Use 2δ as the bound failure probability for the bound
18

from Corollary 9, and use 2δ as the bound failure probability for the sampling
procedure. (The reasoning about the variance of sample values also applies
to the modified procedure, since it zeros some sample values and leaves the
rest unchanged.) Use the m and √
r values from the alternative proof of Corollary 9: Equation 84 and r = ⌈ln n⌉. Let p̃′I be average of the sample values
from the modified sampling method. Then we have bound:


s
√
√

4
4
⌈ln n⌉
ln δ
2⌈ln n⌉ ln δ
2
∀δ > 0 : P rF ∼Dn |p∗ − p̃′I | ≥ ǫ̃I + 2ǫII +
≤ δ,
+


n
3n
(103)

where ǫ̃I is ǫI from Inequality 87 with 2δ substituted for δ:
!
r

 p 2
2e (k + r − 1)
1
1
4
p
√
ǫ̃I ≤
1.06 ln + 3.22 ,
δ
1 − 1e
n − 2e2 (k + r − 1) 2

(104)

and ǫII is from Inequality 88:

ǫII ≤

1
eln

√

n

1
=√ .
n

(105)

The bound range:
2
ǫ̃I + √ +
n
is

s

2⌈ln

√

√

n⌉ ln 4δ
2⌈ln n⌉ ln 4δ
+
n
3n

p

O
(k + ln n)/n .

(106)

(107)

Appendix A presents methods to compute rather than estimate p̂I or p̃′I .
The method to compute p̃′I requires O(n ln n) computation, like sampling,
but it requires O((ln n)4 ) space, and it is more complicated than sampling.
5. Conclusion
We have shown that k-nearest neighbor classifiers have exponential PAC
error bounds with

p
(k + ln n)/n .
(108)
O

error bound ranges. The bounds are quite general. They apply to any type
of inputs, because they are based on probability rather than geometry. Also,
19

they have no terms that increase with the number of dimensions or other
properties of the input space. The bounds also do not require the k-nn
classifier’s method to compute distances among examples to be symmetric
or obey the triangle inequality – it need not be a metric in the mathematical
sense. It can be any function on two example inputs that returns a number.
It may be possible to improve the error bound by using a tighter bound on
the probability that multiple validation subsets have neighbors to an input
that are closer than the k nearest neighbors among the non-validation insample examples. Our bound does not require that each validation subset
have such a neighbor, only that collectively they have as many such neighbors
as the number of validation subsets. Equation 39 enforces that condition. In
practice, use it in place of Lemma 4.
We average bounds over all choices of validation subsets so that we can
prove the resulting bound has a small range. If, instead, we use a single
random choice of validation subsets, then we can also produce an exponential
PAC error bound. To do this, use each validation set Vi to validate fi (), and
use a random subset of the remaining in-sample examples to validate the rate
of all validation subsets having a neighbor closer to an input than the k th
nearest neighbors among the other in-sample examples. (In a transductive
setting [29], or if unlabeled inputs
p are otherwise
 available, use them for this
validation.) This bound has O
(k + ln n)/n in expectation. We average
over choices of validation subsets to guarantee that we realize the expectation.
We showed how to use sampling to “estimate the estimates” of the error
bounds. We also showed (in the appendix) an efficient, but more complex
and space-consuming, method to compute an estimate. It may be possible
to improve or simplify that procedure by gathering terms in a different way.
In the future, it would be interesting to extend the k-nearest neighbor
error bounds from this paper to cover selection of a distance metric from a
parameterized set of “hypothesis” metrics [30]. One approach might be to use
uniform bounds of the type derived in this paper over the class of potential
metrics. The bounds might depend on some notion of the complexity of the
class of potential metrics.
Finally, it would be interesting to apply the speculate-correct technique
from this paper to derive error bounds for classifiers other than nearest neighbors. Other local classifiers include some collective classifiers [31, 32], such
as network classifiers based only on neighbors or neighbors of neighbors in
a graph. (For some background on error bounds for network classifiers, re20

fer to [33, 34, 35].) It may also be possible to apply the speculate-correct
method to other types of classifiers that are typically based on small subsets
of the in-sample examples, such as support vector machines [29, 36, 37] and
set-covering machines [38].
Appendix A. Method to Compute p̂I and p̃′I .
By gathering terms rather than sampling, we can compute p̂I and p̃I
exactly. In this appendix, we show how to compute p̂I exactly and how to
compute p̃′I in O(n ln n) time and O((ln n)4 ) space, assuming k + r ∈ O(ln n)
and ignoring any time and space required to find the k + r nearest neighbors
to each in-sample example. The methods in this section are inspired by a
similar approach for a single validation subset by [39].
Recall from Equations 91 and 92 that


p̂I = E(x,y)∈F Ei∈R Eσ∈P ((x,y),i) {fi,σ } ,
(A.1)
and


fi,σ = I(bi−1 )2i−1 ES⊆Ai−1 (−1)|S| I(g−(S∪{i}) |σ) .

(A.2)

Use the symmetry of permutations over same-size subsets S to compute only
for S = {1, . . . , |S|}, and use s to index values of |S|. Note that


i − 1 −(i−1)
2
.
(A.3)
P rS⊆Ai−1 {|S| = s} =
s
Let As = {1, . . . , s}. Let
Then


p(x,y),i = P rσ∈P ((x,y),i) bi−1 ∧ g−As ∪{i} |σ .
p̂I = E(x,y)∈F

(


r X
i−1 
X
i−1
(−1)s p(x,y),i
s
i=1 s=0

)

(A.4)

.

(A.5)

Refer to the j th nearest neighbor to (x, y) in F − {(x, y)} as neighbor
j. Let ct,u,v (σ) be the condition that a permutation σ assigns the neighbors
to (x, y) to sets F, V1 , . . . , Vr |σ such that there are exactly k voters (in F −
(Vi ∪ V1 . . . Vr )|σ) among neighbors 1 to t, neighbor t is a voter, there are k
neighbors from F − V |σ among neighbors 1 to u, neighbor u is from F − V |σ,
and there are v voters among neighbors 1 to u. Let
pt,u,v = P rσ∈P ((x,y),i) {ct,u,v (σ)} ,
21

(A.6)

and
P̂ = {σ ∈ P ((x, y), i) : ct,u,v (σ)}.
Then

k+(s+1)m−1 k+rm−1

p(x,y),i =

X
t=k

where

(A.7)

u
X X
u=t

pt,u,v ps pi−1−s pg ,

(A.8)

v=k

ps = P rσ∈P̂ {bs |σ} ,

(A.9)

pi−1−s = P rσ∈P̂ {¬as+1 ∧ . . . ∧ ¬ai−1 |σ} , and

pg = P rσ∈P̂ g−As∪{i} |σ .

(A.10)
(A.11)

To see why, compare this to Equation A.4. For each (t, u, v), we multiply the
probability of ct,u,v , which is pt,u,v , by ps , pi−1−s , and pg , each conditioned
on ct,u,v . (Taking probabilities over P̂ conditions on ct,u,v .) Together, the
conditions in ps , pi−1−s , and pg are equivalent to the condition in Equation
A.4, because bs ∧¬as+1 ∧. . .∧¬ai−1 |σ equals bi−1 |σ. The limits of summation
for t and u follow from the fact that, with (x, y) ∈ Vi |σ, there are (s +
1)m − 1 remaining non-voter assignments and rm − 1 remaining validation
set assignments for each σ in P ((x, y), i).
To compute pt,u,v , note that with (x, y) ∈ Vi |σ, for σ ∈ P ((x, y), i), there
are n − 1 remaining assignments, including m − 1 to Vi |σ, m for each other
validation subset, and n − rm for F − V |σ. This includes n − (s + 1)m voters
and (s + 1)m − 1 non-voters. So
pt,u,v =




n−(s+1)m (s+1)m−1   n−(s+1)m−k (s+1)m−1−(t−k)
k
v−k
u−t−(v−k)
k
 t−k

n−1
n−1−t
t
t
u−t
min(k,v−k)

X
z=0

v−k
z



v
k

k
k−z





z
u−t

!

(A.12)
n−rm (r−(s+1))m
k
v−k

n−(s+1)m
v

.





(A.13)
(A.14)

The terms are the probabilities of the following conditions, respectively, each
conditioned on the previous terms’ conditions:
1. There are exactly k voters among the first t neighbors.
2. Neighbor t is one of those k voters.
22

3. The first u neighbors include exactly v voters.
4. Exactly k of the v voters are in F − V |σ.
5. Neighbor u is from F −V |σ. (The sum is over the number z of neighbors
z
t + 1 to u in F − V |σ.) If u−t
= 00 , then treat it as one.
Now consider the three probabilities ps , pi−1−s , and pg . The first is
the probability that the validation subsets V1 |σ, . . . , Vs |σ are all represented
among the nearer neighbors to (x, y) than the k th nearest neighbor from
F − V |σ. Since we condition on ct,u,v (by taking the probability only over
σ ∈ P̂ , for which ct,u,v holds), the condition is that among the neighbors
assigned u − v of the (s + 1)m − 1 non-voter positions, each of s sets of m positions is represented. Use inclusion and exclusion, counting all ways to select
the u − v neighbors, subtracting ways to select the u − v neighbors without
drawing from each set V1 |σ, . . . , Vs |σ, adding those that avoid drawing from
each pair of sets, and so on:
s
X

−1

 
s (s + 1 − j)m − 1 (s + 1)m − 1
.
ps =
(−1)
u
−
v
u
−
v
j
j=0
j

(A.15)

Similarly, the condition for pi−1−s , given ct,u,v , is that all of Vs+1 |σ, . . . , Vi−1 |σ
are represented among the v − k voters with positions in Vs+1 ∪ . . . ∪ Vi−1 ∪
Vi+1 ∪ . . . ∪ Vr |σ. (The other k voters are in F − V |σ.) Once again, use
inclusion and exclusion:
−1



i−1−s
X
(r − s − 1 − j)m (r − s − 1)m
j i−1−s
.
pi−1−s =
(−1)
v
−
k
v
−
k
j
j=0

(A.16)
The condition for pg , given ct,u,v , is that at least
of the nearest k
voters, of which the last is neighbor t, have labels that disagree with y. Let
yj be the label of neighbor j. Let dj count the labels among neighbors 1 to
j that disagree with y. Use b to count how many neighbors with labels that
disagree with y are among the k − 1 voters nearer to (x, y) than neighbor t.
Then
−1



k−1
X
t−1
t − 1 − dt−1
dt−1
.
(A.17)
pg =
k
−
1
k
−
1
−
b
b
k+1
k+1
2

b=

2

−I(yt 6=y)

23

Substitute Equation A.8 into Equation A.5 to get an equation for p̂I :



k+(s+1)m−1 k+rm−1 u
r X
i−1 

X
X
X
X
i−1
s
pt,u,v ps pi−1−s pg .
(−1)
p̂I = E(x,y)∈F


s
u=t
i=1 s=0
t=k
v=k

(A.18)

For

p̃′I ,

reduce the upper limits of summation for t and u to k + r:
)
( r i−1 
k+r X
k+r X
u
X
X X i − 1
pt,u,v ps pi−1−s pg . (A.19)
(−1)s
p̃′I = E(x,y)∈F
s
u=t
i=1 s=0
t=k

v=k

To compute this value, notice that only pg depends on values that are specific
to each example (x, y) – the values dt−1 and I(yt 6= y). Since pg only depends
on those values and t, we can rearrange the sum:
)
( k+r
X
′
pg q(t) ,
(A.20)
p̃I = E(x,y)∈F
t=k

where

k+r X
u
r X
i−1 
X
X
i − 1 −(i−1)
pt,u,v ps pi−1−s .
2
(−1)s
q(t) =
s
u=t v=k
i=1 s=0

(A.21)

To compute q(t), first compute and store pi−1−s for all feasible (i, s, v) and
ps for all feasible (s, u, v). Next, compute and store the last term of pt,u,v for
all feasible (v, u − t), then use those values to compute and store pt,u,v for
all feasible (s, t, u, v). This requires O(r 4 ) computation and storage. Then
compute q(t) for each t ∈ {k, . . . , k + r} by iterating through the sums and
using the pre-computed values for pt,u,v , ps , and pi−1−s . This requires O(r 4 )
computation.
To compute p̃′I , first compute pg for all feasible (t, dt−1 , I(yt 6= y)). This
requires O(rk(k + r)) computation and O(r(k + r)) storage. Then, for each
(x, y) ∈ F , find its k + r nearest neighbors in F − V , use the neighbors’ labels
to compute dt−1 and I(yt 6= y) for t ∈ {k, . . . , k + r}. This requires O(k + r)
computation. Then compute the sum over t in Equation A.20, using dt−1 and
I(yt 6= y) values to select precomputed pg values and using the precomputed
q(t) values. This produces a sample value for (x, y). Average those sample
values over (x, y) ∈ F to compute p̃′I .
24

Using this method, aside from the time to find the k +r nearest neighbors
to each in-sample example, the time complexity is O(max(r 4 , rk(k +r), n(k +
r))) and the storage complexity is O(max(r 4 , r(k + r))). If k ∈ O(ln n) and
r ∈ O(ln n) and n > (ln n)3 , then this is O(n ln n) time and O((ln n)4 )
storage.
References
[1] V. Vapnik, A. Chervonenkis, On the uniform convergence of relative
frequencies of events to their probabilities, Theory of Probability and
its Applications 16 (1971) 264–280.
[2] L. G. Valiant, A theory of the learnable, Commun. ACM 27 (11) (1984)
1134–1142. doi:http://doi.acm.org/10.1145/1968.1972.
[3] N. Littlestone, M. Warmuth, Relating data compression and learnability,
unpublished manuscript, University of California Santa Cruz (1986).
[4] S. Floyd, M. Warmuth, Sample compression, learnability, and the
Vapnik-Chervonenkis dimension, Machine Learning 21 (3) (1995) 1–36.
[5] A. Blum, J. Langford, PAC-MDL bounds, in: Proceedings of the 16th
Annual Conference on Computational Learning Theory (COLT), 2003,
pp. 344–357.
[6] E. Bax, Nearly uniform validation improves compression-based error
bounds, Journal of Machine Learning Research 9 (2008) 1741–1755.
[7] E. Bax, A. Callejas, An error bound based on a worst likely assignment,
Journal of Machine Learning Research 9 (2008) 581–613.
[8] J. Langford, Tutorial on practical prediction theory for classification,
Journal of Machine Learning Research 6 (2005) 273–306.
[9] T. M. Cover, P. E. Hart, Nearest neighbor pattern classification, IEEE
Transactions on Information Theory 13 (1967) 21–27.
[10] T. M. Cover, Rates of convergence for nearest neighbors procedures, in:
B. K. Kinariwala, F. F. Kuo (Eds.), Proceedings of the Hawaii International Conference on System Sciences, University of Hawaii Press, 1968,
pp. 413–415.
25

[11] D. Psaltis, R. Snapp, S. Venkatesh, On the finite sample performance
of the nearest neighbor classifier, IEEE Transactions on Information
Theory 40 (3) (1994) 264–280.
[12] L. Devroye, L. Györfi, G. Lugosi, A Probabilistic Theory of Pattern
Recognition, Springer, 1996.
[13] R. O. Duda, P. E. Hart, D. G. Stork, Pattern Classification, Wiley, 2001.
[14] T. Hastie, R. Tibshirani, J. Friedman, The Elements of Statistical Learning: Data Mining, Inference, and Prediction, Second Edition, Springer,
2009.
[15] W. Rogers, T. Wagner, A finite-sample distribution-free performance
bound for local discrimination rules, Annals of Statistics 6 (1978) 506–
514.
[16] L. Devroye, T. Wagner, Distribution-free inequalities for the deleted and
holdout estimates, IEEE Transactions on Information Theory 25 (1979)
202–207.
[17] E. Bax, Y. Le, Some theory for practical classifier validation, Baylearn.
URL http://arxiv.org/abs/1510.02676
[18] W. Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (301) (1963)
13–30.
[19] S. Boucheron, G. Lugosi, P. Massart, Concentration Inequalities – A
Nonasymptotic Theory of Independence, Oxford University Press, 2013.
[20] E. Bax, Validation of k-nearest neighbor classifiers, IEEE Transactions
on Information Theory 58 (5) (2012) 3225–3234.
[21] V. Chvátal, The tail of the hypergeometric distribution, Discrete Mathematics 25 (3) (1979) 285–287.
[22] M. Skala, Hypergeometric tail inequalities: ending the insanity, arXiv
arXiv:1311.5939v1.
URL https://arxiv.org/abs/1311.5939v1

26

[23] E. Bax, F. Kooti, Ensemble validation: Selectivity has a price, but variety is free,
Baylearn.
URL https://arxiv.org/pdf/1610.01234v1.pdf
[24] A. Maurer, M. Pontil, Empirical bernstein bounds and sample-variance
penalization, 22nd Annual Conference on Learning Theory (COLT).
[25] G. Bennett, Probability inequalities for the sum of independent random variables, Journal of the American Statistical Association 57 (297)
(1962) 33–45.
[26] E. Bax, Validation of average error rate over classifiers, Pattern Recognition Letters (1998) 127–132.
[27] D. A. McAllester, Pac-bayesian model averaging, in: In Proceedings
of the Twelfth Annual Conference on Computational Learning Theory,
ACM Press, 1999, pp. 164–170.
[28] J. Langford, M. Seeger, N. Megiddo, An improved predictive accuracy
bound for averaging classifiers, in: In Proceeding of the Eighteenth International Conference on Machine Learning, 2001, pp. 290–297.
[29] V. Vapnik, Statistical Learning Theory, John Wiley & Sons, 1998.
[30] D. Kedem, S. Tyree, F. Sha, G. R. Lanckriet, K. Q. Weinberger,
Non-linear metric learning, in: F. Pereira, C. J. C. Burges, L. Bottou,
K. Q. Weinberger (Eds.), Advances in Neural Information Processing
Systems 25, Curran Associates, Inc., 2012, pp. 2573–2581.
URL http://papers.nips.cc/paper/4840-sB non-sB linear-sB metric-sB learning.pdf
[31] P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Gallagher, T. Eliassi-Rad,
Collective classification in network data, AI Magazine 29 (3) (2008) 93–
106.
[32] S. A. Macskassy, F. Provost, Classification in networked data: A toolkit
and a univariate case study, Journal of Machine Learning Research 8
(2007) 935–983.
[33] B. London, B. Huang, L. Getoor, Improved generalization bounds for
large-scale structured prediction, in: NIPS Workshop on Algorithmic
and Statistical Approaches for Large Social Networks, 2012.
27

[34] J. Li, A. Sonmez, Z. Cataltepe, E. Bax, Validation of network classifiers,
Structural, Syntactic, and Statistical Pattern Recognition Lecture Notes
in Computer Science 7626 (2012) 448–457.
[35] E. Bax, J. Li, A. Sonmez, Z. Cataltepe, Validating collective classification using cohorts, NIPS Workshop on Frontiers of Network Analysis:
Methods, Models, and Applications.
[36] N. Cristianini, J. Shawe-Taylor, An Introduction to Support Vector Machines and Other Kernel-Based Learning Methods, Cambridge University Press, 2000.
[37] T. Joachims, Learning to Classify Text using Support Vector Machines,
Kluwer Academic Publishers, 2002.
[38] M. Marchand, J. Shawe-Taylor, Learning with the set covering machine,
in: Proceedings of the Eighteenth International Conference on Machine
Learning (ICML 2001), 2001, pp. 345–352.
[39] M. Mullin, R. Sukthankar, Complete cross-validation for nearest neighbor classifiers, Proceedings of the Seventeenth International Conference
on Machine Learning (2000) 639–646.

28

