SVM 공부를 하던 중 아래와 같은 공식이 나왔습니다.
해당 공식은 제약된 조건 하에서 Maximum Margin을 구할 때 사용되는 공식입니다.
유도 과정은 다음과 같습니다. (blog url)
해당 공식에서 사용되는 변수는 w, b, $\alpha$ 입니다.
해당 목적식과 제약식이 있는 상황에서 라그랑주 승수법은 제약 조건을 신경쓰지 않고 문제를 풀 수 있게 변형시켜줍니다.
라그랑주 승수법이란?
$g(x)$라는 제약 조건 하에서 목적 함수 $f(x)$를 최소화하는 문제가 있다고 할 때, 라그랑주 함수라는 새로운 함수를 정의할 수 있습니다.
해당 함수는 다음과 같이 나타낼 수 있습니다.
$$L=f(x)-\alpha*g(x),\ \alpha>=0$$
$\alpha$는 라그랑주 승수(Largrange Multiplier)이며, 0보다 크거나 같다는 조건이 붙습니다.
이렇게 제약이 있는 최적화 문제라면 라그랑주 함수의 정류점(stationary point)가 되는 $\alpha$가 존재해야 하며, 정류점은 모든 편도함수가 0인 지점입니다. 그리고 제약이 있는 최적화 문제의 해는 이런 정류점 중에 있습니다.
예를 들어, 제약이 $g(x,y)=x^2+2y-\alpha (3x+2y+1)$인 조건에서 $f(x)=x^2+2y$를 최소화하는 x와 y의 값을 찾으려고 할 때, 라그랑주 함수와 라그랑주 함수의 편도함수는 다음과 같습니다.
이 편도함수 방정식을 풀게 되면, $x=\frac{3}{2}, y=-\frac{11}{4}, \alpha=1$을 계산할 수 있습니다.
주어진 조건을 만족하는 정류점은 하나뿐이므로 이 값이 제약이 있는 최적화 문제의 해가 됩니다.
즉, 라그랑주 승수법은 연립방정식에 대해서만 적용이 가능하며, 만약 제약조건이 연립 부등식이라면, KKT조건을 만족하도록 라그랑주 승수법을 적용하면 됩니다.
여기서 우리가 사용하고 싶은 제약식의 형태는 연립 부등식의 조건이기 때문에 KKT 조건을 사용하여 식을 구성할 수 있습니다.
즉, KKT 조건을 만족하면서 $mininize \vec{\omega} \n and maximize \alpha_i >= 0$이 되는 최적화 문제를 풀면 됩니다.
KKT 조건
간단하게 조건에 대해서만 소개를 하면 다음과 같습니다.
1. 모든 변수에 대한 미분값은 0이다.
2. 모든 라그랑주 승수값과 제약 조건 부등식의 곱은 0이다.
3. 라그랑주 승수값은 음수가 아니다.
KKT 조건은 정류점이 제약이 있는 최적화 문제의 해가 되기 위한 필수 조건이며, 일정 조건 하에서는 충분조건 이기도 합니다.
reference
'♾️ Math' 카테고리의 다른 글
| 오일러 항등식 (Euler’s Identity)의 성질, 유도 (0) | 2024.05.18 |
|---|
