[Math] Optimization 이란 (Introduction)

Optimization(최적화)란 무엇인가?

Optimization(최적화)는
feasible candidates(가능한 후보)들 중에서
Optimal element(최적의 요소)를 찾아내는 과정임.

쉽게 말해, 어떤 문제에 대해 Optimal solution을 찾는 것임.

1. Feasible candidates (가능 후보들):
   • Optimal solution을 구하기(찾기) 위해 고려하는 candidates(후보들)임.
   • 이 후보들은 보통 constraints (제약 조건)에 의해 범위가 제한됨.
2. Objective function (목적 함수, J):
   • Optimization에서 optimal solution을 찾기 위해 사용하는 함수를 가르키는 generic term임.
   • 실제적으로는 이 함수의 값을 가장 작게(또는 크게) 만드는 것이 optimization의 목표임.
   • 분야에 따라 다른 이름으로도 사용되는데 그 종류는 다음과 같음.
     • cost function: C
     • loss function: L
     • energy function: E
     • utility function (이 경우, 최대화의 대상)
3. Optimal solution (최적해):
   • Objective function의 값이
   • 가능한 범위 내 (=feasible candidates)에서
   • 가장 작은(또는 큰) 값을 가지게 하는 solution임.

---

1. 일반적인 Optimization Problem의 형식

기계학습 등에서는 minimization problem (or maximization)의 수식으로 나타내어지며 수식은 다음과 같음.

참고로 이 절에서는 minimization problem으로 표시했으나,
loss function에 -1을 곱해주면 maximization problem으로 쉽게 변환 가능함을 잊지 말것.

 

$$\underset{\boldsymbol{\omega}}{\min}f(\boldsymbol{\omega})$$

일반적으로 위의 minimization problem(최소화문제)은 다음의 constraint를 가짐.

• $m$개의 부등식 제약 조건 $g_i(\boldsymbol{\omega}) \le 0$ 및
• $p$개의 등식 제약 조건 $h_j(\boldsymbol{\omega})=0$에 종속된다.

위의 설명에서 각 term은 다음과 같음.

• $f(\textbf{x})$ : real-valued function of $\textbf{x}$ (or scalar field)
• $\textbf{x}$ : an input column vector $\textbf{x}=(x_0, x_1, \dots, x_n)^T$, which can be a scalar, while
• $\textbf{g(x), h(x)}$ : vector-valued functions.
  $$f: \mathbb{R}^n \rightarrow \mathbb{R} \\ \textbf{g}: \mathbb{R}^n \rightarrow \mathbb{R}^m\\ \textbf{h}: \mathbb{R}^n \rightarrow \mathbb{R}^p$$

참고: 아래 URL 문서의 첫부분을 참고

2023.07.06 - [.../Math] - [Math] Lagrangian from Standard Form using Indicator Function

[Math] Lagrangian from Standard Form using Indicator Function

---

위와 같은 수식으로 Optimization problem이 정의되기 때문에

objective function $f(\textbf{x})$, inequality constraints $\textbf{g}(\textbf{x})$, 그리고 equality constraints $\textbf{h}(\textbf{x})$들의 종류 및 속성에 의해
Optimization의 종류를 나눌 수 있음.

2024.06.01 - [.../Math] - [Math] Optimization Problem 의 종류

[Math] Optimization Problem 의 종류

---

2. Mathematical Optimization

수학적 최적화는,

• 일정한 domain(정의역)에서
• 주어진 constraints로를 만족시키면서
• Objective function의 extreme value(극값, minimum or maximum)을 찾는 문제로
• 정의된다.

즉, function의 extreme value를 찾는 문제라고 볼 수 있음.

$$\begin{aligned}&\text{minimize }f(\textbf{x})\\ & \text{s.t:}\\ & g_i(\textbf{x}) \le 0, i=1,\dots,m \\ & h_j(\textbf{x})=0,j=1,\dots,p\end{aligned}$$

 

 

때문에 Optimization은 Equation Solving(방정식 풀기)와 관련이 깊음.

2024.02.20 - [.../Math] - [Math] 용어: root, equality, expression

[Math] 용어: root, equality, expression

 

---

 

2-1. Root Finding과 Gradient based Optimization

Optimization은 다음과 같은 특징 때문에 일종의 연립방정식의 root(근)을 찾는 것이라고 볼 수 있음.

