[Data Mining] 10-1. SVM - Separable case

SVM (Support Vector Machine)

1979년 Vapnik가 박사과정때 개발한 SVM(Support Vector Machine), 한동안 주목받지 못하다가 1990년을 넘어서 대중적으로 알려지기 시작한 알고리즘이다. 본 챕터에서는 2개 범주를 SVM으로 분류하는 문제를 다루면서 아래 원리를 알아보도록 한다.

• 두 범주가 하나의 선형함수로 분리 가능한 경우(Separable case) 어떻게 선형 함수를 찾는가?

• 분리가 불가능한 경우(Non-separable case)는 어떻게 해결하는가? (비선형 SVM)

1. Separable case

SVM은 위 그림과 같이 데이터가 두 범주를 가질 때 두 범주를 구분하기 위한 직선을 찾는 알고리즘이다. 이 글에서는 2개 변수를 가지는 경우만 가정하기 때문에 직선으로 보이지만, SVM은 변수가 3개 이상일때도 동작하는 우수한 분류 모형이다. 

위와 같이 독립변수가 3개인 3차원에서는 두 범주를 분류하는 함수는 면(surface)이 된다. 만약 변수가 3개 이상인 다차원인 경우는 도식화 할 수는 없는 어떤 함수로 범주를 분류 할 수 있으며 ,이 함수를 하이퍼플레인(hyperplane)이라 한다.

H: Σj=1~p xj wj + b = 0

w1, ..., wp : 하이퍼플레인의 계수, b : 상수(절편), p : 변수의 수

위 정의와 같이 범주를 선형 하이퍼플레인 함수로 분류할 수 있는 경우를 Separable case라 하고, non-Separable case와 구분되어 분류문제를 풀이한다.

다시 2차차원으로 돌아와서, SVM의 앞서 언급했듯 SVM의 최종목적은 두 범주를 분리할 수 있는 하이퍼플레인을 찾는 것이다. 그런데 위 그림의 경우만 해도 두 범주를 분리할 수 있는 직선은 무수히 많다. SVM은 그 중 범주1의 지지선(wx + b = 1)과 범주2의 지지선(wx + b = -1)사이의 거리, 즉 마진(margin)을 최대화 하는 중앙선을 하이퍼플레인으로 선택한다.

H1: Σj=1~p xj wj + b = 1 (범주 1의 지지선)

H2: Σj=1~p xj wj + b = -1 (범주 -1의 지지선)

※ 그림에는 (+b)가 아니라 (-b)로 표시되어있는데 b는 상수이기 때문에 무시해도 좋다.

Margin = 2 / Σj=1~pwj²

※ 평행한 두 직선의 수직거리 = 1/ √(w1²+w2²) 의 원리에서 왔다. 숫자 2는 별 의미없음.

그럼 이제 마진을 최대화 하는 하이퍼플레인 함수의 계수(wj, b)를 찾는 최적화 문제를 풀면 된다. 다만 SVM의 목적에 따라 범주가 1인 경우는 H(x) ≥ 1, 범주가 -1인 경우는 H(x) ≤ -1라는 제약조건이 붙는다. 즉, 2개의 제약조건이 있는 최적화문제를 풀면 하이퍼플레인을 구할 수 있다. 최적화 문제를 풀 때 추정 파라미터가 분모에 있으면 계산하기가 불편하니 목적함수를 수정하고, 제약조건 2개를 1개의 식으로 아래와 같이 재정의 하여 좀 더 풀기 쉽게 변형하자.

※ 목적함수 : margin을 구하는 식에 역수를 취하였다.

※ 제약조건 : y에 1 혹은 -1을 대입하면 앞서 언급한 제약조건과 동일함을 알 수 있다. 

이 수식은 목적함수가 2차식이고, 제약조건도 x, y 모두 변수이기 때문에 2차식이다. 즉, 둘다 비선형식인데 2차식인것이 그나마 다행이다. 어쨋든, 이런 비선형 최적화 문제를 풀이할 수 있는 일반적인 방법에 대해 잠깐 알아보자.

Karush-Kuhn-Tucker Condition

어떤 목적함수 f(x)를 최소화 하는 최적화문제를 가정하자. → Min f(x)
그리고 이 문제에는 몇 개의 제약조건이 있다. → subject to hj(x) ≤ 0  (j = 1, ... m)

이렇게 제약조건이 있는 문제는 제약조건이 없는 문제로 변환해서 풀이하는 것이 쉽다.
그리고 제약조건을 없애기 위해 Lagrangian multiplier λ를 사용해서 아래와 같이 목적함수와 제약조건을 합친 Lagrangian function을 새로운 목적함수로 정의한다.

Min L(x, λ) = f(x)  + Σi=1~mλj hj(x)

위 최적화식을 해결한다면 f(x)도 최소화 함과 동시에 Σi=1~mλj hj(x)도 최소화된다.
여기서  Σi=1~mλj hj(x)를 최소화 한다는 것은 f(x)와 h(x)를 동시에 만족시키는 극값을 찾는다는 의미다.(f(x)그래프와 h(x)그래프의 교차점)

하지만 아쉽게도 제약식이 부등식이 아니고 등식일 때만 이 방법으로 풀 수 있다. 그래서 이 문제를 쌍대 문제(Wolfe dual problem)로 변환시키고 제약조건도 다시 밖으로 빼낸다다.
※ 쌍대 이론 : 원 문제가 최대화 문제라면 최소화 문제로, 원문제가 최소화 무제라면 최대화 문제로 전환하여 접근하는 방식. 쌍대문제를 풀 수 있으면 원문제도 자동적으로 풀림.

