Journal of Machine Learning Research 2 (2002) 335-358 Submitted 6/01; Published 2/02

Machine Learning with Data Dependent Hypothesis Classes

Adam Cannon cannon@cs.columbia.edu Department of Computer Science Columbia University New York, NY 10027, USA

J. Mark Ettinger ettinger@lanl.gov Nonproliferation and International Security Group, NIS-8 Los Alamos National Laboratory Los Alamos, NM 87545, USA

Don Hush dhush@lanl.gov Clint Scovel jcs@lanl.gov Modeling, Algorithms, and Informatics Group, CCS-3 Los Alamos National Laboratory Los Alamos, NM 87545, USA

Editor: Peter Bartlett

Abstract

We extend the VC theory of statistical learning to data dependent spaces of classifiers. This theory can be viewed as a decomposition of classifier design into two components; the first component is a restriction to a data dependent hypothesis class and the second is empirical risk minimization within that class. We define a measure of complexity for data dependent hypothesis classes and provide data dependent versions of bounds on error deviance and estimation error. We also provide a structural risk minimization procedure over data dependent hierarchies and prove consistency. We use this theory to provide a framework for studying the trade-offs between performance and computational complexity in classifier design. As a consequence we obtain a new family of classifiers with dimension independent performance bounds and efficient learning procedures. Keywords: Computational Learning Theory, Empirical Process Theory, Classification, Shatter Coefficient, Structural Risk Minimization

1. Introduction

Vapnik motivated his development of support vector machines as a kind of structural risk minimization. However, the corresponding class sequence is data dependent and so Vapnik’s theory of structural risk minimization does not apply. To resolve this issue, Shawe-Taylor et al. (1998) have developed a theory of structural risk minimization over data dependent hierarchies which gives performance guarantees for support vector machines (see also Shawe-Taylor & Cristianini, 2000). In addition, the work on data dependent complexity regularization of Buescher and Kumar (1996), the posterior bounds of Freund (1998), the conditional bounds of Devroye (1988), and the work on data dependent penalties of Koltchinskii et al. (2000), Koltchinskii (2001), Boucheron et al. (2000), and Bartlett et al. (2000) have a similar goal.

\begin{matrix}c \\ ◯ \end{matrix}2002 Adam Cannon, J. Mark Ettinger, Don Hush and Clint Scovel.

Cannon, Ettinger, Hush and Scovel

Devroye (1988) developed performance bounds for data dependent hypothesis classes in a similar spirit to those presented here. However Devroye’s approach provides conditional bounds whereas the approach taken here more closely resembles the VC framework developed by Vapnik. Recently Gat (1999) proved a performance bound for the perceptron that extended the VC theorem to the case of data dependent classes of classifiers. This bound uses a counting complexity instead of a shattering complexity for the data dependent class. In this paper we show that Gat’s result can be extended in terms of a shatter coefficient for data dependent classes. We build on this result to construct a new framework for learning with data dependent hypothesis classes. Although the framework of Shawe-Taylor et al. may be more general, its exact relationship to the framework developed here is not clear. At a minimum the two frameworks appear to differ in the ease with which they can be applied to particular learning paradigms. For example, our framework has not yet provided performance guarantees for support vector machines. However, it has facilitated the discovery of new families of classifiers that possess dimension independent performance guarantees for empirical risk minimization.

We contrast our framework with the VC framework. In the VC framework the generalization error can be decomposed into two components, the approximation error A which quantifies the lack of optimality introduced by our choice of hypothesis class, and the estimation error E which quantifies the lack of optimality of empirical error minimization due to finite sample size. For classes with finite VC dimension the celebrated VC theorem provides a distribution independent bound on E that goes to zero as the number of training samples n goes to infinity. Control on the approximation error is provided through a structural risk minimization (SRM) learning procedure that is proved to be consistent for an infinite sequence of classes with finite VC dimension.

In our framework classifier design is decomposed into two components; the first component is the restriction to the data dependent hypothesis class and the second is empirical risk minimization within that class. We define data dependent versions of approximation error A_{D} and estimation E_{D} error in the obvious way. We provide a VC-like theorem that gives bounds on E_{D} in terms of a shatter coefficient for data dependent classes. Based on Vapnik’s construction we also provide a structural risk minimization procedure over data dependent hierarchies and prove consistency. When the data dependent hypothesis class is obtained by restricting a traditional class through a data dependency rule the data dependent approximation error A_{D} splits into

A_{D} = A + E_{DD}

where A is the approximation error for the traditional class and E_{DD} is the data dependency error. Consequently the analysis of approximation error is similar to that for traditional classifiers, except for the data dependency error term. We have just begun the study of this random variable. For example we show that when the data dependency is symmetric in its dependence on the n-sample the infinite sample limit of this random variable is a constant. At present we do not know general conditions on the data dependency that allow this constant to be computed, and in particular when it is zero. However, for the structural risk minimization over multi-sphere classifiers described in Section 5.2 this constant is zero. In this case we have also shown that the infinite sample limit of the data dependent approximation error is zero.

Machine learning with data dependent hypothesis classes

We also wish to address the computational requirements of the learning procedure. Despite the performance guarantees provided by the VC theory, empirical error minimization is computationally intractable for nearly all nontrivial hypothesis classes. One of the strengths of our framework is that it allows us to explore trade-offs between generalization error and computational requirements through the choice of data dependency. For example, it allows us to modify a traditional classifier to obtain a family of classifiers through various data dependencies, and to quantify the performance and computational requirements over this family with a greater degree of flexibility than we have seen before. Among the families considered here are classifiers with dimension independent performance bounds that may benefit from kernel mappings to high dimensions like those used in support vector machines.

This paper is organized as follows. We prove uniform convergence of empirical processes over data dependent classes as an extension of Gat’s theorem. Specific data dependent classes are introduced and their computational and structural complexity analyzed. A structural risk minimization procedure is described and a consistency theorem proven. The structural risk minimization procedure is demonstrated on a specific family of spherical classifiers and conditions for consistency with the Bayes error are provided. Finally we describe a framework for analyzing the trade-offs between computation and performance as a function of the data dependency and apply it to the family of spherical classifiers.

2. Uniform convergence of empirical processes over data dependent classes

Let Z denote a metric space with its Borel σ-algebra and a Borel probability measure μ. We let Z_{n} denote the n-fold product of Z with itself with product σ-algebra and let P_{Z_{n}} = μ^{n} denote the n-fold product of the measure μ. We denote n independent samples {z_{n}(i), i = 1, .., n} as z_{n} = (z_{n}(1), .., z_{n}(n)) ∈ Z_{n}. In this paper we consider functions f : Z → {0, 1}. We define F_{n} to be a class of such functions, where members of this class are determined through application of a data dependency rule to n-samples. For example, in Section 4.2 we consider functions that dichotomize ℜ^{d} with a sphere where the data dependency rule forces the sphere to be centered at one of the n data points. Therefore, F_{n} is a class of binary functions on (Z_{n}, Z). We define a data dependent class F = {F_{n}} to be a collection of classes F_{n}.

We now assume some structure concerning the classes’ data dependency and the classes’ description as a parametric family. We denote the class F restricted to the n-sample z_{n} by F_{z_{n}}. We assume we can describe this class in parametric form through some parameter space Y_{n}, not necessarily a product space, such that each function is f_{y_{n},z_{n}}(z) for some choice of y_{n} ∈ Y_{n} and each choice of y_{n} gives a function in the class. Then the whole data dependent class on n samples can be described by a single function Ξ_{n}(y_{n}, z_{n}, z) = f_{y_{n},z_{n}}(z). Recall that a Polish space is a complete separable metric space and a Suslin space is a Borel measurable image of a Polish space. We say that the data dependent class F_{n} is image admissible Suslin if there exists a Suslin parameter space Y_{n} and a z_{n} parameterized family of maps T_{z_{n}} : Y_{n} → F_{z_{n}} such that the evaluation function

Ξ_{n}; Y_{n} × Z_{n} × Z → {0, 1}

defined by Ξ_{n}(y_{n}, z_{n}, z) = (T_{z_{n}}(y_{n}))(z) is jointly measurable in (y_{n}, z_{n}, z) with the product σ-algebra of the Borel sets of Y_{n} and Z_{n+1}. The inclusion of measurability considerations for the results in this section goes through in much the same way as for the V C theorem as presented by Dudley (1999). On the other hand in the proof of Theorem 15 in Section 5.1.2 measurability is crucial and so we consider it explicitly then.

