Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

داده‌های با ابعاد بالا و نفرین ابعاد

محمود امین‌طوسی، پاییز ۱۴۰۵

گروه علوم کامپیوتر، دانشگاه فردوسی مشهد

واقعیت‌های هندسی این صفحه از The Elements of Statistical Learning (Hastie et al. (2009))، بند 2.5، و فصل 6 کتاب Data Mining and Machine Learning زکی (Zaki & Meira (2020)) گرفته شده‌اند.

اهداف یادگیری. در پایان باید بتوانید

  1. حجم کره و مکعب در dd بعد را حساب کنید و توضیح دهید چرا نسبتشان به صفر میل می‌کند؛

  2. توضیح دهید چرا همسایگی‌ای که نسبتی ثابت از داده را در بر می‌گیرد در ابعاد بالا محلی نیست، و یال آن ed(r)=r1/de_d(r) = r^{1/d} را حساب کنید؛

  3. نشان دهید در ابعاد بالا نزدیک‌ترین و دورترین همسایه تقریباً به یک اندازه دورند، و بگویید این برای k-NN چه معنایی دارد؛

  4. توضیح دهید چرا بیشتر حجم کره در یک پوستهٔ نازک است، و چرا نمونه‌های گاوسی روی شعاع d\sqrt{d} تمرکز می‌کنند؛

  5. نقطه‌ها را به‌طور یکنواخت داخل کره و روی سطحش نمونه‌برداری کنید (چرا شعاع ساده‌لوحانه غلط است)؛

  6. اثر بُعد را روی یک دسته‌بند k-NN، با و بدون دادهٔ بیشتر، اندازه بگیرید.

English · فارسی
English · فارسی

مقدمه

در داده‌کاوی و یادگیری ماشین امروزی اغلب با داده در فضاهای با ابعاد بسیار بالا سر و کار داریم (تصویر، نمایش برداری متن، دادهٔ ژنومی). یک مجموعه‌داده معمولاً به‌صورت ماتریس n×dn \times d یعنی D\mathbf{D} نمایش داده می‌شود: nn نقطه و dd ویژگی.

فضای با ابعاد بالا، یا اَبَرفضا، مثل هندسهٔ دو یا سه بعد رفتار نمی‌کند. مجموعهٔ اثرهایی که از این واقعیت برمی‌آید نفرین ابعاد نامیده می‌شود. پنج پدیده‌ای که بررسی می‌کنیم:

  1. تمرکز حجم: حجم ابرکره در برابر ابرمکعبی که آن را در بر دارد ناچیز می‌شود.

  2. مسئلهٔ همسایگی‌های محلی: همسایگی «محلی»ای که نسبتی ثابت از داده را در بر می‌گیرد دیگر محلی نیست، پس روش‌هایی مثل k-NN معنای خود را از دست می‌دهند (ESL بند 2.5).

  3. تمرکز فاصله: نزدیک‌ترین و دورترین همسایه تقریباً در یک فاصله‌اند، پس رتبه‌بندی همسایه‌ها بی‌معنا می‌شود.

  4. پوستهٔ نازک: تقریباً همهٔ حجم کره نزدیک سطح آن است.

  5. تعامد و رفتار گاوسی: بردارهای تصادفی تقریباً متعامدند، و نمونه‌های گاوسی در یک پوستهٔ نازک روی شعاع d\sqrt{d} متمرکز می‌شوند.

در سراسر این صفحه dd تعداد ابعاد است. شکل‌هایی که از ESL آمده‌اند آن را pp می‌نامند؛ متن اینجا به‌طور یکدست dd به کار می‌برد.

<Figure size 900x500 with 1 Axes>
d =  1:  ball volume = 2.000e+00   ratio ball/cube = 1.000e+00
d =  2:  ball volume = 3.142e+00   ratio ball/cube = 7.854e-01
d =  3:  ball volume = 4.189e+00   ratio ball/cube = 5.236e-01
d = 10:  ball volume = 2.550e+00   ratio ball/cube = 2.490e-03
d = 20:  ball volume = 2.581e-02   ratio ball/cube = 2.461e-08

هندسهٔ اَبَرفضا: مکعب‌ها و کره‌ها

ابرمکعب

