경사 하강법

3. 선형 시스템 상에서의 풀이

경사 하강법은 다음과 같은 연립 일차 방정식을 푸는 데 사용될 수 있다.

:$A\backslash mathbf\{x\}-\backslash mathbf\{b\}=0$

이는 이차 최소화 문제로 다시 공식화될 수 있다. 계수 행렬 $A$가 실수 대칭이고 양정치인 경우, 목적 함수는 다음과 같은 이차 함수로 정의되며, 최소화가 이루어진다.

:$F(\backslash mathbf\{x\})=\backslash mathbf\{x\}^T\; A\backslash mathbf\{x\}-2\backslash mathbf\{x\}^T\backslash mathbf\{b\},$

따라서

:$\backslash nabla\; F(\backslash mathbf\{x\})=2(A\backslash mathbf\{x\}-\backslash mathbf\{b\}).$

일반적인 실수 행렬 $A$의 경우, 선형 최소 제곱법은 다음과 같이 정의된다.

:$F(\backslash mathbf\{x\})=\backslash left\backslash |A\backslash mathbf\{x\}-\backslash mathbf\{b\}\backslash right\backslash |^2.$

실수 $A$와 $\backslash mathbf\{b\}$에 대한 전통적인 선형 최소 제곱법에서는 유클리드 노름이 사용되며, 이 경우

:$\backslash nabla\; F(\backslash mathbf\{x\})=2A^T(A\backslash mathbf\{x\}-\backslash mathbf\{b\}).$

각 반복에서 국소적으로 최적인 단계 크기 $\backslash gamma$를 찾는 선형 탐색 최소화는 이차 함수에 대해 해석적으로 수행될 수 있으며, 국소적으로 최적인 $\backslash gamma$에 대한 명시적인 공식이 알려져 있다.^[11][12]

예를 들어, 실수 대칭이고 양정치인 행렬 $A$의 경우, 간단한 알고리즘은 다음과 같다.^[11]

:$\backslash begin\{align\}$

& \text{반복문 반복:} \\

& \qquad \mathbf{r} := \mathbf{b} - \mathbf{A x} \\

& \qquad \gamma := {\mathbf{r}^\mathsf{T} \mathbf{r}}/{\mathbf{r}^\mathsf{T} \mathbf{A r}} \\

& \qquad \mathbf{x} := \mathbf{x} + \gamma \mathbf{r} \\

& \qquad \hbox{만약 } \mathbf{r}^\mathsf{T} \mathbf{r} \text{ 이 충분히 작으면, 반복문 종료} \\

& \text{반복문 종료} \\

& \text{결과로 } \mathbf{x} \text{ 반환}

\end{align}

각 반복에서 $A$를 두 번 곱하는 것을 피하기 위해, $\backslash mathbf\{x\}\; :=\; \backslash mathbf\{x\}\; +\; \backslash gamma\; \backslash mathbf\{r\}$는 $\backslash mathbf\{r\}\; :=\; \backslash mathbf\{r\}\; -\; \backslash gamma\; \backslash mathbf\{A\; r\}$를 의미한다는 점에 유의하면, 전통적인 알고리즘을 얻을 수 있다.^[13]

:$\backslash begin\{align\}$

& \mathbf{r} := \mathbf{b} - \mathbf{A x} \\

& \text{반복문 반복:} \\

& \qquad \gamma := {\mathbf{r}^\mathsf{T} \mathbf{r}}/{\mathbf{r}^\mathsf{T} \mathbf{A r}} \\

& \qquad \mathbf{x} := \mathbf{x} + \gamma \mathbf{r} \\

& \qquad \hbox{만약 } \mathbf{r}^\mathsf{T} \mathbf{r} \text{ 이 충분히 작으면, 반복문 종료} \\

& \qquad \mathbf{r} := \mathbf{r} - \gamma \mathbf{A r} \\

& \text{반복문 종료} \\

& \text{결과로 } \mathbf{x} \text{ 반환}

\end{align}

