مصنّف بايز وأقرب الجيران

أعطى الانحدار اللوجستي طريقةً واحدة لرسم حدّ فاصل. وقبل مقارنته بغيره، يستحق الأمر أن نعرف كيف يبدو أفضل حدّ ممكن - لأنه موجود، ولأنه لا يُهزم، ولأن كل طريقة في هذا المسار محاولة مختلفة لتخمينه.

المصنّف الذي لا يُهزم

افترض أنك تعرف، عند كل نقطة $x$، الاحتمال الشرطي الحقيقي لكل صنف، ‎$P(Y = j \mid X = x)$‎. يُسنِد مصنّف بايز النقطةَ $x$ إلى الصنف صاحب أكبر احتمال منها.

وتلك القاعدة تصغّر معدل الخطأ، والحجة أقصر من أن تُسمّى برهانًا. فعند كل $x$ على حدة يكون احتمال الخطأ ‎$1 - \max_j P(Y = j \mid X = x)$‎، ولا تستطيع أي قاعدة أخرى أن تصغّره عند تلك النقطة. والقاعدة المثلى عند كل نقطة مثلى وسطيًا. والخطأ الناتج،

$$1 - E\left[\max_j P(Y = j \mid X)\right],$$

هو معدل خطأ بايز: نظير الخطأ غير القابل للاختزال في التصنيف. وهو ليس صفرًا، لأن الأصناف تتداخل فعلًا في المجتمع.

ولاحظ ما تقتضيه القاعدة. إنها تحتاج ‎$P(Y \mid X)$‎ - وهو بالضبط المقدار الذي تحاول كل طريقة واقعية تقديره. فمصنّف بايز إذن مرجعٌ لا يمكن تقويمه إلا في محاكاة بنيتَ بياناتها بنفسك. وليس ذلك سببًا لتجاهله؛ بل هو سبب استحقاق المحاكاة أن تُجرى.

الحساب على المستقيم

خذ صنفين على المستقيم الحقيقي. الصنف 1 هو ‎$N(-1.25, 1)$‎، والصنف 2 هو ‎$N(1.25, 1)$‎، وهما متساويا الاحتمال. فأين الحدّ؟

يتساوى الاحتمالان البعديان حيث ‎$\pi_1 f_1(x) = \pi_2 f_2(x)$‎. ومع تساوي التوزيعات القبلية وتساوي التباينات تكون الكثافتان صورتين متناظرتين، فيكون الحدّ هو نقطة المنتصف، ‎$x = 0$‎. وكل ما يقع يسار الصفر يُسمّى الصنف 1.

ويتبع معدل الخطأ فورًا. فمشاهدة الصنف 2 تُصنَّف خطأً حين تقع تحت الصفر، وذلك باحتمال ‎$\Phi(-1.25) = 0.105650$‎، وبالتناظر ينطبق الشيء نفسه على الصنف 1. فمعدل خطأ بايز إذن

$$0.105650 .$$

نحو تنبؤ واحد من كل عشرة خاطئ، ولن تفعل أي طريقة، مهما بلغت من التعقيد، أفضل من ذلك في هذه المسألة. ومكاملة المزيج عدديًا على أربعة ملايين نقطة من المستقيم تعيد القيمة نفسها إلى ست منازل عشرية.

ما تفعله التوزيعات القبلية

اجعل الآن الصنف 1 أكثر شيوعًا، بـ ‎$\pi_1 = 0.7$‎. يحلّ الحدّ المعادلة ‎$\pi_1 f_1(x) = \pi_2 f_2(x)$‎، وأخذ اللوغاريتم يعطي

$$x = \frac{\sigma^2 \log(\pi_1/\pi_2) + (\mu_2^2 - \mu_1^2)/2}{\mu_2 - \mu_1} = +0.338919 .$$

تحرّك الحدّ نحو الصنف الأندر، فوسّع منطقة الصنف 1. وذلك هو الاتجاه الصحيح، ويستحق التوقف عنده لأن العكس تخمين طبيعي: ما دام الصنف 1 أكثر شيوعًا، أفلا ينبغي أن تنكمش منطقته كي لا يغرق الصنف 2؟ لا - فالنقطة القريبة من الصفر صارت أرجح أن تكون قد جاءت من الصنف 1 لمجرد أن نقاط الصنف 1 أكثر عددًا، والقاعدة المثلى تتبع التوزيع البعدي لا الكثافة.

