SVM - Quadratic Programming(QP) & Kernel Trick

 

# 선형 SVM 분류 모형

가중치 벡터 $\mathrm{w}$ , 편향 $b$

 

샘플 $\mathrm{x}$ 에 $\mathrm{w}$ 을 점곱하고 $b$ 를 더해 계산한 결과를 토대로 예측 $\hat{y}$ 를 구함

 

$$\mathrm{w}^T \cdot \mathrm{x} + b = w_1 x_1 + \cdots + w_n x_n + b$$  

 

$$\hat{y} = \begin{cases} 0 &  \mathrm{w}^T \cdot \mathrm{x} + b < 0 \\ 1 & \mathrm{w}^T \cdot \mathrm{x} + b >= 0 \end{cases}$$

 

 

SVM 분류 모형은 제한된 마진 오류 내에서 가장 큰 마진을 갖는 $\mathrm{w}$ 와 $b$ 를 찾아야 한다. 이때 $\mathrm{w}$ 은 결정 모델의 기울기이며 기울기를 줄일 수록 큰 마진을 갖게 된다.

 

 

 

# 목적 함수

하드 마진 모델일 경우, 양성 샘플은 결정함수 값이 1보다 크며, 음성샘플은 결정함수 값이 -1 보다 작게 된다.

 

음성샘플 $y_i$ = 0 일때 $t_i$ = -1, 양성샘플 $y_i$ = 1 일때 $t_i$ = 1 이 되는 $t_i$ 를 가정하면

 

목적함수는 다음과 같게 되며

$$\text{minimize}_{\mathrm{w} , b} \frac{1}{2} \mathrm{w}^T \cdot \mathrm{w}$$

 

제약조건은 다음과 같다

$$t_i ( \mathrm{w}^T \cdot \mathrm{x}_i + b ) >= 1$$

 

 

 

소프트 마진 모델일 경우 각 샘플에 대한 슬랙변수 $\zeta_i$ >= 0 을 도입하여 얼마나 마진을 위반할지 결정한다.

 

가중치 벡터를 최소화 해야 하는 상황과 슬랙 변수를 최소화 해야 하는 상황의 트레이드오프를 하이퍼파라미터 C 를 이용해 결정한다.

 

소프트 마진 모델의 목적함수와 제약조건은 다음과 같다.

 

$$\text{minimize}_{\mathrm{w} , b , \zeta} \: \frac{1}{2} \mathrm{w}^T \cdot \mathrm{w} + C \sum_{i=1}^{m} \zeta_i$$

 

$$t_i ( \mathrm{w}^T \cdot \mathrm{x}_i + b) >= 1 - \zeta_i ,\quad \zeta_i >= 0$$

 

 

 

 

 

# 콰드라틱 프로그래밍(QP)

선형적인 제약조건 하에 볼록함수 2차 최적화 문제는 quadratic programming 문제이며, 일반화된 공식은 다음과 같다.

 

$$\text{minimize}_p \frac{1}{2} P^T \cdot H \cdot P + f^T \cdot P , \quad A \cdot P <= b$$

 

$P$ : $n_p$ 차원 벡터

$H$ : $(n_p \times n_p)$ 행렬

$f$ : $n_p$ 차원 벡터

$A$ : $(n_c \times n_p)$ 차원 행렬

$b$ : $n_c$ 차원 벡터

$n_p$ : 모델 파라미터 수, $n_c$ : 제약 수

 

 

콰드라틱 프로그래밍은 라그랑주 승수를 응용한 알고리즘으로 풀 수 있을 것이며, 필자도 아직 공부 중이라 풀이법을 모르기 때문에 관련 논문 을 참고할 수 있다.

 

 

 

# 쌍대(dual) 문제

위의 콰드라틱 프로그래밍 문제를 원문제로 해결하는 방법이 있고 쌍대 문제로 해결하는 방법이 있다. 

 

쌍대 문제는 SVM 모델의 연산량을 마법과 같이 줄여주는 수학적 skill 인 커널 트릭(kernel trick)을 가능케 하는 접근 방법이다. 

 

 

