قياس مدى التعقيد وقابلية التعلم لمشاكل التصنيف الاستراتيجي | بواسطة جوناثان ياهاف

حساب العلامات القابلة للتحقيق: معاملات التحطيم الكنسي

يبدو تعريف معاملات التحطيم شفهيًا واضحًا للوهلة الأولى:

نظرا لفئة الفرضية ح, إنه نᵗʰ معامل التحطم، يُشار إليه Sₙ(ح)، يمثل أكبر عدد من العلامات التي يمكن تحقيقها بواسطة المصنفين في ح على عينة من ن ناقلات الميزة.

ولكن ما هو “وضع العلامات“؟ وما الذي يجعله “قابل للتحقيق“؟ إن الإجابة على هذه الأسئلة ستساعدنا على إرساء بعض الأساس في السعي للحصول على تعريف أكثر رسمية.

في سياق التصنيف الثنائي، أ وضع العلامات إن عينة من متجهات المعالم هي ببساطة إحدى الطرق التي يمكننا من خلالها تعيين قيم من المجموعة { -1, 1 } إلى تلك المتجهات. كمثال بسيط للغاية، فكر في متجهين مميزين أحاديي البعد (أي نقاط على خط الأعداد)، س₁ = 1 و س₂ = 2.

التسميات المحتملة هي أي مجموعة من قيم التصنيف التي يمكننا تخصيصها لمتجهات الميزات الفردية بشكل مستقل عن بعضها البعض. يمكننا تمثيل كل تسمية كمتجه، حيث يمثل الإحداثيان الأول والثاني القيم المخصصة لها س₁ و س₂ على التوالي. وبالتالي فإن مجموعة التسميات المحتملة هي { (-1، -1)، (-1، 1)، (1، -1)، (1، 1) }. لاحظ أن عينة بالحجم 2 تنتج 2² = 4 تسميات محتملة – سنرى كيف سيتم تعميم ذلك على العينات ذات الحجم العشوائي قريبًا.

نحن نقول ذلك وضع العلامات هو قابل للتحقيق بواسطة فئة الفرضية ح إذا كان هناك مصنف ح ∈ ح التي يمكن أن ينتج عنها هذا التصنيف. بالاستمرار في مثالنا البسيط، لنفترض أننا مقتصرون على مصنفات النموذج س ≥ ك، ك ∈ ℝ، أي عتبات أحادية البعد بحيث يتم تصنيف أي شيء على يمين العتبة بشكل إيجابي. لا يمكن تحقيق العلامة (1، -1) من خلال فئة الفرضية هذه. س₂ كونها أكبر من س₁ يعني أن أي عتبة تصنف س₁ بشكل إيجابي يجب أن تفعل الشيء نفسه ل س₂. وبالتالي فإن مجموعة العلامات القابلة للتحقيق هي { (-1، -1)، (-1، 1)، (1، 1) }.

بعد أن فهمنا المصطلحات الأساسية، يمكننا البدء في تطوير بعض الرموز للتعبير رسميًا عن عناصر التعريف اللفظي الذي بدأنا به.

نحن نلتزم بتمثيل التصنيفات كمتجهات كما فعلنا في مثالنا البسيط، حيث يمثل كل إحداثي قيمة التصنيف المخصصة لمتجه الميزة المقابل. هناك 2ⁿ التسميات المحتملة في المجموع: هناك خياران محتملان لكل ناقل ميزة، ويمكننا التفكير في التصنيف كمجموعة من ن مثل هذه الاختيارات، يتم اتخاذ كل منها بشكل مستقل عن الباقي. إذا كانت فئة الفرضية ح يمكنه تحقيق جميع التصنيفات الممكنة للعينة 𝒞ₙ, أي إذا كان عدد قابل للتحقيق تسميات 𝒞ₙ يساوي 2ⁿ, نحن نقول ذلك ح يتحطم 𝒞ₙ.

أخيرًا، باستخدام الترميز أعلاه، نتفق على تعريف أكثر صرامة لـ Sₙ(ح):

تمشيا مع شرحنا للتحطيم ، Sₙ(ح) يساوي 2ⁿ يعني وجود عينة من الحجم ن التي تحطمت من قبل ح.

تقدير تعبير فئة الفرضية: البعد VC الكنسي

يعد بُعد Vapnik-Chervonenkis (VC) طريقة لقياس القوة التعبيرية لفئة الفرضيات. إنها مبنية على فكرة التحطيم التي حددناها للتو، وهي تلعب دورًا مهمًا في مساعدتنا في تحديد فئات الفرضيات التي يمكن تعلمها من خلال PAC وأيها لا يمكن تعلمها.

لنبدأ بمحاولة تحديد بُعد VC الأساسي بشكل بديهي:

نظرا لفئة الفرضية ح، البعد VC الخاص به، يُشار إليه بـ VCdim(ح) ، يتم تعريفه على أنه أكبر عدد طبيعي ن التي توجد لها عينة من الحجم ن إنه تحطمت بواسطة ح.

استخدام Sₙ(ح) تمكننا من التعبير عن هذا بشكل أكثر وضوحًا وإيجازًا:

VCdim(ح) = الأعلى{ ن ∈ ℕ : Sₙ(ح) = 2ⁿ }

ومع ذلك، هذا التعريف ليس دقيقا. لاحظ أن مجموعة الأعداد التي معامل التكسر لها يساوي 2ⁿ قد تكون لا نهائية. (وبالتالي، من الممكن أن يكون VCdim(ح) = ∞.) إذا كان الأمر كذلك، فلن يكون للمجموعة حد أقصى محدد جيدًا. نحن نعالج هذا من خلال أخذ السيادة بدلا من ذلك:

VCdim(ح) = رشفة{ ن ∈ ℕ : Sₙ(ح) = 2ⁿ }

وهذا التعريف الدقيق والموجز هو الذي سنستخدمه للمضي قدمًا.

إضافة التفضيلات إلى المزيج: معاملات التحطيم الإستراتيجية

إن تعميم المفاهيم الأساسية التي تناولناها للتو بحيث تعمل في إطار استراتيجي هو أمر واضح ومباشر إلى حد ما. إعادة تعريف معاملات التحطيم من حيث نقطة البيانات أفضل استجابة لقد حددنا في المقالة السابقة هو كل ما يتعين علينا القيام به عمليًا.

نظرا لفئة الفرضية ح، مجموعة التفضيلات ر، ووظيفة التكلفة ج, ال نᵗʰ معامل التحطم Sᴛʀᴀᴄ⟨ح, ر, ج⟩، يُشار إليه بـ σₙ(ح، ر، ج)، يمثل أكبر عدد من العلامات التي يمكن تحقيقها بواسطة المصنفين في ح على مجموعة من ن ناقلات الميزات التي يحتمل أن يتم التلاعب بها، على سبيل المثال، ن نقطة البيانات أفضل الاستجابات.

للتذكير، هذه هي الطريقة التي حددنا بها أفضل استجابة لنقطة البيانات:

يمكننا تعديل الترميز الذي استخدمناه في مناقشتنا لمعاملات التحطيم الأساسية لإضفاء المزيد من الطابع الرسمي على هذا:

والفرق الرئيسي هو أن كل منهما س في العينة يجب أن يكون لها المقابلة ص. بخلاف ذلك، فإن وضع أفضل استجابة لنقطة البيانات حيث كان لدينا x في الحالة الأساسية يعمل بسلاسة.

كفحص سريع للسلامة، دعونا نفكر في ما سيحدث إذا ر = { 0 }. حد المكافأة المحقق 𝕀(ح(ض) = 1) ⋅ ص سيكون 0 في جميع نقاط البيانات. وبالتالي فإن تعظيم المنفعة يصبح مرادفًا لتقليل التكلفة. أفضل طريقة لتقليل التكلفة التي تتكبدها نقطة البيانات هي طريقة تافهة: لا يتم التلاعب مطلقًا بمتجه الميزات الخاص به.

Δ(س, ص; ح) ينتهي به الأمر دائمًا إلى الوجود س, يضعنا بقوة داخل منطقة التصنيف الكنسي. ويترتب على ذلك σₙ(ح{ 0 }, ج) = سₙ(ح) للجميع ح، ج. وهذا يتوافق مع ملاحظتنا التي تمثلها فئة التفضيل المحايدة ر = { 0 } يعادل التصنيف الثنائي الأساسي.

التعبير مع التفضيلات: البعد الاستراتيجي VC (SVC)

وبعد أن تم تعريف نᵗʰ معامل التحطيم الاستراتيجي يمكننا ببساطة مبادلة Sₙ(ح) في التعريف المتعارف عليه لبعد VC لـ σₙ(ح, ر, ج).

SVC(ح، ر، ج) = رشفة{ ن ∈ ℕ : σₙ(ح، ر، ج) = 2ⁿ }

استنادا إلى المثال الذي تناولناه أعلاه، نجد أن SVC(ح{ 0 }, ج) = VCdim(ح) لأي ح, ج. بالفعل، SVC هو VCdim حيث أن معامل التحطيم الاستراتيجي هو معادله القانوني: وكلاهما تعميمات أنيقة للمفاهيم غير الاستراتيجية.

من SVC إلى قابلية التعلم الاستراتيجي PAC: النظرية الأساسية للتعلم الاستراتيجي

يمكننا الآن استخدام SVC لتوضيح النظرية الأساسية للتعلم الاستراتيجي، الذي يربط تعقيد مشكلة التصنيف الاستراتيجي بقابلية تعلم PAC (الملحدة).

مثال التصنيف الاستراتيجي Sᴛʀᴀᴄ⟨ح, ر, ج⟩ يمكن تعلم PAC الحيادي إذا وفقط إذا كان SVC(ح، ر، ج) محدودة. ال تعقيد العينة للتعلم الحيادي الاستراتيجي PAC هو م(δ, ε) ≥ Cε ⁻² ⋅ (سفك(ح، ر، ج) + سجل⁡(1/δ))، مع ج كونها ثابتة.

لن نشرح كثيرًا كيف يمكن إثبات ذلك. يكفي أن نقول إن الأمر يتلخص في اختزال ذكي للنظرية الأساسية (الموثقة جيدًا) إحصائية التعلم، وهو في الأساس النسخة غير الإستراتيجية للنظرية. إذا كنت مهتمًا بالرياضيات ومهتمًا بتفاصيل الإثبات، فيمكنك العثور عليها في الملحق ب من الورقة.

تكمل هذه النظرية بشكل أساسي تعميمنا لتعلم PAC الكلاسيكي على إعداد التصنيف الاستراتيجي. إنه يوضح أن الطريقة التي حددنا بها SVC في الواقع ليست منطقية في رؤوسنا فحسب؛ إنه في الواقع يعمل كتعميم لـ VCdim حيث يكون أكثر أهمية. مسلحين بالنظرية الأساسية، نحن مجهزون جيدًا لتحليل مشاكل التصنيف الاستراتيجي مثلما نفعل مع أي مشكلة تصنيف ثنائي قديمة. في رأيي، إن القدرة على تحديد ما إذا كانت المشكلة الإستراتيجية قابلة للتعلم من الناحية النظرية أم لا أمر لا يصدق!