1. Optimization Using Gradient Descent
2. Constrained Optimization and Lagrange Multipliers
3. Convex Sets and Functions
4. Convex Optimization머신 러닝을 할 때 optimization 문제들이 자주 등장하고, 이것을 어떻게 잘 푸느냐가 좋은 Model을 찾는 것과 직결되는 경우가 많다.
미분 값이 0이 되는 지점, 즉 기울기가 0이 될 때 함수의 최솟값이 되는 경우가 많기 때문에 함수의 gradient 정보가 최적화 하는 데 매우 중요한 역할을 한다.
-optimization의 종류
- unconstrained optimization
- constrained optimization
- convex optimization
Optimization Using Gradient Descent
함수를 최소화 하기 위한 Gradient-type algorithms
Gradient-type algorithms는 다음과 같이 재귀적으로 표현이 된다.
Model의 Loss 함수 L을 정의하는 데이터의 양에 따라서 불리는 이름이 다르다.
Batch gradient
-모든 data point를 고려해서 계산하는 업데이트
Mini-batch gradient
-계산의 효윧성을 위한 특정 subset을 구해 그 안에 있는 gradient만 계산
Stochastic gradient
-Mini-batch gradient의 어떤 gradient가 original batch gradient를 잘 근사할 수 있게 디자인해서 업데이트
Langrange Function과 Langrange Multipliers의 개념
Lagrange Dual Function이 optimal value의 Lower Bound가 된다는 것은 쉽게 확인이 가능하다.
Lower Bound를 Maximaization해도 여전히 Original Optimization의 Lower Bound이다. Lagrange Dual Problem은 가장 좋은 Lower Bound를 제공해 준다. Original Optimization은 x에 대한 Optimization, Lagrange Dual Problem은 λ, ν에 대한 Optimization이 된다.
많은 경우 Dual 문제를 푸는 것이 Primal 문제를 푸는 것보다 쉬운 경우들이 많고, Dual 문제는 Primal 문제에 항상 Lower Bound를 제공한다.
따라서 Lagrange Dual Problem의 optimal value는 Original 문제의 Lower Bound가 된다는 성질이 있는데, 이를 Weak Duality 라고 한다. primal optimization을 풀기가 힘들더라도 dual optimization을 통해서 어느정도의 예측이 가능하다.