$$\text{minimize}_\alpha  \frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_i \alpha_j t_i t_j \mathrm{x}^T_i \cdot \mathrm{x}_j - \sum_{i=1}^{m} \alpha_j$$

 

$$\text{subject to   } i = 1,2, \cdots , m \quad \alpha_i >0$$

 

위의 목적함수를 최소화하는 벡터 $\hat{\alpha}$ 를 찾아 $\hat{\mathrm{w}}$ 과 $\hat{b}$ 를 구할 수 있다.

 

 

$$\hat{\mathrm{w}} = \sum_{i=1}^{m} \hat{\alpha}_i t_i \mathrm{x}_i$$

$$\hat{b} = \frac{1}{n_s} \sum_{i=1}^{m} ( t_i - \hat{\mathrm{w}}^T \cdot \mathrm{x}_i ) , \quad \hat{\alpha}_i > 0$$

 

 

 

 

# 커널 트릭

예를 들어 2차원 데이터 상에서 선형 SVM 분류기를 훈련시키기 위해 데이터를 2차원으로 매핑하는 함수 $\phi$ 가 있다고 하자. 데이터 $\mathrm{x}$ 를 매핑한 결과는 다음과 같을 것이다.

$$\phi (\mathrm{x}) = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1 x_2 \\ x_2^2 \end{pmatrix}$$

이렇게 3차원 벡터가 만들어진다. 데이터 $a$ 와 $b$ 를 $\phi$ 함수로 매핑시키고 둘을 점곱한 결과는 다음과 같다.

$$\phi(a)^T \cdot \phi(b)^T = \begin{pmatrix} a_1^2 \\ \sqrt{2} a_1 a_2 \\ a_2^2 \end{pmatrix}^T \cdot \begin{pmatrix} b_1^2 \\ \sqrt{2} b_1 b_2 \\ b_2^2 \end{pmatrix} = a_1^2 b_1^2 + 2 a_1 a_2 b_1 b_2 + a_2^2 b_2 ^2$$

 

이는 다음의 결과와 같다

$$(a_1 b_1 + a_2 b_2 )^2 = \begin{pmatrix} \begin{pmatrix} a_1 \\ a_2 \end{pmatrix}^T & \cdot & \begin{pmatrix} b_1 \\ b_2 \end{pmatrix} \end{pmatrix}^2 = (a^T \cdot b)^2$$

 

 

와! 놀랍지 않은가??? 

 

실제 매핑함수를 구하지 않고도 매핑함수끼리의 점곱을 원래 데이터의 점곱으로 구할 수가 있다. 이것이 이번 포스트의 핵심 내용인 커널 트릭 이다.

 

위에 살펴본 쌍대 문제의 목적함수에 매핑함수 $\phi$ 를 적용하면, $\phi(x_i)^T \cdot \phi(x_j)$ 를 $\ (x_i^T \cdot x_j)^2$ 바꿀 수 있고, 이는 실제로 데이터를 다차원으로 매핑해서 기하 급수적으로 늘어난 특성 값을 일일히 계산하지 않고도 그와 같은 결과를 낼 수 있게 해준다.

 

모델이 새로운 샘플 $x$ 에 대한 예측값을 예상할 때도 커널 트릭을 이용하여 $\hat{\mathrm{w}}$ 과 $\hat{b}$ 를 직접 구하지 않고 예측값을 도출할 수 있다.

 

이러한 마법같은 단순화 기법은 SVM 모델에서 다차원 데이터를 다룰 때 널리 사용된다.

 

일반적으로 많이 쓰이는 커널들은 아래가 있다.

 

선형커널 $K(a,b)$ = $a^T \cdot b$

다항식 커널 $K(a,b)$ = $(\gamma a^T \cdot b + r)^d$

가우시안RBF 커널 $K(a,b)$ = $exp(- \gamma \| a - b \|^2 )$

시그모이드 커널 $K(a,b)$ = $tanh(\gamma a^T \cdot b + r)$