ML : Model : SVM 이란? / LDA vs SVM / SVM 정의

SVM이란?

 

Support Vector Machine(SVM)은 원 훈련(또는 학습)데이터를 비선형 매핑(Mapping)을 통해 고차원으로 변환한다.

이 새로운 차원에서 초평면(hyperplane)을 최적으로 분리하는 선형분리를 찾는다.

즉, 최적의 Decision Boundary(의사결정 영역)를 찾는다.

 

그렇다면 왜 데이터를 고차원으로 보내는 것일까? 예를 들어, 아래의 [그림1]과 같이 A=[a, d], B=[b, c]는 2차원에서 non-linearly separable(비선형 분리)하다. 이를 

통해 한 차원 높은 3차원으로 Mapping하게 되면 linearly separable(선형 분리)하게 된다. 따라서, 충분히 큰 차원으로 적절한 비선형 매핑을 이요하면, 두 개의 클래스를 가진 데이터는 초평면(hyperplane)에서 항상 분리될 수 있다.

SVM은 복잡한 비선형 의사결정 영역을 모형화 할 수 있기 때문에 매우 정확하며, 다른 모델들 보다 Over Fitting되는 경향이 적다.

 

SVM을 쓰는 이유 (고차원)

출처: https://excelsior-cjh.tistory.com/66 [EXCELSIOR]

Support Vector Machine (SVM, 서포트 벡터 머신)

---

SVM의 과정

다시 이 그림을 보자.

1. 우선 이 data는 같은 공분산 구조를 가질지는 모르지만, 정규분포를 따르지 않는 것을 보아 우리는 LDA는 안되고 SVM을 선택해야한다 라고 생각해야한다.

2. 그리고 선을 그었을 때, 점에 닿을 때 까지 margin을 최대한 늘려준다. (목적함수 : margin을 최대한 늘리자)

3. margin을 늘렸을 때, 혹시나 Error인 부분을(범주 k를 l로, 범주 l을 k로 classify 하는 경우) 적당한 error를 허용하고, 어느정도까지 수용할지 c를 조정한다. (조건함수 : Error를 최대한 줄이는 함수 내에서 목적함수인 margin을 최대한 늘리자.)

---

SVM의 종류

종속변수 데이터의 형태에 따라 범주형 변수와 연속형 변수로 나뉜다.

여기서 Model cost에 영향을 끼칠 점과 끼치지 않을 점을 margin을 통해 구분하는 것이 핵심이다.

 

범주형 변수 → SVM

흔히 범주형 변수, Classification이 일어나는 data는 SVM을 사용한다.

SVM에서는 1. margin 안에 포함되거나, 2. margin을 벗어나 반대방향으로 분류된 점, 이 두 가지를 보고 cost를 측정하며, 이 두 가지가 적게 나오도록 cost function을 최적화 시킨다.

 

연속형 변수 → SVR

반대로 연속형 변수, Classification 이 일어나는 data는 SVR을 사용한다.

SVR은 말 그대로 선형회귀이다. SVM에서 쓰던 margin, Error를 다루는 개념을 그대로 반대로 적용만 한 것이다.
margin을 늘려나감으로써 최대한 많은 점을 margin에 넣고자 포함되지 않는 점들에 대해 Error를 주어, 선에 가깝게 최적화한다.
이러한 최적화를 통해 총 Error를 최소화한다. 이는 margin 바깥의 data 에 대해서만 penalty를 부여한다.

---

SVM의 정의

> β를 평면의 법선벡터로 하는 초평면이 SVM의 Model Function이다.
> Decision Rule 에서 yi(xiTβ + β0) >0 이어야 하는 이유:
yi=1이라는 것은 초록색 집단을 의미하며, 초록색 집단은 초평면 위에 있기 때문에 0보다 크다. 따라서 곱은 양수
yi=-1 이라는 것은 빨간색 집단을 의미하며, 빨간색 집단은 초평면 밑에 있기 때문에 0보다 작으며, 따라서 곱은 양수이다.
올바른 결과가 나오려면 yi(xiTβ + β0) >0 가 유지되야 한다.

> cf) 왜 xiTβ + β0 >= 1 or xiTβ + β0 <= 1이어야 하는지? (내가 헷갈린 부분)
우리는 어떤 β를 잡아야하는지 어떤 β0를 잡아야하는지 전혀 모른다.
단지 β가 중심선과 직교하는 것만 알고 있다.
따라서 decision rule의 식이 최소한 1보다는 큰 값을 주도록 설정한 것이다. (왜 1인지 몰랐었음.... 그리고 1로 지정한 이 부분은 나중에 Largrange 쓰면서 미분으로 없어지는 부분이니 걱정 안해도 된다.)
그리고 y=1, -1 일 때가 초록색, 빨간색이기에 1보다 커야하고, -1보다 작아야 같은 범주안에 들기 때문에 마지노선을 1로 정한 것 이다.
1보다 작은 것은 오류의 위험을 가지고 있어서 제하는 것으로 생각한다.

cf ) M의 크기 (처음에 내가 몰랐음...)

M의 크기 구하는 방법

출처 : https://ratsgo.github.io/machine%20learning/2017/05/23/SVM/

서포트 벡터 머신 (Support Vector Machine) · ratsgo's blog

Cost Function 관점 (목적 함수)

cost function

1. β의 절댓값을 최소화 하자. 그렇다면 Margin을 늘어날 것이다.

 

