04. 최적화를 위한 수치해석 — 종이 위 방법을 코드에서 살리는 법

// BACKGROUND 4/6 — approximation error, floating-point arithmetic, iterative method, convergence, condition number

최적화 알고리즘은 수학적으로 맞아도 컴퓨터에서 불안정할 수 있습니다. 수치해석은 그 차이를 다루는 과목입니다.

Approximation error

근사는 정확한 값을 쉬운 값으로 바꾸는 일입니다. Taylor expansion, finite difference, surrogate model은 모두 근사입니다.

근사 오차는 보통 다음처럼 생각합니다.

\text{error}=\text{true value}-\text{approximation}.

오차가 줄어드는 속도를 알면 step size나 mesh size를 어떻게 정할지 판단할 수 있습니다.

컴퓨터의 실수는 유한한 비트로 저장됩니다. 그래서 실수 연산은 정확한 실수 연산이 아니라 반올림된 연산입니다.

문제는 작은 차이를 큰 수끼리 빼서 만들 때 생깁니다.

f(x+h)-f(x)

에서 $h$ 를 너무 작게 잡으면 두 수가 거의 같아서 유효숫자가 사라집니다. 수치 미분이 자동미분보다 불안정한 이유가 여기에 있습니다.

많은 최적화 알고리즘은 한 번에 답을 구하지 않습니다. 대신 sequence를 만듭니다.

x_0,x_1,x_2,\dots

각 반복에서 더 나은 후보로 이동하고, 충분히 좋아졌다고 판단하면 멈춥니다. Gradient descent, Newton, conjugate gradient가 모두 iterative method입니다.

convergence는 반복 sequence가 어떤 목표에 가까워지는 성질입니다.

알고리즘을 비교할 때는 “한 번의 반복이 싸냐”와 “몇 번 반복해야 하냐”를 함께 봐야 합니다.

condition number는 입력 오차가 출력 오차로 얼마나 증폭되는지 나타냅니다. 선형 시스템 $Ax=b$ 에서 condition number가 크면 작은 오차도 해를 크게 흔듭니다.

\kappa(A)=\|A\|\|A^{-1}\|.

Hessian의 condition number가 크면 길고 좁은 골짜기 모양이 됩니다. Gradient descent는 이런 문제에서 zigzag를 하며 느려집니다. Preconditioning은 이 골짜기를 더 둥글게 바꾸려는 시도입니다.