بخشی از پاورپوینت
اسلاید 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 :
3-4- روشهای حداقل مربعات
با اینکه در بیشتر موارد کلاسهای موجود بطور خطی تفکیکپذیر نمیباشند، ولی این نوع طبقهبندی منجر به عملکرد زیربهینه از منظر احتمال خطای طبقهبندی میشود.
هدف این بخش، محاسبه بردار وزن تحت یک معیار بهینه مناسب میباشد.
3-4-1- تخمین میانگین مجذور خطا
دوباره برای مسئله دوکلاسه هدف طراحی طبقهبندی با خروجیهای 1± میباشد.
برای ورودی x خروجی طبقهبند خواهدبود و خروجی مطلوب با نشان داده میشود.
بردار وزن برای کمینه کردن MSE بین خروجی مطلوب و واقعی محاسبه میشود:
اسلاید 16 :
جمله آخر معادلات بالا را ماتریس همبستگی یا خودهمبستگی نامند و معادل با ماتریس کوواریانس با میانگین صفر خواهدبود.
عبارت بالا را ماتریس کوواریانس متقابل بین خروجی مطلوب و بردار ویژگی ورودی گویند.
روش MSE حل مجموعهای از معادلات خطی با شرط معکوسپذیری ماتریس همبستگی میباشد.
اسلاید 17 :
تعمیم چندکلاسه
هدف طراحی M تابع تمایز خطی بصورت مطابق معیار MSE میباشد.
خروجی مطلوب اینبار بصورت است.
همچنین، بردار برای ورودی x و بعنوان ماتریسی که هر ستونش بردار وزن کلاسی میباشد، تعریف میشوند.
معیار MSE بصورت زیر خواهدبود:
رابطه بالا معادل با M مسئله کمینهسازی مستقل MSE میباشد، یعنی طراحی تابع تمایز خطی با شرط 1 بودن خروجی مطلوب برای بردارهای همان کلاس و صفر بودن برای بردارهای دیگر مطابق معیار MSE
اسلاید 18 :
3-4-2- تخمین تصادفی و الگوریتم LMS
روش MSE به محاسبه ماتریس همبستگی و کوواریانس نیاز دارد. همچنین، توزیع دادهها نامعین میباشند (اگر معین باشند از روش بیزین استفاده میکنیم).
بدون داشتن هرگونه دانشی درباره توزیع کلاسها، معادلهای بشکل را درنظر بگیرید که رشتهای از بردارهایتصادفی با توزیع یکسان است.
مقدار میانگین با نمونههای متغیرهای تصادفی بجای امید ریاضی (بدلیل فقدان دانش) از آزمایشات محاسبه میشود.
گام ρk با ارضای دو شرط زیر منجر به همگرایی رابطه بالا میشود
اسلاید 19 :
بمنظور کار طبقهبندی (مسئله دوکلاسه) با اعمال متوالی جفت بردارهای آموزش بصورت (yk, xk) و اختصاص 1± به خروجی مطلوب در این بردار، داریم:
الگوریتم بالا، الگوریتم LMS یا Widrow- Hoff نام دارد. این روش بطور مجانبی به حل MSE همگرا میشود.
وجود شکلهای مختلف از LMS؛ یکی جایگزینی ρ ثابت بجای ρk که در این حالت به حل MSE همگرا نمیشود.
اگر انتخاب شود، آنگاه الگوریتم به جواب بهینه MSE همگرا خواهدشد
هرچه ρ کوچکتر باشد، واریانس حول تخمین MSE کوچکتر است. از سوییدیگر، کوچک بودن گام حرکت منجر به کند شدن سرعت همگرایی میشود.
گام حرکت ثابت منجر به عملکرد مطلوب برای دادههای غیر ایستان میگردد.
اسلاید 20 :
3-4-3- مجموع تخمین مربعات خطا
معیار مجموع مربعات خطا یا حداقل مربعات (LS) نزدیک به MSE بوده و داریم:
با کمینه کردن معادله بالا، داریم:
با تعریف زیر خواهیم داشت:
X یک ماتریس N × l است که سطرهای آن بردارهای ویژگی آموزش میباشند و y نیز برداری از پاسخهای مطلوب است.
