Advanced Machine Learning

07: Curse of Dimensionality

Schedule

Outline of this lecture

• Curse of dimensionality

Curse of dimensionality

How much rind?

Generalized Pythagoras Theorem

Trapezoid rule

Stirling approximation for $n!$

• $\ln n! = \sum_{k=1}^n \ln k$
• $\int_1^n \ln x dx$
• $\int_1^n \ln x dx = n\ln n -n +1$
• $\int_1^n \ln x dx \sim {1 \over 2}\ln 1 + \ln 2 + \ln 3 + \dots + {1 \over 2}\ln n$
• $\sum_{k=1}^n \ln k \sim n\ln n - n + 1 + {1 \over 2}\ln n$
• $n! \sim Cn^ne^{-n}\sqrt{n}$
• $C = \sqrt{2\pi}$
• $n! \sim n^ne^{-n}\sqrt{2\pi n}$

Stirling approximation for $n!$

$\Gamma$ (Gamma) function

• $\Gamma(n) = \displaystyle\int_0^{\infty} x^{n-1}e^{-x}dx$
• Integration by parts: $\int udv = uv - \int vdu$
• $u=x^{n-1}$, $dv = e^{-x}dx$, $du = (n-1)x^{n-2}dx$, $v = -e^{-x}$
• $\Gamma(n) = -e^{-x}x^{n-1} \displaystyle|_0^{\infty} + (n-1)\int_0^{\infty} x^{n-2}e^{-x}dx$
• $\Gamma(n) = (n-1)\Gamma(n-1)$
• $\Gamma(1) = 1$
• $\Gamma(n) = (n - 1)!$

$\Gamma({1 \over 2})$

• $\Gamma({1 \over 2}) = \displaystyle\int_0^{\infty} x^{-{1 \over 2}}e^{-x}dx$
• Set $x = t^2$, follows $dx = 2tdt$
• $\Gamma({1 \over 2}) = 2 \displaystyle\int_0^{\infty} e^{-t^2}dt = \displaystyle\int_{-\infty}^{\infty} e^{-t^2}dt$
• $\Gamma^2(\frac{1}{2}) = \displaystyle\int_{-\infty}^{\infty}\displaystyle\int_{-\infty}^{\infty} e^{-(x^2+y^2)dxdy}$
• $\Gamma^2(\frac{1}{2}) = \displaystyle\int_{0}^{2\pi}\int_{0}^{\infty} r e^{-r^2} dr d\theta$
• $\Gamma^2(\frac{1}{2}) = \pi $
• $\Gamma(\frac{1}{2}) = \sqrt{\pi} $

Hypersphere Volume

• $\mbox{volume} = C_n r^n$
• $C_1 = 2$, $C_2 = \pi$, $C_3 = \frac{4\pi}{3}$
• $\mbox{surface area} = \frac{dV_n(r)}{dr} = n C_n r^{n-1}$
• $\left(\frac{dV_n(r)}{dr}\right)dr = n C_n r^{n-1}dr$
• \begin{align} \Gamma^n\left(\frac{1}{2}\right) = \pi^{n/2} &= \displaystyle \int_0^{\infty} e^{-r^2} \left(\frac{dV_n(r)}{dr}\right)dr \\ & = \frac{nC_n}{2} \displaystyle \int_0^{\infty} e^{-t} t^{n/2-1}dt \\ & = \frac{nC_n}{2} \Gamma\left(\frac{n}{2}\right)\\ & = C_n \Gamma\left(\frac{n}{2} + 1\right) \end{align}

hyperSphere Volume

In a general hyperwatermelonsphere

Fraction of volume

\[ \frac{V_{rind}}{V_{total}} = 1 - (1 - \epsilon)^D \]

What volume fraction of a hyper-melon does the rind occupy if it takes up an $\epsilon$ fraction of its radius?

Gaussian distribution

What's the probability of a random sample falling on a radius $r$ "shell" around the mean?

What if the flesh isn't in the center?

Local minima and multiple starts

Law of cosines

Angles between vectors

• $\cos\theta = \frac{1}{\sqrt{n}} \to 0$ and $\theta \to \frac{\pi}{2}$
• $\cos\theta = \frac{\sum_{k=1}^n x_k y_k}{XY}$
• Draw vectors to two random points $(\pm 1, \pm 1, \pm 1. \dots, \pm 1)$
• $\cos\theta = \frac{\sum_{k=1}^n (\pm 1)}{n} \stackrel{a.s.}\to 0$, as $n \to \infty$

Angles between vectors

Probability of orthogonality

Estimating probability

4x4 paradox

Alternative distances

$L_1$ $L_{\infty}$

Conditions on a metric

1. $D(x,y) \ge 0$ (non-negative)
2. $D(x,y) = 0$ iff $x=y$ (identity)
3. $D(x,y) = D(y,x)$ (symmetry)
4. $D(x,y) + D(y,z) \ge D(x,z)$ (triangle inequality)

Case study: an average human

Reading list

• p. 33 of "Pattern recognition and Machine Learning" by C. Bishop
• p. 22 of "The Elements of Statistical Learning" by T. Hastie, R. Tibshirani, and J. Friedman
• Chapter 9 of "The Art of Doing Science and Engineering: Learning to Learn" by R. Hamming