والعائد قابل للقياس. فعند الحدّ المنقول يكون معدل الخطأ ‎$0.093565$‎؛ وإبقاء الحدّ عند الصفر وتجاهل التوزيع القبلي يعطي ‎$0.105650$‎، فتكلّف الغلطة ‎$0.012084$‎. وعند ‎$\pi_1 = 0.9$‎ يبلغ الحدّ ‎$+0.878890$‎ ويهبط الخطأ إلى ‎$0.050496$‎، بينما يظل الحدّ عند الصفر يعطي ‎$0.105650$‎ - وعندئذ يزيد تجاهل التوزيع القبلي الخطأ إلى أكثر من الضعف.

وبالمقارنة مع شبكة من 240,001 عتبة مرشّحة، يتبيّن أن الحدّ المشتقّ هو الأفضل المتاح فعلًا. وهو تحقّق يسير يلتقط أخطاء الإشارة، وهي سهلة الوقوع هنا وخفية بعد ذلك.

محاكاة مصنّف بايز بالعدّ

لا تأتي البيانات الواقعية ومعها ‎$P(Y \mid X)$‎. وتقدّرها طريقة أقرب k جار بأبسط سبيل يمكن تخيّله: انظر إلى نقاط التدريب الـ $k$ الأقرب إلى ‎$x_0$‎، واستعمل النسب بينها.

$$P(Y = j \mid X = x_0) = \frac{1}{k} \sum_{i \in \mathcal{N}_0} I(y_i = j)$$

ثم طبّق قاعدة بايز على ذلك التقدير. ولا يُلاءَم شيء سلفًا - فمجموعة التدريب هي النموذج، مما يجعل التدريب فوريًا والتنبؤ مكلفًا.

k هو مفتاح المرونة

خذ مسألة ثنائية البعد معدل خطأ بايز فيها، محسوبًا بالمكاملة، ‎$0.092708$‎. لائم على 200 نقطة تدريب، وقِس على 20,000 نقطة اختبار:

اقرأ الطرفين أولًا. فعند ‎$k = 1$‎ تكون كل نقطة تدريب أقرب جار لنفسها، فيكون خطأ التدريب صفرًا تمامًا - ويكون خطأ الاختبار، ‎$0.138200$‎، أسوأ قيم الجدول عدا ‎$k = 199$‎ المنحلّة. وذلك الزوج الوحيد من الأعداد أوضح برهان ستراه على أن خطأ التدريب ليس تقديرًا لخطأ الاختبار.

وعند ‎$k = 199$‎ من أصل 200 نقطة تدريب تصوّت العينة كلها تقريبًا في كل تنبؤ. وقد كفّ المصنّف عن الاعتماد على $x$ أصلًا وصار يعيد الصنف الأكثر شيوعًا فحسب، فيكون خطؤه، ‎$0.504850$‎، احتمال الصنف القبلي جوهريًا. تحيّز أقصى، وتباين أدنى، وصفر معلومات.

وبينهما يكون المنحنى على شكل U، بقاع ضحل من ‎$k = 9$‎ إلى ‎$k = 45$‎ وأفضل قيمة ‎$0.097150$‎ عند ‎$k = 15$‎ - في حدود نصف نقطة مئوية من أرضية بايز، من طريقة لم تفترض شيئًا عن صورة الحدّ. ولا توجد صيغة لأفضل $k$؛ بل يُختار بالتحقق المتقاطع، وانبساط القاع يعني أنه لا يحتاج عادةً إلا أن يكون تقريبيًا صحيحًا.

ما يكلّفه ذلك

لا تفرض الطريقة أي صورة على الحدّ، فتستطيع تتبّع منحنيات ومناطق منفصلة لا يعبّر عنها أي نموذج خطي. وفي المقابل لا تملك سبيلًا إلى تجاهل متغير غير ذي صلة: فكل بُعد يدخل في المسافة، فتتدهور الدقة كلما أُضيفت متغيرات غير مخبرة. وفي الأبعاد العالية لا يكون «أقرب» الجيران قريبًا من ‎$x_0$‎ بأي معنى نافع، وذلك أحد وجوه لعنة الأبعاد.

ولأن المسافة إقليدية، يهيمن عليها متغير مقيس بوحدات كبيرة. والتوحيد المعياري هنا ليس تحسينًا؛ بل شرطٌ لأن يكون للطريقة أي معنى على الإطلاق.

قبل الاختبار

يختار مصنّف بايز أرجح الأصناف عند كل نقطة ولا يُهزم؛ وما يخلّفه هو معدل خطأ بايز، ‎$0.105650$‎ في المثال أحادي البعد. والتوزيعات القبلية تحرّك الحدّ نحو الصنف الأندر، وتجاهلها يكلّف كلفةً قابلة للقياس. وتحاكي طريقةُ أقرب k جار القاعدةَ بعدّ الجيران، وk هو مفتاح المرونة: فـ ‎$k = 1$‎ يحفظ، و‎$k \approx n$‎ يعيد الصنف الأكثر شيوعًا، والقيم النافعة بينهما.