Week 5.7. Primal and Dual with KKT Condition

Primal and Dual problem

Dual function 의 solution 과 Primal funciton의 solution이 같은해를 가진다는 strong duality를 만족을 해야하는데 , 그것은 KKT 라는 조건을 만족해야 한다. 

KKT Condition 은 아래의 슬라이드를 참조하면 된다.

SVM을 Dual 문제로 넘기기 위해서는 아래의 Hard margin SVM으로 정의 된 부분을 변형시켜야 한다.

Constrained 부분을 (wxj+b)y-1 의 형태로 변경하고 이분에 Lagrange multiplier α 를 붙여 만들어 준다.

j는 모든 데이터셋에 대해 도입되기 때문에 아래와 같이 시그마 (합) 이 도입된다. (아래 식 참조)

 

이제 위식은 아래와 같이 min / max 부분을 바꿔볼수 있다. 바뀐부분을 이용해 α에 대한 부분으로 푸는것으로 적용할수 있다.  α 는 특정의미를 지녀야 한다.

 

 

이제 KKT condition 에 대해 적용을 해보자.

즉 아래의 Largrange Prime function 을 위의 조건에 만족시켜야 된다. 

직접 w, b에 대해 미분을 해보자. 그러면 아래와 같이 2가지 조건이 나오게 된다.

w에 대해 미분

b에 대해 미분

KKT condition 이 충족되면 이제 Dual problem 에 적용할수 있게 된다.

위의 식에서 w를 아래의 유도된 식을 통해 대입해보자.

w에 대해 미분

w 가 각각 term 이 다르기 때문에 i 와 j 로 나눴다.

 

w에 대해 optimization 하는 형태에서 α에 대해 optimization 하는 형태로 변경하였다.

이것은 또다시 quadratic programming의 형태로 변경되었다.

 

즉 α만 quadratic programming을 통해 알게되면 w를 구할수 있게 된다. 즉 DB를 알수 있게 된다.

(x는 input feature , y는 classlabel 이다.)

 

현재까지 Linear SVM에 대해 알아왔기에 w는 Linear한 선에서의 기울기 이다.

 

이제 이것이 Primal problem보다 좋은지 다음 강의를 통해 알아볼 것이다.