# 선형 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)$
댓글