1. SVM Support Vector Machine 1) 개념 2) 결정 경계 3) margin 4) SVM의 종류 2. Linear hard margin SVM 1) 라그랑주 승수법 2) Primal form과 Dual form 3. Linear soft margin SVM 1) slack varibles와 C 2) Dual form 4. Kernel SVM (Non-Linear SVM)
1. SVM Support Vector Machine
1) 개념
: 패턴 인식,분류, 그리고 회귀 분석 등에 사용되는 머신러닝알고리즘
주어진 데이터에서 class를 나누는 기준선을 정의하고, 분류되지 않은 새로운 데이터가 어떤 class에 속할지 판단
📌 margin을 최대화하는 최적 분리 초평면을 찾아 데이터의 class를 분류
(위키백과) 서포트 벡터 머신은 기계 학습의 분야 중 하나로 패턴 인식, 자료 분석을 위한 지도 학습 모델이며, 주로 분류와 회귀 분석을 위해 사용한다. SVM 알고리즘은 주어진 데이터 집합을 바탕으로 하여 새로운 데이터가 어느 카테고리에 속할지 판단하는 비확률적 이진 선형 분류 모델을 만든다. 선형 분류와 더불어 비선형 분류에서도 사용될 수 있다. 비선형 분류를 하기 위해서 주어진 데이터를 고차원 특징 공간으로 사상하는 작업이 필요한데, 이를 효율적으로 하기 위해 커널 트릭을 사용하기도 한다.
(위키백과) 만들어진 분류 모델은 데이터가 사상된 공간에서 경계로 표현되는데 SVM 알고리즘은 그 중 가장 큰 폭을 가진 경계를 찾는 알고리즘이다. 데이터 점이 p-차원의 벡터 (p개의 숫자 리스트)로 주어졌을 때, 이러한 데이터 점을 (p-1)-차원의 초평면으로 분류할 수 있는지를 확인하고 싶은 것이다. 이러한 작업을 선형 분류라고 말한다. 데이터를 분류하는 초평면은 여러 경우가 나올 수 있다. 초평면을 선택하는 타당한 방법 중 하나는 두 클래스 사이에서 가장 큰 분류 또는 마진(margin)을 가지는 초평면을 선택하는 것이다. 그래서 우리는 초평면에서 가장 가까운 각 클래스의 데이터 점들 간의 거리를 최대로 하는 초평면을 선택한다.
[용어 정리] 결정 경계 (decision boundary) : 벡터 공간을 두 class로 분할하는 분류 기준면 초평면(hyperplane) : 고차원 공간에서 결정경계 Support Vector : class에서 결정경계에 가까이 있는 데이터 margin : class 사이 거리 = 결정 경계와 Support Vector 사이의 거리 목적 함수 : margin을 가장 크게하는 결정 경계의 방향 w를 찾는 함수
2) 결정 경계 (decision boundary)
-고차원 공간에서 데이터의 class를 분류하는 최적의 결정 경계를 찾는다.
-결정 경계는 2차원 공간에선 선, 3차원 공간에선 면, 그 이상의 고차원 공간에선 초평면이 된다.
- 예) 데이터의 두 class를 2차원에서는 실선, 3차원에서는 평면을 결정 경계로 사용하여 구분하고 있다.
hard margin SVM = 예외 비허용 : 모든 점 초평면이 양쪽에 존재하고 margin 사이에는 점이 없다고 가정한다. 주로 선형 분리가 가능한 문제 - Support Vector의 수가 줄어들고 적은 샘플로 결정경계를 결정한다. - Overfitting의 우려가 있다.
soft margin SVM = 예외 허용 : 분류 오류를 0으로 만들지 않고 필요한 경우 몇 가지 오류를 포함한다. 주로 선형 분리가 불가능한 문제 - 거의 모든 샘플이 Support Vector가 된다. - Underfiting의 우려가 있다.
all positive points above the π(+) plane all negative points lie below the π(-) plane no points lie in between the margin
x_i : p차원의 실수 벡터 y_i : x_i가 어떤 class에 속해있는지를 나타내는 값, -1 또는 1의 값 w : 초평면의 법선 벡터(normal vector)
초평면 중심면 : w`x + b = 0 초평면 경계면 : w`x + b = 1 / w`x + b = -1 margin : 두 경계면 w`x + b = 1 와 w`x+b= -1 사이의 거리
- y_i는 -1 또는 1의 값을 가지며, 데이터 집합이 y_i값에 따라 선형적으로 분리
- point (x_i, y_i)는 초평면 외부 공간에 존재해야 하므로 모든 i에 대하여 y_i*(w'x_i + b) >= 1이 성립
1) 라그랑주 승수법 Lagrange multipliers
y_i*(w'x_i + b) >= 1 부등식 제약 조건을 만족하면서 Max{ 2/||w||} (혹은 Min{||w||²/2}) 구해야한다.
라그랑주 승수법을 이용해 목적 함수를 작성한다.
maximize margin 2/||w|| (혹은 minimize ||w||²/2) restricted to y_i*(w`_ix + b) >= 1
2) Primal form과 Dual form
- 라그랑주 승수법으로 구한 Lp는 Primal form 문제
- 라그랑주 문제는 일반적으로 Dual form으로 전환하여 해결한다.
- Lp는 w의 2차항만 가지는 convex 성질을 만족하고, KKT(Karush-Kuhn-Tucker) 조건을 만족하기 때문에 KKT 조건을 사용해 Wolfe’s Dual form 문제 Ld로 변환이 가능하다.
- primal form 문제가 maximizing이라면 dual form문제는 minimizing이 되고, 반대로 primal form 문제가minimizing이라면 dual form문제는 maximizing이 된다. SVM은 margin을 최대화하는 문제를 해결하는 것이므로 min을 찾는 Lp 문제 대신 max를 찾는 daul form 문제로 변환하여 해결하는 것이 더 편리하다.
3. Linear soft margin SVM
(위키백과)잘못 분류된 자료들을 허용하는 변형된 최대 마진 분류기 아이디어를 제안했다. 만약 “네” 또는 “아니오”라는 결과를 내야하는 자료들을 분할하는 초평면이 존재하지 않는다고 하자. 그러면 소프트 마진 방법은 여전히 가장 가까이 위치해 있는 제대로 분리되는 자료들의 거리를 최대화하면서, 주어진 자료들을 가능한 한 제대로 분리하는 초평면을 찾을 것이다.
not to make zero classification error in training but to make a few errors if necessary
ζ : 여유 변수(slack varibles) = 결정 경계에서 오분류된 데이터까지 거리 C : ζ가 얼마나 중요한지 알려 주는 매개변수, 일종의 penalty
- 분류 오류를 0으로 만드는 것이 아니라 필요한 최소한의 몇 가지 오류를 포함
1)slack varibles와 C
(위키백과) 이 방법은 음수가 아닌 느슨한 변수(영어: slack variable) ζ_i를 이용하는데, 이 변수는 자료 x_i가 잘못 분류된 정도를 나타낸다. 목적함수는 0이 아닌 ζ_i에 대해 페널티를 부과하는 함수에 의해서 증가된다. 그에 따른 최적화는 마진을 크게 하는 것과 에러에 대한 페널티를 작게 하는 것의 균형을 맞추는 것이 된다.
- margin을 최대한 크게 하며, 동시에 ζ>0인 테이터의 수를 최소화하는 결정 경계 방향 w를 찾는다.
- C값을 크게 잡으면 margin을 줄이는 대신 오분류된 점의 수를 최소화하려는 것으로, 과적합이 발생할 수 있다.
- C값을 작게 잡으면 margin을 늘리는 것을 중요시하지만 오분류가 증가하는 것으로, 과소적합이 발생할 수 있다.
2) Dual form
-soft margin SVM의 dual form의 경우값이 0과 C 사이에 있어야 하는 제약조건이 추가된다.
- Kernel Trick : 커널 함수를 이용해 저차원 데이터를 고차원으로 매핑(mapping)하고, 고차원에서 결정 경계를 찾는다.
- 저차원에서 비선형 형태의 데이터가 고차원에서 더 분리하기 쉬운 형태로 변환될 수 있음을 이용한다.
(위키백과) 비선형 분류 알고리즘은 기존의 선형 분류 알고리즘과 형태상으로 비슷하지만 내적 연산이 비선형 커널 함수로 대체된다. 이를 통해 변환된 특징 공간 (feature space)의 최대 마진 초평면 문제 해결을 할 수 있었다. 여기서 말하는 변환은 비선형 변환이거나 차원을 높이는 변환이 될 수 있다. 즉, 분류기는 고차원 특징 공간에서 선형 초평면이지만 기존 차원 공간 상에선 비선형 초평면이 된다.
