سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
از یک نامساوی در آمار و احتمال که در مورد مقایسه مقدار تخمین زده شده برای یک پارامتر و مقدار واقعی آن وجود داشت استفاده کردیم تا یک حد بالا برای اختلاف این دو مقدار به دست بیاریم. از این رابطه استفاده کردیم برای این مفهوم که در بحث یادگیری چیزی که مورد نظر ما هست اینکه اختلاف بین خطای روی داده‌های آموزش و خطای true رو کم کنیم. (از قبل هم به این حالت می‌گفتیم که مدل تعمیم‌پذیری خوبی داره)
منتها نمی‌تونستیم از این رابطه مستقیم استفاده کنیم. دلیلش هم این بود که این رابطه وقتی برقراره که ما از قبل راجع به نمونه‌ها چیزی ندونیم. مثلا وقتی 1000 تا سکه داریم هر کدوم رو 10 بار میندازیم، اگه بریم سکه‌ای رو برداریم که از بین 1000 تا سکه هر 10 بار رو اومده میزان رو اومدن رو 1 در آوردیم در حالیکه میزان واقعی 0.5 هست و این باعث میشه که مثلا اختلاف خطا تو این حالت 0.5 بشه و چون نمونه رو با آگاهی انتخاب کردیم امکان استفاده از این نامساوی رو نداریم. چون باعث میشه نتیجه‌ای که به دست میاد قابل اعتماد نباشه. پس چیکار کردیم؟ رابطه رو یکم تغییر دادیم و از اون استفاده کردیم.
برای رابطه‌ای که تغییر دادیم و بهش رسیدیم سه تا حالت مختلف رو بررسی کردیم و به حد بالاهای مختلفی رسیدیم. تو یک حالت فرض می‌کردیم که میزان خطای آموزش 0 بشه و حالا دو حالت دیگه‌ای هم بود که تو جلسه قبلی با جزییات بررسی و اثبات کردیم.
فرض کنید دسته‌بندی داریم که در یک محور یک‌بعدی، از یک نقطه به بعد سمت راست رو مثبت گزارش میکنه و از اون نقطه به قبل یعنی سمت چپ رو منفی (به این دسته‌بند positive rays گفته میشه). می‌خوایم تابع رشد رو در این مدل دسته‌بندها به ازای N سمپل به‌دست بیاریم. یعنی می‌خوایم ببینیم به ازای N سمپل چند نحوه برچسب‌دهی مختلف داریم.جواب میشه N+1 حالت مختلف. فرض کنید دو تا نمونه داشته باشیم. تو عکس پایین با قرمز نشون داده شدن. حالاتی که می‌تونیم برچسب‌گذاری‌های مختلف داشته باشیم با خط سبز نشون داده شده. دو تا سمپل داشتیم، حالات برچسب‌گذاری سه تا شد. همین رو به N سمپل تعمیم بدیم، به N+1 حالت برای برچسب‌دهی می‌رسیم.
برای درک بهتر حالت‌های مختلفی که می‌تونیم برچسب داشته باشیم رو تو تصاویر مختلف آوردم. تو حالت اول جوری تقسیم کردیم که هیچ نمونه منفی‌ای وجود نداره.
تو حالت دوم یک نمونه مثبت و یک نمونه منفی داریم.
تو حالت سوم همه نمونه‌ها به صورت منفی دسته‌بندی شدن.
همین رو میشه تعمیم داد به N نمونه.
حالا فرض کنید دسته‌بندی که داریم به این صورته که نمونه‌های داخل یک بازه رو مثبت میده و نمونه‌های خارج از اون بازه رو منفی (به این دسته‌بند positive intervals گفته میشه). تو این حالت تابع رشد به چه صورت میشه؟ جواب میشه (انتخاب 2 از N+1) + 1. حالا چرا؟ به این دلیل که برای انتخاب بازه همواره به دو نقطه نیاز داریم و بازه‌هایی که وجود میان تعدادشون یکی از تعداد سمپل‌ها بیشتره. پس میشه انتخاب 2 از N+1. چرا بعلاوه 1 می‌کنیم؟ برای حالتی که طول بازه 0 باشه و در نتیجه همه نمونه‌ها منفی بشن.
با استفاده از تابع رشد می‌تونیم تعریفی ارائه بدیم که در زمینه تئوری یادگیری خیلی معروفه. برای یک تابع فرضیه کوچکترین break point برامون خیلی ارزشمنده. مفهوم break point رو با مثال پرسپترون تو جلسه گذشته دیدیم که چی بود. حالا چرا کوچکترین break point برامون باارزشه؟ چون فرضا اگر نقطه k برابر با نقطه break بشه، از اونجا به بعد تمامی نقاط break point هستن و کوچکترین نقطه باعث میشه ما به حد بالای خیلی بهتری برسیم.
پس می‌خواهیم جایی رو به‌دست بیاریم که کوچکترین break point رو داره. یه نقطه قبل از break point آخرین جایی هست که نقاط می‌تونن توسط فضای فرضیه shatter بشن (یعنی تمام حالات برچسب‌دهی رو داشته باشه) به همچین جایی حد VC گفته میشه. یعنی حداکثر تعداد سمپل‌هایی که می‌تونیم به ازاشون همه نحوه‌های مختلف برچسب‌دهی رو ایجاد کنیم. به همچین جایی بُعد VC فضای فرضیه میگیم.
برای اثبات اینکه VC فضای فرضیه‌ای مثل H دقیقا برابر با k میشه باید به دو نکته توجه کنیم:
در ادامه چند مثال از VC و کلا نحوه استفاده ازش رو بررسی می‌کنیم.
اولین مثالی که بررسی می‌کنیم همون مثال positive rays هست که بالاتر هم دیدیم. چند نقطه دلخواه می‌تونیم پیدا کنیم که هرجوری برچسب‌گذاری شده باشن بتونیم با استفاده از تابع فرضیه جداشون کنیم؟ این رو هم باید در نظر داشته باشیم که سمت راست همواره داده‌های مثبت برچسب می‌خورن و سمت چپ داده‌های منفی. حالا چجوری به دست بیاریم؟ باید رابطه زیر برقرار باشه تا بتونیم shatter کنیم.
تابع رشد تو این دسته‌بند برابر بود با N+1. حالا به ازای کدوم مقدار از N دو عبارت 2 به‌توان N و N+1 باهم برابر میشن؟ در حالت N=1. تا اینجا فهمیدیم که مقدار VC می‌تونه 1 باشه. آیا مقدار VC می‌تونه برابر با 2 هم بشه؟ خیر. چرا؟ گفتیم این دسته‌بند از هرجا که بخواد تقسیم کنه داده‌هارو سمت راست همواره داده‌های مثبت باید بیفتن. تو مثال زیر فرض کنید داده منفی سمت راست باشه و داده مثبت سمت چپ. به هیچ طریقی امکان دسته‌بندی با این روش وجود نداره. پس مقدار VC نمی‌تونه 2 باشه. پس مقدار VC برابر با 1 شد.
دومین مثال حالتی هست که دسته‌بند inside intervals رو داریم. تو این حالت مقدار VC چند می‌تونه باشه؟ رابطه زیر باید برقرار باشه. چرا؟ چون عبارت سمت راست همون تابع رشد در این دسته‌بند هست. حالا به ازای کدوم مقدار N این رابطه برقرار هست؟ به ازای N=2 برقرار است.
پس تا اینجا مقدار VC می‌تواند 2 باشد. اگر مقدار VC برابر با 3 باشد چه؟ برقرار نیست. دلیلش در تصویر زیر واضحه. نمونه‌های سبز رنگ مثبت و نمونه قرمز رنگ منفی است. پس مقدار VC برای این دسته‌بند برابر با 2 است.
دو مثالی که تا اینجا دیدیم در اسلاید پایین آورده شده.
حالا همون رابطه‌ای که از قبل داشتیم رو بازنویسی کردیم. به‌جای k از مقدار VC استفاده کردیم.
مقدار VC رو برای پرسپترون در حالت دو بعدی محاسبه خواهیم کرد.
مقدار VC تو این مثال برابر با 3 میشه.
حالا می‌خوایم مقدار VC رو در حالتی که d بعد داریم برای پرسپترون محاسبه کنیم. به صورت کلی این مقدار برابر با d+1 میشه. اثباتش رو پایین‌تر توضیح میدیم.
ستون اول ماتریس که همشون یک هستن همون X0 میشه در نظر گرفت. نقاطی هم که انتخاب شدن دست خودمون بوده و به هر ترتیبی که دوست داریم می‌تونیم بچینیم.
از طرفی مطمئنیم که این ماتریس معکوس داره و معکوسش هم قابل محاسبه هست. چون انتخاب نقاط دست خودمون بوده جوری در نظر گرفتیم که معکوس داشته باشه. پس می‌تونیم روابط زیر رو داشته باشیم.
حالا تا اینجا نشون دادیم که برای d+1 نقطه با استفاده از پرسپترون نقاط قابل shatter شدن هستن.
حالا باید این رو نشون بدیم که به ازای d+2 تا نقطه قابل shatter شدن نیستن تا اثبات کامل بشه. d+2 تا نقطه در نظر گرفتیم در فضای d بعدی. مسلما از اونجایی که تعداد نقاطی که داریم از تعداد ابعادمون بیشتره، حداقل یکی از نقاط رو می‌تونیم به صورت ترکیب خطی بقیه بنویسیم.
حالا اون نقطه‌ای که از ترکیب خطی نقاط دیگه به‌دست اومده، از روی همون نقاط دیگه علامتش مشخص میشه. یعنی نقاط دیگه باعث میشن که اون نقطه علامت بگیره و بدون علامت نمونه و این چیز خوبی نیست. چون اون نقطه دیگه نمی‌تونه هم مثبت بشه هم منفی. فقط تابع نقاطی هست که از روشون ساخته شده و فقط یک علامت می‌گیره و عملا هیچ انتخابی نمی‌تونیم براش داشته باشیم.
پس نتیجه‌ای که گرفتیم این شد که مقدار VC برای این مثال d+1 هست و از طرفی برابر با تعداد پارامترهای پرسپترون هست.
تو دو مثالی که بالاتر بررسی کردیم، دسته‌بند positive rays و دسته‌بند positive interval مقداری که برای VC حساب کردیم، در واقع همون مقدار پارامترهای هر دسته‌بند هست. ولی آیا به صورت کلی هم برقرار هست؟ جلوتر بررسی می‌کنیم.
تعداد پارامترهای یک روش بهمون نشون میده که درجه آزادی موجود در فضای فرضیه چقدر هست. مثلا چند جمله‌ای‌های درجه بالاتر پارامترهای بیشتری دارن برای تنظیم کردن. یه جورایی درجه آزادی بیشتری دارن. چیزی که می‌خوایم بگیم اینکه VC یه جورایی داره به‌صورت موثر درجه آزادی مدل رو نشون میده ولی تعداد پارامتر لزوما نیست.
نکته دیگه‌ای هم که وجود داره اینکه که اگر به ازای همه نقاط تابع رشد به صورت 2 به‌توان N باشه، مقدار VC بی‌نهایت میشه. تو این حالت دیگه نمی‌تونیم بر اساس مقدار VC ارزیابی داشته باشیم. حالا سوال اینکه آیا دسته‌بندی هست که همچین چیزی توش برقرار باشه اصلا؟
فرض کنید دسته‌بندی داریم که هر نمونه رو با بقیه نمونه‌ها فاصله‌شو حساب میکنه بعد اون نمونه‌ای که از همه بهش نزدیک‌تره هر برچسبی داشته باشه همون رو اختصاص میده بهش. پس هر نقطه‌ای از فضا نزدیک‌ترین نمونه بهش پیدا میشه و برچسب همون رو می‌گیره. تو این دسته‌بند خطای آموزش به ازای همه نمونه‌ها 0 میشه. به این دلیل که هر نقطه از همه به خودش نزدیک‌تر پس برچسب خودش رو می‌گیره و بنابراین میزان خطا 0 میشه. یعنی تو این دسته‌بند هیچ break point وجود نداره. تو این حالت VC بی‌نهایت میشه که خوب نیست. تو این حالت یعنی انگار به میزان ثابتی بین خطای آموزش و خطای true فاصله افتاده و به هیچ طریقی هم نمی‌تونیم این فاصله رو پوشش بدیم. این فاصله ثابته و دیگه رابطه‌ای با تعداد سمپل نداره.
در مورد یادگیری instance base (که یه نمونه ازش رو تو مثال بالا دیدیم) زیاد کردن تعداد نمونه‌ها از یه جایی به بعد دیگه هیچ تاثیری تو نزدیک شدن دو مقدار خطا نداره بر خلاف یادگیری پارامتریک و روش‌هایی که تا الان داشتیم.
منظور از یادگیری consistent این هست که زیاد کردن تعداد نمونه‌ها باعث میشه میزان دو خطا بهم نزدیک بشه.
قضیه مهمی وجود داره و میگه زمانی یک مدل consistent هست که مقدار VC بی‌نهایت نباشه. برعکس این قضیه هم برقراره. در ضمن وقتی مقدار VC محدود باشه، می‌تونیم در مورد تعمیم‌پذیری مدل هم نظراتی داشته باشیم.
اصل مطلبی هم که در موردش تا الان صحبت کردیم به صورت خلاصه‌وار پایین اومده.
چه نکته منفی‌ای در مورد حدبالایی که به‌دست میاریم وجود داره، از اونجایی که مستقل از الگوریتم یادگیری، تابع هدف، و توزیع ورودی‌هاست؟
باعث میشه خیلی در عمل نتونیم ازشون استفاده کنیم. اما با این وجود برای مقایسه تعمیم‌پذیری تو روش‌های مختلف قابل استفاده هست. در ضمن هرچقدر مقدار VC کمتر باشه باعث میشه که تعمیم‌پذیری بهتری داشته باشیم.
یک قانون سر انگشتی وجود داره و میگه اگر تعداد نمونه‌ها حداقل 10 برابر VC باشه، میشه گفت تعمیم‌پذیری نسبتا خوبی داریم. یعنی فاصله خطای آموزش و true خیلی زیاد نمیشه.
دو تا نمودار پایین اومده که نمودار سمت چپ مقادیر بایاس و واریانس رو در مسئله رگرسیون نشون میده و نمودار سمت چپ هم مربوط به مباحث همین جلسه و VC در مسئله دسته‌بندی هست.
خلاصه حدهایی که به‌دست آوردیم اینجا آورده شده.
این موضوع در عمل خیلی کاربردی نداره، اما از نظر مفهوم و تئوری خیلی مهمه. کاری که اینجا می‌کنیم به این صورته که انگار فضای فرضیه رو به صورت سلسله مراتبی دسته‌بندی می‌کنیم. مثلا فرضیه‌های داخل H1 رو خطوط در نظر می‌گیریم، H2 فرضیه‌های درجه 2 و خطوط رو هم که می‌تونه شامل میشه نشون میده و همینطور الی آخر. روابط ریاضی این فرضیه‌ها تو اسلاید پایین آورده شده.
اگر هر کدوم از این فرضیه‌ها رو از داخلی‌ترین تا بیرونی‌ترین تو محور افقی شکل بچینیم و تو محور عمودی هم میزان خطارو رسم کنیم به نمودارهای زیر می‌رسیم. هرچقدر فضای فرضیه بیشتر و پیچیده‌تر میشه میزان ارور روی داده‌ها (خطای آموزش) کمتر میشه. از طرفی هرچقدر فضای فرضیه زیاد میشه، مقدار VC زیاد میشه و زیاد مقدار VC باعث میشه مقدار Capacity بیشتر بشه. حالا حدی (bound) که روی خطای true به‌دست میومد برابر بود با حاصل جمع Capacity و خطای آموزش که با نمودار خاکستری نشون داده شده. مدلی رو انتخاب می‌کنیم که نمودار خاکستری توش از همه کمتر شده باشه.
به صورت کلی استفاده عملی‌ای که از SRM می‌کنیم زمانی هست که دو تا مدل مختلف خطای آموزش روشون یکسان شده ولی نمی‌دونیم کدوم رو انتخاب کنیم. اونی که مقدار VC توش کمتر شده باشه انتخاب میشه.
به صورت کلی در مورد تئوری یادگیری صحبت کردیم و با مفاهیم VC و SRM آشنا شدیم و حالات مختلف رو براشون بررسی کردیم.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