فضای داده را اغلب یک ابرمکعب dd-بعدی می‌گیرند. برای ابرمکعب Hd(l)H_d(l) با یال ll حجم به‌سادگی عبارت است از

Vol⁡(Hd(l))=ld.\operatorname{Vol}\big(H_d(l)\big) = l^d .

کره و سطح کره

به دو شیء متفاوت نیاز داریم و اشتباه گرفتنشان منبع کلاسیک خطاست:

  • کرهٔ توپر Bd(r)={x:∥x∥≤r}B_d(r) = \{\mathbf{x} : \|\mathbf{x}\| \le r\} جسم صلب است؛ حجمش

Vol⁡(Bd(r))=Kd rd,Kd=πd/2Γ ⁣(d2+1);\operatorname{Vol}\big(B_d(r)\big) = K_d\, r^d, \qquad K_d = \frac{\pi^{d/2}}{\Gamma\!\left(\frac{d}{2}+1\right)} ;
  • سطح کره Sd−1(r)={x:∥x∥=r}S^{d-1}(r) = \{\mathbf{x} : \|\mathbf{x}\| = r\} فقط پوسته است — مجموعه‌ای با اندازهٔ صفر — و با d−1d-1 نوشته می‌شود چون شیئی (d−1)(d-1)-بعدی است که در Rd\mathbb{R}^d زندگی می‌کند. مساحتش dKdrd−1d K_d r^{d-1} است، یعنی مشتق حجم نسبت به rr.

Γ\Gamma تابع گاما است؛ برای آرگومان‌های صحیح Γ(m)=(m−1)!\Gamma(m) = (m-1)!.

شکل 6.4. ابرکره‌ای محاط در ابرمکعب: (الف) دو و (ب) سه بعد (زکی، فصل 6).

مرکز تهی (اثر «خارپشت»)

بزرگ‌ترین کره‌ای را بگیرید که در مکعبی با یال l=2rl = 2r جا می‌شود، یعنی Bd(r)B_d(r). نسبت حجمشان

Vol⁡(Bd(r))Vol⁡(Hd(2r))=πd/22d Γ ⁣(d2+1)  →d→∞  0.\frac{\operatorname{Vol}\big(B_d(r)\big)}{\operatorname{Vol}\big(H_d(2r)\big)} = \frac{\pi^{d/2}}{2^d\,\Gamma\!\left(\frac{d}{2}+1\right)} \;\xrightarrow[d \to \infty]{}\; 0 .

پیامد. با رشد بُعد، کره در برابر مکعب ناچیز می‌شود: تقریباً همهٔ حجم مکعب در گوشه‌های آن است و مرکز عملاً تهی است. در dd بعد 2d2^d گوشه داریم.

گوشه‌ها در ابعاد بالا

نمای مفهومی فضای با ابعاد بالا: (الف) دو، (ب) سه، (ج) چهار و (د) ابعاد بالاتر. در dd بعد 2d2^d گوشه وجود دارد؛ شعاع کرهٔ محاطی همان چیزی است که تفاوت حجم مکعب و کره را دیدنی می‌کند (زکی، فصل 6).

مسئلهٔ همسایگی‌های محلی

یکی از پرپیامدترین جلوه‌های نفرین ابعاد این است که روش‌های «محلی» مثل k نزدیک‌ترین همسایه دیگر محلی نیستند.

یال یک همسایگی

فرض کنید ورودی‌ها به‌طور یکنواخت در ابرمکعب یکه [0,1]d[0,1]^d پخش شده‌اند و همسایگی‌ای می‌خواهیم که نسبت rr از مشاهدات را در بر گیرد. آن همسایگی باید نسبت rr از حجم را بپوشاند و اگر زیرمکعبی با یال ed(r)e_d(r) باشد،

(ed(r))d=r⟹ed(r)=r1/d.\big(e_d(r)\big)^d = r \qquad\Longrightarrow\qquad e_d(r) = r^{1/d} .

شکل 2.6 (ESL). یال زیرمکعبی که برای در برگرفتن نسبت rr از حجم داده لازم است، در ابعاد مختلف pp (شکل بُعد را pp می‌نامد؛ اینجا dd است). در ده بعد باید 80٪ دامنهٔ هر مؤلفه را بپوشانیم تا 10٪ داده را در بر بگیریم.

<Figure size 700x500 with 1 Axes>

