R (17) - Support Vector Machine (SVM)

Support Vector Machine

SVM의 매력은 매우 아름답고 탄탄한 이론적인 배경을 바탕으로 정교하게 고안된 기계학습 알고리즘이라는 것에 있습니다. 여기에 알고리즘의 실제 적용이 여러 모로 쉽고 성능이 강력하며 따라서 실전적이라는 점이 그 매력을 더합니다.

SVM에서 풀고자 하는 문제는 다음과 같습니다.

"How do we divide the space with decision boundaries?"

예시와 함께 보면 좀 더 구체적으로 문제를 좁힐 수 있습니다:

 

1. 우리가 ′+′ 샘플과 ′−′ 샘플을 구별하고 싶다면 어떤 식으로 나눠야 하는가? 
2. 만약 선을 그어 그 사이를 나눈다면 어떤 선이어야 할 것인가? 

가장 쉽게 그리고 직관적으로 생각할 수 있는 답은 아마도 ′+′와 ′−′ 샘플 사이의 거리를 가장 넓게 쓰는 어떤 line으로 다음과 같은 녀석(점선)일 것입니다.

"widest street strategy"

흠... 매우 직관적으로 풀 수 있는 별 것 아닌 문제로 보입니다. 하지만 이 문제에 대한 답을 구체적이고 논리정연하게 이론으로 일반화하는 것은 언뜻 보기와는 달리 쉬운 작업이 아닙니다. SVM은 지금 던진 문제에 대한 답을 찾기 위해 풀어나간 과정입니다.

그래서 제가 오늘 정리하고자 하는 것은 SVM이기도 하지만 어떤 문제를 풀기 위해 체계적으로 아이디어를 개발하고 논리를 전개하는 과정 그 자체라고도 얘기할 수 있겠습니다. 그만큼 SVM은 매우 정교하게 고안된 알고리즘인데요 앞으로도 이런 관점에서 어떤 식으로 문제를 설정하고 어떻게 풀어나가는 지를 염두에 두면서 정리하고자 합니다. 이제 그 과정을 하나하나 따라가 보겠습니다.

Decision rule

그럼 먼저 "decision boundary를 정하기 위한 decision rule은 어떤 형태여야 할 것인가?"에 대해 생각해보겠습니다. 이를 위해 w⃗ 를 하나 그려볼텐데요 이 벡터는 우리가 그릴 street의 중심선에 대해 직교하는 벡터입니다. (일단 여기서 그 길이는 잠시 arbitrary로 제쳐두겠습니다.)

 

그리고 이제 모르는 샘플 u⃗  하나가 있을 때 우리가 궁금한 것은 street를 기준으로 이 녀석이 오른쪽에 속할지 혹은 왼쪽에 속할지입니다.

 

자 여기서 우리가 해볼 수 있는 한 가지 방법은 w⃗ 와 u⃗ 를 내적한 후 그 값이 어떤 상수 c보다 큰 지를 확인하는 것입니다

 

; w⃗ ⋅u⃗ ≥c. 혹은 일반성을 해치지 않는 범위에서 아래와 같이 얘기할 수도 있겠죠:

 

w⃗ ⋅u⃗ +b ≥ 0         then‘+′    (1)

논리는 매우 간단합니다. 내적을 한다는 것은 위에 그림에서 u⃗ 를 w⃗ 에 projection 한다는 것이고, 그 길이가 길어서 어떤 경계를 넘으면 오른쪽, 짧으면 왼쪽에 속한다는 것을 생각해보면 쉽게 이해하실 수 있을 것입니다.

 

따라서 수식 (1)이 우리의 decision rule이 됩니다. 우리가 SVM을 이해하는데 필요할 가장 첫번째 도구이기도 합니다. 하지만 아직은 부족한 점이 많죠. 아직 우리는 저 수식에서 어떤 w⃗ 를 정해야하는지 어떤 b를 잡아야하는지 전혀 모릅니다. 다만 w⃗ 가 우리가 원하는 street의 중심선에 직교한다는 것 하나만 알 수 있을뿐이죠.

아쉽게도 그런 w⃗ 는 매우 다양하게 그릴 수 있기에 여기서 내릴 수 있는 판단은 아직 constraint가 부족하다는 것입니다. 그래서 앞으로 할 것은 우리가 w⃗ 와 b를 계산할 수 있도록 저 수식에 여러 제약 조건들을 추가해가는 작업이 되겠습니다.

 

출처 : jaejunyoo.blogspot.com/2018/01/support-vector-machine-1.html

초짜 대학원생의 입장에서 이해하는 Support Vector Machine (1)