서포트 벡터머신, SVM - (2)
오일식 저, 패턴인식' 교재와 '핸즈온 머신러닝' 그리고 'ratsgo' 블로그를 참고하여 작성하였습니다. SVM에 대해 간략하게 알고 싶으신 분들은 여기를 참고하시면 됩니다.
SVM 이란?
(Support Vector Machine)은 러시아 과학자 Vladimir Vapnik가 1970년대 후반에 제안한 알고리즘으로, 그 당시에는 크게 주목 받지 못했다. 하지만 1990년대에 들어 분류(classification)문제에서 우수한 일반화(generalization) 능력이 입증되어 머신러닝 알고리즘에서 인기 있는 모델이 되었다고 한다. 그리고 SVM은 일반화 측면에서 다른 분류 모델과 비교하여 더 좋거나 대등한 것으로 알려져 있다.
또한, SVM은 선형 또는 비선형 분류 뿐만아니라 회귀, 이상치 탐색에도 사용할 수 있는 모델이며, 특히 복잡한 분류 문제에 잘 맞으며, 중간 크기의 데이터셋에 적합하다.
아래의 그림에서 ① 분류기는 Train set을 틀리게 분류한다. 이를 여러번 학습시켜 모델링하면 ②와 ③ 분류기와 같이 될것이다. Train set 측면에서 보면 ②와 ③ 분류기는 오류가 0이므로 같은 성능을 가진 분류기로 볼 수 있다. 하지만, 일반화(generalization) 측면에서 보면 ② 보다 ③이 더 낫다고 할 수 있다. 그 이유는 ③ 분류기가 두 개의 클래스에 대해 여백(margin) 크기 때문이다.
바로 여기서 이러한 여백, 즉 마진을 어떻게 공식화하고 이 마진을 최대화하는 결정 초평면(decision hyperplane)을 찾는 것이 바로 SVM의 발상이라 할 수 있다.
1. 결정 함수와 예측
Linear SVM은 두 클래스를 분리하기 위한 선형 결정 함수를 찾는 것이며, 이러한 결정 함수는 다음과 같이 나타낼 수 있다.
는 전체 특성 공간을 두 영역으로 분할한다.
→
→
하나의 초평면을 표현하는 식은 여러가지가 있다.
는 초평면의 법선벡터다.
은 초평면의 방향을 나타내고, 는 위치를 나타낸다.
임의의 점 에서 초평면까지 거리는 이다.
2. 목적 함수
SVM에서 풀고자 하는 문제는 아래의 그림에서 마진(margin)을 가장 크게하는 결정 초평면의 방향, 즉 를 찾는 것이다.
위의 그림에서 마진은 색이 칠해진 데이터 포인트에 의해 좌우된다. 이러한 데이터 포인트를 서포트 벡터(Support Vector)라고 한다. 서포트 벡터()에 대한 마진은 다음과 같다.
Train set을 로 표기하자. 는 클래스를 나타내며, 에 속하면 이고, 에 속하면 이 된다.
위와 같은 조건 하에 최대 마진을 갖는 결정 초평면을 찾는 것은 조건부 최적화 문제(constrained optimization porblem)로 나타낼 수 있다. 아래의 조건식에서 등호(=)가 성립하는 데이터 포인트가 바로 서포트 벡터이다.
아래와 같이 최대 마진을 구하는 문제를 역수를 취해, 최소화하는 문제로 바꿀 수 있다.
위의 문제의 두 가지 측면에서 보면 다음과 같다.
해의 유일성(uniqueness)
의 2차항만 가지므로 볼록(convex)한 함수이며, 조건식은 개 모두 선형이다. 따라서, 유일한 해를 가진다.
문제의 난이도
위의 문제는 개의 선형 부등식을 가진 2차함수의 최적화 문제이며, 의 개수는 엄청나게 클 수 있다. 이러한 경우에 라그랑제 승수(Lagrange multiplier)를 이용해 해결할 수 있다.
1) 라그랑제 승수법
위의 문제를 살펴보기 전에 먼저 라그랑제 승수법(Lagrange multiplier method)에 대해 알아보자.
라그랑제 승수법의 기본 개념은 제약이 있는 최적화 문제에서 목적함수로 제약을 옮김으로써 제약이 없는 문제로 변환하는 것이다.
간단한 예로 라그랑제 승수법을 살펴보도록 하자. 아래와 같이 등식 제약의 조건 하에서 함수 를 최소화 하는 를 찾는 문제를 보자.
위의 식을 라그랑제 승수법을 사용하기 위해 라그랑제 함수(Lagrangian, Lagrange function)로 다음과 같이 정의하자.
처럼 가 제약이 있는 최적화 문제의 해라면, 가 함수 의 정류점(stationary point) 즉, 모든 편도함수(partial derivative)가 0인 지점이 되는 가 존재한다는 것을 보였다.
따라서, 에 대한 라그랑지안 의 편도함수를 계산할 수 있으면 이 도함수가 모두 0이 되는 지점을 찾을 수 있고, 제약이 있는 최적화 문제의 해는 이런 정류점 중에 있어야 한다.
위의 식에서 편도함수는 다음과 같다.
모든 편도함수가 0이면, 이므로, , , 을 계산할 수 있다.
라그랑제 함수로 변환
다시 SVM 문제로 돌아가보자. SVM 문제의 조건식에서 각 조건식 마다 라그랑제 승수 를 부여한다. 이들의 벡터를 로 표기하면 다음과 같다.
2) KKT(Karush-Kuhn-Tucker) 조건
위에서 살펴본 예제는 등식 제약 조건부 최적화 문제였다. 하지만, SVM은 부등식 제약(inequality constrained) 최적화 문제이다(예를들어 ).
이러한 부등식 제약 최적화 문제는 다음과 같이 세 가지 KKT조건을 이용해 풀수 있다. KKT 조건은 필요 조건 이므로 반드시 만족해야 한다.
라그랑제 함수 에서 라그라제 승수를 제외한 로 편미분한 식이 이되어야 한다.
모든 라그랑제 승수 은 0보다 크거나 같아야 한다.
모든 조건식에 대해 이거나 이 되어야 한다. 이때, 인 데이터 포인트가 바로 서포트 벡터이다.
3. Wolfe 쌍대(Dual) 문제
위에서 SVM 문제는 볼록 성질을 만족한다는 것을 알 수 있었다. 이러한 볼록 성질을 만족하는 조건부 최적화 문제는 Wolfe dual 문제로 변환할 수 있다.
원래(primal) 문제가 , 이라는 조건 하에 를 최소화 하는 문제라고 하면 쌍대(dual) 문제는 과 이라는 두 가지 조건 하에 를 최대화 하는 문제로 표현할 수 있다.
따라서, 위의 라그랑지안 SVM 문제를 쌍대 문제로 나타내면 다음과 같다.
위의 식을 에 대입하여 정리하면 다음과 같다.
최종적으로 다음과 같이 Dual 문제로 쓸 수 있다.
위의 식은 다음과 같은 특징이 있다.
하나의 등식 조건과 개의 부등식 조건을 가진 2차(quadratic) 목적함수의 최대화 문제이다.
와 가 사라졌으므로, 라그랑제 승수 를 구하는 문제가 되었다. 따라서, 를 구하면 와 를 구할 수 있다.
목적함수에서 특성 벡터 가 내적 로 나타난다. 이러한 점은 선형 SVM을 비선형 SVM으로 즉, Kernel SVM으로 확장하는데 결정적인 역할을 한다.
4. Soft Margin SVM
아래의 그림처럼 여유 변수(slack varibles, )를 추가한 소프트 마진 SVM(soft margin SVM)의 목적함수는 다음과 같다.
위의 식을 다음과 같이 해석할 수 있다.
Margin을 최대한 크게 하며, 동시에 인 테이터의 수를 최소한으로 하는 결정 초평면의 방향 를 찾아라.
위의 식에서 는 일종의 penalty라고 볼 수 있다.
를 작게한다는 것은 마진을 나타내는 첫번째 항 ()을 중요하게 생각하는 것으로 볼 수 있다.
반대로 를 크게한다는 것은 마진을 줄이는 대신 마진 사이에 존재하는 데이터 그리고 틀린 데이터의 수를 줄이겠다는 의미이다.
Loss Function
Soft Margin SVM은 어느정도의 오류를 포함하기 때문에 이를 손실함수(loss function)를 이용해 최적화 할 수 있다.위의 Soft Margin SVM 의 제약식,
은 다음과 같이 나타낼 수 있다.
따라서, 위의 식을 손실함수 측면에서 보면 다음과 같이 손실함수를 정의할 수 있다.
형태를 hinge loss 함수라고 한다.
6. Kernel SVM
선형으로 분리되지 않는 데이터를 비선형 매핑, 즉 커널 함수를 이용해 저차원()에서 고차원()으로의 매핑(mapping)을 통해 해결할 수 있다. 이러한 커널함수를 이용하는 SVM을 Kernel SVM이라 한다.
커널함수는 두 개의 벡터(데이터)를 입력으로 가지며, 형태로 나타낸다. 이러한 커널 함수는 다음 성질을 만족해야 한다.
공간 상의 두 벡터 와 를 입력 변수로 갖는 커널 함수 는 를 만족하는 매핑 함수 가 존재해야 한다. 이를 머서(Mercer)의 정리라고 한다.
즉, 커널함수의 값과 상으로 매핑된 두 점 와 의 내적이 같아야 한다.
위의 성질을 간단한 예를 통해서 알아보자. 2차원의 공간을 3차원의 공간으로 매핑하는 커널함수는 다음과 같이 나타낼 수 있다.
두개의 벡터를 ,
Kernel SVM을 사용하면 목적함수를 다음과 같이 나타낼 수 있다.
커널의 종류
Scikit-Learn의 SVC 클래스에서 제공하는 커널의 종류는 다음과 같다. 각 변수에 대한 자세한 내용은 해당 링크를 참고하면 된다.
선형(linear) :
다항식(poly) :
가우시안 RBF(rbf) :
시그모이드(sigmoid) :
7. 실습 코드
Scikit-Learn을 이용한 SVM 실습코드는 https://github.com/ExcelsiorCJH/Hands-On-ML/blob/master/Chap05-SVM/Chap05-SVM.ipynb 에서 확인할 수 있다.