تحلیل. با d=10d = 10 و r=0.1r = 0.1 به e10(0.1)=0.10.1≈0.80e_{10}(0.1) = 0.1^{0.1} \approx 0.80 نیاز داریم: برای گرفتن 10٪ داده باید 80٪ دامنهٔ هر مؤلفه را بپوشانیم. چنین همسایگی‌ای به هیچ معنای سودمندی محلی نیست — تقریباً همهٔ فضا است.

فاصله تا مرز

چگالی نمونه‌برداری به دلیل دومی هم کم است. برای NN نقطهٔ یکنواخت در کرهٔ یکه Bd(1)B_d(1)، میانهٔ فاصلهٔ مبدأ تا نزدیک‌ترین نقطهٔ داده

d(d,N)=(1−(12)1/N)1/d.d(d, N) = \left(1 - \left(\tfrac{1}{2}\right)^{1/N}\right)^{1/d} .

این فرمول از کجا می‌آید. احتمال اینکه یک نقطهٔ یکنواخت در کرهٔ شعاع tt بیفتد tdt^d است، پس احتمال اینکه بیرون بیفتد 1−td1 - t^d است، و احتمال اینکه همهٔ NN نقطه بیرون بیفتند (1−td)N(1 - t^d)^N. میانهٔ فاصله تا نزدیک‌ترین نقطه همان ttی است که این احتمال را برابر 1/21/2 می‌کند:

(1−td)N=12  ⟹  t=(1−(12)1/N)1/d.(1 - t^d)^N = \tfrac{1}{2} \;\Longrightarrow\; t = \left(1 - \left(\tfrac{1}{2}\right)^{1/N}\right)^{1/d} .

با N=500N = 500 و d=10d = 10 تقریباً 0.52 به دست می‌آید: بیش از نیمهٔ راه تا مرز. پس بیشتر نقطه‌های داده به مرز فضای نمونه نزدیک‌ترند تا به هر نقطهٔ دادهٔ دیگر، و پیش‌بینی مسئلهٔ برون‌یابی است نه درون‌یابی.

تمرکز فاصله

پدیده‌ای که بیش از همه به k-NN آسیب می‌زند یال همسایگی نیست، خود فاصله‌هاست. برای یک نقطهٔ پرس‌وجو، dmin⁡d_{\min} را فاصله تا نزدیک‌ترین همسایه و dmax⁡d_{\max} را فاصله تا دورترین نقطهٔ نمونه بگیرید. در یک بعد نسبت dmin⁡/dmax⁡d_{\min}/d_{\max} کوچک است: واقعاً نقطهٔ نزدیکی وجود دارد. در ابعاد بالا این نسبت به 1 میل می‌کند: نزدیک‌ترین نقطه تقریباً به اندازهٔ دورترین است، پس «نزدیک‌ترین» گزاره‌ای دربارهٔ نوفه است نه دربارهٔ شباهت.

آزمایش زیر nn نقطه را به‌طور یکنواخت در مکعب یکه برای d=2,10,100,1000d = 2, 10, 100, 1000 می‌ریزد، یک نقطهٔ پرس‌وجوی تصادفی برمی‌دارد و میانگین نسبت dmin⁡/dmax⁡d_{\min}/d_{\max} را روی پرس‌وجوهای زیاد گزارش می‌کند.

<Figure size 700x400 with 1 Axes>
d =    2:  mean d_min/d_max = 0.016
d =   10:  mean d_min/d_max = 0.269
d =  100:  mean d_min/d_max = 0.700
d = 1000:  mean d_min/d_max = 0.893

عددها را بخوانید: در دو بعد نزدیک‌ترین همسایه معمولاً کسر کوچکی از دورترین فاصله است، پس رتبه‌بندی همسایه‌ها آگاهی‌بخش است. در هزار بعد نسبت نزدیک 1 است — هر نقطه تقریباً از هر نقطهٔ دیگر هم‌فاصله است. دو پیامد:

  • رتبه‌بندی همسایه‌ها زیر سلطهٔ نوفه است: اینکه کدام نقطه «نزدیک‌ترین» است با اغتشاش‌های کوچک داده عوض می‌شود، پس رأی k-NN ناپایدار است.

  • کره‌ای حول پرس‌وجو که kk همسایه را در بر می‌گیرد چنان بزرگ است که بخش خوبی از داده را شامل می‌شود، پس میانگین «محلی» محلی نیست.

