جزوه دوره یادگیری ماشین دکتر مهدیه سلیمانی - جلسه ششم - رگرسیون با دیدگاه احتمالاتی، کلسیفیکیشن

سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.محتوای این جلسهحل مسئله رگرسیون با دیدگاه احتمالاتی (پیش‌نیاز این مباحث، جلسه دوم است.)شروع مسئله کلسیفیکیشن و دسته‌بندیرگرسیون با دیدگاه احتمالاتیتا اینجا تو روشی که داشتیم پراکندگی نمونه‌هارو با یک تابع مدل می‌کردیم. حالا می‌خوایم با استفاده از مدل‌های احتمالاتی این کارو انجام بدیم و توزیع رو تشخیص بدیم. در واقع می‌خوایم ببینیم تو هر نقطه x احتمال y چقدره. انگار می‌خوایم تو هر نقطه از x ببینیم نقاط چه توزیعی دارن. (نمودار آبی رنگ داره تو شکل پایین این رو نشون میده) می‌خوایم p(y|x) رو مدل کنیم.تو دیدگاه احتمالاتی مدل کردن به صورت پارامتریک چجوری بود؟ تو جلسه دوم راجع بهش مفصل توضیح دادیم. اینجوری بود که میومدیم یه مدل پارامتری در نظر می‌گرفتیم بعد سعی می‌کردیم از روی داده‌ها پارامترها رو پیدا کنیم.تو اسلاید پایین منظورمون از اون فرمول نوشته شده اینکه میانگین تو هر نقطه از x برابر میشه با داده‌هایی که حول f(x; w) هستن (تو شکل بالا نمودارش قرمز رنگه) و یه واریانس ثابت هم براش در نظر گرفتیم که مشخص کننده نویز حول تابع است.الان کلا دنبال چی هستیم و می‌خوایم چیکار کنیم؟ یه داده train داریم که می‌خوایم ازش یه خطی رو بگذرونیم (شکل تصویر بالا) به نحوی که تخمین خوبی باشه برای توزیع نقاط باشه. حالا کدوم توزیع؟ توزیع f(x; w). به عبارت دیگه می‌خوایم نقاط خوبی رو از اون توزیع انتخاب کنیم. حالا تو دیدگاه آماری و تخمین آماری چجوری میومدیم اون نقاط خوب رو انتخاب می‌کردیم؟ معیارمون چی بود؟ مثلا تو دیدگاه likelihood اینجوری بود که مقدار maximum likelihood رو به دست بیاریم. یعنی مقدار likelihood بیشینه بشه.خط اول تعریف کلی likelihood رو نشون میده و خط دوم مسئله‌ایه که دنبالشیم. با پارمتر تتا توزیع شرطی (y|x) مشخص شده، حالا می‌خوایم طوری مقدار پارامتر تتا رو پیدا کنیم که وقتی مقدار توزیع شرطی روی نمونه‌های مختلف به دست میاد و در هم ضرب میشه، در کل مقدارش ماکسیمم بشه.الان تو شکل پایین چرا اون خطی که در نظر گرفتیم تخمین خوبی نیست؟ بخاطر اینکه تفاضل y از مقدار خط عدد بزرگی میشه و باعث میشه مقدار احتمال عدد کوچیکی بشه در نهایت ضربشون هم عدد کوچیکی میشه. به همین نسبت هرچقدر اون اختلاف کوچیکتر باشه باعث میشه عدد احتمال بزرگ‌تر بشه.همه چیزایی که گفتیم تو تصویر پایین اومده. دنبال این هستیم که حاصل ضرب بیشینه رو به دست بیاریم.تو جلسه دوم هم دیده بودیم که می‌تونیم به‌جای خود likelihood ازش لگاریتم بگیریم و مقدار اونو حساب کنیم. جواب نهایی فرقی نداره.تا اینجا تابع likelihood رو به دست آوردیم. از اینجا به بعد میریم سراغ بیشینه کردنش. حالا این بیشینه کردن یعنی پیدا کردن یه وزن مناسب که باعث بشه بیشترین جواب رو پیدا کنیم. حالا از طرفی دیگه می‌دونیم که پیدا کردن بیشینه یه تابع برابره با پیدا کردن مینیمم منفی اون تابع.تو رویکرد قبلی هم می‌خواستیم تابع هزینه رو مینیمم کنیم. حالا با این تعریفی که بالا کردیم داریم دقیقا همین کارو انجام می‌دیم.حالا مقدار سیگما به توان 2 چی میشه؟ می‌تونیم مشتق بگیریم و برابر با 0 بذاریم. تعریفی که برای واریانس به دست میاد دقیقا همون چیزی میشه که می‌دونیم از قبل.تا اینجا با تعریف maximum likelihood دقیقا به همون جوابی که می‌خواستیم رسیدیم. یعنی مینمم کردن تابع هزینه. حالا بریم مسئله رو با دیدگاه MAP حل کنیم ببینیم همون میشه یا نه.می‌خوایم روی پارامترهامون که W هست یه prior در نظر بگیریم و بعد به کمک likelihood که تو قسمت قبلی محاسبه کردیم، سعی کنیم مقدار بهینه پارامتر رو به دست بیاریم.مقداری که برای prior در نظر گرفته با p(w) مشخص شده. ببینیم چجوری به این مقدار رسیده. اگه به ازای هر w یه گاوسی با تعریف زیر داشته باشیم:می‌تونیم برای کل W تعریف زیر رو داشته باشیم، یعنی ضرب همه این گاوسی‌ها در هم:به این طریق به اون تعریف بالا رسیده.حالا چرا مقدار میانگین رو 0 در نظر گرفتیم؟ بخاطر اینکه با این کار می‌تونیم مقادیری از w رو به دست بیاریم که به 0 نزدیک باشه. انگار داریم از همون اول به مقادیر کوچیکی از w اولویت بیشتری میدیم.حالا باید در مقدار MAP مقدار likelihood رو ضرب کنیم و بعد مقدار W رو به گونه‌ای پیدا کنیم که حاصل رو بیشینه کنه.حالا پیدا کردن ماکسیمم رابطه بالا معادل میشه با پیدا کردن مینمم منفی اون روابط. (قبلا دلیلش رو گفتیم) پس اول اومدیم تو روابط بالا -2 ضرب کردیم و از این بعد دنبال پیدا کردن مینمم روابط زیر هستیم. در ادامه اومدیم جمله sigma^2 رو در طرفین ضرب کردیم. (از اونجایی که این جمله مثبته تاثیری تو جواب نداره) مثل این می‌مونه که انگار بیایم رابطه بالا رو با یه ترم regularization به مقدار sigma^2/alpha^2 جمع کنیم.پس چی شد تا اینجا؟ یه فرض اولیه داشتیم، گفتیم یه توزیع گاوسی با میانگین صفر داریم اول کاری و داده‌هامون از اون توزیع میان. این باعث شد که در نهایت یه ترم regularization هم تو تخمین MAP ظاهر بشه. تابع هزینه بستگی به توزیعی داره که اول کاری در نظر می‌گیریم. اگر به جای توزیع گاوسی از یه توزیع دیگه استفاده می‌کردیم تابع هزینه جور دیگه‌ای میشد.حالا ببینیم اگه با دیدگاه Bayesian مسئله رو حل کنیم به چه صورت میشه.دیدگاه Bayesian اینجوری بود که به‌جای اینکه از اول یه گاوسی رو در نظر بگیریم، چند تا گاوسی داشتیم و بعد به هرکدوم یه وزنی رو اختصاص می‌دادیم.حالا اگه انتگرال رو حل کنیم به جواب زیر می‌رسیم:حالا جوابی که اینجا به دست میاد با جوابی که قبلا به‌ دست آوردیم باهم فرق دارن. در قالب یه مثال فرقشو می‌بینیم.هر دور واریانسی که این جواب بهمون میده تو نقاط مختلف x متفاوته. یعنی تو قبلیا مقدار نویز انگار یه چیز ثابت بود، ولی اینجا با توجه به اینکه چند تا سمپل از x داریم هر دفعه متفاوت شده.عکس زیر داره همین دیدگاه Bayesian رو مشخص میکنه. همین که گفتیم تو هر مرحله تعدادی گاوسی هست که به هر کدوم با یه وزنی اهمیت میده رو نشون میده. میبینیم که هر چقدر تعداد داده‌ها بیشتر شده به تخمین بهتری رسیده.کلسیفیکیشن و دسته‌بندیتو این نوع قراره به ازای هر ورودی یه خروجی گسسته داشته باشیم. مثلا یه عکس تو ورودی بدیم، تو خروجی برامون مشخص کنه که آیا رقمی که اون عکس داره نشون میده چنده. (بین 0 تا 9) برخلاف رگرسیون که یه تابع هزینه ثابت داریم و همواره از اون استفاده می‌کنیم، تو این نوع از مسئله‌ها چندین تابع هزینه داریم و باید باهم مقایسه کنیم تا بفهمیم برای مسئله‌ای که داریم کدومش بهتره.موضوعاتی که قراره به صورت کلی تو این بخش از درس بررسی کنیم به شرح زیره:خروجی‌مون که y هست می‌تونه مقادیر گسسته از 1 تا K داشته باشه.حالا دو نگاه مختلف برای حل اینجور مسائل داریم:به صورت کلی می‌خوایم دسته‌ها رو مشخص کنیم. فرض کنید شکل زیر رو داریم:اولین راه اینکه بیایم مرزها رو مشخص کنیم.دومین راه اینکه بیایم به ازای هر کلاس یه تابع داشته باشیم. مثلا سه تا تابع مختلف f1، f2 و f3 داشته باشیم برای سه کلاس تصویر بالا. بعد هرجایی این توابع بیشترین مقدار رو داشتن بگیم اونجا برای همون کلاسه. پس یعنی انگار اینجوریه که ما به ازای هر کلاس یه تابع داریم، بعد میایم این توابع رو بررسی می‌کنیم و می‌فهمیم که هر تابع داره کدوم بخش رو مشخص می‌کنه.حالا اگه با دیدگاه دوم پیش بریم، در نهایت می‌تونیم مرزهارو هم به سادگی تشخیص بدیم. مرز بین کلاس‌ها میشه جایی که توابع هر کلاس باهم مقدارش یکی میشه.مسئله کلسیفیکیشن با دو دستهتو این مسئله دو تا کلاس داریم. فرض کنید می‌خوایم دو تا تابع مختلف هم در نظر بگیریم. برای کلاس اول تابع f(x) رو در نظر می‌گیریم و برای کلاس دوم منفی این تابع رو. پس اینجوری می‌تونیم مشخص کنیم.دسته‌بند خطیمنظورمون از دسته‌بند خطی یا linear classifier اینکه بیایم مرز جداکننده بین کلاس‌هارو خطی در نظر بگیریم. با این دلیل که خطی بودن مرز کار رو خیلی ساده‌تر میکنه و باعث میشه چالش کمتری داشته باشیم.حالا برای مثال بریم برای مسئله دو کلاسه یه linear classifier پیدا کنیم.یه تابع خطی در نظر گرفتیم. هرجا این تابع مقدارش مثبت باشه برای دسته اول در نظر می‌گیریم، هر جا منفی باشه برای دسته دوم. حالا مرز این دو کلاس چی میشه؟ میشه جایی که مقدار این تابع 0 شده. از نظر هندسی این فضا معادل با یه ابر صفحه میشه. یعنی انگار یه صفحه داریم که اومده دو تا کلاس رو از هم جدا کرده.یه مثال از چیزی که تا اینجا گفتیم:حالا تو این بخش نیاز به یه سری مباحث هندسه داریم تا به کمکش یه سری فرمول که به کارمون میاد رو بنویسیم.فاصله علامت‌دار نقطه x از صفحه H از طریق رابطه زیر به دست میاد:حالا برای اینکه ببینیم چجوری به این رابطه رسیدیم، روابط زیر رو در نظر بگیرید:فرض کنید بیایم x رو به صورت جمع فاصله عمودش از صفحه و فاصله مبدا از صفحه بنویسیم. بعد مقداری که برای x به دست آوردیم رو جایگزین کنیم تو فرمول.حالا اصلا کاربرد این رابطه‌ای که دیدیم چیه؟ بعدها ازش استفاده می‌کنیم و داره بهمون فاصله رو نشون میده. اگر نقطه‌ای که روی صفحه نباشه رو تو این فرمول جایگذاری کنیم بهمون یه عددی غیر صفر میده. حالا هرچقدر این فاصله بیشتر باشه اون عدد بزرگتر میشه. پس یعنی تو مقایسه دو تا نقطه، هر نقطه‌ای که عدد بیشتری داشته باشه تو این فرمول، از صفحه مورد نظرمون دورتره.همه چیزایی که گفتیم تا اینجا خلاصه‌وار تو شکل زیر اومده:از نظر هندسی هم اگه بخوایم تو کلاس رو از هم جدا کنیم و مرزشون رو نشون بدیم اینطور میشه:بررسی حالت غیرخطیحالا تو مثال زیر یه نمونه از حالتی رو داریم که به صورت غیرخطی اومدیم داده‌هارو از هم جدا کردیم. حالا چون این فضا غیر خطیه نمی‌تونیم با یه خط این‌هارو از هم جدا کنیم. پس اول باید بیایم فضا رو عوض کنیم، بعد جواب مورد نظر رو پیدا کنیم.تابع هزینه در دسته‌بندی خطیاول بریم سراغ همون تابع هزینه‌ای که تو رگرسیون خطی دیدیم. ببرسی کنیم که آیا اون می‌تونه تابع هزینه خوبی اینجا برامون باشه یا نه.فرض کنید نمونه‌های مثبت و منفی رو با این خط از هم جدا کردیم. حالا اگر طبق همون تابع هزینه قبلی پیش بریم چه اتفاقی میفته؟ به ازای نمونه‌های مثبت و نمونه‌های منفی که درست دسته‌بندی شدن ولی از خط دورتر قرار گرفتن انگار یه میزان پنالتی در نظر می‌گیره. پس باعث میشه که به این نتیجه برسیم که تابع هزینه رگرسیون خطی برای این مسئله به درد نمی‌خوره. چرا؟ به این دلیل که ما می‌خوایم مقدار تابع هزینه یه چیزی نزدیک 1 بشه، ولی چون این نقطه‌ها خیلی از خط فاصله دارن، باعث میشن مقدار تابع هزینه خیلی بیشتر از 1 بشه (با وجود اینکه به درستی دسته‌بندی شدن ولی مقدار تابع هزینه از 1 خیلی بیشتر میشه.)الان تو مثال زیر اومده با این تابع هزینه خط رو به دست آورده. بخاطر اینکه اون داده‌های آبی خیلی دور بودن و تاثیر گذاشتن، خطی که در نهایت کشیده به اون شکل در اومده.اگه دقیق‌تر بخوایم بررسی کنیم باید بیایم یه نمودار تشکیل بدیم برحسب WTX و میزان ضرر تو هر نقطه. حالا نموداری که رسم می‌کنیم داره تابع هزینه رو نشون میده. همونطور که مشخصه مقدار خطا داره به صورت یه سهمی افزایش پیدا می‌کنه و برای داده‌هایی که درست دسته‌بندی شدن پنالتی خیلی زیادی در نظر گرفته میشه.حالا بیایم تابع هزینه رو تغییر بدیم و یه چیز دیگه در نظر بگیریم. مقدار y که خروجی‌مونه یا مقدارش برابر با 1 میشه یا -1. یه تابع علامت تعریف کنیم. اگر داده‌ای درست دسته بندی شده باشه با توجه به اون بهش مقدار بدیم که به صورت زیر تعریف کردیم:حالا با توجه به فرمول بالا اگه یه داده‌ای مثبت باشه و تو دسته مثبت‌ها قرار گرفته باشه مقدار تابع هزینه براش 0 میشه. همینطور اگر یه داده‌ای منفی باشه و تو دسته منفی‌ها بیفته بازم 0 میشه مقدار تابع هزینه. در بدترین حالت چیزی که تابع هزینه برامون حساب میکنه مقدار میشه:4 × تعداد نمونه‌هایی که درست دسته‌بندی نشدنتابع هزینه‌ای که اینجا تعریف کردیم یه مشکلی داره. مشکلش اینکه نمی‌تونیم ازش مشتق بگیریم یا از گرادیان کاهشی براش استفاده کنیم تا بتونیم مقدار مینمم رو توش پیدا کنیم.حالا پس باید چیکار کرد؟ فرض کنید بیایم به جای تابع علامت از تابع سیگموید استفاده کنیم. (تابع سیگموید شبیه همین تابع علامته فقط فرقش اینکه تیز نیست و نرم داره حرکت میکنه و بین 1 و -1 تغییر میکنه)تصویر چپ تابع علامت - تصویر راست تابع سیگمویدمنتها تابع سیگموید هم انتخاب خوبی نیست. به این دلیل که اگر بخوایم از روش گرادیان کاهشی برای حلش استفاده کنیم به مشکل می‌خوریم. چه مشکلی؟ اینکه دچار کمینه‌های محلی میشیم و همین باعث میشه که نتونیم مینیمم اصلی رو پیدا کنیم. پس چیکار کنیم؟ باید بریم سراغ روش‌های دیگه که جلوتر معرفی می‌کنیم.الگوریتم پرسپترونمی‌خواستیم چیکار کنیم تا الان؟ دنبال یه دسته‌بند خطی بودیم. یعنی یه خطی پیدا کنیم که به‌ کمکش بتونیم داده‌های مثبت و منفی رو از هم جدا کنیم. حالا برای تخمین از علامت WTX استفاده می‌کنیم. (اگه مثبت باشه یعنی خروجی 1 میشه اگه منفی باشه یعنی خروجی -1 میشه)حالا می‌خوایم ببینیم که چقدر اشتباه کردیم. چجوری تشخیص بدیم؟ یک تابع هزینه لازم داریم برای این کار که به صورت زیر تعریف شده:تو تصویر زیر جزییات تابع هزینه رو بررسی کردیم:مقدار WTX داره همون فاصله از مرز رو نشون میده و هر چقدر این فاصله بیشتر باشه از مرز و درست هم دسته‌بندی نشده باشه مقدار پنالتی بیشتر میشه و تابع هزینه رو مقدارشو بیشتر میکنه. یعنی فقط درست و غلط دسته‌بندی کردن مهم نیست، مقدار فاصله از مرز هم براش مهمه.الان فرق این با قبلی چیه؟ فرقش تو اینکه قبلی فقط میومد تعداد اونایی که درست دسته‌بندی شده بودن یا نشده بودن رو میشمرد، ولی این میاد فاصله از مرز رو هم لحاظ میکنه. تو شکل زیر هم مشخصه.حالا برای بهینه کردن این تابع هزینه جدید که اینجا تعریف کردیم، می‌تونیم از گرادیان کاهشی استفاده کنیم. هر دور بردار وزن رو آپدیت می‌کنیم و برای اتمامش هم اینو در می‌گیریم که اگر مقدار گرادیان از یه حدی کمتر شد دیگه ادامه نده.الگوریتم پرسپترون رو تو جلسه اول هم دیده بودیم ولی با چیزی که اینجا دیدیم یکمی فرق داشت. برای اینکه به همون روش برسیم باید از گرادیان کاهشی stochastic استفاده کنیم. یعنی به جای اینکه هر دفعه بریم کل نمونه‌های غلط دسته‌بندی شده رو ببینیم فقط یه نمونه رو به صورت رندوم برداریم و بررسی کنیم.عکس پایین مثالی رو نشون میده که در جلسه اول هم بررسی کردیم. وقتی خروجی مثبت باشه، یعنی حاصل (i)X(i)y مثبت شده. حالا یه داده‌ای رو تو خروجی اشتباهی منفی در آورده. یعنی باعث شده که زاویه بین بردار X و w بیشتر از 90 بشه. پس میاد با تغییری که میده باعث میشه این زاویه کمتر از 90 درجه بشه و خروجی درست بشه. (شکل بالا سمت چپ) حالا اگه باید منفی در میاورده و اشتباهی مثبت در آورده هم همینطوره. باید زاویه بیشتر از 90 می‌شده ولی کمتر از 90 شده پس میاد تصحیح میکنه و زاویه رو بیشتر از 90 میکنه. (شکل بالا سمت راست)درسته که داره تو روش گرادیان کاهشی stochastic داده‌هارو یکی یکی تغییر میده و چک می‌کنه ولی در نهایت باعث میشه که به همگرایی برسه. (اگر یک خط وجود داشته باشه که داده‌های مثبت و منفی رو جدا کنه حتما این الگوریتم می‌تونه اونو پیدا کنه)تصویر پایین هم یه مثال از نحوه تغییر خط تو این الگوریتمه. به این صورته که هر دفعه با توجه به فاصله از مرز میاد وزن رو تغییر میده که باعث میشه خط سیاه به خط سبز تغییر کنه.تصویر پایین هم داره اینو نشون میده که چجوری جابجا شده و به بهینه سراسری رسیده.ایراد الگوریتم پرسپترونایراد این الگوریتم اینکه صرفا میاد یک خط رو (اگر خطی وجود داشته باشه برای جدا کردن دو داده) پیدا میکنه. ممکنه بیشتر از یک خط برای جداکردن داده‌های مثبت و منفی پیدا بشه و فقط یکی از اون خط‌ها بهترین حالت ممکن باشه. ولی این الگوریتم دنبال بهترین خط نمی‌گرده و فقط یک خط رو پیدا می‌کنه. بعدا با الگوریتم SVM که سعی می‌کنه این ایراد رو حل کنه آشنا میشیم و خطی رو پیدا می‌کنیم که تعیم‌پذیری بهتری داشته باشه.ایراد دیگه‌ای که این الگوریتم داره، اینکه اگر هیچ خطی وجود نداشته باشه تو یه حلقه بی‌نهایت گیر می‌کنه هیچوقت متوقف نمیشه. روش کار این الگوریتم اینجوری بود که اگر مثلا 100 تا داده داریم، تو هر دور میره هر کدم از داده‌هارو میبینه، اونایی که غلط دسته‌بندی شدن رو تصحیح می‌کنه و هر وقت 100 تا داده رو دید و تموم شد دوباره از اول شروع می‌کنه و انقدر ادامه میده تا بتونه یک خط رو پیدا کنه. حالا اگه خطی نباشه تو یه حلقه بی‌نهایت گیر می‌کنه و هیچوقت بررسی کردنش تموم نمیشه و اگر بخوایم متوقفش کنیم تو یه نقطه رندوم متوقف میشه که نمی‌دونیم آیا خط خوبی رو بهمون داده یا نه. برای حل این مشکل میایم از الگوریتم جدیدی به‌نام pocket استفاده می‌کنیم. این الگوریتم رو در جلسه اول دیدیم. به صورت خلاصه فقط اینجا مرور می‌کنیم.الگوریتم Pocketفرقش با الگوریتم پرسپترون تو اینکه میاد یه خطایی رو هم در نظر می‌گیره. به وسیله این خطا می‌تونه تو بهترین نقطه از حلقه بیاد بیرون نه فقط یک نقطه رندوم و یک خط رو انتخاب کنه که یه جورایی تو بهترین حالت تونسته داده‌هارو از هم جدا کنه. خطایی که حساب میکنه خطای روی داده‌های آموزشه.جمع‌بندی مطالب گفته شدهمسئله رگرسیون رو با دیدگاه احتمالاتی بررسی کردیم.مبحث دسته‌بندی رو شروع کردیم و الگوریتم پرسپترون رو دیدیم.ایرادات الگوریتم پرسپترون رو بررسی کردیم و با الگوریتم pocket آشنا شدیم.اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.اسلایدهای این جلسه (بخش رگرسیون با دیدگاه احتمالاتی)اسلایدهای این جلسه (بخش دسته‌بندی و کلسیفیکیشن)ویدیو این جلسهجزوه جلسه قبلی (جلسه پنجم)جزوه جلسه بعدی (جلسه هفتم)