There is a one to one mapping between functions f : Z → {0, 1} and their indicator sets I(f) = {z : f(z) = 1}. Throughout this paper we make this identification regularly without comment. In particular we identify μ(f) = μ(I(f)).

Definition 1 For n ≤ m define N_{n}(z_{m}, F) to be the number of distinct dichotomies of the m points z_{m} generated as the functions vary over the union of the data dependent classes determined by all subsets of z_{m} containing n points. That is, let I_{f} = {z : f(z) = 1} denote the set where the function is equal to one. Then N_{n}(z_{m}, F) is the number of different sets in

{{z_{m}(1), ..., z_{m}(m)} ∩ I_{f} : f ∈ F_{w_{n}}, w_{n} ⊂ z_{m}}

where w_{n} ⊂ z_{m} means that {w_{n}(i), i = 1, .., n} ⊆ {z_{m}(j), j = 1, .., m}. The shatter coefficient for a data dependent class F is defined as

S_{n/m}(F) = sup_{z_{m}} N_{n}(z_{m}, F).

We begin by citing Gat’s (1999) observation that Vapnik’s basic lemma regarding ghost samples still applies for data dependent classes. Let z_{n} denote the n-sample and z_{n_{2}} the ghost sample. Denote z_{m} = (z_{n}, z_{n_{2}}) with m = n + n_{2}. We write the empirical means

μ̂(f) = μ̂_{1}(f) = \frac{1}{n} ∑_{i=1}^{n} f(z_{n}(i))

and

μ̂_{2}(f) = \frac{1}{m − n} ∑_{i=1}^{m−n} f(z_{n_{2}}(i)).

Lemma 2 (Gat)

P_{Z_{n}} ( sup_{f∈F_{zn}} |μ(f) − μ̂_{1}(f)| > ϵ) ≤ 2P_{Z_{m}} ( sup_{f∈F_{zn}} |μ̂_{2}(f) − μ̂_{1}(f)| > ϵ − \frac{1}{m − n})

Proof Just follow Vapnik’s proof (Vapnik, 1998, page 132) and observe that the relevant n is n_{2} and the data dependency makes no difference.

Now we state and prove our main theorem for data dependent classes.

Theorem 3 For any m > n,

P_{Z_{n}} ( sup_{f∈F_{zn}} |μ(f) − μ̂_{1}(f)| > ϵ) ≤ 2S_{n/m}(F)e^{2ϵ}e^{−( \frac{1}{n} + \frac{1}{m−n})^{−1}ϵ^{2}}.

Proof Gat (1999) proved the version of this theorem that counted the number of functions in {F_{w_{n}}, w_{n} ⊆ z_{m}} when m = 2n. We show this proof can generate bounds in terms of the shatter coefficient for the data dependent class. Consider

P_{Z_{m}} ( sup_{f∈F_{zn}} |μ̂_{2}(f) − μ̂_{1}(f)| > ϵ́)

where ϵ́ = ϵ − \frac{1}{m−n}. Let Σ denote the set of permutations of the integers (1, 2, ..., m) and use the same designation for the set of permutations induced on the m sample z_{m}. Since P_{Z_{m}} is invariant under Σ, for any permutation σ

P_{Z_{m}} ( sup_{f∈F_{zn}} |μ̂_{2}(f) − μ̂_{1}(f)| > ϵ́) = P_{Z_{m}} ( sup_{f∈F_{σ(zm)_{1}}} |μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́)

where σ(z_{m}) = (σ(z_{m})_{1}, σ(z_{m})_{2}) and σ(z_{m})_{1} is of length n.

Place the uniform probability distribution on Σ. It then follows that

P_{Z_{m}} ( sup_{f∈F_{zn}} |μ̂_{2}(f) − μ̂_{1}(f)| > ϵ́) = P_{Z_{m},Σ} ( sup_{f∈F_{σ(zm)_{1}}} |μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́)

= ∫ (P_{Σ|Z_{m}}( sup_{f∈F_{σ(zm)_{1}}} |μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́ | Z_{m})) dP_{Z_{m}}  (1)

but for fixed Z_{m}

P_{Σ|Z_{m}} ( sup_{f∈F_{σ(zm)_{1}}} |μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́ | Z_{m}) ≤

S_{n/m}(F) sup ; f∈⋃_{σ∈Σ} F_{σ(zm)_{1}} P_{Σ|Z_{m}} (|μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́ | Z_{m}) .  (2)

To bound

P_{Σ|Z_{m}} (|μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́ | Z_{m})

we map to the hypergeometric distribution in the following fashion. For f fixed, let l be the number of indices such that f(z_{m}(i)) = 1. For fixed σ let k denote the number of indices i = 1, .., n such that f(σ(z_{m})_{1}(i)) = 1. For each combination of k indices chosen from l and n − k chosen from m − l, there are n!(m − n)! permutations. The number of combinations which obtain k indices from the l and n − k from the m − l is \binom{l}{k}\binom{m−l}{n−k} so the number of corresponding permutations is \binom{l}{k}\binom{m−l}{n−k}n!(m − n)!. Consequently, the fraction of permutations with k ones in the first n indices and the remaining l−k ones in the remaining m − n indices is

\frac{\binom{l}{k}\binom{m−l}{n−k}n!(m − n)!}{m!} = \begin{matrix}\binom{l}{k} & \binom{m−l}{n−k} \\ ( & {m \atop n} & ) \end{matrix}

and so is distributed like the hypergeometric random variable K(n, m, l) of how many defectives are selected when n items are randomly selected without replacement from a population of m items of which l are defective. For each of these permutations

μ̂_{σ(z_{m})_{1}}(f) − μ̂_{σ(z_{m})_{2}}(f) = \frac{k}{n} − \frac{l − k}{m − n} = \frac{m}{n(m − n)}(k − \frac{ln}{m}).

Consequently,

P_{Σ|Z_{m}}(|μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́ | Z_{m}) = P_{K(n,m,l)} (|k − \frac{ln}{m}| > \frac{n(m − n)}{m}ϵ́) .

Applying Serfling’s result (Serfling, 1974) on concentration of sampling without replacement to the hypergeometric distribution

P_{K(n,m,l)} (|\frac{k}{n} − \frac{l}{m}| > t) ≤ e^{− \frac{2nm}{m−n+1} t^{2}}

with t = \frac{m−n}{m} ϵ́ we obtain

P_{Σ|Z_{m}}(|μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́ | Z_{m}) ≤ e^{−2 \frac{n}{m} \frac{(m−n)^{2}}{m−n+1} ϵ́^{2}}.

We use the crude lower bound \frac{1}{m−n+1} ≥ \frac{1}{2} \frac{1}{m−n}, losing almost a factor of 2 in exponent, to obtain the simpler formula

P_{Σ|Z_{m}}(|μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́ | Z_{m}) ≤ e^{−( \frac{1}{n} + \frac{1}{m−n})^{−1}ϵ́^{2}}.

Consequently, from Equation 2 we obtain

P_{Σ|Z_{m}} ( sup_{f∈F_{σ(zm)_{1}}} |μ̂_{σ(z_{m})_{2}}(f) − μ̂_{σ(z_{m})_{1}}(f)| > ϵ́) ≤ S_{n/m}(F)e^{−( \frac{1}{n} + \frac{1}{m−n})^{−1}ϵ́^{2}}  (3)

Substituting ϵ́ = ϵ − \frac{1}{m−n} we bound

−(\frac{1}{n} + \frac{1}{m − n})^{−1}ϵ́^{2} ≤ 2ϵ − (\frac{1}{n} + \frac{1}{m − n})^{−1}ϵ^{2}

so that combining with the bound from Lemma 2 and Equation 1, we obtain

P_{Z_{n}} ( sup_{f∈F_{zn}} |μ(f) − μ̂(f)| > ϵ) ≤ 2S_{n/m}(F)e^{2ϵ}e^{−( \frac{1}{n} + \frac{1}{m−n})^{−1}ϵ^{2}}

and the proof is finished.

Before we proceed, let us mention that the data dependent version of Vapnik and Chervonenkis’ lemma inducing bounds on estimation error from bounds on error deviance (as stated by Devroye et al., 1996) also holds. The proof is the same as the data independent version.

Lemma 4 Let f̂(z_{n}) = arg min_{f∈F_{zn}} μ̂(f) denote the empirical mean minimizer in the data dependent class F_{z_{n}} and let μ^{∗}(z_{n}) = inf_{f∈F_{zn}} μ(f) be the data dependent optimum. Then

μ(f̂(z_{n})) − μ^{∗}(z_{n}) ≤ 2 sup_{f∈F_{zn}} |μ̂(f) − μ(f)|