این همان دلیل نظری پشت آزمایش پایان این صفحه است.

استدلال پوستهٔ نازک

حجم داخل کره کجاست؟ پوستهٔ نازکی با ضخامت ϵ\epsilon درست زیر سطح کرهٔ شعاع rr را در نظر بگیرید. حجمش

Vol⁡(Bd(r))−Vol⁡(Bd(r−ϵ))=Kd(rd−(r−ϵ)d),\operatorname{Vol}\big(B_d(r)\big) - \operatorname{Vol}\big(B_d(r-\epsilon)\big) = K_d\left(r^d - (r-\epsilon)^d\right),

پس نسبت حجمی که در پوسته است

Vol⁡(shell)Vol⁡(Bd(r))=1−(1−ϵr)d  →d→∞  1.\frac{\operatorname{Vol}(\text{shell})}{\operatorname{Vol}\big(B_d(r)\big)} = 1 - \left(1 - \frac{\epsilon}{r}\right)^{d} \;\xrightarrow[d\to\infty]{}\; 1 .

شکل 6.6 (زکی، فصل 6): پوستهٔ کره حجم را با رشد dd در خود جمع می‌کند.

برای قرصی (d=2d=2) با r=1r=1 و ϵ=0.01\epsilon=0.01 پوسته 1−0.992≈2%1-0.99^2 \approx 2\% از مساحت را دارد. برای d=100d=100 همان پوسته 1−0.99100≈0.631-0.99^{100} \approx 0.63 — نزدیک دو سوم.

نتیجه. در ابعاد بالا، برای پوسته‌ای با ضخامت نسبی ثابت ϵ/r\epsilon/r، تقریباً 100٪ حجم — و جرم احتمال توزیع یکنواخت — نزدیک سطح متمرکز است. درون آن عملاً تهی است.

<Figure size 900x500 with 1 Axes>
d =  2:  shell fraction = 0.360
d = 10:  shell fraction = 0.893
d = 30:  shell fraction = 0.999

گریز: نمونه‌برداری یکنواخت در کره

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

نمونه‌برداری ردکردنی — تولید نقطهٔ یکنواخت در مکعب و نگه داشتن آن‌هایی که داخل کره‌اند — نرخ پذیرش برابر نسبت دو حجم دارد که به صفر می‌رود (اثر خارپشت). از حدود ده بعد به بعد عملاً بی‌فایده است. جدول زیر نرخ پذیرش را برای d=2,…,10d = 2, \dots, 10 با 2000 نقطهٔ پذیرفته‌شده اندازه می‌گیرد و با مقدار نظری Kd/2dK_d/2^d مقایسه می‌کند.

<Figure size 800x500 with 1 Axes>
d =  2:  measured = 0.8003   theory = 0.7854   candidates per accepted point =      1.2
d =  3:  measured = 0.5255   theory = 0.5236   candidates per accepted point =      1.9
d =  4:  measured = 0.3163   theory = 0.3084   candidates per accepted point =      3.2
d =  5:  measured = 0.1687   theory = 0.1645   candidates per accepted point =      5.9
d =  6:  measured = 0.0811   theory = 0.0807   candidates per accepted point =     12.3
d =  7:  measured = 0.0371   theory = 0.0369   candidates per accepted point =     27.0
d =  8:  measured = 0.0158   theory = 0.0159   candidates per accepted point =     63.2
d =  9:  measured = 0.0062   theory = 0.0064   candidates per accepted point =    160.0
d = 10:  measured = 0.0025   theory = 0.0025   candidates per accepted point =    408.0

نرخ اندازه‌گیری‌شده به‌طور هندسی افت می‌کند و Kd/2dK_d/2^d را دنبال می‌کند: تا d=10d=10 فقط حدود یک نقطهٔ نامزد از هر چهارصد نامزد داخل کره می‌افتد و هزینهٔ هر نقطهٔ پذیرفته‌شده با هر بُعد اضافه دو برابر می‌شود.

نقطه‌ها روی سطح: جهت‌های گاوسی

شگردی که نمونه‌برداری یکنواخت را ساده می‌کند استفاده از تقارن کروی توزیع گاوسی است. اگر xi∼N(0,1)x_i \sim \mathcal{N}(0,1) مستقل باشند، چگالی مشترک

