الـ maximum margin classifier (مصنّف الهامش الأقصى) | ML-101

نرسم أحسن خط ممكن

تخيّل إن عندك مجموعتين نقط على مستوى بُعدين — حمرا وزرقا — ولازم ترسم خط يفصل بينهم. فيه خطوط مالهاش عدد ممكن تنفع. بس أنهي فيهم الأحسن؟ الإجابة اللي بتقدّمها الـ support vector machines (آلات المتجهات الداعمة) (SVMs) أنيقة: اختار الخط الأبعد ما يمكن عن المجموعتين. ودي فكرة الـ maximum margin classifier (مصنّف الهامش الأقصى).

والمنطق هنا إن الـ decision boundary (حد القرار) اللي بعيد عن الفئتين بيعمّم أحسن. أما الحد اللي قريب من فئة منهم، فهيغلط في تصنيف نقط مش مختلفة كتير عن بيانات التدريب. ولما نكبّر الفجوة — يعني الـ margin (الهامش) — بنبني متانة قصاد التغييرات الصغيرة في البيانات.

الـ hyperplane الفاصل

في بُعدين، الـ decision boundary خط. وفي أبعاد أعلى، هو hyperplane (مستوٍ فائق): فضاء مسطّح أبعاده (n−1) جوه فضاء features أبعاده n. والـ hyperplane بيتعرّف بـ vector الـ weights w والـ bias b. وأي نقطة x على المستوى بتحقق:

معادلة الـ hyperplane

\mathbf{w}^\top \mathbf{x} + b = 0

w هو vector عمودي على الـ hyperplane. وb هو الـ bias (الإزاحة عن نقطة الأصل). والنقط اللي على ناحيتين المستوى بتدّي إشارات عكس بعض.

وفي الـ classification، بنحدّد الفئة على حسب الناحية اللي النقطة واقعة فيها: لو w^Tx + b > 0 نتنبأ بالفئة +1؛ ولو < 0 نتنبأ بالفئة −1. والـ hyperplane نفسه (اللي التعبير فيه بيساوي صفر) هو الـ decision boundary.

الـ margin

الـ margin هو العرض الكلي للشريط اللي بين الفئتين، متقاس عمودي على الـ decision boundary. والـ SVMs بتعرّف hyperplaneين متوازيين للـ margin، واحد لكل فئة: w^Tx + b = +1 وw^Tx + b = −1. وبيانات التدريب لازم تقع عليهم أو برّاهم. والـ margin — المسافة بين المستويين — هو:

عرض الـ margin الهندسي

\text{margin} = \dfrac{2}{\|\mathbf{w}\|}

عرض الـ margin بيساوي 2 مقسوم على طول vector الـ weights. فتكبير الـ margin هو نفسه تصغير ‖w‖.

وعشان نكبّر الـ margin، بنصغّر ‖w‖ بشرط إن كل نقط التدريب تتصنّف صح وتقع بره شريط الـ margin. ودي مسألة quadratic optimization محدّبة ليها حل أمثل عالمي واحد — ميزة كبيرة قصاد طرق زي الـ neural networks اللي ممكن يبقى فيها local minima كتير.

الـ support vectors

نقط التدريب اللي واقعة بالظبط على مستويين الـ margin (اللي عندها w^Tx + b = ±1) اسمها الـ support vectors (متجهات الدعم). دي النقط الأقرب للـ decision boundary من كل فئة، وهي لوحدها اللي بتحدّد مكان الـ hyperplane واتجاهه.

ودي خاصية عميقة: حل الـ SVM بيعتمد على جزء صغير بس من بيانات التدريب. لو شلت أي نقطة مش support vector، الـ decision boundary مش هيتغيّر. والتناثر ده بيخلّي الـ algorithm كفء وقت التنبؤ — كفاية تخزّن الـ support vectors لوحدها.

ليه "support vectors"؟

كلمة "support" جاية من إن النقط دي بتسند حدود الـ margin وبتثبّتها. حرّك support vector شوية، والحد كله هيتحرّك. وحرّك أي نقطة تانية (طالما فضلت بره شريط الـ margin)، ومفيش حاجة هتتغيّر. وده منطقي هندسيًا: الحد بيتحدّد كله من أكتر الأمثلة اللي فيها معلومات وواقفة على الحافة.

الـ hard-margin SVM

لما البيانات تبقى linearly separable (قابلة للفصل الخطي) — يعني فيه hyperplane واحد على الأقل بيفصلها تمامًا — نقدر نستخدم الـ hard-margin SVM (الهامش الصلب). وده بيلاقي الـ hyperplane اللي الـ margin بتاعه أقصى من غير أي غلط في التصنيف. ومسألة الـ optimization هي:

مسألة الـ optimization (hard margin)

\min_{\mathbf{w},b}\;\tfrac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.}\quad y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1 \;\forall\, i

بنصغّر مربع طول w (وده نفسه تكبير الـ margin) بشرط إن كل نقطة تدريب تتصنّف صح وبره شريط الـ margin. وy_i ∈ {-1, +1} هي labels الفئات.

