High Dimensional Data & the curse of dimensionality

Mahmood Amintoosi, Fall 2024

Computer Science Dept, Ferdowsi University of Mashhad

در فضاهای با ابعاد بالا:

• مفهوم محلی بودن کمرنگ می‌شود، ESL

• حجم ابرکره تقریبا صفر است، کتاب زکی

• حجم اصلی فضا در گوشه‌ها هست

• اکثر چگالی کره در پوسته‌ی آن جمع است، کتاب زکی

• با بردارهای با مؤلفه‌های گوسی، بیشتر چگالی نقاط در فاصله خاصی تا مرکز است

• همه بردارهای قطری، عمود بر محورها هستند، کتاب زکی

• بردارهای با مؤلفه‌های گوسی عمود بر هم هستند؟

برای آزمون برخی از اینها باید نقاطی با توزیع یکنواخت در داخل ابرکره تولید کنیم

import numpy as np
import matplotlib.pyplot as plt
import seaborn as sns
from scipy.stats import norm

x = np.random.randn(10000)
sns.displot(x, kde=True)

C:\Users\m.amintoosi\AppData\Roaming\Python\Python310\site-packages\seaborn\_oldcore.py:1119: FutureWarning: use_inf_as_na option is deprecated and will be removed in a future version. Convert inf values to NaN before operating instead.
  with pd.option_context('mode.use_inf_as_na', True):
C:\Users\m.amintoosi\AppData\Roaming\Python\Python310\site-packages\seaborn\axisgrid.py:118: UserWarning: The figure layout has changed to tight
  self._figure.tight_layout(*args, **kwargs)

<seaborn.axisgrid.FacetGrid at 0x1e251916ce0>

میانگین ایکس صفر هست اما میانگین قدرمطلق ایکس‌ها که اندازه فاصله آنها تا مبدا هست، صفر نیست.

abs_x = np.abs(x)
print(abs_x.mean(), np.sqrt(np.var(x)))
# sns.displot(abs_x, kde=False)

0.7963389532877564 0.999001957122858

According to Wiki: most of the volume of the d-cube concentrates near the boundary of a sphere of radius \(\sigma \sqrt{d}\)

Also according to section Distance of Points from the Mean of Chap 6 of Zaki: whereas the density of the standard multivariate normal is maximized at the center 0, most of the probability mass (the points) is concentrated in a small band around the mean distance of \(\sqrt{d}\) from the center.

x = np.random.randn(100, 2)
norm_x = np.linalg.norm(x, axis=1)
print(norm_x.mean(), np.sqrt(2))
# sns.displot(norm_x, kde=False)

1.3573055706605999 1.4142135623730951

x = np.random.randn(10000, 200)
norm_x = np.linalg.norm(x, axis=1)
print(norm_x.mean(), np.sqrt(200))

14.13576670923273 14.142135623730951

برمی‌گردیم به تولید نقاط تصادفی در گوی واحد.

ابتدا تولید نقاط تصادفی با توزیع یکنواخت بر روی دایره.

روش مختصات قطبی قابل تعمیم به فضاهای بالاتر نیست.

نشان می دهیم که اگر داده ها با توزیع نرمال در فضا تولید شده و سپس بر روی کره واحد نگاشت شوند توزیع آنها بر روی سطح کره یکنواخت هست

اگر هر داده را بر نرمش تقسیم کنیم، اندازه‌ی همه داده‌ها یک خواهد شد و روی کره‌ی واحد قرار خواهند گرفت

\[x = (x_1,x_2,\dots,x_d)\]

\[x_i \sim \mathcal{N}(\mu,\sigma^2)\]

\[f(x) = \frac{1}{\sqrt{2\pi}\sigma} e^{-\frac{1}{2}\left(\frac{x-\mu}{\sigma}\right)^2}\]

\[\mu=0, \sigma^2=1\]

\[f(x_i) = \frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}x_i^2}\]

\[y=\frac{x}{||x||}\]

y یک بردار تصادفی یکه با توزیع یکنواخت روی کره واحد است

مطابق روابط ۱.۱۹ و ۱.۲۰ از کتاب زکی تابع چگالی ایکس به صورت زیر است:

Joint probability function of \(x\) is given as:

\[\begin{split} \begin{aligned} f(x)&=\prod_{i=1}^d f(x_i)\\ &= \prod_{i=1}^d\frac{1}{\sqrt{2\pi}} e^{-\frac{1}{2}x_i^2} \\ &= \left(\frac{1}{\sqrt{2\pi}}\right)^d e^{-\frac{1}{2}\sum_{i=1}^dx_i^2} \\ &= \frac{1}{(2\pi)^{d/2}} e^{-\frac{||x||^2}{2}} \end{aligned} \end{split}\]

یعنی چگالی فقط به اندازه بردار بستگی دارد. پس همه نقاط روی کره‌ی به شعاع مشخص چگالی یکسانی دارند.

