[OpenCV] 08-2-1. Understanding SVM

< 8-2-1. Understanding SVM >

이번 장에서는

• SVM의 직관적인 이해를 도울 것이다!

Theory

Linearly Separable Data

빨강 / 파랑 두 가지 타입의 데이터가 존재하는 아래 이미지를 보자. kNN에서는 테스트 데이터에 대해, 학습 데이터들과의 거리를 측정하고 가장 최솟값의 거리를 갖는 것을 택했다. 이는 모든 거리들을 측정하는데 많은 시간이 들고 모든 학습 샘플들을 저장하는데 메모리도 많이 차지한다. 하지만 아래 이미지 처럼 데이터가 주어졌다면 그럴 필요가 있을까??

한 번 다르게 생각을 해보자. 데이터들을 두 영역으로 나누는 f(x)=ax1+bx2+c 선을 찾아보자. 그리고 새로운 테스트 데이터 X를 받으면, f(x)에 대입시키면 된다. f(X)>0일 경우, 파란 그룹에 속하고, 반대의 경우 빨간 그룹에 속하게 된다. 이러한 선을 Decision Boundary라고 부른다. 이는 매우 간단하고 메모리-효율적인 방법이다. 직선으로 두 가지로 나눌수 있는 데이터를 Linear Separable이라고 부른다.

그래서 위의 이미지에서, 가능한 선들을 많이 볼 수 있다. 그 중에서 어느 선을 고를까?? 직관적으로 보면 모든 점으로 부터 최대한 멀리 떨어져있는 선을 골라야한다. 왜 그럴까? 왜냐하면 입력 데이터에 노이즈가 있을 수 있기 때문이다. 이러한 데이터는 분류 정확도에 영향을 미치지 않아야 한다. 그래서 노이즈에 대응하기 위해 멀리 있는 선을 골라서 면역을 키워주는 것이다. 그래서 SVM이 하는 것은 학습 샘플들에 대해 최소 거리가 가장 큰 직선(또는 초평면)을 찾는 것이다. 아래 굵은 선을 보자.

Decision Boundary를 찾기 위해서, 학습 데이터가 필요하다. 전부가 필요할까? 아니다. 반대 편에서 가까운 하나만 골라도 충분하다.(경계선에서 선택) 이미지를 보면, 파란색로 칠해진 원 하나와 빨간색으로 칠해진 사각형 두 개를 볼 수 있다. 이들을 Support Vectors라고 부르고 그들을 가로지르는 선을 Support Planes라고 부른다. 그들은 decision boundary를 찾는데에 적합하다. 모든 데이터에 대해 생각할 필요가 없다. 이는 데이터 감소에 도움을 준다.

먼저 데이터를 대표할 수 있는 두 개의 초평면이 도출되었다. 예를 들어서, 파란 데이터는 wTx+b0>1로 표현되고, 빨간 데이터는 wTx+b0<−1로 표현되는데, w는 weight vector(w=[w1,w2,...,wn])이고, x는 feature vector (x=[x1,x2,...,xn])이다. b0은 bias(편향)이다. Weight vector는 decision boundary의 방향을 정하고, bias는 위치는 정한다. 이제 decision boundary는 초평면 가운데 중앙에 놓이게 되어서, wTx+b0=0으로 표현된다. support vector로 부터 decision boundary까지의 이 최소거리는 다음 식으로 구해진다. distancesupport vectors=1||w||. Margin은 이 거리를 두 배한 값이 되고, 우리는 이 마진을 최대화해야한다. 즉, 새로운 함수인 L(w,b0)을 아래의 제약이 포함된 상태에서 최소화하여야 한다.

minw,b0L(w,b0)=12||w||2subject to ti(wTx+b0)≥1 ∀i

ti는 각 클래스의 라벨이고 ti∈[−1,1]이다.

Non-Linearly Separable Data

어떤 데이터들은 직선을 이용하여 둘로 나눌 수 없을 수 있다. 예를 들어서, 1차원 공간에서 ‘X’는 -3과 3에 위치하고 ‘O’는 -1과 1에 위치할 경우이다. 이는 명확하게 선형으로 분리할 수 없다. 하지만 다른 방법으로 해결할 수 있다. 만약 f(x)=x2에 매핑하여, ‘X’를 9, ‘O’를 1에 놓는다면 선형으로 분리가능하다.