3. Classification

We now consider classification. Let Z = (X, Y) with Y = {0, 1} where X is a metric space with Borel σ-algebra inducing a σ-algebra on Z in the obvious way. We assume additionally that X is Polish so that Z is also Polish and so Suslin. Again we consider independent samples so all n-sample probability measures will be the product measures. Let the Borel probability measure be decomposed as

μ(f́) = μ_{1}(f́(·, 1))p(1) + μ_{0}(f́(·, 0))p(0)

for two Borel probability measures μ_{1} and μ_{0} where we use the notation p(1) = p(y = 1) and p(0) = p(y = 0) for the probability on Y = {0, 1}. We require that each function correspond to a classifier hypothesis. That is, each function f́: Z → {0, 1} satisfies

f́(x, y) = I_{{f(x)=y}}

for some classifier f : X → {0, 1}. Equivalently f́ must satisfy

f́(x, 1) + f́(x, 0) = 1

and so is determined by some classifier f : X → {0, 1} by f(x) = f́(x, 1). For any class C of classifiers f : X → {0, 1} let Ć be the class of functions defined by f́(x, 1) = f(x) and f́(x, 0) = 1 − f(x). The decomposition of the measure combined with the constraints for classifier hypotheses determines the formula for generalization error

e(f) = μ(1 − f́) = (1 − μ_{1}(f))p(1) + μ_{0}(f)p(0).  (4)

Now we define

e^{∗}(z_{n}) = inf_{f∈F_{zn}} e(f)

to be the optimal generalization error in the data dependent class. Also define

e^{∗}(z_{∞}) = lim sup_{n→∞} e^{∗}(z_{n})

to be its infinite sample limit. Let B denote the Borel measurable sets. Define

e_{B} = inf_{f∈B} e(f)

to be the Bayes error.

4. Data Dependent Classes for Classification

In this section we introduce and analyze some specific data dependent hypothesis classes for classification. The first is a class we call simple linear classifiers, and the second is a family of classes that we refer to collectively as multi-sphere classifiers (see Cannon and Cowen, 2000; Marchette and Priebe, 2001; Priebe, DeVinney, and Marchette, 2001 for related work). In each case we derive bounds on their shatter coefficients and establish hardness results for the computational complexity of empirical risk minimization. Throughout this section we let Z = (X, Y) with X Polish so that Z is also Polish and so Suslin. Also, our data dependent classes Ć are defined through function classes C of functions X → {0, 1} as described in the previous section. With this definition the shatter coefficient for Ć is the same as for C.

4.1 Simple linear classifiers

Here X = ℜ^{d} with metric determined by the usual inner product. Let the data dependent class C_{x_{n}} be the subset of linear classifiers whose orientations are determined by the pairwise differences between samples, that is

C_{x_{n}} = {f, 1 − f : f(x) = H ((x_{n}(i) − x_{n}(j)) · x + b) , i, j ≤ n, b ∈ ℜ}

where H is the heaviside function. The shatter coefficient is determined as follows. Recall that in the determination of the shatter coefficient we need to include a ghost sample.

Consider linear classifiers whose orientations are determined by a single sample pair (x(i), x(j)). The class of sets {x : (x(i) − x(j)) · x + b < 0} is ordered by subset relation as we vary the threshold b and so has VC dimension equal to one (Devroye et al., 1996), and so the number of subsets of the 2n points is at most 2(2n + 1). For any sample of size 2n we find at most \binom{2n}{2} = n(2n − 1) unique sample pairs, so we can bound S_{2n/2n}(C) by 8n^{3} − 2n. Since each function in C_{x_{n}} is in C_{x_{2n}}, S_{n/2n}(C) ≤ S_{2n/2n}(C) ≤ 8n^{3} − 2n. Note that for this simple class the shatter coefficient is independent of dimension. This class also admits tractable learning algorithms in that empirical risk minimization over C_{x_{n}} can be solved in polynomial time. To see this consider the run time of the brute force algorithm which examines all O(n^{2}) sample pairs and determines the optimal threshold for each. Since it takes O(nd + n log n) to determine the threshold for each pair the overall run time is O(n^{3}(d + log n)).

4.2 Multi-sphere classifiers

For the computational considerations we let X = ℜ^{d} with metric determined by the usual inner product. Let z_{n_{1}} be the ordered subset of z_{n} with y = 1 where the ordering is induced from z_{n}, and the random variable n_{1} denotes its size. We define the single sphere data dependent class as

C_{z_{n}} = {f : f(x) = H (r − ∥x − x_{n_{1}}(i)∥) , i ≤ n_{1}, r ∈ ℜ_{+}}

That is, x is assigned the label 1 if it falls in a closed ball B(x_{n_{1}}(i), r) ⊆ X of radius r centered at one of the data samples with label y = 1, and 0 otherwise. Determination of the shatter coefficient parallels the procedure above. The class of sets {B(x, r), r ≥ 0}, is ordered by subset relation and so has V C dimension equal to one, and so the number of subsets of the 2n−1 remaining points (which include the ghost sample) is at most 2n. Now, for any sample of size 2n we have at most 2n unique centers, so we can bound S_{2n/2n}(C) by (2n)^{2}. Since each function in C_{z_{n}} is in C_{z_{2n}}, S_{n/2n}(C) ≤ S_{2n/2n}(C) ≤ (2n)^{2}. Note that once again the shatter coefficient is independent of dimension. In addition, empirical risk minimization over C_{z_{n}} can be solved in polynomial time since the brute force algorithm, which examines all 2n centers and determines the optimal radius for each, has an overall run time of O(n^{2}(d + log n)).

Now consider an extension of C_{z_{n}} to multiple spheres. We define

C_{z_{n}}^{q} = {f : f = ⋃_{i=1}^{q} B (x_{q}(i), r_{i}) , x_{q} ⊆ x_{n_{1}}}

which is the set of functions corresponding to the union of q closed balls of q possibly different radii centered at q of the data points x_{n_{1}}, where q ≤ n. To bound the shatter coefficient for this class recall that the number of dichotomies induced by a single ball placed at one of the data points is at most 2n. Then we rewrite

C_{z_{n}}^{q} = ⋃_{x_{q}⊆x_{n_{1}}} ⨆_{i=1}^{q} B (x_{q}(i), r_{i})

where ⋃ denotes the union of classes of sets and ⨆ denotes the operation of forming unions of sets to form new classes. As shown by Devroye et al. (1996, page 219), the shatter coefficient of A_{1} ⋃ A_{2} is bounded by the sum of the shatter coefficients of A_{1} and A_{2} and the shatter coefficient of A_{1} ⨆ A_{2} is bounded by the product of the shatter coefficients of A_{1} and A_{2}. Consequently, for q balls placed at q points the shattering of 2n points is bounded by (2n)^{q} and for the \binom{2n}{q} choices of subsets of size q from 2n points the shatter coefficient for q balls on 2n points is at most \binom{2n}{q}(2n)^{q} ≤ (2n)^{2q}. Therefore S_{n/2n}(C^{q}) ≤ (2n)^{2q}. Note that the shatter coefficient remains independent of dimension.

We now discuss a family of multi-sphere classifiers which are obtained by varying the data dependency. Specifically we consider variants of the q-sphere class where we vary our specification of the q centers and their radii. The classes we consider include all combinations where

1. the q centers may be any subset of x_{n_{1}}, or

2. the q centers are a pre-determined subset of x_{n_{1}},

and

1. a different radius is chosen for each center, or

2. a single radius (same for all centers) must be chosen, or

3. the radii are pre-determined (i.e. fixed ahead of time).

The simplest case is where both the index set of center points and the radii are predetermined. This class has only one function and so its shatter coefficient is 1 and its computational requirements are trivial.

The next level of sophistication is when q = 1. We have already considered the case where both the center sample index and its radius are variable. The tables below give bounds on the shatter coefficient and computational requirements for empirical risk minimization for all combinations with q = 1.

Shatter Coefficient Bounds q = 1

Radius Dependency

Center Index Dependency Fixed Variable
Fixed  1  2n
Variable  2n  (2n)^{2}

Computation Bounds q = 1

Radius Dependency

Center Index Dependency Fixed  Variable
Fixed O(1) O(dn log n)
Variable  O(dn^{2}) O(n^{2}(d + log n))

The next variant we consider is one where the q > 1 center sample indices are fixed and we allow a single variable radius (the same for each ball). It is easy to show that the shatter coefficient for this variation is bounded by 2n, and the empirical error can be minimized with a brute force algorithm that runs in O(nq(d + log n)) time.

