CS ۲۲۹

Star

بواسطة افشین عميدي و شروين عميدي

تمت الترجمة بواسطة رضوان لغوينسات

تمت المراجعة بواسطة فارس القنيعير

مقدمة للتعلّم غير المُوَجَّه

الحافز الهدف من التعلّم غير المُوَجَّه هو إيجاد الأنماط الخفية في البيانات غير المٌعلمّة $\{x^{(1)},...,x^{(m)}\}$.

متباينة جينسن لتكن $f$ دالة محدبة و $X$ متغير عشوائي. لدينا المتباينة التالية:

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

التجميع

تعظيم القيمة المتوقعة

المتغيرات الكامنة المتغيرات الكامنة هي متغيرات مخفية/غير معاينة تزيد من صعوبة مشاكل التقدير، غالباً ما ترمز بالحرف $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$

خوارزمية تعظيم القيمة المتوقعة (Expectation-Maximization) هي عبارة عن طريقة فعالة لتقدير المُدخل $\theta$ عبر تقدير تقدير الأرجحية الأعلى (maximum likelihood estimation)، ويتم ذلك بشكل تكراري حيث يتم إيجاد حد أدنى للأرجحية (الخطوة M)، ثم يتم تحسين (optimizing) ذلك الحد الأدنى (الخطوة E)، كما يلي:

الخطوة E : حساب الاحتمال البعدي $Q_{i}(z^{(i)})$ بأن تصدر كل نقطة $x^{(i)}$ من مجموعة (cluster) $z^{(i)}$ كما يلي:

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

الخطوة M : يتم استعمال الاحتمالات البعدية $Q_i(z^{(i)})$ كأوزان خاصة لكل مجموعة (cluster) على النقط $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

نرمز لمجموعة النقط $i$ بـ $c^{(i)}$، ونرمز بـ $\mu_j$ مركز المجموعات $j$.

خوارزمية بعد الاستهلال العشوائي للنقاط المركزية (centroids) للمجوعات $\mu_1,\mu_2,...,\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\}}}}\]

دالة التحريف لكي نتأكد من أن الخوارزمية تقاربت، ننظر إلى دالة التحريف المعرفة كما يلي:

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

التجميع الهرمي

خوارزمية هي عبارة عن خوارزمية تجميع تعتمد على طريقة تجميع هرمية تبني مجموعات متداخلة بشكل متتال.

الأنواع هنالك عدة أنواع من خوارزميات التجميع الهرمي التي ترمي إلى تحسين دوال هدف (objective function) مختلفة، هذه الأنواع ملخصة في الجدول التالي:

ربط وارْد (ward linkage)	الربط المتوسط	الربط الكامل
تصغير المسافة داخل المجموعة	تصغير متوسط المسافة بين أزواج المجموعات	تصغير المسافة العظمى بين أزواج المجموعات

مقاييس تقدير المجموعات

في التعلّم غير المُوَجَّه من الصعب غالباً تقدير أداء نموذج ما، لأن القيم الحقيقية تكون غير متوفرة كما هو الحال في التعلًم المُوَجَّه.

معامل الظّل إذا رمزنا $a$ و $b$ لمتوسط المسافة بين عينة وكل النقط المنتمية لنفس الصنف، و بين عينة وكل النقط المنتمية لأقرب مجموعة، المعامل الظِلِّي $s$ لعينة واحدة معرف كالتالي:

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

مؤشر كالينسكي-هارباز إذا رمزنا بـ $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\]

مؤشر كالينسكي-هارباز $s(k)$ يشير إلى جودة نموذج تجميعي في تعريف مجموعاته، بحيث كلما كانت النتيجة أعلى كلما دل ذلك على أن المجموعات أكثر كثافة وأكثر انفصالاً فيما بينها. هذا المؤشر معرّف كالتالي:

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

تقليص الأبعاد

تحليل المكون الرئيس

إنها طريقة لتقليص الأبعاد ترمي إلى إيجاد الاتجاهات المعظمة للتباين من أجل إسقاط البيانات عليها.

قيمة ذاتية ، متجه ذاتي لتكن $A\in\mathbb{R}^{n\times n}$ مصفوفة، نقول أن $\lambda$ قيمة ذاتية للمصفوفة $A$ إذا وُجِد متجه $z\in\mathbb{R}^n\backslash\{0\}$ يسمى متجهاً ذاتياً، بحيث:

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

مبرهنة الطّيف لتكن $A\in\mathbb{R}^{n\times n}$. إذا كانت $A$ متناظرة فإنها يمكن أن تكون شبه قطرية عن طريق مصفوفة متعامدة حقيقية $U\in\mathbb{R}^{n\times n}$. إذا رمزنا $\Lambda=\textrm{diag}(\lambda_1,...,\lambda_n)$ ، لدينا:

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

ملحوظة: المتجه الذاتي المرتبط بأكبر قيمة ذاتية يسمى بالمتجه الذاتي الرئيسي (principal eigenvector) للمصفوفة $A$.

خوارزمية تحليل المكون الرئيس (Principal Component Analysis, PCA) طريقة لخفض الأبعاد تهدف إلى إسقاط البيانات على $k$ بُعد بحيث يتم تعطيم التباين (variance)، خطواتها كالتالي:

الخطوة 1: تسوية البيانات بحيث تصبح ذات متوسط يساوي صفر وانحراف معياري يساوي واحد.

\[\boxed{x_j^{(i)}\leftarrow\frac{x_j^{(i)}-\mu_j}{\sigma_j}}\quad\textrm{where}\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}\]

الخطوة 2: حساب $\displaystyle\Sigma=\frac{1}{m}\sum_{i=1}^mx^{(i)}{x^{(i)}}^T\in\mathbb{R}^{n\times n}$، وهي متناظرة وذات قيم ذاتية حقيقية.
الخطوة 3: حساب $u_1, ..., u_k\in\mathbb{R}^n$ المتجهات الذاتية الرئيسية المتعامدة لـ $\Sigma$ وعددها $k$ ، بعبارة أخرى، $k$ من المتجهات الذاتية المتعامدة ذات القيم الذاتية الأكبر.
الخطوة 4: إسقاط البيانات على $\textrm{span}_\mathbb{R}(u_1,...,u_k)$.

هذا الإجراء يعظم التباين بين كل الفضاءات البُعدية.

تحليل المكونات المستقلة

هي طريقة تهدف إلى إيجاد المصادر التوليدية الكامنة.

افتراضات لنفترض أن بياناتنا $x$ تم توليدها عن طريق المتجه المصدر $s=(s_1,...,s_n)$ ذا $n$ بُعد، حيث $s_i$ متغيرات عشوائية مستقلة، وذلك عبر مصفوفة خلط غير منفردة (mixing and non-singular) $A$ كالتالي:

\[\boxed{x=As}\]

الهدف هو العثور على مصفوفة الفصل $W=A^{-1}$.

خوارزمية تحليل المكونات المستقلة (ICA) لبيل وسجنوسكي (Bell and Sejnowski) هذه الخوارزمية تجد مصفوفة الفصل $W$ عن طريق الخطوات التالية:

اكتب الاحتمال لـ $x=As=W^{-1}s$ كالتالي:

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

لتكن $\{x^{(i)}, i\in[\![1,m]\!]\}$ بيانات التمرن و $g$ دالة سيجمويد، اكتب الأرجحية اللوغاريتمية (log likelihood) كالتالي:

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

هكذا، باستخدام الصعود الاشتقاقي العشوائي (stochastic gradient ascent)، لكل عينة تدريب $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)}\]