1
ماشین بردار پشتیبان
2
مقدمه
SVM دسته بندی کننده ای است که جزو شاخه Kernel Methods دریادگیری ماشین محسوب میشود.
SVMدر سال 1992 توسط Vapnik معرفی شده و بر پایه statistical learning theory بنا گردیده است.
شهرت SVM بخاطر موفقیت آن در تشخیص حروف دست نویس است که با شبکه های عصبی بدقت تنظیم شده برابری میکند: 1.1% خطا
3
مقدمه
هدف این دسته الگوریتم ها تشخیص و متمایز کردن الگوهای پیچیده در داده هاست ( از طریق کلاسترینگ، دسته بندی، رنکینگ، پاکسازی و غیره)
مسایل مطرح:
الگوهای پیچیده را چگونه نمایش دهیم
چگونه از مسئله overfitting پرهیز کنیم
4
ایده اصلی
با فرض اینکه دسته ها بصورت خطی جداپذیر باشند، ابرصفحه هائی با حداکثر حاشیه (maximum margin) را بدست می آورد که دسته ها را جدا کنند.
در مسایلی که داده ها بصورت خطی جداپذیر نباشند داده ها به فضای با ابعاد بیشتر نگاشت پیدا میکنند تا بتوان آنها را در این فضای جدید بصورت خطی جدا نمود.
5
تعریف
Support Vector Machines are a system for efficiently training linear learning machines in kernel-induced feature spaces, while respecting the insights of generalisation theory and exploiting optimisation theory.
Cristianini & Shawe-Taylor (2000)
6
مسئله جداسازی خطی: Linear Discrimination
اگر دو دسته وجود داشته باشند که بصورت خطی از هم جداپذیر باشند، بهترین جدا کننده این دو دسته چیست؟
الگوریتم های مختلفی از جمله پرسپترون میتوانند این جداسازی را انجام دهند.
آیا همه این الگوریتمها بخوبی از عهده اینکار بر میآیند؟
7
Intuitions
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
8
Intuitions
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
9
Intuitions
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
10
Intuitions
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
11
A “Good” Separator
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
12
Noise in the Observations
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
13
Ruling Out Some Separators
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
14
Lots of Noise
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
15
Maximizing the Margin
X
X
O
O
O
O
O
O
X
X
X
X
X
X
O
O
16
ضرب داخلی
ضرب داخلی را میتوان معیاری از تشابه دانست
در حالت n بعدی میتوان آنرا بصورت زیر نمایش داد.
17
خط یا ابر صفحه جدا کننده
هدف: پیدا کردن بهترین خط ( ابر صفحه) که دو دسته را از هم جدا کند. در حالت دو بعدی معادله این خط بصورت زیر است:
در حالت n بعدی خواهیم داشت:
18
ایده SVM برای جدا سازی دسته ها
دو صفحه مرزی بسازید :
دو صفحه مرزی موازی با صفحه دسته بندی رسم کرده و آندو را آنقدر از هم دور میکنیم که به داده ها برخورد کنند.
صفحه دسته بندی که بیشترین فاصله را از صفحات مرزی داشته باشد، بهترین جدا کننده خواهد بود.
19
حداکثر حاشیه
بر طبق قضیه ای در تئوری یادگیری اگر مثالهای آموزشی بدرستی دسته بندی شده باشند، از بین جداسازهای خطی، آن جداسازی که حاشیه داده های آموزشی را حداکثر میکند خطای تعمیم را حداقل خواهد کرد.
20
چرا حداکثر حاشیه؟
به نظر میرسد که مطمئن ترین راه باشد.
تئوری هائی برمبنای VC dimension وجود دارد که مفید بودن آنرا اثبات میکند.
بطور تجربی این روش خیلی خوب جواب داده است.
21
بردار پشتیبان
نزدیکترین داده های آموزشی به ابر صفحه های جدا کننده بردار پشتیبان نامیده میشوند
Class 1
Class -1
X2
X1
SV
SV
SV
22
تعمیم و SVM
در صورت استفاده مناسب از SVM این الگوریتم قدرت تعمیم خوبی خواهد داشت:
علیرغم داشتن ابعاد زیاد (high dimensionality) از overfitting پرهیز میکند. این خاصیت ناشی از optimization این الگوریتم است
فشرده سازی اطلاعات:
بجای داده های آموزشی از بردارهای پشتیبان استفاده میکند.
23
حل مسئله برای حالت دو بعدی
نمونه های آموزشی
x n
y {-1, 1}
تابع تصمیم گیری
f(x) = sign(<w,x> + b)
w n
b
ابر صفحه
<w, x> + b = 0
w1x1 + w2x2 … + wnxn + b = 0
میخواهیم مقادیر W, bرابگونه ای پیدا کنیم که:
نمونه های آموزشی را بدقت دسته بندی کند
با این فرض که داده ها بصورت خطی جدا پذیر باشند
حاشیه را حداکثر نماید
24
Linear SVM Mathematically
Let training set {(xi, yi)}i=1..n, xiRd, yi {-1, 1} be separated by a hyperplane with margin ρ. Then for each training example (xi, yi):
For every support vector xs the above inequality is an equality. After rescaling w and b by ρ/2 in the equality, we obtain that distance between each xs and the hyperplane is
Then the margin can be expressed through (rescaled) w and b as:
wTxi + b ≤ – ρ/2 if yi = -1
wTxi + b ≥ ρ/2 if yi = 1
yi(wTxi + b) ≥ ρ/2
25
حل مسئله برای حالت دو بعدی
فاصله خط جداکننده از مبدا برا براست با
فاصله نمونه ای مثل x از خط جدا کننده برابر است با
X2
X1
f(x)=0
f(x)>0
f(x)<0
w
x
بردار w بر هر دو صفحه مثبت ومنفی عمود خواهد بود.
26
تعیین حاشیه بین خطوط جدا کننده
Plus-plane = { x : w . x + b = +1 }
Minus-plane = { x : w . x + b = -1 }
Classify as..
-1 if w . x + b <= -1
+1 if w . x + b >= 1
27
محاسبه پهنای حاشیه
صفحه مثبت و منفی را بصورت زیر در نظر میگیریم:
Plus-plane = { x : w . x + b = +1 }
Minus-plane = { x : w . x + b = -1 }
بردار w بر صفحه مثبت ومنفی عمود خواهد بود.
فرض کنید X- نقطه ای در صفحه منفی بوده و X+ نزدیکترین نقطه در صفحه مثبت به X- باشد.
28
محاسبه پهنای حاشیه
خطی که X- رابه X+ وصل میکند بر هر دو صفحه عمود خواهد بود. لذا فاصله بین دو صفحه مضربی ازW خواهد بود.
در اینصورت خواهیم داشت:
x+= x-+ λ w for some value of λ.
29
محاسبه پهنای حاشیه
میدانیم که:
w . x+ + b = +1
w . x- + b = -1
X+= x-+ λ w
| x+- x-| = M
لذا میتوان M را برحسب Wو b محاسبه کرد.
30
محاسبه پهنای حاشیه
w . x+ + b = +1
w . x- + b = -1
X+= x-+ λ w
| x+- x-| = M
w.( x-+ λ w) + b = +1
w.x-+ λ w.w + b = +1
-1+ λ w.w = +1
λ=2/ w.w
31
محاسبه پهنای حاشیه
32
محدودیت
اگر برای مثال دو بعدی فوق مقدار دسته ها را با 1 و 1- مشخص کنیم داریم:
<w,xi> + b ≥ 1 for y=1
<w,xi> + b £ -1 for y= -1
که میتوان آنرابصورت زیر نوشت
yi (<w,xi> + b) ≥ 1 for all i
33
جمع بندی حل مسئله
در SVM بدنبال حل همزمان معادلات زیر هستیم:
با داشتن مثالهای آموزشی (xi, yi) که i=1,2,…N; yi{+1,-1}
Minimise ||w||2
Subject to : yi (<w,xi> + b) ≥ 1 for all i
Note that ||w||2 = wTw
این یک مسئله quadratic programming با محدودیت هائی بصورت نامعادلات خطی است. روشهای شناخته شده ای برای چنین مسئله هائی بوجود آمده اند.
34
Quadratic Programming
35
Recap of Constrained Optimization
Suppose we want to: minimize f(x) subject to g(x) = 0
A necessary condition for x0 to be a solution:
a: the Lagrange multiplier
For multiple constraints gi(x) = 0, i=1, …, m, we need a Lagrange multiplier ai for each of the constraints
36
Recap of Constrained Optimization
The case for inequality constraint gi(x) £ 0 is similar, except that the Lagrange multiplier ai should be positive
If x0 is a solution to the constrained optimization problem
There must exist ai ≥ 0 for i=1, …, m such that x0 satisfy
The function is also known as the Lagrangrian; we want to set its gradient to 0
37
راه حل معادله
Construct & minimise the Lagrangian
Take derivatives wrt. w and b, equate them to 0
The Lagrange multipliers ai are called ‘dual variables’
Each training point has an associated dual variable.
parameters are expressed as a linear combination of training points
only SVs will have non-zero ai
38
راه حل معادله
a6=1.4
Class 1
Class 2
a1=0.8
a2=0
a3=0
a4=0
a5=0
a7=0
a8=0.6
a9=0
a10=0
39
The Dual Problem
If we substitute to Lagrangian , we have
Note that
This is a function of ai only
40
The Dual Problem
Properties of ai when we introduce the Lagrange multipliers
The result when we differentiate the original Lagrangian w.r.t. b
The new objective function is in terms of ai only
It is known as the dual problem: if we know w, we know all ai; if we know all ai, we know w
The original problem is known as the primal problem
The objective function of the dual problem needs to be maximized!
The dual problem is therefore:
41
The Dual Problem
This is a quadratic programming (QP) problem
A global maximum of ai can always be found
w can be recovered by
42
راه حل معادله
So,
Plug this back into the Lagrangian to obtain the dual formulation
The resulting dual that is solved for by using a QP solver:
The b does not appear in the dual so it is determined separately from the initial constraints
Data enters only in the form of dot products!
43
دسته بندی داده های جدید
پس از آنکه مقادیر (*, b*) با حل معادلات quadratic بر اساس داده های ورودی بدست آمد، میتوان SVM را برای دسته بندی نمونه های جدید بکار برد.
اگر x یک نمونه جدید باشد، دسته بندی آن بصورت زیر مشخص میشود:
sign[f(x, *, b*)], where
Data enters only in the form of dot products!
44
ویژگی های راه حل
The solution of the SVM, i.e. of the quadratic programming problem with linear inequality constraints has the nice property that the data enters only in the form of dot products!
Dot product (notation & memory refreshing): given x=(x1,x2,…xn) and y=(y1,y2,…yn), then the dot product of x and y is xy=(x1y1, x2y2,…, xnyn).
This is nice because it allows us to make SVMs non-linear without complicating the algorithm
45
The Quadratic Programming Problem
Many approaches have been proposed
Loqo, cplex, etc.
Most are “interior-point” methods
Start with an initial solution that can violate the constraints
Improve this solution by optimizing the objective function and/or reducing the amount of constraint violation
For SVM, sequential minimal optimization (SMO) seems to be the most popular
A QP with two variables is trivial to solve
Each iteration of SMO picks a pair of (ai,aj) and solve the QP with these two variables; repeat until convergence
In practice, we can just regard the QP solver as a “black-box” without bothering how it works
46
داده هائی که بصورت خطی جدا پذیر نیستند
یک فرض بسیار قوی در SVM این بود که داده ها بصورت خطی جداپذیر باشند. در حالیکه در عمل در بسیاری مواقع این فرض صحیح نیست.
47
افزودن متغیر های slack
یک راه حل این است که اندکی کوتاه آمده و مقداری خطا در دسته بندی را بپذیریم!
این کار با معرفی متغیر xi انجام میشود که نشانگر تعداد نمونه هائی است که توسط تابع wTx+b غلط ارزیابی میشوند.
48
افزودن متغیر های slack
با معرفی متغیرxi, i=1, 2, …, N, محدودیت های قبلی ساده تر شده و رابطه
yi (<w,xi> + b) ≥1
بصورت زیر تغییر میکند:
yi (<w,xi> + b) ≥1- xi , xi ≥ 0
در حالت ایده آل همه این متغیر ها باید صفر باشند.
49
در اینصورت مسئله بهینه سازی تبدیل میشود به یافتن w به نحوی که معادله زیر مینیمم شود:
که در آن C > 0 میباشد. جمله اضافه شدن سعی دارد تا حد امکان همه متغیرهای slack را کوچک نماید.
50
رابطه دوگان در حالت جدید بصورت زیر خواهد بود.
مقدار مناسب C بر اساس داده های مسئله انتخاب میشود.
find ai that maximizes
subject to
51
Soft Margin Hyperplane
If we minimize wi xi, xi can be computed by
xi are “slack variables” in optimization
Note that xi=0 if there is no error for xi
xi is an upper bound of the number of errors
We want to minimize
C : tradeoff parameter between error and margin
The optimization problem becomes
52
The Optimization Problem
The dual of this new constrained optimization problem is
w is recovered as
This is very similar to the optimization problem in the linear separable case, except that there is an upper bound C on ai now
Once again, a QP solver can be used to find ai
53
مسئله جداسازی غیر خطی : یادگیری در فضای ویژگی
میتوان با نگاشت داده به یک فضای ویژگی آنها را بصورت خطی جداپذیر نمود:
54
تبدل داده به فضای ویژگی
انجام محاسبات در فضای ویژگی میتواند پرهزینه باشد برای اینکه ابعاد بیشتری دارد.
در حالت کلی ابعاد این فضا بی نهایت است.
برای غلبه بر این مشکل از kernel trick استفاده میشود.
f(.)
Feature space
Input space
Note: feature space is of higher dimension than the input space in practice
55
مشکلات فضای ویژگی
کار کردن با فضای ویژگی با ابعاد بالا مشکل است
علاوه بر مسئله بالا رفتن هزینه محاسباتی ممکن است مشکل تعمیم نیز بواسطه curse of dimensionality بوجود آید.
56
نگاشت غیر مستقیم به فضای ویژگی
We will introduce Kernels:
Solve the computational problem of working with many dimensions
Can make it possible to use infinite dimensions
efficiently in time / space
Other advantages, both practical and conceptual
57
کرنل
Transform x (x)
The linear algorithm depends only on xxi, hence transformed algorithm depends only on (x)(xi)
Use kernel function K(xi,xj) such that K(xi,xj)= (x)(xi)
58
Suppose f(.) is given as follows
An inner product in the feature space is
So, if we define the kernel function as follows, there is no need to carry out f(.) explicitly
This use of kernel function to avoid carrying out f(.) explicitly is known as the kernel trick
An Example for f(.) and K(.,.)
59
کرنل های نمونه:
60
مثال: کرنل چند جمله ای
61
Modification Due to Kernel Function
Change all inner products to kernel functions
For training,
Original
With kernel function
62
Modification Due to Kernel Function
For testing, the new data z is classified as class 1 if f³0, and as class 2 if f <0
Original
With kernel function
63
Modularity
Any kernel-based learning algorithm composed of two modules:
A general purpose learning machine
A problem specific kernel function
Any K-B algorithm can be fitted with any kernel
Kernels themselves can be constructed in a modular way
Great for software engineering (and for analysis)
64
ساخت کرنل ها
مجموعه قوانین زیر در مورد کرنل ها صادق است:
If K, K’ are kernels, then:
K+K’ is a kernel
cK is a kernel, if c>0
aK+bK’ is a kernel, for a,b >0
Etc etc etc……
به این ترتیب میتوان کرنل های پیچیده را از روی کرنل های ساده تر ساخت.
65
Example
Suppose we have 5 1D data points
x1=1, x2=2, x3=4, x4=5, x5=6, with 1, 2, 6 as class 1 and 4, 5 as class 2 y1=1, y2=1, y3=-1, y4=-1, y5=1
We use the polynomial kernel of degree 2
K(x,y) = (xy+1)2
C is set to 100
We first find ai (i=1, …, 5) by
66
Example
By using a QP solver, we get
a1=0, a2=2.5, a3=0, a4=7.333, a5=4.833
Note that the constraints are indeed satisfied
The support vectors are {x2=2, x4=5, x5=6}
The discriminant function is
b is recovered by solving f(2)=1 or by f(5)=-1 or by f(6)=1, as x2 and x5 lie on the line and x4 lies on the line
All three give b=9
67
Example
Value of discriminant function
1
2
4
5
6
class 2
class 1
class 1
68
مثالی از کاربرد
تشخیص حروف دست نویس
در اداره پست آمریکا با استفاده از این روش توانسته اند به خطائی در حدود 4% برسند.
69
مراحل استفاده از SVM برای دسته بندی
Prepare the data matrix
Select the kernel function to use
Execute the training algorithm using a QP solver to obtain the i values
Unseen data can be classified using the i values and the support vectors
70
انتخاب تابع کرنل
جدی ترین مسئله در روش SVM انتخاب تابع کرنل است.
روشها و اصول متعددی برای این کار معرفی شده اسـت:
diffusion kernel, Fisher kernel, string kernel, …
و تحقیقاتی نیز برای بدست آوردن ماتریس کرنل از روی داده های موجود در حال انجام است.
در عمل
In practice, a low degree polynomial kernel or RBF kernel with a reasonable width is a good initial try
Note that SVM with RBF kernel is closely related to RBF neural networks, with the centers of the radial basis functions automatically chosen for SVM
71
SVM applications
SVMs were originally proposed by Boser, Guyon and Vapnik in 1992 and gained increasing popularity in late 1990s.
SVMs are currently among the best performers for a number of classification tasks ranging from text to genomic data.
SVMs can be applied to complex data types beyond feature vectors (e.g. graphs, sequences, relational data) by designing kernel functions for such data.
SVM techniques have been extended to a number of tasks such as regression [Vapnik et al. ’97], principal component analysis [Schölkopf et al. ’99], etc.
Most popular optimization algorithms for SVMs use decomposition to hill-climb over a subset of αi’s at a time, e.g. SMO [Platt ’99] and [Joachims ’99]
Tuning SVMs remains a black art: selecting a specific kernel and parameters is usually done in a try-and-see manner.
72
نقاط قوت و ضعف SVM
Strengths
Training is relatively easy
Good generalization in theory and practice
Work well with few training instances
Find globally best model, No local optimal, unlike in neural networks
It scales relatively well to high dimensional data
Tradeoff between classifier complexity and error can be controlled explicitly
Non-traditional data like strings and trees can be used as input to SVM, instead of feature vectors
Weaknesses
Need to choose a “good” kernel function.
73
نتیجه گیری
SVMs find optimal linear separator
They pick the hyperplane that maximises the margin
The optimal hyperplane turns out to be a linear combination of support vectors
The kernel trick makes SVMs non-linear learning algorithms
Transform nonlinear problems to higher dimensional space using kernel functions; then there is more chance that in the transformed space the classes will be linearly separable.
74
سایر جنبه های SVM
How to use SVM for multi-class classification?
One can change the QP formulation to become multi-class
More often, multiple binary classifiers are combined
One can train multiple one-versus-all classifiers, or combine multiple pairwise classifiers “intelligently”
How to interpret the SVM discriminant function value as probability?
By performing logistic regression on the SVM output of a set of data (validation set) that is not used for training
Some SVM software (like libsvm) have these features built-in
75
Multi-class Classification
SVM is basically a two-class classifier
One can change the QP formulation to allow multi-class classification
More commonly, the data set is divided into two parts “intelligently” in different ways and a separate SVM is trained for each way of division
Multi-class classification is done by combining the output of all the SVM classifiers
Majority rule
Error correcting code
Directed acyclic graph
76
نرم افزار
لیستی از نرم افزار های مختلف را میتوانید در آدرس زیر بیابید:
http://www.kernel-machines.org/software.html
برخی نرم افزارها نظیر LIBSVM میتوانند بصورت چند دسته ای کار کنند.
نرم افزار SVMLight در مراجع مختلفی بکار رفته است.
چندین toolbox در Matlab برای SVM معرفی شده اند.
77
مراجع
[1] b.E. Boser et al. A training algorithm for optimal margin classifiers. Proceedings of the fifth annual workshop on computational learning theory 5 144-152, Pittsburgh, 1992.
[2] l. Bottou et al. Comparison of classifier methods: a case study in handwritten digit recognition. Proceedings of the 12th IAPR international conference on pattern recognition, vol. 2, pp. 77-82.
[3] v. Vapnik. The nature of statistical learning theory. 2nd edition, Springer, 1999.