f(x)=∏i=1d12πe−xi2/2=1(2π)d/2e−∥x∥2/2,f(\mathbf{x}) = \prod_{i=1}^d \frac{1}{\sqrt{2\pi}} e^{-x_i^2/2} = \frac{1}{(2\pi)^{d/2}} e^{-\|\mathbf{x}\|^2/2},

که فقط به طول ∥x∥\|\mathbf{x}\| بستگی دارد و هرگز به جهت. پس توزیع نسبت به دوران ناوردا است (همسانگرد)، همهٔ جهت‌ها به یک اندازه محتمل‌اند، و

y=x∥x∥\mathbf{y} = \frac{\mathbf{x}}{\|\mathbf{x}\|}

به‌طور یکنواخت روی سطح کرهٔ یکه Sd−1(1)S^{d-1}(1) پخش است.

<Figure size 500x500 with 1 Axes>

نقطه‌ها داخل کره

مقیاس دادن یک جهت با یک عدد تصادفی یکنواخت ρ∼U(0,1)\rho \sim U(0,1) غلط است: حجم پوستهٔ شعاع tt مثل td−1t^{d-1} رشد می‌کند، پس بیشتر حجم نزدیک سطح است و شعاع یکنواخت نقطه‌ها را نزدیک مرکز جمع می‌کند.

شعاع درست. برای توزیع یکنواخت داخل کره، احتمال اینکه نقطه در شعاع tt باشد باید متناسب با حجمی باشد که در بر می‌گیرد:

F(t)=P(R≤t)=Vol⁡(Bd(t))Vol⁡(Bd(1))=KdtdKd=td.F(t) = P(R \le t) = \frac{\operatorname{Vol}(B_d(t))}{\operatorname{Vol}(B_d(1))} = \frac{K_d t^d}{K_d} = t^d .

نمونه‌برداری وارون تبدیل با a∼U(0,1)a \sim U(0,1) آن‌گاه ρ=F−1(a)=a1/d\rho = F^{-1}(a) = a^{1/d} می‌دهد. برای d=2d=2، ρ=a\rho = \sqrt{a}:

a∼U(0,1)a \sim U(0,1)0.000.100.250.500.751.00
ρ=a\rho = \sqrt{a}0.0000.3160.5000.7070.8661.000

الگوریتم نقطه‌های یکنواخت در کرهٔ Bd(1)B_d(1):

  1. x∼N(0,Id)\mathbf{x} \sim \mathcal{N}(0, I_d) بکش؛

  2. نرمال کن، y=x/∥x∥\mathbf{y} = \mathbf{x}/\|\mathbf{x}\| — یک جهت یکنواخت؛

  3. a∼U(0,1)a \sim U(0,1) بکش؛

  4. a1/d ya^{1/d}\,\mathbf{y} را برگردان.

<Figure size 1100x500 with 2 Axes>
d =  2, naive  : fraction with rho < 0.5 = 0.4967   (expected 0.2500)
d =  2, correct: fraction with rho < 0.5 = 0.2479   (expected 0.2500)
d =  3, naive  : fraction with rho < 0.5 = 0.4966   (expected 0.1250)
d =  3, correct: fraction with rho < 0.5 = 0.1240   (expected 0.1250)
d = 10, naive  : fraction with rho < 0.5 = 0.5015   (expected 0.0010)
d = 10, correct: fraction with rho < 0.5 = 0.0009   (expected 0.0010)

جهت‌های تقریباً متعامد

خاصیت ضدشهودی دیگری این است که در ابعاد بالا «هر جهت بر هر جهت دیگر عمود است»، یا دقیق‌تر: بردارهای تصادفی تقریباً متعامدند.

قطر ابرمکعب

قطر اصلی مکعب را در نظر بگیرید، 1=(1,1,…,1)⊤\mathbf{1} = (1, 1, \dots, 1)^\top. زاویهٔ θd\theta_d میان آن و یک محور مختصات e1=(1,0,…,0)⊤\mathbf{e}_1 = (1, 0, \dots, 0)^\top در رابطهٔ

cos⁡θd=e1⊤1∥e1∥ ∥1∥=1d  →d→∞  0,\cos\theta_d = \frac{\mathbf{e}_1^\top \mathbf{1}}{\|\mathbf{e}_1\|\,\|\mathbf{1}\|} = \frac{1}{\sqrt{d}} \;\xrightarrow[d\to\infty]{}\; 0,

