인공지능 기초수학 개념으로, 선형대수에 이어 미적분과 관련이 많은 '최적화'에 대해 간단히 정리하려 한다.
4년간 배운 내용과 다른 블로그, 유튜브 등 여러 곳에서 조금씩 참고하여 정리했다.
전체적인 흐름은 '혁펜하임' 유튜브 채널의 최적화 부분을 따랐다.
매우 기초적인 내용은 제외하고, 인공지능의 기초 내용에 대해 중요하면서도 외워둬야 할 것들(특히 Convex Problem과 Gradient Descent) 위주로 정리할 것이다.
목차
0. 미분 기초, Optimization 개요, 용어 정리
가장 먼저 기초 함수들의 미분에 대해 간단히 복습해보자.
\( (\frac{1}{g(x)})' = - \frac{g'(x)}{\{g(x)\}^2} \)
\( (\frac{f(x)}{g(x)})' = - \frac{f'(x)g(x) - f(x)g'(x)}{\{g(x)\}^2} \)
\( (e^{f(x)})' = e^{f(x)} \cdot f(x)' \)
\( (a^x)' = a^x \ln a \)
\( (\ln x)' = \frac{1}{x} \)
\( (\log_{a} x)' = \frac{1}{x \ln a} \)
\( (\sin x)' = \cos x \)
\( (\cos x)' = - \sin x \)
\( (\tan x)' = \sec^2 x \)
1) Optimization Problem
최적화의 개념이 인공지능에 필요한 이유는, 어떤 변수에 대해 cost를 줄이는것이 목표인 최적화의 개념을 머신러닝에서 모델이 무언가를 예측할 때 사용할 수 있기 때문이다.
convex problem이란, 단순히 볼록한 모양의 cost-variable 그래프에서 최적의 값(cost의 최솟값)과 포인트(그 때 변수의값)를 찾는 것으로 생각할 수 있다.
여기서 cost는 개념적으로 에러가 될수도, 확률(이 경우, 최적 값은 높은 값을 찾는 것이 될 것임)이 될 수도 있다.
최적화라는 주제의 전반적인 과정은 이러한 convex problem에서 여러 조건이 추가되었을 때, 최적 값을 어떻게 찾을 것인지 알아가는 것이다.
2) Terminologies
위와 같이, \(f(x) = y=3x^2 - 5x + 2\)를 cost funciton(=objective function)으로 갖는 그래프가 있다고 해보자.
최적화(Optimization) 문제는 \( \min f(x) \)를 찾는 문제로 볼 수 있다.
여기서 변수 \(x\)에 대해 다음과 같은 제한 조건이 있을 수 있다.
- equality constraint
- ex: \(subject \; to \; h(x) = 0\)
- inequality constraint
- ex: \(subject \; to \; g(x) \leq 0 \)
이러한 제한 조건을 모두 만족하는 변수를 'feasible(실현 가능한) solution', feasible solution의 집합을 'feasible set'이라 한다.
이때 feasible set 중에서 \(\min f(x)\)를 만족하는 solution을 'Optimal solution'이라 하고, \(x^*\)로 표시한다.
\(x^* \triangleq \underset{x}{argmin} \, f(x) \)
다음으로, 극대와 극소에 대해 알아보자. 주의할 점은, 미분값 = 0이면 극대 또는 극소는 아니다. 미분이 불가능한 점도 극대점 또는 극소점이 될 수 있다.
극댓점(local maximum point)이란, 어떤 점의 주변에서 함수값을 가장 크게 만드는 그 점, 극솟점(local minimum point)이란 어떤 점의 주변에서 함수값을 가장 작게 만드는 그 점을 말한다.
함수의 최대점(global maximum point), 최소점(global minimum point)은 각각 정의역 상의 모든 점에서 함수값이 가장 큰 점, 작은 점이다.
함수 \(f: [a, b]\)에 대해
- global minimum point : \(A\)
- global maximum point : \(J\)
- local minimum point : \(E, G\)
- local maximum point : \(B, D, F, J\)
이다. 나머지 점은 아무것도 아닌 점이다.
이중 미분 가능한 점은 B, E, J 뿐이다.
1. Convex Optimization Problem
Convex Optimization Problem이란, objective function \(f(x)\)가 convex이고, feasible set이 convex인 문제를 말한다.
convex라는 의미는 f(x)에서와 feasible set에서 조금 다른데, 각각 어떻게 다른지 알아보자.
1) Convex Set
기본적으로 집합이 볼록하다는 것은 그 원소들이 이루는 집합의 형태가 타원형의 형태를 나타내는 것을 말한다.
구체적인 의미는 다음과 같다.
두 벡터 \(\mathbf{x_1}, \mathbf{x_2}\)와 집합 \(S\)에 대해
\(\mathbf{x_1}, \mathbf{x_2} \in S \Rightarrow \alpha \mathbf{x_1} + (1 - \alpha) \mathbf{x_2} \in S\)
단, \( \alpha \in [0, 1] \)
여기서 '\(\alpha \mathbf{x_1} + (1 - \alpha) \mathbf{x_2}\)'란, 두 벡터 사이를 잇는 선이다.
식을 풀어보면 \(\mathbf{x_2} + \alpha(\mathbf{x_1} - \mathbf{x_2})\)로 나타낼 수 있는데,
이는 \(\alpha = 0\)일 때 벡터 \( \mathbf{x_2}\)의 종점, \(\alpha = 1\)일 때 벡터 \(\mathbf{x_1}\)의 종점을 나타낸다.
2) Convex Function
기본적으로 convex는 '볼록한'이라는 의미이다. 위의 그래프와 같이 함수가 볼록한 경우를 말한다.
구체적인 의미는 다음과 같다.
두 변수 \( x_1, x_2\)와 정의역 \(X\)에 대해
\(x_1, x_2 \in X, \alpha \in [0, 1]\)
\(f(\alpha x_1 + (1-\alpha) x_2) \leq \alpha f(x_1) + (1- \alpha)f(x_2)\)
여기서 \(\alpha x_1 + (1-\alpha) x_2\)는 x축 상에서 \(x_1\)부터 \(x_2\)까지를 의미하고, 따라서 좌변은 해당 부분의 그래프를 말한다.
우변은 점 \((x_1, f(x_1))\)과 \((x_2, f(x_2))\)를 잇는 직선(분홍색 직선 중 \(x_1\)부터 \(x_2\)까지)이다. 위 식은 그래프가 직선보다 작거나 같다는 것을 의미한다.
이에 따라 \(x_1\), \(x_2\)를 정의역 내에서 어떻게 잡든 만족하면 convex function인 것이다.
미분이 가능하다면, convex를 쉽게 판단할 수 있다. 단순히 정의역 내의 모든 x에 대해 두번 미분한 값이 0보다 같거나 크면 convex function이다.
\( \forall x, \{f(x)\}'' \geq 0 \Leftrightarrow convex \; function\)
좀 더 일반적인 상황을 생각해보자.
만약 \(f\)가 \(f(x) = f( \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} ) \) (단, \(\mathbf{x_1}\), \(\mathbf{x_2}\)는 벡터)와 같이 두 개 이상의 벡터에 대한 함수일 때, \(f(x)\)값, 즉 스칼라 값을 두 번 미분 가능하다면(Hessian Matrix가 존재한다면), 다음 조건을 만족할 때 Convex이다.
\( if \; Hessian \; matrix \; is \; positive \; semidefinite \; matrix \Leftrightarrow convex \)
positive semidefinite란, 스칼라의 음수, 양수를 판단하듯 matrix의 양수를 판단하는 개념이다.
열벡터 \(\mathbf{z}\), hessian matrix \(H\)에 대해 \( \mathbf{z}^T H \mathbf{z} \geq 0 \)이면 positive semidefinite를 만족하는 것이다. (행벡터 * 행렬 * 열벡터 형태의 곱이므로 결과값이 스칼라이다.)
3) Convex Optimization Problem 학습의 목적
Convex Optimization Problem은 local minimum(전제 : feasible set에 포함되어야 함)이 global minimum이 되는 단순한 문제이다.
이를 증명하는 과정은 생략한다. 단순히 기하학적 형태로 이해해보자.
따라서 복잡한 함수를 Convex Problem으로 바꿔줄 수만 있다면, Optimal Solution을 쉽게 찾을 수 있다.
4) Gradient Descent
Gradient Descent란, 함수에서 local minimum에 이르기 위해 함수 기울기의 반대 방향으로 이동시키는 과정이다.
단순히 Gradient는 방향을 나타내고, 얼마나 내려갈지는 step size (딥러닝에서의 learning rate)로 나타낸다.
Gradient는 경사(기울기), 즉 미분의 개념이다. (\(df/dx\))
간단한 과정을 알아보자.
- Initialize \(x_0\)
- \(x_{k+1} = x_{k} - \alpha \frac{df}{dx} \) (단, \(\alpha\)는 step size)
- 2번 과정 반복
2번 식에서 경사'하강'법이기 때문에 -를 붙여준다.
조금 일반화하여 (벡터를 입력으로 받는 경우) 예제를 하나 풀어보자.
예측값 벡터를 \(\mathbf{x}\), 어떤 변환 행렬 \(A\), 실제값 벡터를 \(\mathbf{z}\)라고 하면, \(\mathbf{z}\)는 다음과 같이 표현 가능하다.
\(\mathbf{z} = A \mathbf{x} + \mathbf{e} \) (단, \(\mathbf{e}\)는 오차)
cost function은 예를 들어 오차의 제곱 개념으로 설정할 수 있다.
하지만, 벡터는 제곱을 할 수 없으니 내적을 이용하여 표현할 수 있다.
\(f = (\mathbf{z} - A \mathbf{x})^T (\mathbf{z} - A \mathbf{x}) \)
initialize 과정은 넘어가고, 경사 하강의 핵심 과정을 살펴보자.
f는 스칼라이므로, 벡터로 미분하는 표현은 다음과 같다.
\( \begin{align*} df &= \frac{\partial f}{\partial \mathbf{x}}d\mathbf{x} \\ &= (-A d\mathbf{x})^T(\mathbf{z}-A \mathbf{x} ) - (\mathbf{z} - A \mathbf{x})^T A d \mathbf{x} \\ &= \{(-A d\mathbf{x})^T(\mathbf{z}-A \mathbf{x} )\}^T - (\mathbf{z} - A \mathbf{x})^T A d \mathbf{x} \\ &= -2(\mathbf{z} - A \mathbf{x})^T A d \mathbf{x} \end{align*} \)
\(\mathbf{x}\)는 모두 열벡터이므로, 위 식의 결과(행벡터)에 transpose를 취하여 경사하강법 식을 다음과 같이 표현한다. (step size를 조절해주면 되므로, 상수 2는 제외한다.)
\( \mathbf{x_{k+1}} = \mathbf{x_k} + \alpha A^T(\mathbf{z} - A \mathbf{x_k}) \)
최근댓글