f(x)=sign(w.x+b).
بردار وزن w، بردار عمود بر ابرصفحه جداکننده و b مقدار بایاس است و منظور از w.x حاصلضرب داخلی می باشد. Vapnik ثابت کرد که بعد VC برای طبقه بندی کننده هایی از نوع ابر صفحات کانونی دارای یک کران بالاست که این کران بالا با توان دوم نرم بردار وزن یعنی نسبت مستقیم دارد [۱۳] .
در واقع اگر ما را محدود کرده و مینیمم کنیم، بعد VC طبقه بندی کننده را می نیمم کردهایم و تخمین ما از مقدار ریسک واقعی بصورت احتمالی دقیق تر بوده و خاصیت تعمیم دستهبندی کننده بیشتر خواهد شد.
(۱-۱۲)
رابطه بین خاصیت تعمیم طبقه بندی کننده با نرم بردار وزن را می توان به طریق دیگر نیز توجیه کرد :
فرض کنید دادههای دو کلاس جدایی پذیر باشند و بردارهای ویژگی مرزی کلاس اول روی ابرصفحه و بردارهای ویژگی مرزی کلاس دوم روی ابرصفحه قرار گیرند . ابر صفحات و به این صورت تعریف می شوند:
+۱ , (۱-۱۳)
الگوهایی که بر روی ابر صفحات و قرار می گیرند بردار پشتیبان[۶] نامیده می شوند. ناحیه بین دو ابر صفحه و را حاشیه یا ناحیه مرزی[۷] گویند . فاصله بین دو ابر صفحه و برابر خواهد بود . طراحی ابر صفحه با بیشترین عرض ناحیه مرزی یا ناحیه مرزی بهینه [۸]بر این استوار است که با شرط درست طبقهبندی شدنِ الگوها، عرض ناحیه مرزی حداکثر شود ، یعنی ماکزیمم شود و مینیمم گردد . هدف این است که اولا الگوها درست طبقهبندی گردند و ثانیًا بر روی و یا خارج از ناحیه مرزی واقع شوند یعنی:
For i=1,2,…,N yi(wxi+b)(1-14)
پس در واقع طراحی یک طبقهبندی کننده ابرصفحه ای با ناحیه مرزی بهینه بصورت زیر خواهد بود:
(۱-۱۵)
واضح است که داریم :
W= (1-16)
مسأله فوق یک مسأله بهینه سازی مقید از نوع محدب و درجه دوم است . برای حل این مسأله ، تابع لاگرانژی زیر را تشکیل داده و ضرایب لاگرانژ را بدست میآوریم :
L(w,b,α)=۱/۲w.w- (1-17)
برای اینکه (w,b,α) جواب مسأله باشد، این جواب باید در شرایط KKT [۹] صدق کند و در نقطه جواب مشتق L نسبت به w,b,α برابر صفر باشد.با مساوی قرار دادن مشتق برابر صفر به معادلات زیر می رسیم:
W= , =0 (1-18)
با قرار دادن w از رابطه فوق در L(w,b,α) به مسأله دوگان برای بهینه سازی مقید خواهیم رسید:
(۱-۱۹)
پس از حل این مسأله دوگان بهینه سازی، ضرایب لاگرانژ بدست می آید در واقع هر کدام از ضرایب لاگرانژ متناظر با یکی از الگوهای می باشند، الگوهای را که متناظر با هستند بردار پشتیبان می نامیم. مقدار بردار وزن و b از روابط زیر بدست میآیند:
(۱-۲۰) W=
(۱-۲۱)
تابع تمایز برای طبقهبندی یک الگوی ورودی x بصورت زیر خواهد بود:
F(x)=sign (1-22)
۱-۴-۲ ماشین بردار پشتیبان درحالت جدایی ناپذیر
در بخش ۱-۴-۱، مسأله SVM را برای حالت جدایی پذیر بیان شد ولی در تمامی مسایل بصورت جدایی ناپذیر میباشد. برای حالت جدایی ناپذیر یک دسته از متغیرها ی بنام متغیرهای کمبود تعریف
میکنیم طوری که شرط زیر برقرار باشد[۱۴]:
(۱-۲۳)
واضح است که هر چقدر مجموع مقادیر متغیرهای بیشتر شود، از حالت بهینه دورتر خواهیم شد و خطا بیشتر می گردد پس مسأله بهینه سازی مقید را بصورت زیر تعریف میکنیم:
(۱-۲۴)
برای این مسأله نیز شرایط KKT را در نقطه جواب تشکیل داده و به دوگان زیر میرسیم:
(۱-۲۵)
همانطور که ملاحظه میشود حل مسأله SVM در حالت جدایی ناپذیر مشابه حل آن در حالت جدایی پذیر است با این جدایی ناپذیر مشابه حل آن در حالت جدایی پذیر است با این فرق می کند. پس از بدست آوردن ضرایب لاگرانژ الگوهایی که ضرایب لاگرانژ آنها در رابطه زیر صدق میکنند، بردار پشتیبان می شوند:
مقدار W و شکل تابع تمایز هم مشابه حالت جدایی پذیر خواهد بود. ابر صفحه بدست آمده در حالت جدایی ناپذیر را ابر صفحه با ناحیه مرزی نرم مینامند.
۱-۴-۳ ماشین بردار پشتیبان غیرخطی
ماشینهای بردار پشتیبان ذکر شده در ۱-۴-۱ و ۱-۴-۲ ، برای دستهبندی الگوهای یک مسأله دو کلاسه از مرزهای جداکننده خطی و از یک ابرصفحه استفاده میکند و در واقع حاصلضرب داخلی بردار ورودی با هر کدام از بردارهای پشتیبان در فضای dبعدی ورودی محاسبه میشود.
Vapnik با بهره گرفتن از مفهوم حاصلضرب داخلی در فضاهای هیلبرت و قضیه هیلبرت اشمیت نشان داد که ابتدا میتوان بردار ورودی x را با یک تبدیل غیرخطی به یک فضای با بعد زیاد انتقال داد و در آن فضا حاصلضرب داخلی را انجام داد و ثابت کرد که اگر یک هسته متقارن ، شرایط قضیه Mercer را داشته باشد، اعمال این هسته در فضای ورودی با بعد کم میتواند به عنوان حاصلضرب داخلی در یک فضای هیلبرت با بعد زیاد تلقی شود و محاسبات را به شدت کاهش دهد. [ ۱۵] بعنوان مثال تابع هسته میتواند به فرمهای زیر باشد:
K(x,y)=
K(x,y)=exp , K(x,y)=tanh(xy+θ) (۱-۲۶)
این هستهها به ترتیب هسته چند جمله ای، هسته گاوسی و هسته تانژانت هیپربولیک هستند . مسأله بهینهسازی دوگان در حالت جدایی ناپذیر و غیرخطی بصورت زیر خواهد بود:
(۱-۲۷)
بردارهای پشتیبان الگوهایی هستند که ضرایب لاگرانژ متناظر آنها در رابطه صدق کند . تعدادی از بردارهای پشتیبان که ضرایب لاگرانژ متنا ظر آنها در رابطه صدق کند و تعداد آنها است برای محاسبه b استفاده میشود:
, .b=(1-28)
تابع تصمیمگیری بصورت زیر خواهد بود:
F(x)=sign (1-29)
شاید به گونه ای بتوان محبوبیت کنونی روش ماشین بردار پشتیبان را با محبوبیت شبکههای عصبی در دهه گذشته مقایسه کرد. علت این قضیه نیز قابلیت استفاده این روش در حل مسائل گوناگون می باشد، در حالیکه روشهایی مانند درخت تصمیمگیری را نمیتوان به راحتی در مسائل مختلف به کار برد.
در هیچیک از این روشها خاصیت تعمیم طبقهبندی کننده بطور مستقیم در تابع هزینه روش دخالت داده نشده است و طبقهبندی کننده طراحی شده نیز دارای خاصیت تعمیم دهندگی کمی میباشد.
اگر طراحی دسته بندی کننده الگو را بعنوان یک مسأله بهینهسازی در نظر بگیریم ، بسیاری از این روشها با مشکل بهینه های محلی در تابع هزینه مواجهاند و در دام بهینههای محلی گرفتار میآیند.
مشکل دیگری نیز وجود دارد وآن، تعیین ساختار و توپولوژی دستهبندی کننده قبل از طراحی است، که بعنوان مثال تعیین تعداد بهینه گرههای لایه مخفی درشبکه های عصبی MLP تعداد توابع گاوسی در شبکههای عصبی RBF و یا تعداد بهینه حالتها و توابع گاوسی در مدل پنهان مارکف میباشد. همه این عوامل باعث میشوند که در عمل با روش های پیشنهاد شده قبلی نتوانیم به یک دستهبندی کننده بهینه برسیم.
در اینجا فرایند یادگیری در دو بخش انجام میشود:
[یکشنبه 1400-08-02] [ 08:06:00 ب.ظ ]
|