است، پس θd→90∘\theta_d \to 90^\circ: قطر تقریباً بر هر محور عمود است.

بردارهای تصادفی

همین برای دو بردار تصادفی مستقل هم برقرار است و دلیلش قانون اعداد بزرگ است: برای x\mathbf{x} و y\mathbf{y} با مؤلفه‌های مستقل، میانگین صفر و واریانس یک،

x⊤y∥x∥ ∥y∥≈∑ixiyid d,\frac{\mathbf{x}^\top \mathbf{y}}{\|\mathbf{x}\|\,\|\mathbf{y}\|} \approx \frac{\sum_i x_i y_i}{\sqrt{d}\,\sqrt{d}},

که صورتش مجموع dd جملهٔ مستقل با میانگین صفر و واریانس 1 و بنابراین به اندازهٔ d\sqrt{d} است — نسبت O(1/d)O(1/\sqrt{d}) می‌شود.

cosine similarities of 10 random pairs in 200-D:
[-0.0401  0.0349 -0.0056 -0.0042 -0.075  -0.0497 -0.0402  0.0836  0.0071
  0.1518]
max |cosine| = 0.1518   (1/sqrt(d) = 0.0707)

توزیع گاوسی در ابعاد بالا

از پوسته‌های هندسی به پوسته‌های آماری

اثرهای هندسی بالا دربارهٔ حجم کره بودند. توزیع گاوسی همان پدیده را آماری نشان می‌دهد: با اینکه چگالی‌اش در مبدأ بیشینه است، تقریباً هیچ نمونه‌ای نزدیک مبدأ نمی‌افتد.

چرا نقطه‌های گاوسی نزدیک میانگین جمع نمی‌شوند

بگذارید x=(x1,…,xd)∼N(0,Id)\mathbf{x} = (x_1, \dots, x_d) \sim \mathcal{N}(0, I_d). در یک بعد بسیاری از نمونه‌ها «نزدیک صفر»اند و ∣x∣|x| معمولاً کوچک است. این شهود از دو بعد به بعد می‌شکند: چگالی در مبدأ بیشینه است، ولی حجم موجود نزدیک مبدأ ناچیز است.

  • در یک بعد «مرکز» یک نقطه است و رشد حجمی وجود ندارد.

  • در dd بعد حجم پوسته مثل rd−1r^{d-1} رشد می‌کند، پس تعداد نقطه‌های روی شعاع rr چگالی × حجم است.

مرکز بیشترین چگالی را دارد ولی تقریباً هیچ حجمی، پس تقریباً هیچ نمونه‌ای آنجا نمی‌افتد.

فاصلهٔ یک بردار گاوسی از مبدأ

یک اتحاد سراسر این رفتار را توضیح می‌دهد:

∥x∥2=∑i=1dxi2∼χd2,E∥x∥2=d,E∥x∥≈d.\|\mathbf{x}\|^2 = \sum_{i=1}^d x_i^2 \sim \chi^2_d, \qquad \mathbb{E}\|\mathbf{x}\|^2 = d, \qquad \mathbb{E}\|\mathbf{x}\| \approx \sqrt{d}.

پس ∥x∥≈0.8\|\mathbf{x}\| \approx 0.8 برای d=1d=1، ≈1.41\approx 1.41 برای d=2d=2، ≈3.16\approx 3.16 برای d=10d=10 و ≈14.1\approx 14.1 برای d=200d=200 (نگاه کنید به توزیع کای‌دو). افزودن بُعد همهٔ نمونه‌ها را به بیرون می‌راند، نه فقط داده‌های پرت را: کل توزیع در پوستهٔ نازکی حول شعاع d\sqrt{d} می‌نشیند.

<Figure size 1100x400 with 2 Axes>
mean norm = 14.12   std = 0.70   sqrt(d) = 14.14
fraction of samples with norm within 10% of sqrt(d): 0.96

این دو بافت‌نگار نسخهٔ آماری اثر هندسی پوستهٔ نازک‌اند: دادهٔ گاوسی یک‌بعدی روی میانگین می‌نشیند، دادهٔ گاوسی دویست‌بعدی روی کره‌ای به شعاع 14.1 با پهنایی که با dd رشد نمی‌کند.