margin의 크기가 최대가 되어야 두 그룹을 잘 분류하는 model을 만들 수 있다.

이는 distance가 2/||w=β||=이다. max(margin) 라면, 같은의미로 만들려면 min(1/2(||w=β||)**2) 해야한다.

또한 ξ는 Classfication을 잘못했을 때, 분류에 속해야하는 margin의 끝에서 그 data간의 거리이다. 즉 오차율이다.

Error가 최소가 되어야 두 그룹을 잘 분류하는 model이 된다. 즉 Error를 포함하더라도 최소화하는 Margin의 최댓값을 알아내야 한다. Margin의 최댓값을 알아내는 것은 베타의 최솟값을 아는 것과 동일하다.

 

2. C가 크면 ξ가 낮아져야한다. 따라서 C가 크면 오차율도 크게 줄어들 것이다.

C가 무한대이면 margin 안에 있는 Error 의 거리, ξ은 0이어야 하므로, 오류를 포함하지 않겠다는 것이다.

 

따라서 min (1/max(margin) + Cξ) 을 cost function으로 잡았다.

 

subject to (조건 함수)

3. ξ 는 무조건 거리이기 때문에, 0보다 크다.

 

4. yi(xiTβ + β0) >= 1, 원래 decision rule은 1보다 크게 정해놓았다. (위에 정리해두었다.) 이 decision rule에서 오차율을 포함하는 식으로 yi(xiTβ + β0) >= 1-ξ 를 만들었다.

ξ가 1보다 작다면, margin이 ξi보다 줄어들어도 어느정도 허용을 하겠다는 의미이다.

ξ가 1보다 크다면, yi(xiTβ + β0) >= 1-ξ 에서 1-ξ가 원래는 양수를 띄는 조건을 가져야 하는데 음수를 띈다.

이는 우리가 정해둔 조건, 각자 분류에 맡게 지정한 초평면을 구역을 지나서 잘못된 초평면 위에 있다는 의미,

즉 분류가 잘못됬다고 볼 수 있다.

Lagrange Multiplier 도입 (목적 - 조건)

라그랑주 승수법 도입

yi(xiTβ + β0) >= 1-ξi, ξi>0 조건함수를 만족하는 min (1/max(margin) + Cξ)인 cost function 목적함수의 해는

위의 식을 최소화하는 β, β0, ξi 값을 찾아줄 것이다.

각 세가지 변수에 대해 미분한 이유는 미분값이 0일때가 Largrange Function이 min 한 값을 가지기 때문이다.

위는 각 세가지 변수로 미분할 결과를 모두 ai로 표현하기위해 (ai만 구하면 모든게 해결, 모든 변수에 ai가 있다.)

Lp->LD

미분한 해를 대입하여 Lp -> LD 식으로 바꾼결과 다음과 같다.

중간에 위의 식을 최소화시키는 ai hat을 알고리즘을 통하여 구한다고 되어있는데, 이는 컴퓨터가 계산하며, 복잡한 식이라 여기서는 생략했다.

중간에 위의 식을 최소화시키는 ai hat을 알고리즘을 통하여 구하고, β hat = Σαxy 이기 때문에, 초평면의 법선벡터를 구할 수 있다.

---

Karush-Khun-Tucker-conditions

LP -> LD 식에서 옆에 3가지 조건을 만족한다면, LD식을 최소화하는 ai를 찾기위한 식이다.

 

그래프 중에서 4차함수처럼 미분값이 여러개라서 최솟값이 딱 정해지지 않을 때, KKT 식을 사용하면 최솟값과 일정하다를 의미한다.

 

세번째 식은 SVM 정의상에서 이미 만족하였다.

 

첫번째 식이  제일 우리한테는 관건이다.

i) ai = 0 이라면 : yi(xiTβ + β0) - (1-ξi) 이 0이 아니다. 이는 이미 만족하는 값이며, 평면 위에 있는 점들에 해당한다.

ii) yi(xiTβ + β0) - (1-ξi) = 0 이라면 : ai가 0이 아니며, 이는 margin 양 끝에 존재하는 초평면 위에 있는 점들에 해당한다. 우리는 이 margin 평면 위에 있는 점들, i에 해당하는 점들을 support vector 라고 한다. (β = Σαxy 인데 여기서 α가 0이 버리면 초평면의 법선벡터가 사라지게 되기 때문에, 무조건 우리는 두 번째 조건을 사용해야 한다.)

---

정리

• SVM은 이진분류하는 ML model로 주로 쓰이며, decision rule은 처음 평면의 법선벡터를 최소 단위벡터라고 지정을 하였다.
• SVM의 목적함수는 최대 margin을, margin의 길이가 법선벡터의 길이에 반비례 하므로 최소의 법선벡터의 길이를 가지되 Error를 포함하는 Model이다.
• SVM의 조건함수는 데이터의 오차의 거리는 항상 양수이며, yi(xiTβ + β0) >= (1-ξi) 이다.
• KKT 조건은 만족을 한다고 가정해야한다.
• 목적함수와 조건함수를 Largrange Function으로 변환 후, 미분을 하여 β, β0, ξi 을 ai로 변환한 값을 찾을 것이다.
• β, β0, ξi 를 ai로 표현하는 행위는 하나의 식으로 만들기 위함이다. Lp를 LD ai 관련된 식으로 바꾼다.
• LD 식에서 최소화시키는 ai 를 알고리즘을 통해 구할 수 있고, 초평면은 β hat = Σαxy 이기 때문에, 구할 수 있다.