linearly Separable하지 않은 경우엔 어떻게 할건지

차원을 확장하면 좀 더 쉬운 분류가 가능하다!

어떻게 분류해? “large margin”으로 분류하자

Margins

데이터 포인트와 평면사이의 공간을 가장 크게 만들 수 있는 평면을 찾자!!

Find the hyperplane yielding more space between data points and hyperplane

• space: margin (이 공간을 최대화 하자!)

margin은 어떻게 측정하지?

• Functional margin
• Geometric margin

Notation

우리의 데이터가 linearly separable하다고 가정하자.

binary classification 문제 label y & feature x

y 는 2개의 class {-1, 1}을 가짐

x가 양수면 f(x)=1, 음수면 f(x)=-1

Functional Margin

functional margin γ(gamma) = (wx+b)y

Large functional margin은 confident prediction을 의미한다.

γ > 0 이면 correct prediction 을 의미

γ를 키우기 위해서 임의의 수를 곱하면 어떨까? (arbitratily scaling)

γ = (2wx+2b)y

γ값은 커짐 ⇒ 하지만 이런식으로 margin이 커진다고 해서 더 좋은 예측이 되는 것은 아님

그래서 m개의 training sample의 γ에 대해 최솟값을 취함

smallest margin of all data points 모든 데이터에 대해서 functional margin을 구하고 최솟값 택

Geometric Margin

geometric margin γ : Distance from the point A to the hyperplane (wx+b=0)

점에서 평면까지의 거리 공식을 이용

γ =y(wx+b / |w|)

Rescaling은 영향을 미치지 않음 ⇒ 역시 m개의 training sample에 대해 최솟값을 선택한다.

Optimal margin classifier

geometric margin을 이용해서 training sample을 positive와 negative로 분리

가정: 임의의 평면으로 데이터를 positive와 negative로 분리가 가능하다고 가정 즉, linearly separable하다.

SVM에서의 decision rule

f(x) = wx+b ≥ 0, then positive samples

y =1 for positive samples

y= -1 negative samples

따라서, 모든 샘플에 대해 y(wx+b) ≥ 1 이다.

이항하면 y(wx+b)-1 ≥ 0

decision boundary에서 positive&negative side에서 가장 가까이 위치한 점에 2개의 선을 추가

(평면과 가장 가까운 곳에 위치한 두 점)

이 선에서는 margin 식 y(wx+b)-1 =0 이 된다

두 선 사이의 공간을 최대화하자!!

objective function in SVM

단위벡터 이용해서 두 점사이의 거리를 구함 2/||w||

하지만 이 형태가 미분할 수 없음 ⇒ 미분하기 좋게 만드려고 제곱을 취함(square) + minimize하는 문제로 바꿈

⇒ perfectly convex, differentiable objective function

그래서 우리는 objective function을 최소화 하는 게 목적, 제한조건: y(wx+b)≥1

목적 함수가 볼록하면서 이차 함수 형태(convex quadratic), 이 특성 덕분에 최적의 해를 찾기 쉬워지고, 그 결과 optimal margin classifier를 얻을 수 있다는 뜻

그럼 제한조건이 있는 optimization problem은 어떻게 해결할까?

이를 위해서는 Lagrangian duality(primal problem)를 알아야함

Lagrangian duality(primal problem)

constrained optimization problem 해결법

f(w)의 최솟값을 구하고, 제한 조건: g(w)≤0, h(w) = 0

generalized Lagrangian : L(w,α,β) = f(w) + sigma[ α*g(w)] + sigma[β*h(w)]

이때, 알파&베타는 Lagrange multipliers ≥0

만약 조건을 만족하는 w가 있다면, 라그랑지안으로 바꾸고 max를 취하면 결국 f(w)가 됨.

