Machine learning Support vector Machine case study which implies

Machine learning

2. Lesson 6
Support vector machine (SVM)

3. Support vector machine

4. Support vector machine

5. Support vector machine

6. Support vector machine

7. Support vector machine –Linear or Non-linear
Linear SVM
Non-Linear SVM

8. Non-Linear to Linear

9. Linear Support vector machine

10. Linear Support vector machine

11. Linear Support vector machine
????????????=??????
??????
??????+??????
0=0
For all the points on the hyper plane, g(x) = 0

12. Linear Support vector machine
????????????=??????
??????
??????+??????
0>0
For all the points above the hyper plane, g(x) > 0

13. Linear Support vector machine
????????????=??????
??????
??????+??????
0<0
For all the points below the hyper plane, g(x) < 0

14. Linear Support vector machine
????????????=??????
??????
??????+??????
0=0
????????????=??????
??????
??????+??????
0<0
????????????=??????
??????
??????+??????
0>0
We choose the hyperplane that has
the maximum separating margin

15. What is Separating Margin?
H is the separating hyperplane
H
+
is the plane parallel to H and passing through the
nearest +vepoints to H
H
-
is the plane parallel to H and passing through the
nearest -vepoints to H
Separating margin is the distance between H
+
and H
-
We choose H that has the maximum margin.

16. Finding Separating Hyperplane with maximum Margin?
????????????=??????
??????
??????+??????
0=0

17. Finding Separating Hyperplane with maximum Margin?
Let us take two points x
1and x
2lying on g(x)
????????????=??????
??????
??????+??????
0=0
??????(&#3627408485;
1)=??????(&#3627408485;
2)=0

18. Finding Separating Hyperplane with maximum Margin?
Let us take two points x
1and x
2lying on g(x)
????????????=??????
??????
??????+??????
0=0
??????(&#3627408485;
1)=??????(&#3627408485;
2)=0
⇒??????
??????
??????
1+??????
0=??????
??????
??????
1+??????
0
⇒??????
??????
??????
1−??????
1=0

19. Finding Separating Hyperplane with maximum Margin?
Let us take two points x
1and x
2lying on g(x)
????????????=??????
??????
??????+??????
0=0
??????(&#3627408485;
1)=??????(&#3627408485;
2)=0
⇒??????
??????
??????
1+??????
0=??????
??????
??????
1+??????
0
⇒??????
??????
??????
1−??????
1=0
It means ??????is orthogonal (90
o
/perpendicular) the vector (x
1-x
2).
It means ??????is orthogonal (90
o
/perpendicular) to g(x).

20. Finding Separating Hyperplane with maximum Margin?
Let x be a point in space.
Let rbe the distance of the point xfrom the hyperplane g(x),
and x
pbe the corresponding projection point of xon g(x).
Now, vector ??????can be defined by the sum of the vector ??????
??????and vector ??????.
??????=??????
??????+??????
⇒??????=??????
??????+??????
??????
??????

21. Finding Separating Hyperplane with maximum Margin?
Let x be a point in space.
Let rbe the distance of the point xfrom the hyperplane g(x),
and x
pbe the corresponding projection point of xon g(x).
Now, vector ??????can be defined by the sum of the vector ??????
??????and vector ??????.
??????=??????
??????+??????
⇒??????=??????
??????+??????
??????
??????
If you substitute ??????in g(??????).
⇒????????????=??????
??????
??????
??????+??????
??????
??????
??????
??????
+??????
&#3627409358;
⇒????????????=??????
??????
??????
??????+??????
&#3627409358;+??????
??????
??????
??????
??????
⇒????????????=??????
??????
??????
??????
??????
⇒??????=
??????(??????)
??????

22. Finding Separating Hyperplane with maximum Margin?
Distance of ??????
??????from g(x)=0 is
⇒??????
&#3627409358;=
??????
??????
&#3627409358;+??????
0
??????
??????=
??????(??????)
??????
??????=
??????(??????)
??????
So, the distance of origin from g(x)=0 is
⇒??????
&#3627409358;=
??????
0
??????

23. Finding Separating Hyperplane with maximum Margin?
What is the Margin between H+ and H-?

24. Finding Separating Hyperplane with maximum Margin?
To define the expression for H+ and H-, let us make the
following assumptions.
Given a datapoint <??????
??????,&#3627408486;
??????> where &#3627408486;
????????????{+????????????,−????????????}is the class
label of ??????
??????,
•let us replace –veby +1, and –veby -1.

25. Finding Separating Hyperplane with maximum Margin?
??????
??????
??????
??????+??????
&#3627409358;≥1,∀&#3627408486;
??????=+1
To define the expression for H+ and H-, let us make the
following assumptions.
Given a datapoint <??????
??????,&#3627408486;
??????> where &#3627408486;
????????????{+????????????,−????????????}is the class
label of ??????
??????,
•Let us replace –veby +1, and –veby -1.
•Now, each data point will satisfy the following
??????
??????
??????
??????+??????
&#3627409358;≤−1,∀&#3627408486;
??????=−1

