본문 바로가기

ML & DM/SVM

SVM (Support Vector Machine) Part 1

SVM (Support Vector Machine)은 Logistic Regression , Neural Network, Bayes classifier 같은 Linear classifier(초평면을 이용하는 분류기를 말함) 들 중에 하나이다. 분류상으로는 당연히Supervised Learning에 속한다.

SVM 에서 중요한 요소 3가지는 마진(Margin), 서포트벡터(Support Vector), 커널(Kernel)이다.

이 3가지에 대한 기본 개념을 알아야 뒤에 나올 최대 마진 분류기(Maximum margin classifier, 혹은 Hard Margin SVM이라고 불림), 슬랙변수를 가진 SVM( 혹은 Soft Margin SVM 이라고 불림), 마지막으로  커널을 활용한 SVM(혹은 Soft Margin SVM with Kernel)을 이해할 수 있다.


1.1 마진(Margin)


마진은 하나의 데이터포인트(Support Vector)와 판별경계(Hyperplane)사이의 거리를 말한다. 더 정확히는 각각의 클래스의 데이터 벡터들로 부터 주어진 판별 경계까지의 거리 중 가장 짧은 것을 말한다. SVM에서는 이 마진이 클수록 분별을 잘하는 분류기인데 분류기와 데이터포인트간의 거리(마진)를 두는 이유는 학습오차와 일반화오차 중 일반화오차 부분 즉 데이터속에서 내제하는 기본적인 오차부분정도(노이즈)를 표현하기 위해 존재한다. 좀 더 풀어서 말하자면, 일반적으로 학습데이터에 과다적합될수록 높은 복잡도의 비선형 분류기가 되는데 이렇게 학습데이터에 과다 적합될 수록 학습데이터의 노이즈까지 학습시켰기 때문에 오차는 커지는 현상이 발생한다. 따라서 학습데이터에 일정정도의 오차를 내야 (노이즈는 학습을 시키지 않는다는 말임) 최적의 분류기가 나온다. SVM에서는 이 일정정도의 오차를 Margin으로 둔 것이다. 이를 통해 일반화 오류를 줄이면서 데이터의 판별의 정확도를 높일 수 있다.

 마진은 여러개의 판별경계후보가 있을때 벡터공간에서의 가장 합리적인 판별경계를 찾을 수 있는 기준인 셈이다. 



1.1-1 VC dimension


우리가 위에서 마진을 크게 하는 분류기 일수록 좋은 분류기라고 하였는데 이를 직관적으로 말하기보다 하나의 이론적인 방법으로 설명을 하는게 좋을 것이다. 이 Classifier가 얼마나 좋은 성능을 내는지를 보여주기 위한 척도 중 하나라고 볼 수 있는 VC dimension에 대해 설명을 해보겠다. VC Dimension 은 Shattering과 Dichotomy 로 구성된다. Dichotomy는 말그대로 데이터포인트를 나누는 것을 말한다. 만약 우리가 N개의 데이터포인트를 가지고 있다고 해보자. 이 N개의 포인트들은 +와 - 두개로 라벨링을 한다면 2N개의 방식으로 라벨링이 될 수 있다. 그러므로 2N개의 다른 훈련 문제들은 N개의 데이터에 의해 정의된다. 만약 이러한 문제들중 어느것에 대해서도, -로부터 +예제들을 구분하는 한 가정(분류모델)을 찾을 수 있다면, 우리는 이 분류모델이 N개의 데이터 포인트들을 Shatter한다고 말한다. 즉 다시말해, N개의 예제들에 의해 정의될 수 있는 학습문제는 어떤 한 분류기에 의해 오류없이(완전히) 학습되어질 수 있다. 분류기에 의해 shattered 될 수 있는 이 데이터 포인트의 최대 갯수를 바로 분류기의 VC Dimension 이라고 한다. 따라서 VC dimension은 분류기의 데이터 수용능력을 측정한다. 보통 n차원의 선형분류기에서는 VC dimension은 n+1 이라고 한다. 2차원 선형 분류기가 XOR 문제 때문에 4개(주대각선끼리 같은 점 비 주대각선끼리 같은점) 데이터포인트를 분류하지 못하는것을 생각하면 납득이 갈 것이다. 일반적으로 VC dimension이 높아지면 일반화오류가 높아진다고 알려졌는데, Shatter를 할시에 데이터에 대해 오류없이 완전히 학습되어 지므로 이는 과적합의 문제가 있을 것이다. 따라서 학습할 데이터의 차원이 높아질수록 해당차원의 노이즈까지 학습하게 되므로 전체적으로 일반화 오차가 커지는 현상이 나타나기 때문에 VC dimension은 높으면 좋지 않다. 

