Study/최적화

Ridge regression과 Inequality constraint optimization problem의 관계

빠릿베짱이 2016. 11. 30. 10:23
반응형

regularization을 공부하다가

Ridge regression을 만나게 되고,

l2 Norm regularization을 설명하면서

기하학적인 뷰에서 regularization의 의미를 많이 설명하는데,


이 설명을 위해, unconstraint optimization problem 과 constraint optimization problem과 같다고 하고 설명을 한다.


그래서 대체 왜 같은지를 찾기 위해, 파고파고 파다 보니, KKT까지 왔다.


전체적인 흐름을 보면,


조건부 최적화에는 equality constraint와 inequality constraint 문제가 있다.

먼저, equality constraint 문제는 lagrange multiplier를 사용하여 풀고,

inequality constraint는 KKT multiplier를 사용해서 해결하는 듯 하다.


처음에는 기본 ridge regression의 에러 함수를 바로 inequality constraint optimization 문제로 변경하는 방법에 대해서

찾고 있었다. 하지만 아무리 찾아도... 나오지 않았다.


그러던 중 [ Lecture Notes on ridge regression ] 발견

여기에 원하는 설명이 있었다.


설명을 보면, 먼저 ridge regression의 에러 함수를 푸는 것은 inequality constraint optimization을 푸는 것과 같다라고 하였다.

이를 설명하기 위해, 

먼저, inequality constraint optimization 문제를 정의하고, ridge regression에서 구한 해가  inequality constraint 

optimization의 해와 같음을 보이면 되는 것이다.


방법은

1. ridge regression을 Constrained optimization problem으로 변경, 왜냐하면 우리는 이 둘이 같다라는 것을 보일 것이므로

2. lagrangian을 이용해서 조건이 없는 문제로 변경

3. 이 문제에서 우리가 정한 람다와 ridge regression에서 구한 w*이 Constrained optimization problem에서 해임을 보이면 같다라고 볼 수 있음.



링크

1. 강의 PT 자료 =  http://www.csc.kth.se/utbildning/kth/kurser/DD3364/Lectures/KKT.pdf

2. Constraint Optimization example :  https://ocw.mit.edu/courses/mechanical-engineering/2-854-introduction-to-manufacturing-systems-fall-2010/lecture-notes/MIT2_854F10_kkt_ex.pdf


KKT로 문제를 해결하는 간단한 예제를 찾아보니, 자료는 많았다.

근데 손으로 푸는 과정은 어느정도 이해를 했으나, 실제 이를 적용하여 프로그래밍하려니

어떻게 할 지 감이 오지 않았다.


역시 구글링을 해보니, Quadratic programming이라는 방법으로 해당 문제를 어떻게 푸는지 설명하고 있었다.

자세히 보지는 않았으나, 많은 방법들이 존재하는 것 같다. 


반응형