Soft margin classifier

앞에서 봤던 Hard margin SVM은 data들에 대해 linear한 decision boundary를 찾을 수 있는 경우에 사용가능한 방법이었다.

하지만 현실에선 대부분 linear한 decision boundary 찾기 힘든 non-linear한 case이다.

-> 이때 사용하는 게 Soft margin classifier ( Soft margin SVM)

 

Soft margin classifier

-> perfectly linearly separable case가 불가능하므로 잘못 classification 된 point들(outlier)도 허용하겠다 !!

  -> outlier들이 margin 안에 어느정도 포함되도록 너그럽게 기준 잡음

 

- c가 크면 outlier를 더 많이 고려함. outlier까지 잘 classfication하는 방향으로 decision boundary가 형성되어 margin이 작아질 것

- c가 작아지면 outlier를 조금 고려함. penalty term을 많이 고려하지 않겠다

 

Q) Against overfitting, how we adjust c?

A) outlier들을 좀 더 허용해야 한다. 따라서 c를 줄여야한다

 

Kernel이란?

고차원 mapping과 내적 두 가지를 한번에 하고 싶어함

 

Kernel trick이란?

-> 등장배경 : 현재 data space에서 separable boundary를 찾지 못하기 때문에 이를 kernel을 이용하여 좀 더 높은 차원에 투영시켜보면 decision boundary 찾기에 용이해지지 않을까라는 생각에서 나왔다

-> kernel trick은 non-linear situation에서 data를 더 높은 차원으로 투영시키기 위해 사용 (더 높은 차원으로 점을 투영함으로써 separable hyperplane을 찾게 될 수도 있어서!)

-  kernel function : 점들을 고차원으로 투영시키는 것에 사용한 함수

- kernel trick 적용가능한 조건 

   -> optimization problem should be addressed in formula containing the inner product of two input vectors.

       -> 이러지 않으면 계산양이 너무 많아져 문제 발생해서

 

How to apply kernel trick?

1. kernel을 적용하기 위해선 두 input vector를 inner product한 형태로 표현해야한다(<x,z>형태). kernel trick 적용조건이다.

2. kernel function 적용

3. kernel computation한다. (각각을kernel함수 취한 후 곱한 형태이다)

4. <x,z>를 K(x,z)로 replace한다. (두 input vector를 내적한 형태를 kernel함수 적용한 으로 바꿔주기)

 

 

예시를 통해 위의 방식을 이해해보자

우선 첫 방식이다. 각각의 input을 kernel 적용시킨 후 이 둘을 곱해 계산하는 방식이다.

-> 시간복잡도가 O(n**2)이 되어 복잡하다.

좀 더 간단한 방식없나?

이 방식은 위와 달리 kernel함수를 취한 "후" product 취하는 것이 아니라 input끼리 내적을 먼저 하는 방식이다!

-> 이때 각각의 input이 n차원이기에 시간 복잡도는O(n)이 되고 dimension이 아무리 커져도 input끼리 내적 취하는 것이기에 complexity가 O(n)으로 linear 하다.

 

어느 함수든 Merer's theorem만 만족하면 커널함수가 될 수 있다 !!

이때 Mercer's theorem이란?

-> 커널함수를 적용했을 때 하나의 kernel matrix가 나올거고 이 kernel matrix가 symmetric 해야하고 대각원소가 전부 0보다 크거나 같아야 한다.

 

 

이제부터 가장 많이 사용되는 커널함수에 대해 알아보자

 

1. Polynomial Kernel

-> x와z에 대해서만 있었는데 더 높은 차원에서 inner product한 형태로 도출되었음을 볼 수있다.

-> 우리는 각각의 input 값들을 polynomial function에 투영한 값을 inner prodect하는 게 필요한 게 아니라 두 input을 inner product한 값만 알면 더 높은 차원에서 투영했을 때의 inner product 한 값을 바로 구할 수 있어 유용하다.

Q) if c=0?

-> x**2와 z**2를 내적한 걸로 바뀜. 이는 고차원으로 투영시킨 게 아니라 original 점들을 더 멀리떨어뜨린 점으로 이동한 형태

Q) c와 d는 어떻게 결정하나?

-> 여러번의 실험을 반복해 다양한 c,d 해본 후 classification 결과가 가장 좋은 c,d 선택한다. (highest classification accuracy)

 

 

2. Gaussian Kernel (RBF)

non linear한상황을 더 잘 handle 할 수 있는 커널함수.

단순히 2,3차원이 아니라 무한한 dimension에 투영시켜 거기서의 inner product를 계산할 수 있다

가우시안 커널을 사용해 두 점의 관계가 어떤지 보면 r값이 커짌록 inner product 값이 줄어들고 있음을 알 수 있다.

또한 서로 많이 떨어진 점들을 가우시안 커널 사용하면 결과값이 거의 0임을 알 수 있다.

-> 이를 통해 near neighbor일수록 impact가 커짐을 알 수 있다.

 

 

 

(||x-z||**2/2gamma**2)의 impact를 조절하기 위한 control parameter 감마는 어떻게 결정?

-> 얘도 마찬가지로 실험적으로 분류의 결과를 가장 잘 가져오는 방향으로 감마를 선택하게 된다.

 

3. Linear kernel

: 자기자신을 넣는 경우 ( 맨 앞에서 다룸 )

 

Kernel function K를 사용할 때 우리는 모든 data points를 K 이용해서 계산할 필요 없다!

-> 우리는 그냥 두 개의 input vector를 inner product 한 값을 계산하면 된다

 

Kernel은 SVM뿐만 아니라 다양한 머신러닝 알고리즘에서 다양한 목적으로 사용된다.

 

Q) How to choose Kernel for SVM?

-> 무조건적인 규칙은 없고 dataset에 매우 의존적이다.

case 1. No prior knowledge on data

  -> go with Gaussian (RBF) kernel

case 2. data points are linearly separable

  -> go with linear kernel

case 3. if you have some idea on decision boundary and it has to be smooth( 데이터 패턴을 과도하게 복잡하게 만들지 않고 적절하게 일반화될 수 있어야 한다)

  -> go with Gaussian (RBF) kernel

-> 직접 cross-validation 이용해 실험해보며 어떤 거 사용할지 정하기