SMO (Sequential Minimal Optimization) 알고리즘

SMO (Sequential Minimal Optimization) 알고리즘은 서포트 벡터 머신(SVM)의 최적화 문제를 해결하는데 사용됩니다. SVM에서의 최적화 문제는 일반적으로 쌍대 문제를 풀어야 하며, SMO는 이를 해결하기 위해 두 개의 변수 $\alpha_i$와 $\alpha_j$를 순차적으로 최적화합니다. 각 $\alpha_i$는 라그랑주 승수이고, SMO는 이를 최소화하는 방법으로 최적의 $\mathbf{w}$와 $b$를 찾습니다.

---

$q(\alpha) = \max_{\alpha} \left( \sum_{i=1}^{4} \alpha_i - \frac{1}{2} \sum_{i,j=1}^{4} \alpha_i \alpha_j y_i y_j \mathbf{x}_i \cdot \mathbf{x}_j \right)$

SVM에서 풀던 쌍대 문제

---

SMO 알고리즘

1. 초기화:

   • 모든 라그랑주 승수 $\alpha_i$를 0으로 초기화합니다.
   • 바이어스 $b$는 일반적으로 0으로 초기화합니다.

2. 알고리즘 반복:

   • 첫 번째 변수 선택: i를 선택합니다. 일반적으로, $\alpha_i$가 커질 가능성이 있는 $\alpha_i$를 선택합니다.
   • 두 번째 변수 선택: j를 선택합니다. j는 i와 다르며, 최적화가 필요한 다른 변수입니다.

3. 최적화 조건:

   • 두 변수 $\alpha_i$와 $\alpha_j$에 대해 최적화 문제를 풀어 업데이트합니다. 이는 라그랑주 승수 업데이트가 KKT 조건을 만족할 때까지 반복합니다.

4. 변수 업데이트:

   • 각 라그랑주 승수를 업데이트합니다. 두 변수에 대해 계산한 최적의 값을 반영하여 $\alpha_i$와 $\alpha_j$를 업데이트합니다.
   • 이때, 쌍대 문제의 목적 함수 $q(\alpha)$는 라그랑주 승수에 따라 최대화됩니다.

5. 바이어스 업데이트:

   • $b$는 업데이트된 $\alpha_i$와 $\alpha_j$ 값에 따라 업데이트됩니다. 일반적으로 두 라그랑주 승수의 차이에 따라 바이어스를 계산합니다.

6. 종료 조건:

   • $\alpha_i$와 $\alpha_j$의 변화가 매우 작을 때 (변화가 일정 임계값 이하) 알고리즘을 종료합니다.

핵심 아이디어

SMO 알고리즘은 두 개의 라그랑주 승수만을 선택하여 최적화합니다. 왜냐하면, 두 개의 변수만 최적화하면 최적화 문제를 단순화할 수 있기 때문입니다. 이 과정은 반복적으로 이루어져 최종적으로 최적의 $\alpha_i$들이 수렴하게 됩니다. 최적화된 $\alpha_i$ 값들로부터 최적의 $\mathbf{w}$와 $b$를 구할 수 있습니다.

SMO 알고리즘의 주요 단계

1. 두 라그랑주 승수 선택: 최적화할 두 라그랑주 승수 $\alpha_i$와 $\alpha_j$를 선택합니다. 일반적으로, 조건이 만족되지 않는 $\alpha_i$와 $\alpha_j$를 선택합니다.

2. 제약 조건 확인: 두 라그랑주 승수에 대해 다음 제약 조건이 만족되는지 확인합니다:

   • $\alpha_i \geq 0$
   • $\alpha_j \geq 0$
   • $\sum_{i=1}^{n} \alpha_i y_i = 0$ (합은 항상 0이어야 함)

3. 최적화 진행: 두 변수에 대해 쌍대 문제를 최적화합니다. 이때, $\alpha_i$와 $\alpha_j$는 동시에 업데이트됩니다.

4. 바이어스 업데이트: $\alpha_i$와 $\alpha_j$ 업데이트 후, 바이어스를 조정합니다.

5. 반복: 이 과정을 반복하면서 $\alpha_i$들이 최적화될 때까지 진행합니다.

SMO 알고리즘은 매우 효율적이며, 대규모 데이터셋에서도 잘 작동합니다.