이것이 왜 Margin과 연관이 있느냐하면 과적합을 막기위해서는 VC dimension을 낮추어야 하고 이는 곧 shattering 할 수 있는 데이터셋을 줄여야 한다. 이 데이터셋을 줄이는 방법이 바로 Margin인 것이다. SVM은 분류를 할때 어떤 선형분류기를 기준으로 마진을 재서 이 마진을 기준으로 분류를 하기 때문에 이 마진안에 들어온 데이터는 무시를 하여 Shattering 할 수 있는 데이터셋을 줄여 과적합을 막는 것 더 나아가 VC dimension을 낮추는 것이다. 이것이 바로 위 1.1 에서 말한 일정정도의 오차를 둔다는 말과 일맥 상통하는 말이다.

더 자세한 설명은 링크를 참조하기 바란다.



1.2 서포트벡터(Support Vector)


서포트 벡터는 위에서 말한 데이터 포인트가 바로 서포트 벡터이다. 다시말하자면 판별경계(Hyperplane)까지의 거리가 가장 짧은 데이터 벡터를 서포트 벡터라고 한다. 



서포트벡터와 마진은 결정 경계에 따라 달라진다. 이 서포트 벡터로 인해서 SVM이 가지는 장점은 새로운 데이터포인트가 들어왔을때 전체 데이터포인트와의 내적거리를 보지않고 서포트벡터와의 내적거리만 구하면 되므로 상당히 계산비용을 줄일 수 있다는 점에서 강점이 있다. 


1.3 커널(Kernel)


선형분리가 불가능한 저차원의 데이터를 고차원의 공간의 값으로 매핑시켜 선형평면(Hyperplane)으로 분류 가능한 선형문제로 변환을 시켜 분류를 가능하게 할 수 있지만 여기서 차원을 높임으로 인해 계산비용이 높아지는 문제가 생긴다. 이러한 문제를 해결할 수 있는 방법이 바로 커널법이다. 

예를들어 n차원의 입력데이터 x를 m 차원의 특징데이터 f(x)로 매핑시킨후 이를 SVM으로 분류한다 가정했을때 차원m이 아주 크다면 고차원의 특징벡터 f(x)를 사용하는 것은 계산비용이 너무 들어 현실적으로 불가능하다. 뒤에서 보겠지만 SVM의 연산을 보면 각각의 특징벡터 f(x1),f(x2)를 이용하는게 아니라 두벡터의 내적을 사용한다. 여기서 각 특징벡터를 선형분포로의 매핑이 있다고 가정하면, 이 둘을 내적한 벡터도 당연히 선형분포의 형태로 매핑이 될것이다. 따라서 각 특징벡터의 고차원 매핑함수 f()를 각각 정의하지 않고 전체의 내적함수만 정의하여 계산량을 줄일 수 있다. 여기서 나온 이 내적함수가 바로 커널 함수이고 이렇게 계산량을 줄이는 방법을 커널법 혹은 커널트릭이라고 한다.

이러한 커널트릭은 SVM 뿐 아니라 Gaussian processes, PCA 등 모든 비선형 문제를 가진 분류기에서 쓰일 수 있다.



이제 본격적으로 SVM의 종류들에 대해서 알아보자.


2. 최대마진 분류기 SVM 또는 Hard margin SVM


최대마진 분류기는 마진을 최대로 하는 선형 결정경계를 찾는 분류기를 말한다. 가장 일반적인 서포트 벡터 머신이다. 

이 식에서 는 초평면의 법선 벡터가 되고 는 원점에서 직선까지의 거리를 결정하는 값이 된다.  한점 x에서 결정 경계 까지의 거리는 아래와 같이 계산되는데, 지금까지는 크기가 1인 법선 벡터 를 썻으나 꼭 크기가 1일 필요는 없다. 밑에 식은 평면으로 부터의 거리만 수정을 한것이다.



위 결정 경계를 중심으로 d의 부호로 데이터를 구분할 수 있다. 



SVM의 판별 경계로 부터 가장 가까운 데이터 벡터들 사이의 거리는 같도록 할 것이며, 따라서 어떠한 에 대해서 각각의 클래스의 서포트 벡터 x+와 x-는 다음식을 만족시키도록 와 의 크기를 수정할 수 있다.



이 것을 만족시키는 선형 판별경계(Hyperplane)을 정의하면 y값의 범위가 -1에서 1사이이므로로 정의 된다.


이때 두 서포트 벡터로부터 선형판별경계까지의 거리는 아래와 같다.



우리가 필요한 것은 거리라는 절대값이므로 Margin은 위 둘의 절대값을 더한다.



이제 이 마진을 최대화시키는(|W|를 최소화시키는) 와 를 찾으면 된다. 그런데 여기서 제약조건이 하나 나온다.라벨값 y를 생각해 보면 두 클래스에 대해 다음과 같이 라벨값을 정의 할 수 있다.



선형판별경계(hyperplane)이 데이터들을 완벽히 분류하기 위해서는 다음식을 만족시켜야 하며, 



