هذه المقالة هي روايتي المجانية للتعلم يمكن أن تكون غير قابلة للنقض ، Shai Ben-David ، وآخرون.

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

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

بضع كلمات عن التعلم PAC بشكل عام

أول ما أربكني في مراجعة من مجلة Nature News هو أن مشكلة التعلم نفسها قدمت كشيء جديد تمامًا. في الواقع ، هذه مشكلة طويلة ومدروسة جيدًا.

بعض المفاهيم الأساسية لأولئك الذين ليسوا على دراية بهذا السؤال

المخاطرة هي وظيفة $y ، \ hat {y}$ - القيمة الحقيقية والمتوقعة للمتغير المستهدف ، وهو ما يعكس مدى خطأ توقعاتنا. انخفاض قيمة يعكس خطأ أصغر. أبسط مثال لمشكلة التصنيف هو وظيفة المؤشر. $\ mathbb {1} (y \ neq \ hat {y})$ . بالنسبة إلى الانحدار ، سيكون هذا الانحراف المعياري $\ sqrt {y ^ 2 - \ hat {y} ^ 2}$ . من الواضح ، قد يكون هناك خيارات أكثر تعقيدًا. اسم آخر لهذا المفهوم هو وظيفة الخسارة.

متوسط المخاطرة - متوسط قيمة المخاطرة على مساحة بيانات الإدخال بأكملها. نظرًا لحقيقة أن مثل هذه المساحة عادةً ما تكون غير محدودة (على سبيل المثال ، للميزات الحقيقية) ، أو كبيرة بشكل كبير (على سبيل المثال ، مساحة للصور 1024x1024 وقيم البكسل من 0 إلى 255) ، لا يمكننا تقدير هذه القيمة مباشرةً. ومع ذلك ، هناك طرق لتقدير هذه الكمية لن نذهب إليها الآن. هذا هو المؤشر الذي نريد في النهاية التقليل منه. أحيانًا يسمى هذا المؤشر أيضًا خطأ التعميم.

المخاطر التجريبية هي متوسط قيمة المخاطرة في مجموعة بيانات تجريبية معينة تم اختيارها من مساحة بيانات الإدخال بأكملها. عادة ما تشارك خوارزميات التعلم الآلي لدينا في تقليل هذه القيمة.

تتمثل مهمة التعلم الآلي في بناء حل (وظيفة) بناءً على مجموعة البيانات التجريبية المتوفرة والتي من شأنها أن تعطي الحد الأدنى لقيمة متوسط المخاطرة.

هناك نظرية للتعلم الصحيح على الأرجح تقريبًا (من المحتمل أن يكون التعليم صحيحًا أو غير صحيح ، PAC ).

تعريف مبسط لخوارزمية تعلم الآلة المدربة من PAC

الخوارزمية A التي تصنع ، باستخدام عينة تجريبية X من الحجم n ، بعض الوظائف h التي تستعيد قيمة المتغير المستهدف تكون مدربة على اختبار PAC إذا كان لأي عتبة $\ epsilon$ والثقة $\ دلتا$ يوجد مثل هذا الحجم من عينة التدريب n للوظيفة التي تعلمتها h ، يتم استيفاء الشرط التالي: احتمال تجاوز متوسط قيمة المخاطرة $\ epsilon$ أقل من $1 - \ دلتا$ .

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

تعود هذه النظرية إلى ثمانينيات القرن الماضي. ومع ذلك ، فإنه لا يوفر أي مؤشر قابل للقياس من شأنه أن يعكس القدرة على التعلم من خوارزمية. ولكن هذه الإجابة مقدمة من نظرية التعلم الإحصائي ( نظرية VC ) التي طورها بالفعل V. Vapnik و A. Chervonenkis. تعتمد هذه النظرية على مؤشر رقمي لبعد VC. البعد VC عبارة عن تقدير متحد للحد الأقصى لحجم البيانات الذي يمكن أن تقسمه الخوارزمية إلى جزأين بكل الطرق الممكنة.

مثال

افترض أن لدينا خوارزمية تقوم بإنشاء طائرة تشعبية فاصلة في مساحة ذات أبعاد n. ضع في اعتبارك مساحة ذات بعد واحد: يمكن دائمًا تقسيم نقطتين في مثل هذه المساحة ، ولكن لا يمكن تقسيم ثلاث نقاط بعد الآن ، مما يعني أن VC = 2. ضع في اعتبارك مساحة ذات بعدين: يتم تقسيم ثلاث نقاط دائمًا إلى فئتين ، لكن لا يمكن تقسيم أربع نقاط بكل الوسائل الممكنة ، لذلك VC = 3.

في الواقع ، يمكن أن يُظهر بدقة أن VC لفئة من الطائرات المفرطة في الفضاء ذي البعد n $ن + 1 دولا$ .

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

وبالتالي ، فإن مشكلة التعلم الآلي لخوارزميات التعلم الآلي بحد ذاتها تمت دراستها جيدًا ولديها قاعدة رياضية صارمة.

ما هو إذن موضوع مقال في Nature؟

يكتب المؤلفون أن مشكلة نظرية PAC ، القائمة على أبعاد مختلفة للبعد ، هي أنها ليست عالمية.

مؤشرات البعد المختلفة من نظرية PAC

مهمة	الأبعاد
التصنيف الثنائي	البعد VC
تصنيف متعدد الطبقات	البعد من Natarajan
تراجع	تحطيم الدهون
...	...