따라서 primal problem을 다시 쓰면 min(max(L((w,α,β))) ← 우리는 결국 최솟값 구해야 하니까

Lagrangian duality(Dual problem)

optimal한 w,α,β* 가 있다면 min과 max의 순서를 바꿔도 동일하다

KKT dual complementary condition

w,α,β*조건

• L(w,α,β*)를 w,β에 대해 미분한 값이 0이 되야함
• αg(w) = 0 KKT dual complementary condition α가 양수면 g(w)=0 이 된다.

다시 우리의 최적화 문제로 돌아와서,

제한조건 g(w) ⇒ y(wx+b)≥1

다시쓰면 g(w) = -y(wx+b)+1 ≤ 0

최적화 문제에 라그랑지안 적용

쉽게 말하면 min(max(L((w,α,β)) == max(min(L((w,α,β)) 이 되는 파라미터를 찾겠다!

primal problem & Dual problem을 적용해서 식을 다시 씀

결론은 Optimization only needs the dot product of the pair of input vectors

Support Vectors

decision boundary에 가장 가까운 포인트

According to KKD, αg(w) = 0

α가 양수이면 KKD를 충족함 **..? g(w) = 0 이기때문에 α*가 양수여도 충족하는거 아닌지?**

두 점선 위의 선은 g(w)=0 이기 때문에 α가 0이 아닌 값을 가질 수 있음

점선이 아닌 다른 곳에 위치한 점들은 전부 α=0이여야함 (g(w)≠0이기 때문)

따라서 Support Vector Machine은 분류할 때 단지 “suport vector”만 고려하면 됨!!

Lagrangian multipliers α

w = sigma[αyx] , α≠0을 만족하는건 support vector밖에 없음

새로운 데이터 z에 대해 f(z) = wz+b = sigma[αy<x.z>] + b

결과가 positive면 +, 그렇지 않으면 -

💡

📌 "최적의 w(가중치)는 제한된 수의 입력 데이터 포인트들의 linear combination이다."

즉, 최적의 가중치 w는 전체 데이터가 아닌, 일부 중요한 입력 데이터 포인트들(support vector)만을 이용해 linear combination으로 표현된다 ⇒ 최종 분류 결정에 중요한 역할을 하는 서포트 벡터만이 최적의 decision boundary를 형성하는 데 기여한다는 것

📌 Lagrange multiplier(α)를 계산할 때, 두 input vector의 내적만 계산하면 된다.

📌 Classification decision을 만들기 위해선, 새로운 샘플 z와 support vector만 비교하면 된다.

• SVM에의해 decision boundary가 어떻게 결정되는가? The optimization pursues maximizing the margin.(두 점선 위에 있는 두 점 사이의 공간) The objective function은 다음과 같다 min ||w||^2/2
  

• support vector위치 찾기, 이 점에서 라그랑지안 Multiplier 알파는 0인지 아닌지 알파는 NOT zero. KKD dual complementary 조건에 따르면 αg(w) = 0 should be hold. support vector에서 g(w) = 0 이므로 (wx+b=1, y=1 이기 때문) 알파는 0이 아닌 값을 가질 수 있다.
  

Kernel

라그랑지안 계산에서 w와 b를 직접 계산할 필요가 없다.

2개의 input vector <xi,xj> 의 내적만 계산하면 된다. ⇒ Kernel trick

Soft margin classifier

완벽하게 선형으로 분리되는 경우는 불가능하기 때문에 일부 misclassified point들을 허용한다.

잘못 분류된 경우

1. negative인데 positive로 분류 (반대도 마찬가지)
2. decision boundary와 가까이 있는데 support vector들이 위치한 점선 안쪽 에 있는 경우

c : Penalty parameter ⇒ 잘못 분류된 경우에 penalty를 주겠다

c가 커지면,

페널티가 커진다 ⇒ margin은 작아진다. (잘못 분류된 사례를 줄이려면 마진은 계속 작아져야함)

높은 페널티: avoid misclassification

Hard margin : a smaller margin hyperplane (굉장히 작은 마진을 갖는것)

Overfitting: c가 커지면 오버피팅 가능성도 커짐

c가 작아지면,

페널티가 작아진다 ⇒ margin은 커진다

아웃라이어(이상치)를 적게 허용하기 때문에 마진이 더 커진다"는 뜻이에요. 여기서 "margin"은 보통 결정 경계와 데이터 포인트 사이의 거리**를 의미해요. 아웃라이어가 줄어들면 모델이 더 안정적이고 일반화 능력이 좋아져, 결정 경계와 주요 데이터 사이의 거리가 더 넓어질 수 있어요.

낮은 페널티: allow some misclassification

Soft margin: a larger margin hyperplane

Underfitting: c가 작아지면 언더피팅 가능성

Overfitting을 피하기 위해선 c를 줄여야 한다!!!

Kernel trick

1차원에서는 결정 경계를 찾는 것이 어렵다 ⇒ 커널함수를 이용해 feature dimension을 증가시킨다

커널함수는 data points를 high-dimensional space로 맵핑해준다.

kernel trick은 어떻게 적용하는가?

1. 두 input vector의 내적 관점에서 알고리즘 작성 <x,z>
2. 커널 함수 적용
3. 커널 계산의 디테일 정의 K(x,z)
4. <x,z> 대신 K<x,z>

x,z에 각각 커널 함수를 적용하게 되면 시간복잡도가 매우 커짐 ⇒ 너무 복잡해~!

커널함수를 적용하기 전에 내적을 먼저하자!!

We don’t even need to map each point into higher-dimension
all we need is the inner product of two points

Polynomial Kernel

K(x,z) = (xz + c)^d

c: Coefficient of polinomial

d: Degree of polynomial

c=0 이면 어떨까?

커널이 차원을 더해주지 않고 단순히 입력을 리스케일링하는 결과

모든 입력값에 대해 동일한 상수로 결과를 리스케일링하는 역할

입력 공간의 차원을 확장하는 원래의 목적을 달성하지 못하고 단순히 값만 커지거나 작아질 뿐

c,d는 어떻게 결정할까?

교차 검증 을 통해 여러값을 시도하여, 최종적으로 가장 좋은 성능을 내는 값(더 분류를 잘하는 값)

cross validation

Gaussian Kernel (RBF)

K(x,z) = exp (-γ ||x-z||^2/2σ^2)

커널이 점들을 무한대의 차원에 맵핑시킴

x와z 둘이 가까울 수록 영향을 많이 줌

멀리 떨어져있는 점일수록 (x-z)^2값이 커지니까 커널함수의 결과값은 0에 가까워진다. (exponential)

감마가 크면 커널의 값이 줄어듬

γ는 어떻게 결정할까? 역시나 실험적으로 찾음

차원을 무한대로 확장시켜도 역시나 두 data point를 내적한 값

커널의 종류

• Linear kernel
  K(x,z) = x_tz
• Polynomial kernel
• Gaussian kernel or Radial Basis Function(RBF)

Mercer’s theorem

이 조건을 만족하면 어떤 임의의 함수도 커널 함수가 될 수 있다.

any of d points, the corresponding kernel matrix K ≥ 0 and symmetric

커널함수를 적용한 커널metrix가 ≥ 0 값을 가짐, 즉 diag(K) ≥ 0

• 왜 SVM에 kernel trick을 적용할까?
  현재 데이터 공간에서 separable한 boundary를 찾을 수 없을 때, 주어진 데이터를 higher-dimensional space에서 적절하게 분리하는 hyperplane을 찾기 위해 커널을 적용한다.
• 커널 트릭을 적용하기 위한 중요한 조건이 뭘까?
  The optimization problem should be addressed in the formula containing the inner dot product of two input vectors. That’s required, otherwise applying kernel function should be computationally very expensive.
• polynomial kernel에서 c와 d를 어떻게 찾을까?
  실험을 통해서. 랜덤하게 training & testing 로 multiple pairs를 만든 뒤 multiple subsets 이용 ⇒ By using each pair of sets, explore various combinations of c and d and pick c and d with highest classification accuracy.
• 커널함수를 이용할 때, 모든 데이터 포인트를 계산해야 하는가?
  No. All we need to do is compute the inner product of two input vectors regardless of linear, polynomial or non-linear kernels.

---