7-1 Large Margin Classification

지도학습에서 자주 사용하는 알고리즘 중 하나인 SVM에 대해 알아본다.

SVM에 대해 알아보기 전 익숙한 로지스틱 회귀를 다시 보자.

로지스틱 회귀에서 가설 h(x)의 정의는 시그모이드 함수를 사용하였다. 만약 y=1인 data가 있을 때 정확히 예측하고 싶다면 h(x)의 값이 1에 가까워야 한다. 다시 말해z가 0보다 매우 클 수록 1에 가까워지게 된다. 반대로 y=0인 데이터가 있을 때는 h(x) 값이 0에 가까워지길 원한다. 따라서 z값이 매우 매우 작은 값이 될 수록 좋다.

로지스틱 회귀의 cost 값은 다음과 같다. Y=1일 때 z값은 매우 클 수록 좋다고 했다. 그 이유는 z가 크면 클 수록 아래에 있는 cost 값이 점점 줄어들기 때문이다.

이제 cost function을 조금 수정하여 직선형태로 바꿔보자. (SVM에서 쉽게 사용하기 위해 조금 수정하는 것이다.)

y=0인 경우도 똑같이 두개의 직선으로 cost function을 수정한다. 다른 함수긴 하지만 로지스틱 회귀에서 사용하는 cost function과 매우 유사하다.

이렇게 만든 함수를 cost_1(z), cost_0(z)로 정의하자 (y=1 or y=0인 경우로 나눈 것)

앞서 정의한 csot_1(z)와 cost_0(z)는 로지스틱 회귀 cost function의 해당 term에 대응된다.

이제 SVM에서 최적화된 파라미터를 찾기 위한 cost function은 다음과 같이 정의할 수 있다.

여기서 1/m은 지워도 된다. 왜냐하면 이건 그냥 상수 값이고 어차피 우리가 하고자 하는 건 cost 값을 최소화하는 θ를 찾는 것이다. 따라서 1/m은 지워도 상관 없다.( U-5)^2 +1이 최소값을 갖는 u는 5이다. 이 함수에 상수 10을 곱한다 할지라도 최소값이 되는 u는 5이다. 따라서 상수인 1/m은 지워도 우리가 찾고자 하는 파라미터 θ는 변하지 않는다.

로지스틱 회귀의 cost function을 cost term과 regularization term의 합으로 생각하고 cost term을 A, regularization term을 람다B로 볼 수 있다.

여기서 람다는 A와 B를 trade off하기 위한 파라미터였다. SVM에서는 람다가 trade off를 하기 위한 파라미터가 아니라 다른 파라미터를 사용한다. 이 파라미터를 C라고 하면 CA + B가 되고 우리가 하고자 하는 것은 CA+B를 최소화하는 파라미터 θ를 찾는 것이다. C가 매우 작은 값이라면 B가 A보다 더 큰 값을 가지게 된다.

(그냥 간단하게 로지스틱 회귀에선 A+람다*B를 썻지만 SVM에서는 C*A + B를 쓴다고 생각)

 

결과적으로 SVM에서 사용하고자 하는 cost function 이렇게 정의된다.

로지스틱 회귀와는 다르게 SVM에서는 h(x)가 클래스에 대한 확률 값이 아니라 z가 0이상인지 아닌지에 따라 그냥 1 or 0이다.

SVM이 Large margin Classifier로 불리는 이유에 대해 알아본다.

SVM의 cost function은 다음과 같다.

Binary classification에서 y=1이면, z가 1이상이면 되고 y=0이면 z가 -1이하이면 된다. 로지스틱 회귀와 달리 prediction되는 값이 z가 +1, -1을 기준으로 달라지게 된다.

SVM cost function에서 붙어 있는 C는 regularization 역할을 하는 파라미터이다. 만약 C가 아주 큰 값이라면 cost term의 값이 그만큼 커질 수 있다. 이런 경우 cost_1(z) 혹은 cost_0(z)가 0이 되면 된다. Cost(z)가 0이된다는 것은 y=1일 때 z>=1, y=0일 때 z<=-1라는 것을 의미한다.

SVM cost function에서 붙어 있는 C는 regularization 역할을 하는 파라미터이다. 만약 C가 아주 큰 값이라면 cost term의 값이 그만큼 커질 수 있다. 이런 경우 cost_1(z) 혹은 cost_0(z)가 0이 되면 된다. Cost(z)가 0이된다는 것은 y=1일 때 z>=1, y=0일 때 z<=-1라는 것을 의미한다.

문제를 최적화 관점에서 다시 생각해보면 그냥 cost term이 0이면 되고 이게 우리가 원하는 것이다. 그래서 cost term이 0이라면 결국 우리의 decision boundary는 간단하게 뒤에 남은 term이 된다.

다음과 같은 positive, negative sample을 분류해야 할 때, 분홍색 or 초록색 decision boundary로 데이터를 분류할 수 있다. 그러나 SVM이 그리는 decision boundary는 검은색 직선이 된다. 이러한 boundary는 큰 distance를 가지고 있다고 하는데 distance라는 의미는 여기서 margin을 말한다. 즉 검은색 decision boundary가 분홍색, 초록색 boundary보다 sample과의 margin(거리)가 더 크기 때문이다. 이러한 이유로 SVM을 Large margin classifier라고 한다.

SVM으로 다음과 같은 decision boundary를 그렸다고 하자

