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

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

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

با در نظر گرفتن مجموعه‌ای از نمونه‌های داده‌ی $\{x^{(i)}, \dots, x^{(m)} \}$ متناظر با مجموعه‌ی خروجی‌های $\{y^{(i)}, \dots, y^{(m)} \}$، هدف ساخت دسته‌بندی است که پیش‌بینی $y$ از روی $x$ را یاد می‌گیرد.

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

	وایازش (رگرسیون)	دسته‌بندی
خروجی	اعداد پیوسته	دسته
نمونه‌ها	وایازش خطی	وایازش لجستیک، ماشین بردار پشتیبان، بیز ساده

نوع مدل انواع مختلف مدل‌ها در جدول زیر به اختصار آمده‌اند.

	مدل متمایزکننده	مدل مولد
هدف	تخمین مستقیم $P(y\|x)$	تخمین $P(x\|y)$ و سپس نتیجه‌گیریِ $P(y\|x)$
چیزی که یاد گرفته می‌شود	مرز تصمیم‌گیری	توزیع احتمال داده‌ها
تصویر
نمونه‌ها	وایازش‌ها، ماشین‌های بردار پشتیبان	GDA، بِیز ساده

نماد‌ها و مفاهیم کلی

فرضیه فرضیه که با $h_\theta$ نمایش داده می‌شود، همان مدلی است که ما انتخاب می‌کنیم. به ازای هر نمونه داده ورودی $x^{(i)}$، حاصل پیش‌یینی مدل $h_\theta(x^{(i)})$ می‌باشد.

تابع خطا تابع خطا (Loss function) تابعی است به صورت $L:(z,y)\in\mathbb{R}\times Y\longmapsto L(z,y)\in\mathbb{R}$ که به عنوان ورودی مقدار پیش‌بینی‌شده‌ی $z$ متناظر با مقدار داده‌ی حقیقی $y$ را می‌گیرد و اختلاف این دو را خروجی می‌دهد. توابع خطای معمول در جدول زیر آمده‌اند:

خطای کمترین مربعات	خطای لجستیک	Hinge خطای	آنتروپی متقاطع
$\displaystyle\frac{1}{2}(y-z)^2$	$\displaystyle\log(1+\exp(-yz))$	$\displaystyle\max(0,1-yz)$	$\displaystyle-\Big[y\log(z)+(1-y)\log(1-z)\Big]$

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

تابع هزینه تابع هزینه‌ی $J$ (Cost function) معمولاً برای ارزیابی عملکرد یک مدل استفاده می‌شود و با توجه به تابع خطای $L$ به صورت زیر تعریف می‌شود:

\[\boxed{J(\theta)=\sum_{i=1}^mL(h_\theta(x^{(i)}), y^{(i)})}\]

گرادیان کاهشی با نمایش نرخ یادگیری به صورت $\alpha \in \mathbb{R}$، رویه‌ی به‌روزرسانی گرادیان کاهشی (Gradient descent) که با نرخ‌یادگیری و تابع هزینه‌ی $J$ بیان می‌شود به شرح زیر است:

\[\boxed{\theta\longleftarrow\theta-\alpha\nabla J(\theta)}\]

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

درست‌نمایی از مقدار درست‌نمایی یک مدل $L(\theta)$ با پارامتر‌های $\theta$ در پیدا کردن عوامل بهینه $\theta$ ‌از طریق روش بیشینه‌سازی درست‌نمایی مدل استفاده می‌شود. البته در عمل از لگاریتم درست‌نمایی $\ell(\theta) = \log(L(\theta))$ که به‌روزرسانی آن ساده‌تر است استفاده می‌شود. داریم::

\[\boxed{\theta^{\textrm{opt}}=\underset{\theta}{\textrm{arg max }}L(\theta)}\]

الگوریتم نیوتن الگوریتم نیوتن یک روش عددی است که $\theta$ را به گونه‌ای پیدا می‌کند که $\ell'(\theta)=0$ باشد. رویه‌ی به‌روزرسانی آن به صورت زیر است:

