نظریهٔ یادگیری الگوریتمی

نظریهٔ یادگیری الگوریتمی (; ALT) شاخه‌ای از یادگیری ماشینی و نظریه محاسبات است که به بررسی رسمی و ریاضی الگوریتم‌های یادگیری می‌پردازد. در این نظریه، برخلاف نظریه یادگیری آماری، فرض نمی‌شود که داده‌ها از یک توزیع تصادفی نمونه‌برداری شده باشند. این حوزه گاهی با نام‌های (نظریهٔ یادگیری رسمی) یا (استنتاج استقرایی) نیز شناخته می‌شود.

 ویژگی‌های متمایز 
نظریهٔ یادگیری الگوریتمی برخلاف بسیاری از نظریه‌های آماری یادگیری، بر تصادفی بودن داده‌ها تکیه ندارد. داده‌ها به‌صورت دنباله‌هایی در نظر گرفته می‌شوند که ممکن است ساختاریافته اما غیرتصادفی باشند. این ویژگی باعث می‌شود این نظریه برای حوزه‌هایی مانند یادگیری زبان طبیعی و کشف علمی خودکار مناسب باشد.

مفهوم اساسی در این نظریه «یادگیری تا حد نامحدود» () است. در این چارچوب، انتظار می‌رود که با افزایش داده‌ها، الگوریتم یادگیرنده به یک فرضیه صحیح همگرا شود و پس از آن دیگر فرضیهٔ خود را تغییر ندهد. این نوع همگرایی شکلی غیراحتمالی از همگرایی در یادگیری است.

در بسیاری از مدل‌های نظریهٔ یادگیری الگوریتمی، توانایی یادگیری ماشین تورینگ‌ها بررسی می‌شود. با این حال، برخی چارچوب‌ها کلاس‌های محدودتری از الگوریتم‌ها را در نظر می‌گیرند؛ برای مثال الگوریتم‌هایی که فقط در زمان چندجمله‌ای قادر به محاسبهٔ فرضیه‌ها هستند.

 یادگیری تا حد نامحدود 
یادگیری تا حد نامحدود نخستین بار در مقالهٔ کلاسیک «شناسایی زبان‌ها تا حد نامحدود» نوشتهٔ E. Mark Gold معرفی شد. در مسئلهٔ شناسایی زبان، هدف این است که یک ماشین با دریافت نمونه‌هایی از یک زبان، برنامه‌ای را شناسایی کند که بتواند تشخیص دهد آیا یک جمله عضو آن زبان است یا خیر.

در مدل گلد، یادگیرنده در هر مرحله یک نمونه دریافت می‌کند و بر اساس آن یک فرضیه ارائه می‌دهد که نمایانگر برنامه‌ای برای تشخیص زبان است. فرض می‌شود که تمام جملات ممکن، چه عضو زبان باشند و چه نباشند، در نهایت در دنبالهٔ داده‌ها ظاهر می‌شوند، اما ترتیب ارائهٔ آن‌ها از پیش تعیین نشده است.

یک زبان زمانی «یادگرفته‌شده» تلقی می‌شود که یادگیرنده پس از تعداد محدودی مرحله، دیگر فرضیهٔ خود را تغییر ندهد. یادگیرنده ممکن است نداند که به فرضیهٔ صحیح رسیده است، اما شرط اصلی این است که فرضیهٔ نهایی با زبان هدف سازگار باشد.

 معیارهای دیگر شناسایی 
در نظریهٔ یادگیری الگوریتمی، معیارهای مختلفی برای ارزیابی فرایند یادگیری مطرح شده‌اند، از جمله:
 کارایی: حداقل‌سازی تعداد نمونه‌های لازم پیش از همگرایی به فرضیهٔ صحیح.
 تغییر ذهن: کاهش تعداد دفعاتی که یادگیرنده پیش از رسیدن به همگرایی، فرضیهٔ خود را تغییر می‌دهد. این مفهوم با کران‌های خطا در نظریه یادگیری آماری مرتبط است.

 کنفرانس سالانه 
از سال ۱۹۹۰، کنفرانس بین‌المللی نظریهٔ یادگیری الگوریتمی (; ALT) هر سال برگزار می‌شود. این رویداد در ابتدا به‌صورت کارگاه برگزار می‌شد و از سال ۱۹۹۲ تا ۲۰۱۶، مقالات آن در مجموعهٔ LNCS منتشر می‌شدند. از سال ۲۰۱۷ به بعد، مقالات این کنفرانس در مجموعهٔ چاپ می‌شوند.

 پیوند به بیرون 
 وبگاه رسمی نظریهٔ یادگیری در علوم رایانه
 مدخل (نظریهٔ یادگیری رسمی) در دانشنامهٔ فلسفهٔ استنفورد
 صفحهٔ کنفرانس نظریهٔ یادگیری الگوریتمی (ALT) در DBLP
 مجموعهٔ مقالات کنفرانس ALT در انتشارات World Scientific
 Proceedings of Machine Learning Research – مقالات ALT
 نسخهٔ انگلیسی مقاله در ویکی‌پدیا

 منابع 
 Osherson, Daniel N. ; Stob, Michael; Weinstein, Scott (1990). Systems That Learn: An Introduction to Learning Theory for Cognitive and Computer Scientists. MIT Press. ISBN 978-0-262-65024-3
 Jain, Sanjay; Osherson, Daniel N. ; Royer, James S. ; Sharma, Arun (1999). Systems That Learn: An Introduction to Learning Theory. MIT Press. ISBN 978-0-262-10077-9
 Angluin, Dana (1990). «Inductive Inference». در: Handbook of Theoretical Computer Science. Elsevier. ISBN 978-0-444-88074-1
 Case, John; Smith, Carl (1983). «Comparison of Identification Criteria for Machine Inductive Inference". Theoretical Computer Science. جلد ۲۵، صص ۱۹۳–۲۲۰
 Gold, E. Mark (1967). «Language Identification in the Limit". Information and Control. جلد ۱۰، شمارهٔ ۵، صص ۴۴۷–۴۷۴. doi:10.1016/S0019-9958(67)91165-5
 International Conference on Algorithmic Learning Theory. وبگاه رسمی کنفرانس ALT. https://www.learningtheory.org
 Stanford Encyclopedia of Philosophy. "Formal Learning Theory". https://plato.stanford.edu/entries/learning-formal/
 Wikipedia contributors. "Algorithmic learning theory". Wikipedia, The Free Encyclopedia. https://en.wikipedia.org/wiki/Algorithmic_learning_theory