• loss function $f(\textbf{x})$을 최소화하는 최적값(optimal value) $\hat{\textbf{x}}$에서는, 그 loss function의 derivative(도함수)나 gradient (multi-variable function이 loss function인 경우)가 0이 됨: $\nabla f(\hat{\textbf{x}})=0$
  • 이에 대한 inverse(역)는 반드시 참이 아님을 주의할 것.
  • 즉, 도함수나 gradient가 0이라고 해서 반드시 최적값은 아님.
• 최적해가 되기 위한 necessary condition(필요조건)은 derivative 또는 gradient가 0임.

즉, Graident-based Optimization은

• $\nabla f(\textbf{x})=0$ 형태의 연립방정식을 풀어서
• optimal solution이 될 수 있는 stationary points(=gradient가 0이 성립하는 근들)를 구하는 것으로 출발함: 이는 root-finding관 연결됨.

2022.05.19 - [.../Math] - [Math] 필요조건, 충분조건, 필요충분조건

[Math] 필요조건, 충분조건, 필요충분조건

2023.07.10 - [.../Math] - [Math] Stationary point (or Critical point)

[Math] Stationary point (or Critical point)

 

Optimization 에서 가장 널리 사용되는 접근 방식(=Gradient based Optimization)은 다음과 같음:

1. Object function의 derivative 또는 gradient가 0이 되는 stationary points를 찾고
2. 1에 찾은 여러 stationary points(후보들)에 대해 최적성(optimality)으로 테스트하고 가장 최적의 solution을 선정.

Gradient-based Optimization이 널리 사용되지만 이 방법이 항상 적용 가능한 것은 아님.

• derivative나 gradient를 명시적으로 구하기 어렵거나 혹은 존재하지 않을 수 있으며,
• 또는 object function이 local minima 나 saddle points 등을 가질 경우, 원하는 global optimum 을 찾지 못할 수 있음.

때문에 종종 다른 numerical method(수치적 접근)을 사용하는 경우도 많음.
하지만, 대부분이 방정식 풀이(numerical methods for root finding)와 밀접하게 관련되어 있음.

 

하지만, DL등에서는 Gradient based Optimization이 매우 널리 사용됨.

Gradient based Optimization에 속하는 방법으로 유명한 방법은 Gradient Descent와 Newthon's Method (or Newtonn-Raphson Method for Optimization) 등이 있음: 엄밀히 말해서 Newton's Method는 Hessian based Optimization임.

2022.06.07 - [Computer/ETC] - [ML] Newton-Raphson Method

[ML] Newton-Raphson Method

---

Optimization에서 gradient를 사용하기 때문에,  Optimization에서 사용되는 objective function이나 constraints는 continuous하고 smooth한 경우가 많음.

2024.06.01 - [.../Math] - [Math] Importance of Continuous and Smooth Functions in Optimization Problems

[Math] Importance of Continuous and Smooth Functions in Optimization Problems

---

2-2. Analytical Method: Lagrange method.

참고로

equality constraints가 있는 optimization에서 널리 이용되는 방법 중 하나로는 Lagrange Method가 있음.

2023.07.06 - [.../Math] - [Math] Lagrangian from Standard Form using Indicator Function

[Math] Lagrangian from Standard Form using Indicator Function

 

Lagrange Method는

Karush-Kuhn-Tucker conditions(KKT conditions)를 통해 inequality constraints도 다룰 수 있으나

equality constraints로 한정한 경우에 보다 쉽게 사용할 수 있음.

2023.06.26 - [.../Math] - [Math] Lagrange Method or Lagrange Multiplier Method

[Math] Lagrange Method or Lagrange Multiplier Method

 

Lagrange Method는 대표적인 analytical method로,

• Gradient Decent가 iterative하게 근사해를 찾는 것(=Iterative Numerical Method)과 달리,
• 수학적으로 closed form의 식을 유도하여 정확한 solution를 계산해냄. 

Largrange Mehtod가 항상 closed form solution을 제공하는 것은 아님.
고차 다항식이나 비선형 제약조건이 있는 경우 Numerical Method를 통해 solution을 구해야할 수도 있음.
단, 적용하는 방식 자체는 analytical method임.

 

2022.04.29 - [.../Math] - Closed-form solution and Closed-form expression

Closed-form solution and Closed-form expression

---

