서포트벡터머신을 위한 비선형 계획 문제의 쌍대정리Duality in Non-Linear Programming for Support Vector Machine

서포트벡터머신(이하 SVM)을 공부하다 보면 마지막 과정에서 쌍대문제라는 것이 등장한다.

최소화 문제인 원래 문제를 라그랑지 승수에 대한 최대화 문제로 바꿔서 풀게 되는데 이 때 바뀐 최대화 문제를 원래 문제의 쌍대 문제라 한다.

이 두 문제가 어째서 같은 해를 주게 되는지에 대한 설명은 좀 진지한 SVM 문헌이 아니고서는 잘 나오지 않는다.

그 이유는 쌍대문제를 푸는 궁극적인 목적이 커널트릭에 있으므로 쌍대문제를 그냥 받아드리고 쌍대문제에서 나타나는 커널함수에 대한 설명을 중점적으로 하기 때문인 것으로 보인다.

본 문서는 쌍대문제가 정의되는 과정을 가능한 자세한 수식과 충분한 그림을 중심으로 이야기함으로 원문제와 쌍대문제의 관계를 알아보는 것을 목적으로 한다.

본 글의 주 참고문헌은 [arora_2] 5.5절 DUALITY IN NONLINEAR PROGRAMMING이며, [nocedal], [bazaraa], [boyd]의 내용을 부분 부분 함께 정리, 보충 설명하였다.

다루는 내용은 다음과 같다.

전체 글은 jupyter notebook으로 작성되어 있어서 아래 링크를 통해 nbviewer로 공유한다.