\[\boxed{\theta\leftarrow\theta-\frac{\ell'(\theta)}{\ell''(\theta)}}\]

نکته: تعمیم چندبُعدی این روش، که به روش نیوتون-رافسون معروف است، قانون به‌روزرسانی زیر را دارد:

\[\theta\leftarrow\theta-\left(\nabla_\theta^2\ell(\theta)\right)^{-1}\nabla_\theta\ell(\theta)\]

مدل‌های خطی

وایازش خطی

در این‌جا فرض می‌کنیم $y|x;\theta\sim\mathcal{N}(\mu,\sigma^2)$

معادلات نرمال اگر $X$ یک ماتریس باشد، مقداری از $\theta$ که تابع هزینه را کمینه می‌کند یک راه‌حل به فرم بسته دارد به طوری که:

\[\boxed{\theta=(X^TX)^{-1}X^Ty}\]

الگوریتم LMS با نمایش نرخ یادگیری با $\alpha$، رویه‌ی به‌روزرسانی الگوریتم کمینه‌ی میانگین مربعات (LMS - Least Mean Squares) برای یک مجموعه‌ی آموزش با $m$ نمونه داده، که به رویه‌ی به‌روزرسانی Widrow-Hoff نیز معروف است، به صورت زیر خواهد بود:

\[\boxed{\forall j,\quad \theta_j \leftarrow \theta_j+\alpha\sum_{i=1}^m\left[y^{(i)}-h_\theta(x^{(i)})\right]x_j^{(i)}}\]

نکته: این رویه‌ی به‌روزرسانی، حالت خاصی از الگوریتم گرادیان کاهشی است.

LWR وایازش محلی‌وزن‌دار یا LWR - Locally Weighted Regression نوعی دیگر از انواع وایازش‌های خطی است که در محاسبه‌ی تابع هزینه‌ی خود هر کدام از نمونه‌های آموزش را وزن $w^{(i)}(x)$ می‌دهد، که این وزن با عامل $\tau \in \mathbb{R}$ به شکل زیر تعریف می‌شود:

\[\boxed{w^{(i)}(x)=\exp\left(-\frac{(x^{(i)}-x)^2}{2\tau^2}\right)}\]

دسته‌بندی و وایازش لجستیک

تابع سیگموئید تابع سیگموئید $g$ که به تابع لجستیک هم معروف است به صورت زیر تعریف می‌شود:

\[\forall z\in\mathbb{R},\quad\boxed{g(z)=\frac{1}{1+e^{-z}}\in]0,1[}\]

وایازش لجستیک فرض می‌کنیم که $y|x; \theta \sim \textrm{Bernoulli}(\phi)$. داریم:

\[\boxed{\phi=p(y=1|x;\theta)=\frac{1}{1+\exp(-\theta^Tx)}=g(\theta^Tx)}\]

نکته: هیچ راه‌حل بسته‌ای برای وایازش لجستیک وجود ندارد.

وایازش Softmax وایازش Softmax یا وایازش چنددسته‌ای، در مواقعی که بیش از ۲ کلاس خروجی داریم برای تعمیم وایازش لجستیک استفاده می‌شود. طبق قرارداد داریم $\theta_K=0$. در نتیجه عامل برنولی $\phi_i$ برای هر کلاس $i$ به صورت زیر خواهد بود:

\[\boxed{\displaystyle\phi_i=\frac{\exp(\theta_i^Tx)}{\displaystyle\sum_{j=1}^K\exp(\theta_j^Tx)}}\]

مدل‌های خطی تعمیم‌یافته

خانواده‌ی نمایی به گروهی از توزیع‌ها خانواده‌ی نمایی (Exponential family) گوییم اگر بتوان آن‌ها را با استفاده از عامل طبیعی $\eta$، که معمولاً عامل متعارف یا تابع پیوند نیز گفته می‌شود، آماره‌ی کافی $T(y)$، و تابع دیواره‌بندی لگاریتمی $a(\eta)$ به صورت زیر نوشت:

\[\boxed{p(y;\eta)=b(y)\exp(\eta T(y)-a(\eta))}\]

نکته: معمولاً داریم $T(y)=y$. هم‌چنین می‌توان به $\exp(-a(\eta))$ به عنوان یک عامل نرمال‌کننده نگاه کرد که باعث می‌شود جمع احتمال‌ها حتماً برابر با یک شود.

رایج‌ترین توزیع‌های نمایی در جدول زیر به اختصار آمده‌اند:

توزیع	$\eta$	$T(y)$	$a(\eta)$	$b(y)$
برنولی	$\log\left(\frac{\phi}{1-\phi}\right)$	$y$	$\log(1+\exp(\eta))$	$1$
گاوسی	$\mu$	$y$	$\frac{\eta^2}{2}$	$\frac{1}{\sqrt{2\pi}}\exp\left(-\frac{y^2}{2}\right)$
پواسون	$\log(\lambda)$	$y$	$e^{\eta}$	$\displaystyle\frac{1}{y!}$
هندسی	$\log(1-\phi)$	$y$	$\log\left(\frac{e^\eta}{1-e^\eta}\right)$	$1$

فرضیه‌های مدل‌های خطی تعمیم‌یافته مدل‌های خطی تعمیم‌یافته (GLM - Generalized Linear Models) به دنبال پیش‌بینی متغیر تصادفی $y$ به عنوان تابعی از $x \in \mathbb{R}^{n + 1}$ هستند و بر سه فرض زیر استوارند:

$(1)\quad\boxed{y|x;\theta\sim\textrm{ExpFamily}(\eta)}$

$(2)\quad\boxed{h_\theta(x)=E[y|x;\theta]}$

$(3)\quad\boxed{\eta=\theta^Tx}$

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

ماشین‌های بردار پشتیبان

هدف ماشین‌های بردار پشتیبان (Support Vector Machines) پیدا کردن خطی هست که حداقل فاصله تا خط را بیشینه می‌کند.

دسته‌بند حاشیه‌ی بهینه دسته‌بند حاشیه‌ی بهینه‌ی $h$ به گونه‌ای است که:

\[\boxed{h(x)=\textrm{sign}(w^Tx-b)}\]

که $(w, b) \in \mathbb{R}^n \times \mathbb{R}$ راه‌حلی برای مساله‌ی بهینه‌سازی زیر باشد:

\[\boxed{\min\frac{1}{2}||w||^2}\quad\quad\textrm{و }\quad \boxed{y^{(i)}(w^Tx^{(i)}-b)\geqslant1}\]

نکته: در این‌جا خط با $w^Tx-b=0$ تعریف شده است.

خطای Hinge در ماشین‌های بردار پشتیبان از تابع خطای Hinge استفاده می‌شود و تعریف آن به صورت زیر است:

\[\boxed{L(z,y)=[1-yz]_+=\max(0,1-yz)}\]

هسته برای هر تابع نگاشت ویژگی‌های $\phi$، هسته‌ی $K$ (Kernel) به صورت زیر تعریف می‌شود:

\[\boxed{K(x,z)=\phi(x)^T\phi(z)}\]

در عمل، به هسته‌ی $K$ که به صورت $K(x,z)= \exp \left(-\frac{\|x-z\|^2}{2\sigma^2}\right)$ تعریف شده باشد، هسته‌ی گاوسی می‌گوییم. این نوع هسته یکی از هسته‌های پراستفاده محسوب می‌شود.

نکته: می‌گوییم برای محاسبه‌ی تابع هزینه از «حقه‌ی هسته» استفاده می‌شود چرا که در واقع برای محاسبه‌ی آن، نیازی به دانستن دقیق نگاشت $\phi$ که بیشتر مواقع هم بسیار پیچیده‌ست، نداریم؛ تنها دانستن مقادیر $K(x,z)$ کافیست.

لاگرانژی لاگرانژی $\mathcal{L}(w,b)$ (Lagrangian) به صورت زیر تعریف می‌کنیم:

\[\boxed{\mathcal{L}(w,b)=f(w)+\sum_{i=1}^l\beta_ih_i(w)}\]

نکته: به ضرایب $\beta_i$ ضرایب لاگرانژ هم می‌گوییم.

یادگیری مولِد

یک مدل مولد (Generative model) ابتدا با تخمین زدن $P(x|y)$ سعی می‌کند یاد بگیرد چگونه می‌توان داده را تولید کرد، سپس با استفاده از $P(x|y)$ و هم‌چنین قضیه‌ی بِیز، $P(y|x)$ را تخمین می‌زند.

تحلیل متمایزکننده‌ی گاوسی

فرضیات در تحلیل متمایزکننده‌ی گاوسی (Gaussian Discriminant Analysis) فرض می‌کنیم $y$ و $x|y = 0$ و $x|y = 1$ به طوری که:

$(1)\quad\boxed{y\sim\textrm{Bernoulli}(\phi)}$

$(2)\quad\boxed{x|y=0\sim\mathcal{N}(\mu_0,\Sigma)}$

$(3)\quad\boxed{x|y=1\sim\mathcal{N}(\mu_1,\Sigma)}$

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

$\widehat{\phi}$	$\widehat{\mu_j}\quad{\small(j=0,1)}$	$\widehat{\Sigma}$
$\displaystyle\frac{1}{m}\sum_{i=1}^m1_{\{y^{(i)}=1\}}$	$\displaystyle\frac{\sum_{i=1}^m1_{\{y^{(i)}=j\}}x^{(i)}}{\sum_{i=1}^m1_{\{y^{(i)}=j\}}}$	$\displaystyle\frac{1}{m}\sum_{i=1}^m(x^{(i)}-\mu_{y^{(i)}})(x^{(i)}-\mu_{y^{(i)}})^T$

دسته‌بند بِیز ساده

فرض مدل بِیز ساده (Naive Bayes) فرض می‌کند تمام خصوصیات هر نمونه‌ی داده از هم‌دیگر مستقل است.

\[\boxed{P(x|y)=P(x_1,x_2,...|y)=P(x_1|y)P(x_2|y)...=\prod_{i=1}^nP(x_i|y)}\]

راه‌حل‌ها بیشنه‌کردن لگاریتم درست‌نمایی به پاسخ‌های زیر می‌رسد، که $k\in\{0,1\},l\in[\![1,L]\!]$

\[\boxed{P(y=k)=\frac{1}{m}\times\#\{j|y^{(j)}=k\}}\quad\textrm{ و }\quad\boxed{P(x_i=l|y=k)=\frac{\#\{j|y^{(j)}=k\textrm{ و }x_i^{(j)}=l\}}{\#\{j|y^{(j)}=k\}}}\]

نکته: دسته‌بند بِیز ساده در مساله‌‌های دسته‌بندی متن و تشخیص هرزنامه به صورت گسترده استفاده می‌شود.

روش‌های مبتنی بر درخت و گروه

این روش‌ها هم در مسائل وایازش و هم در مسائل دسته‌بندی می‌توانند استفاده شوند.

CART درخت‌های وایازش و دسته‌بندی (Classification and Regression Trees)، عموما با نام درخت‌های تصمیم‌گیری شناخته می‌شوند. می‌توان آن‌ها را به صورت درخت‌هایی دودویی نمایش داد. مزیت ‌آن‌ها قابل تفسیر بودنشان است.

جنگل تصادفی (Random forest) یک تکنیک مبتی بر درخت است، که تعداد زیادی درخت تصمیم‌گیری که روی مجموعه‌هایی تصادفی از خصوصیات ساخته‌شده‌اند، را به کار می‌گیرد. روش جنگل تصادفی برخلاف درخت تصمیم‌گیری ساده، بسیار غیر قابل تفسیر است البته عمکرد عموماً خوب آن باعث شده است به الگوریتم محبوبی تبدیل شود.

نکته: جنگل تصادفی یکی از انواع «روش‌های گروهی» است.

ترقی‌دادن ایده‌ی اصلی روش‌های ترقی‌دادن (Boosting) ترکیب چند مدل ضعیف و ساخت یک مدل قوی از آن‌هاست. انواع اصلی آن به صورت خلاصه در جدول زیر آمده‌اند:

ترقی‌دادن سازگارشونده (Adaptive boosting)	ترقی‌دادن گرادیانی (Gradient boosting)
برای خطاها وزن‌ بالایی در نظر می‌گیرد تا در مرحله‌ی بعدیِ ترقی‌دادن، مدل بهبود یابد.	چند مدل ضعیف روی باقی خطاها آموزش می‌یابند

سایر رویکرد‌های غیر عاملی

$k$-همسایه‌ی نزدیک الگوریتم k-همسایه‌ی نزدیک که عموماً با (k-NN - k-nearest neighbors) نیز شناخته می‌شود، یک الگوریتم غیرعاملی است که پاسخ مدل به هر نمونه داده از روی k همسایه‌ی آن در مجموعه دادگان آموزش تعیین می‌شود. این الگوریتم هم در دسته‌بندی و هم در وایازش استفاده می‌شود.

نکته: هرچه پارامتر k برزرگ‌تر باشد پیش‌قدر مدل بیشتر خواهد بود، و هر چه کوچکتر باشد واریانس مدل بیشتر خواهد شد.

نظریه یادگیری

کران اجتماع اگر $A_1, \dots, A_k$، $k$ عدد رخداد باشد، داریم:

\[\boxed{P(A_1\cup ...\cup A_k)\leqslant P(A_1)+...+P(A_k)}\]

نامساوی هوفدینگ اگر $Z_1, \dots, Z_m$، $m$ عدد متغیر تصادفی مستقل با توزیع یکسان و نمونه‌برداری‌شده از توزیع برنولی با پارامتر $\phi$ باشند و هم‌چنین $\widehat{\phi}$ میانگین آن‌ها و $\gamma>0$ ثابت باشد، داریم:

\[\boxed{P(|\phi-\widehat{\phi}|>\gamma)\leqslant2\exp(-2\gamma^2m)}\]

نکته: این نامساوی به کران چرنوف نیز معروف است.

خطای آموزش به ازای هر دسته‌بند $h$، خطای آموزش $\widehat{\epsilon}(h)$ (یا همان خطای تجربی)، به صورت زیر تعریف می‌شود:

\[\boxed{\widehat{\epsilon}(h)=\frac{1}{m}\sum_{i=1}^m1_{\{h(x^{(i)})\neq y^{(i)}\}}}\]

احتمالاً تقریباً درست (PAC - Probably Approximately Correct) چارچوبی است که در ذیل آن نتایج متعددی در نظریه یادگیری اثبات شده است و فرض‌های زیر را در بر دارد:

• مجموعه‌ی آموزش و مجموعه‌ی آزمایش از یک توزیع هستند.

• نمونه‌های آموزشی مستقل از یکدیگر انتخاب شده‌اند.

خرد شدن (Shattering) برای مجموعه‌ی $S=\{x^{(1)},...,x^{(d)}\}$ و مجموعه‌ای از دسته‌بندهای $\mathcal{H}$ می‌گوییم، $\mathcal{H}$ مجموعه‌ی $S$ را اصطلاحاً خرد می‌کند اگر به ازای هر مجموعه‌ای از برچسب‌های $\{y^{(1)}, ..., y^{(d)}\}$ داشته باشیم:

\[\boxed{\exists h\in\mathcal{H}, \quad \forall i\in[\![1,d]\!],\quad h(x^{(i)})=y^{(i)}}\]

قضیه‌ی کران بالا اگر $\mathcal{H}$ یک مجموعه‌ی متناهی از فرضیه ها (دسته‌بندها) باشد به طوری که $|\mathcal{H}|=k$ باشد و $\delta$ و $m$ ثابت باشند، آنگاه با احتمالِ حداقل $1-\delta$ داریم:

\[\boxed{\epsilon(\widehat{h})\leqslant\left(\min_{h\in\mathcal{H}}\epsilon(h)\right)+2\sqrt{\frac{1}{2m}\log\left(\frac{2k}{\delta}\right)}}\]

بُعد VC بُعد Vapnik-Chervonenkis برای هر مجموعه‌ی نامتناهی از فرضیه‌ها (دسته‌بندها) $\mathcal{H}$ که با $\textrm{VC}(\mathcal{H})$ نمایش داده می‌شود، برابر است با اندازه‌ی بزرگ‌ترین مجموعه‌‌ای که می‌توان با استفاده از $\mathcal{H}$ آن‌ را خرد کرد.

نکته:‌بُعد VC مجموعه‌ی $H=${همه‌ی دسته‌بندهای خطی در ۲ بعد} برابر با ۳ است.

قضیه (Vapnik) به ازای $\mathcal{H}$ به طوری که $\textrm{VC}(\mathcal{H}) = d$ و هم‌چنین $m$ تعداد نمونه‌های آموزشی باشد، با احتمالِ حداقل $1 - \delta$ داریم:

\[\boxed{\epsilon(\widehat{h})\leqslant \left(\min_{h\in\mathcal{H}}\epsilon(h)\right) + O\left(\sqrt{\frac{d}{m}\log\left(\frac{m}{d}\right)+\frac{1}{m}\log\left(\frac{1}{\delta}\right)}\right)}\]