26. Finding Separating Hyperplane with maximum Margin?
??????
??????
??????
??????+??????
&#3627409358;≥1,∀&#3627408486;
??????=+1
To define the expression for H+ and H-, let us make the
following assumptions.
Given a datapoint <??????
??????,&#3627408486;
??????> where &#3627408486;
????????????{+????????????,−????????????}is the class
label of ??????
??????,
•let us replace –veby +1, and –veby -1.
•Now, each data point will satisfy the following
??????
??????
??????
??????+??????
&#3627409358;≤−1,∀&#3627408486;
??????=−1
The above two expression can be merged to form a single expression
&#3627408486;
??????(??????
??????
??????
??????+??????
&#3627409358;)≥1,∀??????
??????

27. Finding Separating Hyperplane with maximum Margin?
??????
??????
??????
??????+??????
&#3627409358;≥1,∀&#3627408486;
??????=+1
To define the expression for H+ and H-, let us make the
following assumptions.
Given a datapoint <??????
??????,&#3627408486;
??????> where &#3627408486;
????????????{+????????????,−????????????}is the class
label of ??????
??????,
•let us replace –veby +1, and –veby -1.
•Now, each data point will satisfy the following
??????
??????
??????
??????+??????
&#3627409358;≤−1,∀&#3627408486;
??????=−1
The above two expression can be merged to form a single expression
&#3627408486;
??????(??????
??????
??????
??????+??????
&#3627409358;)≥1,∀??????
??????
&#3627408486;
??????(??????
??????
??????
??????+??????
&#3627409358;)−1≥0,∀??????
??????

28. Finding Separating Hyperplane with maximum Margin?
????????????=??????
??????
??????+??????
&#3627409358;=1
????????????=??????
??????
??????+??????
&#3627409358;=−1
????????????=??????
??????
??????+??????
&#3627409358;=0
H+:
H-:
H:

29. Finding Separating Hyperplane with maximum Margin?
????????????=??????
??????
??????+??????
&#3627409358;=1
????????????=??????
??????
??????+??????
&#3627409358;=−1
????????????=??????
??????
??????+??????
&#3627409358;=0
H+:
H-:
H:
Margin=??????
??????
+−??????
??????
−
=
??????
0−1
??????
−
??????
0+1
??????
=
??????
0−1−??????
0−1
??????
⇒????????????????????????????????????=
−2
??????

30. Finding Separating Hyperplane with maximum Margin?
????????????=??????
??????
??????+??????
&#3627409358;=1
????????????=??????
??????
??????+??????
&#3627409358;=−1
????????????=??????
??????
??????+??????
&#3627409358;=0
H+:
H-:
H:
Margin=??????
??????
+−??????
??????
−
=
??????
0−1
??????
−
??????
0+1
??????
=
??????
0−1−??????
0−1
??????
⇒????????????????????????????????????=
−2
??????
As we are interested in the absolute value, we consider the margin as
2
??????

31. Finding Separating Hyperplane with maximum Margin?
????????????????????????????????????=
2
??????
⇒????????????????????????????????????=
1
??????
2
Task is to find the hyperplane (g(x)=0) that maximizes
the margin
2
??????

32. Finding Separating Hyperplane with maximum Margin?
????????????????????????????????????=
2
??????
⇒????????????????????????????????????=
1
??????
2
Task is to find the hyperplane (g(x)=0) that maximizes
the margin
2
??????
Maximizing
2
??????
is equivalent to minimizing
??????
&#3627409360;
Minimizing
??????
&#3627409360;
is equivalent to minimizing
??????
??????
??????
&#3627409360;

33. Finding Separating Hyperplane with maximum Margin?
Minimizeobjective function
??????
??????
??????
&#3627409360;
Subject to the constraint
&#3627408486;
??????(??????
??????
??????
??????+??????
&#3627409358;)≥1,∀??????
??????
Now, we need to solve the following optimization

34. Finding Separating Hyperplane with maximum Margin?
Objective function is to minimize
??????
??????
??????
&#3627409360;
Subject to
&#3627408486;
??????(??????
??????
??????
??????+??????
&#3627409358;)≥1,∀??????
??????
??????
??????=
??????
??????
??????
&#3627409360;
−෍
??????=&#3627409359;
??????
λ
??????&#3627408486;
??????(??????
??????
??????
??????+??????
&#3627409358;)−1
where λ
??????areLagrange multipliers
To find the parameters ??????and where ??????
0, solve
the following optimization function

35. What are the support vectors?
??????
??????=
??????
??????
??????
&#3627409360;
−෍
??????=&#3627409359;
??????
λ
??????&#3627408486;
??????(??????
??????
??????
??????+??????
&#3627409358;)−1
[
In order to find the parameters, we need to solve this objective function.
]

36. Summary
•What is separating hyperplane?
•How to define separating hyperplane?
•What are Support Vector Machine?
•How to classify a new example using SVM