All remaining variants allow either the q > 1 center sample indices to vary or the q > 1 radii to vary. The table below provides a summary of shatter coefficient bounds for these variants.

Shatter Coefficient Bounds q > 1

Radius Dependency

Center Index Dependency Fixed Variable
Fixed  1  (2n)^{q}
Variable  (2n)^{q}  (2n)^{2q}

We now show that any variant that requires q > 1 to be determined algorithmically is NP-Hard. The formal definitions for these problems are stated as prize collecting versions of the class cover problem (Cannon & Cowen, 200).

Definition 5 (PRIZE COLLECTING CLASS COVER: PC-CC) Given an n-sample x_{n} = (x_{n_{0}}, x_{n_{1}}), x_{n}(i) ∈ X, a distance function d : X × X → ℜ^{+}, and a positive integer q ≤ n_{1}. Determine a subset x_{q} ⊆ x_{n_{1}} of size q and a set of radii r_{q}, r_{q}(i) ∈ ℜ^{+}, one for each sample in x_{q} that minimizes the error

e(x_{q}) = |x_{n_{1}} ∩ x̄_{c}| + |x_{n_{0}} ∩ x_{c}|

where x_{c} is the set of points covered by the q balls,

x_{c} = {x_{n}(i) : ∃x_{n_{1}}(j) ∈ x_{q} such that d(x_{n}(i), x_{n_{1}}(j)) ≤ r_{n_{1}}(j)}

and x̄_{c} = x_{n} \ x_{c}.

Definition 6 (SINGLE RADIUS CLASS COVER: SRCC) This problem is the same as PC-CLASS COVER except that every sample in x_{q} is forced to use the same radius, so only a single radius value must be determined.

Definition 7 (FIXED RADIUS CLASS COVER: FRCC) This problem is the same as PC-CLASS COVER except that the radii are fixed, i.e. a fixed set of radii r_{n_{1}}, one for each sample in x_{n_{1}}, is provided as part of the problem instance, and we must determine only x_{q}.

Definition 8 (FIXED CENTER CLASS COVER: FCCC) This problem is the same as PC-CLASS COVER except that the centers are fixed, i.e. x_{q} is provided as part of the problem instance, and we must determine only r_{q}.

The last variant presented involves fixing q > 1 centers and algorithmically determining the corresponding radii. We do not present a hardness proof for this version but conjecture that even this simple variant is hard for q > 1. The following theorem gives hardness results for the first three variants.

Theorem 9 PC-CC, SRCC and FRCC are NP-Hard.

Proof Our proofs are by reduction from K-CENTER (Hochbaum, 1997, Section 9.4.1).

Definition 10 (K-CENTER: KC) Given a weighted graph G = (V, E) with |V | = n, and a positive integer k ≤ n. Let {w_{i,j}} represent the set of shortest path distances between vertices v_{i} and v_{j} in V. Find a subset of vertices S of size k so that the greatest distance among all vertices in V to a nearest vertex in S is minimized. More formally,

min_{S⊂V,|S|=k}{ max_{v_{i}∈V \S} min_{v_{j}∈S} w_{i,j}}.

We begin with the reduction to PC-CC, and then show how the same reduction can be used for both SRCC and FRCC as well.

Notice that the value of the objective function will always be one of \binom{n}{2} possible shortest path distances. We will generate at most \binom{n}{2} instances of PC-CC. First, order the \binom{n}{2} distances w_{i,j}. Let d_{(i)} be the i^{th} smallest distance and let ϵ be half of the smallest nontrivial pairwise difference between the distances,

ϵ = min_{d_{(i)}≠d_{(j)}} \frac{1}{2}|d_{(i)} − d_{(j)}|

Now we generate a copy of the weighted graph G(V, E) and color every vertex blue. Add n red vertices, each with an edge to a corresponding blue vertex that has weight d_{(\binom{n}{2})} + ϵ. Note that each blue vertex now has a red vertex whose shortest path distance is d_{(\binom{n}{2})} + ϵ and no red vertices closer. The shortest path distances for all vertices in this modified graph satisfy the properties of a metric and can thus be embedded as points in a Euclidean space of finite dimension in polynomial time (Young, 1938). These points serve as inputs to the PC-CC problem where we make a one to one correspondence between the blue (red) vertices and the points in x_{n_{1}} (x_{n_{0}}). Now set q = k and solve the PC-CC problem. Observe that this version of PC-CC is trivially solved with zero error.

We repeat the process now using d_{(\binom{n}{2}−1)}. The red vertices are now “one step” closer. This time we have no guarantee of existence of a zero error solution. If the error is zero, then we repeat the process bringing the red nodes another step closer. We continue until we reach a PC-CC solution with nonzero error. As soon as this occurs the blue vertices corresponding to the points x_{q} of the most recent zero error solution provide to an optimal solution to the original K-CENTER instance. Indeed if this were not the case then any superior solution to the K-CENTER instance would lead to a zero error solution for the most current version of PC-CC. If it turns out that all \binom{n}{2} versions of PC-CC have zero error solutions then at least n − k distances must be the same and the latest (final) solution is optimal for the k-center problem.

Hence if we could solve PC-CC in polynomial time, T_{pc−cc}(n_{0} + n_{1}), then we could solve K-CENTER on n vertices in O(n^{2} · T_{s}(n) · T_{e}(n) · T_{pc−cc}(n)) time, where T_{s}(n) is the time required to compute the shortest path distances for the modified graph, and T_{e}(n) is the time required to embed the modified graph into a Euclidean space.

The same reduction can be used to prove hardness for SRCC by noting that at each step, as we move the red vertices closer, the set of optimal solutions (e.g. points and their radii) always includes an equal radius solution. For example at the step where d_{(i)} is used to determine the new edge weights for the modified graph, if there is a zero error solution then there is a zero error solution where the radii for all q blue points are set to d_{(i)} (at this radius each of the q blue points covers as many other blue points as possible without introducing errors). So the reduction works when we substitute SRCC for PC-CC at each step.

The reduction also works when we substitute FRCC for PC-CC. This follows directly from the observation that if there is a zero error solution, then there is a zero error solution whose radii are all d_{(i)}. This means that we can simply set all the radii in r_{n_{1}} to d_{(i)} and solve FRCC (instead of PC-CC).

In summary, we have provided bounds on both the structural and computational complexity for a family of spherical classifiers. However, we have not provided a procedure for selecting the best member from this family. This is the topic of the next section.

5. Structural Risk Minimization

In classification it often not clear what hypothesis space to choose. Vapnik (1998) addressed this problem by considering a sequence of hypothesis spaces large enough to contain a good classifier. The structural risk minimization procedure (Vapnik, 1998) is a method designed to find this good classifier even though classifier complexity of the sequence is large. We now present a structural risk minimization procedure and prove convergence for a sequence of data dependent classifier spaces. Although utilized in the construction of classifiers, we present the analysis in terms of empirical process theory. We consider a sequence F = {F^{q}, q = 1, ....} of data dependent classes F^{q}. The symbol F used here is the same as we used for the data dependent class before. However, now the data dependent classes in the sequence are denoted F^{q} and F is the sequence so there should be no confusion. We say that F is image admissible Suslin if each F^{q} is. For simplicity of presentation we set m = 2n. Let S_{q,n} denote bounds on the shatter coefficients S_{n/2n}(F^{q}). Our method is similar to that presented by Vapnik (1998) (also see Devroye, Györfi, and Lugosi, 1996). Given a training set z_{n} we select a function f̃_{z_{n}}^{q} from every class F_{z_{n}}^{q} which minimizes empirical mean over the class. From these we select the function f_{z_{n}}^{∗} that minimizes over q the complexity penalized function:

μ̃(f̃_{z_{n}}^{q}) = μ̂(f̃_{z_{n}}^{q}) + r(q, n)

where μ̂ is the empirical mean and r(q, n) is the penalty term

r(q, n) = \sqrt{2\frac{log en}{n log n} log(S_{q,n})}

Let

μ_{q}^{∗}(z_{n}) = inf_{f∈F_{zn}^{q}} μ(f)

define the function μ_{q,n}^{∗} and

μ^{∗}(z_{∞}) = inf_{q} lim sup_{n→∞} μ_{q}^{∗}(z_{n})

define the function μ_{∞}^{∗}. If we let the intermediate

μ_{q}^{∗}(z_{∞}) = lim sup_{n→∞} μ_{q}^{∗}(z_{n})

define the function μ_{q}^{∗}, then

