핸즈온 머신러닝 2 chap 5 SVM

5.1 선형 SVM 분류

왼쪽 그래프에서 만들어진 결정경계 2개 중 어떤게 더 좋은 경계일까 답은 오른쪽과같은 경계로 경계로부터 샘플까지 거리가 가장 먼 경계이다. 이르 라지 마진 분류(large margin classification) 하고 한다.

 

5.1.1 소프트 마진 분류 (soft margin classification)

모든 샘플이 경계로부터 점선 밖에 존재한다면 이는 하드 마진 분류 (hard margin classification) 이라함. 

하드 마진분류는 단점이 2개 있음. 1. 선형적으로만 구분 될수 있으며 2. 이상치에 민감함.

왼쪽과 같이 샘플이 분포되어 있으면 하드마진을 찾을수가 없다.

이를 조금 유연하게 한것이 소프트 마진 이다.

소프트 마진은 마진 오류 (margin violation) 을 적당히 봐주는것.

SVM 만들때 C 라는 parameter 가 있는데 이를 높게 설정할수록 하드마진에 가까워 진다.

(※ SVM 이 overfitting 이라면 C 를 감소히켜 모델을 규제할 수 있다.)

 

5.2 비선형 SVM 분류

선형만으로 분류가 불가능한경우도 존재한다. 이런경우에는 특성을 추가해서 차원을 늘려 선형적으로 구분하도록 만드는 것.

왼쪽의 경우 구분이 힘들지만 오른쪽처럼 차원을 확장시킨경우 선형으로 구분이 가능하다.

 

5.2.1 다항식 커널

SVM 은 커널 트릭(Kernel trick) 을 사용. 실제 특성을 추가하지는 않지만 여러 특성을 추가한것과 같은 효과를 낼수있는것.

그럼 이와같은 경계를 만드는 것도 가능함.

 

5.2.2 유사도 특성

 

비선형을 다루는 또다른 방법중 랜드마크(ladnmark) 와 얼마나 닮았는지 측정하는 유사도 함수(similarity function) 이있음.

그럼 랜드마크는 어떻게 만드느냐? 간단히는 모든 샘플을 랜드마크로 설정하는 방법. 이러면 차원이 매우 커지게되고 선형적으로 구분될 가능성이 높다. 대신 n개의 특성 m 개의 샘플이 m개의 특성, m개의 샘플로 바뀐다는것. 또 샘플수가 많으면 동인한 크기의 아주많은 특성이 만들어짐.

가우시안 RBF

5.2.3 가우시안 RBF 커널

RBF 커널 사용시 유사도 특성을 많이 추가하는것과 비슷한 결과를 얻을 수 있다. 여기서 감마값을 올려주면 bell 모양이 더 좁아지게 되고decision boundary 가 더 불규칙적으로 변하게 된다. 즉 오버피팅되면 감마값을 줄여야 하고 언더피팅시 증가시키면 된다.

문자열 커널(string kernel) 은 텍스트 문서나 DNA 서열을 분류할 때 사용

 

5.2.4 계산 복잡도

LinearSVC 는 O(m*n) 의 시간복잡도를 가짐. 정밀도를 높이면 알고리즘 수행시간이 길어지고 이는 허용오차 ε를 이용하여 조절 가능.

SCV 커널트릭은 O(m^2 * n) ~ O(M^3 * n) 사이다. 즉 샘플수가 많아지면 엄청 느려진다는 뜻이다. 하지만 희소 특성(sparse feature) 즉 샘플에 0이 아닌 특성이 몇개 없는경우 에는 잘 확장됨. 이런경우는 알고리즘 성능이 샘플이 가진 0 이아닌 특성수의 평균수에 비례한다고함.

 

5.3 SVM 회귀

선형 비선형 분류 뿐만아니라 선형/비선형 회귀에서도 사용가능함. 적용방법은 목표를 반대로 하는거임. 한마디로 일정한 마진 오류 안에 셈플이 최대한 많이 들어가도록 학습하는것. 도로폭은 ε 로 조절한다.

마진안에서는 샘플이 추가되어도 모델의 예측에는 영항이 없다, 그래서 ε에 민감하지 않다(ε-insensitive) 라고 말함.

 

5.4 SVM 이론

표기법 정리 편향 = b ,가중치벡터 = w

 

5.4.1 결정 함수와 예측

위와 같은 실을통해 x 의 클래스를 예측함. 0보다크면 양성클래스(1) 아니면 음성클래스(0) 로 분류됨.

선형 SVM 을 훈련한다는 것은 마진오류가 없거나 제한적인 오류를 가지면서 가능한 큰 마진을 가지게하는 w와 b를 찾는것이다.

 

5.4.2 목적함수

결정함수의 기울기는 ||w|| 와 같다. 이 기울기를 2로 나누면 결정함수의 값이 ±1이 되는 점들이 결정 경계로부터 2배 멀어진다. 즉 기울기를 2로 나누는것은 마진에 2를 곱하는 것과 같은것이다.

즉 마진을 크게 하기위해 ||w|| 를 최소화 하면 됨. 또 모든 양성샘플은 1보다 크고 음성은 -1보다 작아야함.