이 방법은 선형 방정식을 푸는 데 거의 사용되지 않으며, 가장 인기 있는 대안 중 하나는 켤레 기울기법이다. 경사 하강법 반복 횟수는 일반적으로 계수 행렬 $A$의 스펙트럼 조건수 $\backslash kappa(A)$ (의 최대 고유값과 최소 고유값의 비율)에 비례하는 반면, 켤레 기울기법의 수렴은 일반적으로 조건수의 제곱근에 의해 결정되므로 훨씬 빠르다. 두 방법 모두 전처리의 이점을 얻을 수 있으며, 경사 하강법은 전처리기에 대한 가정이 덜 필요할 수 있다.^[13]

4. 비선형 시스템 상에서의 풀이

경사하강법은 비선형 방정식계를 푸는 데에도 사용할 수 있다. 다음은 경사하강법을 사용하여 세 개의 미지수 ''x''₁, ''x''₂, ''x''₃를 구하는 예시이다.

다음과 같은 비선형 방정식계를 고려하자.

:$\backslash begin\{cases\}$

3x_1-\cos(x_2x_3)-\tfrac{3}{2} =0 \\

4x_1^2-625x_2^2+2x_2-1 = 0 \\

\exp(-x_1x_2)+20x_3+\tfrac{10\pi-3}{3} =0

\end{cases}

이 방정식계와 관련된 함수 $G(\backslash mathbf\{x\})$를 다음과 같이 정의한다.

:$G(\backslash mathbf\{x\})\; =\; \backslash begin\{bmatrix\}$

3x_1-\cos(x_2x_3)-\tfrac{3}{2} \\

4x_1^2-625x_2^2+2x_2-1 \\

\exp(-x_1x_2)+20x_3+\tfrac{10\pi-3}{3} \\

\end{bmatrix},

여기서

:$\backslash mathbf\{x\}\; =\backslash begin\{bmatrix\}$

x_1 \\

x_2 \\

x_3 \\

\end{bmatrix}.

목적 함수 $F(\backslash mathbf\{x\})$는 다음과 같이 정의할 수 있다.

:

&{}\qquad\left. \left(\exp(-x_1x_2) + 20x_3 + \frac{10\pi-3}{3} \right)^2 \right].\end{align}

초기값 $\backslash mathbf\{x\}^\{(0)\}=\; \backslash mathbf\{0\}\; =\; \backslash begin\{bmatrix\}$

0 \\

0 \\

0 \\

\end{bmatrix}에서 시작하여 최소값을 찾는다.

다음 단계의 값은 다음과 같이 계산된다.

:$\backslash mathbf\{x\}^\{(1)\}=\backslash mathbf\{0\}-\backslash gamma\_0\; \backslash nabla\; F(\backslash mathbf\{0\})\; =\; \backslash mathbf\{0\}-\backslash gamma\_0\; J\_G(\backslash mathbf\{0\})^\backslash mathrm\{T\}\; G(\backslash mathbf\{0\}),$

여기서 야코비 행렬 $J\_G$는 다음과 같다.

:$J\_G(\backslash mathbf\{x\})\; =\; \backslash begin\{bmatrix\}$

3 & \sin(x_2x_3)x_3 & \sin(x_2x_3)x_2 \\

8x_1 & -1250x_2+2 & 0 \\

• x_2\exp{(-x_1x_2)} & -x_1\exp(-x_1x_2) & 20\\

• 2.5\\
• 1\\

• 7.5\\
• 2\\

• 0.20944 \\

5. 평가 및 장단점

경사 하강법은 다양한 장점과 단점을 가지며, 다른 최적화 알고리즘과 비교하여 특징을 살펴볼 수 있다.

경사 하강법은 모든 차원과 모든 공간에서 적용 가능하며, 심지어 무한 차원(함수 공간)에서도 사용 가능하다.^[10] 기울기(1계 미분)만을 고려하기 때문에 방법이 간편하고 계산 속도가 빠르다.^[10]

하지만, 경사 하강법은 지역 최적해로 수렴하는 경향이 있으며, 전역적인 최적해를 보장하지 않는다.^[34] 시작점 $\backslash mathbf\{x\}\_0$의 선택에 따라 결과가 달라지기 때문에, 여러 시작점에 대해 하강법을 적용하여 가장 좋은 결과를 선택하는 방법이 사용되기도 한다.

또한, 경사 하강법은 안장점 근방에서 속도가 느려질 수 있다. 제약 없는 이차 최소화 문제에서조차, 반복이 진행됨에 따라 후속 값들의 지그재그 패턴을 생성하여 수렴 속도가 느려진다. 함수의 곡률에 따라서 거의 같은 위치에서 시작했음에도 불구하고 완전히 다른 결과로 이어질 수도 있다.

