Hi,
The way I understood it, we originally cover all the D-dimensional space with N samples (balls of radius \(\delta\) ), since for any input we find a nearest sample at distance roughly \(\delta\).
Now if we want the distance to be reduced to \(\delta /2\), then as a ball of radius r has volume r^D in a D-dimensional space, a ball of radius \(\delta /2\) will have volume (\(\delta /2\))^D. Hence there is a factor 2^(-D) that we need to compensate.
Hi,
The way I understood it, we originally cover all the D-dimensional space with N samples (balls of radius \(\delta\) ), since for any input we find a nearest sample at distance roughly \(\delta\).
Now if we want the distance to be reduced to \(\delta /2\), then as a ball of radius r has volume r^D in a D-dimensional space, a ball of radius \(\delta /2\) will have volume (\(\delta /2\))^D. Hence there is a factor 2^(-D) that we need to compensate.
Another way to see it (without balls, but \(D << \infty\)):
Imagine you have a point A that pops in your space and is at distance \(\delta\). It can reach your neighborhood and can be correctly classify. If he pops at a smaller distance \(\delta/2\), you'll need more point to reach it.
If you have points defining a cube, you will need twice more points in each dimension, so \(2^3\) more points.
Q4 exam 2019
Hello,
I struggle to understand the correction of the question 4 of the exam 2019… can you explain it maybe in another way or help me please?
1
Hi,
The way I understood it, we originally cover all the D-dimensional space with N samples (balls of radius \(\delta\) ), since for any input we find a nearest sample at distance roughly \(\delta\).
Now if we want the distance to be reduced to \(\delta /2\), then as a ball of radius r has volume r^D in a D-dimensional space, a ball of radius \(\delta /2\) will have volume (\(\delta /2\))^D. Hence there is a factor 2^(-D) that we need to compensate.
3
up.
Hi,
The way I understood it, we originally cover all the D-dimensional space with N samples (balls of radius \(\delta\) ), since for any input we find a nearest sample at distance roughly \(\delta\).
Now if we want the distance to be reduced to \(\delta /2\), then as a ball of radius r has volume r^D in a D-dimensional space, a ball of radius \(\delta /2\) will have volume (\(\delta /2\))^D. Hence there is a factor 2^(-D) that we need to compensate.
3
Another way to see it (without balls, but \(D << \infty\)):
Imagine you have a point A that pops in your space and is at distance \(\delta\). It can reach your neighborhood and can be correctly classify. If he pops at a smaller distance \(\delta/2\), you'll need more point to reach it.
If you have points defining a cube, you will need twice more points in each dimension, so \(2^3\) more points.
Add comment