쌍대문제 / 라그랑주 승수법 / KKT 조건

 쌍대 문제(Dual problem), 라그랑주 승수법(Lagrange multiplier method), KKT 조건(Karush-Kuhn-Tucker Condition)은 머신러닝에서 자주 언급되는 목적함수(Object function, Loss function, Cost function, ...)의 해를 구할 때 언급되는 용어들입니다. 

 각각에 대한 수식적이고, 깊은 설명은 Ratsgo's blog와 같은 멋진 분들이 잘 설명해주신 글들이 많기에, 저는 간단히 흐름만 체크해보겠습니다.

 저희가 머신러닝을 공부하는 과정 중에 마주치는 어떤 목적함수를 떠올려봅시다. 어떤 것이라도 괜찮아요. RMSE 따위를 가정해보면, 저희가 어떤 모델에게 원하는 학습의 방향은, 이 RMSE를 최소화하는 것입니다. 어떤 함수의 최소값을 구한다. 잠깐 고등학생 시절을 떠올려보면, 어떤 다항함수 f(x) 의 최소값을 구하는 방법은, f(x)의 미분값이 0이 되도록하는 x값을 계산해서, 그 x를 f(x)에 대입하면되었습니다. 최대냐 최소냐 판단하던 일은 차차하면 되구요. 모델을 학습시킬 때도, 이 아이디어를 그대로 유지하면 참 좋을 것 같습니다,,. 만 그게 안됩니다. 컨벡스(Convex, 볼록)라는 조건 때문인데, x^2처럼 볼록-하게 생기면, 미분값이 0인 지점에서 극값을 갖지만, 너저분하게 생긴 형상에서는 극값을 보장을 하지 못한다-라고 쉽게 표현할 수 있을 것 같습니다. 물론 RMSE 자체는 볼록합니다만, 상황이(문제가) 복잡할수록, 해당 함수에 대한 여러가지 제약조건(Straint condition)이 걸리게될텐데, 이 경우에는 문제를 어떻게 해결할 것인가가 문제가 될 것입니다.

 다시 정리하면, 저희게 풀고 싶은 메인문제(Primal problem)가 제약조건(Straint condition)을 달고 있어서 해결이 어렵다. 이를 해결하기 위해 쌍대문제(Dual problem)가 등장합니다. 메인문제가 지저분하니, 메인문제와 같은 솔루션을 갖는 다른문제(Dual problem)을 정의하고, 이를 풀어버리자는 겁니다. 위에서 지저분한 것과 지저분하지 않은 것을 구분짓는 핵심 요소로 컨벡스를 언급했는데, 쌍대문제도 논컨벡스라면, 지저분한거 피해서 왔더니 다시 지저분한게 있는 결과가 될텐데, 이건 별로 자연스럽지 못하겠죠. 저희가 다루고자하는건 당연히 컨벡스이길 원하고, 그렇게 만드는게 목표가 됩니다. 이 때 사용되는 방법 중 하나가 라그랑주 승수법입니다. 메인문제를 컨벡스한 쌍대문제로 정의하는 방법-이 되겠죠. 아이디어는 간단한 것으로, 이곳을 참조하시면 될 것 같습니다.

 쨋든 이렇게 만들어진 쌍대문제는 컨벡스이며, 간단히 해를 구할 수 있습니다-만, 결국 메인문제를 직접 해결한 것이 아니라 우회해서 다른 문제를 해결한 것이니, 둘 간의 해가 항상 같으냐-하는 문제는 또다른 포인트가 됩니다. 정답은 당연히 항상 같음을 보장하지 않습니다. 특정 조건을 만족할 때야 같을 뿐입니다. 그 조건이 무엇이냐-하는 것은 수식을 안쓰고는 말할 수 없으니 여기서 다루지 않겠습니다.

 이렇게 쌍대문제와 라그랑주 승수법 사이의 관계를 굉장히 단순히 정리해봤는데, 더 깊이 들어가보면 KKT 조건-이 등장합니다. 이또한 수식을 포함하지 않고는 설명이 어렵기에 관련 명제만 언급하자면

 (충분조건) 어떤 x,u,v가 KKT조건을 만족하면, 이러한 x,u,v는 각각 메인문제와 쌍대문제의 해가 된다.

 (필요조건) 어떤 x,u,v가 각각 메인문제와 쌍대문제의 해이면서 zero duality를 보장한다면, 이러한 x,u,v는 KKT조건을 만족한다.

 명제만보면 x,u,v가 뭔지, KKT조건이 뭔지, zero duality가 뭔지 전혀 모르겠습니다. 조금 무책임하지만, 링크된 분들의 글에 굉장히 잘 설명되어있으니, 참조하시면 충분히 이해가 가실 것이라 생각됩니다. 이상입니다.