فصل ۸: کاهش ابعاد
بسیاری از مسائل یادگیری ماشین برای هر نمونهٔ آموزشی هزاران یا حتی میلیونها ویژگی دارند. این حجم از ویژگیها نهتنها آموزش را بسیار کند میکند، بلکه همانطور که خواهیم دید پیدا کردن یک راهحل خوب را نیز دشوارتر میسازد. معمولاً از این مشکل با عنوان نفرین ابعاد یاد میشود.
خوشبختانه در مسائل دنیای واقعی اغلب میتوان تعداد ویژگیها را بهشکل قابلتوجهی کاهش داد و مسئلهای که در عمل حلناپذیر به نظر میرسد به مسئلهای قابلحل تبدیل کرد. برای نمونه، تصاویر MNIST را در نظر بگیرید: پیکسلهای حاشیهٔ تصویر تقریباً همیشه سفید هستند، بنابراین میتوان آنها را تقریباً بدون از دست دادن اطلاعات از مجموعهٔ آموزشی حذف کرد. در فصل قبل نیز شکل ۷-۶ نشان داد که این پیکسلها برای کار طبقهبندی عملاً بیاهمیتاند. افزون بر این، دو پیکسل مجاور اغلب همبستگی زیادی دارند؛ اگر آنها را مثلاً با گرفتن میانگین شدت دو پیکسل به یک پیکسل تبدیل کنید، معمولاً اطلاعات زیادی از دست نمیرود.
کاهش ابعاد مقداری از اطلاعات را از بین میبرد؛ همانطور که فشردهسازی تصویر به JPEG میتواند کیفیت را کاهش دهد. بنابراین هرچند آموزش را سریعتر میکند، ممکن است عملکرد سامانه اندکی بدتر شود. همچنین Pipeline را پیچیدهتر و نگهداری آن را دشوارتر میکند. پیشنهاد کتاب این است که پیش از کاهش ابعاد ابتدا سامانه را با دادهٔ اصلی آموزش دهید. گاهی کاهش ابعاد با حذف نویز و جزئیات غیرضروری عملکرد را بهتر میکند، اما معمولاً هدف اصلی آن افزایش سرعت آموزش است.
کاهش ابعاد علاوه بر افزایش سرعت آموزش برای بصریسازی داده نیز بسیار مفید است. کاهش تعداد ابعاد به دو یا سه بُعد امکان ترسیم نمای فشردهای از یک مجموعهٔ دادهٔ پُربعد را فراهم میکند و با مشاهدهٔ الگوهایی مانند خوشهها میتوان بینش مهمی به دست آورد. بصریسازی همچنین برای انتقال نتایج به افرادی که دانشمند داده نیستند، بهویژه تصمیمگیرندگانی که از نتایج استفاده خواهند کرد، ضروری است.
در این فصل ابتدا نفرین ابعاد و رفتار فضاهای پُربعد بررسی میشود. سپس دو رویکرد اصلی کاهش ابعاد، یعنی Projection و Manifold Learning، معرفی میشوند و پس از آن سه روش پرکاربرد یعنی PCA، Random Projection و Locally Linear Embedding یا LLE بررسی خواهند شد.
نفرین ابعاد
ما آنقدر به زندگی در سه بُعد عادت کردهایم که شهودمان هنگام تصور فضاهای پُربعد بهسرعت از کار میافتد. حتی تصور یک ابرمکعب چهاربعدی ساده دشوار است، چه برسد به یک بیضیوارهٔ ۲۰۰بعدی که در فضایی ۱۰۰۰بعدی خم شده باشد.
شکل 8-1. نقطه، پارهخط، مربع، مکعب و Tesseract؛ ابرمکعبهای صفر تا چهار بُعد
بسیاری از پدیدهها در فضای پُربعد رفتاری کاملاً متفاوت دارند. اگر نقطهای را بهطور تصادفی در یک مربع واحد انتخاب کنید، تنها حدود ۰٫۴٪ احتمال دارد فاصلهٔ آن از یکی از مرزها کمتر از ۰٫۰۰۱ باشد؛ یعنی احتمال اینکه نقطه در یکی از ابعاد «افراطی» باشد بسیار کم است. اما در یک ابرمکعب واحدِ ۱۰٬۰۰۰بعدی این احتمال از ۹۹٫۹۹۹۹۹۹٪ بیشتر است. در نتیجه بیشتر نقاط یک ابرمکعب پُربعد به مرز آن بسیار نزدیکاند.
تفاوت آزاردهندهتر به فاصلهٔ نقاط مربوط میشود. فاصلهٔ متوسط دو نقطهٔ تصادفی در مربع واحد تقریباً ۰٫۵۲ است و در مکعب واحد سهبعدی به حدود ۰٫۶۶ میرسد. اما در یک ابرمکعب واحد با یک میلیون بُعد، فاصلهٔ متوسط تقریباً ۴۰۸٫۲۵ است. این نتیجه در نگاه نخست ضدشهودی است، زیرا هر دو نقطه داخل همان ابرمکعب واحد قرار دارند؛ بااینحال در ابعاد زیاد فضای بسیار زیادی وجود دارد.
در نتیجه، مجموعهدادههای پُربعد در معرض تنکشدن شدید قرار دارند و بیشتر نمونههای آموزشی از یکدیگر بسیار دور میشوند. نمونهٔ جدید نیز احتمالاً از هر نمونهٔ آموزشی فاصلهٔ زیادی خواهد داشت؛ بنابراین پیشبینیها نسبت به فضای کمبعد به برونیابیهای بزرگتری وابسته میشوند و قابلیت اعتماد کمتری دارند. بهطور خلاصه، هرچه ابعاد مجموعهٔ آموزشی بیشتر باشد خطر بیشبرازش افزایش مییابد.
در نظریه میتوان برای مقابله با نفرین ابعاد تعداد نمونههای آموزشی را افزایش داد تا تراکم کافی ایجاد شود. در عمل تعداد نمونهٔ لازم برای رسیدن به یک تراکم معین بهصورت نمایی با تعداد ابعاد رشد میکند. حتی اگر فقط ۱۰۰ ویژگی داشته باشید و هر ویژگی بین صفر و یک باشد، برای اینکه فاصلهٔ متوسط نمونهها از یکدیگر کمتر از ۰٫۱ شود ــ با فرض پخش یکنواخت در همهٔ ابعاد ــ به تعداد نمونهای بیشتر از تعداد اتمهای جهان قابل مشاهده نیاز خواهید داشت.
رویکردهای اصلی کاهش ابعاد
پیش از ورود به الگوریتمهای مشخص، دو رویکرد اصلی کاهش ابعاد را بررسی میکنیم: فرافکنی یا Projection و یادگیری منیفلد یا Manifold Learning.
Projection
در بیشتر مسائل دنیای واقعی، نمونههای آموزشی بهصورت یکنواخت در همهٔ ابعاد پخش نشدهاند. بسیاری از ویژگیها تقریباً ثابتاند و برخی دیگر همبستگی زیادی دارند. بنابراین نمونهها معمولاً روی یک زیرفضای با ابعاد بسیار کمتر، یا در نزدیکی آن، قرار میگیرند. شکل ۸-۲ نمونهای سهبعدی را نشان میدهد که نقاط آن نزدیک یک صفحه قرار گرفتهاند.
شکل 8-2. مجموعهٔ سهبعدی نزدیک یک زیرفضای دوبعدی
این صفحه یک زیرفضای دوبعدی در فضای سهبعدی است. اگر همهٔ نمونهها را عمود بر این صفحه فرافکنی کنیم، مجموعهٔ دوبعدی شکل ۸-۳ به دست میآید. به این ترتیب ابعاد داده از سه به دو کاهش یافته است. محورهای جدید z1 و z2 مختصات نقاط فرافکنیشده روی صفحه هستند.
شکل 8-3. مجموعهٔ دوبعدی جدید پس از Projection
Manifold Learning
Projection همیشه بهترین راه نیست. گاهی زیرفضای کمبعد خمیده و پیچخورده است؛ مجموعهٔ آزمایشی مشهور Swiss Roll در شکل ۸-۴ نمونهای از این وضعیت است.
شکل 8-4. مجموعهدادهٔ Swiss Roll
اگر فقط آن را روی یک صفحه فرافکنی کنیم، مثلاً با کنار گذاشتن x3، لایههای مختلف رول روی هم فشرده میشوند؛ همان چیزی که در سمت چپ شکل ۸-۵ دیده میشود. هدف مطلوبتر این است که رول باز شود تا نمایش دوبعدی سمت راست شکل حاصل گردد.
شکل 8-5. فشردهشدن با Projection در برابر باز کردن Swiss Roll
Swiss Roll نمونهای از یک منیفلد دوبعدی است. به زبان ساده، منیفلد دوبعدی شکلی دوبعدی است که میتواند در فضای با ابعاد بیشتر خم و پیچیده شود. بهطور عمومی، منیفلد dبعدی بخشی از فضای nبعدی است، با شرط d < n، که در نواحی محلی شبیه یک ابرصفحهٔ dبعدی به نظر میرسد. در Swiss Roll، مقدار d=2 و n=3 است: در مقیاس محلی شبیه صفحهٔ دوبعدی است، ولی در بُعد سوم رول شده است.
بسیاری از الگوریتمهای کاهش ابعاد منیفلدی را که نمونهها روی آن قرار دارند مدل میکنند؛ این روش یادگیری منیفلد نام دارد. این رویکرد به فرضیهٔ منیفلد متکی است: بیشتر مجموعهدادههای واقعی با ابعاد زیاد نزدیک یک منیفلد با ابعاد بسیار کمتر قرار دارند. این فرض در عمل بسیار زیاد مشاهده میشود.
دوباره MNIST را در نظر بگیرید. تصاویر ارقام دستنویس ویژگیهای مشترکی دارند: از خطوط پیوسته ساخته شدهاند، حاشیهها سفید است و رقم تقریباً در مرکز قرار دارد. اگر تصاویر را کاملاً تصادفی تولید کنید، فقط بخش بسیار ناچیزی از آنها شبیه رقم دستنویس خواهد شد. بنابراین درجات آزادی لازم برای ساخت یک رقم بسیار کمتر از درجات آزادی ساخت یک تصویر کاملاً دلخواه است و همین محدودیتها داده را روی منیفلدی با ابعاد کمتر فشرده میکنند.
فرضیهٔ منیفلد معمولاً با فرض دیگری همراه است: مسئلهٔ اصلی، مثلاً طبقهبندی یا رگرسیون، در فضای کمبعد منیفلد سادهتر خواهد بود. این فرض همیشه درست نیست. در ردیف بالایی شکل ۸-۶، مرز تصمیم در فضای سهبعدی پیچیده است ولی پس از باز کردن Swiss Roll به یک خط مستقیم تبدیل میشود. در ردیف پایینی، برعکس، مرز x1 = 5 در فضای اصلی یک صفحهٔ عمودی ساده است، اما روی منیفلد بازشده به چند قطعهٔ خط مستقل تبدیل میشود.
شکل 8-6. مرز تصمیم در ابعاد کمتر همیشه سادهتر نمیشود
در نتیجه کاهش ابعاد معمولاً آموزش را سریعتر میکند، ولی تضمینی ندارد که راهحل نهایی سادهتر یا بهتر شود؛ نتیجه کاملاً به ساختار داده بستگی دارد.
PCA؛ تحلیل مؤلفههای اصلی
Principal Component Analysis یا PCA محبوبترین الگوریتم کاهش ابعاد است. PCA ابتدا ابرصفحهای را پیدا میکند که بیشترین نزدیکی را به داده دارد و سپس داده را روی آن فرافکنی میکند.
حفظ واریانس
پیش از فرافکنی باید ابرصفحهٔ مناسب انتخاب شود. شکل ۸-۷ یک مجموعهٔ دوبعدی و سه محور یکبعدی مختلف را نشان میدهد. در سمت راست، فرافکنی داده روی هر محور نمایش داده شده است. محور پیوسته بیشترین واریانس را حفظ میکند، محور نقطهچین کمترین واریانس را و محور خطچین مقدار میانی را.
شکل 8-7. انتخاب زیرفضای مناسب برای Projection
انتخاب محوری که بیشترین واریانس را نگه میدارد منطقی است، زیرا احتمالاً اطلاعات کمتری از دست میرود. تعبیر معادل این انتخاب آن است که این محور میانگین فاصلهٔ مربعی بین دادهٔ اصلی و فرافکنی آن را کمینه میکند. این همان ایدهٔ بنیادین PCA است.
مؤلفههای اصلی
PCA ابتدا محوری را پیدا میکند که بیشترین سهم از واریانس مجموعهٔ آموزشی روی آن قرار دارد. سپس محور دوم را عمود بر محور اول انتخاب میکند تا بیشترین مقدار واریانس باقیمانده را توضیح دهد. در فضای با ابعاد بیشتر، محور سوم عمود بر دو محور قبلی، سپس محور چهارم و به همین ترتیب تا تعداد ابعاد داده پیدا میشود. محور iام، مؤلفهٔ اصلی iام یا PC نام دارد.
در شکل ۸-۷، مؤلفهٔ اول روی بردار c1 و مؤلفهٔ دوم روی بردار c2 قرار دارد. در شکل ۸-۲ دو مؤلفهٔ اصلی اول داخل صفحهٔ فرافکنی هستند و مؤلفهٔ سوم عمود بر آن است. پس از فرافکنی در شکل ۸-۳، PC اول با محور z1 و PC دوم با محور z2 متناظر است.
برای هر مؤلفهٔ اصلی، PCA یک بردار واحد با مرکز صفر در جهت آن مؤلفه پیدا میکند. چون دو بردار واحد مخالف روی یک محور قرار دارند، جهت علامت بردارهای خروجی PCA پایدار نیست. با تغییر کوچک داده ممکن است جهت بردار برعکس شود؛ بااینحال معمولاً همان محور را تعریف میکند. اگر واریانس دو محور خیلی نزدیک باشد، دو بردار ممکن است بچرخند یا جابهجا شوند، ولی صفحهای که تعریف میکنند معمولاً ثابت میماند.
پیدا کردن مؤلفهها با SVD
برای یافتن مؤلفههای اصلی میتوان از تجزیهٔ ماتریسی استاندارد Singular Value Decomposition یا SVD استفاده کرد. این روش ماتریس آموزشی X را به حاصلضرب سه ماتریس U Σ Vᵀ تجزیه میکند. ماتریس V بردارهای واحد تعریفکنندهٔ مؤلفههای اصلی را در خود دارد.
معادله ۸-۱ — ماتریس مؤلفههای اصلی
V = [ c1 c2 … cn ]
کد زیر با تابع svd() در NumPy تمام مؤلفههای اصلی مجموعهٔ سهبعدی را به دست میآورد و دو بردار واحد نخست را استخراج میکند:
import numpy as np
X = [...] # create a small 3D dataset
X_centered = X - X.mean(axis=0)
U, s, Vt = np.linalg.svd(X_centered)
c1 = Vt[0]
c2 = Vt[1]
PCA فرض میکند داده حول مبدأ مرکز شده است. کلاسهای PCA در Scikit-Learn این مرکزسازی را خودکار انجام میدهند. اگر PCA را خودتان پیادهسازی میکنید یا از کتابخانهٔ دیگری استفاده میکنید، مرکزسازی داده را فراموش نکنید.
فرافکنی به d بُعد
پس از شناسایی مؤلفههای اصلی، میتوان داده را با فرافکنی روی ابرصفحهای که توسط نخستین d مؤلفه ساخته میشود به d بُعد کاهش داد. این انتخاب بیشترین مقدار ممکن از واریانس را نگه میدارد. در مثال سهبعدی، فرافکنی روی صفحهٔ ساختهشده از دو مؤلفهٔ اصلی اول بخش بزرگی از واریانس را حفظ میکند.
معادله ۸-۲ — فرافکنی مجموعهٔ آموزشی به d بُعد
Xd-proj = X Wd
ماتریس Wd از نخستین d ستون ماتریس V تشکیل میشود. برای فرافکنی مثال سهبعدی روی دو مؤلفهٔ اول:
W2 = Vt[:2].T
X2D = X_centered @ W2
استفاده از PCA در Scikit-Learn
کلاس PCA در Scikit-Learn نیز از SVD استفاده میکند و مرکزسازی داده را خودکار انجام میدهد:
from sklearn.decomposition import PCA
pca = PCA(n_components=2)
X2D = pca.fit_transform(X)
پس از Fit، ویژگی components_ ترانهادهٔ Wd را نگه میدارد؛ یعنی برای هر یک از d مؤلفهٔ اصلی نخست، یک سطر دارد.
نسبت واریانس توضیحدادهشده
اطلاعات مهم دیگر، Explained Variance Ratio هر مؤلفهٔ اصلی است که در explained_variance_ratio_ در دسترس است. این نسبت مشخص میکند چه سهمی از واریانس کل داده در راستای هر مؤلفه قرار دارد:
>>> pca.explained_variance_ratio_
array([0.7578477 , 0.15186921])
در این نمونه تقریباً ۷۶٪ واریانس روی مؤلفهٔ اول و حدود ۱۵٪ روی مؤلفهٔ دوم قرار دارد. در نتیجه تنها حدود ۹٪ برای مؤلفهٔ سوم باقی میماند و میتوان حدس زد اطلاعات آن نسبتاً کم است.