وبلاگ

با کمی دقت در الگوریتم های آموزشی به نظر می­رسد که یکی از مشکلات چنین سیستم هایی از یک طرف تعداد زیاد نمونه ها برای آموزش و از طرف دیگر افزایش تعداد ویژگی ها برای بیان هر نمونه یا به عبارت دیگر افزایش بعد می باشد بنابراین برای داشتن خروجی مطلوب نیاز به طبقه بندی کننده ای است که بتواند یک مجموعه بزرگ از داده های آموزشی با ابعاد زیاد را حمایت کند.ابعاد زیاد در یک طبقه بندی باعث بوجود آمدن پارامترهای زیادی می شود(مثلا وقتی که ابعاد زیاد شود، ماتریس کواریانس بزرگ­تر شده و پارامترهای بیشتری باید محاسبه شود) که تخمین آنها کار دشواری است.

به طور معمول پارامترهای زیاد انعطاف پذیری بالای طبقه کننده را نسبت به داده های آموزشی به دنبال دارد ولی همیشه اینطور نیست.طبقه بندی کننده هایی نیز وجود دارند که انعطاف پذیری بسیار بالایی دارند ولی در مقابل، پارامترهای کمی دارند. البته باید به این نکته توجه کرد که انعطاف پذیری بالا بر روی داده های آموزشی دلیل مناسب بودن یک طبقه بندی کننده نیست چون ممکن است طبقه کننده ای که از انعطاف پذیری بالایی روی داده های آموزشی برخوردار است بیش برازش شود و روی نمونه جدیدی که وارد طبقه بندی کننده می­ شود بسیار نامناسب عمل کند.همچنین Vapnik بیان کرد انعطاف پذیری لزوماً متناسب با تعداد پارامترهای دسته بندی کننده نیست.براین اساس Vapnik بعد ^[42]VC را به عنوان معیار مناسب تری برای سنجش انعطاف پذیری یک طبقه بندی کننده تعریف نموده است و در نهایت طبقه بندی کننده را براساس مینیمم کردن ریسک ساختاری^[43] به جای مینیمم کردن ریسک تجربی^[44] طراحی نمود.در ادامه بعد VC، ریسک ساختاری و تجربی توضیح داده خوهد شد]11[.

2-8-3 کاربردهای SVM

الگوریتم SVMجز الگوریتم­های تشخیص الگو دسته بندی می­ شود.از الگوریتم SVMدر هر جایی که نیاز به تشخیص الگو یا دسته بندی اشیاء در کلاس های خاص باشد می توان استفاده کرد.در ادامه به کاربردهای این الگوریتم به صورت موردی اشاره می­ شود.
سیستم آنالیز ریسک، کنترل هواپیما بدون خلبان، ردیابی انحراف هواپیما، شبیه سازی مسیر، سیستم راهنمایی اتوماتیک اتومبیل، سیستمهای بازرسی کیفیت، آنالیز کیفیت جوشکاری، پیش بینی کیفیت، آنالیز کیفیت کامپیوتر، آنالیز عملیاتهای آسیاب، آنالیز طراحی محصول شیمیایی، آنالیز نگهداری ماشین، پیشنهاد پروژه، مدیریت و برنامه ریزی، کنترل سیستم فرایند شیمیایی و دینامیکی، طراحی اعضای مصنوعی، بهینه سازی زمان پیوند اعضا، کاهش هزینه بیمارستان، بهبود کیفیت بیمارستان، آزمایش اتاق اورژانس، اکتشاف روغن و گاز، کنترل مسیر در دستگاه های خودکار، ربات، جراثقال، سیستمهای بصری، تشخیص صدا، اختصار سخن، کلاسه بندی صوتی، آنالیز بازار، سیستمهای مشاوره ای محاسبه هزینه موجودی، اختصار اطلاعات و تصاویر، خدمات اطلاعاتی اتوماتیک، مترجم لحظه ای زبان، سیستمهای پردازش وجه مشتری، سیستمهای تشخیص ترمز کامیون، زمانبندی وسیله نقلیه، سیستمهای مسیریابی، کلاسه بندی نمودارهای مشتری/بازار، تشخیص دارو، بازبینی امضا، تخمین ریسک وام، شناسایی طیفی، ارزیابی سرمایه و غیره.

2-8-4 مزایا و معایب SVM

• • طراحی دسته بندی کننده با حداکثر تعمیم

• • رسیدن به بهینه سراسری تابع هزینه

• • تعیین خودکار ساختار و توپولوژی بهینه برای طبقه بندی کننده

• • مدل کردن توابع تمایز غیر خطی با بهره گرفتن از هسته های غیرخطی و مفهوم حاصلضرب داخلی در فضاهای هیلبرت

• • آموزش نسبتا ساده است

• • برخلاف شبکه های عصبی در ماکزیمم های محلی گیر نمی­افتد.

• • برای داده های با ابعاد بالا تقریبا خوب جواب می­دهد.

• • مصالحه بین پیچیدگی دسته بندی کننده و میزان خطا به طور واضح کنترل می­ شود.

• • به یک تابع کرنل خوب و انتخاب پارامتر C نیاز دارد]9[.

2-8-5 تعاریف کلی

2-8-5-1تابع تصمیم مسائل دو کلاسی

ابتدا طبقه بندی یک بردار  - بعدی  به یکی از دو کلاس را بررسی می­کنیم. فرض می­کنیم که  و  به ترتیب تابع تصمیم برای کلاس های یک و دو باشند و به کلاس یک تعلق دارد اگر  و به کلاس دو تعلق دارد اگر  .
تابع های ذکر شده در بالا را تابع تصمیم گوئیم.
شکل (2-8)-تابع تصمیم فضای دو بعدی
این روابط را به صورت زیر نیز می­توانیم تعریف کنیم که به کلاس یک تعلق دارد، اگر  و به کلاس دو تعلق دارد، اگر  .مرز دو کلاس نیز به شکل  معرفی خواهد شد.
نشان می دهدکه مرز کلاس به صورت غیر مستقیم بدست می آید. این نوع از تابع تصمیم را، تابع تصمیم غیر مستقیم^[45] می­نامیم.
اگر تابع تصمیم را به صورت  تعریف کنیم، را در کلاس یک طبقه بندی می­کنیم، اگر  و در کلاس دو طبقه بندی می­کنیم، اگر  .مرز کلاس به صورت  تعریف می شود. این نوع تابع تصمیم یک تابع تصمیم مستقیم^[46] نامیده می شود.
اگر تابع تصمیم خطی باشد، دراین صورت  را به صورت  تعریف می­کنیم.در واقع این معادله خط در فضای دو بعدی، صفحه در فضای سه بعدی و فوق صفحه در فضاهای بزرگتر است.  یک بردار m-بعدی است و  ، ترم بایاس است. کلاسی که در طرف مثبت ابرصفحه است  و کلاس دیگر که در طرف منفی ها است. این چنین مسائل را که توسط یک خط از هم جدا شده اند را جداپذیر خطی^[47] گویند.
شکل (2-9)- مرکز کلاس برای شکل 2-8

2-8-5-2 تعیین تابع تصمیم(ابر صفحه جداکننده)^[48]

شکل 2-10 که در زیر آمده ،یک نمونه از تابع تصمیم را نشان می­دهد طوری که داده های آموزشی دو کلاس کاملاً مجزا هستند.فرض کنید که دایره و مربع به ترتیب داده های آموزشی مربوط به دو کلاس یک و دو باشند.حتی اگر تابع تصمیم  را به سمت راست جا به جا شود(منحنی نقطه نقطه در شکل (2-10)) بازهم داده های آموزشی درست طبقه بندی شده اند. بنابراین می توانیم چندین تابع تصمیم داشته باشیم طوری که داده های آموزشی را به درستی طبقه بندی کنند.
شکل (2-10)- مرز کلاس بدون هیچ اشتراکی
اگر چه بی نهایت حالت برای تعیین مکان تابع تصمیم وجود دارد اما آنچه باید اینجا ذکر شود این است که تابع تصمیمی که بیشترین فاصله را با داده های آموزشی داشته باشد را تابع تصمیم بهینه گوئیم.اما تعیین تابع تصمیم غیر خطی چندان ساده نیست.به همین منظور بهتر است که فضای ورودی­ ها را به فضایی با بعد بالاتر با نام فضای ویژگی ها نگاشت داده شود که در این فضا تابع تصمیم یا ابر صفحه بهینه را بدست آوریم.

2-8-5-3 بعد VC

اگر مجموعه  مجموعه ای از توابع تصمیم گیری و  بردار ویژگی^[49] باشد، می­توان  های مختلفی را تعریف کرد که بعد VC یک ویژگی از این مجموعه توابع می­باشد.حال اگر مجموعه داده شامل l نقطه باشد در حالت دو کلاسه می توان آنها را با  حالت ممکن برچسب دهی^[50] کرد.بعد VC که با h نمایش داده می­ شود، بیانگر ماکزیمم تعداد نقاطی است که می­توانند توسط مجموعه  از هم جدا شوند.برای مثال در یک فضای دو بعدی می توان سه نقطه را به یکی از هشت حالت ممکن برچسب دهی کرد که در هر هشت حالت می توان این سه نقطه را بطور خطی به کلاس مربوطه اختصاص داد.
شکل (2-11)- بعد VC ]11[
در حالت کلی برای یک مجموعه l نقطه ای، اگر یک نقطه به عنوان مرجع در نظر گرفته شود و حالتهای l-1 نقطه باقیمانده بطور خطی غیر وابسته باشند، میتوان در فضای  آنها را توسط فوق صفحات^[51] جهت دار دسته بندی کرد.نتیجه اینکه در یک فضای N بعدی، h برابر با N+1 می­باشد.
بنابراین طبق این تعریف میتوان گفت بعد VC یک طبقه بندی کننده خطی در فضای دو بعدی برابر 3 و بعد VC یک طبقه بندی کننده نزدیک ترین همسایه در فضای دو بعدی برابر با  است.توجه شود که در طبقه بندی کننده نزدیک ترین همسایه مهم نیست که چه تعداد داده آموزشی داریم، بلکه میتوان با هر تعداد داده آموزشی یک طبقه بندی کننده مناسب طراحی کرد که داده ها را به طور مجزا از هم تفکیک کند]11[.
2-8-5-4حداقل سازی ریسک تجربی^[52]
عمل تقسیم بندی دو کلاسه نمونه ها را می توان به فرم زیر نوشت :
و
که  تابع تصمیم گیری،  بردار پارامترها و  مجموعه ای از پارامترهاست.همچنین یک مجموعه از مثال های  داریم که دارای تابع توزیع نامعلوم  هستند.هدف پیدا کردن  است که منجر به حداقل شدن ریسک مورد انتظار^[53] زیر می­ شود :

تابع  معمولا تحت عنوان تابع فرضیه^[54] و مجموعه  تحت عنوان فضای فرضیه^[55] نامیده می­شوند که این فضا را با H نمایش می­دهیم.بنابراین ریسک مورد انتظار معیاری برای ارزیابی عملکرد  ها در نسبت دادن صحیح برچسب y به نمونه X می­باشد.
به عنوان مثال مجموعه توابع  می تواند مجموعه ای از توابع RBF یا یک پرسپترون چندلایه^[56] (با تعداد معینی واحد مخفی) باشد که در این حالت مجموعه  مرزهای شبکه می­باشد.
از آنجا که تابع توزیع  نامشخص است نمی­ توان ریسک مورد انتظار را محاسبه کرد و در نتیجه نمی­ توان این ریسک را حداقل نمود.ولی به دلیل اینکه ما به نمونه های  دسترسی داریم، می توان یک تخمین از  را محاسبه نمود که این تقریب، ریسک تجربی نامیده می­ شود.