ماشین بردار پشتیبانی

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

ماشین بردار پشتیبانی (Support vector machines - SVMs) یکی از روش‌های یادگیری بانظارت[۱] است که از آن برای طبقه‌بندی[۲] و رگرسیون[۳] استفاده می‌کنند.

این روش از جملهٔ روش‌های نسبتاً جدیدی است که در سال‌های اخیر کارایی خوبی نسبت به روش‌های قدیمی‌تر برای طبقه‌بندی از جمله شبکه‌های عصبی پرسپترون نشان داده است. مبنای کاری دسته‌بندی کنندة SVM دسته‌بندی خطی داده‌ها است و در تقسیم خطی داده‌ها سعی می‌کنیم خطی را انتخاب کنیم که حاشیه اطمینان بیشتری داشته باشد. حل معادلة پیدا کردن خط بهینه برای داده‌ها به وسیله روش‌های QP که روش‌های شناخته شده‌ای در حل مسائل محدودیت‌دار هستند صورت می‌گیرد. قبل از تقسیمِ خطی برای اینکه ماشین بتواند داده‌های با پیچیدگی بالا را دسته‌بندی کند داده‌ها را به وسیلهٔ تابعِ phi به فضای با ابعاد خیلی بالاتر[۴] می‌بریم. برای اینکه بتوانیم مساله ابعاد خیلی بالا را با استفاده از این روش‌ها حل کنیم از قضیه دوگانی لاگرانژ[۵] برای تبدیلِ مسالهٔ مینیمم‌سازی مورد نظر به فرم دوگانی آن که در آن به جای تابع پیچیدهٔ phi که ما را به فضایی با ابعاد بالا می‌برد، تابعِ ساده‌تری به نامِ تابع هسته که ضرب برداری تابع phi است ظاهر می‌شود استفاده می‌کنیم. از توابع هسته مختلفی از جمله هسته‌های نمایی، چندجمله‌ای و سیگموید می‌توان استفاده نمود.

یکی از معروفترین خودآموزها مربوط به [۶] است.

کاربردهای SVM[ویرایش]

الگوریتم SVM، جز الگوریتم های تشخیص الگو دسته بندی می شود.از الگوریتم SVM، در هر جایی که نیاز به تشخیص الگو یا دسته بندی اشئادر کلاس های خاص باشد می توان استفاده کرد.در ادامه به کاربرد های این الگوریتم به صورت موردی اشاره می شود:

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

تاریخچه[ویرایش]

الگوریتم SVM اولیه در ۱۹۶۳ توسط Vladimir Vapnik ابداع شدو در سال ۱۹۹۵ توسط Vapnik و Corinna Cortes برای حالت غیرخطی تعمیم داده شد.

خلاصه استفاده عملی از SVM[ویرایش]

ماتریس الگو را آماده می کنیم. تابع کرنلی را برای استفاده انتخاب می کنیم. پارامتر تابع کرنل و مقدار C را انتخاب می کنیم. برای محاسبه ی مقادیرα_i الگوریتم آمورشی را با استفاده از حل کننده های QP اجرا می کنیم. داده های جدید با استفاده از مقادیرα_i و بردارهای پشتیبان می توانند دسته بندی شوند.

مزایا و معایب SVM[ویرایش]

آموزش نسبتاً ساده است برخلاف شبکه های عصبی در ماکزیمم های محلی گیر نمی‌افتد. برای داده های با ابعاد بالا تقریباً خوب جواب می دهد. مصالحه بین پیچیدگی دسته بندی کننده و میزان خطا به طور واضح کنترل می شود. به یک تابع کرنل خوب و انتخاب پارامتر C نیاز دارد.

ماشین بردار پشتیبان خطی[ویرایش]

H3 (green) doesn't separate the two classes. H1 (blue) does, with a small margin and H2 (red) with the maximum margin.
Maximum-margin hyperplane and margins for an SVM trained with samples from two classes. Samples on the margin are called the support vectors.

ما مجوعه داده های آزمایش \mathcal{D} شامل n عضو(نقطه)را در اختیار داریم که به صورت زیر تعریف می شود:

\mathcal{D} = \left\{ (\mathbf{x}_i, y_i)\mid\mathbf{x}_i \in \mathbb{R}^p,\, y_i \in \{-1,1\}\right\}_{i=1}^n

جایی که مقدار y برابر ۱ یا -۱ و هر \mathbf{x}_i یک بردار حقیقی p-بعدی است. هدف پیدا کردن ابرصفحه جداکننده با بیشترین فاصله از نقاط حاشیه ای است که نقاط با y_i=1 را از نقاط باy_i=-1 جدا کند. هر ابر صفحه می تواند به صورت مجموعه ای از نقاط \mathbf{x} که شرط زیر را ارضا می کند نوشت:

\mathbf{w}\cdot\mathbf{x} - b=0,\, جایی که . علامت ضرب است. {\mathbf{w}} بردار نرمال است، که به ابرصفحه عمود است. ما می خواهیم {\mathbf{w}} و {\mathbf{b}} را طوری انتخاب کنیم که بیشترین فاصله بین ابر صفحه های موازی که داده ها را از هم جدامی کنند، ایجاد شود. این ابرصفحه ها با استفاده از رابطه زیر توصیف می شوند.

\mathbf{w}\cdot\mathbf{x} - b=1\,

و

\mathbf{w}\cdot\mathbf{x} - b=-1.\,

اگر داده های آموزشی جدایی پذیر خطی باشند، ما می توانیم دو ابر صفحه در حاشیه نقاط به طوری که هیچ نقطه مشترکی نداشته باشند، در نظر بگیریم و سپس سعی کنیم، فاصله آنها را، ماکسیمم کنیم. با استفاده از هندسه، فاصله این دو صفحه \tfrac{2}{\|\mathbf{w}\|} است. بنابر این ما باید \|\mathbf{w}\| را مینیمم کنیم. برای اینکه از ورود نقاط به حاشیه جلو گیری کنیم، شرایط زیر را اضافه می کنیم: برای هر i

of the first class \mathbf{w}\cdot\mathbf{x}_i - b \ge 1\qquad\text{ for }\mathbf{x}_i

یا

of the second class \mathbf{w}\cdot\mathbf{x}_i - b \le -1\qquad\text{ for }\mathbf{x}_i

این می تواند به صورت زیر نوشته شود:

y_i(\mathbf{w}\cdot\mathbf{x}_i - b) \ge 1,  \quad \text{ for all }  1 \le i \le n.\qquad\qquad(1)

با کنار هم قرار دادن این دو یک مسئله بهینه سازی به دست می آید:

Minimize (in {\mathbf{w},b})

\|\mathbf{w}\|

subject to (for any i = 1, \dots, n)

y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1. \,

فرم اولیه[ویرایش]

مسئله بهینه سازی مشاهده شده در قسمت قبل، مسئله سختی، برای حل کردن است، زیرا به||w|| وابسته است (نرم w ) . خوشبختانه می توانیم، بدون تغییر در مسئله||w|| را با\tfrac{1}{2}\|\mathbf{w}\|^2 جانشین کنیم( عبارت ½ برای آسودگی در محاسبات ریاضی آورده شده). این یک مسئله بهینه سازی (OP)برنامه ریزی غیرخطی(QP) است. به طور واضح تر :

Minimize (in {\mathbf{w},b}) c

\frac{1}{2}\|\mathbf{w}\|^2

subject to (for any i = 1, \dots, n)

y_i(\mathbf{w}\cdot\mathbf{x_i} - b) \ge 1.

می توان عبارت قبل را با استفاده از ضرایب نا منفی لاگرانژ به صورت زیر نوشت که در آن ضرایب لاگرانژ هستند \alpha_i:

\min_{\mathbf{w},b,\boldsymbol{\alpha}}  \{ \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n}{\alpha_i[y_i(\mathbf{w}\cdot \mathbf{x_i} - b)-1]} \}

اما فرمول فوق اشتباه است . فرض کنید ما بتوانیم خانواده ای از ابرصفحات که نقاط را تقسیم می کنند پیدا کنیم . پس همه y_i(\mathbf{w}\cdot\mathbf{x_i} - b) - 1 \ge 0 . بنا بر این ما می توانیم مینیمم را با فرستادن همه \alpha_i به+\infty پیدا کنیم. با این حال شرط پیش گفته می تواند به صورت پایین بیان شود:

\min_{\mathbf{w},b } \max_{\boldsymbol{\alpha} } \{ \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{n}{\alpha_i[y_i(\mathbf{w}\cdot \mathbf{x_i} - b)-1]} \}

ما به دنبال نقاط saddle میگردیم.حالا می توان این مسئله را به کمک برنامه ریزی غیرخطی استاندارد حل کرد. جواب می تواند به صورت ترکیب خطی از بردارهای آموزشی بیان شود :

\mathbf{w} = \sum_{i=1}^n{\alpha_i y_i\mathbf{x_i}}

تنها چند\alpha_i بزرگتر از صفر خواهد بود.\mathbf{x_i} متناظر، دقیقاً همان بردار پشتیبان خواهد بود و به شرط را ارضا خواهد کرد. از این می توان نتیجه گرفت که بردارهای پشتیبان شرط زیر را نیز ارضا می کنند: y_i(\mathbf{w}\cdot\mathbf{x_i} - b) = 1 که اجازه می دهد مفدار b تعریف شود. در عمل الگوریتم مقاوم تر خواهد بود اگر از تمام N_{SV} بردار پشتیبان میانگین گرفته شود:

b = \frac{1}{N_{SV}} \sum_{i=1}^{N_{SV}}{(\mathbf{w}\cdot\mathbf{x_i} - y_i)}

فرم دوگان[ویرایش]

استفاده از این واقعیت که \|\mathbf{w}\|^2 = w\cdot w و جانشینی \mathbf{w} = \sum_{i=1}^n{\alpha_i y_i\mathbf{x_i}} می توان نشان داد که دوگان SVM به مسئله بهینه سازی زیر ساده می شود:

Maximize (in \alpha_i )

\tilde{L}(\mathbf{\alpha})=\sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i, j} \alpha_i \alpha_j y_i y_j \mathbf{x}_i^T \mathbf{x}_j=\sum_{i=1}^n \alpha_i - \frac{1}{2}\sum_{i, j} \alpha_i \alpha_j y_i y_j k(\mathbf{x}_i, \mathbf{x}_j)

subject to (for any i = 1, \dots, n)

\alpha_i \geq 0,\,

and to the constraint from the minimization in  b

 \sum_{i=1}^n \alpha_i y_i = 0.

در اینجا هسته به صورت k(\mathbf{x}_i,\mathbf{x}_j)=\mathbf{x}_i\cdot\mathbf{x}_j تعریف می شود. عبارت \alpha تشکیل یک دوگان برای بردار وزن ها مجموعه آموزشی می دهد:

\mathbf{w} = \sum_i \alpha_i y_i \mathbf{x}_i.

ماشین بردار پشتیبان چند کلاسی[ویرایش]

SVM اساساً یک جداکننده دودویی است. در بخش قبلی پایه های تئوری ماشین های بردار پشتیبان برای دسته بندی دو کلاس تشریح شد. یک تشخیص الگوی چند کلاسی می تواند به وسیله ی ترکیب ماشین های بردار پشیبان دو کلاسی حاصل شود. به طور معمول دو دید برای این هدف وجود دارد. یکی از آنها استراتژی "یک در مقابل همه " برای دسته بندی هر جفت کلاس و کلاس های باقی‌مانده است. دیگر استراتژی "یک در مقابل یک" برای دسته بندی هر جفت است. در شرایطی که دسته بندی اول به دسته بندی مبهم منجر می شود.برای مسائل چند کلاسی٬رهیافت کلی کاهش مسئله ی چند کلاسی به چندین مسئله دودویی است. هریک از مسائل با یک جداکننده دودویی حل می شود. سپس خروجی جداکننده های دودویی SVM با هم ترکیب شده و به این ترتیب مسئله چند کلاس حل می شود.

ماشین های بردار پشتیبان غیرخطی[ویرایش]

Kernel Machine (Method)

ابرصفحه جداکننده بهینه اولین بار توسط Vapnik در سال ۱۹۶۳ ارائه شد که یک دسته کننده خطی بود. در سال ۱۹۹۲ ،Bernhard Boser ، Isabelle GuyonوVapnik راهی را برای ایجاد دسته بند غیرخطی، با استفاده قرار دادن هسته برای پیدا کردن ابرصفحه با بیشتر حاشیه، پیشنهاد دادند.[۷] الگوریتم نتیجه شده ظاهراً مشابه است، به جز آنکه تمام ضرب های نقطه ای با یک تابع هسته غیرخطی جایگذین شد اند. این اجازه میدهد، الگوریتم، برای ابرصفحه با بیشترین حاشیه در یک فضای ویژگی تغییرشکل داده، مناسب باشد. ممکن است، تغییرشکل غیرخطی باشد و فضای تغییر یافته، دارای ابعاد بالاتری باشد. به هر حال دسته کننده، یک ابرصفحه در فضای ویژگی با ابعاد بالا است، که ممکن است در فضای ورودی نیز غیرخطی باشد.

اگر از هسته با تابع گوسیین استفاده شود، فضای ویژگی متناظر، یک فضای هیلبرت نامتناهی است. دسته کننده ی بیشترین حاشیه، خوش ترتیب است، بنابر این ابعاد نامتناهی، نتیجه را خراب نمی‌کند. هسته های متداول به صورت زیر هستند:

هسته با انتقال \varphi(\mathbf{x_i}) با تساوی k(\mathbf{x_i}, \mathbf{x_j}) = \varphi(\mathbf{x_i})\cdot \varphi(\mathbf{x_j}) در ارتباط است. همچنین مقدار wدر فضای انتقال یافته برابر \textstyle\mathbf{w} = \sum_i \alpha_i y_i \varphi(\mathbf{x}_i). است. ضرب نقطه ای با w می تواند توسط هسته محاسبه شود یعنی \textstyle \mathbf{w}\cdot\varphi(\mathbf{x}) = \sum_i \alpha_i y_i k(\mathbf{x}_i, \mathbf{x}). به هر حال در حالت عادی w' وجود ندارد، به طوری که \mathbf{w}\cdot\varphi(\mathbf{x}) = k(\mathbf{w'}, \mathbf{x}).