정확성을 위해서는 극값으로 이동함에 있어 매우 많은 단계를 거쳐야 하며, 단계 크기(학습률) γ가 너무 작으면 수렴이 느려지고, γ가 너무 크면 발산하게 되므로, γ의 적절한 설정을 찾는 것이 중요하다.^[8]

이러한 경사 하강법의 단점을 극복하기 위해 여러 개선 방법이 제안되었다. 예를 들어, 모멘텀^[15], 네스테로프 가속 경사법^[16], 프랭크-울프^[17]와 같은 방법들이 있다. 또한, Adam, DiffGrad, Yogi, AdaBelief 등과 같이 지수 이동 평균^[18] 및 양수-음수 모멘텀^[19]을 활용하는 최적화 알고리즘도 개발되었다.

뉴턴 방법 및 헤세 행렬의 역행렬을 켤레 기울기 기법을 사용하여 계산하는 방법이 더 나은 대안이 될 수 있지만,^[20][21] 일반적으로 이러한 방법은 더 적은 반복으로 수렴하지만, 각 반복의 비용은 더 높다. 매우 큰 문제의 경우, L-BFGS와 같은 제한된 메모리 방법을 사용해야 한다.

5. 1. 장점

5. 2. 단점

• 지역 최솟값 문제: 경사 하강법은 현재 위치에서 기울기가 가장 가파른 방향으로 이동하기 때문에, 지역 최솟값(local minimum)에 빠지면 전역 최솟값(global minimum)으로 이동하지 못하고 갇힐 수 있다. 이는 마치 산에서 안개 속에 갇혀 내려갈 때, 작은 구덩이에 빠져 더 낮은 곳으로 가지 못하는 상황과 유사하다.
• 안장점 문제: 안장점(saddle point)은 한 방향에서는 극솟값이지만 다른 방향에서는 극댓값인 지점이다. 경사 하강법은 안장점 근처에서 기울기가 0에 가까워져 매우 느리게 수렴하거나, 잘못된 방향으로 이동할 수 있다.
• 평탄한 영역 문제: 함수의 표면이 평탄한 영역(plateau)에서는 기울기가 매우 작아져 경사 하강법의 이동 속도가 매우 느려진다. 이는 마치 넓고 평평한 고원에 갇힌 것과 유사한 상황이다.
• 학습률(learning rate) 설정 문제: 학습률은 한 번에 얼마나 크게 이동할지를 결정하는 값이다. 학습률이 너무 작으면 수렴 속도가 느려지고, 너무 크면 발산하거나 최적점을 지나칠 수 있다.
• 곡률(curvature) 문제: 함수의 곡률이 방향에 따라 크게 다르면, 경사 하강법은 특정 방향으로 진동하며 수렴 속도가 느려질 수 있다. 이는 마치 좁고 구불구불한 계곡을 따라 내려가는 것과 유사한 상황이다.

5. 3. 모멘텀 (Momentum)

5. 4. 빠른 경사 방법 (Fast Gradient Methods)

5. 5. 기타 방법

6. 프로그램 코드 예제

다음은 파이썬 언어로 작성한 경사 하강법 알고리즘으로, f|에프^영어(x) = x⁴ − 3x³ + 2 함수의 극값을 미분값인 f|에프^영어'(x) = 4x³ − 9x²를 통해 찾는 예시를 보여준다.^[36]

```python

# 계산을 통해 극솟값이 x=9/4에서 발생할 것이라고 예상할 수 있다.

x_old = 0

x_new = 6 # 알고리즘은 x=6에서 시작한다.

eps = 0.01 # 이동 크기(step size)

precision = 0.00001

def f_prime(x):

return 4 * x3 - 9 * x2

while abs(x_new - x_old) > precision:

x_old = x_new

x_new = x_old - eps * f_prime(x_old)

print(f"극솟값은 다음 위치에서 발생한다: {x_new}")

```<sup>[37]</sup>

위 코드는 x 값 하나에 대해서만 극값을 파악한다. 실제로는 여러 개의 특징값(feature)들이 있으므로, 해당 값들마다 '''병행적으로''' 결과 값을 구하면서 반복해야 한다.

