نظریه یادگیری محاسباتی
نظریه یادگیری محاسباتی(به : Computational Learning Theory) شاخه‌ای از ریاضیات و علوم رایانه است که به ارزیابی کارایی الگوریتم‌های یادگیری ماشینی می‌پردازد. این نظریه عموماً به تحلیل الگوریتم‌های یادگیری با نظارت می‌پردازد و سعی می‌کند کران‌هایی برای کارایی یک الگوریتم در داده دیده‌نشده با استفاده از اطلاعات کارایی آن الگوریتم در داده در دسترس و پیچیدگی الگوریتم بیابد. بعد وی‌سی و یادگیری صحیح احتمالی تخمینی مثال‌هایی از نظریه یادگیری محاسباتی هستند که به ترتیب به اختراع الگوریتم‌های ماشین بردار پشتیبانی و بوستینگ انجامیدند. این نظریه به تحلیل پیچیدگی زمانی الگوریتم‌های یادگیری نیز می‌پردازد. همچنین این تئوری به دنبال جواب سوالاتی مانند "تحت چه شرایطی یادگیری موفق، ممکن یا ناممکن است؟" ویا "تحت چه شرایطی یک الگوریتم یادگیری خاص موفقیت یادگیری را تضمین می‌کند؟" می‌باشد. دو چهارچوب برای بررسی یادگیری الگوریتم‌های یادگیری در نظر گرفته می‌شود. چهارچوب اول، چهارچوب تقریباً درست یا PAC که در بالا اشاره ‌‌شد، می‌باشد. در این چهارچوب کلاس فرضیه‌هایی را که می‌توان یا نمی‌توان با تعداد چندجمله‌ایی از نمونه‌های آموزشی یادگرفت را بررسی می‌کند و معیاری طبیعی برای پیچیدگی فضای فرضیه‌ای که تعداد نمونه‌های آموزشی برای یادگیری استقرایی را محدود می‌کند، تعریف می‌کنیم. در چهارچوب کران خطا تعداد خطاهای آموزشی ای را که یادگیر قبل از تعیین فرضیه درست انجام می‌دهد را بررسی می‌کنیم. در مطالعه یادگیری ماشین، این سؤال طبیعی است که بپرسیم : اگر چه جواب جامع همه این سوالات هنوز معلوم نیست، اما این قسمت از هوش محاسباتی برای پاسخ به این سوالات به وجود آمده‌است. برای مثال مسئله یادگیری استقرایی تابع هدفی نامعلوم از نمونه‌های آموزشی این تابع هدف و فضای فرضیه معلوم را در نظر بگیرید. در این مثال پاسخ به سوالاتی مثل تعداد نمونه‌های لازم برای یادگیری موفق و تعداد اشتباهات قبل از یادگیری کامل مطرح می‌شود. برای تعیین مرزهای این کمیت‌ها به ویژگی‌های مسئله‌ یادگیری از جمله موارد زیر بستگی دارد :‌ در اکثر موارد ما بر روی الگوریتم یادگیری خاصی تمرکز نمی‌کنیم و ترجیح می‌دهیم بیشتر بر روی کلاس‌های الگوریتم‌های یادگیری با خواص یکسان (فضای فرضیه‌ای مشابه، نحوه نمایش نمونه‌های آموزشی مشابه و ...) بحث کنیم. در اکثر موارد سوالات بالا مطرح هستند. توجه کنید روش‌های گوناگونی برای تعریف "موفق" وجود دارد. ممکن است یادگیری فرضیه‌ای را موفق بدانیم که خروجی آن دقیقا مشابه هدف باشد، همچنین ممکن است یادگیری‌ای را موفق بدانیم که فرضیه اش در اکثر موارد مشابه هدف باشد.  در این بخش، حالت خاصی را برای مسائل یادگیری در نظر می‌گیریم، این حال مدل یادگیری تقریباً درست (PAC) نامیده می‌شود. برای سادگی کار، یادگیری مفاهیم منطقی از داده‌های آموزشی بدون خطا را در نظر بگیرید. با این وجود بسیاری از نتایج حاصل را می‌توان به حالت کلی یادگیری توابع حقیقی مقادیر تابع هدف تعمیم داد. همچنین بسیاری دیگر از نتایج را می‌توان به یادگیری از انواع خاصی از داده‌های خطادار تعمیم داد. فرض کنید formula_1 مجموعه‌ای از تمامی نمونه‌های ممکن بر روی تابع هدف مفروض باشد. برای مثال، مجموعه تمامی افراد با ویژگی‌های سن (پیر و جوان) و قد (بلند و کوتاه) باشد. formula_2 مجموعه مفاهیم هدفی است که ممکن است، یادگیر برای یادگیری آن‌ها برای یادگیری آنها، به کار برده باشد. هر مفهوم هدف formula_3 در مجموعه formula_2 متناسب با زیر مجموعه‌ای از formula_1 است. به‌طور مشابه formula_3 متناسب با تابع formula_7 می‌باشد. برای مثال، یک تابع هدف formula_3 در formula_2، ممکن است مفهوم "افراد اسکی باز" باشد. اگر formula_10 نمونه مثبتی از formula_3 باشد، داریم :  formula_12
در این حالت فرض می‌کنیم که نمونه‌ها به صورت تصادفی و با توزیع احتمال formula_13 انتخاب می‌شوند. برای مثال، formula_13 ممکن است، توزیع احتمال نمونه افرادی باشد که از یک باشگاه ورزشی بیرون می‌آیند (توزیع احتمالی بر روی تمامی افراد). در کل formula_13 ممکن است، هر توزیع احتمالی باشد و درحالت کلی این توزیع برای یادگیر ناشناخته است. تمامی اطلاعات موجود در formula_13 این است که توزیع احتمالی ثابت است، بدین معنا که این توزیع احتمال با زمان تغییر نمی‌کند. نمونه‌های آموزشی با این توزیع احتمال انتخاب شده و به همراه مقدار تابع هدفشان (formula_17) به یادگیر داده می‌شوند. یادگیر formula_18 مجموعه‌ای از فرضیه‌های ممکن مانند formula_19 را در یادگیری مفهوم هدف در نظر می‌گیرد. برای مثال، formula_19 ممکن است، مجموعه تمامی فرضیه‌های قابل بیان به صورت عطف سن و قد باشد. بعد از مشاهده یک سری از نمونه‌های آموزشی، برای تابع هدف formula_3، باید فرضیه‌ای مانند formula_22 از formula_19 که تخمین آن از formula_3 است، به عنوان فرضیه‌ تخمینی خروجی دهد. موفقیت formula_18 را کارایی این فرضیه formula_22 بر روی نمونه‌های جدیدی که به صورت تصادفی از formula_1 و باتوزیع formula_13 انتخاب می‌شوند، می‌سنجیم. در چنین حالتی، علاقه ما به کارایی یادگیرهای مختلف formula_18 با فضای فرضیه‌های مختلف formula_19 در یادگیری مجموعه توابع هدف مختلف درون formula_2 است. زیرا ما می‌خواهیم یادگیر formula_18 به اندازه کافی جامع باشد تا بتواند هر تابع هدف درون formula_2 را مستقل از اینکه توزیع formula_13 چیست، یاد بگیرد. در بعضی مواقع نیز علاقه داریم که بدترین حالت توابع هدف درون formula_2 را برای تمامی توزیع‌های formula_13 بررسی کنیم. چون علاقه ما به نزدیکی فرضیه خروجی formula_22 به تابع هدف حقیقی formula_3 است، پس کار را با تعریف خطای واقعی یک فرضیه formula_22 بر روی formula_3 و توزیع احتمال formula_13 شروع می‌کنیم. خطای واقعی formula_22، حطای formula_22 در دسته‌بندی نمونه‌های جدید با توزیع formula_13 است.
تعریف :‌ خطای واقعی(formula_45) فرضیه formula_22 برای تابع هدف formula_3 و توزیع احتمال نمونه formula_13 این است که نمونه انتخابی بر اساس توزیع formula_13 اشتباه دسته‌بندی شود. (در رابطه زیر، formula_50 نشان دهنده احتمال عبارت با فرض اینکه formula_10 از توزیع formula_13 پیروی می‌کند، می‌باشد.
formula_53
توجه کنید که خطا را طوری تعریف کرده ایم که که خطای تمامی نمونه‌های ممکن را اندازه بگیرد و فقط محدود به نمونه‌های آموزشی نباشد. بنابراین انتظار داریم که زمانی که از فرضیه بدست آمده بر روی نمونه‌های تصادفی جدید استفاده می‌کنیم، چنین خطایی داشته باشد. همچنین توجه کنید که این خطا به شدت به توزیع احتمال formula_13 وابسته است. برای مثال، اگر formula_13 توزیعی یکنواخت باشد که به تمامی نمونه‌های formula_1 احتمالی یکسان نسبت می‌دهد، خطای فرضیه آمده در شکل روبرو نسبت به نمونه‌های درون نواحی هلالی به تمامی نمونه‌ها خواهد بود. در نتیجه اگر formula_13 احتمال بیشتری به نمونه‌های نواحی هلالی نسبت دهد، خطا بیشتر خواهد شد. در بدترین حالت نیز،formula_13، احتمال صفر به نمونه‌های خارج نواحی هلالی و احتمال ۱ به نمونه‌های درون نواحی هلالی نسبت می‌دهد و خطا ۱ خواهد بود، با وجود اینکه formula_3 و formula_22 واقعا اشتراک دارند. توجه داشته باشید که خطای formula_22 برای formula_3 به‌طور مستقیم، برای یادگیر غیرقابل مشاهده است. formula_18 فقط کارایی formula_22 را بر روی نمونه‌های آموزشی، در دسترس دارد و باید انتخاب خود در مورد فرضیه را بر اساس همین معیار انجام دهد. ما از عبارات خطای آموزشی (در مقابل خطای واقعی) برای نمایش نسبت نمونه‌های آموزشی با دسته‌بندی اشتباه توسط formula_22 به کل نمونه‌های آموزشی استفاده می‌کنیم. قسمت بزرگی از بررسی ما از پیچیدگی یادگیری بر محور این سؤال متمرکز می‌شود که "چگونه احتمال دارد که خطای آموزشی مشاهده شده، معیاری غلط‌انداز از formula_45 باشد؟" است.
با وجود اینکه تمرکز، بیشتر بر مدل PAC می‌باشد،‌ تئوری یادگیری محاسباتی تعریف مسئله‌های دیگر را در بر می‌گیرد. تعریف مسئله‌های یادگیری مختلفی که مورد مطالعه قرار گرفته‌است، در نحوه ایجاد نمونه‌های یادگیری، نویز داده‌ها(با خطا یا بدون خطا)، تعریف موفق (مفهوم هدف باید یاد گرفته شود یا اینکه تقریباً با احتمال خاصی یادگرفته شود.)، فرض‌های یادگیر(شامل توزیع نمونه‌ای و اینکه formula_67) و معیاری که با آن یادگیر ارزیابی می‌شود (مانند تعداد نمونه‌های آموزشی، تعداد اشتباه‌ها، زمان کل یادگیری و ...)، متفاوت است. در این مدل، یادگیر با تعداد اشتباه‌هایش قبل از همگرایی به فرضیه درست، ارزیابی می‌شود. مشابه تعریف مسئله در مدل PAC، فرض کنید، یادگیر یک سری از نمونه‌های آموزشی را دریافت ‌‌می‌کند. با این وجود، در اینجا می‌خواهیم یادگیر، قبل از دریافت هر نمونه formula_10، مقدار تابع هدف formula_17 را(قبل از معلوم شدن مقدار درست هدف) پیش‌بینی کند. حال سؤال این است که "یادگیر قبل از یادگیری مفهوم هدف چه تعداد پیش‌بینی اشتباه خواهد کرد؟". اهمیت این سؤال در کاربرد عملی است، زیرا که یادگیری باید زمانی که سیستم در حال استفاده واقعی است، انجام شود، نه در مرحله آموزشی مجزا. برای مثال، اگر سیستم برای یادگیری پیش‌بینی اینکه چه پرداخت‌هایی برای یک کارت اعتباری باید ثبت شود و چه پرداخت‌‌،‌هایی تقلبی هستند، بر اساس اطلاعاتی که در حین استفاده از سیستم، جمع‌آوری می‌کند، طراحی می‌شود. بنابراین علاقه خواهیم داشت که تعداد اشتباهات قبل از همگرایی به تابع هدف کمینه شود. در اینجا تعداد کل اشتباهات، می‌تواند اهمیت بیشتری نسبت به تعداد کل نمونه‌های آموزشی داشته باشد. این مسئله یادگیری مرز خطا را می‌توان در شرایط خاص مختلفی مورد مطالعه قرار داد. برای مثال، ممکن است تعداد اشتباهات قبل از یادگیری PAC تابع هدف را بشماریم. اما در اکثر مثال‌ها قبل از اینکه یادگیر، مفهوم هدف را دقیقا یاد بگیرد، تعداد اشتباه‌ها را در نظر می‌گیریم. یادگیری مفهوم هدف به این معناست که به فرضیه‌ای میل کنیم که داشته باشیم:
formula_70