راهنمای کوتاه یادگیری بدون نظارت

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

مبانی یادگیری بدون نظارت

انگیزه هدف از یادگیری بدون نظارت (Unsupervised learning) کشف الگوهای پنهان در داده‌های بدون برچسب $\{x^{(1)},...,x^{(m)}\}$ است.

نابرابری ینسن (Jensen's inequality) فرض کنید $f$ تابعی محدب و $X$ یک متغیر تصادفی باشد. در این صورت نابرابری زیر را داریم:

\[\boxed{E[f(X)]\geqslant f(E[X])}\]

خوشه‌بندی

بیشینه‌سازی امید ریاضی

متغیرهای نهفته متغیرهای نهفته (Latent variable) متغیرهای پنهان یا مشاهده‌نشده‌ای هستند که مسائل تخمین را دشوار می‌کنند، و معمولاً با $z$ نمایش داده می‌شوند. شرایط معمول که در آن‌ها متغیرهای نهفته وجود دارند در زیر آمده‌اند:

موقعیت	$z$ متغیر نهفته‌ی	$x\|z$	توضیحات
ترکیب $k$ توزیع گاوسی	$\textrm{Multinomial}(\phi)$	$\mathcal{N}(\mu_j,\Sigma_j)$	$\mu_j\in\mathbb{R}^n, \phi\in\mathbb{R}^k$
تحلیل عامل	$\mathcal{N}(0,I)$	$\mathcal{N}(\mu+\Lambda z,\psi)$	$\mu_j\in\mathbb{R}^n$

الگوریتم الگوریتم بیشینه‌سازی امید ریاضی (EM - Expectation-Maximization) روشی بهینه برای تخمین پارامتر $\theta$ از طریق تخمین درستی بشینه در اختیار قرار می‌دهد. این کار با تکرار مرحله‌ی به دست آوردن یک کران پایین برای درستی (مرحله‌ی امید ریاضی) و همچنین بهینه‌سازی آن کران پایین (مرحله‌ی بیشینه‌سازی) طبق توضیح زیر انجام می‌شود:

• مرحله‌ی امید ریاضی: ‌احتمال پسین $Q_{i}(z^{(i)})$ که هر نمونه داده $x^{(i)}$ متعلق به خوشه‌ی $z^{(i)}$ باشد به صورت زیر محاسبه می‌شود:

\[\boxed{Q_i(z^{(i)})=P(z^{(i)}|x^{(i)};\theta)}\]

• مرحله‌ی بیشینه‌سازی: با استفاده از احتمالات پسین $Q_{i}(z^{(i)})$ به عنوان وزن‌های وابسته به خوشه‌ها برای نمونه‌های داده‌ی $x^{(i)}$، مدل مربوط به هر کدام از خوشه‌ها، طبق توضیح زیر، دوباره تخمین زده می‌شوند:

\[\boxed{\theta_i=\underset{\theta}{\textrm{argmax }}\sum_i\int_{z^{(i)}}Q_i(z^{(i)})\log\left(\frac{P(x^{(i)},z^{(i)};\theta)}{Q_i(z^{(i)})}\right)dz^{(i)}}\]

خوشه‌بندی $k$-میانگین (k-means clustering)

توجه کنید که $c^{(i)}$ خوشه‌ی نمونه داده‌ی $i$ و $\mu_j$ مرکز خوشه‌ی $j$ است.

الگوریتم بعد از مقداردهی اولیه‌ی تصادفی مراکز خوشه‌ها $\mu_1, \mu_2, \dots, \mu_k \in \mathbb{R}^n$، الگوریتم $k$-میانگین مراحل زیر را تا هم‌گرایی تکرار می‌کند:

\[\boxed{c^{(i)}=\underset{j}{\textrm{arg min}}||x^{(i)}-\mu_j||^2}\quad\textrm{و}\quad\boxed{\mu_j=\frac{\displaystyle\sum_{i=1}^m1_{\{c^{(i)}=j\}}x^{(i)}}{\displaystyle\sum_{i=1}^m1_{\{c^{(i)}=j\}}}}\]

تابع اعوجاج برای تشخیص اینکه الگوریتم به هم‌گرایی رسیده است، به تابع اعوجاج (Distortion function) که به صورت زیر تعریف می‌شود رجوع می‌کنیم:

\[\boxed{J(c,\mu)=\sum_{i=1}^m||x^{(i)}-\mu_{c^{(i)}}||^2}\]

خوشه‌بندی سلسله‌مراتبی (Hierarchical clustering)

الگوریتم یک الگوریتم خوشه‌بندی سلسله‌مراتبی تجمعی است که خوشه‌های تودرتو را به صورت پی‌در‌پی ایجاد می‌کند.

انواع انواع مختلفی الگوریتم خوشه‌بندی سلسله‌مراتبی وجود دارند که هر کدام به دنبال بهینه‌سازی توابع هدف مختلفی هستند، که در جدول زیر به اختصار آمده‌اند:

پیوند بخشی (Ward)	پیوند میانگین (Average)	پیوند کامل (Complete)
کمینه‌کردن فاصله‌ی درونِ خوشه	کمینه‌کردن فاصله‌ی میانگین بین هر دو جفت خوشه	کمینه‌کردن حداکثر فاصله بین هر دو جفت خوشه

معیارهای ارزیابی خوشه‌بندی

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

ضریب نیم‌رخ با نمایش $a$ به عنوان میانگین فاصله‌ی یک نمونه با همه‌ی نمونه‌های دیگر در همان کلاس، و با نمایش $b$ به عنوان میانگین فاصله‌ی یک نمونه با همه‌ی نمونه‌های دیگر از نزدیک‌ترین خوشه، ضریب نیم‌رخ $s$ به صورت زیر تعریف می‌شود:

\[\boxed{s=\frac{b-a}{\max(a,b)}}\]

شاخص Calinski-Harabasz با در نظر گرفتن $k$ به عنوان تعداد خوشه‌ها، ماتریس پراکندگی درون خوشه‌ای $B_k$ و ماتریس پراکندگی میان‌خوشه‌ای $W_k$ به صورت زیر تعریف می‌شوند:

\[B_k=\sum_{j=1}^kn_{c^{(i)}}(\mu_{c^{(i)}}-\mu)(\mu_{c^{(i)}}-\mu)^T,\quad\quad W_k=\sum_{i=1}^m(x^{(i)}-\mu_{c^{(i)}})(x^{(i)}-\mu_{c^{(i)}})^T\]

شاخص Calinski-Harabasz $s(k)$ بیان می‌کند که یک مدل خوشه‌بندی چگونه خوشه‌های خود را مشخص می‌کند، به گونه‌ای که هر چقدر مقدار این شاخص بیشتر باشد، خوشه‌ها متراکم‌تر و از هم تفکیک‌یافته‌تر خواهند بود. این شاخص به صورت زیر تعریف می‌شود:

\[\boxed{s(k)=\frac{\textrm{Tr}(B_k)}{\textrm{Tr}(W_k)}\times\frac{N-k}{k-1}}\]

کاهش ابعاد

تحلیل مولفه‌های اصلی

روشی برای کاهش ابعاد است که جهت‌هایی را با حداکثر واریانس پیدا می‌کند تا داده‌ها را در آن جهت‌ها تصویر کند.

مقدار ویژه، بردار ویژه (Eigenvalue, eigenvector) برای ماتریس دلخواه $A \in \mathbb{R}^{n \times n}$، $\lambda$ مقدار ویژه‌ی ماتریس $A$ است اگر وجود داشته باشد بردار $z \in \mathbb{R}^n\backslash\{0\}$ که به آن بردار ویژه می‌گویند، به طوری که:

\[\boxed{Az=\lambda z}\]

قضیه‌ی طیفی (Spectral theorem) فرض کنید $A \in \mathbb{R}^{n \times n}$ باشد. اگر $A$ متقارن باشد، در این صورت $A$ توسط یک ماتریس حقیقی متعامد $U \in \mathbb{R} ^{n \times n}$ قطری‌پذیر است. با نمایش $\Lambda = \textrm{diag}(\lambda_1, \dots, \lambda_n)$ داریم:

\[\boxed{\exists\Lambda\textrm{ diagonal},\quad A=U\Lambda U^T}\]

نکته: بردار ویژه‌ی متناظر با بزرگ‌ترین مقدار ویژه، بردار ویژه‌ی اصلی ماتریس $A$ نام دارد.

الگوریتم رویه‌ی تحلیل مولفه‌های اصلی (Principal component analysis) یک روش کاهش ابعاد (Dimension reduction) است که داده‌ها را در فضای $k$-بعدی با بیشینه کردن واریانس داده‌ها، به صورت زیر تصویر می‌کند:

• مرحله‌ی ۱: داده‌ها به گونه‌ای نرمال‌سازی می‌شوند که میانگین ۰ و انحراف معیار ۱ داشته باشند.

\[\boxed{x_j^{(i)}\leftarrow\frac{x_j^{(i)}-\mu_j}{\sigma_j}}\quad\textrm{و}\quad\boxed{\mu_j = \frac{1}{m}\sum_{i=1}^mx_j^{(i)}}\quad\textrm{ و }\quad\boxed{\sigma_j^2=\frac{1}{m}\sum_{i=1}^m(x_j^{(i)}-\mu_j)^2}\]

• مرحله‌ی ۲: مقدار $\displaystyle\Sigma=\frac{1}{m}\sum_{i=1}^mx^{(i)}{x^{(i)}}^T\in\mathbb{R}^{n\times n}$، که ماتریسی متقارن با مقادیر ویژه‌ی حقیقی است محاسبه می‌شود.

• مرحله‌ی ۳: بردارهای $u_1, \dots, u_k \in \mathbb{R}^n$ که $k$ بردارهای ویژه‌ی اصلی متعامد $\Sigma$ هستند محاسبه می‌شوند. این بردارهای ویژه متناظر با $k$ مقدار ویژه با بزرگ‌ترین مقدار هستند.

• مرحله‌ی ۴: داده‌ها بر روی فضای $\text{span}_ {\mathbb{R}} (u_1, \dots, u_k)$ تصویر می‌شوند.

این رویه واریانس را در فضای $k$-بعدی به دست آمده بیشینه می‌کند.

تحلیل مولفه‌های مستقل

روشی است که برای پیدا کردن منابع مولد داده به کار می‌رود.

فرضیه‌ها فرض می‌کنیم که داده‌ی $x$ توسط بردار $n$-بعدی $s=(s_1, \dots, s_n)$ تولید شده است، که $s_i$ها متغیرهای تصادفی مستقل هستند، و این تولید داده از طریق بردار منبع به وسیله‌ی یک ماتریس معکوس‌پذیر و ترکیب‌کننده‌ی $A$ به صورت زیر انجام می‌گیرد:

\[\boxed{x=As}\]

هدف پیدا کردن ماتریس ضدترکیب $W=A^{-1}$ است.

الگوریتم تحلیل مولفه‌های مستقل Bell و Sejnowski این الگوریتم ماتریس ضدترکیب $W$ را در مراحل زیر پیدا می‌کند:

• احتمال $x = As = W^{-1}s$ به صورت زیر نوشته می‌شود:

\[p(x)=\prod_{i=1}^np_s(w_i^Tx)\cdot|W|\]

با نمایش تابع سیگموئید با $g$، لگاریتم درست‌نمایی با توجه به داده‌های $\{x^{(i)}, i\in[\![1,m]\!]\}$ به صورت زیر نوشته می‌شود:

\[l(W)=\sum_{i=1}^m\left(\sum_{j=1}^n\log\Big(g'(w_j^Tx^{(i)})\Big)+\log|W|\right)\]

بنابراین، رویه‌ی یادگیری گرادیان تصادفی افزایشی برای هر نمونه از داده‌های آموزش $x^{(i)}$ به گونه‌ای است که برای به‌روزرسانی $W$ داریم:

\[\boxed{W\longleftarrow W+\alpha\left(\begin{pmatrix}1-2g(w_1^Tx^{(i)})\\1-2g(w_2^Tx^{(i)})\\\vdots\\1-2g(w_n^Tx^{(i)})\end{pmatrix}{x^{(i)}}^T+(W^T)^{-1}\right)}\]