μ^{∗}(z_{∞}) = inf_{q} μ_{q}^{∗}(z_{∞}).

μ_{q,n}^{∗} can be extended to a function with the same name on Z_{∞} in the obvious way. In general we make this extension without notice. When we apply this theory to classification we make use of Equation 4 for the generalization error

e(f) = μ(1 − f́) = p(1) + μ_{0}(f)p(0) − μ_{1}(f)p(1)

and the corresponding definitions for e_{q,n}^{∗},e_{∞}^{∗}, e_{q}^{∗}.

Let SE denote the class of subexponential functions on the positive integers. That is g ∈ SE if and only if

∑_{n>0} g(n)e^{−nα} < ∞

for all α > 0. This class includes the polynomials, polynomials with logarithms and even such functions as e^{\frac{n}{log n+1}} . We use the bound from Theorem 3 with m = 2n

P_{Z_{n}}( sup_{f∈F_{zn}^{q}} |μ(f) − μ̂(f)| > ϵ) ≤ 2S_{q,n}e^{2ϵ}e^{− \frac{nϵ^{2}}{2}} .

The proof of the the following structural risk minimization theorem closely resembles a theorem presented by Devroye et al. (1996, Theorem 18.2). However, because of the data dependencies, the conditions of the theorem are somewhat different than usual. Let wp1 denote the terminology “with probability 1”.

Theorem 11 Suppose that F is image admissible Suslin and there exists bounds S_{q,n} for

the shatter coefficients such that ∑_{q} S_{q,n}^{− \frac{1}{log n}} ∈ SE and S_{q,n} ∈ SE for every q. Let f_{z_{n}}^{∗} be determined by the structural risk minimization procedure. Then lim sup_{n→∞} μ(f_{z_{n}}^{∗}) ≤ μ_{∞}^{∗} wp1 .

5.1 Structural assumptions on F

This structural risk theorem was very general and assumed only that F was image admissible Suslin, but assumed nothing about the relationship between F_{n_{1}}^{q_{1}} and F_{n_{2}}^{q_{2}}. Although stronger limit theorems can be made under structural assumptions about F we analyze this question at present only in terms of μ_{∞}^{∗}.

5.1.1 z-increasing F

Definition 12 We say that F is z-increasing if F_{z_{n}}^{q} ⊆ F_{zń}^{q} when z_{n} ⊆ zń for each q.

If F is z-increasing, then lim sup_{n→∞} μ_{q}^{∗}(z_{n}) = inf_{n} μ_{q}^{∗}(z_{n}) and so

μ^{∗}(z_{∞}) = inf_{q} inf_{n} μ_{q}^{∗}(z_{n}) = inf_{q} inf_{n} inf_{f∈F_{zn}^{q}} μ(f)

but since generally inf_{w} inf_{v} = inf_{w,v} we obtain that

μ^{∗}(z_{∞}) = inf_{f∈F} μ(f)

and since μ(f_{z_{n}}^{∗}) ≥ inf_{f∈F} μ(f) = μ^{∗}(z_{∞}) we obtain the following much stronger theorem.

Theorem 13 Suppose the data dependent sequence F is z-increasing and image admissible

Suslin and there exists bounds S_{q,n} for the shatter coefficients such that ∑_{q} S_{q,n}^{− \frac{1}{log n}} ∈ SE and S_{q,n} ∈ SE for every q. Let f_{z_{n}}^{∗} be determined by the structural risk minimization procedure. Then μ(f_{z_{n}}^{∗}) ⟶_{n→∞} inf_{f∈F} μ(f) wp1 .

An interesting thing also happens to the shatter coefficients.

Lemma 14 Suppose the data dependent class G is z-increasing. Then

N_{n}(z_{m}, G) ≤ Nń(z_{m}, G)

and

S_{n/m}(G) ≤ S_{ń/m}(G)

for all n ≤ ń ≤ m. In particular,

S_{n/m}(G) ≤ S_{m/m}(G).

Proof The z-increasing assumption G_{z_{n}} ⊆ G_{zń} when z_{n} ⊆ zń implies that

N_{n}(z_{m}, G) = |{{z_{m}(1), ..., z_{m}(m)} ∩ I_{f} : f ∈ G_{w_{n}}, w_{n} ⊂ z_{m}}|
≤ |{{z_{m}(1), ..., z_{m}(m)} ∩ I_{f} : f ∈ G_{zń}, zń ⊂ z_{m}}| = Nń(z_{m}, G)

and taking the supremum over z_{m} finishes the proof.

We define the data dependent V C dimension of order m as

V C_{m}(G) = max{n : ∃z_{n} ⊆ z_{m} : G_{z_{m}}shatters z_{n}}.

In words V C_{m}(G) is the size of the largest subset of some m points which is shattered by the data dependent class on those m points. The Sauer lemma (Devroye et al., 1996) can be directly applied. In particular

S_{n/m}(G) ≤ S_{m/m}(G) ≤ m^{V C_{m}(G)} + 1.

5.1.2 Symmetric F

We say that F is z-symmetric if

F_{z_{n}}^{q} = F_{σ(z_{n})}^{q}

for every permutation σ of the n points. In this section we will show that when F is zsymmetric, μ_{∞}^{∗} is measurable and constant wp1 . As we mentioned in the introduction, such measurability considerations are appropriate through most of this work, but feel these technicalities would obscure the presentation. However, the following result depends so critically on measurability assumptions that we include these technicalities here. We now assume that F is z-symmetric. Before we state the next theorem we need to introduce some terminology. A universally measurable set in a measurable space is a set M which is measurable for the completion of every measure. In particular, for each measure ν their exists measurable sets

A ⊂ M ⊂ B

such that ν(A) = ν(B). Consequently, we can and will be a little sloppy and say ν(M) = ν(A) = ν(B) for the universally measurable set M. A universally measurable function between measurable spaces is one such that the preimage of a measurable set is a universally measurable set. For a specific measure, we can consider universally measurable sets as measurable for the completion of the measure (Ash, 1972). Indeed not only do they form a σ-algebra, but it is elementary to show that if {M_{n}} is a countable collection of universally measurable sets such that

A_{n} ⊂ M_{n} ⊂ B_{n}

with ν(A_{n}) = ν(B_{n}) for each n, then ⋃_{n} M_{n} and ⋂_{n} M_{n} are both universally measurable,

⋃_{n} A_{n} ⊆ ⋃_{n} M_{n} ⊆ ⋃_{n} B_{n},

⋂_{n} A_{n} ⊆ ⋂_{n} M_{n} ⊆ ⋂_{n} B_{n},

ν(⋃_{n} A_{n}) = ν(⋃_{n} B_{n}), and ν(⋂_{n} A_{n}) = ν(⋂_{n} B_{n}).

Theorem 15 Suppose that Z is a Suslin space with Borel measure μ. Suppose that the data dependent sequence F is z-symmetric and image admissible Suslin. Then μ_{∞}^{∗} is universally measurable and μ_{∞}^{∗} = constant wp1 .

Proof Since F is image admissible Suslin, for fixed q, Ξ_{n}^{q} is measurable. Since Ξ_{n}^{q} is positive Fubini’s theorem tells us that

μ (f(T_{q}(y_{n})_{z_{n}})) = μ (Ξ^{q}(y_{n}, z_{n}, ·))

is jointly measurable. By the theorem of Sainte-Beuve as presented by Dudley (1999)

μ_{q}^{∗}(z_{n}) = inf_{f∈F_{zn}} μ(f) = inf_{y_{n}∈Y_{n}} μ (f(T_{q}(y_{n})_{z_{n}}))

is universally measurable on Z_{n} and extends naturally to a universally measurable function on Z_{∞}. We work on Z_{∞} for the rest of this proof. In particular, for every c the set {μ_{q,n}^{∗} ≥ c} is universally measurable. Consequently, there exists measurable sets

A_{q,n} ⊂ {μ_{q,n}^{∗} ≥ c} ⊂ B_{q,n}

such that P_{Z_{∞}}(A_{q,n}) = P_{Z_{∞}}(B_{q,n}). Since F is z-symmetric {μ_{q,n}^{∗} ≥ c} is invariant under permutation of the first n positions in Z_{∞}. If we let S_{n}^{+} denote the upper symmetric envelope of a set (the union over all permutations of the first n position indices) and S_{n}^{−} the lower symmetric envelope it is clear from the fact that universally measurable sets behave like measurable sets with respect to unions and intersections that A_{q,n} = S_{n}^{+}(A_{q,n}) and B_{q,n} = S^{−}(B_{q,n}) are measurable, symmetric in there first n positions, and