7. 한국에서의 활용 및 연구 동향

이 문단은 비어 있습니다. 내용을 추가해 주세요.

참조

<sub>[1]</sub> 서적 Convex Optimization http://dx.doi.org/10[...] Cambridge University Press 2004-03-08
<sub>[2]</sub> 학술지 Cauchy and the Gradient Method https://www.math.uni[...] 2020-01-26
<sub>[3]</sub> 학술지 Mémoire sur le problème d'analyse relatif à l'équilibre des plaques élastiques encastrées 1908
<sub>[4]</sub> 학술지 Variational methods for the solution of problems of equilibrium and vibrations 1943
<sub>[5]</sub> 학술지 The Method of Steepest Descent for Non-linear Minimization Problems
<sub>[6]</sub> 학술지 Two-Point Step Size Gradient Methods
<sub>[7]</sub> 서적 Optimization and Control with Applications Springer
<sub>[8]</sub> 학술지 Convergence Conditions for Ascent Methods 1969-04
<sub>[9]</sub> arXiv On the distance between two neural networks and the stability of learning 2020-06-12
<sub>[10]</sub> 서적 Adaptive filter theory Pearson Education India
<sub>[11]</sub> 서적 Introduction to Optimization https://www.research[...]
<sub>[12]</sub> 서적 Iterative methods for sparse linear systems https://archive.org/[...] Society for Industrial and Applied Mathematics
<sub>[13]</sub> 학술지 Nonsymmetric Preconditioning for Conjugate Gradient and Steepest Descent Methods
<sub>[14]</sub> 서적 Functional Analysis Pergamon Press
<sub>[15]</sub> 학술지 Survey of Optimization Algorithms in Modern Neural Networks 2023-01
<sub>[16]</sub> 학술지 Generalized Momentum-Based Methods: A Hamiltonian Perspective https://epubs.siam.o[...] 2021-01
<sub>[17]</sub> 학술지 Accelerated Frank–Wolfe Algorithms http://epubs.siam.or[...] 1974-11
<sub>[18]</sub> arXiv Adam: A Method for Stochastic Optimization 2017-01-29
<sub>[19]</sub> 학술지 Positive-Negative Momentum: Manipulating Stochastic Gradient Noise to Improve Generalization https://proceedings.[...] PMLR 2021-07-01
<sub>[20]</sub> 서적 Numerical Recipes in C: The Art of Scientific Computing https://archive.org/[...] Cambridge University Press
<sub>[21]</sub> 서적 Data Fitting and Uncertainty: A Practical Introduction to Weighted Least Squares and Beyond Springer Vieweg
<sub>[22]</sub> 학술지 An optimal control theory for nonlinear optimization 2019-07
<sub>[23]</sub> 서적 Introductory Lectures on Convex Optimization : A Basic Course Springer
<sub>[24]</sub> 웹사이트 Fast Gradient Methods https://www.seas.ucl[...] 2019
<sub>[25]</sub> 학술지 Nesterov's Method for Convex Optimization https://epubs.siam.o[...] 2023
<sub>[26]</sub> 학술지 Optimized First-order Methods for Smooth Convex Minimization
<sub>[27]</sub> 학술지 The Exact Information-based Complexity of Smooth Convex Minimization 2017
<sub>[28]</sub> 학술지 On the momentum term in gradient descent learning algorithms 1999-01
<sub>[29]</sub> 웹사이트 Momentum and Learning Rate Adaptation http://www.willamett[...] Willamette University 2014-10-17
<sub>[30]</sub> 웹사이트 The momentum method https://www.coursera[...] 2018-10-02
<sub>[31]</sub> 서적 Fixed-Point Algorithms for Inverse Problems in Science and Engineering Springer
<sub>[32]</sub> 웹사이트 Mirror descent algorithm https://tlienart.git[...]
<sub>[33]</sub> arXiv Theory of Convex Optimization for Machine Learning
<sub>[34]</sub> 서적 最適化の数学 共立出版 2011-06-23
<sub>[35]</sub> 기타 경사 상승법
<sub>[36]</sub> wiki 미분을 통해 계수를 유도하는 이유
<sub>[37]</sub> 블로그 이 코드에 대한 해설 https://m.blog.naver[...]