سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
به صورت کلی در دو جلسه (این جلسه و جلسه بعدی) راجع به مباحث زیر توضیح خواهیم داد.
اگر یک دسته‌بند یا regressor روی مجموعه داده‌های آموزش داشته باشیم، چگونه مطمئن شویم که روی نمونه‌های جدید هم درست کار می‌کند؟ در این بخش از درس این مورد را بررسی خواهیم کرد. در جلسات اولیه درس هم دیدیم که به ازای یک مجموعه سمپل نمی‌توانیم حدس بزنیم که جواب دقیقا چه خواهد بود و ممکن است حالت‌های متعددی داشته باشد.
دو سوال به صورت کلی وجود داره:
چیزی که در این بخش از درس برایمان مهم است پیدا کردن پاسخ سوال اول است. به صورت کلی دنبال این هستیم که اگر روی مجموعه داده‌ای دسته‌بندی قرار دادیم و به صورت مناسبی عمل کرد، با احتمال خوبی مطمئن باشیم که روی نمونه‌های جدید هم به خوبی عمل خواهد کرد.
قبل از اینکه بحث یادگیری رو ادامه بدیم، نیاز به مرور بحث نامساوی در آمار و احتمال در قالب یک مثال داریم. فرض کنید ظرفی داریم که داخل آن تعدادی گلوله سبز و قرمز قرار گرفته است. تعدادی نمونه از این ظرف بیرون آورده‌ایم. چیزی که می‌خوایم بررسی کنیم اینکه با چه احتمالی گلوگه‌های این ظرف قرمز هستند. طی انجام یک آزمایش به این جواب می‌رسیم که احتمالا تعداد گلوله‌های قرمز 'u است و تعداد واقعی گلوله‌های قرمز رو هم u در نظر گرفتیم.
یک نامساوی در آمار و احتمال وجود دارد که رابطه بین 'u و u را نشان می‌دهد. احتمال اینکه فاصله چیزی که محاسبه کردیم از مقدار واقعی خودش از اپسیلون بیشتر باشه، کوچیک‌تر مساوی یک عددی هست. جزییات این رابطه در زیر آورده شده است. اپسیلون میزان دقت است و N تعداد نمونه‌ها را مشخص می‌کند. به صورت احتمالی راجع به این رابطه صحبت می‌کنیم.
تصیویر زیر جزییات مسئله‌ای که مطرح کردیم را مشخص می‌کند.
مجموعه H رو فضای فرضیه در نظر گرفتیم و به صورت کلی یک مسئله کلسیفیکیشن داریم.
حالا اصلا چطور می‌خوایم نامساوی‌ای که بالاتر دیدیم رو به بحث یادگیری ربط بدیم و ازش استفاده کنیم؟ فرض کنید در جاهایی که تابع فرضیه برابر با هدف هست گلوله‌های سبز در نظر بگیریم و جاهایی که برابر نیستند رو برابر با گلوله‌های قرمز. از اونجایی که گلوله‌های قرمز رو معادل با خطا در نظر گرفتیم، احتمال گلوله‌های قرمز همان خطای true می‌شود.
تعاریف مختلف خطا در اسلاید پایین آورده شده است.
آیا می‌توانیم با استفاده از تعاریف بالا، به رابطه زیر برسیم؟ محتوای ظرف که سبز است یا قرمز تحت تاثیر تابع H است و انگار ظرف ثابت نیست و هویتش تغییر می‌کنه. مستقیم نمی‌تونیم از رابطه پایین استفاده کنیم. فرض کنید یک آزمایش داریم که در آن یک سری سکه داریم که با احتمال 0.5 رو و با احتمال 0.5 پشت می‌آیند. اگر 1 سکه داشته باشیم و برای مثال 6 بار آن را پرتاپ کنیم و هر 6 دفعه سکه رو بیاید، می‌توانیم از این نامساوی استفاده کنیم و متوجه شویم که با چه احتمالی در کل سکه رو می‌آید. در آزمایش دیگری فرض کنید 1000 سکه داریم و آن‌ها را 10 بار پرتاپ کردیم. بعد از دیدن نتیجه سکه‌ای که از همه کمتر رو آمده است را انتخاب کرده‌ایم. آیا همچنان این نامساوی در آن صدق می‌کند؟ خیر. چرا؟ چون می‌دانیم در حالت کلی احتمال رو آمدن سکه 0.5 است، اما چون مشاهده خود را فقط به همان نمونه که با احتمال کمتری سکه رو بیاید محدود کرده‌ایم فرضا به احتمال 0 رسیدیم (مثلا در 10 پرتاب باری رو نیامده باشد) در شرایطی مشابه، در همین مثال پایین نیز قادر به استفاده مستقیم از این رابطه نیستیم. چون تابع H وابسه به مشاهداتمان است.
پس چگونه از این رابطه کمک بگیریم؟ در ادامه خواهیم دید.
اگر M فرضیه مختلف در فضای فرضیه داشته باشیم، هر دور که فرضیه رو عوض می‌کنیم درصد گلوله‌های سبز و قرمز تغییر می‌کنه. چرا؟ چون درصد گلوله‌های قرمز نشون دهنده true error هست و هر بار که فرضیه تغییر می‌کند این خطا نیز عوض می‌شود.
مثالی که در اینجا آورده شده است، شبیه مثال سکه‌هاست که پیشتر دیدیم. اما نکته دیگری نیز وجود دارد. هرچقدر سایز فضای فرضیه را بزرگ در نظر بگیریم، احتمال اینکه یک فرضیه پیدا شود که به نمونه‌های train فیت شود بیشتر می‌شود.
یک فرضیه به‌نام f از داخل فضای فرضیه با توجه به نمونه‌هایی که در اختیار داشتیم برداشته‌ایم. پس مستقیما نمی‌توانیم از رابطه نامساوی Hoeffding استفاده کنیم. اما می‌توانیم به طریقی دیگر این رابطه را بنویسیم. به صورت خاص نمی‌توانیم در مورد خود f نظری داشته باشیم اما می‌دانیم که فرضیه f از داخل یک فضای فرضیه انتخاب شده است، اگر این رابطه برای خود f صدق نکند اما بالاخره یک فرضیه دیگر در این فضا وجود دارد که در مورد آن صدق می‌کند. پس احتمال صدق کردن این رابطه در مورد f کوچک‌تر مساوی احتمال صدق کردن همین رابطه در مورد یکی از فرضیه‌های دیگر می‌شود.
عبارت "وجود دارد یک" را می‌توان به OR تبدیل کرد و به صورت زیر در آورد. در نهایت یک تقریب کلی زده‌ایم و به رابطه زیر رسیده‌ایم. اما به صورت کلی، تقریب زیر تقریب خوبی نیست. چرا؟ چون ممکن است این جملات باهم اشتراک داشته باشند.
رابطه‌ای که به دست آوردیم را اگر در یک منفی ضرب کنیم و مقدار 1 را از آن کم کنیم به رابطه زیر می‌رسیم.
اگر اپسیلون را بر اساس دلتا بنویسیم به رابطه زیر می‌رسیم. با زیاد شدن تعداد سمپل‌ها (N) اپسیلون که بر حسب دلتا نوشته شد کم‌کم از بین میره و خیلی کوچیک میشه. از طرفی دیگه هر چقدر سایز فضای فرضیه بیشتر بشه، فاصله دو خطا از هم بیشتر میشه.
رابطه‌ای که بالا به‌دست آوردیم رو می‌تونیم به شکل دیگری هم بنویسیم.
نامساوی‌ای که اول دیدیم تو حالت عام‌تری بود. در اینجا یه نامساوی خاص‌تر رو خواهیم دید که اثبات ساده‌تری هم دارد. حالتی که اینجا بررسی می‌کنیم حالتیه که فرض کنیم حتما یک فرضیه در فضای فرضیه داریم که خطای train به ازای اون برابر با 0 میشه. تو حالت قبلی صرفا روی فاصله خطای true و خطای train بحث می‌کردیم. حالا پس اینجا نامساوی که تو حالت بالاتر دیدیم فقط جمله خطای true براش باقی‌می‌مونه که تو خط آخر اسلاید پایین آورده شده.
شکل زیر هم در مورد فرض اولیه‌ای که کردیم هست. اینکه یک فرضیه‌ای وجود داشته باشه که خطای آموزش روی اون 0 بشه.
به نامساوی اسلاید پایین که از روی روابطی که تا الان دیدیم به‌دست اومده، به اصطلاح نامساوی Hussler گفته میشه.
در ادامه می‌خواهیم این نامساوی رو اثبات کنیم.
احتمال اینکه این فرضیه یک نمونه رو درست دسته‌بندی کنه چقدر هست؟ کمتر از مقدار 1 - اپسیلون. حالا احتمال اینکه N نمونه رو درست دسته‌بندی کنیم چقدر هست؟ باید احتمال دسته‌بندی درست یک نمونه رو N بار در هم ضرب کنیم. (هر دو رابطه در پایین اسلاید اومده)
فرضیه‌هایی که داشتیم رو اینجوری در نظر گرفتیم که ارور آموزش روشون 0 باشه و ارور true از اپسیلون روشون بیشتر شه. فرض کنید اصطلاحا به اینا فرضیه‌های بد بگیم. حالا می‌خوایم این رو حساب کنیم که چقدر احتمال داره که از این فرضیه‌های بد در فضای فرضیه‌مون وجود داشته باشه. فرض کنید k تا از این فرضیه‌های بد وجود داره که از h1 تا hk مشخص شدن. در آخر گفته مقدار k در بدترین حالت برابر با کل فضای فرضیه میشه برای همینم تونسته از H که کل فضای فرضیه رو نشون میده تو رابطه استفاده کنه. تو آخرین خط نوشته شده تو اسلاید پایین هم صرفا از یک معادل‌سازی استفاده کرده.
کل چیزی که الان بهش رسیدیم تو اسلاید زیر آورده شده:
در صورتی که در رابطه بالا مقدار N و مقدار اپسیلون رو بخوایم تنها کنیم به روابط زیر می‌رسیم:
برای اینکه مطالبی که تا اینجا دیدیم بهتر جا بیفته، یک مثال ببینیم.
فرض کنید یک فضای فرضیه خیلی ساده داریم که فقط یک قانون برای مشخص کردن کلاس مثبت داره که از روی AND کردن خود فیچرها یا نقیضشون به‌دست میاد. از طرفی لزوما هم قرار نیست تمامی فیچرها یا نقیضشون ظاهر بشه. اگر تعداد ویژگی‌هامون d باشه تعداد فضای فرضیه‌مون 3 به‌توان d میشه. (هر ویژگی سه حالت داره، یا خودش ظاهر میشه، یا تقیضش، یا هم کلا ظاهر نمیشه) حالا فرض کنید تو این مثال برای مقادیر دلتا و اپسیلون هم مقادیر ثابتی در نظر گرفته شده. به ازای d های مختلف اومده نامساوی‌ای که بالاتر دیدیم رو حساب کرده.
یک مثال دیگه هم که بررسی کرده درخت تصمیم تا عمق دوم هست. برخلاف اینکه درخت تصمیم هست و قواعد خیلی پیچیده هستن ولی سایز فضای فرضیه کوچیک‌تر شده. دلیلش هم این هست که عمق درخت رو به صورت ثابت 2 در نظر گرفتیم تو این مثال.
تا اینجا دو موردی که بررسی کردیم و اثبات کردیم، در حالتی بود که سایز فضای فرضیه رو محدود در نظر گرفته بودیم. حالا می‌خوایم حالتی رو بررسی کنیم ببینیم اگر فضای فرضیه رو خیلی بزرگ یا بی‌نهایت در نظر بگیریم چطور میشه.
به صورت کلی اثبات این حالت خیلی پیچیده‌تره و اینجا هم با جزییات بررسی نمیشه صرفا برای درک بهتر یک شهود ازش گفته میشه.
برای این کار اول یک سری مفاهیم رو باید تعریف کنیم.
اولا، به دسته‌بندی که داده‌هارو به دو کلاس مثبت و منفی دسته‌بندی می‌کنه dichotomy گفته میشه. دوما، فرضیاتی که داده‌هارو به یک صورت دسته‌بندی می‌کنن باهم یکی در نظر می‌گیریم. در نهایت هم یک growth function داریم که حداکثر تعداد نحوه‌های مختلف برچسب‌دهی به n سمپل با استفاده از فضای فرضیه رو نشون میده.
یه مثال ببینیم از چیزی که تا اینجا گفتیم.
فرض کنید دسته‌بندی که داریم پرسپترون هست. فضای ویژگی‌مون رو هم دو بعدی در نظر بگیرید. همچنین فقط 3 تا نمونه داریم که می‌خوایم روشون بررسی کنیم. اگه فرضیات داخل فضای فرضیه پرسپترون رو در نظر بگیریم، این 3 نقطه چند نحوه برچسب‌دهی خواهند داشت؟ 8 حالت مختلف میشه. حالا اگه 4 تا نمونه داشته باشیم، نحوه برچسب‌دهی با پرسپترون 16 حالت میشه؟ خیر 14 حالت میشه. یک سری حالت‌های غیر خطی رو پرسپترون نمی‌تونه هندل کنه. تو growth function ما حالتی رو در نظر می‌گیریم که حداکثر میزان برچسب‌دهی رو بتونیم داشته باشیم.
اگر به ازای N سمپل همه نحوه‌های مختلف برچسب‌دهی در فضای فرضیه باشه، اصطلاحا می‌گیم که فضای فرضیه N سمپل رو shatter می‌کند.
معمولا عددی که برای growth function به‌دست میاد، به‌جای اینکه خود 2 به‌توان N باشه، معمولا یه چندجمله‌ای برحسب N میشه. حالا در چه صورتی این اتفاق میفته؟ تعدادی نقطه پیدا کنیم به‌صورتی که با فضای فرضیه shatter نشن (k تا نقطه که با فضای فرضیه shatter نمیشن) در این صورت، مقدار growth function می‌تونه چندجمله‌ای بشه.
مثلا تو الگوریتم پرسپترون با فضای ویژگی دو بعدی (مثال بالاتر) مقدار k برابر با 4 میشه و اگر تعداد نمونه‌ها به 4 برسه تو فضای فرضیه shatter نمیشن.
قضیه‌ای وجود داره که میگه در این حالت (حالتی که اگر تعداد نمونه‌ها k بشه و دیگه قابل shatter شدن تو فضای فرضیه نباشه) حد بالا از طریق یه رابطه‌ای به دست میاد. اون رابطه پایین اسلاید پایین آورده شده.
حالا حدی که بهش می‌رسیم به صورت زیر تعریف شده. همونطور که مشخصه مشکل حالت قبلی رو نداره. فضای فرضیه تو رابطه‌ش وجود نداره برای همین حتی اگه فضای فرضیه بی‌نهایت هم بشه مشکلی به‌وجود نمیاد.
فرض کنید تو هر کدوم از این مستطیل‌ها هر نقطه معادل با مجموعه داده‌ای بشه که روی اون داریم آموزش رو انجام میدیم. تو حالتی که از Hoeffding استفاده می‌کردیم یک فرضیه داشتیم. در یک‌جاهایی که فاصله خطای train و خطای true از اپسیلون بیشتر میشد اتفاقات بدی میفتاد. فرض کنید برای فرضیه اول این مکان‌هارو با رنگ قرمز نشون بدیم. حالت دومی که بررسی کردیم می‌گفت هر کدوم از فرضیه‌ها یک جایی مختص خودشون دچار خطا میشن. ولی این درست نیست چون ممکنه هم‌پوشانی باهم داشته باشن و از هم جدا نباشن. حالت سوم چیزی که نشون میده اینکه اگر یک فرضیه تو نقطه‌ای دچار خطا بشه خیلی محتمله که فرضیه‌های دیگه هم تو اون نقطه یا نزدیک اون نقطه دچار خطا بشن. یه جورایی ایراد حالت دوم رو برطرف کرده که می‌گفت اصلا هم‌پوشانی وجود نداره.
سه حالت مختلف رو برای اختلاف میزان خطای train و خطای true به‌دست آوردیم و بررسی کردیم. برای هر کدوم به یک حد بالای خاص رسیدیم. در جلسه بعدی با جزییات بیشتری حالت سوم رو بررسی خواهیم کرد.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
