نظرية كوفر

تُعدّ نظرية كوفر بيانًا في نظرية التعلّم الحسابي ، وهي من أهمّ الدوافع النظرية لاستخدام أساليب النواة غير الخطية في تطبيقات التعلّم الآلي . وقد سُمّيت بهذا الاسم نسبةً إلى عالم نظرية المعلومات توماس إم. كوفر الذي صاغها عام 1965، مُشيرًا إليها باسم نظرية دالة العدّ .

ليكن عدد المجموعات المتجانسة القابلة للفصل الخطي من${\displaystyle N}$النقاط في${\displaystyle d}$يمكن تعريف الأبعاد كدالة عد .${\displaystyle C(N,d)}$من عدد النقاط${\displaystyle N}$والأبعاد${\displaystyle d}$تنص النظرية على أن${\displaystyle C(N,d)=2\sum _{k=0}^{d-1}{\binom {N-1}{k}}}$.

يشترط ذلك، كشرط ضروري وكافٍ، أن تكون النقاط في وضع عام . ببساطة، يعني هذا أن تكون النقاط مستقلة خطيًا (غير متراصفة) قدر الإمكان. يتحقق هذا الشرط "باحتمالية 1" أو شبه مؤكدة لمجموعات النقاط العشوائية، بينما قد يُنتهك بسهولة في البيانات الحقيقية، نظرًا لأنها غالبًا ما تكون مُنظمة على طول متشعبات ذات أبعاد أقل ضمن فضاء البيانات.

الوظيفة${\displaystyle C(N,d)}$يتبع نظامين مختلفين اعتمادًا على العلاقة بين${\displaystyle N}$و${\displaystyle d}$.

• ل${\displaystyle N\leq d+1}$، الدالة أسية في${\displaystyle N}$هذا يعني أساسًا أن أي مجموعة من النقاط المصنفة في مواقع عامة وعدد لا يتجاوز البعد + 1 قابلة للفصل الخطي؛ بعبارة أخرى، يُقال إن المصنف الخطي يُفكك أي مجموعة نقاط تحتوي على${\displaystyle N\leq d+1}$. تُعرف هذه الكمية المحددة أيضًا باسم بُعد فابنيك-تشيرفونينكيس للمصنف الخطي.

• ل${\displaystyle N>d+1}$، تبدأ دالة العد في النمو بمعدل أقل من النمو الأسي. هذا يعني أنه، بالنظر إلى عينة ذات حجم ثابت${\displaystyle N}$، للأبعاد الأكبر${\displaystyle d}$من المرجح أن تكون مجموعة عشوائية من النقاط المصنفة قابلة للفصل الخطي. وعلى العكس، مع ثبات الأبعاد، كلما زاد حجم العينة، قلّ عدد مجموعات النقاط العشوائية القابلة للفصل الخطي، أو بعبارة أخرى، تقل احتمالية العثور على عينة قابلة للفصل الخطي.${\displaystyle N}$.

من نتائج هذه النظرية أنه بالنظر إلى مجموعة بيانات تدريبية غير قابلة للفصل الخطي ، يمكن للمرء باحتمالية عالية تحويلها إلى مجموعة تدريب قابلة للفصل الخطي عن طريق إسقاطها في فضاء ذي أبعاد أعلى عبر بعض التحويلات غير الخطية ، أو:

من المرجح أن تكون مشكلة تصنيف الأنماط المعقدة، التي يتم صياغتها في فضاء عالي الأبعاد بشكل غير خطي، قابلة للفصل الخطي أكثر من كونها قابلة للفصل في فضاء منخفض الأبعاد، بشرط ألا يكون الفضاء مكتظًا بالسكان.

بالاستقراء مع العلاقة التكرارية$${\displaystyle C(N+1,d)=C(N,d)+C(N,d-1).}$$لإثبات ذلك، مع ثبات${\displaystyle N}$، متزايد${\displaystyle d}$لتحويل مجموعة من النقاط من غير قابلة للفصل إلى قابلة للفصل، يمكن استخدام دالة حتمية : لنفترض أن هناك${\displaystyle N}$النقاط. ارفعها على رؤوس المجسم البسيط في${\displaystyle N-1}$الفضاء الحقيقي ذو الأبعاد. بما أن كل تقسيم للعينات إلى مجموعتين قابل للفصل بواسطة فاصل خطي ، فإن الخاصية تتبع.

تحتوي الورقة البحثية لعام 1965 على العديد من النظريات.

النظرية 6: ليكن${\textstyle X\cup \{y\}=\left\{x_{1},x_{2},\cdots ,x_{N},y\right\}}$كن في${\textstyle \phi }$-الموقف العام في${\textstyle d}$-المسافة، حيث${\textstyle \phi =\left(\phi _{1},\phi _{2},\cdots ,\phi _{d}\right)}$. ثم${\textstyle y}$غامض فيما يتعلق بـ${\textstyle C(N,d-1)}$ثنائيات${\textstyle X}$بالنسبة لفئة الجميع${\textstyle \phi }$-الأسطح.

النتيجة: إذا كان كل واحد من${\textstyle \phi }$- ثنائيات قابلة للفصل من${\textstyle X}$إذا كان الاحتمال متساوياً، فإن الاحتمال${\textstyle A(N,d)}$الذي - التي${\textstyle y}$غامض فيما يتعلق بالعشوائي${\textstyle \phi }$- ثنائية قابلة للفصل${\textstyle X}$يكون${\displaystyle {\frac {C(N,d-1)}{C(N,d)}}}$.

لو${\displaystyle N/d\to \beta }$ثم عند حد${\displaystyle N\to \infty }$، يتقارب هذا الاحتمال إلى${\displaystyle \lim _{N}A(N,d)={\begin{cases}1,&0\leq \beta \leq 2\\{\frac {1}{\beta -1}},&\beta \geq 2\end{cases}}}$.

يمكن تفسير ذلك على أنه حدٌّ لسعة الذاكرة لوحدة البيرسيبترون الواحدة .${\displaystyle d}$يمثل عدد أوزان الإدخال في الشبكة العصبية. وتنص الصيغة على أنه عند حد القيم الكبيرة${\displaystyle d}$، من شبه المؤكد أن يكون البيرسيبترون قادراً على حفظ ما يصل إلى${\displaystyle 2d}$التصنيفات الثنائية، ولكن من شبه المؤكد أنهم يفشلون في حفظ أكثر من ذلك. ( ماكاي 2003 ، ص 490) 

• آلة المتجهات الداعمة
• طريقة النواة

• هايكين، سيمون (2009). الشبكات العصبية وآلات التعلم (  الطبعة الثالثة). أبر سادل ريفر، نيو جيرسي: بيرسون إديوكيشن إنك.، الصفحات 232-236 . ISBN  978-0-13-147139-9.
• كوفر، تي إم (1965). "الخصائص الهندسية والإحصائية لأنظمة المتباينات الخطية مع تطبيقات في التعرف على الأنماط" (ملف PDF) . مجلة IEEE للمعاملات الإلكترونية . EC-14 (3): 326-334 . doi : 10.1109/pgec.1965.264137 . S2CID 18251470. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 20 ديسمبر 2019. 
• ميهروترا، ك.؛ موهان، س.ك.؛ رانكا، س. (1997). عناصر الشبكات العصبية الاصطناعية (  الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا. ISBN 0-262-13328-8.(القسم 3.5)
• ماكاي، ديفيد جيه سي (2003). "40. سعة عصبون واحد". نظرية المعلومات، والاستدلال، وخوارزميات التعلم . كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-0-521-64298-9.