[머신 러닝] 서포트 벡터 머신 (SVM) 보충 - 라그랑즈 승주법

라그랑즈 승주법에 대해 간단하게 설명해보겠습니다.

 

라그랑즈 승주법

• 최적화 문제에서 사용되는 수학적 기법
• 최대 또는 최솟값을 찾으려는 문제에서 해결방법으로 사용된다.

 

라그랑즈 승주법을 사용하는 방법

 

• 목적 함수
• 제약 조건 
• 제약 조건에 대해 새로운 변수 
• 를 이용하여 다음의 보조 방정식을 만든다.
•  

 

목적 함수와 제약 조건에 대해 위와 같은 보조 방정식을 만들고 문제를 풀 수 있게 되는 이유는 제약 조건을 만족시키면서 목적 함수를 최대화 또는 최소화 시키는 점에서는 목적함수의 gradient(쉽게 말해 기울기)와 제약 조건의 gradient가 평행하기 때문이다. 

 

출처: 위키피디아

 

라는 제약조건을 만족시키면서 

가 커질 수 있는 최대값은?

 

물론 d1일 것임 (제약조건을 지나는 값이 d1밖에 없으므로)

 

그런데 이 값을 유심히 관찰하면 

 

 와 가 접점을 이루는 곳이 제한된 조건을 만족하는 의 최대값이라는 것을 알 수 있다. 

 

그렇다면 접점을 찾는 조건은 바로 두 곡선의 기울기가 접점에서 평행을 이룬다는 사실이다.

 

곡선의 기울기는 미분을 통해서 알 수 있는데, 변수가 많아지면 편미분을 통해서. 조금 더 자세하게는 gradient 를 통해 구함

 

접점의 값을 구하는 조건은 아래와 같다.

where

또한, 일반적으로 여러개의 제약 조건이 붙는 경우에는 다음과 같이 만들 수도 있을 것이다.

즉 이러한 경우에는 다음 식의 해를 구하게 되면 최적화 조건을 찾을 수 있게 되는 것이다.

 

reference

https://angeloyeo.github.io/2020/09/30/SVM.html#2-%EB%9D%BC%EA%B7%B8%EB%9E%91%EC%A3%BC-%EC%8A%B9%EC%88%98%EB%B2%95%EC%97%90-%EB%8C%80%ED%95%9C-%EC%9D%B4%ED%95%B4

서포트 벡터 머신(SVM) - 공돌이의 수학정리노트

 

Addtional note

 

Lagrangian multiplier를 이용하여 Lagrangian primal 문제로 변환

 

먼저 프라이멀 부분먼저 보자.

원래는 맥스 민 같이 보는 문제이다. 여그래서 max 알파, min w.b

궁극적인 목표는 W와 b값을 구하는 것임!!!

그 다음 맥스 문제인 알파를 구해보자..

 

 w와 b에 대한 식을 알았고, 알파에 대한 관계식도 구했다.

 

그럼 이제 w는 더이상 없어진 것.

 

최종적으로 남은 것은

 

여기서 이제 듀얼문제로 바뀜

w와 b에 대해 정리하였기 때문이다.

 

따라서 알파와의 듀얼문제로 바뀌었음

 

 

벡터들의 내적 (inner product)

 

이제 듀얼을 구하는 것이다.

알파를 풀어서 w를 구해야함!!(기울기)

 

그러면 KKT Condition 을 이용해서 구할 수 있다.

 

KKT Condition

 

 

알파 a가 0보다 크면 뒤의 값은 0이 된다.

+ 플러스 플레인

 

서포트 벡터는 마지노선. 즉 지지선이다!

 

알파 a가 0인 경우, 뒤의 값은 0이 되면 안된다,

서포트 벡터에 대해 해당하는 것을 이용해서 w를 구한다.!!!!!

Sparse representation!!!

대표적인 몇가지만 이용해서 구함..

 

이제 w는 구했는데 b를 구해야함

 

우리는 알파, w값을 알고있다. 그러면 b값은?

 

 

이렇게 w와 베타 b를 구한 것이면 서포트 벡터를 구한 것이다!

 

요약