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

سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.

مباحث ریاضی و آماری این جلسه یکمی زیاده و اگه فکر کردین که خیلی خوب متوجه مطالب نشدید ایرادی نداره، مفاهیمش رو هم بتونید درک کنید، خیلی عالیه.

محتوای این جلسه

• دسته‌بندهای احتمالاتی

دسته‌بندهای احتمالاتی

می‌خوایم ببینیم حل مسئله کلسیفیکیشن به روش احتمالاتی یعنی چی. باید اول بریم سراغ یه سری تعریف اولیه.

• عبارت p(y=c1) درصد نمونه‌های متعلق به دسته اول رو نشون میده.

• عبارت p(x) توزیع داده‌هارو مستقل از کلاسی دارن که بهمون نشون میده. یعنی انگار برچسب داده‌هارو بریزیم دور، بعد همه داده‌هارو بریزیم رو هم و توزیعشو پیدا کنیم.
• عبارت p(x|c1) توزیع داده‌های دسته اول رو بهمون نشون میده.
• عبارت p(c1|x) داره میگه اگه داده x رو داشته باشیم، احتمال اینکه از کلاس c1 اومده باشه چقدره. اگه بخوایم مقدارش رو حساب کنیم از قانون بیز استفاده می‌کنیم.

یه سری تعریف دیگه هم داریم که از قبل باهاشون آشنا شدیم و تو تصویر زیر اومده:

مفهوم Bayes Rule

داره میگه اگه ما توزیع داده‌هارو داشته باشیم کلسیفایر بهینه چیزیه که به صورت زیر عمل می‌کنه:

اگر نمونه x اومده باشه، به مقادیر posterior هر کلاس نگاه می‌کنه، هرکدوم بیشتر باشه همون کلاس رو انتخاب می‌کنه.

برای اثبات این قانون اومده اول مفهومی با عنوان احتمال خطا تعریف کرده. به این صورت که میگه اگه در نظر بگیریم که نمونه x از کلاس c1 میاد به اندازه p(c2|x) دچار خطا شدیم و برعکس.

حالا تو هر نقطه چه تصمیمی بگیریم تا خطای کمتری مرتکب شده باشیم؟ اون کلاسی که به ازاش مقدار posterior بیشتره رو تو اون نقطه بعنوان تصمیم در نظر می‌گیریم که باعث بشه که اون کلاسی که مقدارش کمتره بعنوان احتمال خطا در نظر گرفته بشه.

حالا فرض کنید یه کلسیفایر داریم که به شرح زیره:

• خروجی = alpha(x) -> تو هر نقطه x یکی از مقادیر 1 تا k رو بعنوان خروجی بهمون میده (برای سادگی مقدار k اینجا 2 در نظر گرفته شده)
• ناحیه = Rk -> مقادیری از x که به ازای اون خروجی شده k (ناحیه‌ای که کلسیفایر به کلاس k ام انتساب میده)
• خطا = p(error) -> چقدر احتمال داره چیزی که ما به‌دست میاریم با چیزی که در مقدار واقعی هست تفاوت داشته باشه (یا داده واقعی متعلق به کلاس دوم بوده ما اشتباهی به کلاس 1 انتساب دادیم، یا هم برعکس)

ناحیه R1 و R2 رو به چه صورت باید مشخص کنیم تا خطا کمینه بشه؟ به عبارتی دیگه، ما از کل فضایی که داریم یه قسمت رو گذاشتیم R1 بقیه رو گذاشتیم R2، حالا نحوه تقسیم‌بندی باید چجوری باشه تا جمع انتگرال‌های بالا برابر با حداقل مقدار خودش بشه؟ به همون شیوه‌ای که بالاتر با یه بیان دیگه گفتیم.

خب پس تا اینجا اینکه چجوری تصمیم بگیریم و خطا رو مشخص کنیم تعیین شده. تنها چالشی که داریم همون تخمین مقدار posterior هست.

قبل از اینکه یه مثال بزنیم یک سری مفاهیم رو تو تصویر زیر ببینیم:

حالا بریم یه مثال ببینیم:

فرض کنید توزیع داده‌ها در کلاس اول و دوم رو داشته باشیم. یک سری اطلاعات هم از اول داریم که ربطی به نمونه‌ها نداره. از قبل می‌دونیم. مثلا فرض کنید می‌خواید تشخیص بدیم آدمایی که وارد دانشگاه میشن چه تعداد خانم هستن، چه تعداد آقا. قبل اینکه نمونه‌ای بیاد، می‌دونیم از قبل مثلا نسبت مردها به زن‌ها تو اون دانشگاه 2 به 1 عه مثلا.

حالا با استفاده از قانون بیز که تو اسلاید قبلی دیدیم میاد مقدار posterior رو حساب میکنه. حالا posterior رو حساب کردیم، چجوری مرزهای تصمیم رو مشخص کنیم؟ هرجا مقدار قرمز بیشتره بشه برای ناحیه کلاس قرمز، هرجا مقدار مشکی بیشتره بشه برای ناحیه کلاس مشکی.

برای ساده‌تر کردن محاسبات، می‌تونیم مقدار p(x) رو محاسبه کنیم اصلا و مقایسه زیر رو انجام بدیم:

حالا ببینیم با این روش دوم چجوری مقایسه رو می‌تونیم انجام بدیم. کافیه p(x|c1) رو دو برابر کنیم بعد مقدارش رو با p(x|c2) بسنجیم. (مقدار prior هم دخیل شده) می‌بینیم که جواب مثل قبل میشه. چرا نیومدیم مستقیم p(x|c1) رو با مقدار p(x|c2) مقایسه کنیم؟ چون حجم نمونه‌ها توش دخیل نیست پس نمونه مقایسه خوبی باشه، پس مقدار prior رو هم باید تو مقایسه بیاریم.

حالا بریم یه مثال دیگه ببینیم.

از روی تعداد گلبول‌های سفید افراد می‌خوان تشخیص بدن آیا اون فرد دیابت داره یا نداره. نمودار زیر داره یک سری نمونه از اونایی که دیابت داشتن (قرمز) و اونایی که دیابت نداشتن (رنگ سبز) نشون میده. در واقع یه جورایی همون مقدار likelihood هست. (توزیع نمونه‌ها داخل دو کلاس). حالا اگه از قبل بدونیم که مثلا از هر 10 نفر 2 نفر دیابت دارن بهش prior میگیم. حالا می‌خوایم به کمک likelihood و prior تصمیم‌گیری انجام بدیم.

حالا یه فردی اومده که هنوز آزمایش نداده و هیچی در موردش نمی‌دونیم. فقط با توجه به prior می‌تونیم بگیم که احتمال اینکه دیابت داشته باشه 0.2 هست. حالا می‌خوایم مقدار posterior که میشه بعد آزمایش رو تخمین بزنیم.

ما تو این مسئله توزیع نداریم. صرفا یه سری نمونه داریم از هر دو کلاس. چه کنیم؟ با استفاده از روش‌های تخمین که در جلسه دوم دیدیم می‌تونیم مقدار توزیع رو تخمین بزنیم.

حالا فرض کنید از توزیع گاوسی استفاده کنیم. نمونه‌های کلاس افرادی که دیابت دارن و افرادی که سالم هستن رو هر کدوم با یه گاوسی جدا مشخص می‌کنیم.

حالا پارامتراشو چجوری در بیاریم؟ قبلا مثال‌هاشو دیدیم تو جلسه دوم. از طریق همون روش‌ها مثلا maximum likelihood می‌تونیم پارامترهارو در بیاریم.

برای هر کلاس جدا جدا میایم مقدار پارامترهارو حساب می‌کنیم.

خب تا اینجا مقدار prior رو داریم. مقادیر p(x|c1) و p(x|c2) رو هم حساب کردیم. برای مشخص کردن تصمیم‌گیری دیگه فقط کافیه که برای هر کلاس این مقادیر رو در هم ضرب کنیم و جواب به دست میاد.

یه مشکلی اینجا داریم، اونم اینکه این دو تا توزیع خیلی تو هم رفتن (با هم هم‌پوشانی زیادی دارن). این باعث میشه که نقاط مبهم زیاد باشه در نتیجه خطا خیلی زیاد شه. چجوری حل کنیم این مشکلو؟ فیچر اضافه کنیم. فیچر دومی که اضافه کردیم مقدار گلوکز در خون بوده.

حالا که این فیچر رو اضافه کردیم داده‌ها بهتر از هم جدا شدن. ولی بازم یه مشکلی هست. چجوری توی فضای دو بعدی بیایم توزیع رو تخمین بزنیم؟ باید توزیع گاوسی چند بعدی بلد باشیم. (جزییات مرتبط با توزیع گاوسی چند بعدی از دقیقه 28 تا 37 از ویدیو این جلسه قابل مشاهده است و در اینجا آورده نشده است)

حالا می‌خوایم برای هر کلاس یک گاوسی چند متغیره مدل کنیم و بعد بریم سراغ استفاده از قانون بیز و تصمیم‌گیری.

حالا باید پارامترهای این گاوسی رو به دست بیاریم. دو تا پارمتر داریم که به صورت زیر تعریف میشن:

مقدار پارامترهارو برای هر کدوم از کلاس‌ها حساب می‌کنیم:

حالا اول جزییات مرزی که این دو تا کلاس رو از هم جدا میکنه ببینیم که به چه صورته. اصلا مرز دو کلاس کجاست؟ جاییه که مقدار posterior دو کلاس باهم برابر میشه. می‌تونیم از دو طرف ln بگیریم تا محاسبات راحت‌تر بشه. با استفاده از قوانین لگاریتم اومده ضرب رو به جمع تبدیل کرده. در نهایت اون بخشی رو که داخلش x ظاهر شده آورده باز کرده. حالا شکلی که مرز رو نشون میده اون جملاتی هست که توش x ظاهر شده. چون دو تا جمله که حاوی x هستن دارن در هم ضرب میشن، پس فرمی که x به خودش می‌گیره مرتبه 2 هست. پس یعنی انگار مرزی که داره دو کلاس رو هم جدا می‌کنه از نوع درجه دو است.

اگر ماتریس کواریانس هر دو کلاس رو یکی در نظر بگیریم مرز جدا کننده خطی میشه و دیگه درجه دو نیست.

تو شکل زیر سعی کرده همه چیزایی که گفتیم تا اینجا رو نشون بده. یه جورایی شکلی که به دست اومده شبیه تابع سیگمویده.

حالا بریم حالتی از مسئله رو حل کنیم که مرز دو کلاس به صورت خطی در میاد و ماتریس کواریانس هر دو کلاس باهم برابره.

این حالت یکمی پیچیده‌تر از حالت قبلیه. تو حالت قبلی وقتی می‌خواستیم با maximum likelihood تخمین بزنیم، داده‌های تو کلاس کاملا قابل جدا شدن بودن چون اصلا پارامتر مشترکی نداشتیم. ولی اینجا فرق داره. یه کواریانس مشترک داریم که باعث میشه نتونیم داده‌ها رو مثل قبل از هم جدا کنیم.

حالا باید از likelihood × prior مشتق بگیریم و برابر با صفر قرار بدیم. حالا میانگین و prior جوابش مثل قبل شد. ولی ماتریس کواریانس جوابش فرق داره یکمی و داره از نمونه‌های هر دو کلاس تاثیر می‌پذیره.

حالا تو شکل زیر وقتی مرز خطی شده رسمش کردیم:

تا اینجا مثال‌ها و مواردی که بررسی کردیم برای مسئله دو کلاسه بوده. حالا می‌خوایم مسئله رو تو حالت کلی چند کلاسه بررسی کنیم ببینیم جوابمون به چه صورت در میاد.

فرض کنید مثلا سه تا کلاس مختلف داریم. کلاس قرمز رنگ رو انتخاب کردیم و می‌خوایم در مورد اون تصمیم بگیریم (خط مشکی). حالا خطایی که تو اون قسمت داریم برابر میشه با کل کلاس قرمز منهای بخشی که کلاس سبز اومده و منهای بخشی که از کلاس آبی اومده. به عبارت دیگه فقط داریم در مورد کلاس قرمز تصمیم درست می‌گیریم و برای بقیه کلاس‌ها تصمیم غلط گرفته میشه.

چیزی که بالا گفتیم پایین به صورت ریاضی نشون داده شده. میگه اگر از کل 1 اون قسمتی رو که می‌خوایم در موردش تصمیم‌گیری کنیم کم کنیم میزان خطا رو می‌تونیم به دست بیاریم.

حالا تو این مورد ما می‌خوایم خطارو حداقل کنیم. یعنی انگار 1 منهای جمع بقیه رو داریم حداقل می‌کنیم. به عبارتی دیگه انگار کلاس مد نظرمون رو باید حداکثر کنیم. پس یعنی مثل همون مسئله دو کلاسه شد. جایی که posterior حداکثر باشه رو قانون تصمیم‌گیری‌مون در نظر می‌گیریم.

حالا اینجا می‌خوایم یه تابع loss ای رو تعریف کنیم که با تعریف قبلی تفاوت داشت. تو قبلی (یعنی مسئله دو کلاسه) برای اندازه‌گیری خطا چی می‌گفتیم؟ می‌گفتیم که اگه داده‌ای رو درست تشخیص دادیم مقدار loss براش 0 در نظر گرفته میشه و اگر اشتباه تشخیص دادیم یه پنالتی به اندازه 1 براش لحاظ می‌کنیم. ولی اینجا چیزی که تعریف می‌کنیم متفاوته با اون.

برای درک بهتر با یه مثال بررسی می‌کنیم. فرض کنید می‌خوایم یه آزمایشی طراحی کنیم که به واسطه اون سرطان رو تو افراد تشخیص بدیم. اگه کسی سرطان نداشته باشه و درست تشخیص بدیم یا کسی سرطان داشته باشه و بازم درست تشخیص بدیم پس یعنی هیچ خطایی نداشتیم و مقدار loss رو براش 0 در نظر می‌گیریم. ولی دو تا حالت دیگه هم داریم. وقتی که فرد سرطان نداره ولی ما به اشتباه تشخیص سرطان داریم و وقتی که فرد سرطان داره و ما به غلط گفتیم سالمه. تو حالت اول مقدار loss رو 1 در نظر گرفتیم. چون اونقدر خطای فاحشی نبوده. مثلا فرد یه آزمایش دوم هم میده و مشخص میشه که سالمه و سرطان نداره. اما تو حالت دوم مقدار loss رو برابر با 100 در نظر گرفتیم. چون می‌خوایم آزمایش افرادی که سرطان دارن رو بهتر مشخص کنه. پس پنالتی‌ای که بهش اختصاص می‌دیم خیلی بیشتر میشه.

پس یه ماتریس Loss در نظر می‌گیریم به صورت کلی که با حرف L نشونش می‌دیم و اگر k تا کلاس داشته باشیم اندازه‌ش میشه k × k.

درایه ij این ماتریس = هزینه انتساب برچسب i به نمونه، در حالیکه برچسب درست j بوده

اگه ماتریس L جوری باشه که همه درایه‌های قطرش 0 باشه و بقیه درایه‌هاش 1 باشه دقیقا میشه معادل با همون چیزی که تو مسئله‌های قبلی داشتیم. یعنی کمینه کردن خطا برابر میشه با حداکثر کردن posteriorها.

در صورتی که مقدار درایه‌ها مقادیر مختلف باشه جواب به این شکل در نمیاد.

خب تا اینجا اومدیم حالت دوکلاسه رو به سادگی تعمیم دادیم به حالت چند کلاسه. از قبل یه چیزی داشتیم برای مشخص کردن کلاس‌ها. اینجوری بود که میومدیم برای هر کلاس یه تابع در نظر می‌گرفتیم، هر جا مقدار اون تابع بیشتر میشد می‌گفتیم ناحیه مختص همون کلاسه (تو جلسه قبلی در موردش بیشتر توضیح دادیم). معادل همون حرف اینجا میشه در نظر گرفتن posterior برای هر کلاس و بیشینه کردنش یا در نظر گفتن ریسک (معادل همون ماتریس L) و حداقل کردنش.

دسته‌بند Naive Bayes

تا اینجا برای تصمیم‌گیری یه قانون ساده در نظر گرفتیم. از طرفی بلدیم که چجوری تخمین بزنیم و توزیع داده‌های هر دسته رو تخمین می‌زنیم و از قانون بیز هم برای راحت‌تر انجام دادن دسته‌بندی استفاده می‌کنیم. ولی مشکلاتی وجود داره:

• اولا، از کجا معلوم که داده‌های موجود در یک کلاس حتما توزیع گاوسی دارن؟ (چون ما همچین فرضی کرده بودیم)
• دوما، محاسبه prior ممکنه دشوار باشه برامون تو یه سری مسائل و ممکنه کلا نداشته باشیمش.
• سوما، اگر تعداد داده‌ها کم باشه تعداد پارامترهایی که تخمین می‌زنیم چه بلایی سرشون میاد؟

فرض کنید d تا پارامتر برای کلاس اول، d تا پارامتر برای کلاس دوم و 2/(d(d+1)) پارامتر برای ماتریس کواریانس در نظر بگیریم. اگه تعداد پارامترها زیاد باشه فضای زیادی برای حل مسئله نیاز خواهیم داشت. یک راه حل برای اینکه پیچیدگی این مسئله رو کم کنیم اینکه یک فرض ساده کننده در نظر بگیریم. فرضمون می‌تونه این باشه که اینو در نظر بگیریم که در کلاس k ام همه ابعاد ویژگی از هم مستقل باشن. لزوما فرض درستی نیست ولی خیلی جاها مرزی که بهمون میده تا حد خوبی همونیه که دنبالشیم.

این فرض مستقل در نظر گرفتن مثل این می‌مونه که تو مثال گاوسی ماتریس کواریانس رو قطری در نظر بگیریم.

قانون کلیش به شکل زیر در میاد:

حالا می‌خوایم ببینیم تعداد پارامترهای یک گاوسی با این کلسیفایر چجوری میشه. فرض کنید مسئله‌مون دو کلاس‌ست از طرفی x ای که داریم d بعدیه.

با این روش تعداد پارامترهامون به ازای هر کلاس میشه d+d (یکی برای میانگین یکی برای واریانس) تعداد پارامترهامون در مقایسه با روش قبلی خیلی کمتر شد.

حالا در ادامه بریم یه مثال از فضای گسسته ببینیم.

فرض کنید دو ویژگی سیگار کشیدن و دیابت داریم. هدف هم داشتن یا نداشتن بیماری قلبیه. حالا می‌خوایم از دسته‌بند Naive Bayes استفاده کنیم و دسته‌بندی رو انجام بدیم. چه پارامترهایی رو لازمه که تخمین بزنیم؟

می‌دونیم که توزیع داده‌ها به صورت برنولی هست. یکی از پارامترهایی که باید تخمین بزنیم prior هست که اینجا میشه درصد داده‌هایی که بیماری قلبی دارن. یعنی باید نمونه‌هارو بشمریم ببینیم چندتاشون برچسبشون مثبت شده.

p(x | H=yes) = p(D | H=yes) p(S | H=yes)

اگر ویژگی‌هامون باینری باشن و فرض Naive Bayes رو نداشته باشیم و تعداد d تا ویژگی هم داشته باشیم، چند تا پارامتر باید تخمین بزنیم؟ 2 به توان d تا به ازای هر کلاس و یک پارامتر به ازای prior. چرا؟ چون به ازای هر ویژگی دو تا حالت داریم (مقدار ویژگی‌مون باینری بود)

حالا اگه فرض Naive Bayes رو داشته باشیم چی؟ تو هر کلاس d پارامتر رو باید حساب کنیم و یک پارامتر به ازای prior. تعداد پارامترها با این روش خیلی کمتر شدن.

جمع‌بندی مطالب گفته شده

با استفاده از قانون بیز اومدیم مقدار posterior رو تو حالت‌های مختلف بررسی کردیم. در جلسه بعدی به صورت مستقیم و بدون استفاده از قانون بیز این مقدار رو می‌خوایم تخمین بزنیم.

اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.

اسلایدهای این جلسه

ویدیو این جلسه

جزوه جلسه قبلی (جلسه هفتم)

جزوه جلسه بعدی (جلسه نهم)