[Machine Learning] SVM(Support Vector Machine): 원초 문제에서 쌍대 문제로(From the Primal to the Dual Problem)

※ [Machine Learning] 커널 기법(Kernel Method): 커널 트릭(Kernel Trick), 서포트 벡터 머신(Support Vector Machine)

[Machine Learning] 커널 기법(Kernel Method): 커널 트릭(Kernel Trick), 서포트 벡터 머신(Support Vector Machine)

---

SVM에서 배웠던 라그랑주 승수법(Lagrange Multiplier)의 원초 문제에서 쌍대 문제로 푸는 방법과 요구되는 조건들을 다뤄볼 예정이다.

슬랙 변수(Slack Variable)를 사용하지 않는 SVM에서 LMC(Large Margin Classifer)의 원리를 따라 양수와 음수의 데이터들의 마진(Margin)을 최대화하는 분류기를 얻고자 한다. 따라서, 다음과 같은 최소화 문제를 해결한다. 

$$\min_{\mathbf {w}, b} \frac {1}{2} ||\mathbf {w}||^2$$

다만, 다음 조건에 제한된다.

$$\forall^N_{i = 1}: y_i \cdot (\mathbf {w}^{\top} \Phi(\mathbf {x}_i) + b) \geq 1$$

※ 일반적인 라그랑주 승수법의 제약 등식(Equality Constraint)과 달리 부등식(Inequality) $\geq$의 조건을 갖는다. 그러므로 일반적인 방법으로 라그랑주 문제를 풀 수 없다.

최적화된 모수들을 계산하고 난 후, 결정 함수(Decision Function)은 다음과 같이 주어지며, 새로운 데이터를 분류하는데 해당 함수를 사용한다.

$$sign(\mathbf {w}^{\top} \Phi(\mathbf {x}) + b)$$

여기까지가 저번 포스팅에서 배웠던 내용이다.

---

슬레이터의 조건(Slater's Condition)

슬레이터의 조건은 라그랑주 승수법에서 제약 조건으로 부등식이 주어졌을 경우 문제를 해결하는데 필요한 조건이다.

컨벡스 함수(Convex Function) $f$를 가정했을 때, 다음과 같은 최적화 문제를 풀려고 한다.

$$min_{\theta} f (\theta)$$

해당 문제는 부등식 제한 조건이 있다. 함수 $g_i$도 컨벡스하다.

$$\forall^n_{i = 1}: g_i (\theta) \leq 0$$

만약 $\forall^n_{i = 1}: g_i (\theta) < 0$을 만족하는 점 $\theta$가 존재한다면, 최적화 문제의 답은 라그랑주 쌍대 공식(Lagrange Dual Formulation)으로 푼다. 공식 안에 있는 최소화 문제는 분석적으로 풀 수 있다.

$$\max_{\alpha} \{ \min_{\theta} \{ f(\theta) + \sum^n_{i = 1} \alpha_i g_i (\theta) \} \} \ \ \forall^n_{i = 1} \alpha_i \geq 0$$

제약 조건이 만족이 안 될 때마다($g_i (\theta) > 0$), $\alpha_i g_i (\theta)$는 양수가되며, 이 값을 $\max_{\alpha}$로 최대화하려고 한다.

---

SVM의 슬레이터 조건(Slater's Condition for SVM)

$$\exists \mathbf {w}, b \text { s.t. } \forall^N_{i = 1}: y_i \cdot (\mathbf {w}^{\top} \Phi (\mathbf {x}_i) + b) > 1$$

즉, 두 클래스는 선형적으로 구분이 가능해야 된다. 만약 슬레이터 조건이 검증되었다면, 최적화 문제는 다음과 같이 쓸 수 있다.

$$\max_{\alpha} \{ \min_{\theta} \{ \frac {1}{2} || \mathbf {w} ||^2 + \sum^n_{i = 1} \alpha_i \cdot (1 - y_i \cdot (\mathbf {w}^{\top} \Phi(\mathbf {x}_i) + b)) \} \} \ \ \text { s.t. } \alpha \succeq 0$$

Q. 편향(Bias) $b$는 어떻게 찾는가?
A. 두 클래스 간의 마진을 최대화했기 때문에, 결정 경계(Decision Boundary)로부터 가장 가까운 점은 정확히 마진 위에 있다.
$$\min_{i | y_i = 1} \{ y_i \cdot (\mathbf {w}^{\top} \Phi(\mathbf {x}_i) + b) \} = 1$$
$$\therefore b = 1 - \min_{i | y_i = 1} \{ \mathbf {w}^{\top} \Phi(\mathbf {x}_i) + b \}$$

Q. 소프트 마진 SVM(Soft Margin SVM)을 위한 편향 $b$는 어떻게 찾는가?
A. 소프트 마진 SVM의 편향은 쌍대 문제로부터 KKT 조건(KKT Condition)으로 구할 수 있다.

---

KKT 조건(KKT Condition)

출처: https://en.wikipedia.org/wiki/Karush–Kuhn–Tucker_conditions

부등식 $\forall^n_{i = 1}: g_i (\theta) \leq 0$에 제약을 받는 최적화 문제 $\min f(\theta)$를 가정하자. 이를 위한 KKT(Karush-Kuhn-Tucker) 조건은 다음과 같다.

$$\begin {align*}
\nabla f(\theta) + \sum^n_{i = 1} \lambda_i \nabla g_i (\theta) &= 0 \label {stationarity} \tag {stationarity} \\
\forall^n_{i = 1}: g_i (\theta) &\leq 0 \label {primalfeasibility} \tag {primal feasibility} \\
\forall^n_{i = 1}: \lambda_i &\geq 0 \label{dualfeasibility} \tag {dual feasibility} \\
\lambda_i g_i(\theta) &= 0 \label {complementaryslackness} \tag {complementary slackness}
\end {align*}$$

슬레이터 조건이 만족된다면, KKT 조건은 최적에서 만족된다. 원초 문제의 편향은 $\ref {complementaryslackness}$ 식으로부터 구할 수 있다.

---

1. Richard O. Duda, Peter E. Hart, and David G. Stork. 2000. Pattern Classification (2nd Edition). Wiley-Interscience, USA.

2. Müller, K.R., Montavon, G. (2021). Lecture on Machine Learning 1-X. Technische Universität Berlin, Berlin, Germany.