الـ kernel trick (خدعة النواة) | ML-101

مشكلة الخطية

في الدرس اللي فات شفنا إن الـ support vector machines (آلات المتجهات الداعمة) بتلاقي الـ hyperplane اللي الـ margin بتاعه أقصى — فكرة قوية، بس مبتشتغلش غير لما الفئتين ينفع يتفصلوا بخط مستقيم أو مستوى مسطّح. والبيانات الحقيقية نادرًا ما بتبقى بالسهولة دي. تخيّل فئتين مترتّبين في حلقات متحدة المركز، أو pattern زي XOR: مفيش hyperplane يقدر يفصلهم.

الطريقة الكلاسيكية للمسائل اللي مش خطية هي الـ feature engineering (هندسة الميزات): إنك تبني features جديدة بإيدك تخلّي المسألة بتتفصل خطيًا. مثلًا، لو بياناتك فيها feature اسمها x، ممكن تزوّد x² كـ feature جديدة. بس الطريقة دي متعبة ومحتاجة خبرة في المجال، وكمان بتبقى مستحيلة في الأبعاد العالية.

والـ kernel trick (خدعة النواة) بيعمل الفكرة دي أوتوماتيك وبيعمّمها بشكل أنيق: بيخلّي الـ SVMs تشتغل في فضاء features أبعاده كتير جدًا (لحد ما لا نهاية) من غير ما تحسب إحداثيات الفضاء ده خالص.

الـ feature maps

رسميًا، الـ feature map (دالة تعيين الميزات) φ بتحوّل نقطة البيانات x من فضاء الـ input الأصلي لفضاء features أبعاده أعلى:

الـ feature map

\phi: \mathbb{R}^n \to \mathcal{F}

φ بتنقل كل input x من ℝⁿ لفضاء features ℱ ممكن يبقى فيه أبعاد أكتر بكتير من الفضاء الأصلي — ويمكن أبعاد مالهاش نهاية.

بعد ما نطبّق φ على كل الـ inputs، بندرّب linear SVM في الفضاء الجديد. الـ decision boundary خطي في فضاء الـ features، بس بيقابل حد مش خطي في فضاء الـ input الأصلي. المشكلة: لو φ نقلت لفضاء أبعاده كتير جدًا، إنك تحسب φ(x) صراحةً وبعدين تعمل dot product لنقطها بيبقى مكلّف جدًا حسابيًا.

مثلًا، الـ polynomial feature map من الدرجة التانية لـ featureين (x₁، x₂) بتطلّع 6 features: (1، x₁، x₂، x₁²، x₁x₂، x₂²). ولدرجة d مع p feature أصلية، حجم فضاء الـ features بيوصل O(p^d) — رقم فلكي بسرعة.

الـ kernel function

وهنا الملاحظة الأساسية: في صياغة مسألة الـ SVM الـ dual (الثنائية)، نقط البيانات بتظهر بس كـ dot product φ(x)^Tφ(z). مش محتاجين إحداثيات φ(x) وφ(z) لوحدهم — محتاجين الـ inner product بتاعهم بس. والـ kernel function (دالة النواة) بتحسب الحاصل ده على طول من الـ inputs الأصلية، من غير ما تبني φ خالص:

الـ kernel function

K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x})^\top \phi(\mathbf{z})

K(x, z) بتحسب الـ inner product بتاع φ(x) وφ(z) في فضاء الـ features من غير ما تحسب φ(x) أو φ(z) صراحةً. ده هو الـ kernel trick.

وده معناه كبير: نقدر نشتغل في فضاء أبعاده كتير جدًا (أو مالهاش نهاية) بتكلفة حسابية زي إنك تقيّم function بسيطة في الفضاء الأصلي. والتعقيد الحسابي بيعتمد على البُعد الأصلي، مش على بُعد فضاء الـ features.

الـ kernel بيبقى صالح إمتى؟

