Curse of Dimensionality ... as illustrated by Christopher Bishop

Question

I'm reading Christopher Bishop's book "Neural Networks for Pattern Recognition". I'm on pg 7 about curse of dimensionality. Here is the relevant part:

For simplicity assume the dimensionality we are working with is 3. Now "divide the input variables $x_1, \dots x_d$ into M intervals, so that the value of a variable can be specified approximately by saying in which interval it lies. This leads to a division of the whole input space into a large number of [3D] boxes or cells ... Each of the training examples corresponds to a point in one of the cells , and carries an associated value of the output variable $y$. ... [To find $y$ for a given point], by finding which cell the point falls in, and then returning the average value of y for all training points that lie in that cell."

The claim is that if each input variable is divided into $M$ divisions, then the total number of cells is $M^d$.

First and foremost, why is this true? Why do we need $M^d$ cells? Secondly, what does it mean to divide an input variable into intervals or divisions. (I assume an input variable is $x_i$ from $x_1, \dots, x_d$ for $1\leq i \leq d$.)

I'm interested in making sure that I understand this because this seems (at least to me) a clever way of thinking about the curse of dimensionality.

Answer 1

I'll answer to the best of my ability with a simple example. First, imagine we're in one dimension ($d = 1$). So there's an input $x$ and an output $y$ which is supposedly dependent on $x$. Now imagine that $x$ was in $[0,1]$ (in between 0 and 1). We could split our interval in half ($M=2$). So if $x \in [0,0.5)$ we put it in "box" A, and if $x \in [0.5,1]$ we put it in "box" B. Then we could guess our output by seeing which "box" the input is and outputting the average of the output values in that "box".

Now, still in one dimension, we could instead split our output into 3 sections ($M=3$), with [0,1/3), [1/3, 2/3), and [2/3,1] as our input set. We could do this for any $M \in \mathbb{Z}$.

Now, imagine instead we're in 2 dimensions ($d=2$). So we have 2 inputs, $x_1$ and $x_2$, and an output $y$. Now, when we split up our input we have to consider both splitting up $x_1$ into $M$ pieces and splitting up $x_2$ into $M$ pieces. So we would have $M^2$ different "boxes" which our input could be in.

Generalizing, we could have $d$ input variables, $x_1, x_2, ..., x_d$, and to make the appropriate "boxes" of inputs, if we split each variable into $M$ subsets, we would have $M^d$ "boxes".

Answer 2

Let's be explicit and consider $M=3$. If $d=1$, then you divide a segment into three subsegments. For example you divide the interval $[0,1]$ into $[0,1/3)$, $(1/3,2/3]$, and $(2/3,1]$.

If $d=2$, then you divide a square into thirds horizontally and also vertically, so there are $9$ areas. If $d=3$, then you divide a cube into thirds in all three directions, like a Rubik's cube, leading to $3^3=27$ volumes. That's why you need $M^d$ cells.