41. Python - SVM 이론 2

오늘은 SVM 이론의 두 번째 파트를 공부해보겠습니다.

[쌍대 문제]

원 문제(Primal problem)라는 제약이 있는 최적화 문제가 주어지면 쌍대 문제(dual problem)라고 하는 깊게 관련된 다른 문제로 표현할 수 있습니다. 일반적으로 쌍대 문제 해는 원 문제 해의 하한값이지만, 어떤 조건 하에서는 원 문제와 똑같은 해를 제공합니다.

다행히도, SVM 문제는 이 조건을 만족시킵니다. (목적 함수가 볼록 함수이고, 부등식 제약 조건이 연속 미분 가능하면서 볼록 함수입니다.) 따라서 원 문제 또는 쌍대 문제 중 하나를 선택하여 풀 수 있습니다.

(LinearSVC, LinearSVR의 매개변수 dual의 기본값 True를 False로 변경하면 원 문제를 선택하고, SVC, SVR은 쌍대 문제만 풉니다.)

아래의 식이 선형 SVM 목적 함수의 쌍대 형식입니다.

[선형 SVM 목적 함수의 쌍대 형식]

이 식을 최소화하는 벡터 을 찾았다면, 아래의 식을 사용해 원 문제의 식을 최소화하는 과 을 계산할 수 있습니다.

[쌍대 문제에서 구한 해로 원 문제의 해 계산하기]

훈련 샘플 수가 특성 개수보다 작을 때 원 문제보다 쌍대 문제를 푸는 것이 더 빠릅니다.

더 중요한 것은, 원 문제에서는 적용이 안 되는 커널 트릭을 가능하게 합니다. 그렇다면 커널 트릭은 도대체 무엇일까요?

[커널 SVM]

moons 데이터셋과 같은 2차원 데이터셋에 2차 다항식 변환을 적용하고 선형 SVM 분류기를 변환된 훈련 세트에 적용한다고 합시다. 아래의 식은 우리가 적용하고자 하는 2차 다항식 매핑 함수 입니다.

[2차 다항식 매핑]

변환된 벡터는 2차원이 아니고 3차원이 됩니다. 두 개의 2차원 벡터 a와 b에 대해 2차 다항식 매핑을 적용한 다음 변환된 벡터로 점곱(dot product)을 하면 어떻게 되는지 살펴봅시다.

결과가 어떤가요? 변환된 제곱의 점곱이 원래 벡터의 점곱의 제곱과 같습니다.

핵심은 다음과 같습니다. 모든 훈련 샘플에 변환(phi)를 적용하면 쌍대 문제에 접곱이 포함될 것입니다.

하지만 phi가 2차 다항식 변환이라며녀 변환된 벡터의 점곱을 간단하게 점곱의 제곱으로 바꿀 수 있습니다.

그래서 실제로 훈련 샘플을 변환할 필요가 전혀 없습니다. (즉, 점곱을 제곱으로 바꾸기만 하면 됨)

결괏값은 실제로 훈련 샘플을 어렵게 변환해서 선형 SVM 알고리즘을 적용하는 것과 완전히 같습니다.

하지만 이 기법이 전체 과정에 필요한 계산량 측면에서 훨씬 효율적입니다. 바로 이것이 커널 트릭입니다.

함수 를 2차 다항식 커널이라고 부릅니다. 머신러닝에서 커널은 변환(phi)를 계산하지 않고, 

또는 phi를 모르더라도, 원래 벡터 a와 b에 점곱을 계산할 수 있는 함수입니다.

아래는 가장 널리 사용되는 커널의 일부를 나열하였습니다.

*네 개의 커널이 사이킷런의 SVC, SVR에서 매개변수 kenel에 지정할 수 있는 함수입니다.

*선형은 linear, 다항식은 poly, 가우시안 rbf는 rbf, 시그모이드는 sigmoid로 지정합니다.

*시그모이드 함수는 로지스틱 함수나 tanh함수와 같이 S자 모양의 곡선을 갖는 함수를 말합니다.

# 머서의 정리

머서의 정리(Mercer's theorem)에 따르면 함수 K(a,b)가 머서의 조건(K가 매개변수에 대해 연속, 대칭임. 즉, K(a,b) K(b,a) 등) 이라 부르는 몇 개의 수학적 조건을 만족할 때, a와 b를 (더 높은 차원의) 다른 공간에 매핑하는 와 같은 함수 가 존재합니다. 그래서 를 모르더라도 가 존재하는 것은 알기 때문에 K를 커널로 사용할 수 있습니다.

가우시안 RBF 커널의 경우 는 각 훈련 샘플을 무한 차원의 공간에 매핑하는 것으로 볼 수 있습니다.

따라서 실제로 매핑하지 않는 것이 다행입니다.

자주 사용하는 일부 커널(예를 들면 시그모이드 커널)은 머서의 조건을 모두 따르지 않지만, 일반적으로 실전에서는 잘 작동합니다. 

아직 언급하지 않았던 부분, 선형 SVM분류기일 경우 쌍대 문제를 풀어서 원 문제를 해결하는 식은 다음과 같습니다.

하지만 커널 트릭을 사용한다면, 결국 예측 식에 를 포함해야 합니다. 의 차원이 매우 크거나, 무한한 의 차원과 같아져야 하므로 이를 계산할 수 없습니다. 그렇다면, 를 모른 채로 예측을 만들 수 있을까요?

다행히도, 에 대한 식(위에서 봤던) 을 새로운 샘플 의 결정 함수에 적용해서 입력 벡터 간의 점곱으로만 된 식을 얻을 수 있습니다. 이렇게 하면 커널트릭을 사용할 수 있게 되어, 아래의 식이 됩니다.

[커널 SVM으로 예측하기]

서포트 벡터만 이기 때문에 예측을 만드는 데는 전체 샘플이 아라 서포트 벡터와 새 입력 벡터 간의 점곱만 계산하면 됩니다. 물론 편향 도 커널 트릭을 사용해 계산해야 합니다.

[ 커널 트릭을 사용한 편향 계산 ]

머리가 아픈건 당연하다네요.

전 눈으로 이해하려고 노력하는 중입니다..ㅋㅋㅋ

커널 트릭으로 생기는 부수적 효과중 하나라고 합니다. 자연스러운 효과 ㅋㅋ..

[ 힌지 손실 ]

max(0, 1-t) 함수를 힌지 손실(hinge loss) 함수라고 부릅니다. 

이 함수는 t가 1보다 크거나 같을 때, 0입니다. 이 함수의 도함수(기울기)는 t<1이면 -1이고, t>1이면 0입니다.

t=1에서 미분 가능하지 않지만, 라쏘 회귀처럼 t=1에서 서브 그래디언트를 사용해 경사 하강법을 사용할 수 있습니다.

(즉, -1과 0 사이의 값을 사용합니다.)

자 드디어 SVM 장이 끝났는데요. 

정말 머리아프고 무슨 말인지 잘 이해가 안되는 부분도 많았네요.

부족한 게 많은 것 같습니다. ㅠㅠ

 블로그 

출처

이 글의 상당 부분은  [핸즈온 머신러닝, 한빛미디어/오렐리앙 제롱/박해선] 서적을 참고하였습니다.

나머지는 부수적인 함수나 메서드에 대해 부족한 설명을 적어두었습니다.

학습용으로 포스팅 하는 것이기 때문에 복제보다는 머신러닝에 관심이 있다면 구매해보시길 추천합니다.

도움이 되셨다면 로그인 없이 가능한

아래 하트♥공감 버튼을 꾹 눌러주세요!