يقدم المؤلفون مثالًا مثيرًا للاهتمام لمشكلة تم تصميم بيانها نفسه بحيث لا يمكن صياغة النجاح كتعلم PAC. يكتب المؤلفون:

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

المشكلة هنا هي أننا لا نعرف حقًا من سيزور الموقع في المستقبل. لتلخيص ، يمكن وصف بيان مثل هذه المشكلة على النحو التالي:

وجود مجموعة ميزة $F$ على المجموعة $X$ العثور على هذه الوظيفة $F_ {best}$ بحيث متري لها على توزيع غير معروف $P$ كان الحد الأقصى. علاوة على ذلك ، من الضروري إيجاد مثل هذه الوظيفة استنادًا إلى مجموعة محدودة من الكميات المستقلة الموزعة المتماثلة من $P$

تدريب EMX

يقدم Shai Ben-David وزملاؤه مفهومًا جديدًا - E حفز M im X imum (تعلم EMX) ، والذي يعطي فقط معايير التعلم لمشاكل التعظيم هذه:

لمجموعة الميزة $F$ ، مجموعات من المدخلات $X$ والتوزيع غير معروف $P$ لأي رقم $d = d (\ epsilon، \ delta)$ وظيفة $G (s)$ ومن $(\ epsilon، \ delta)$ -MX المدربين إذا لأي توزيع $P$ :

P r_{S s i m P^{d}} [m a t h b b E_{P} (G (S)) l e q s u p_{h i n F} m a t h b b E (h) - e p s i l o n] l e q d e l t a

$Pr_ {S \ sim P ^ d} [\ mathbb {E} _P (G (S)) \ leq \ sup_ {h \ in F} \ mathbb {E} (h) - \ epsilon] \ leq \ delta$

هذا التعريف للتعلم هو بلا شك أكثر عمومية من مفهوم PAC.

ثم أين علاقة "مشكلة الرياضيات التي لم تحل" مع ذلك؟

يثبت المؤلفون النظرية التالية:
دوران EMX $F$ حول $P$ مستقلة عن نظام البديهية Zermelo - Frenkel مع البديهية المفضلة (المشار إليها فيما يلي ZFC).

بمعنى آخر ، باستخدام البديهيات الرياضية القياسية ، لا يمكننا في الحالة العامة إثبات إما إمكانية إيجاد حل لمشكلة التعلم EMX أو إثبات استحالة إيجاد هذا الحل.

يوضح المؤلفون أيضًا أنه بالنسبة للحالة العامة لتعلم EMX ، لا يوجد أي تناظر للبعد VC (أو أي بعد آخر) سيكون محدودًا في حالة قابلية القياس EMX ، والعكس صحيح ، ستتبع قابلية التعلم EMX من الدقة. بشكل أكثر صرامة لديهم أنها وضعت على النحو التالي:

هناك مثل هذا الثابت $ج$ أنه إذا افترضنا اتساق ZFC ، فلا يوجد مثل هذه الخاصية $A (X ، Y)$ هذا بالنسبة للبعض $ inline $ m، M> c $ inline $ لأي $X$ وميزة مجموعة $F$ سيتم تنفيذها:

إذا $A (X ، Y)$ صحيح بعد ذلك $(1/3 ، 1/3)$ تعقيد التعلم EMX $F$ لا يتجاوز M ؛
إذا $A (X ، Y)$ كاذبة ثم $(1/3 ، 1/3)$ تعقيد التعلم EMX $F$ على الأقل م ؛

على العكس ، هذا صحيح ، على سبيل المثال ، بعد VC ، منذ ذلك الحين $A (X ، Y)$ مساو $VC \ leq d$ سيكون أساسا صياغة النظرية الرئيسية لنظرية VC.

استنتاج

في الواقع لا ترتبط رسالة العمل كثيرًا بالمسائل العملية للتعلم الآلي ، أو حتى بالأسئلة النظرية لنظرية التعلم الإحصائي. يبدو لي أن هناك فكرتين رئيسيتين في العمل:

علاقة جميلة بين التعلم EMX ونظريات Gödel.
الاستحالة الأساسية لإنشاء توصيف عالمي للتعلم (مثل البعد VC) للفئة العامة لمشاكل التعلم الآلي.

في الوقت نفسه ، أنا شخصياً لا أحب تمامًا العنوان "واجه التعلم الآلي مشكلة رياضية لم يتم حلها" ، المستخدمة في ترجمة مراجعة لهذه المقالة . في رأيي ، هذا نقرة مطلقة ، علاوة على ذلك ، ببساطة لا يتوافق مع الواقع. العمل الأصلي لا يعني أن شخصًا ما قد واجه شيئًا ما. التعلم الآلي ونظرية PAC على حد سواء عملت ومواصلة العمل. يشار إلى أن نظرية PAC لا يمكن تعميمها على بعض العبارات المعينة لمشكلة التعلم الآلي ، تم العثور على روابط مثيرة مع نظريات Gödel ، ولكن ليس كلمة عن بعض المشاكل التي لم يتم حلها التي واجهها التعلم الآلي.

يمكن أن يكون قابلية التعلم مراجعة غير قابلة للنقض

بضع كلمات عن التعلم PAC بشكل عام

ما هو إذن موضوع مقال في Nature؟

تدريب EMX

ثم أين علاقة "مشكلة الرياضيات التي لم تحل" مع ذلك؟

استنتاج

More articles: