مهمترین الگوریتم های کاربردی یادگیری ماشین چیست؟ فصل سوم

خلاصه ای از کتاب صد صفحه ای یادگیری ماشین، اثر آندری بورکوف فصل سوم: الگوریتم های اصلیما تو بخش یک و دو کتاب مقدمات رو بررسی کردیم که می تونید از لینک های پایین مطالعه کنید: https://virgool.io/@hamidreza.firooze/%D9%85%D9%87%D9%85%D8%AA%D8%B1%DB%8C%D9%86-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%87%D8%A7%DB%8C-%DA%A9%D8%A7%D8%B1%D8%A8%D8%B1%D8%AF%DB%8C-%DB%8C%D8%A7%D8%AF%DA%AF%DB%8C%D8%B1%DB%8C-%D9%85%D8%A7%D8%B4%DB%8C%D9%86-%DA%86%DB%8C%D8%B3%D8%AA-cxhxyt8lev4n https://virgool.io/@hamidreza.firooze/%D9%85%D9%87%D9%85%D8%AA%D8%B1%DB%8C%D9%86-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%87%D8%A7%DB%8C-%DA%A9%D8%A7%D8%B1%D8%A8%D8%B1%D8%AF%DB%8C-%DB%8C%D8%A7%D8%AF%DA%AF%DB%8C%D8%B1%DB%8C-%D9%85%D8%A7%D8%B4%DB%8C%D9%86-%DA%86%DB%8C%D8%B3%D8%AA-sqzf92yi1dhc تو این فصل ما 5 تا از پرکاربردترین الگوریتم های یادگیری ماشین رو بررسی می کنیم.3-1 رگرسیون خطیاحتمالا همه ما در مورد رگرسیون خطی تو درسهای آمار خودمون خونده باشیم. هدف اصلی رگرسیون خطی تخمین یک خط برای محاسبه خروجی بر اساس ورودی هاست. هدف ما به دست آوردن این تخمین از فرمول زیره:که تو این فرمول w یک بردار با بعد D و b هم یک عدد حقیقی است. نماد w,b برای تابع f نشون میده که این تابع دو پارامتر برای تخمین داره. هدف ما پیدا کردن مقدار بهینه برای w و b به طوری که دقیق ترین پیش بینی رو به ما بده. مدل SVM که تو فصل یک بررسیش کردیم خیلی شبیه این مدل بود و تنها تفاوتش نقش مرز تصمیم گیری در SVM است.3-1-2 راه حلبه منظور به دست آوردن مقدار بهینه برای w و b تابع زیر رو باید مینیمم کنیم.به این تابع حداقل مربعات گفته میشه و هدفش حداقل کردن مربع فاصله واقعی هر نقطه از مقدار پش بینی شده است. تمامی مدل هایی که ما بررسی می کنیم یه همچین تابعی برای حداقل کردن دارند که به اون تابع هزینه یا Cost Function می گند. حالا چرا ما از تابع مربع فاصله در رگرسیون خطی استفاده می کنیم و نه از قدر مطلق فاصله. در واقع ما می تونیم از هر تابعی استفاده کنیم و این بستگی به نظر ما و ماهیت مساله داره. در مورد رگرسیون خطی یکی از دلایلی که از تابع مربعات فاصله استفاده میشه اینه که تخمین زننده هایی w و b که از این روش استفاده میشند نا اریبند و کارایی بیشتری دارند. برای اینکه تخمینی از w و b داشته باشیم باید از تابع هزینه نسبت به این دوتا مشتق بگیریم و برابر صفر قرار بدیم. بعدش از طریق حل دو معادله دومجهول مقدارشون محاسبه میشه و در نهایت امید ریاضیشون رو محاسبه می کنیم که برابر با w و b خواهند شد.تصمیم برای نوع مدل و نوع تابع هزینه ما رو به مدل های متفاوتی می رسونه و درواقع به خاطر دلایل زیره که همیشه الگوریتم های جدید تر ابداع میشند:1- الگوریتم جدید بهتر از الگوریتم های موجود مسئله عملی خاصی رو حل می کنه.2- الگوریتم جدید تضمین های بهتری در مورد کیفیت مدلی که تولید می کنه، داره.دلایلی که مدل های خطی رگرسیون خیلی استفاده میشه سادگی اونها و احتمال کم Overfitting است. مدل های که بیش از اندازه پیچیده هستند ممکنه داده های آموزشی مارو به طور دقیق پیش بینی کنند ولی در داده های تست نتایج خیلی ضعیفی به ما بدند.3-2 رگرسیون لجستیکقبل از شروع صحبت در این مورد باید بدونید که رگرسیون لجستیک یک رگرسیون نیست بلکه یه روش طبقه بندیه یا همون کلاسیفیکیشنه. این اسم گذاری به خاطر شباهت فرومول بندی آماری اون با رگرسیونه.3-2-1 تعریف مسالهدر این مساله هدف ما تخمین y بر اساس ترکیب خطی از xهاست با این تفاوت که y حالت صفر و یک داره. با توجه به اینکه ترکیب خطی wx+b میتونه مقداری بین مثبت بی نهایت تا منفی بی نهایت بگیره، باید تابعی پیدا بشه که بتونه این تبدیل باینری رو انجام بده. این تبدیل هم به این صورته که هر چه خروجی به 1 نزدیکتر باشه این داده جزء کلاس یک خواهد بود و برعکس. بنابراین باید تابعی وجود داشته باشه که بردش بین 0 و 1 باشه.تابع سیگمویید این ویژگی رو داره. با بهینه سازی مقدار w و b در تابع بالا ما می تونیم خروجی تابع رو به عنوان احتمال عضویت یک داده به کلاس یک یا صفر تفسیر کنیم. به طور مثال اگر مقدار تابع بالا بیشتر از 0.5 بود عضو کلاس یک و اگر کمتر بود عضو کلاس صفر خواهد بود.3-2-1 راه حلبرای محاسبه مقدار بهینه برای w و b، ماباید برازندگی مدل را حداکثر کنیم. برازندگی در واقع میزان شباهت خروجی مدل را با مشاهدات ما نشون میده. به همین منظور تابع حداکثر برازندگی رو به صورت زیر در نظر می گیریم.قیافه تابع بالا خیلی ترسناکه ولی درواقع اونقدرها هم ترسناک نیست. همیشه یک ترم از فرمول بالا برابر صفر خواهد بود. پیشنهاد می کنم خودتون این موضوع رو بررسی کنید.به منظور ساده سازی فرایند بهینه سازی از دوطرف log می گیریم و خروجی به صورت زیر خواهد بود.از اونجا که ln یک تابع کاملاً افزایشیه، به حداکثر رسوندن این تابع در واقع حداکثر رساندن عبارت های اون خواهد بود، و راه حل این مسئله جدید بهینه سازی همون مساله اصلیه.بر خلاف رگرسیون خطی ، هیچ راه حل مشخصی برای مسئله بهینه سازی بالا وجود نداره. یک روش بهینه سازی عددی معمول که در چنین مواردی استفاده میشه، روش گرادینت دیسنته(Gradient Descent) که در موردش تو فصل بعدی صحبت خواهیم کرد.3-3 درخت تصمیم گیریدرخت تصمیم گیری یک گرافه که به ما کمک می کنه در مورد یک بردار ورودی از داده ها تصمیم گیری کنیم. در هر شاخه یکی از ویژگی های بردار ویژگی ها بررسی میشه و در صورتی که کمتر از مقدار مشخصی باشه به شاخه سمت چپ و در غیر اینصورت به شاخه سمت راست حرکت می کنیم و این کار آنقدر ادامه پیدا می کنه تا به برگ ها برسیم و تصمیم لازم در مورد اینکه داده مورد نظر در کدام کلاس قرار داره رو بگیریم.3-3-1 تعریف مسالههدف ما ساخت درخت تصمیم گیری ای هستش که بتونه برچسب داده ها رو که 0 یا 1 هست پیش بینی کنه3-3-2 راه حلفرمول بندی های مختلفی برای درخت تصمیم گیری وجود داره که کتاب بر روی الگوریتم ID3 تمرکز داره. مثل رگرسیون لجستیک تابع هزینه رو به صورت حداکثر برازندگی تعریف می کنیم.که در اون fID3 پیش بینی درخت تصمیم گیری ID3 از برچسب داده های ورودی خواهد بود. بر خلاف الگوریتم رگرسیون لجستیک، الگوریتم ID3 از طریق ساخت یک مدل غیر پارامتریک تقریبا بهینه(Approximately Optimum) می کنیم. به این صورت که ما در هر مرحله داده ها را بر اساس فیچر j و حد t تقسیم می کنیم. در هر تقسیم باید تخمین بزنیم که چقدر این تقسیم خوبه. خوب بودن هر تقسیم از طریق معیاری به اسم آنتروپی اندازه گیری میشه. در هر مرحله ما دنبال پیدا کردن تقسیمی هستیم که آنتروپی رو حداقل کنه. برای اینکه درمورد آنتروپی بیشتر بدونید پیشنهاد می کنم به کتاب مراجعه کنید.به خاطر اینکه الگوریتم ID3 در هر مرحله تقسیم داده ها رو به صورت محلی انجام میده(به تقسیم ها بعدی وابسته نیست)، تضمینی وجود ندارد که جواب بهینه رو به ما بده.یکی از الگوریتم هایی که بیشترین کاربرد رو داره، الگوریتم C4.5 است. این الگوریتم مزایایی نسبت به ID3 داره که شامل موارد زیره:هم با فیچر های پیوسته و هم گسسته کار می کنه.مثالهای ناقص رو به قبول می کنه. با استفاده از تکنیکی از پایین به بالا به نام "هرس(Pruning)" مشکل Overfitting رو حل می کنه.هرس کردن به معنی اینه که بعد از اینکه مدل یک بار ایجاد شد، دوباره بر می گردیم و شاخه هایی که حذف کردنشون تاثیر زیادی روی افزایش خطای مدل نمی زاره، با برگ جایگزین می کنیم.3-4 مدل یادگیری Support Vector Machineما تو فصل اول در مورد SVM صحبت کردیم ولی دوتا سوال وجود داره که باید بهش جواب بدیم:1- اگر داده های ما دارای نویز بودن چکار کنیم؟2- اگر با یه صفحه خطی نتونیم داده ها رو از هم جداکنیم و یه صفحه غیر خطی لازم داشتیم چکار باید بکنیم؟شکل زیر شرایطی رو برای حالت های بالا نشون میده.شکل سمت چپ وجود نویز و شکل سمت راست صفحه غیر خطی رو نشون میدههدف ما ساختن مدلی بود که معادله زیر رو ارضا کنه. برای بهینه سازی مساله باید ||w|| رو حداقل کنیم و این یعنی مقدار2^||w|| رو حداقل کنیم. استفاده از مربع این عبارت بعدا امکان بهینه سازی مربعات رو برای ما فراهم می کنه. پس در نهایت باید عبارت زیر بهینه بشه:3-4-1 وجود نویز در داده هازمانی که داده ها به صورت خطی جداپذیر نباشند، از تابع هزینه hinge استفاده می کنیم. در این تابع در صورتی که تخمین ما از سمت قرار گیری یک نقطه نسبت به مرز تصمیم گیری درست باشه، اندازه تابع برابر با صفر خواهد بود و در غیر اینصورت مقدار اون متناسب با فاصله از مرز تصمیم خواهد بود.هایپر پارامتر C ترید اف بین افزایش اندازه مرز تصمیم و اطمینان از اینکه یک x در جهت درست مرز تصمیم بیفاته است. هر چه مقدار C بیشتر بشه ترم دوم فرمول بالا نادیده گرفته میشه و SVM سعی می کنه کوچکترین حاشیه رو حساب کنه و به طور کلی تخیمن نادرست رو نادیده بگیره. برعکس اگه C رو کاهش بدیم، کلاس بندی اشتباه پر هزینه خواهد بود و SVM سعی می کنه کمترین خطا رو داشته باشه و اندازه حاشیه رو قربانی این مساله کنه. همونطور که قبلا گفتیم حاشیه بیشتر برای تعمیم مدل بهتر بود. بنابراین C رابطه بین قابلیت تعمیم مدل (Generalization) و طبقه بندی خوب داده های آموزشی (به حداقل رساندن خطر تجربی) تنظیم می کند.3-4-2 مساله غیر خطی بودن ذاتیدر حالتی که داده به صورت ذاتی با یک صفحه جدا نشند، ما می تونیم داده ها رو به یک بعد بالاتر ببریم و اونجا داده ها رو به صورت خطی جدا کنیم. در SVM استفاده از یک تابع برای بردن فضا به یک بعد بالاتر در حین بهینه سازی تابع هزینه رو روش کرنل(kernel trick) می گند. بردن داده ها به یک بعد بالا تر از طریق کرنلشکل بالا نشون دهنده نحوه استفاده از کرنل برای مساله شکل قبل سمت راست است.توابع کرنل متفاوتی وجود دارند ولی یکی از پرکاربردترینشون تابع کرنل RBF است. با تغییر دادن هایپر پارامتر سیگما ، تحلیلگر داده می تونه بین به دست آوردن یک مرز تصمیم صاف یا منحنی در فضای اصلی انتخاب کنه.3-5 الگوریتم K-نزدیک ترین همسایه(K-nearest neighbors)الگوریتم KNN بر خلاف باقی الگوریتم هایی که تا کنون درموردشون بحث کردیم، یک الگوریتم غیرپارامتریکه و از همه داده ها برای ساخت مدل استفاده می کنه و داده های آزمایشی رو در حافظه خودش نگه می داره. با رسیدن هر داده جدید، الگوریتم k همسایه نزدیک این داده را پیدا می کنه و بیشترین برچسب مشاهده شده در این داده ها رو به عنوان برچسب داده جدید به خروجی منتقل می کنه.نزدیک بودن نقطه ها بر اساس فاصله آنها سنجیده میشه مثل فاصله اقلیدسی. یکی دیگه از توابع محبوبی که در این زمینه استفاده میشه تابع شباهت کوسینوس(cosine similarity) است.این تابع شباهت بین دو بردار غیر صفر رو اندازه گیری می کنه. اگه دو بردار در یک جهت باشند،زاویه بین دوبردار صفر خواهد بود، مقدار تابع 1 خواهد بود و اگر دوبردار بر هم عمود باشند مقدار تابع برابر صفر خواهد بود. اگر دوبردار در جهت مخالف هم باشند، اونوقت مقدار تابع برابر -1 خواهد بود. در این حالت اگر بخواهیم از تابع شباهت به جای تابع فاصله استفاده کنیم باید مقدار آن را در -1 ضرب کنیم. چند تا تابع فاصله دیگر تابع Chebychev و Mahalanobis و Hamming هستند. انتخاب تابع فاصله و k جز هایپرپارامترهای مساله هستند و توسط تحلیلگر انتخاب میشند. تا اینجا ما سه فصل از کتاب رو بررسی کردیم. تو فصل چهارم در مورد آناتومی یه الگوریتم یادگیری صحبت خواهیم کرد که می تونید از لینک زیر مطالعش کنید. https://virgool.io/@hamidreza.firooze/%D9%85%D9%87%D9%85%D8%AA%D8%B1%DB%8C%D9%86-%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85-%D9%87%D8%A7%DB%8C-%DA%A9%D8%A7%D8%B1%D8%A8%D8%B1%D8%AF%DB%8C-%DB%8C%D8%A7%D8%AF%DA%AF%DB%8C%D8%B1%DB%8C-%D9%85%D8%A7%D8%B4%DB%8C%D9%86-%DA%86%DB%8C%D8%B3%D8%AA%D9%81%D8%B5%D9%84-%DA%86%D9%87%D8%A7%D8%B1%D9%85-xatvzk4gm0iv