반면에 이 1차원 공간을 2차원 공간으로 변환할 수 있다. f(x)=(x,x2) 함수에 데이터를 매핑한다. 그러면 ‘X’는 (-3,9), (3,9)가 되고, ‘O’는 (-1,1),(1,1)이 된다. 그러면 선형으로 분리가 가능해진다! 요약하자면, 낮은 차원 공간에서 비선형 분리가 가능한 데이터가 고차원 공간에서는 선형 분리가 가능해질 가능성이 크다.

일반적으로, 선형 분리가 가능한시 확인하기 위해 d-차원 공간을 D-차원 공간(D>d)으로 점들을 매핑하는 것은 가능하다. 저차원 공간에서 연산을 수행함으로써, 고차원 공간(커널)에서 점곱(dot product) 연산하는데 도움이 되는 아이디어가 있다. 아래의 예를 보는게 빠르다…!

2차원 공간에서 2개의 점 p=(p1,p2)와 q=(q1,q2)을 생각해보자. ϕ를 2차원 점을 3차원 공간으로 매핑해주는 매핑 함수라고 생각해보자.

ϕ(p)=(p21,p22,2‾‾√p1p2)ϕ(q)=(q21,q22,2‾‾√q1q2)

두 점을 점곱(dot product)하지 않는 커널 함수 K(p,q)를 정의해보자.

K(p,q)=ϕ(p).ϕ(q)=ϕ(p)T,ϕ(q)=(p21,p22,2‾‾√p1p2).(q21,q22,2‾‾√q1q2)=p21q21+p22q22+2p1q1p2q2=(p1q1+p2q2)2ϕ(p).ϕ(q)=(p.q)2

3차원 공간에서의 내적(점곱)은 2차원 공간에서 내적을 제곱함으로써 얻을 수 있다. 이는 더 높은 차원 공간에서도 적용될 수 있다. 그래서 저차원으로 부터 고차원 특성들을 계산할 수 있다. 한 번 더 계산하면 더 높은 차원 공간을 얻게 된다.

이 개념들에 추가적으로, 잘못된 분류에 대한 문제가 발생한다. 즉, 최대 마진을 가지는 decision boundary를 찾는 것 만으로는 부족하다는 것이다. 잘못 분류된 에러의 문제 또한 생각할 필요가 있다. 때때로, 마진이 작지만 오분류가 줄어드는 decision boundary를 찾을 수 있다. 최대한의 마진을 가진 decision boundary를 찾도록 해야하지만, 오분류도 덜 발생시켜야한다. 식이 다음과 같아진다.

min||w||2+C(distance of misclassified samples to their correct regions)

아래의 이미지는 이 개념을 보여준다. 학습 데이터의 각 샘플에 대해 새로운 파라미터 ξi가 정의된다. 이 파라미터는 학습 샘플이 그들의 decision region과 일치하기까지의 거리를 말한다. 오분류 되지 않은 샘플이라면, 대응하는 support planes에 놓일 것이고, 거리는 0이 될 것이다.

(ξ1은 파란점 ~ 원래 영역까지의 거리 차이를 보여주는 것이다. 각 색선위의 점들은 제대로 분류되어서 선 위에 존재하여 거리가 0이 되는 것이다.)

그래서 새로운 최적화 식은 다음과 같다 :

minw,b0L(w,b0)=||w||2+C∑iξi subject to yi(wTxi+b0)≥1−ξi and ξi≥0 ∀i

파라미터 C는 어떻게 선택되어야 할까? 이는 학습 데이터들이 어떻게 분포되어있는지에 대해 의거하여 대답할 수 있는 문제임이 분명하다. 비록 일반적인 답은 없지만, 다음의 규칙을 따르는 것이 유용하긴 하다.

• 높은 값의 C는 오분류 에러를 적게 해주지만 마진은 작아진다. 오분류 에러의 비용이 큰 경우를 생각해보자. 그럴 경우에는 분류를 정확히 하는 것이 중요하기에 이 방법이 좋다.
• 작은 값의 C는 큰 마진을 갖게하고 많은 분류 에러를 일으킨다. 이 경우에서는 비용을 생각하지 않고 큰 마진을 가지는 초평면을 찾는데에 집중하는 것이다.