پدیدهٔ حلقهٔ گاوسی

گزارهٔ صوری چنین است:

با احتمال غالب یک نمونهٔ گاوسی در بازهٔ d±O(1)\sqrt{d} \pm O(1) از مبدأ است — حلقه‌ای نازک که ضخامتش با dd رشد نمی‌کند.

با افزایش dd شعاع مثل d\sqrt{d} رشد می‌کند در حالی که ضخامت ثابت می‌ماند، پس ضخامت نسبی به صفر میل می‌کند. همین دلیل استفادهٔ نظری از بردارهای گاوسی است: آن‌ها همان هندسهٔ فضای با ابعاد بالا هستند، همان‌گونه که نقطه‌های یکنواخت در کره.

پیوند با بخش‌های پیشین

نتیجهٔ پیشیننسخهٔ گاوسی
مرکز کره تهی استجرم گاوسی از مبدأ می‌پرهیزد
حجم یکنواخت روی سطح متمرکز استجرم گاوسی روی d\sqrt{d} متمرکز است
نمونه‌برداری یکنواخت به ρ=a1/d\rho = a^{1/d} نیاز داردنمونه‌برداری گاوسی این کار را خودکار می‌کند
بردارهای تصادفی تقریباً متعامدندبردارهای گاوسی نرمال‌شده تقریباً متعامدند

چرا مهم است

چون تقریباً همهٔ بردارهای گاوسی طول ≈d\approx \sqrt{d} دارند، دو بردار گاوسی مستقل x\mathbf{x} و y\mathbf{y} در ∥x−y∥2≈2d\|\mathbf{x} - \mathbf{y}\|^2 \approx 2d صدق می‌کنند، با پراکندگی نسبی‌ای که با رشد dd کوچک می‌شود: فاصله‌های دوبه‌دو پایدارند و ضرب داخلی بردارهای نرمال‌شده کوچک است. همین دو واقعیت تصویرهای تصادفی را کارا می‌کند و همان خواصی است که در بحث تصویرهای تصادفی و لم جانسون–لیندن‌شتراوس در ادامهٔ درس به آن برمی‌گردیم.

k-NN زیر نفرین ابعاد

استدلال تمرکز فاصله پیش‌بینی می‌کند که k-NN با رشد بُعد بدتر می‌شود — و اینکه این بدترشدن با دادهٔ بیشتر جبران‌شدنی است. آزمایش زیر هر دو پیش‌بینی را روی دادهٔ مصنوعی با make_classification می‌آزماید:

  • سطر 1: nn ثابت (n=600n = 600) در حالی که dd از 2 به 200 رشد می‌کند. فقط دو ویژگی آگاهی‌بخش‌اند (n_informative=2) و d−2d-2 ویژگی بقیه نوفه است. با nn ثابت، بُعد بیشتر یعنی نوفهٔ بیشتر و نقطهٔ کمتر به ازای هر بُعد.

  • سطر 2: nn با dd رشد می‌کند (n=100 dn = 100\,d)، پس تعداد نقطه به ازای هر بُعد ثابت می‌ماند. اگر نفرین دربارهٔ چگالی باشد و نه خود بُعد، این باید دقت را برگرداند.

هر پیکربندی روی پنج بذر تکرار می‌شود و نمودارها میانگین دقت را با نواری از ±1\pm 1 انحراف معیار نشان می‌دهند. دسته‌بند 5-NN روی ویژگی‌های استانداردشده است.

fixed n = 600 d =   2  n =    600   accuracy = 0.934 +- 0.039
fixed n = 600 d =   5  n =    600   accuracy = 0.903 +- 0.040
fixed n = 600 d =  10  n =    600   accuracy = 0.850 +- 0.039
fixed n = 600 d =  25  n =    600   accuracy = 0.773 +- 0.034
fixed n = 600 d =  50  n =    600   accuracy = 0.667 +- 0.052
fixed n = 600 d = 100  n =    600   accuracy = 0.608 +- 0.041
fixed n = 600 d = 200  n =    600   accuracy = 0.594 +- 0.022
n = 100 d     d =   2  n =    200   accuracy = 0.963 +- 0.036
n = 100 d     d =   5  n =    500   accuracy = 0.929 +- 0.057
n = 100 d     d =  10  n =   1000   accuracy = 0.878 +- 0.048
n = 100 d     d =  25  n =   2500   accuracy = 0.824 +- 0.075
n = 100 d     d =  50  n =   5000   accuracy = 0.737 +- 0.047
n = 100 d     d = 100  n =  10000   accuracy = 0.671 +- 0.016
n = 100 d     d = 200  n =  20000   accuracy = 0.627 +- 0.029
<Figure size 800x500 with 1 Axes>

