Hi,

Can anyone familiar with the book 'A Probabilistic Theory of Pattern Recognition' or the theory described help me out?

See quote from chapter 12, 'Vapnik-Chervonenkis Theory', of 'A Probabilistic Theory of Pattern Recognition' below. I'm not following the geometric setup outlined there.

Some specific questions:

The hyperrectangle referred to is as in http://en.wikipedia.org/wiki/Hyperrectangle, right?

Does $\phi \in C$ correspond to hyperrectangles of arbitrary dimension?

When the text says "assign the smallest hyperrectangle containing these points", I assume it means both in the sense of smallest dimension as well as size. I'm not sure whether this means the $\phi_i$ are of fixed dimension. I think so.

However, my main source of perplexity is the sentence beginning "Clearly, for each $\phi$..." and ending "on the boundary of the hyperrectangle". I've no idea why this would be true.

There is a similar setup earlier in the book, Section 4.5, but this talks about hyperplanes, and is easier to follow.

No doubt I'm misreading or something. Clarifications appreciated.

```
Regards, Faheem.
```

(Some background to the extract that follows.)

In what follows, d is just a fixed integer. I guess it represents the dimension.

Suppose you have a classifier

$$ \phi: \mathbb{R}^d \longrightarrow \{0, 1\}$$

and $n$ ordered pairs $(X_i, Y_i)$, where $X_i \in \mathbb{R}^d$ are the data values, and $Y_i\in \{0,1\}$ are the correct classifications of the $X_i$. Then the empirical error (or risk) of $\phi$ is

$$ \hat{L}_n(\phi) = \frac{1}{n} \sum_{i=1}^n I_{\{\phi(X_i)\neq Y_i\}} $$

that is, the number of errors made by the classifier is counted and normalized.

From pg 191 of 'A Probabilistic Theory of Pattern Recognition' by Devroye et al, chapter 12, 'Vapnik-Chervonenkis Theory'.

Let $C$ be the class of classifiers assigning 1 to those $x$ contained in a closed hyperrectangle and 0 to all other points, Then a classifier minimizing the empirical error $\hat{L}_n(\phi)$ over all $\phi \in C$ may be obtained by the following algorithm: to each 2d-tuple $(X_{i_1}, X_{i_{2d}})$ of points from $X_1,\dots, X_n$, assign the smallest hyperrectangle containing these points. If we assume that $X$ has a density, then the points $X_1,\dots, X_n$ are in general position with probability one. This way we obtain at most ${n \choose 2d}$ sets. Let $\phi_i$ correspond to the $i$-th such hyperrectangle, that is, the one assigning 1 to those $x$ contained in the hyperrectangle, and 0 to other points. Clearly, for each $\phi \in C$, there exists a $\phi_i$, i = 1, ${n \choose 2d}$, such that

$$\phi(X_j) = \phi_i(X_j)$$

for all $X_k$, except possibly for those on the boundary of the hyperrectangle. Since the points are in general position, there are at most $2d$ such points. Therefore, if we select a classifier $\hat{\phi}$ among $\phi_1, \phi_{{n \choose 2d}}$ to minimize the empirical error, then it approximately minimized the empirical error over the whole class $C$ as well.