نقطة الضعف الأساسية في الـ hard margin: بيشترط فصل خطي كامل. والبيانات الحقيقية نادرًا ما بتحقق ده — دايمًا فيه noise أو outliers أو فئات متداخلة. ونقطة واحدة في مكان غلط ممكن تخلّي المسألة مالهاش حل. وده اللي بيستدعي امتداد الـ soft margin.

الـ soft-margin SVM

الـ soft margin (الهامش اللين) بيرخّي القيود الصارمة بإنه يدخّل slack variables (متغيرات الترخيص) ξ_i ≥ 0، واحد لكل نقطة تدريب. الـ slack variable بيمثّل الشرط اتكسر قد إيه: ξ_i = 0 معناه متصنّفة صح وبره الـ margin؛ 0 < ξ_i ≤ 1 معناه النقطة جوه الـ margin بس متصنّفة صح؛ وξ_i > 1 معناه غلط في التصنيف.

مسألة الـ optimization (soft margin)

\min_{\mathbf{w},b,\boldsymbol{\xi}}\;\tfrac{1}{2}\|\mathbf{w}\|^2 + C\sum_{i=1}^{n}\xi_i \quad \text{s.t.}\quad y_i(\mathbf{w}^\top \mathbf{x}_i + b) \geq 1-\xi_i,\;\xi_i\geq 0

حد العقوبة C·Σξ_i بيسمح لشوية نقط إنها تكسر الـ margin. وC بيتحكم في التوازن بين عرض الـ margin والعقوبة الكلية على الكسر.

الـ parameter C

الـ regularization parameter (معامل التنظيم) C هو أهم hyperparameter في الـ SVM. بيتحكم في التوازن بين تكبير الـ margin وتقليل الـ training error:

C كبير: عقوبة الغلط في التصنيف عالية، فالـ model بيحاول يصنّف كل النقط صح. بيطلع margin أضيق بس training errors أقل. bias أقل بس variance أعلى — ممكن يعمل overfitting (الإفراط في التخصيص) مع البيانات اللي فيها noise.

C صغير: العقوبة واطية فبيسمح بكسر الـ margin. بيدّي الأولوية لـ margin واسع على حساب التصنيف المثالي. بيطلّع حد أنعم وفيه regularization أكتر — bias أعلى بس variance أقل، وده أحسن للبيانات اللي فيها noise أو متداخلة.

ولما C → ∞، الـ soft margin بيقرّب من الـ hard margin. وعمليًا، C بيتختار بالـ cross-validation، عادةً بالبحث على مقياس لوغاريتمي (مثلًا: 0.001، 0.01، 0.1، 1، 10، 100).

الـ feature scaling ضروري

الـ SVMs حسّاسة لمقياس الـ features لأن الـ margin بيتقاس في فضاء الـ features الأصلي. feature قيمها في [0، 1000] هتسيطر على طول الـ vector w قصاد feature قيمها في [0، 1]. فاعمل دايمًا normalization للـ features لمتوسط صفر وvariance واحد قبل تدريب الـ SVM — ده أشهر سبب للأداء الضعيف بتاعها.

نقط القوة والقيود

الـ maximum margin classifier ليه كذا خاصية مقنعة. ليه أساس نظري متين جاي من statistical learning theory — تكبير الـ margin بيصغّر على طول حد أعلى للـ generalization error. وكمان فعّال في الفضاءات اللي أبعادها كتير، وده اللي خلّاه في المقدمة في text classification سنين طويلة. والتمثيل المتناثر بالـ support vectors لوحدها بيخلّي التنبؤ كفء.

بس الـ SVMs بتاعة الـ hard margin والـ soft margin متقيّدة بالمسائل اللي بتتفصل خطيًا (أو تقريبًا خطيًا). مسائل حقيقية كتير محتاجة حدود مش خطية — الفئات ممكن تبقى على شكل clusters أو حلزونات أو دواير متحدة المركز مفيش hyperplane يقدر يفصلها. والقيود دي بتتحل بشكل أنيق بـ الـ kernel trick (خدعة النواة) اللي هندرسه في الدرس الجاي.

في الدرس الجاي، هنشوف إزاي الـ kernel trick بيخلّي الـ SVMs تلاقي decision boundaries مش خطية، بإنها تنقل البيانات ضمنيًا لفضاء أبعاده أعلى — من غير ما تحسب النقلة دي صراحةً.

أهم اللي اتعلمناه

الـ maximum margin classifier بيلاقي الـ hyperplane اللي بيكبّر المسافة لأقرب نقط من كل فئة.
عرض الـ margin بيساوي 2/‖w‖ — تكبير الـ margin هو نفسه تصغير طول vector الـ weights.
الـ support vectors هي نقط التدريب اللي على مستويين الـ margin؛ وهي لوحدها اللي بتحدّد الـ decision boundary.
الـ hard margin بيشترط فصل خطي كامل؛ والـ soft margin بيسمح بالكسر عن طريق الـ slack variables ξ_i.
الـ parameter C بيوازن بين عرض الـ margin والـ training error: C كبير = margin ضيق + أخطاء أقل؛ C صغير = margin واسع + شوية أخطاء مسموحة.
الـ feature scaling ضروري — الـ SVMs حسّاسة لمقياس الـ features.
الـ linear SVM محدود بالحدود الخطية؛ والـ kernel trick (الدرس الجاي) بيوسّعه للمسائل اللي مش خطية.