A_{q,n} ⊆ A_{q,n} ⊆ {μ_{q,n}^{∗} ≥ c} ⊆ B_{q,n} ⊆ B_{q,n}.

Consequently P_{Z_{∞}}(A_{q,n}) = P_{Z_{∞}}(B_{q,n}). Now consider

μ^{∗}(z_{∞}) = inf_{q} lim sup_{n→∞} μ_{q}^{∗}(z_{n}) = inf_{q} inf_{N} sup_{n≥N} μ_{q}^{∗}(z_{n})

so that

{μ_{∞}^{∗} ≥ c} = ⋂_{q} ⋂_{N} ⋃_{n≥N}{μ_{q,n}^{∗} ≥ c}.

It is clearly universally measurable and if we define A_{∞} = ⋂_{q} ⋂_{N} ⋃_{n≥N} A_{q,n} and B_{∞} = ⋂_{q} ⋂_{N} ⋃_{n≥N} B_{q,n},

A_{∞} ⊆ {μ_{∞}^{∗} ≥ c} ⊆ B_{∞}

and

P_{Z_{∞}}(A_{∞}) = P_{Z_{∞}}(B_{∞}).

Since A_{q,n} is symmetric in its first n components, ⋃_{n≥N} A_{q,n} is symmetric in the first N. Consequently, ⋂_{N} ⋃_{n≥N} A_{q,n} is symmetric for any finite permutation and the same is true for A_{∞}. This argument works just as well for B_{∞}. Therefore both A_{∞} and B_{∞} are measurable and symmetric. By the Hewitt-Savage Zero-One law (Shiryaev, 1980)

P_{Z_{∞}}(A_{∞}) = P_{Z_{∞}}(B_{∞}) = 0 or 1

and the proof is finished.

Consequently, when F is both z-symmetric and z-increasing we obtain that μ(f_{z_{n}}^{∗}) converges to μ_{∞}^{∗} = inf_{f∈F} μ(f) wp1 and that μ_{∞}^{∗} = inf_{f∈F} μ(f) = constant wp1 .

Note that in the course of proving this theorem we have shown that for a fixed symmetric image admissible Suslin data dependent class, the limit μ_{∞}^{∗} = lim sup_{n→∞} μ^{∗}(z_{n}) is constant wp1 .

5.2 Structural risk minimization for multi-sphere classifiers

When the structural risk minimization theorem is applied it would be very nice to be able to characterize μ_{∞}^{∗}. For example, when is μ_{∞}^{∗} the minimum value over the unconstrained sequence UF = ⋃_{q,n,z_{n}∈Z_{n}} F_{z_{n}}^{q} wp1 ? We can provide no general facts in this regard at present but in the this section we show that this is true for multi-sphere classifiers. We first show that e_{∞}^{∗} is the Bayes optimal and then show we can apply the Structural Risk Minimization Theorem 13. The analysis below works for closed or open balls, balls all of the same radii, and when the complements of the union of the balls is included in the class of functions.

Theorem 16 Consider the data dependent multi-sphere classifiers on a Polish space X with Borel measure μ on Z = (X, {0, 1}). Let e_{B} denote the Bayes error. Let the structural risk minimization procedure be applied with S_{q,n} = (2n)^{2q} to produce the classifier f_{z_{n}}^{∗}. Then

e(f_{z_{n}}^{∗}) ⟶_{n→∞} e_{B} wp1 .

Proof

To prove this theorem we have to do two things. The first is to show that e_{∞}^{∗} is universally measurable and that e_{∞}^{∗} = e_{B} wp1 . The second is to show that we can apply the Structural Risk Minimization Theorem 13. We now proceed with the first.

Lemma 17 Consider a Borel measurable random variable Z = (X, {0, 1}) with X Polish and Borel measure μ. Then for the data dependent multi-sphere classifiers, e_{∞}^{∗} is universally measurable and e_{∞}^{∗} = e_{B} wp1 .

Proof We now show that for the multi-sphere classifiers that the evaluation function Ξ^{q} is jointly measurable for each q. The data dependent classes Ć of functions on Z are the data dependent classes ⋃_{q≤n} Ć^{q} where C_{x_{n}}^{q} is the set of functions on X which are one on the union of a set of q balls placed on the x component of the data samples. It is clear that Ć is both z-symmetric and z-increasing. Consider the class B_{x_{q}} for a fixed set of q points x_{q}. We define the parameter space of radii W_{q} = ℜ_{+}^{q} and the parameterization that T_{x_{q}}(w_{q})(z) = max_{1≤i≤q} I_{|x−x_{q}(i)|≤w_{q}(i)} where I is the indicator function. For each i the set I_{|x−x_{q}(i)|≤w_{q}(i)} is closed and so measurable in W_{q}, Z_{q}, X. Consequently the evaluation function

Ξ^{q}(w_{q}, z_{q}, X) = T_{x_{q}}(w_{q})(z) = max_{1≤i≤q} I_{|x−x_{q}(i)|≤w_{q}(i)}

is jointly measurable. Since the measurable sets are closed under complement, the evaluation function for the class corresponding to the functions on Z is measurable on W_{q}, Z^{q}, Z. Consequently, the conditions of Theorem 15 are satisfied and so e_{∞}^{∗} is universally measurable and e_{∞}^{∗} is constant wp1 . What is left is to show that this constant is e_{B}.

To this end note that

e_{B} ≤ e_{q}^{∗}(z_{n})

so that

e_{B} ≤ e^{∗}(z_{∞}).

Now we prove that e_{∞}^{∗} ≤ e_{B} wp1 which will then finish the proof. The idea is as follows. We keep an eye on the generalization error (Equation 4) e(f) = p(1) + μ_{0}(f)p(0) − μ_{1}(f)p(1) and show that for any f we can use a data dependent placement of balls to form a classifier f^{∗} such that μ_{0}(f^{∗}) is never much larger than μ_{0}(f) while at the same time show that for large enough n with high probability μ_{1}(f^{∗}) is not much smaller than μ_{1}(f). For the first part we utilize the continuity of the measure of a decreasing family of measurable sets and for the second the fact that the measure of a measurable set on a Polish space can be approximated from below by the measure of compact measurable sets. This compactness allows us to show that with high probability the randomly placed set of balls will have μ_{1} measure not too much smaller than that of f. Consequently from the generalization error formula we see that with high probability we can control the increase in generalization error over the generalization error of any measurable set through a random placement of balls. We now carry out the details.

Let ϵ_{1} > 0. Then there exists a measurable f_{ϵ_{1}} such that

e(f_{ϵ_{1}}) ≤ e_{B} + ϵ_{1}.  (5)

Since X is Polish it follows (see e.g. Ash, 1972) that f_{ϵ_{1}} can be approximated from below by compact sets. That is, given any ϵ_{2} > 0 there is a compact h_{ϵ_{2}} ≤ f_{ϵ_{1}} such that

μ_{1}(f_{ϵ_{1}}) − ϵ_{2} ≤ μ_{1}(h_{ϵ_{2}}) ≤ μ_{1}(f_{ϵ_{1}}).  (6)

Since it is compact, for any covering of h_{ϵ_{2}} of open balls B_{i}^{ϵ_{3}} of radius ϵ_{3} there is a finite subcovering. From this subcovering choose the positive measure subcovering such that μ_{1}(B_{i}^{ϵ_{3}}) > 0 for each ball in the subcover. Note that the positive measure subcover is not really a covering. However μ_{1}(⋃ B_{i}^{ϵ_{3}}) ≥ μ_{1}(h_{ϵ_{2}}) for the positive measure subcover. Consider the classifier f_{z_{n}}^{2ϵ_{3}} ∈ F_{z_{n}} which places closed balls B̄^{2ϵ_{3}} of radius 2ϵ_{3} at each of the data points which satisfy h_{ϵ_{2}}(x) = 1. The triangle inequality implies that

B̄^{2ϵ_{3}}(x) ⊃ B^{ϵ_{3}}

whenever x ∈ B^{ϵ_{3}} so that if the sample z_{n} has at least one point in every ball B_{i}^{ϵ_{3}} of the positive measure subcover, then f_{z_{n}}^{2ϵ_{3}} ≥ h_{ϵ_{2}} and so

μ_{1}(f_{z_{n}}^{2ϵ_{3}}) ≥ μ_{1}(h_{ϵ_{2}}).  (7)

From Equation 6 we see that for ϵ_{2} < μ_{1}(f_{ϵ_{1}}), μ_{1}(h_{ϵ_{2}}) > 0 and since the positive measure subcover is finite we know then for large enough n with high probability there will be at least one point in every ball. That is, given an ϵ_{4} > 0 there exists an M(ϵ_{4}) such that

P_{Z_{∞}}(μ_{1}(f_{z_{n}}^{2ϵ_{3}}) ≥ μ_{1}(h_{ϵ_{2}})) ≥ 1 − ϵ_{4}

for all n ≥ M(ϵ_{4}). Now f_{z_{n}}^{2ϵ_{3}} ≤ N_{2ϵ_{3}}(h_{ϵ_{2}}) where N_{ϵ}(A) is the set of all points at distance less that or equal to ϵ from the set A. Consequently, μ_{0}(f_{z_{n}}^{2ϵ_{3}}) ≤ μ_{0}(N_{2ϵ_{3}}(h_{ϵ_{2}})) and so μ_{0}(f_{z_{n}}^{2ϵ_{3}}) ≤ μ_{0}(N_{2ϵ_{3}}(f_{ϵ_{1}})). Since in addition, μ_{1}(h_{ϵ_{2}}) ≥ μ_{1}(f_{ϵ_{1}}) − ϵ_{2}, if we put this together in the generalization formula we obtain

P_{Z_{∞}}(e(f_{z_{n}}^{2ϵ_{3}}) ≤ e(f_{ϵ_{1}}) + p(0)(μ_{0}(N_{2ϵ_{3}}(h_{ϵ_{2}})) − μ_{0}(h_{ϵ_{2}}))

+ p(0)(μ_{0}(h_{ϵ_{2}}) − μ_{0}(f_{ϵ_{1}})) + p(1)(ϵ_{2})) ≥ 1 − ϵ_{4}.

Since e(f_{ϵ_{1}}) ≤ e_{B} + ϵ_{1} and h_{ϵ_{2}} ≤ f_{ϵ_{1}} we further obtain

P_{Z_{∞}}(e(f_{z_{n}}^{2ϵ_{3}}) ≤ e_{B} + ϵ_{1} + p(0)(μ_{0}(N_{2ϵ_{3}}(h_{ϵ_{2}})) − μ_{0}(h_{ϵ_{2}})) + p(1)(ϵ_{2})) ≥ 1 − ϵ_{4}.

Since e^{∗}(z_{n}) ≤ e(f_{z_{n}}^{2ϵ_{3}}) we obtain

P_{Z_{∞}}(e_{n}^{∗} ≤ e_{B} + ϵ_{1} + p(0)(μ_{0}(N_{2ϵ_{3}}(h_{ϵ_{2}})) − μ_{0}(h_{ϵ_{2}})) + p(1)(ϵ_{2})) ≥ 1 − ϵ_{4}

where, as before, since we know that e_{n} is universally measurable the probability statement is for the probability of the two measurable sets that trap the event. The proof of Theorem 15 showed that the limit of a decreasing sequence of universally measurable sets was universally measurable and that the probability of the limit is the limit of the sequence of probabilities. Consequently,

P_{Z_{∞}}(e_{∞}^{∗} ≤ e_{B} + ϵ_{1} + p(0)(μ_{0}(N_{2ϵ_{3}}(h_{ϵ_{2}})) − μ_{0}(h_{ϵ_{2}})) + p(1)(ϵ_{2})) = 1.

Since a metric space is Hausdorff, the compact set h_{ϵ_{2}} is closed and so the μ_{0}(N_{2ϵ_{3}}(h_{ϵ_{2}})) converges to μ_{0}(h_{ϵ_{2}}) as ϵ_{3} goes to zero. Consequently we can choose ϵ_{3} small enough so that

P_{Z_{∞}}(e_{∞}^{∗} ≤ e_{B} + ϵ_{1} + ϵ_{2}) = 1.

Letting ϵ_{2} and ϵ_{1} go to zero, we obtain

P_{Z_{∞}}(e_{∞}^{∗} ≤ e_{B}) = 1

and the proof is finished.

We have already shown Ć to be image admissible Suslin and have observed that it is also both z-symmetric and z-increasing. From Theorems 13,15, and Lemma 17 all that is left is to show that the bound on the shatter coefficient S_{q,n} satisfies the conditions of Theorem 13. In Section 4.2 we showed that S_{n/2n}(Ć^{q}) ≤ (2n)^{2q}. Thus, a direct calculation with S_{q,n} = (2n)^{2q} shows that the conditions of Theorem 13 are satisfied. We note that these shattering bounds are dimension independent, whereas if the balls could be located anywhere this would not be the case.

6. A framework for classification

The empirical process results in the preceding sections form the basis of a new framework to analyze the performance of statistical learning paradigms. In this framework classifier design is decomposed into two components; the first component is the restriction to the data dependent hypothesis class and the second is empirical risk minimization within that class. Analysis within this framework involves the the study of the decomposition induced on both error and computation. There are several goals we might hope to accomplish with this framework: tighter performance bounds for existing learning paradigms, simpler (or more elegant) proofs, greater flexibility in the analysis, and the discovery of new mechanisms for controlling error and/or computation (which may lead to new learning paradigms). In this section we discuss progress along these fronts using the VC framework as a benchmark for comparison. Specifically, we make comparisons between error bounds for traditional classes C, and their data dependent counterparts C, where the data dependency is introduced in different ways. A natural way of defining a data dependent class is to impose a constraint on a traditional class C to obtain C_{z_{n}}. If this is not the case we define C = ∪_{z_{n}}C_{z_{n}} as the traditional hypothesis class.

We now examine the structure of the induced error decomposition. It is common to break the generalization error into two components, approximation error and estimation error, which are defined as follows. The approximation error for C is

A = inf_{f∈C} e(f) − e_{B}

and the estimation error is

E = e(f̂) − inf_{f∈C} e(f)

where f̂ ∈ C minimizes the empirical error.

The approximation error for the data dependent class C is

A_{D} = inf_{f∈C_{zn}} e(f) − e_{B}

and the estimation error is

E_{D} = e(f̃) − inf_{f∈C_{zn}} e(f),

where f̃ ∈ C_{z_{n}} minimizes the empirical error. The data dependent approximation error A_{D} splits into

A_{D} = A + E_{DD}

where the data dependency error is

E_{DD} = inf_{f∈C_{zn}} e(f) − inf_{f∈C} e(f).

Consequently we see the increase in approximation error due to data dependency. The data dependent estimation error splits into

E_{D} = E − E_{DD} + e(f̃) − e(f̂)

giving

A_{D} + E_{D} = A + E + e(f̃) − e(f̂).

The right hand side shows the possible benefits of data dependent learning which we analyze through the terms on the left hand side.

Analysis of the data dependent approximation error is similar to that for traditional classifiers, except for the data dependency error term. Our treatment of this random variable has just begun. We have shown that its infinite sample limit is constant when the data dependency is symmetric in its dependence on the n-sample. Although we have provided no general conditions on the data dependency that allow computation of this constant, we have shown that it is zero when we employ the structural risk minimization over multisphere classifiers as described in Section 5.2. In this case we have also shown that the infinite sample limit of the data dependent approximation error is zero.

In both the traditional and data dependent theory estimation error is controlled in terms of the shatter coefficient. While the traditional theory uses the Sauer lemma to provide a simple bound for the shatter coefficient in terms of the VC dimension (Devroye et al., 1996) we have discovered no such simplification in the data dependent case. Indeed, we have not yet found a way to bound the shatter coefficient in terms of general characteristics of the data dependent class. In fact we suspect incorporation of the expectation process in the shatter bounds will become important. Such an approach leads to problems in the field of probabilistic geometry (Ambartzumian, 1990). However, there are few distribution independent results in this field, the most notable exception being the result of Rogers (1978) concerning the probability that the convex hulls of two samples do not intersect. Although relevant, we have been unable to extend it to more than two dimensions.

We argue that the change in shatter coefficient due to data dependency may not always be significant. Let C be a finite VC class and let the corresponding data dependent class be the subset of C that achieves the minimum empirical error on the n-sample,

C_{z_{n}} = {f̂: f̂ = arg min_{f∈C} ê(f)}

Since C_{z_{n}} ⊆ C it is clear that S_{n/2n}(C) is less than or equal to the shatter coefficient S(n, C) of C, but the question is whether S_{n/2n}(C) is sufficiently smaller (uniformly) to guarantee a reduction in estimation error. The existence of lower bounds on the generalization error for empirical error minimization (Devroye et al., 1996; Vapnik, 1998) that closely match the upper bounds with which we wish to compare suggest not.

