Proof-Carrying Optimality for Finite Identification under Bounded Adversarial Answer Errors

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

يتناول بحث جديد أجراه فيكرام ليكس في "KarLex AI" هذه المشكلة من خلال تقديم طريقة لا تكتفي بتخمين الإجابة، بل تقدم برهاناً رياضياً على صحتها. يركز البحث على نسخة محددة من اللعبة حيث لا يمكن للمتعلم إلا طرح أسئلة من قائمة ثابتة ومعتمدة مسبقاً، ويكون عدد الأكاذيب محدوداً بصرامة. طور المؤلف نظاماً يولد "شهادات محمولة" (Portable Certificates). فكر في هذه الشهادات كتقرير درجات ذاتي الاحتواء؛ فبدلاً من مطالبة حاسوب خارق بإعادة حل اللغز بالكامل للتحقق من العمل، تسمح هذه الشهادات لأي شخص بالتحقق من النتيجة بسرعة وبشكل مستقل. يجمع النظام بين استراتيجية لطرح الأسئلة وبين "شاهد" (Witness)، وهو مجموعة صغيرة ومحددة من الأمثلة التي تثبت أنه لا توجد استراتيجية ممكنة يمكن أن تفعل أفضل من ذلك. هذا النهج ينقل العبء من مجرد إيجاد الإجابة إلى إثبات أن الإجابة هي الأفضل على الإطلاق.

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

يتحقق البحث من هذه النتائج من خلال اختبارات مكثفة على مجموعة متنوعة من جداول المشكلات، والتي تتراوح من الخيارات الثنائية البسيطة إلى الهياكل المنطقية المعقدة. اختبر الباحثون 303 سيناريوهات مختلفة، بما في ذلك الجداول العشوائية وتلك المستمدة من مفاهيم واقعية مثل المنطق البولياني (Boolean logic) والاقترانات الرتيبة (Monotone conjunctions). وفي 302 من أصل 303 حالة، نجح النظام في إنتاج شهادة تثبت العدد الأدنى الدقيق للأسئلة المطلوبة. وفي معظم الحالات، كان الأسلوب الجديد لإيجاد "شهود العزل" أكثر فعالية بكثير من التقنيات السابقة، حيث غطى 69 من أصل 101 جدول معقد بينما نجحت الطرق القديمة في تغطية 25 فقط. كما أظهرت الدراسة أن القدرة على تكييف الأسئلة بناءً على الإجابات السابقة توفر ميزة كبيرة؛ ففي العديد من السيناريوهات المختبرة، تطلب النهج التكيفي عدداً أقل بكما من الأسئلة مقارنة بالنهج غير التكيفي، حيث أظهرت بعض الحالات فرقاً يصل إلى قرابة أربعين سؤالاً.

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

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