이제 positive sample들 사이에 negative sample이 들어왔다고 하자. 그럼 이걸 제대로 분류하기 위해 SVM은 분홍색 decision boundary를 그릴 것이다.

만약 저렇게 들어온 데이터가 outlier라면 저런 outlier하나에 민감하게 반응해서 검은색 boundary에서 분홍색 boundary로 바꾸는 것은 결코 좋은 선택이 아니다. 만약 C가 매우 큰 값이었다면 분홍색 boundary처럼 바뀔 것이다. 왜냐하면 C가 엄청 크면 cost term도 엄청나게 커지게 되고, 결국 outlier같은 것에 너무 민감하게 반응하기 때문이다.

 

그러나 C가 적당히 작은 값이라면 outlier같은 data가 존재하더라도 검은색 decision boundary를 유지할 것이다.

SVM의 수학적 개념에 대해 알아본다.

벡터 u, v가 존재할 때, 두 벡터의 내적 u'v란 무엇인가?

벡터 v를 벡터 u에 projection시켜 p라는 length 값을 얻는다. 그리고 p와 u의 길이를 곱한 것이 두 벡터의 내적을 의미한다.

만약 두 벡터 v, u 사이의 각도가 90도가 넘으면 p는 음수가 된다.

간단하게 설명하기 위해 𝜽0는 0으로 두고 2개의 feature만 존재한다고 해보자.

그럼 SVM의 decision boundary는 간단하게 1/2(𝜽1^2, 𝜽2^2)이 된다. 그리고 이걸 루트를 씌워서 생각해보면 이전에 벡터의 길이를 구하기 위한 식과 같아지므로 벡터 𝜽의 길이로 볼 수 있다. 따라서 decision boundary는 1/2 ||𝜽||^2으로 쓸 수 있다.

또한 𝜽'x(i)는 두 벡터의 내적 u'v로 생각할 수 있다. 2개의 feature만 사용한다고 했으므로 벡터 X와 벡터 𝜽가 다음과 같이 그려진다고 하자. 그럼 벡터 x를 벡터 𝜽에 projection시켜서 p를 구할 수 있으므로 𝜽'x를  P ∙ ||𝜽||로 쓸 수 있다.

𝜽'x는 p ∙ ||𝜽||와 같으므로 다음과 같이 정의할 수 있다.

만약 SVM이 왼쪽 아래와 같은 초록색 decision boundary를 그렸다면 이러한 선택은 training sample에 매우 가깝기 때문에 margin이 크지 않아 좋은 decision boundary라 할 수 없다.(𝜽0가 0이기 때문에 decision boundary는 원점을 지나야 한다.) SVM은 이러한 선택을 하지 않는다. 그 이유는 다음과 같다.

 

일단 파라미터 벡터 𝜽는 decision boundary와 직교이므로 파란색이 벡터 𝜽가 된다.

이제  sample x(1)을 하나 선택해서 이걸 파라미터 𝜽 벡터에 projection 시킨다. 그러면 빨간색의 작은 직선 p(1)을 얻을 수 있다.

이러한 방법으로 다른 sample x(2)를 선택하여 똑같이 𝜽 벡터에 projection 시킨 뒤 작은 분홍색 직선 p(2)를 구한다.

벡터 x(2)가 벡터 𝜽와 이루는 각도가 90도가 넘기 때문에 p(2)는 음수가 된다.

 

Positive sample로 분류되기 위해선 p(i) ∙ ||𝜽|| 값이 1이상이어야 한다. 반대로 negative sample로 분류되기 위해선 p(i) ∙ ||𝜽|| 값이 -1 이하여야 한다.

따라서 우리가 선택한 2개의 sample x(1), x(2)에 대해서 p(1) ∙ ||𝜽|| >=1 이어야 하고 p(2) ∙ ||𝜽|| <=-1 이어야 한다. 그런데 지금 decision boundary가 sample들 사이와 거리가 작기 때문에 우리가 구한 p(i)는 매우 작은 값이다. 그러므로 위 조건을 만족하려면 𝜽가 커야한다.

 

그런데 최적화 관점에서 다시 생각해보면 우리는 파라미터 𝜽가 작은 값을 가지길 원한다. 따라서 𝜽는 작고 p(i)는 큰 게 우리한테 좋기 때문에 이런 decision boundary는 좋은 boundary가 될 수 없다.

SVM이 오른쪽처럼 decision boundary를 그렸다고 하자. 벡터 𝜽는 decision boundary와 직교이므로 파란색 선처럼 그려진다.

이전에 했던 것과 똑같이 두개의 sample을 고를 것이다. X(1)을 골라서 벡터 𝜽에 projection 시킨 뒤 p(1)을 구한다. X(2)를 가지고 똑같은 방법으로 p(2)를 구한다. 이렇게 구한 p(1), p(2)는 왼쪽 예제의 p(1), p(2)보다 더 큰 값을 가진다. p(i)가 큰 값을 가지기 때문에 우리가 원했던 것처럼  𝜽는 그만큼 작아질 수 있다. 그리고 이러한 decision boundary는 가장 가까이 있는 sample들과의 margin이 최대가 된다.

쉽게 보기 위해 𝜽0를 0으로 놓고 예시를 들었다. 𝜽0가 0이기 때문에 decision boundary는 원점을 지나지만 0이 아니면 오른쪽처럼 그려져야 한다.