We now discuss examples where the improvement is significant. We begin by considering the sphere classifiers where the multi-sphere class is restricted to a single sphere. The traditional class C, whose center and radius are unrestricted, can be represented as a generalized linear classifier with VC dimension ≤ d+2 (Cover, 1965) (where d is the dimension of the sample space) and so has shatter coefficient S(n, C) ≤ n^{d+2}. Forcing the sphere to be centered at a data point represents a clear restriction on the function class. Note that traditional VC theory accounts for the reduction in complexity that results from placing the center at any fixed location. Indeed, in this case S(n, C) ≤ n, but the center location must be chosen before we see the data. On the other hand, a data dependent framework like the one in this paper is required if we wish to account for the reduction in complexity that results from centering the sphere at a data point. We have shown that S_{n/2n}(C) ≤ (2n)^{2} which demonstrates that the complexity reduction is manifested in a shattering bound that is independent of dimension. While this class restriction may give tighter control on the estimation error, it is likely to increase the approximation error. However, the dimension independent nature of the estimation error allows us to employ methods for reducing approximation error that were not previously available to us. For example we can map to a higher dimensional space and implement the single sphere classifier there (in much the same way we do with support vector machines). This can be accomplished in a computationally efficient way through the use of a kernel to compute distances (Schölkopf, 2001). Finally we note that forcing the sphere to be centered at a data sample gives rise to a significant reduction in the computational requirements for learning. Computing the optimal position and radius of a single ball is NP-Hard (Johnson & Preparata, 1978), but determining the optimal center sample and its radius can be accomplished in (low order) polynomial time (e.g. the brute force algorithm runs in O(dn^{2} log n) time). In summary, the data dependent framework has allowed us to quantify the reduction in class complexity obtained by forcing the ball to be centered at a data point, provided dimension independent error bounds, and consequently led us to consider a new learning paradigm that is computationally tractable. Similar conclusions can be drawn for the set of simple linear classifiers introduced in Section 4.1.

It is possible that the significant decrease in estimation error in these examples is countered by a large increase in approximation error. However, we can reduce the approximation error substantially by using multiple balls (or linear classifiers). For example we consider variations of the q-sphere classifiers introduced in Section 4.2. Theorem 16 tells us that under very general conditions we can drive the approximation (and estimation) error to zero asymptotically (wp1 ). In practice, where q and n are finite, since the estimation error bounds remain independent of dimension, we can combine the technique of mapping to a higher dimension through a kernel with multiple balls to help reduce approximation error. While this is an attractive idea, computational requirements may limit its utility. Theorem 9 states that the problem of finding the best q out of n balls and their radii is NP-Hard 1. Consequently it may be beneficial to consider variations of the data dependent class C_{z_{n}}^{q} that allow us to trade approximation and/or estimation error for computational resources.

For example suppose we restrict C_{z_{n}}^{q} by either fixing the radii or fixing the subset of the samples where the balls are centered. These restrictions lead to a natural reduction in the shatter coefficient for the corresponding data dependent class as shown is Section 4.2. Note however, that when we fix the subset where the balls are centered symmetry is violated and the infinite sample limit of the data dependent optimal generalization error may not be constant (see the proof of Theorem 15). While these variations may remain NP-Hard(see Section 4.2) it is possible that they admit a polynomial time approximation that is acceptable for use in practice. They may also be solved by an algorithm whose expected (or typical) run time is polynomial.

Finally, we obtain a computationally tractable variant of this problem by fixing the q samples where the balls are centered and employ a single radius (the same for each ball) that is chosen to minimize the empirical error.

In summary, we have introduced a new framework which, although incomplete, has demonstrated its utility by allowing us to more thoroughly quantify the trade-offs between performance and computational complexity, and has lead to the discovery of new families of classifiers with dimension independent performance bounds and efficient learning procedures.

1. Note that since there are at most \binom{n}{q} = O(n^{q}) choices for the center points, and for each of these no

more than n^{q} choices for the radii, the problem is polynomial for fixed q. Even so, it is not practical for

q greater than about 3.

Acknowledgments

We would like to thank Leonid Gurvits for a very helpful conversation. Clint Scovel gratefully acknowledges support from the Los Alamos DOE Program in Applied Mathematics. Adam Cannon gratefully acknowledges support from Los Alamos National Laboratory.

References

R.V. Ambartzumian. Factorization Calculus and Geometric Probability. Cambridge University Press, Cambridge, 1990.

R.B. Ash. Real Analysis and Probability. Academic Press, New York, 1972.

P.L. Bartlett, S. Boucheron, and G. Lugosi. Model selection and error estimation. preprint, 2000. (A shorter version of this paper was apparently presented at COLT 2000.).

S. Boucheron, G. Lugosi, and P. Massart. A sharp inequality with applications. Random Structures and Algorithms, 16:277–292, 2000.

K. Buescher and P. Kumar. Learning by canonical smooth estimation, part ii: Learning and choice of model complexity. IEEE Transactions on Automatic Control, 41:557–569, 1996.

A.H. Cannon and L.J. Cowen. Approximation algorithms for the class cover problem. In Proceedings of the 6th International Symposium on Mathematics and Artificial Intelligence, 2000.

C. Cortes and V. Vapnik. Support-vector networks. Machine Learning, 20:273–297, 1995.

T. Cover. Geometrical and statistical properties of systems of linear inequalities with applications in pattern recognition. IEEE Transactions on Electronic Computers, 14:326–334, 1965.

N. Cristianini and J. Shawe-Taylor. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press, Cambridge, 2000.

L. Devroye. Automatic pattern recognition: A study of the probability of error. IEEE Transactions on Pattern Recognition and Machine Intelligence, 10(4):530–543, 1988.

L. Devroye, L. Györfi, and G. Lugosi. A Probabilistic Theory of Pattern Recognition. Springer-Verlag, 1996.

R.M. Dudley. Uniform Central Limit Theorems. Cambridge University Press, New York, 1999.

Y. Freund. Self bounding learning algorithms. In COLT; Proceedings of the Workshop on Computational Learning Theory. Morgan Kaufmann, 1998.

Y. Gat. A bound concerning the generalization ability of a certain class of learning algorithms. Technical Report 548, University of California, Berkeley, 1999.

Dorit S. Hochbaum. Approximation Algorithms for NP-Hard Problems. PWS Publishing Company, 1997.

D. Hush and C. Scovel. On the vc dimension of bounded margin classifiers. Machine Learning, 45:33–44, 2001.

D.S. Johnson and F.P. Preparata. The densest hemisphere problem. Theoretical Computer Science, 6:93–107, 1978.

V.I. Koltchinskii. Rademacher penalties and structural risk minimization. IEEE Transactions on Information Theory, 47(5):1902–1914, 2001.

V.I. Koltchinskii, C.T. Abdallah, M. Ariola, P. Dorato, and D. Panchenko. Improved sample complexity estimates for statistical learning control of uncertain systems. IEEE Transactions on Automatic Control, 45(12):2383–2388, 2000.

D.J. Marchette and C.E. Priebe. Characterizing the scale dimension of a high dimensional classification problem. Pattern Recognition. forthcoming.

C.E. Priebe, J.G. DeVinney, and D.J. Marchette. On the distribution of the domination number for random class cover catch digraphs. Statistics and Probability Letters, 55(3): 239–246, 2001.

L.C.G. Rogers. The probability that two samples in the plane have disjoint convex hulls. Journal of Applied Probability, 15:790–802, 1978.

B. Schölkopf. The kernel trick for distances. Advances in Neural Information Processing Systems, 13:301–307, 2001. Editors: T.K. Leen, T.G. Dietterich, and V. Tresp.

R.J. Serfling. Probability inequalities for the sum in sampling without replacement. Annals of Statistics, 2(1):39–48, 1974.

J. Shawe-Taylor, P.L. Bartlett, R.C. Williamson, and M. Anthony. Structural risk minimization over data-dependent hierarchies. IEEE Transactions on Information Theory, 44(5):1926–1940, 1998. Also appeared in NeuroCOLT Technical Report, NC-TR-96-053, 1996.

J. Shawe-Taylor and N. Cristianini. On the generalization of soft margin algorithms. Technical Report NC2-TR-2000-082, NeuroCOLT2 Technical Report Series, 2000.

A.N. Shiryaev. Probability. Springer-Verlag, New York, 1980.

V.N. Vapnik. Statistical Learning Theory. John Wiley and Sons, Inc., New York, 1998.

G. Young and A.S. Householder. Discussion of a set of points in terms of their mutual distances. Psychometrika, 3:19–22, 1938.