مش كل function K(x، z) بتقابل inner product صحيح في فضاء ما. الـ function K تبقى kernel صالح (اسمه كمان Mercer kernel (نواة ميرسر)) لو وبس لو الـ kernel matrix K (اللي فيها K_ij = K(x_i، x_j)) positive semi-definite (شبه محددة موجبة) لكل training sets الممكنة. وده شرط ميرسر (Mercer's condition).

وبالإحساس، الـ matrix الـ positive semi-definite بتضمن إننا بنحسب inner products في فضاء inner product صحيح. ولو الشرط ده متحققش، ممكن الـ optimization ميبقاش ليه حل واحد أو ميتقاربش. وعمليًا، الـ kernels المعتادة (RBF، polynomial، linear) كلها بتحقق شرط ميرسر، ونادرًا ما بنحتاج نتأكد منه صراحةً.

الـ kernels المشهورة

مجموعة صغيرة من الـ kernels المعتادة كفاية لأغلب المسائل العملية:

الـ kernel	المعادلة	فضاء الـ features
linear	K(x,z) = x^Tz	الفضاء الأصلي (من غير نقل)
polynomial	K(x,z) = (x^Tz + c)^d	كل الـ monomials لحد الدرجة d
RBF / Gaussian	K(x,z) = exp(−γ‖x−z‖²)	أبعاده مالهاش نهاية
sigmoid	K(x,z) = tanh(κx^Tz + θ)	بيقرّب layer في neural network

الـ RBF kernel بالتفصيل

الـ radial basis function (RBF) kernel (نواة دالة الأساس الشعاعي)، أو الـ Gaussian kernel، هو الأكتر استخدامًا. بيقيس التشابه كـ Gaussian function في المسافة الإقليدية بين نقطتين:

الـ RBF kernel

K(\mathbf{x}, \mathbf{z}) = \exp\!\left(-\gamma \|\mathbf{x} - \mathbf{z}\|^2\right)

γ (جاما) بيتحكم في عرض الجرس الـ Gaussian. γ كبير → جرس ضيق → النقط القريبة جدًا بس هي اللي شبه بعض → حد متعرّج. γ صغير → جرس عريض → النقط البعيدة لسه شبه بعض → حد أنعم.

الـ RBF kernel بيقابل فضاء features أبعاده مالهاش نهاية — وتقدر تتأكد من ده بفك Taylor series بتاعة الأُسّي. ومع كده، التدريب والتنبؤ بيفضلوا ممكنين لأننا مبنحسبش غير K(x_i، x_j) ومبنحسبش φ(x) أبدًا. والـ RBF kernel هو universal approximator: ببيانات كفاية وقيمة γ مناسبة، يقدر يمثّل أي decision boundary مستمر.

الـ parameter γ

الـ parameter γ في الـ RBF kernel ساعات بيتكتب 1/(2σ²) فبيرتبط بالـ variance بتاع الـ Gaussian. والقيمة الافتراضية المعتادة γ = 1/عدد_الـ features (الافتراضي في scikit-learn). وزي C، بيتظبط بالـ cross-validation. γ كبير بيخاطر بالـ overfitting (الحد بيحفظ نقط التدريب)؛ وγ صغير بيخاطر بالـ underfitting (الحد أنعم من اللازم).

ليه الصياغة الـ dual مهمة؟

الـ kernel trick محتاج البيانات تظهر كـ dot products بس. وده مضمون لما نشتغل في الشكل الـ dual للـ optimization بتاع الـ SVM. والصياغة الـ dual بتعيد كتابة مسألة الـ SVM الأصلية (تصغير ‖w‖ مع القيود) كمسألة مكافئة على الـ Lagrange multipliers (مضاعفات لاغرانج) α_i:

الـ dual objective بتاع الـ SVM

\max_{\boldsymbol{\alpha}}\;\sum_{i=1}^n \alpha_i - \tfrac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j K(\mathbf{x}_i,\mathbf{x}_j) \quad\text{s.t.}\quad 0\le\alpha_i\le C,\;\sum_i\alpha_i y_i=0

الـ Lagrange multipliers α_i مرتبطة بكل نقطة تدريب. والـ α_i اللي مش صفر بتقابل الـ support vectors. والـ kernel K(x_i, x_j) بياخد مكان الـ inner product φ(x_i)ᵀφ(x_j).

وبعد ما نحل الصياغة الـ dual، التنبؤ لنقطة جديدة x بيبقى:

التنبؤ

f(\mathbf{x}) = \text{sign}\!\left(\sum_{i:\,\alpha_i>0} \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b\right)

التنبؤ هو مجموع موزون لتقييمات الـ kernel قصاد الـ support vectors بس (α_i > 0). وده بيخلّي التنبؤ سريع حتى في فضاءات أبعادها مالهاش نهاية.

المجموع ماشي على الـ support vectors بس (اللي عندها α_i > 0)، وده بيخلّي التنبؤ كفء. وتعقيد المسألة الـ dual من O(n²) لـ O(n³) في عدد أمثلة التدريب n — ودي عنق الزجاجة الأساسي في إن الـ SVMs تكبر مع datasets ضخمة جدًا.

اختيار الـ kernel المناسب

اختيار الـ kernel فن وعلم في نفس الوقت. ودي شوية إرشادات عملية:

الـ linear kernel: ابدأ بيه. أسرع في التدريب وأسهل في التفسير. ولو بياناتك فيها features أكتر بكتير من الأمثلة (text classification، علم الجينوم)، الـ linear SVM غالبًا بيغلب اللي مش خطي.

الـ RBF kernel: الاختيار الافتراضي لأغلب المسائل لما الـ linear kernel ميكفيش. اختيار آمن لما ميبقاش عندك معرفة مسبقة قوية بشكل البيانات. ظبط C وγ مع بعض بـ grid search على مقياس لوغاريتمي.

الـ polynomial kernel: مفيد لما تكون شايف إن تفاعل الـ features مهم عند درجة معيّنة. الدرجة التانية مشهورة في مهام الـ computer vision. وأقل استقرارًا عدديًا من الـ RBF في الدرجات العالية.

الـ custom kernels: تقدر تعرّف K بتاعك طالما بيحقق شرط ميرسر. والـ kernels الخاصة بالمجال — string kernels للنصوص، وgraph kernels للجزيئات — تقدر تحط معرفة المجال على طول في مقياس التشابه.

الـ kernel matrix هي الـ model

من الاستنتاجات الأنيقة للـ kernel trick: الـ model كله متشفّر في الـ kernel matrix K. أي algorithmين بيستخدموا نفس الـ kernel على نفس البيانات هيطلّعوا نفس الـ decision boundary، مهما كان تنفيذهم من جوه. وعشان كده طرق الـ kernel modular بمرونة — لما تبدّل الـ kernel بتبدّل مفهوم التشابه من غير ما تغيّر أي حاجة تانية في الـ algorithm.

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

الـ kernel SVMs بتدّي مرونة من غير feature engineering صريح. مبنية على أساس متين، وليها ضمانات generalization قوية، وبتشتغل كويس حتى مع البيانات القليلة. والـ RBF kernel هو universal approximator وهيقرّب، بأمثلة كفاية، أي decision boundary ناعم.

القيد الأساسي هو الـ scalability (قابلية التوسع). تخزين الـ kernel matrix وحلها بياكلوا O(n²) memory وO(n³) وقت تدريب. ولـ datasets أكبر من ~100 ألف مثال، الـ kernel SVMs بتبقى مش عملية من غير طرق تقريب (زي Nyström approximation أو random features). وعشان كده الـ deep learning، اللي بيكبر خطيًا مع حجم الـ dataset عن طريق الـ stochastic gradient descent، خد مكان الـ SVMs في المهام الكبيرة — والـ kernel SVMs لسه بتنافس على الـ datasets الصغيرة والمتوسطة.

في الدرس الجاي، هننتقل من النظرية للتطبيق: إزاي ندرّب الـ SVMs ونظبطها ونقيّمها على datasets حقيقية باستخدام scikit-learn، بما فيها استراتيجيات الـ cross-validation وخطوات الـ grid search الكاملة لـ C وγ.

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

الـ kernel trick بيخلّي الـ SVMs تشتغل في فضاءات features أبعادها عالية من غير ما تحسب الـ feature map φ صراحةً.
الـ kernel function K(x, z) بتحسب الـ inner product φ(x)·φ(z) على طول من الـ inputs الأصلية.
شرط ميرسر (kernel matrix positive semi-definite) بيضمن إن الـ kernel بيقابل فضاء inner product صحيح.
التلات kernels المعتادين: linear (من غير نقل)، وpolynomial (monomials لحد الدرجة d)، وRBF (Gaussian أبعاده مالهاش نهاية).
الـ RBF kernel هو الأكتر استخدامًا؛ وγ بيتحكم في عرض جرس التشابه — γ كبير معناه حد معقّد، وγ صغير معناه حد ناعم.
في الصياغة الـ dual، التنبؤ بيستخدم تقييمات الـ kernel قصاد الـ support vectors بس، وده بيخلّيه كفء حتى في فضاءات أبعادها مالهاش نهاية.
الـ kernel SVMs بتكبر بـ O(n²) في الـ memory وO(n³) في التدريب — مش عملية للـ datasets الضخمة جدًا من غير تقريب.