Linear SVM

1. Decision Boundary with Margin

1) Decision Boundary

*Decision boundary line: t(w)*x + b = 0

-위 경계선의 위: Positive case

-위 경계선의 아래: Negative case

 

2) How to Calculate the Margin?

*support vector을 만드는 점을 x라 한다면, f(x) = t(w)*x + b = a (a > 0)

x와 결정경계 사이의 거리를 r이라 하면, r = f(x) / ||w||

-> Margin은 양쪽(음의 방향, 양의 방향)에 존재

전체 Margin M = 2r = 2a / ||w||

-> a로 나누면 M = 2 / ||w|| 가 Margin의 길이가 되며, 이를 최대화하는 결정 경계를 찾아야 함

 

∴모든 점들에 대해 (t(w)*xi + bi)yi >= 1 for i = 1, 2, ..., n

조건을 만족한다는 가정 하에, t(w)*w*0.5를 최소화하는 w와 b를 찾는 것

 

 

2. Soft Margin vs. Hard Margin

1) Soft Margin

일부의 에러(오류)를 허용하는 것

yi(t(w)*xi + b) >= 1 + ei for i = 1, 2, ..., n

(ei: 허용되는 최대 에러, 오류값)

-Finding a line boundary which maximizes the margin and minimizes the error

 

*Error Function

-C가 무한대일 때

-> error 허용 X -> Narrow margin

-> Equivalent to hard margin SVM
-> Over-fitting

 

-C=0일 떼

-> Maximum allowance for error -> Maximum margin

-> Over-generalization