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.



A question about Chapter 12 (Vapnik-Chervonenkis Theory) of 'A Probabilistic Theory of Pattern Recognition'
Yes, a hyperrectangle is a generalisation of rectangle to higher dimensions. Here the data is given by points in $\mathbb{R}^d$, so the hyperrectangles are all of that dimension. As with all such algorithms you need to find a way to get a handle on the set of classifiers, so rather than the infinite class of all hyperrectangles of dimension $d$, the choice will be from the $n \choose 2 d$ hyperrectangles of dimension $d$, each of which is the smallest for some choice of $2 d$ of the data points.


For example, if the data consisted of 1000 points in $\mathbb{R}^2$, rather then the infinite class of all rectangles, we confine ourselves to the $1000 \choose 4$ rectangles which minimally contain a subset of 4 of the data points.


One task then is to show that the best of this finite set is almost as good as the best of all the hyperrectangles -- good in the sense that were the data points each labelled $+$ or $-$, the $+$s would be best separated from the $-$s. The argument claims that for each hyperrectangle there will be one from the finite set agreeing with it except for a small number of points on the boundary equal to the number of faces of the hyperrectangles. In the example above, it says that for any rectangle, there is one in the set of $1000 \choose 4$ which encloses exactly the same points, except possibly for 4 on the boundary. Not completely obvious, I agree.


Edit: If hyperrectangles are restricted to have lines parallel to the axes, then it is obvious. Judging from problem 11.6 on page 183, this may well be the case.