پانوشته‌ها[ویرایش]

  1. Supervised learning
  2. Classification
  3. Regression
  4. High dimensional space
  5. Lagrange Duality Theorems
  6. A Tutorial on Support Vector Machines
  7. B. E. Boser, I. M. Guyon, and V. N. Vapnik. A training algorithm for optimal margin classifiers. In D. Haussler, editor, 5th Annual ACM Workshop on COLT, pages 144–152, Pittsburgh, PA, 1992. ACM Press

جستارهای وابسته[ویرایش]

منابع[ویرایش]

Christopher J. C. Burges. "A Tutorial on Support Vector Machines for Pattern Recognition". Data Mining and Knowledge Discovery 2:121 - 167, 1998 (http://research.microsoft.com/~cburges/papers/SVMTutorial.pdf)

پیوند به خارج[ویرایش]

کتاب شناسی[ویرایش]

  • Sergios Theodoridis and Konstantinos Koutroumbas "Pattern Recognition", 4th Edition, Academic Press, 2009, ISBN 978-1-59749-272-0
  • Nello Cristianini and John Shawe-Taylor. An Introduction to Support Vector Machines and other kernel-based learning methods. Cambridge University Press, 2000. ISBN 0-521-78019-5 ([۱] SVM Book)
  • Huang T.-M., Kecman V., Kopriva I. (2006), Kernel Based Algorithms for Mining Huge Data Sets, Supervised, Semi-supervised, and Unsupervised Learning, Springer-Verlag, Berlin, Heidelberg, 260 pp. 96 illus., Hardcover, ISBN 3-540-31681-7 [۲]
  • Vojislav Kecman: "Learning and Soft Computing — Support Vector Machines, Neural Networks, Fuzzy Logic Systems", The MIT Press, Cambridge, MA, 2001.[۳]
  • Bernhard Schölkopf and A. J. Smola: Learning with Kernels. MIT Press, Cambridge, MA, 2002. (Partly available on line: [۴].) ISBN 0-262-19475-9
  • Bernhard Schölkopf, Christopher J.C. Burges, and Alexander J. Smola (editors). "Advances in Kernel Methods: Support Vector Learning". MIT Press, Cambridge, MA, 1999. ISBN 0-262-19416-3. [۵]
  • John Shawe-Taylor and Nello Cristianini. Kernel Methods for Pattern Analysis. Cambridge University Press, 2004. ISBN 0-521-81397-2 ([۶] Kernel Methods Book)
  • Ingo Steinwart and Andreas Christmann. Support Vector Machines. Springer-Verlag, New York, 2008. ISBN 978-0-387-77241-7 ([۷] SVM Book)
  • P.J. Tan and D.L. Dowe (2004), MML Inference of Oblique Decision Trees, Lecture Notes in Artificial Intelligence (LNAI) 3339, Springer-Verlag, pp1082-1088. (This paper uses minimum message length (MML) and actually incorporates probabilistic support vector machines in the leaves of decision trees.)
  • Vladimir Vapnik. The Nature of Statistical Learning Theory. Springer-Verlag, 1995. ISBN 0-387-98780-0
  • Vladimir Vapnik, S.Kotz "Estimation of Dependences Based on Empirical Data" Springer, 2006. ISBN 0-387-30865-2, 510 pages [this is a reprint of Vapnik's early book describing philosophy behind SVM approach. The 2006 Appendix describes recent development].
  • Dmitriy Fradkin and Ilya Muchnik "Support Vector Machines for Classification" in J. Abello and G. Carmode (Eds) "Discrete Methods in Epidemiology", DIMACS Series in Discrete Mathematics and Theoretical Computer Science, volume 70, pp. 13–20, 2006. [۸]. Succinctly describes theoretical ideas behind SVM.
  • Kristin P. Bennett and Colin Campbell, "Support Vector Machines: Hype or Hallelujah?", SIGKDD Explorations, 2,2، 2000, 1–13. [۹]. Excellent introduction to SVMs with helpful figures.
  • Ovidiu Ivanciuc, "Applications of Support Vector Machines in Chemistry", In: Reviews in Computational Chemistry, Volume 23, 2007, pp. 291–400. Reprint available: [۱۰]
  • Catanzaro, Sundaram, Keutzer, "Fast Support Vector Machine Training and Classification on Graphics Processors", In: International Conference on Machine Learning, 2008 [۱۱]
  • Colin Campbell and Yiming Ying, Learning with Support Vector Machines, 2011, Morgan and Claypool. ISBN 978-1-60845-616-1. [۱۲]