여기서 t 는 양성에는 1 음성에는 -1인 값

그러면 위 식으로 표현이 가능하다.

이젠 SVM의 목적함수를 제약이 있는 최적화(constrained optimization)문제로 표현 가능함.

1/2 는 나중에 간략화를 위해 있는 상수

위 식은 당연히 하드 마진의 경우이고 소프트 마진의 경우는 슬랙변수(slack variable) ζ >= 0를 같이 써줘야함. 𝜁 는 i 번째 샘플이 얼마나 마진을 위반할지 정하는것. 그리고 파라미터 C 가 등장하는 이는 두 목표사이의 트레이드 오프를 정의

 

5.4.3 콰드라틱 프로그래밍

선형적인 제약조건이 있는 볼록함수의 이차 최적화 문제를 쿼드라틱 프로그래밍 (quadratic programmin) QP 라고 함.

이미 준비되어있는 QP 알고리즘에 관련된 파라미터를 전달하는것으로 훈련시킬수 있음.

비슷하게 소프트 마진에서도 QP 알고리즘을 사용할수있음.

 

5.4.4 쌍대 문제

원문제 (primal problem) 이라는 제약이 있는 최적화 문제가 주어지면 쌍대문제(dual problem) 라고하는 관련된 문제로 표현할 수 있다. 쌍대는 원문제의 하한인데 어떤 조건하에서는 같은 해를 낸다. SVM 은 해당 조건을 만족하므로 원문제 또는 쌍대문제중 하나로 선택해서 풀 수 있다.

이때 최소화 하는 α_hat 을 찾았다면 아래식을 통해 w 와 b 를 계산할 수 있다.

((훈련의 샘플수 < 특성의 수)) 일때는 쌍대 문제를 푸는게 더 빠르다. + 원 문제에서는 적용이 안되는 커널트릭이 가능하다.

 

5.4.5 커널 SVM

2차원을 3차원으로 매핑해주는 ∅ 가 있다고 하자

이때 점곱(dot product)를 해보자

변환된 벡터의 점곱은 원래 벡터의 점곱의 제곱이랑 같다.

실제로 훈련샘플을 변환할 필요는 없다는 것이다. 제곱으로만 바꾸면 된다.

값은 실제로 어렵게 변환후 SVM을 적용하는것과 완전히 같다. 대신 계산측면에서 훨싼 효율적이다.

 

커널트릭을 사용시 예측식에 ∅을 포함해야함. w의 차원이 매우 크거나 무한한 ∅의차원과 같아져야 함으로

계산이 불가능해짐.  하지만 사용은 가능함.      

서포트 벡터만 a^(i) != 0 이기에 전체샘플이 아니라 서포트벡터와 새 입력 벡터 X간의 점곱만 계산하면 된다. 물론 b_hat 도 커널트릭을 사용해 계산해야 한다.

 

 

5.4.6 온라인 SVM

새로운 샘플이 들어왔을때 점진적으로 학습하는거

 

힌지손실 (hinge loss)

max(0,1-t) 형태를 힌지손실이라고함 

미분 불가능 지점에서는 라쏘 회귀 때처럼 서브 그레디언트를 사용하면 경사 하강법 사용 가능하다.

 

 

 

 

SVM 쌍대 문제

일단 라그랑주 승수법 (Lagrange multiplier method 를 이해해야함).

ex) 등식 제약(equality constraint) 3x+2y+1=0 에서   f(x,y) = x^2+2y 를 최소화 하는 x,y 를 찾아보자

먼저 라그랑주 함수 (Lagrangian function) 을 정의

이때 정류점(stationary point) 를 찾아야함. -> 모든 편도함수가 0인 지점

0일때 나온 x,y,a 값이 하나면 제약있는 최적화 문제의 해가 됨.

하지만 이방법은 동등성 제약에만 적용. 다만 어떤 정칙조건(regularity condition)을 만족할경우 부등식 제약(inequality constraint)에서도 일반화 될 수 있음.

여기서는 그냥 알파 대신 KKT(Karush-Kuhn-Tucker)승수 를 사용 (0보다 큰 알파들)

 

이때 하드마진을 위한 일반화된 라그랑주 함수는

그럼 KKT 조건을 만족하는 점류점 (w_hat,b_hat,alpha_hat)중에 해가 있다.

w와 b에 대해 일반화된 라그랑주 함수의 편도함수는 아래 식과같이 계산 할 수 있다.

 

편도함수를 0으로 하면

정류점의 속성

이 결과를 일반화된 라그랑주 함수 정의에 대입하면 일부항 제거되고

가 된다.

이제 이 함수를 최소화 하고 alpha_hat 을 찾아야 한다.

찾았다면 

를 통해 w_hat 을 계산할 수 있다.

b_hat 은 

을 통해 구할 수 있다. k 번쨰 샘플이 서포트 벡터라면 그냥 식을 넘기고 계산할 수 있지만 안정적으로 더 정확한 값을 계산하기 위해서는 모든 서포트 벡터에 대해 평균을 구한다.