SVM 서포트 벡터 머신 알고리즘 개념 정리 (2): 불완전한 분류편

 

전 장에서 SVM 알고리즘의 특정 예시, 모든 점을 완벽하게 분리할 수 있는 경우를 살펴보았다. 그러나 현실 속에서 데이터는 100% 정확히 분류하기 어려운 경우가 더 많을 것이다. 사과와 수박을 부피 및 무게에 따라 분류하는 것은 상대적으로 쉬울테지만, 사과와 오렌지를 분류한다고 하는 경우는 난이도가 더 높을 것으로 예상되지 않는가?

 

이번 장에서는 두 데이터를 깔끔하게 분리할 수 없는, 즉 어느정도의 오류가 불가피한 경우의 SVM 알고리즘에 대해 살펴보고자 한다. 그 전에, 간단히 Support Vector Machine 알고리즘의 명칭에 대한 유래를 소개하고자 한다.

 

지탱하는 Support Vector,  그 사이의 분류기

서포트 벡터의 개념을 이해하기 위해서는 볼록포, 혹은 Convex hull 에 대한 이해가 필요하다. Convex hull은 주어진 점을 모두 포함하는 최소 크기의 영역을 정의하는 집합이다. 아래의 예시를 보자.

 

8개의 점에 대한 볼록볼록 볼록포

2차원 평면에 무작위의 점 8개가 있다고 하자. 이들을 모두 포함하는 영역을 규정한다면 가장 바깥쪽에 위치한 점들을 서로 이은 도형이 될 것이다. 따라서, 아래 도형에서 테두리 긋기를 통해 규정된 오각형 모양의 영역이 바로 이 점들의 볼록포이다.

 

그렇다면 서포트 벡터란? 하나의 볼록체의 범위를 규정하는 (또는 지탱하는) 점이다. 점이라고 하지 않는 이유는 점 역시 하나의 공간에서 정의되는 '벡터'이기 때문이다. 서포트 벡터는 하나만 존재하지 않으며, 볼록체를 구성하는 점의 수에 따라 여러개가 동시에 존재한다. 심지어 두개의 점이 동시에 서포트 벡터가 될 수도 있다.

다양한 종류 및 형태의 서포트 벡터가 가능하다

그렇다면 우리의 SVM 분류 문제로 돌아와 보자. 우리는 '빨강'과 '파랑'이라는 두개의 볼록체를 가지고 있고, 각 볼록체 별로 다양한 서포트 벡터를 정의할 수 있다. 그 중 상대의 영역에 가장 가까운 서포트 벡터를 기준으로, 각각의 벡터를 지나는 서로 평행한 두 직선을 선택할 수 있다.

 

해당 직선의 개수는 여러개가 가능하지만, 전 장에서 살펴 보았듯이 우리는 두 직선 사이의 마진을 최대로 하는 직선을 최적의 조합으로 선택한다. 이 두 직선의 중간에 바로 우리의 분류기가 위치한다. (SVM 이라는 명칭이 무색하게, 정작 우리의 분류기는 서포트 벡터들과 맞닿아 있지 않다는 점이 아이러니하다)

서포트 벡터를 지나는 서로 평행한 두 직선, 최대의 마진

'분리가 불가능한 문제'의 정의

전 장에서 살펴 보았듯이,  모든 데이터 값이 완벽하게 분리 가능하다면 위의 정의 만으로 충분히 분류 알고리즘을 구성할 수 있다. 반면 '사과'와 '오렌지' 같이 그 경계가 상대적으로 애매한 경우는 어떨까? 크게 두가지 오류를 생각해 볼 수 있다.

 

두개의 불량 과일을 예의주시하자

1. 사과를 오렌지로 잘못 판별하는 경우 (위 그림의 빨강점)
2. 오렌지로 분류 하기는 했는데, 확신 하기에는 애매한 경우 (위 그림의 파랑점)

 

알고리즘을 통해 한번 자세히 살펴보자.

전 장에서 우리는 '올바르게 분류된 값'이란 아래 공식을 충족한다고 배웠다.

 

yi ( w · xi +b ) ≥1

 

yi = { 1, -1 }, '사과'인지 '오렌지'인지 구분하는 데이터 값의 레이블

 

( w · xi +b ) = 데이터 값을 함수에 대입하여 얻은 값. 학습 데이터 기준 모든 함수 값은 +1 보다 크거나 , -1 보다 작다.

 

쉽게 말해, (과일의 부피 및 무게를 대입하여 얻은) 함수 값이 -1 이하, 실제 레이블이 '사과(-1)' 라면 두 값의 곱은 +1 이상의 양수 이며, 함수 값이 +1 이상이고 실제 레이블이 '오렌지 (+1)' 이라면 마찬가지로 함수 값은 +1 이상의 양수인 것이다.

 

그렇다면 위 1, 2번 각각의 점은 어떠할까?

 

먼저 1번 예시의 빨강 점은 함수값이 +1 이상의 양수 이며, 사과 (빨강점) 이므로 -1 의 y값을 갖는다. 두 값의 곱은 -1 이하의 음수이다.

-1 ≥ yi ( w · xi +b )

 

반면 2번 예시의 파랑점은 오렌지 이므로 +1 의 y값을 갖고 0과 1 사이의 함수값을 갖는다. 두 값의 곱은 0과 1 사이의 양수이다.

0 < yi ( w · xi +b ) < 1

 

따라서, 두 경우 모두 위에서 명시한 '올바른 분류의 기준'을 충족하지 않는다.

 

 

분리가 불가능한 경우 SVM 함수의 목표

그렇다면 이와 같이 오류가 발생할 때, SVM 알고리즘은 어떤 새로운 기준으로 답을 찾아 낼까?

 

첫째, 바로 발생한 총 오류의 정도이다. 위의 그림을 다시한번 살펴보자. 잘못 분류된 점과 '옳게 분류되는 범위' 사이의 거리의 정도를 각각 ξj, ξi (Error term, 즉 오류의 값) 으로 정의하고 있다. 쉽게 말해, 잘못 분류된 점이 정상의 범주에서 얼만큼 떨어져있는가를 보여주는 값이다. 특정 알고리즘이 잘못 분류한 모든 점들의 오류값을 더한 값이 바로 그 알고리즘의 총 오류가 될 것이다.

 

둘째는 우리에게 익숙한 개념 마진이다. 마찬가지로 두 볼록체의 경계에 위치한 서포트 벡터를 기준으로 직선을 설정하며, 두 직선과 분류기 간 거리 (마진)을 최대로 하는 값을 선택한다.

 

위의 두 기준을 종합하여 아래와 같이 알고리즘의 목표를 정리할 수 있다.

왼쪽: '분류기의 마진을 최대로 해! = ∥w∥ 을 최소로 해!'

오른쪽: '발생하는 오류를 최소로 해!'

 

물론 두 목표를 동시에 충족하는 최적의 해가 있다면 다행 이겠지만, 현실에서는 각 목표의 비중에 따라 해가 달라진다. 따라서, 우리는 C 라는 파라미터를 통해 두 목표 간 우선순위를 조정한다. (C가 높을수록 오류 증가에 대한 페널티 상승)

 

<예시1.>
대출심사를 하는 은행의 입장이라면, 상환능력이 없는 고객에게 잘못 대출을 해주는 경우를 피하는 것이 급선무이므로 후자에 대한 페널티를 높게 설정하는 것이 보다 중요할 것이다.

<예시2.>
두 소비자 집단을 구분하여 보고 싶은 마케팅 애널리스트의 경우 오류에 대한 페널티 값을 작게 설정할 수 있을 것이다. 경계선 부근에서 발생하는 오류를 어느정도 감안하더라도, 넓은 마진을 통해 서로 다른 고객군을 명확히 나누어 볼 수 있기 때문이다.

 

물론 실제 적용 시에는 더욱 많은 조건이 고려되고 튜닝되어야 하는 것이 알고리즘이다. 다만 본 글을 통해 머신러닝 분류기라는 '매직박스'의 구동 원리에 대한 기본적인 이해를 갖추었으면 하는 마음이다 (사실 스스로 정리하기 위함도 있다).

 

아무튼, 두 글에 걸쳐 대표적인 분류기 알고리즘 SVM 에 대해 살펴보았다. SVM 은 강화학습이자 분류의 문제를 해결하는 알고리즘 중 하나이며, 실제로는 가용 가능한 데이터 및 컴퓨팅 파워 등에 따라 알고리즘 선택은 달라 질 것이다.

 

다음 장에서는 또 다른 대표적인 분류 알고리즘인 K-최근접이웃 (K-Nearest Neighbor)에 대해 살펴보고자 한다!