دوباره تکه برنامه قبلی رو می‌نویسیم

x = np.random.randn(100, 2)
norm_x = np.linalg.norm(x, axis=1)
print(norm_x.mean(), np.sqrt(2))
# sns.displot(norm_x, kde=False)
x.shape, norm_x[:,np.newaxis].shape

1.333765378402273 1.4142135623730951

((100, 2), (100, 1))

y = x/norm_x[:,np.newaxis]
plt.scatter(x[:,0],x[:,1], 2)
plt.scatter(y[:,0],y[:,1], 5)
ax = plt.gca()
ax.set_aspect('equal', adjustable='box')
plt.draw()

با داشتن اعداد تصادفی با توزیع یکنواخت می‌توان اعداد تصادفی با هر توزیعی تولید کرد

Cumulative Distribution Function

For random variable \(X\), its cumulative distribution function (CDF) \(F:\mathbb{R} \to [0,1]\), gives the probability of observing a value at most some given value \(x\): (eq. 1.17 of Zaki)

\[ \large \begin{aligned} F(x) = P(X \le x) \qquad \text{for all } -\infty < x < \infty \end{aligned} \]

If \(a\sim \mathcal{U}(0,1) \Rightarrow P(a\leq a_0) = a_0\)

If we get \(X=F^{-1}(a)\), then \(X\) has probabilty distribution \(F\).

\[\begin{split} \begin{aligned} P(X \le x) &= P(F^{-1}(a) \le x) \\ &= P(a \le F(x)) \\ &= F(x) \quad \textrm{Since} \quad a\sim \mathcal{U}(0,1) \end{aligned} \end{split}\]

Due to the monotonicity of \(F^{-1}\), the inequality \(F^{-1}(a) \leq x\) holds if and only if \(a \leq F(x)\):

\[ P(F^{-1}(a) \leq x) = P(a \leq F(x)) \]

حالا موارد بالا را امتحان می‌کنیم. ابتدا برای تولید اعداد تصادفی نرمال با استفاده از توزیع یکنواخت و بعد برای مورد تولید نقاط تصادفی در داخل گوی واحد بدون استفاده از روشی که قبلا بکار برده بودیم یعنی

Rejection Sampling.

یک تعداد عدد تصادفی از توزیع یکنواخت تولید کرده و سپس با وارون تابع تجمعی توزیع نرمال به توزیع نرمال می‌رسیم

https://stackoverflow.com/questions/20626994/how-to-calculate-the-inverse-of-the-normal-cumulative-distribution-function-in-p

from statistics import NormalDist # Needs Python >= 3.8
x = np.random.rand(10000)
sns.displot(x)

C:\Users\m.amintoosi\AppData\Roaming\Python\Python310\site-packages\seaborn\_oldcore.py:1119: FutureWarning: use_inf_as_na option is deprecated and will be removed in a future version. Convert inf values to NaN before operating instead.
  with pd.option_context('mode.use_inf_as_na', True):
C:\Users\m.amintoosi\AppData\Roaming\Python\Python310\site-packages\seaborn\axisgrid.py:118: UserWarning: The figure layout has changed to tight
  self._figure.tight_layout(*args, **kwargs)

<seaborn.axisgrid.FacetGrid at 0x1e2519153c0>

y = [NormalDist().inv_cdf(a) for a in x]
y = np.array(y)
print(y.mean(), y.var())

-0.0013618378781789012 0.9982451176139835

sns.displot(y, kde=True)

C:\Users\m.amintoosi\AppData\Roaming\Python\Python310\site-packages\seaborn\_oldcore.py:1119: FutureWarning: use_inf_as_na option is deprecated and will be removed in a future version. Convert inf values to NaN before operating instead.
  with pd.option_context('mode.use_inf_as_na', True):
C:\Users\m.amintoosi\AppData\Roaming\Python\Python310\site-packages\seaborn\axisgrid.py:118: UserWarning: The figure layout has changed to tight
  self._figure.tight_layout(*args, **kwargs)

<seaborn.axisgrid.FacetGrid at 0x1e251b7f940>

تولید نقاط تصادفی با توزیع یکنواخت در داخل گوی واحد

یک سری نقاط تصادفی که هر مؤلفه‌ی هر نقطه از توزیع گوسی آمده است تولید می‌کنیم، سپس مشابه برنامه بالا هر نقطه را بر اندازه‌اش تقسیم می‌کنیم.

x = np.random.randn(400, 2)
norm_x = np.linalg.norm(x, axis=1)
y = x/norm_x[:,np.newaxis]

قبلاً مشاهده کردیم که y ها از نگاشت x ها بر روی دایره واحد به دست می‌آیند. اگر y ها را در یک مقدار ثابت کمتر از یک ضرب کنیم، آن‌ها در داخل دایره واحد جابجا می‌شوند:

\[x = (x_1,x_2,\dots,x_d)\]

\[x_i \sim \mathcal{N}(\mu,\sigma^2)\]

\[y=\rho\frac{x}{||x||}, \quad 0\le \rho \le 1\]

اما چگالی نقاط تولید شده در داخل دایره یکنواخت نیست.

rho = np.random.rand(len(x))
y = rho[:,np.newaxis] * x/norm_x[:,np.newaxis]
plt.figure(figsize=(6, 6))
plt.scatter(x[:,0],x[:,1],.1)
plt.scatter(y[:,0],y[:,1],3)
ax = plt.gca()
ax.set_aspect('equal', adjustable='box')
plt.draw()

قبل از ادامه، یادآوری چند تعریف از کتاب زکی:

ابتدا ابرگوی و ابرکره، رابطه ۶.۱ کتاب زکی

The data hyperspace can be represented as a \(d\)-dimensional hyperball centered at \(0\) with radius \(r\), defined as

\[ B_d(r) = \bigl\{ x\; |\;\; ||x|| \le r\bigr\} \]

The surface of the hyperball is called a hypersphere, and it consists of all the points exactly at distance \(r\) from the center of the hyperball

\[ S_d(r) = \bigl\{ x\; |\;\; ||x|| = r\bigr\} \]

البته حجم هر دو یکسان هست، رابطه ۶.۱۰ کتاب زکی:

\[ \textrm{Vol}(S_d(r))=K_d r^d \]

که در آن $k_d$ حجم کره واحد d بعدی هست.

\[ \textrm{Vol}(S_d(1))= K_d \]

در بالا rho با توزیع یکنواخت در بازه صفر و یک بود و خروجی آنچنان که می‌خواستیم نشد. اگر بتوانیم rho را از توزیعی ایجاد کنیم که متناسب با حجم ابرگوی ما باشد نقاط به صورت یکنواخت در داخل ابرگوی ما خواهند بود.

اگر قرار باشد چگالی نقاط در همه جا یکسان باشد، رو باید از توزیع دیگری باشد به نحوی که تابع توزیع تجمعی آن متناسب با نسبت حجم گوی به شعاع r به حجم گوی واحد باشد:

\[F(\rho) = P(\rho \le r) = \frac{\textrm{Vol}(S_d(r))}{\textrm{Vol}(S_d(1))}\]

که در آن، صورت کسر، حجم گوی d بعدی به شعاع r هست و مخرج کسر حجم گوی واحد.

می‌دانیم که حجم گوی d بعدی به شعاع r، r به توان d برابر حجم گوی واحد هست یعنی:

\[P(\rho \le r) = \frac{r^d K_d}{K_d} = r^d \]

لذا تابع توزیع تجمعی (CDF) باید به صورت x^d باشد:

\[ F(x) = x^d\]

مطابق آنچه در بالاتر دیدیم، برای اینکه رو از همچین توزیعی دربیاد، کافیست a را با توزیع یکنواخت تولید کنیم و وارون تابع توزیع تجمعی رو را روی آن اعمال کنیم:

\(a\sim \mathcal{U}(0,1)\)

\[\rho = F^{-1}(a) = a ^ {1/d}\]

a = np.random.rand(len(x))
d = 2
rho = a**(1/d)
y = rho[:,np.newaxis] * x/norm_x[:,np.newaxis]
plt.figure(figsize=(6, 6))
plt.scatter(x[:,0],x[:,1],.1)
plt.scatter(y[:,0],y[:,1],3)
ax = plt.gca()
ax.set_aspect('equal', adjustable='box')
plt.draw()

We did it :)

• بررسی تقریبا متعامد بودن بردارهای با مؤلفه‌های گوسی در فضاهای با ابعاد بالا

x = np.random.randn(4, 200)
norm_x = np.linalg.norm(x, axis=1)
y = x/norm_x[:,np.newaxis]

# rho = np.random.rand(len(x))
# y = rho[:,np.newaxis] * y

# a = np.random.rand(len(x))
# d = 2
# rho = a**(1/d)
# y = rho[:,np.newaxis] * y

for i in range(len(y)):
    for j in range(i+1,len(y)):
        print(np.dot(y[i],y[j]))

-0.03266827994478738
-0.06715105526363858
-0.01307570018736591
0.09975298665446185
-0.023308848425242605
0.04607856574295245

تمرینها:

• مقایسه تولید نقاط در گوی واحد در ابعاد بالا با روش نمونه‌برداری بازپس‌زننده روش ذکر شده در بالا از منظر زمان اجرا

• تخمین حجم ابرکره با روش مونت کارلو

• تخمین نسبت حجم ابرکره به ابرمکعب محیط بر آن

• تخمین نسبت حجم پوسته‌ی به ضخامت اپسیلون به کل ابرکره