Insights
AI가 자동으로 큐레이션·번역·정리하는 기술 동향 피드입니다.
본 기사는 최소값을 찾는 반복 알고리즘(최대 하강법, 뉴턴법, 준뉴턴법)을 비교 분석합니다. 목적 함수를 직접 풀기 어려운 경우, 현재 위치에서 점진적으로 기울기가 0인 지점에 근접하는 방법을 다룹니다. 직선 탐색법의 원리와 알미호 조건 등 수리 최적화 기법에 대한 깊이 있는 이해를 제공하며, 실제 다중 회귀 문제 해결 예시를 통해 학습합니다.
AI 자동 생성 콘텐츠
본 콘텐츠는 Zenn ML의 원문을 AI가 자동으로 요약·번역·분석한 것입니다. 원 저작권은 원저작자에게 있으며, 정확한 내용은 반드시 원문을 확인해 주세요.
원문 바로가기『분석가를 위한 수리 최적화 입문』(이토 모토하루・하라다 코헤이・마츠오카 유키, 소시무, 2026년)의 제3장을 4편에 나누어 기사로 작성하고 있습니다. 이 글은 두 번째 편으로, 최소값을 반복적으로 찾는 알고리즘을 다룹니다.
목적 함수를 최소화하는 지점에서는 기울기(편미분을 나열한 벡터)가 0이 됩니다. 기울기가 0이 되는 점을 식 변형으로 직접 구할 수 있는 문제도 있지만, 로지스틱 회귀처럼 직접 풀 수 없는 문제가 많습니다. 이때 사용하는 것이 현재 위치에서 목적 함수가 조금씩 작아지는 방향으로 이동하여, 기울기가 0인 점에 가까워지는 알고리즘입니다.
본 기사에서는 답이 알려진 문제를 일부러 반복적으로 풀어봅니다. 답과 비교함으로써, 알고리즘이 올바른 지점에 도달했는지, 그리고 몇 번 만에 도달했는지를 확인할 수 있기 때문입니다.
글을 다 읽고 나면 다음 질문에 답할 수 있기를 목표로 합니다.
수식에는 고등학교 미분과 벡터 내적, 대학교 1학년 정도의 편미분과 행렬을 사용합니다. 새로운 도구가 나올 때마다 짧은 예시로 설명하겠습니다.
웹 서버의 가상 모니터링 데이터(40분 분)를 사용하여, 평균 응답 시간을 요청 수와 평균 응답 크기의 1차식으로 예측하는 다중 회귀 문제를 풀 것입니다.
결정할 값(변수)은
np.linalg.lstsq
입니다. 그 답을
만들 파일은 다음 4가지입니다.
| 파일 | 역할 |
|---|---|
server_data.py | 가상 모니터링 데이터 생성 |
optimizers.py | 직선 탐색법(최대 하강법・뉴턴법・BFGS법)을 직접 구현 |
compare.py | 다중 회귀 문제를, 직접 만든 3가지 방법과 SciPy의 3가지 방법으로 풀고 비교 |
newton_1d.py | 뉴턴법이 발산하는 예시를 확인 |
제약 조건이 있는 문제(변수에 상한이나 하한이 있는 문제)는 이번에는 다루지 않습니다.
| 항목 | 구동 환경 |
|---|---|
| OS | Windows 11 |
| ... |
직선 탐색법은 다음 식을 반복하여 점
| 기호 | 명칭 | 의미 |
|---|---|---|
| 탐색 방향 | 어느 쪽으로 갈지 (벡터) | |
| 스텝 사이즈 | 그 방향으로 얼마나 갈지 (양의 수) |
'먼저 방향을 정하고, 다음으로 그 방향의 직선 위에서 진행 폭을 결정한다'고 하므로, 직선 탐색법이라고 부릅니다. 이 기사에서 다루는 3가지 방법 모두 이 틀 안에서 방향입니다.
유한 번의 반복만으로는 기울기가 정확히 0이 되는 경우는 거의 없습니다. 그래서 기울기의 크기
방향
1변수의 경우, 점
여기서,
높이의 변화 $ allingdotseq$ 경사 × 가로로 움직인 거리라는 의미입니다. 예를 들어
다변수에서는 미분
고등학교에서 배운 내적 공식 기울기와의 각도라는 의미입니다.
방향이 내리막길이라 하더라도, 너무 많이 가면 계곡을 넘어서 반대쪽 사면을 오르거나, 오히려
부터 시작할 $\alpha = 1 - $알미호 조건을 만족한다면, 그
를 사용할 $\alpha$ - 만족하지 못하면,
를 반으로($\alpha$ 배) 줄여서 2로 돌아갑니다.$
ho = 0.5$
크기가 큰 scipy.optimize.line_search
의 기본값과 같습니다.
알고리즘이 올바르게 작동하는 것을 어떻게 보장할지 생각해봅니다. 이상적인 것은 '어떤 초기점에서 시작하든, 전역 최적해에 도달'하는 것이지만, 이는 너무 엄격한 요구입니다. 그래서 다음 2가지 성질로 생각합니다.
| 성질 | 의미 |
|---|---|
| 전역적 수렴성 | 어떤 초기점에서 시작하더라도, 정지점(기울기가 0인 점)에 가까워진다 |
| 국소적 수렴성 | 정지점에 충분히 가까운 초기점에서 시작하면, 그 정지점에 가까워진다 |
스텝 사이즈에 알미호 조건을 부과하는 것은 전역적 수렴성을 보장하기 위함입니다. 하강 조건을 만족하는 방향으로, 알미호 조건을 만족하는 보폭으로 진행한다면, 매번
참고로, 임계점(停留点)이 반드시 최소점인 것은 아닙니다. 목적 함수가 볼록 함수(오목한 그릇 모양의 함수)라면, 임계점은 최소점이 됩니다. 이번 회귀 분석의 목적 함수는 볼록 함수입니다.
최단강하법은 해당 지점에서 가장 가파른 내리막길 방향으로 진행하는 방법입니다. '가장 가파른 내리막길'은 길이가 1인 방향에 대해 그래디언트와 정반대 방향일 때 최소가 됩니다.
그 길이는 스텝 사이즈(step size)로 결정됩니다.
최단강하법은 그래디언트만으로 계산할 수 있어 간단합니다. 하지만 등고선이 가늘고 긴 타원 형태의 함수에서는 계곡을 가로지르는 방향으로 진행하게 되어, 지그재그로 왕복하며 느리게 전진하는 경향이 있습니다. 이 약점은 6-2에서 실제로 확인할 수 있습니다.
최단강하법은 1차 근사(접선)를 사용하여 방향을 결정했습니다. 이 근사를 한 단계 더 정밀하게 하여, 2차 근사(포물선)를 사용하는 것이 뉴턴법입니다.
변수가 1개일 경우, 지점 $x_k$에서 함수 $f(x)$의 다음 점 $x_{k+1}$은 다음과 같습니다.
$$x_{k+1} = x_k - rac{f'(x_k)}{f''(x_k)}$$
이 스텝 사이즈를 1로 설정하면, 한 번의 업데이트로 다음 점은 다음과 같이 됩니다.
$$x_{k+1} = x_k -
abla^2 f(x_k)^{-1}
abla f(x_k)$$ (수식 생략)
변수가 여러 개인 경우, 2계 미분 $
abla^2 f$를 사용하여 다음과 같이 계산합니다.
$$x_{k+1} = x_k - [
abla^2 f(x_k)]^{-1}
abla f(x_k)$$ (수식 생략)
마찬가지로, 헤세 행렬(Hessian matrix)이 역행렬을 가지는(정칙적인) 경우에 이 방정식은 풀립니다.
만약 목적 함수가 2차 함수라면, 2차 근사값은 근사가 아니라 원래의 함수 그 자체입니다. 따라서 2차 함수의 경우 뉴턴법은 1회의 반복으로 최소점에 도달합니다. 회귀 분석의 오차 제곱합(Sum of Squared Errors)은 2차 함수이므로, 6-1에서 1회 만에 도착하는 것을 확인할 수 있습니다.
뉴턴법에는 두 가지 큰 약점이 있습니다.
첫째는 전역적 수렴성(Global Convergence)이 없다는 것입니다. 스텝 사이즈를 항상 1로 설정한 순수 뉴턴법은 초기점이 임계점에서 멀리 떨어져 있으면 발산할 수 있습니다. 예를 들어, 다음 함수를 생각해 봅시다.
매번 업데이트할 때마다 (수식 생략)
둘째는 헤세 행렬의 계산이 무겁다는 것입니다. 변수가 $D$개일 경우, $
abla^2 f(x)$를 계산하는 것은 많은 연산을 필요로 합니다.
준뉴턴법은 헤세 행렬을 직접 계산하는 대신, 그래디언트의 변화를 통해 근사 행렬을 만들어 나가는 방법입니다.
변수가 1개일 경우, 2계 미분은 '미분의 변화율'이므로, 직전 두 지점의 미분을 사용하여 다음과 같이 근사할 수 있습니다.
$$f''(x_k) rac{x_{k+1} - x_k}{x_{k+1} - x_k}$$ (수식 생략)
변수가 여러 개인 경우, 이동한 양 $ ext{s}k = x{k+1} - x_k$와 그래디언트의 변화 $ ext{y}k =
abla f(x{k+1}) -
abla f(x_k)$를 사용하여 다음과 같은 근사 행렬 $B_{k+1}$을 만듭니다.
$$B_{k+1} = B_k + rac{ ext{y}_k ext{y}_k^T}{ ext{y}_k^T ext{s}_k}$$ (수식 생략)
이 식을 만족하는 행렬은 많기 때문에, 이전의 $B_k$를 업데이트할 때 다음과 같은 공식을 사용합니다.
$$B_{k+1} = B_k + rac{ ext{y}_k ext{y}_k^T}{ ext{y}_k^T ext{s}_k} - rac{(B_k ext{s}_k)(B_k ext{s}_k)^T}{( ext{s}_k^T B_k ext{s}_k)}$$ (수식 생략)
BFGS법의 중요한 성질은, 근사 행렬이 양의 정부호(Positive Definite)인 한, BFGS법의 방향은 반드시 내리막길이라는 것입니다. 순수 뉴턴법에서는 헤세 행렬이 양의 정부호가 아닌 지점에서 이 보장이 없습니다.
다만, BFGS법도 L-BFGS-B는 변수의 상한과 하한을 다루는 기능을 추가한 것입니다.
최단강하법은 직전 어느 방향으로 진행했는지와 관계없이 매번 그래디언트의 역방향으로 진행합니다. 따라서 가늘고 긴 계곡에서는 같은 곳을 왕복하는 경향이 있습니다. 공액 기울기법(CG법)은 이전 방향을 반영하여 다음 방향을 결정함으로써 이러한 왕복을 줄이는 방법입니다.
2차 함수의 경우, 공액 기울기법은 이전 방향 $ ext{s}k$과 직전 방향의 최소점까지 정확하게 진행하면, 변수가 $D$개일 때 다음과 같은 관계가 성립합니다.
$$ ext{s}{k+1} = ext{s}_k + ext{y}_k$$ (수식 생략)
이것은 2차 함수 외에도 사용할 수 있도록 확장한 비선형 공액 기울기법(Polak–Ribière method)입니다.
"""웹 서버의 가상의 모니터링 데이터를 생성합니다 (난수 시드를 고정)."""
import numpy as np
# 정답 파라미터. 최적화로 이 값에 가까운 답이 나오는지 확인합니다.
...
혼잡한 시간대일수록 응답도 커진다는 관계를 넣은 가상의 데이터입니다. 시드를 고정했기 때문에, 몇 번을 실행해도 같은 데이터가 나옵니다.
"""직선 탐색법: 알파호 조건의 백트래킹과 3가지 종류의 탐색 방향"""
import numpy as np
def backtracking(f, x, d, g, alpha=1.0, rho=0.5, c1=1e-4):
...
| 함수 | 하는 일 | 제1장~제4장과의 대응 |
|---|---|---|
backtracking | 알파호 조건(Armijo condition)을 만족할 때까지, | 1-3 |
steepest_descent | 제2장 | |
newton | 제3-1 | |
bfgs | 제4-1 |
세 함수는 방향 backtracking으로 보폭을 결정하고, 그래디언트의 크기가 tol에 도달하면 (최대 반복 횟수(max_iter)에 도달할 때까지 실행됩니다. 반환값인 history는 각 반복에서의 그래디언트 크기 리스트이며, len(history) - 1
가 반복 횟수입니다.
"""다중 회귀의 오차 제곱합을, 반복으로 최소화하는 방법들끼리 비교"""
from pathlib import Path
import matplotlib
...
| 부분 | 의미 |
|---|---|
X_raw | 1열, 요청 수, 크기를 원래 단위 그대로 나열한 행렬 |
X_std | 요청 수와 크기를 각각 "평균을 빼고 표준편차로 나누는" 표준화(standardization)를 한 행렬 |
to_original | 표준화된 데이터로 구한 계수를, 원래 단위의 |
f ,grad ,hess | 목적 함수, 기울기 (gradient), 헤세 행렬 (Hessian) |
np.linalg.cond | 헤세 행렬의 조건수(condition number) (최대 고유값 ÷ 최소 고유값). 클수록 등고선이 길쭉한 타원형입니다 |
minimize(..., method=...) | SciPy의 BFGS, CG, L-BFGS-B로 같은 문제를 풉니다 |
f
등을 lambda t, X=X:
라고 작성하는 것은, 루프 안에서 만든 함수가 각각의 루프에서의 X를 기억하도록 하기 위함입니다.
표준화로 계수를 원래 단위로 되돌리는 식은 다음과 같이 유도할 수 있습니다. 표준화된 값으로
uv run python compare.py
답 (lstsq): b = 57.98, a1 = 0.0507, a2 = 0.3176
--- 원래 단위 (헤세 행렬의 조건수 3208074.6)
직접 구현 경사 하강법: 반복 20000회, b = 0.81, a1 = 0.0565, a2 = 0.8078
...
결과를 표로 정리합니다.
| 방법 | 원래 단위 그대로 | 표준화한 후 |
|---|---|
| 직접 구현 경사 하강법 | 20,000회에서 중단 ( |
84회 |
| 직접 구현 뉴턴법 | 1회 | 1회 |
| 직접 구현 BFGS법 | 9회 | 10회 |
| SciPy BFGS | 5회 | 11회 |
| ... |
표준화된 데이터에서는 6가지 모든 방법이
직접 구현 뉴턴법은 1회 만에 도착했습니다. 3-1에서 본 것처럼, 목적 함수가 이차 함수이기 때문에, 이차 근사(quadratic approximation)가 원래 함수와 일치하기 때문입니다. 경사 하강법은 84회, BFGS법은 10회였습니다. BFGS법은 반복할 때마다 기울기의 변화로부터 곡률을 학습하므로, 경사 하강법보다 훨씬 적은 횟수로 도착합니다.
기울기 크기의 감소를 그림으로 그리면 다음과 같습니다 (세로축은 로그 스케일).
反復回数と勾配の大きさ
표준화된 경사 하강법(주황색)은 기울기 크기가 일정한 비율로, 직선적으로 줄어들고 있습니다. BFGS법(녹색)은 중간부터 급격히 줄어들고, 뉴턴법(빨간색)은 1회 만에
원래 단위 그대로에서는, 경사 하강법이 20,000번 반복해도, 절편
원인은 헤세 행렬의 조건수가 약 320만으로 매우 크기 때문입니다. 요청 수는 수백~천이고, 절편에 곱해지는 1열은 1이며, 자릿수 차이가 나는 값들이 나열되어 있어, 목적 함수의 등고선이 극단적으로 길쭉한 타원형을 이루고 있습니다. 경사 하강법의 방향은 등고선에 수직이므로, 길쭉한 계곡에서는 계곡을 가로지르는 방향만을 계속 가리키게 되고, 알미호 조건(アルミホ条件)으로 보폭도 작게 유지됩니다. 그 결과, 계곡 바닥을 따라 절편 방향으로는 거의 진행할 수 없습니다.
표준화하면, 조건수는 9.6까지 낮아졌습니다. 등고선이 원에 가까워지므로, 기울기의 역방향이 계곡 바닥 쪽을 향하게 되어, 84회 만에 도착했습니다.
한편, 뉴턴법과 BFGS법은 원래 단위 그대로에서도 각각 1회와 9회로 도착했습니다. 둘 다 헤세 행렬(또는 그 근사치)을 사용하여 방향을 결정하므로, 등고선의 길쭉함을 상쇄하도록 방향을 보정할 수 있기 때문입니다.
3-2의
"""f(x) = √(1 + x^2)를 뉴턴법으로 최소화한다. 스텝 사이즈를 조정하지 않으면 발산할 수 있다"""
import numpy as np
from optimizers import newton
...
uv run python newton_1d.py
x0 = 0.5: 순수 뉴턴법 (Pure Newton) 0.5 → -0.125 → 0.00195 → -7.45e-09 → 0
x0 = 0.5: 직선 탐색 사용 시 3회 만에 x = -7.5e-09
x0 = 1.5: 순수 뉴턴법 1.5 → -3.38 → 38.4 → -5.68e+04 → 1.83e+14
...
| 오류 또는 증상 | 원인 | 대처 방법 |
|---|---|---|
| 최단 하강법이 최대 반복 횟수까지 반복해도 멈추지 않음 | 변수의 스케일이 달라 헤세 행렬의 조건수가 클 때 | 6-2와 같이 표준화하여 풀거나 BFGS법 등으로 변경한다. |
| 뉴턴법 값이 갑자기 커짐 | 스텝 사이즈를 1로 고정하고 초기점이 멀리 떨어져 있을 때 | 6-3과 같이 알미호(Armijo) 조건으로 보폭을 조정한다. |
뉴턴법에서 np.linalg.LinAlgError: Singular matrix | ||
| 헤세 행렬이 역행렬을 갖지 못함 (같은 정보의 열이 두 개 있는 경우 등) | 변수를 재검토하거나, 헤세 행렬을 사용하지 않는 BFGS법 등으로 변경한다. | |
| Git Bash에서 출력을 파이프나 리다이렉트에 통과시키면 한글이 깨짐 | 출력 대상이 콘솔이 아닐 때 Python이 Windows의 문자 코드(cp932)로 출력함 | PYTHONUTF8=1 uv run python compare.py와 같이 UTF-8 모드로 실행한다. |
본 기사에서는 답을 알고 있는 다중 회귀 문제에 대해, 반복적으로 최소값을 찾는 알고리즘으로 다시 풀었습니다.
최단 하강법, 뉴턴법, 준뉴턴법은 '얼마나 곡률 정보(curvature)를 사용할지'로 이해하면 쉽습니다. 기울기만 사용하는 최단 하강법은 1회 계산이 가볍지만 스케일 차이에 약하고, 헤세 행렬을 쓰는 뉴턴법은 적은 횟수로 도착하지만 1회 계산이 무겁습니다. 준뉴턴법은 그 중간 지점을 차지하는 방법입니다.
