بخشی از پاورپوینت
اسلاید 1 :
طبقهبندهای خطی
Linear Classifiers
اسلاید 2 :
رئوس مطالب
1- توابع تمایز خطی و ابرصفحههای تصمیم
2- الگوریتم پرسپترون
3- روشهای حداقل مربعات
4- تخمین میانگین مربع
5- تمایز لجستیک
6- ماشینهای بردار پشتیبان
اسلاید 3 :
3-1- مقدمه
مزیت اصلی طبقهبندهای خطی در سادگی و جذابیت محاسباتی
فرضیه طبقهبندی تمام بردارهای ویژگی از کلاسهای موجود با طبقهبند خطی
3-2- توابع تمایز خطی و ابرصفحههای تصمیم
برای مسئله دو کلاسه و تابع تمایز خطی، ابرصفحه تصمیم در فضای ویژگی l بعدی
در رابطه بالا، بردار وزن و نیز مقدار آستانه میباشد
اگر x1 و x2 دو نقطه روی ابرصفحه تصمیم باشند، آنگاه داریم
باتوجه به برقراری رابطه بالا بازای هر دو نقطه از صفحه تصمیم، لذا بردار وزن بر ابرصفحه عمود میباشد
اسلاید 4 :
برای و شکل زیر داریم
اسلاید 5 :
3-3- الگوریتم پرسپترون
هدف محاسبه پارامترهای نامعین جهت تعریف ابرصفحه تصمیم میباشد
جهت سادگی، مسئله دو کلاسه با جداییپذیری خطی را درنظر بگیرید. یک ابرصفحه با معادله وجود دارد بطوریکه
معادله بالا حالت کلیتری از رابطه قبلی است، اگر در فضای l+1 بعدی بنویسیم
جهت حل معادله با یک مسئله بهینهسازی مواجه هستیم. بنابراین، یک تابع هزینه، تابع هزینه پرسپترون، بصورت زیر انتخاب میکنیم
در رابطهبالا، Y زیرمجموعهای از بردارهای آموزش است که بطور اشتباه طبقهبندی شده و
اسلاید 6 :
تابع هزینه تعریفی همواره بزرگتر یا مساوی صفر خواهدبود. این تابع زمانی کمینه میشود که تمام نمونهها بدرستی تفکیکشده و لذا، تابع هزینه صفر شود.
با استفاده از روش گرادیان نزولی (Gradient descent) برای بردار وزن داریم
در رابطه بالا، ρt رشتهای از اعداد حقیقی مثبت بوده و t نیز اندیس مراحل تکرار میباشد.
در نقاط پیوسته تابع هزینه، مشتق نسبت به بردار وزن موجود بوده و داریم
با جایگزینی در رابطه گرادیان نزولی، رابطه بازگشتی زیر حاصل میشود
معادله بالا در تمام نقاط تعریف شده است و به الگوریتم پرسپترون معروف میباشد.
با مقداردهی اولیه بردار وزن و تشکیل بردار تصحیح از روی ویژگیهای اشتباه طبقهبندی شده، الگوریتم تا طبقهبندی صحیح تمام ویژگیها ادامه مییابد.
اسلاید 7 :
یک شبه کد برای اینکار بصورت زیر میباشد
نقش ρt در همگرایی الگوریتم با تعداد محدودی از گام تکرار میباشد.
عدم یکتایی راهحل بدلیل وجود بیشاز یک ابرصفحه خطی برای دو کلاس جداییپذیر خطی
اسلاید 8 :
مثال: شکل زیر خطچین را با بردار وزن نشان میدهد. این خط در آخرین گام از الگوریتم با ρt= ρ= 0.7 محاسبه شدهاست و تمام نقاط باستثنای دو نقطه را بدرستی طبقهبندی میکند.
اسلاید 9 :
مطابق الگوریتم، در گام بعدی بروز کردن بردار وزن داریم
خط جدید تصمیم، خط پر، معادله داشته و تمامی دادهها را بطور درست طبقهبندی میکند.
شکلهای دیگر الگوریتم پرسپترون
N بردار آموزش بطور چرخشی وارد الگوریتم میشوند. اگر الگوریتم با یکبار مشاهده دادهها همگرا نشود، آنگاه روش تا همگرایی الگوریتم، طبقهبندی صحیح تمام دادههای آموزش، تکرار میشود.
اسلاید 10 :
بیایید w(t) بردار وزن و xt نیز بردار ویژگی مربوطه در گام t باشند. الگوریتم بصورت زیر خواهد بود
الگوریتم بالا به خانواده روشهای پاداش و جزا (Reward and Punishment) تعلق دارد.
با طبقهبندی درست، پاداش عدم تغییر بردار وزن میباشد و جزا نیز تصحیح بردار وزن در صورت اشتباه است.
مثال: مطابق شکل، نقاط آبی به کلاس 1 و نقاط خاکستری به کلاس 2 تعلق دارند. با الگوریتم بالا و نرخ همگرایی واحد و w(0)= [0, 0, 0]T، یک طبقهبند خطی طراحی نمایید
اسلاید 13 :
باتوجه به عدم تغییر بردار وزن در 4 تکرار متوالی، لذا الگوریتم همگرا بوده و جواب نهایی برابر w(0)= [-1, 1, 0]T میباشد. همچنین، خط تصمیم نیز است.
پرسپترون
پساز همگرایی الگوریتم پرسپترون به بردار وزن w و آستانه w0، هدف بعدی نسبت دادن بردار ویژگی ناشناس ورودی به یکی از دو کلاس موجود میباشد.
اسلاید 14 :
عناصر بردار ویژگی، ، به گرههای ورودی شبکه اعمال میشوند. هر ویژگی در وزن مربوطه، ، ضرب میگردد. این وزنها به وزنهای سیناپتیک یا سیناپس معروف میباشند.
اعمال تابع فعالیت (Activation function) به خروجی جمعکننده، و تعیین عضویت x به یکی از کلاسها مطابق علامت خروجی بصورت زیر:
شبکه پایه فوق را شبکه پرسپترون یا نرون مینامند که سادهترین نوع از یادگیری ماشینی محسوب میشود.
گاهی اوقات به ترکیب نرون با هارد لیمیتر نرون مک کالوچ-پیتس نیز گویند.
الگوریتم پاکت (Pocket algorithm)
شرط لازم برای همگرایی پرسپترون، تفکیکپذیری خطی کلاسها میباشد.
در عمل این شرط کمتر برقرار است، الگوریتم پاکت برای حل این مشکل پیشنهاد گردید.
اسلاید 15 :
مراحل مختلف الگوریتم:
بطور تصادفی بردار وزن، ، را مقداردهی میکنیم. یک بردار ذخیره (پاکت!)، ، تعریف میشود. تنظیم شمارنده سابقه، ، برای بردار ذخیره با عدد صفر
در گام تکرار t، بردار وزن بهینه با روش پرسپترون محاسبه میشود. استفاده از این بردار بروز شده برای تعداد h بردار آموزش که بطور صحیح طبقهبندی شدهاند. اگر h > hs باشد آنگاه بردار وزن و h گام t را بترتیب جایگزین بردار ذخیره و شمارنده کرده و الگوریتم را ادامه میدهیم.
عمارت کِسلر (Kesler’s construction)
برای مسئله M کلاسه با تابع تمایز خطی داریم:
برای هر بردار آموزش از کلاس تعداد بردار تشکیل میدهیم
اسلاید 16 :
این بردارها، بردارهای بلوکی با مقدار صفر در همهجا بجز مکان iام و jام میباشند، که بترتیب مقادیر x و –x را بازای i # j دارند.
همچنین، بردار بلوکی وزن نیز تشکیل میشود.
اگر x به کلاس ωi تعلق داشته باشد، آنگاه
کار اکنون طراحی یک طبقهبند خطی در فضای بسطیافته (l +1)M بعدی بطوریکه هر (M -1)N بردار آموزش در سمت مثبت قرار گیرد.
مثال: مسئله سه کلاسه در فضای ویژگی دو بعدی با بردارهای آموزشی زیر را با جداییپذیری خطی درنظر بگیرید. برای طبقهبندی، ابتدا بردارهای آموزش به فضای سه بعدی بسط داده میشوند.
اسلاید 17 :
کار اکنون طراحی یک طبقهبند خطی در فضای بسطیافته (l +1)M بعدی بطوریکه هر (M -1)N بردار آموزش در سمت مثبت قرار گیرد.
الگوریتم پرسپترون برای برقراری با 18 بردار 9 بعدی اجرا میشود. الگوریتم با گام 0.5 پس از 4 اجرا همگرا میشود.
اسلاید 18 :
3-4- روشهای حداقل مربعات
با اینکه در بیشتر موارد کلاسهای موجود بطور خطی تفکیکپذیر نمیباشند، ولی این نوع طبقهبندی منجر به عملکرد زیربهینه از منظر احتمال خطای طبقهبندی میشود.
هدف این بخش، محاسبه بردار وزن تحت یک معیار بهینه مناسب میباشد.
3-4-1- تخمین میانگین مجذور خطا
دوباره برای مسئله دوکلاسه هدف طراحی طبقهبندی با خروجیهای 1± میباشد.
برای ورودی x خروجی طبقهبند خواهدبود و خروجی مطلوب با نشان داده میشود.
بردار وزن برای کمینه کردن MSE بین خروجی مطلوب و واقعی محاسبه میشود:
اسلاید 19 :
جمله آخر معادلات بالا را ماتریس همبستگی یا خودهمبستگی نامند و معادل با ماتریس کوواریانس با میانگین صفر خواهدبود.
عبارت بالا را ماتریس کوواریانس متقابل بین خروجی مطلوب و بردار ویژگی ورودی گویند.
روش MSE حل مجموعهای از معادلات خطی با شرط معکوسپذیری ماتریس همبستگی میباشد.
اسلاید 20 :
تعمیم چندکلاسه
هدف طراحی M تابع تمایز خطی بصورت مطابق معیار MSE میباشد.
خروجی مطلوب اینبار بصورت است.
همچنین، بردار برای ورودی x و بعنوان ماتریسی که هر ستونش بردار وزن کلاسی میباشد، تعریف میشوند.
معیار MSE بصورت زیر خواهدبود:
رابطه بالا معادل با M مسئله کمینهسازی مستقل MSE میباشد، یعنی طراحی تابع تمایز خطی با شرط 1 بودن خروجی مطلوب برای بردارهای همان کلاس و صفر بودن برای بردارهای دیگر مطابق معیار MSE