라벨값(y)가 +1면 판별식의 최소값도 +1이 되고 라벨 값이 -1이면 판별식의 최소값도 -1이므로 결국 이 부등식의 최소값은 0이 된다. 따라서 이를 일반화 시켜 양변에 yi를 곱했을 경우 모든 데이터들에 대해 다음의 제약조건을 만족해야한다.



정리해보면, SVM은 위의 마진을 최대화 하며(|W|를 최소화), 위의 제약조건을 만족시키는 와 를 찾는 문제가 된다. 여기서 변수가 분모에 있는 경우 계산에 어려움이 있으므로, 편의성을 위해 목적함수를 아래와 같이 수정할 수 있다. 이제 이 변형된 목적함수를 최소화하면 된다. 2로 나눈 이유는 j(w)를 미분하면 |w|만 나오게 하기 위해서 이다. 



이제 목적함수 와 제약조건 에 대한 정의가 끝났으므로 이를 하나의 식으로 묶어 최적의 파라미터와 를 추정할 수 있다. 이를 하기 위해서는 라그랑지 승수법을 써야 한다. 라그랑지 승수법을 써 둘의 식을 결합한 식은 다음과 같다.




우리가 최적의 파라미터를 얻기위해서는 와 를 최소화하고, 제약함수는 최대화가 되게 하면 마진을 가장 크게하는 분류기이다. 이제 라그랑주 함수(목적함수)에서 와 의 최소값 그리고 제약승수 람다의 최대값을 찾기 위해 라그랑제 함수에 대해 와 로  편미분 하면 다음과 같은 관계식을 얻는다.



위 식으로 부터 를 도출하고 위 두식을 위 라그랑주식에 대입해 다음과 같은 새로운 형태의 목적 함수를 얻을 수 있다.



이와 동시에 라그랑주변수에 대한 다음 조건을 만족하여야 한다.



이렇게 라그랑제 함수로 표현된 최적화 문제에 대해서 라그랑주로 표현된 최적화 문제에 대한 이원적 문제라고 하며 이제 이차 계획법(Quadratic programming)을 사용하여  라그랑주 함수가 람다()에 대한 이차 함수이므로 를 최소화 하는 추정치 를 찾는다. 다른 최적화 방법에 비해 이러한 이차계획법이 가지는 장점은 Gradient descent 같은 최적화 알고리즘의 경우 광역 최적점을 보장하지 않는다. 그러나 이차함수는 convex function 이므로 항상 광역 최적점을 보장한다는 점에서 강점을 가진다. 이렇게 을 찾은후에 이에 맞는 서포트벡터를 구하는 작업을 하는데 부등식을 제약 조건으로 가지고 있는 라그랑주함수는 KKT조건을 따르며 이는 다음과 같다.





여기서 추정된  에서 한가지 중요한 성질이 나오는데 위 조건식에서 안의 값은 데부분의 데이터가 결정경계와는 떨어져 있기 때문에 이 조건식을 만족하게 된다. 이 경우에 KKT 조건을 만족하기 위해서 는 반드시 0이 되어야 한다. 꼭 이 조건이 아니더라도을 최대화 하기 위해 라그랑주 승수(제약조건)부분이 최소화 되어야 하므로 음이 아닌(라그랑주 변수의 조건) 값은 0이 됨을 알 수 있다. 따라서 대부분의 학습데이터에 대응되는 라그랑제 승수 는 0이 되며, 오직 가 0인 경우에만 가  0이 아닐 수 있다. 그런데 여기서 =0을 만족하는 데이터는 결정경계에 가장 가까이 있어 마진을 결정하는 서포트 벡터가 된다. 즉 오로지 서포트 벡터 데이터에 대해서만 는 0이 아닌 값을 가지게 됨을 알 수 있다.  이렇게 도출된 서포트벡터 집합을 이용해 다음의 최적의  와 를 찾을 수 있다.



따라서 최종적으로 위 식을 판별함수에 대입하면 



같은 식이 나온다.

위의 최대마진 분류기법은 모든 학습 데이터들에 대해서 정확이 분류될 것을 그 제약조건으로 하고 있다. 하지만 이렇게 판별이 가능하다는 것은 현실적으로 불가능하다. 따라서 약간의 오분류를 허용하도록 제약조건을 수정해야할 필요성이 생기는데 여기서 나오는 것이 바로 슬랙변수를 가진 SVM(혹은 Soft Margin SVM)과 커널법을 이용한 Soft Margin SVM 이다. 이 두 SVM에 대해서는 다음 파트에서 다루겠다.


참고문헌 : http://deepcumen.com/2015/04/support-vector-machine/

            https://www.youtube.com/watch?v=eHsErlPJWUU&hd=1

'ML & DM > SVM' 카테고리의 다른 글

SVM (Support Vector Machine) Part 2  (0) 2016.03.09