3. ML과 DL에서의 Optimization: 

ML이나 DL에서는 model이 주어진 데이터를 얼마나 잘 설명하는지를 평가하기 위해 loss function (손실 함수)을 사용함.

• model의 성능이 좋을수록 loss function의 값이 작아짐.
• 최적의 model을 찾는 과정이 learning이며, 해당 learning은 training을 통해 이루어짐.
• training은 loss function의 값을 최소화하는 model을 찾기 위해 Optimization을 사용함.

---

3-1. Learning(학습), Training(훈련), Optimization(최적화)의 관계: 

Learning(학습), Training(훈련), Optimization(최적화)는 ML과 DL에서 매우 중요한 개념임.

 

이들은 다음과 같이 서로 밀접하게 연관되어 있음.

1. Learning(학습):
   • Learning이란 training dataset(학습 데이터)를 통해
   • 우리가 원하는 성능으로 특정 작업(task)을 수행하는 model을 얻는 과정임.
   • Learning의 목표는 model이 주어진 데이터를 이해하고, 새로운 데이터에 대해서도 정확한 예측을 할 수 있도록 하는 것임.
2. Training(훈련):
   • Training은 model을 학습시키는 과정을 가리킴.
   • 이 과정에서는 model이 training dataset을 통해 parameters를 조정하여 성능을 향상(=loss 를 최소화)시키는 것을 목표로 함.
   • Training에서는 loss function을 사용해 model의 성능을 평가하고,
   • Optimization Algorithms을 통해 loss function를 최소화하도록 parameters를 조정함.
3. Optimization(최적화):
   • Optimization(최적화)는 training 에서 최적의 parameters를 찾는 데 사용되는 방법임.
   • Model의 loss function을 최소화하기 위해 parameters를 조정하는 과정임.

---

3-2. ML, DL에서의 Optimization 관련 용어

1. 손실 함수(Loss function): 모델이 학습 데이터를 얼마나 잘 설명하는지를 측정하는 함수임.
2. 모델의 파라미터(Parameter): 모델의 성능을 조절하는 변수들임.
3. Optimizer(최적화 알고리즘): 손실 함수를 최소화하기 위해 모델의 파라미터를 조정하는 알고리즘임.

참고로
가장 기본적인 Optimization Algorithm은 바로 gradient descent (경사 하강법).

• 이 알고리즘은 loss function을 가장 가파르게 최소화시키는 방향(gradient)을 찾아 parameters를 조금씩 조정함.
• 이를 반복하면 loss function의 값이 점점 작아지고, 결국 최적의 parameters를 찾게 됨: Iterative Method.

2023.10.19 - [Programming] - [ML] Gradient Descent Method : 경사하강법

[ML] Gradient Descent Method : 경사하강법

---

3-3. 예시: DL에서의 최적화

DL의 Artificial Neural Network (ANN)을 생각해 볼 것.

ANN은 여러 층(layer)으로 이루어져 있으며, 각 층에는 많은 노드(node)와 연결(connection)이 있음.
각 연결에는 가중치(weight)라는 파라미터 (bias포함)가 존재함.

• 학습 과정 (Learning): 모델이 데이터를 통해 패턴을 인식하고 예측을 수행할 수 있도록 하는 과정.
• 훈련 과정 (Training): loss function을 사용해 모델의 예측 성능을 평가하고, optimization(최적화 알고리즘)을 통해 가중치를 조정함.
• 최적화 (Optimization): 훈련 과정에서 손실 함수를 최소화하기 위해 가중치를 조정하는 구체적인 과정임.

이처럼 Optimization은 ML이나 DL에서 핵심적인 역할을 하며, modeld의 학습에서 매우 중요한 과정임.

Learning과 Training은 Optimization를 통해 이루어지며,
Optimization을 통해 model이 데이터를 가장 잘 설명하도록 만드는 것이 바로 DL의 목표임.

---

같이 읽어보면 좋은 자료들

Numerical Python : Scientific Computing and Data Science Applications with Numpy, SciPy and Matplotlib, 2nd Ed., Robert Johansson, Uraysasu-shi, and Chiba, 2019, Apress.

https://www.amazon.com/Numerical-Python-Scientific-Applications-Matplotlib/dp/1484242459

http://acornpub.co.kr/book/numerical-python-2e

파이썬과 수치 해석 2/e

---