نظرية سولومونوف للاستدلال الاستقرائي

تستند هذه النظرية إلى أسس فلسفية، وقد أسسها راي سولومونوف حوالي عام 1960. ^{[ 9 ]} وهي عبارة عن مزيج رياضي مُصاغ من مبدأ أوكام ^{[ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]} ومبدأ التفسيرات المتعددة . ^{[ 10 ]} تُستخدم جميع النظريات القابلة للحساب التي تصف بدقة الملاحظات السابقة لحساب احتمالية الملاحظة التالية، مع إعطاء وزن أكبر للنظريات الأقصر. ويعتمد الذكاء الاصطناعي الشامل لماركوس هوتر على هذا لحساب القيمة المتوقعة لأي فعل.

يُقال إن استقراء سولومونوف هو الصياغة الحسابية للمنهج البايزي الخالص . ^{[ 3 ]} لفهم ذلك، تذكر أن المنهج البايزي يستنتج الاحتمال اللاحق.${\displaystyle \mathbb {P} [T|D]}$نظرية${\displaystyle T}$البيانات المعطاة${\displaystyle D}$بتطبيق قاعدة بايز، والتي ينتج عنها

${\displaystyle \mathbb {P} [T|D]={\frac {\mathbb {P} [D|T]\mathbb {P} [T]}{\mathbb {P} [D|T]\mathbb {P} [T]+\sum _{A\neq T}\mathbb {P} [D|A]\mathbb {P} [A]}}}$

حيث النظريات${\displaystyle A}$بدائل للنظرية${\displaystyle T}$لكي تكون هذه المعادلة منطقية، يجب أن تكون الكميات${\displaystyle \mathbb {P} [D|T]}$و${\displaystyle \mathbb {P} [D|A]}$يجب أن تكون محددة جيدًا لجميع النظريات${\displaystyle T}$و${\displaystyle A}$بمعنى آخر، يجب على أي نظرية أن تحدد توزيعًا احتماليًا على البيانات القابلة للملاحظة${\displaystyle D}$. يختزل استقراء سولومونوف بشكل أساسي إلى اشتراط أن تكون جميع توزيعات الاحتمالات هذه قابلة للحساب .

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

يُتيح استقراء سولومونوف بالتالي إمكانية وضع تنبؤات احتمالية للبيانات المستقبلية${\displaystyle F}$وذلك ببساطة عن طريق اتباع قوانين الاحتمالات. أي أننا لدينا${\displaystyle \mathbb {P} [F|D]=\mathbb {E} _{T}[\mathbb {P} [F|T,D]]=\sum _{T}\mathbb {P} [F|T,D]\mathbb {P} [T|D]}$يمكن تفسير هذه الكمية على أنها متوسط ​​التوقعات${\displaystyle \mathbb {P} [F|T,D]}$من بين جميع النظريات${\displaystyle T}$بالنظر إلى البيانات السابقة${\displaystyle D}$، مرجحة بحسب مصداقيتها اللاحقة${\displaystyle \mathbb {P} [T|D]}$.

يعتمد برهان "الشفرة" على الخصائص الرياضية المعروفة لتوزيع الاحتمالات على مجموعة قابلة للعد . هذه الخصائص مهمة لأن المجموعة اللانهائية لجميع البرامج هي مجموعة قابلة للعد. يجب أن يكون مجموع احتمالات جميع البرامج (S) مساويًا للواحد تمامًا (وفقًا لتعريف الاحتمال )، وبالتالي يجب أن تتناقص الاحتمالات تقريبًا كلما قمنا بترقيم المجموعة اللانهائية لجميع البرامج، وإلا فإن S سيكون أكبر من واحد. بتعبير أدق، لكل${\displaystyle \epsilon }$إذا كان طول البرنامج أكبر من صفر، فهناك طول معين l بحيث يكون احتمال أن تكون جميع البرامج أطول من l على الأكثر${\displaystyle \epsilon }$لكن هذا لا يمنع البرامج الطويلة جدًا من أن يكون لها احتمالية عالية جدًا.

تُعدّ مفاهيم الاحتمالية الخوارزمية وتعقيد كولموغوروف من المكونات الأساسية لهذه النظرية . الاحتمالية المسبقة الشاملة لأي بادئة p من متتالية قابلة للحساب x هي مجموع احتمالات جميع البرامج (في حاسوب شامل ) التي تحسب شيئًا ما يبدأ بـ p . وبمعرفة قيمة p وأي توزيع احتمالي قابل للحساب ولكنه غير معروف يتم أخذ عينة x منه ، يمكن استخدام الاحتمالية المسبقة الشاملة ونظرية بايز للتنبؤ بالأجزاء غير المرئية من x على النحو الأمثل.

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

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

على الرغم من أن الاستدلال الاستقرائي لسولومونوف غير قابل للحساب ، إلا أن العديد من الخوارزميات المشتقة من AIXI تُقارب هذا الاستدلال لجعله قابلاً للتنفيذ على الحواسيب الحديثة. وكلما زادت القدرة الحاسوبية المتاحة لهذه الخوارزميات، اقتربت تنبؤاتها من تنبؤات الاستدلال الاستقرائي (حيث أن حدها الرياضي هو الاستدلال الاستقرائي لسولومونوف). ^{[ 11 ] [ 12 ] [ 13 ]}

يعتمد اتجاه آخر للاستدلال الاستقرائي على نموذج إي. مارك غولد للتعلم في النهاية من عام 1967، وقد تطور منذ ذلك الحين إلى نماذج تعلم أكثر فأكثر. ^{[ 14 ]} السيناريو العام هو التالي: بالنظر إلى فئة S من الدوال القابلة للحساب، هل يوجد متعلم (أي دالة تكرارية) يُخرج، لأي مدخل من الشكل ( f (0), f (1), ..., f ( n ))، فرضية (مؤشر e بالنسبة لترقيم مقبول متفق عليه مسبقًا لجميع الدوال القابلة للحساب؛ قد يُشترط أن تكون الدالة المفهرسة متوافقة مع القيم المعطاة لـ f )؟ يتعلم المتعلم M الدالة f إذا كانت جميع فرضياته تقريبًا تحمل نفس المؤشر e ، الذي يُولد الدالة f ؛ ويتعلم M الفئة S إذا تعلم كل دالة f في S. النتائج الأساسية هي أن جميع فئات الدوال القابلة للتعداد التكراري قابلة للتعلم، بينما فئة REC لجميع الدوال القابلة للحساب غير قابلة للتعلم. تمّت دراسة العديد من النماذج ذات الصلة، كما أن تعلّم فئات المجموعات القابلة للتعداد التكراري من البيانات الموجبة هو موضوع دُرِسَ منذ ورقة غولد الرائدة عام 1967. وقد طُوِّرَ امتدادٌ واسع النطاق لمنهج غولد من خلال نظرية شميدهوبر لتعقيدات كولموغوروف المعممة، ^{[ 15 ]} والتي تُعدّ أنواعًا من الخوارزميات فائقة التكرار .