선형 SVM 분류
두 클래스를 선형으로 분류
선 1개로 클래스를 잘 분류해야 함
이때 결정 경계가 샘플에 너무 가까우면 좋지 않음.
멀어야 혹시나 관측하지 못한 데이터를 잘 예측할 수 있음
∴ \therefore ∴ 폭이 가장 넓은 도로를 찾는 것이 목표
⇒ \Rarr ⇒ Large Margin Classification
결정 경계로부터 가장 가까운 샘플에 의해 전적으로 의지
이러한 샘플을 서포트 벡터 라고 함.
서포트 벡터보다 더 경계와 가까운 곳에 해당 클래스 샘플이 생겨나도 문제가 되지 않음
하드 마진 분류
모든 샘플이 도로(서포트 벡터를 지나는 경계와 평행한 선) 바깥쪽에 올바르게 분류하는 상황
이는 데이터가 선형적으로 구분되어야 함
또한 이상치에 민감하다.
위 문제를 피하기위해 더욱 유연한 모델 사용
도로 폭 너비와 마진 오류 사이의 적절한 균형 잡아야 함
⇒ \Rarr ⇒ 소프트 마진 분류
소프트 마진 분류
일정 수준의 오류 수용
도로 폭 너비와 마진 오류 사이의 적절한 균형
하이퍼 파라미터 C
는 마진 오류 조절
C
가 높을 수록 적은 마진 오류를 택한다.
in scikit-learn
from sklearn. linear_model import SGDClassifier
from sklearn. svm import SVC, LinearSVC
svm_clf = LinearSVC( C= 1 , loss= 'hinge' )
svc = SVC( kernel= "linear" , C= 1 )
sgd_clf = SGDClassifier( loss= "hinge" , alpha= 1 / ( m* C) )
비선형 SVM 분류
데이터를 선형으로 분류할 수 없는 경우가 많다.
Polynomial Features(다항 특성)와 같은 feature를 더욱 추가
polynomial_svm_clf = Pipeline( [
( "poly_features" , PolynomialFeatuers( degree= 3 ) ) ,
( "scaler" , StandardScaler( ) ) ,
( "svm_clf" , LinearSVC( C= 10 , loss= "hinge" ) )
] )
다항식 커널
낮은 차수의 다항식은 매우 복잡한 데이터셋을 잘 표현하지 못하고, 높은 차수의 다항식은 굉장이 많은 특성을 추가해 모델을 느리게 만듦
커널 트릭 사용
실제로는 특성을 추가하지 않으면서 다항식 특성을 많이 추가한 것과 같은 결과 냄
poly_kernel_svm_clf = SVC( kernel= "poly" , degree= 3 , coef0= 1 , C= 5 )
3차 다항식 커널을 통해 SVM 분류기 훈련
coef0
: 모델이 높은 차수와 낮은 차수에 얼마나 영향을 받을지 조절
유사도 특성
각 샘플이 특정 랜드마크와 얼마나 닮았는지 측정해 특성으로 추가
방사 기저 함수(Radial Basis Function; RBF)
ϕ γ ( x , l ) = e − γ ∣ ∣ x − l ∣ ∣ 2 \phi_\gamma (x,l) = e^{-\gamma||x-l||^2} ϕ γ ( x , l ) = e − γ ∣ ∣ x − l ∣ ∣ 2
랜드 마크에서 아주 멀리 떨어진 경우(0 )부터 랜드마크와 같은 위치(1 )까지 변화하며 종 모양으로 나타냄
ex) x 1 = − 1 x_1 = -1 x 1 = − 1 , 첫번째 랜드마크에서 1만큼 떨어져 있고, 두번째 랜드마크에서 2만큼 떨어져 있다.
γ = 0.3 \gamma = 0.3 γ = 0 . 3
x 2 = e − 0.3 ∗ 1 2 ∼ 0.74 , x 3 = e − 0.3 ∗ 2 2 ∼ 0.30 x_2 = e^{-0.3 * 1^2} \sim 0.74, x_3 = e^{-0.3 * 2^2} \sim 0.30 x 2 = e − 0 . 3 ∗ 1 2 ∼ 0 . 7 4 , x 3 = e − 0 . 3 ∗ 2 2 ∼ 0 . 3 0
∴ ( x 2 , x 3 ) = ( 0.74 , 0.30 ) \therefore (x_2, x_3) = (0.74, 0.30) ∴ ( x 2 , x 3 ) = ( 0 . 7 4 , 0 . 3 0 )
랜드마크 선택 방법
모든 데이터 위 랜드마크 생성
차원이 매우 커진다.
선형으로 구분될 가능성이 높지만 훈련세트가 클수록 아주 많은 특성이 만들어짐
가우시안 RBF 커널
rbf_kernel_svm_clf = SVC( kernel= 'rbf' , gamma= 5 , C= 0.001 )
gamma
: 종 모양 그래프의 너비 조절
클수록 좁아지고 각 샘플의 영향 범위가 작아짐
→ \rarr → : 조금 더 불규칙해지고 구불구불해짐
규제의 역할
과대적합일 경우에는 감소시키고, 과소적합일 경우에는 증가시켜야 함
다른 여러가지 커널도 존재
문자열 커널, 문자열 서브시퀀스 커널, 레벤슈타인 거리 기반 커널 등
선형 커널을 통해 가장 먼저 시도해보고, 훈련 세트가 너무 크지 않다면 가우시안 RBF 커널 시도
계산 복잡도
LinearSVC
클래스는 선형 SVM을 위한 최적화된 알고리즘을 구현한 liblinear
라이브러리 기반으로 작동
커널 트릭을 지원하지는 않지만, 훈련 샘플과 특성 수에 거의 선형적으로 늘어남
훈련 시간 복잡도: O ( m ⋅ n ) O(m\cdot n) O ( m ⋅ n )
정밀도를 높이면 수행 시간 길어짐
허용오차 하이퍼파라미터 tol
로 조절 - 기본값으로 두면 잘 작동
SVC
는 커널 트릭 알고리즘을 구현한 libsvm
라이브러리 기반 작동
훈련 시간 복잡도 O ( m 2 ⋅ n ) , O ( m 3 ⋅ n ) O(m^2\cdot n), O(m^3 \cdot n) O ( m 2 ⋅ n ) , O ( m 3 ⋅ n )
복잡하지만 작거나 중간 규모의 훈련 세트에 적합
SVM 회귀
분류와 목표를 반대로
일정한 마진 안에서 두 클래스 간의 도로 폭이 가능한 최대가 되도록 하고, 제한된 마진 오류 안에서 도로 안에 가능한 많은 샘플이 들어가도록 학습
하이퍼파라미터 epsilon
: 도로의 폭 조절
ε \varepsilon ε 에 민감하지 않다
마진 안에 훈련 샘플이 추가되어도 모델 예측에 영향이 없음
from sklearn. svm import LinearSVR, SVR
svm_reg = LinearSVR( epsilon= 1.5 )
svm_poly_reg = SVR( kernel= 'poly' , degree= 2 , C= 100 , epsilon= 0.1 )
SVM 이론
선형 SVM 분류 모델은 단순히 결정 함수 w T x + b = w 1 x 1 + ⋯ + w n x n + b w^Tx + b = w_1x_1 + \dots + w_nx_n + b w T x + b = w 1 x 1 + ⋯ + w n x n + b 를 계산
예측값이 0보다 크면 양성 클래스, 그렇지 않으면 음성 클래스
y ^ = { 0 w T x + b < 0 1 ≥ 0 \hat y = \begin{cases} 0 \;\; w^Tx + b < 0 \\ 1 \;\; \ge 0 \end{cases} y ^ = { 0 w T x + b < 0 1 ≥ 0
결정 경계: 결정 함수 값이 0인 점들로 이루어져 있음
n n n 개의 특성이 있을 때 결정 함수는 n n n 차원의 초평면, 결정 경계는 ( n − 1 ) (n-1) ( n − 1 ) 차원의 초평면
마진 오류를 최소화하며 마진을 최대화하는 w w w 와 b b b 를 찾도록 학습
W T x + + b = 1 w T ( x − + λ w ) + b = 1 ( w T x − + b ) + λ w T w = 1 − 1 + λ w T w = 1 λ = 2 w T w W^Tx^+ + b = 1 \\ w^T(x^- + \lambda w) + b = 1\\ (w^Tx^- + b) + \lambda w^T w = 1 \\ -1 + \lambda w^T w = 1 \\ \lambda = \cfrac{2}{w^T w} W T x + + b = 1 w T ( x − + λ w ) + b = 1 ( w T x − + b ) + λ w T w = 1 − 1 + λ w T w = 1 λ = w T w 2
M a r g i n = d i s t a n c e ( x + , x − ) = ∣ ∣ x + − x − ∣ ∣ 2 = ∣ ∣ ( x − + λ w ) − x − ∣ ∣ 2 = ∣ ∣ λ w ∣ ∣ 2 = λ w T w = 2 w T w w T w = 2 w T w = 2 ∣ ∣ w ∣ ∣ 2 Margin = distance(x^+, x^-)\\ = ||x^+ - x^-||_2 = ||(x^- + \lambda w) - x^-||_2\\ = ||\lambda w||_2 = \lambda \sqrt{w^Tw} = \cfrac{2}{w^T w}\sqrt{w^T w} \\ = \cfrac{2}{\sqrt{w^T w}} = \cfrac{2}{||w||_2} M a r g i n = d i s t a n c e ( x + , x − ) = ∣ ∣ x + − x − ∣ ∣ 2 = ∣ ∣ ( x − + λ w ) − x − ∣ ∣ 2 = ∣ ∣ λ w ∣ ∣ 2 = λ w T w = w T w 2 w T w = w T w 2 = ∣ ∣ w ∣ ∣ 2 2
max M a r g i n = max 2 w T w = min w T w 2 \max Margin = \max \cfrac{2}{\sqrt {w^T w}} = \min \cfrac{\sqrt{w^Tw}}{2} max M a r g i n = max w T w 2 = min 2 w T w
목적 함수
결정 함수의 기울기는 가중치 벡터의 노름(∣ ∣ w ∣ ∣ ||w|| ∣ ∣ w ∣ ∣ )과 같다.
이 기울기를 2로 나누면 결정 함수의 값이 ± 1 \pm 1 ± 1 이 되는 지점의 점들이 결정 경계로부터 2배 멀어짐
기울기를 2로 나누는 것은 마진에 2를 곱하는 것과 같음
마진을 크게 하기 위해 ∣ ∣ w ∣ ∣ ||w|| ∣ ∣ w ∣ ∣ 를 최소화
마진 오류 최소화를 위해서는 결정 함수가 모든 양성 훈련 샘플은 최대한 1보다 커야하고, 모든 음성 훈련 샘플은 최소한 -1보다 작아야 함
음성 샘플(y ( i ) = 0 y^{(i)}=0 y ( i ) = 0 )일 때 t ( i ) = − 1 t^{(i)}=-1 t ( i ) = − 1 로, 양성 샘플(y ( i ) = 1 y^{(i)}=1 y ( i ) = 1 )일 때 t ( i ) = 1 t^{(i)}=1 t ( i ) = 1
그러므로 목적 함수를 제약이 있는 최적화 문제로 표현 가능(하드 마진)
m i n i m i z e w , b 1 2 w T w t ( i ) ( w T x ( i ) + b ) ≥ 1 minimize_{w,b} \cfrac{1}{2}w^Tw\\ t^{(i)}(w^Tx^{(i)}+b) \ge 1 m i n i m i z e w , b 2 1 w T w t ( i ) ( w T x ( i ) + b ) ≥ 1
미분을 위해 ∣ ∣ w ∣ ∣ ||w|| ∣ ∣ w ∣ ∣ 가 아닌 1 2 ∣ ∣ w ∣ ∣ 2 \cfrac{1}{2}||w||^2 2 1 ∣ ∣ w ∣ ∣ 2 를 최소화(미분 불가능)
소프트 마진 분류기의 경우, 각 샘플에 대해 슬랙 변수 ζ ( i ) ≥ 0 \zeta^{(i)} \ge 0 ζ ( i ) ≥ 0 도입
ζ ( i ) \zeta^{(i)} ζ ( i ) 는 i i i 번째 샘플이 얼마나 마진을 위반할 지 정함
해당 문제는 상충되는 목표
마진 최대화를 위한1 2 ∣ ∣ w ∣ ∣ 2 \cfrac{1}{2}||w||^2 2 1 ∣ ∣ w ∣ ∣ 2 최소화
마진 오류 최소화를 위한 ζ ( i ) \zeta^{(i)} ζ ( i ) 최소화
하이퍼 파라미터 C
로 트레이드 오프 조절
C
가 커지면 ζ ( i ) \zeta^{(i)} ζ ( i ) 의 변화에 따른 손실 함수가 커져 ζ ( i ) \zeta^{(i)} ζ ( i ) 의 규제 효과 커짐
더 적은 마진 오류 수용한다는 의미
m i n i m i z e w , b , ζ 1 2 w T w + C Σ i = 1 m ζ ( i ) t ( i ) ( w T x ( i ) + b ) ≥ 1 − ζ ( i ) a n d ζ ( i ) ≥ 0 minimize_{w,b,\zeta} \cfrac{1}{2}w^Tw + C \Sigma^m_{i=1}\zeta^{(i)}\\ t^{(i)}(w^Tx^{(i)}+b) \ge 1 -\zeta^{(i)} \;\;and \;\; \zeta^{(i)} \ge 0 m i n i m i z e w , b , ζ 2 1 w T w + C Σ i = 1 m ζ ( i ) t ( i ) ( w T x ( i ) + b ) ≥ 1 − ζ ( i ) a n d ζ ( i ) ≥ 0
콰드라틱 프로그래밍(이차 방정식)
하드 마진과 소프트 마진 문제는 선형적인 제약 조건이 있는 볼록 함수의 이차 최적화 문제
이런 문제를 콰드라틱 프로그래밍이라고 함
m i n i m i z e p 1 2 p T H p + f T p 조건 : A p ≤ b minimize_p \cfrac{1}{2}p^THp+f^Tp\\ 조건: Ap \le b m i n i m i z e p 2 1 p T H p + f T p 조 건 : A p ≤ b
p p p : n p n_p n p 차원 벡터 (n p n_p n p : 모델의 파라미터 수)
H H H : n p ⋅ n p n_p \cdot n_p n p ⋅ n p 크기 행렬
f f f : n p n_p n p 차원 벡터
A A A : n c ⋅ n p n_c \cdot n_p n c ⋅ n p 크기 행렬 (n c n_c n c : 제약 수)
b b b : n c n_c n c 차원 벡터
A p ≤ b Ap \le b A p ≤ b : n c n_c n c 개의 제약 정의
QP 파라미터 지정 시, 하드 마진을 갖는 선형 SVM 분류기의 목적 함수 검증 가능
n p = n + 1 n_p = n+1 n p = n + 1 (∵ \because ∵ 편향, n n n : 특성 수)
n c = m n_c = m n c = m (m m m : 훈련 샘플 수)
H H H : 왼쪽 맨 위의 원소가 0인 것을 제외하고는 단위 행렬
f = 0 f = 0 f = 0 : 영 벡터
b = 1 b = 1 b = 1 : 일 벡터
a ( i ) = − t ( i ) x ˙ ( i ) a^{(i)} = - t^{(i)} \dot x^{(i)} a ( i ) = − t ( i ) x ˙ ( i )
x ˙ ( i ) \dot x^{(i)} x ˙ ( i ) : 편향을 위해 특성 x ˙ 0 = 1 \dot x_0 = 1 x ˙ 0 = 1 을 추가한 x ( i ) x^{(i)} x ( i )
결과 벡터 p p p 는 편향 b = p 0 b=p_0 b = p 0 와 특성 가중치 w i = p i w_i = p_i w i = p i 를 담음
커널 트릭을 위해서는 최적화 문제를 다른 형태로 바꿔야 함
쌍대 문제
원 문제라는 제약이 있는 최적화 문제를 쌍대 문제로 표현 가능
쌍대 문제는 원 문제 해의 하한값이지만 어떤 조건 하에서는 똑같은 해 제공
SVM은 해당 조건 만족
Lagrangian Primal 사용
L ( w , b , α ) = 1 2 ∣ ∣ w ∣ ∣ 2 2 − Σ i = 1 n α i ( y i ( w T x i + b ) − 1 ) L(w,b,\alpha) = \cfrac{1}{2}||w||^2_2 - \Sigma^n_{i=1} \alpha_i (y_i(w^Tx_i+b)-1) L ( w , b , α ) = 2 1 ∣ ∣ w ∣ ∣ 2 2 − Σ i = 1 n α i ( y i ( w T x i + b ) − 1 )
- ∂ L ( w , b , α ) ∂ w = 0 → w = Σ i = 1 n α i y i x i ∂ L ( w , b , α ) ∂ b = 0 → Σ i = 1 n α i y i = 0 \cfrac{\partial L(w,b,\alpha)}{\partial w} = 0 \rarr w = \Sigma^n_{i=1} \alpha_iy_ix_i \\ \cfrac{\partial L(w,b,\alpha)}{\partial b} = 0 \rarr \Sigma^n_{i=1} \alpha_iy_i = 0 ∂ w ∂ L ( w , b , α ) = 0 → w = Σ i = 1 n α i y i x i ∂ b ∂ L ( w , b , α ) = 0 → Σ i = 1 n α i y i = 0
w w w 계산을 위해서는 α \alpha α 만 알면 됨
1 2 ∣ ∣ w ∣ ∣ 2 2 = 1 2 w T w = 1 2 w T Σ j = 1 n α j y j x j = 1 2 Σ j = 1 n α j y j ( w T x j ) = 1 2 Σ j = 1 n α j y j ( Σ i = 1 n α i y i x i T x j ) = 1 2 Σ i = 1 n Σ j = 1 n α i α j y i y j x i T x j \cfrac{1}{2}||w||^2_2 = \cfrac{1}{2} w^Tw \\= \cfrac{1}{2}w^T\Sigma^n_{j=1} \alpha_jy_jx_j = \cfrac{1}{2} \Sigma^n_{j=1} \alpha_j y_j (w^T x_j) \\= \cfrac{1}{2} \Sigma^n_{j=1} \alpha_j y_j (\Sigma^n_{i=1} \alpha_i y_i x_i^T x_j) \\= \cfrac{1}{2} \Sigma^n_{i=1}\Sigma^n_{j=1} \alpha_i\alpha_jy_iy_jx_i^Tx_j 2 1 ∣ ∣ w ∣ ∣ 2 2 = 2 1 w T w = 2 1 w T Σ j = 1 n α j y j x j = 2 1 Σ j = 1 n α j y j ( w T x j ) = 2 1 Σ j = 1 n α j y j ( Σ i = 1 n α i y i x i T x j ) = 2 1 Σ i = 1 n Σ j = 1 n α i α j y i y j x i T x j
− Σ i = 1 n α i ( y i ( w T x i + b ) − 1 ) = − Σ i = 1 n α i y i ( w T x i + b ) + Σ i = 1 n α i = − Σ i = 1 n α i y i w T x i − b Σ i = 1 n α i y i + Σ i = 1 n α i = − Σ i = 1 n Σ j = 1 n α i α j y i y j x i T x j + Σ i = 1 n α i - \Sigma^n_{i=1} \alpha_i (y_i(w^Tx_i+b)-1) \\= -\Sigma^n_{i=1}\alpha_iy_i(w^Tx_i+b) + \Sigma^n_{i=1} \alpha_i \\ = -\Sigma^n_{i=1}\alpha_iy_iw^Tx_i - b\Sigma^n_{i=1} \alpha_i y_i + \Sigma^n_{i=1} \alpha_i \\ = - \Sigma^n_{i=1}\Sigma^n_{j=1}\alpha_i\alpha_jy_iy_jx_i^Tx_j + \Sigma^n_{i=1} \alpha_i − Σ i = 1 n α i ( y i ( w T x i + b ) − 1 ) = − Σ i = 1 n α i y i ( w T x i + b ) + Σ i = 1 n α i = − Σ i = 1 n α i y i w T x i − b Σ i = 1 n α i y i + Σ i = 1 n α i = − Σ i = 1 n Σ j = 1 n α i α j y i y j x i T x j + Σ i = 1 n α i
m i n i m i z e α 1 2 Σ i = 1 m Σ j = 1 m α ( i ) α ( j ) t ( i ) t ( j ) x ( i ) x ( j ) − Σ i = 1 m α ( i ) minimize_\alpha \cfrac{1}{2} \Sigma^m_{i=1} \Sigma^m_{j=1} \alpha^{(i)}\alpha^{(j)}t^{(i)}t^{(j)}x^{(i)}x^{(j)}-\Sigma^m_{i=1}\alpha^{(i)} m i n i m i z e α 2 1 Σ i = 1 m Σ j = 1 m α ( i ) α ( j ) t ( i ) t ( j ) x ( i ) x ( j ) − Σ i = 1 m α ( i )
해당 식을 최소화하는 벡터 α ^ \hat \alpha α ^ 를 찾았다면 원문제의 식을 최소화하는 w ^ \hat w w ^ , b ^ \hat b b ^ 계산 가능
w ^ = Σ i = 1 m α ^ ( i ) t ( i ) x ( i ) b ^ = 1 n Σ i = 1 m ( t ( i ) − w ^ T x ( i ) ) \hat w = \Sigma^m_{i=1} \hat \alpha^{(i)} t^{(i)} x^{(i)}\\ \hat b = \cfrac{1}{n} \Sigma^m_{i=1} (t^{(i)}-\hat w^T x^{(i)}) w ^ = Σ i = 1 m α ^ ( i ) t ( i ) x ( i ) b ^ = n 1 Σ i = 1 m ( t ( i ) − w ^ T x ( i ) )
원 문제를 통해 커널 트릭을 가능하게 함
커널 SVM
2차원 데이터셋에 2차 다항식 변환 적용해 선형 SVM 분류기 적용
ϕ ( x ) = ϕ ( ( x 1 x 2 ) ) = ( x 1 2 2 x 1 x 2 x 2 2 ) \phi(x) = \phi \begin{pmatrix}\begin{pmatrix} x_1\\ x_2 \end{pmatrix}\end{pmatrix} = \begin{pmatrix} x_1^2 \\ \sqrt 2x_1x_2\\ x_2^2 \end{pmatrix} ϕ ( x ) = ϕ ( ( x 1 x 2 ) ) = ⎝ ⎜ ⎛ x 1 2 2 x 1 x 2 x 2 2 ⎠ ⎟ ⎞
2개의 2차원 벡터 a a a , b b b 에 2차 다항식 매핑을 적용한 다음 점곱 적용
ϕ ( a ) T ϕ ( b ) = ( a 1 2 2 a 1 a 2 a 2 2 ) ( b 1 2 2 b 1 b 2 b 2 2 ) = a 1 2 b 1 2 + 2 a 1 b 1 a 2 b 2 + a 2 2 b 2 2 = ( a 1 b 1 + a 2 b 2 ) 2 = ( ( a 1 a 2 ) T ( b 1 b 2 ) ) = ( a T b ) 2 \phi(a)^T\phi(b) = \begin{pmatrix} a_1^2 \\ \sqrt2 a_1 a_2\\ a_2^2\end{pmatrix} \begin{pmatrix} b_1^2 \\ \sqrt 2 b_1 b_2 \\ b_2^2 \end{pmatrix} = a^2_1b_1^2 + 2 a_1b_1 a_2 b_2 + a_2^2 b_2^2\\ = (a_1b_1 + a_2b_2)^2 = \begin{pmatrix} \begin{pmatrix} a_1 \\ a_2 \end{pmatrix}^T \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \end{pmatrix} = (a^Tb)^2 ϕ ( a ) T ϕ ( b ) = ⎝ ⎜ ⎛ a 1 2 2 a 1 a 2 a 2 2 ⎠ ⎟ ⎞ ⎝ ⎜ ⎛ b 1 2 2 b 1 b 2 b 2 2 ⎠ ⎟ ⎞ = a 1 2 b 1 2 + 2 a 1 b 1 a 2 b 2 + a 2 2 b 2 2 = ( a 1 b 1 + a 2 b 2 ) 2 = ( ( a 1 a 2 ) T ( b 1 b 2 ) ) = ( a T b ) 2
변환된 벡터의 점곱이 원래 벡터의 점곱의 제곱과 같다.
ϕ ( a ) T ϕ ( b ) = ( a T b ) 2 \phi(a)^T\phi(b) = (a^Tb)^2 ϕ ( a ) T ϕ ( b ) = ( a T b ) 2
모든 훈련 샘플에 변환 ϕ \phi ϕ 를 적용하면 쌍대 문제에 점곱 ϕ ( x ( i ) ) T ϕ ( x ( j ) ) \phi(x^{(i)})^T\phi(x^{(j)}) ϕ ( x ( i ) ) T ϕ ( x ( j ) ) 포함
ϕ \phi ϕ 가 2차 다항식 변환이라면 변환된 벡터의 점곱을 간단하게 ( x ( i ) T x ( j ) ) 2 (x^{(i)^T}x^{(j)})^2 ( x ( i ) T x ( j ) ) 2 으로 바꿈
그래서 실제 훈련 샘플을 변환할 필요가 없이 쌍대식의 점곱을 제곱으로 바꾸기만 하면 됨
값은 실제로 변환해서 알고리즘을 적용한 값과 동일하지만, 계산량이 훨씬 효율적
2차 다항식 커널 = 함수 K ( a , b ) = ( a T b ) 2 K(a,b) = (a^Tb)^2 K ( a , b ) = ( a T b ) 2
커널 : 변환 ϕ \phi ϕ 를 계산하지 않고도 원래 벡터에 기반해 접곱 ϕ ( a ) T ϕ ( b ) \phi(a)^T\phi(b) ϕ ( a ) T ϕ ( b ) 를 계산하는 함수
커널 종류
선형: K ( a , b ) = a T b K(a,b) = a^Tb K ( a , b ) = a T b
다항식: K ( a , b ) = ( γ a T b + γ ) K(a,b) = (\gamma a^T b + \gamma) K ( a , b ) = ( γ a T b + γ )
가우시안 RBF: K ( a , b ) = e − γ ∣ ∣ a − b ∣ ∣ 2 K(a,b) = e^{-\gamma ||a-b||^2} K ( a , b ) = e − γ ∣ ∣ a − b ∣ ∣ 2
시그모이드: K ( a , b ) = tanh ( γ a T b + γ ) K(a,b) = \tanh(\gamma a^T b + \gamma) K ( a , b ) = tanh ( γ a T b + γ )
머서의 정리: 몇 개 수학적 조건을 만족할 때 ϕ \phi ϕ 를 모르더라도 존재하는 것을 알기 때문에 K K K 를 커널로 사용하는 것
커널 트릭 사용 시, 결국 예측 식에 ϕ ( x ( i ) ) \phi(x^{(i)}) ϕ ( x ( i ) ) 를 포함해야 함
w ^ \hat w w ^ 의 차원이 ϕ ( x ( i ) ) \phi(x^{(i)}) ϕ ( x ( i ) ) 와 같이 무수히 커져야 함을 의미
w ^ \hat w w ^ 에 대한 식을 x ( n ) x^{(n)} x ( n ) 의 결정 함수에 적용해 입력 벡터 간 점곱으로만 된 식을 얻을 수 있다.
h w ^ b ^ ( ϕ ( x ( n ) ) ) = w ^ T ϕ ( x ( n ) ) + b ^ = ( Σ i = 1 m α ^ ( i ) t ( i ) ϕ ( x i ) ) T ϕ ( x ( n ) ) + b ^ = Σ i = 1 m α ^ ( i ) t ( i ) ( ϕ ( x ( i ) ) T ϕ ( x ( n ) ) ) + b ^ = Σ i = 1 m α ^ ( i ) t ( i ) K ( x ( i ) , x ( n ) ) + b ^ h_{\hat w \hat b}(\phi(x^{(n)})) = \hat w^T \phi(x^{(n)}) + \hat b = (\Sigma^m_{i=1} \hat \alpha^{(i)}t^{(i)}\phi(x^{i}))^T \phi(x^{(n)}) + \hat b \\ = \Sigma^m_{i=1} \hat \alpha^{(i)} t^{(i)}(\phi(x^{(i)})^T \phi(x^{(n)})) + \hat b \ = \Sigma^m_{i=1} \hat \alpha^{(i)} t^{(i)} K(x^{(i)}, x^{(n)}) + \hat b h w ^ b ^ ( ϕ ( x ( n ) ) ) = w ^ T ϕ ( x ( n ) ) + b ^ = ( Σ i = 1 m α ^ ( i ) t ( i ) ϕ ( x i ) ) T ϕ ( x ( n ) ) + b ^ = Σ i = 1 m α ^ ( i ) t ( i ) ( ϕ ( x ( i ) ) T ϕ ( x ( n ) ) ) + b ^ = Σ i = 1 m α ^ ( i ) t ( i ) K ( x ( i ) , x ( n ) ) + b ^
b ^ \hat b b ^ 역시 커널 트릭으로 계산해야 함
b ^ = 1 n s Σ i = 1 m ( t ( i ) − w ^ T ϕ ( x ( i ) ) ) = 1 n Σ i = 1 m ( t ( i ) − ( Σ j = 1 m α ^ ( j ) t ( j ) ϕ ( x ( j ) ) ) T ϕ ( x ( i ) ) ) = 1 n s Σ i = 1 m ( t ( i ) − Σ j = 1 m α ^ ( j ) t ( j ) K ( x ( i ) , x ( j ) ) ) \hat b = \cfrac{1}{n_s} \Sigma^m_{i=1} (t^{(i)} - \hat w^T \phi(x^{(i)})) = \cfrac{1}{n} \Sigma^m_{i=1} (t^{(i)} - (\Sigma^m_{j=1} \hat \alpha^{(j)}t^{(j)}\phi(x^{(j)}))^T\phi(x^{(i)})) \\ = \cfrac{1}{n_s}\Sigma^m_{i=1} (t^{(i)} - \Sigma^m_{j=1} \hat \alpha^{(j)}t^{(j)}K(x^{(i)}, x^{(j)})) b ^ = n s 1 Σ i = 1 m ( t ( i ) − w ^ T ϕ ( x ( i ) ) ) = n 1 Σ i = 1 m ( t ( i ) − ( Σ j = 1 m α ^ ( j ) t ( j ) ϕ ( x ( j ) ) ) T ϕ ( x ( i ) ) ) = n s 1 Σ i = 1 m ( t ( i ) − Σ j = 1 m α ^ ( j ) t ( j ) K ( x ( i ) , x ( j ) ) )
온라인 SVM
원 문제로부터 유도된 비용 함수를 최소화하기 위한 경사 하강법 사용
QP 기반 방법보다 훨씬 느리게 수렴
J ( w , b ) = 1 2 w T w + C Σ i = 1 m max ( 0 , 1 − t ( i ) ( w T x ( i ) + b ) ) J(w,b) = \cfrac{1}{2}w^Tw+C\Sigma^m_{i=1} \max(0, 1-t^{(i)}(w^Tx^{(i)}+b)) J ( w , b ) = 2 1 w T w + C Σ i = 1 m max ( 0 , 1 − t ( i ) ( w T x ( i ) + b ) )
첫번째 항: 모델이 작은 가중치 벡터 w w w 를 갖도록 제약을 가해 마진을 크게 가짐
두번째 항: 모든 마진 오류를 계산, 샘플이 도로에서 올바른 방향으로 벗어나 있다면 0
힌지 손실: max ( 0 , 1 − t ) \max(0, 1-t) max ( 0 , 1 − t ) - ReLU 반대방향 꼴
참고
Hands-on Machine Learning with Scikit-Learn, Keras & Tensorflow 2 - 오렐리앙 제롱
https://www.youtube.com/watch?v=qFg8cDnqYCI