Max f(x) = Σi=1~mλj hj(x)

subject to Δf(x) + Σi=1~mλj hj(x) = 0

지금까지 원문제를 풀기위해 Lagrangian function으로 변환시켰다가 다시 쌍대문제로 돌아왔는데 여전히 위 식은 풀기가 쉽지 않다. 이 때 생각의 전환이 필요하다. 어릴 때 배웠던 필요충분조건 개념을 떠올려 보자.

(Constraint)

↓Constraint를 충족시키면 Optimal solution이 도출된다. (충분조건)

Optimal solution이면 제약함수는 충족된다. (필요조건)↑

(Optimal solution)

위 상황을 가정했을 때 필요충분조건을 유도하면 이 문제를 해결할 수 있다. 하지만 필요충분조건을 유도하는 것은 여전히 매우 어렵다. 결국 충분조건이나 필요조건 중 하나라도 유도해야 하는데, 다행히 몇 가지 필요조건을 유도한 3명의 위인이 있다. 그 3명의 이름을 딴 Karush-Kuhn-Tucker 이론은 

"어떤 문제의 최적해 x*에 대해 

우리가 제안하는 명제(KKT condition)를 만족시키는 λ, μ가 있다." 

라며 KKT condition을 제안하였다. 즉, KKT condtion을 만족시키면(=Optimal solution이면) 제약함수는 충족된다는 뜻이다. (우리가 유도하고 싶어하는 필요조건이다!)

그래서 우리가 가지고 있는 문제를 변형하면 위와 같이 KKT condition에 대입할 수 있다.

게다가 KKT condition에서 주장하는 또 한가지가 있는데, 바로 f(x)와 제약식 h(x)가 convex(볼록한) 함수일 때는 KKT condition이 최적해의 충분조건도 될 수 있다는 것이다. 즉, 필요조건이 아니라 필요충분조건이 될 수 있다는 의미인데, 심지어 우리의 목적함수 f(x)와 제약식 h(x)는 convex한 함수이다.
※ 최대화 함수나 최소화 함수는 convex 하다.

KKT condition으로 오기까지 상당히 오래걸리긴 했는데, 우리 문제를 KKT condition에 투영시켜서 풀면 optimal solution의 필요충분조건이 될 것이란 것을 알았다.

그래서 위 식을 KKT 조건을 충족시키기 위해 아래와 같이 제약조건별로 라그랑지 계수 α를 도입하여 새로운 목적 함수를 만들고, 

(기존의 목적함수와 제약조건의 합으로 구성되어 있다.)

위 목적 함수를 KKT condtion을 적용하면 아래와 같다. 즉, 아래 조건을 만족하면 Optimal solution이라는 뜻이다.

우리가 최종적으로 구하고자 하는 것은 wj인데, 위 KKT condtion에서 wj의 조건이 가장 위 gradient 조건에 유도되어 있다. 즉, wj는 αj의 함수이다. 그리고 나머지 직교, feasibility, 비음 조건은 제약조건이 된다.
※ 원 문제는 w를 구하는 문제였는데, 라그랑지안 계수 α를 구하는 문제로 변형됐다.
※ gradient 조건에서 x, y는 표본이기 때문에 알고있는 값임으로 α의 함수다.

위 KKT condition을 풀기 위해 KKT condition을 쌍대 문제로 전환하면 아래와 같이 변환할 수 있다. 변환된 식을 살펴보면 목적함수는 α의 2차함수고, 제약조건은 α의 1차 함수다. 즉, quadratic programming으로 풀 수 있는 매우 쉬운 문제로 변형되었다. 
※ quadratic P/G은 로직이 간단해서 쉽게 풀 수 있다. 풀이법은 생략한다.

SVM의 목적함수를 풀기 위해 매우 돌아왔다. 정리하자면,

• SVM의 최적화는 목적함수와 제약조건은 모두 2차식이라 풀기 어려운 문제다. 

• 비선형 최적화 문제를 풀기위해 원변수 → 라그랑지안 → 쌍대문제로 변환했다.

• 제약조건↔최적해의 필요충분조건을 KKT condition으로부터 찾았다.

• KKT condition 문제를 쌍대문제로 전환시키면 라그랑지안 계수 α를 구하는 quadratic P/G 문제로 변환된다. 

• quadratic P/G은 수학적으로도, 컴퓨터입장에서도 쉬운 문제다.
  즉, 풀이가 어려운 비선형최적화 문제를 풀기 쉬운 quadratic P/G으로 변환시켰다.

(이렇게까지 깊게 알아야하나 싶지만, 좋은 경험했다고 생각한다.)

마지막으로 예제를 풀어보고 Separable SVM 문제에 대한 정리를 끝낸다.

변수가 2개, 관측치는 9개가 주어졌다. 그리고 붉은 점이 범주1, 검은점이 범주-1 이다.

원 문제의 정의에 따라 우리는위 목적함수를 최소화 하고 9개(관측치의 수)의 제약조건을 만족시키는 문제를 풀어야 한다. 

하지만 우리가 고생해서 얻은 위 식을 통해 α를 푸는 문제로 변환할 수 있고, 관측치 9개를 대입하면 9개의 라그랑지안 계수 α를 구할 수 있다.

9개의 α를 구했으면 위의 KKT condition 으로부터나온 아래 수식에 따라 w1, w2를 구할 수 있다.

새삼 SVM을 라이브러리로 만들어준 개발자들에게 고마움을 느끼는 시간이다.

생각보다 Separable case의 강의리뷰가 길어져서 한번 끊고, 다음 글에서 Non-Separable case에 대해 알아보도록 하자.