منحنی اول با رشد بُعد افت می‌کند هرچند ساختار آگاهی‌بخش هرگز عوض نمی‌شود: دو ویژگی سودمند هنوز هستند ولی زیر d−2d-2 ویژگی نوفه دفن شده‌اند، و فاصله‌هایی که k-NN به آن‌ها اعتماد می‌کند زیر سلطهٔ نوفه‌اند.

منحنی دوم می‌آزماید که آیا دادهٔ بیشتر درمان است. کمک می‌کند — هر مقدار کمی بهتر از نقطهٔ متناظر منحنی اول است — ولی افت را متوقف نمی‌کند: دقت هنوز از حدود 0.96 در d=2d=2 به حدود 0.63 در d=200d=200 می‌افتد، با 33 برابر دادهٔ بیشتر. دادهٔ بیشتر چگالی می‌خرد و چگالی اینجا قید مقیدکننده نبود: قید مقیدکننده این است که تقریباً همهٔ مختصات نوفه‌اند، پس تمرکز فاصلهٔ بخش‌های پیشین خاصیتی از توزیع است، نه فقط از اندازهٔ نمونه.

پیامد عملی همان است که ESL در بند 2.5 می‌گیرد: برای دادهٔ با ابعاد بالا، k-NN باید پس از چیزی بیاید که جهت‌های بی‌اطلاع را حذف یا کم‌وزن کند — انتخاب ویژگی، PCA، یا یک متریک یادگرفته. افزودن نقطه سودمند است ولی جانشین آن نیست.

جمع‌بندی

  • فضای با ابعاد بالا در مرکز تهی است: حجم کره در برابر مکعب ناچیز است و تقریباً همهٔ حجم مکعب در 2d2^d گوشهٔ آن است.

  • همسایگی‌ای که نسبت ثابت rr از نقطه‌ها را در بر می‌گیرد یال ed(r)=r1/de_d(r) = r^{1/d} دارد: در ده بعد، 10٪ داده به 80٪ دامنهٔ هر مؤلفه نیاز دارد.

  • فاصله‌ها متمرکز می‌شوند: dmin⁡/dmax⁡→1d_{\min}/d_{\max} \to 1، پس رتبه‌بندی همسایه‌ها نوفه می‌شود و k-NN بدتر — مگر اینکه nn با dd رشد کند.

  • بیشتر حجم کره در پوستهٔ نازکی با ضخامت نسبی ثابت است، و نمونه‌های گاوسی روی شعاع d\sqrt{d} با ضخامتی که با dd رشد نمی‌کند متمرکز می‌شوند.

  • نمونه‌برداری یکنواخت در کره به شعاع ρ=a1/d\rho = a^{1/d} نیاز دارد؛ راه ساده یک جهت گاوسی ضرب در آن شعاع است. نمونه‌برداری ردکردنی به‌طور نمایی می‌میرد.

  • بردارهای تصادفی تقریباً متعامدند و فاصله‌های دوبه‌دو پایدارند — همان خواصی که پشت تصویرهای تصادفی است.

منابع

  • Hastie et al. (2009)، بند 2.5 (روش‌های محلی در ابعاد بالا، شکل 2.6) و بند 2.9 (برآورد مدل).

  • Zaki & Meira (2020)، فصل 6 (فضای با ابعاد بالا، شکل‌های 6.4 تا 6.6).

  • Blum، Hopcroft و Kannan، Foundations of Data Science، فصل 2 (تمرکز اندازه، تصویرهای تصادفی).

References
  1. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data Mining, Inference, and Prediction (2nd ed.). Springer.
  2. Zaki, M. J., & Meira, W. (2020). Data Mining and Machine Learning: Fundamental Concepts and Algorithms (2nd ed.). Cambridge University Press. https://www.cambridge.org/9781108497367