[Diffusion Models] 확산 모델 이해하기 (2) - Euler's Method

 

Euler’s method(오일러 기법)

 

Euler’s method(오일러 기법)은 초기 조건(Initial Condition)을 알고 있는 상미분방정식(ODE)의 해를 근사하기 위한 가장 간단한 형태의 수치해석(Numerical Analysis) 기법입니다.

 

즉, ODE에 의해 결정되는 벡터장의 방향(미분의 정보)을 따라 아주 작은 스텝으로 이동함으로써, 전체 해(커브)를 단계적으로 근사해 나가는 방식입니다.

Diffusion Model이나 Score-based Generative Model을 이해하기 위해서는, 역방향 과정(Reverse Process)을 해석할 때 ODE(또는 확률적 미분방정식 SDE)에 대한 수치해가 중요합니다.

 

Euler’s method는 이러한 수치해 기법 중 가장 기초가 되는 방법으로, SDE 해법인 Euler–Maruyama Method의 기반이 되기도 합니다. 이번 글에서는 오일러 기법의 동기와 원리를 간단히 살펴보겠습니다.

 

---

 

 

1. Motivation

 

1-1. ODE의 기본 형태

 

일반적인 ODE는 다음과 같은 형태를 가집니다.

 

$\frac{dx(t)}{dt} = f (x(t),t)$

 

- $x(t)$ : 시간 $t$에서의 미지함수 (해)

- $\frac{dx(t)}{dt}$ : $x(t)$가 $t$에 따라 변하는 비율 (기울기)

 

우리가 ODE를 푼다는 것은, 위 식과 초기 조건 $x(t_0)$을 동시에 만족하는 해 $x(t)$를 구하는 것과 같습니다.

 

그러나, 이 식을 직접 적분하여 해석적으로(Analytically) 구하기는 쉽지 않을 수 있습니다.

 

그래서, 수치해석적 접근인 Euler's method가 등장합니다.

 

 

 

<적분을 하기 위해 아래 수식을 풀어야 하는데 쉽지 않음>

 

 

$\mathbf{x} (t_0 + \Delta t) = \mathbf{x} (t_0) + \int_{t_0}^{t_0 + \Delta t} f(x(t), t) dt$

 

 

 

1-2. First-order Taylor Expansion 관점

 

ODE를 아주 작은 시간 구간 $\Delta t$로 쪼개어 생각해보면, 다음과 같은 First-order Taylor Expansion을 적용할 수 있습니다.

 

$x(t + \Delta t) \approx x(t) + \frac{dx(t)}{dt} \dot \Delta t$

 

그리고, $\frac{dx(t)}{dt} = f (x(t),t)$임을 이용하면,

 

$x(t + \Delta t) \approx x(t) + f (x(t),t) \Delta t$

 

즉, 현재 시점에서의 기울기 (벡터장) 정보를 이용해 다음 시점의 값을 근사할 수 있습니다.

 

이것이 Euler's method의 핵심 아이디어 입니다.

 

2. Euler's Method

 

2-1. 알고리즘 (순서)

 

Euler's method는 다음과 같은 절차로 진행.

 

1. 초기 조건 $x(t_0)$와 고정된 스텝 크기 $\Delta t$를 정한다.
2. 현재 시점 $t_k$에서의 기울기 $f(x(t_k),t_k)$를 계산한다.
3. 다음 식을 통해 다음 시점의 값을 근사한다.
   1. $x(t_{k+1}) = x(t_k) + f(x(t_k),t_k) \Delta t$
4. 2-3 과정을 원하는 최종 시점까지 또는 필요한 횟수 만큼 반복한다.

 

 

2-2. 도식적 해석

 

아래 내용처럼 간단히 기울기가 알려진 지점에서 그 방향으로 $\Delta t$만큼 선형적으로 이동하여 다음 점을 구하고, 이를 반복 연결해 해를 추정해 나가는 과정을 나타낸다.

 

(t0) -- f(x(t0), t0) --> (t1) -- f(x(t1), t1) --> (t2) ...

 

step $\Delta t$가 충분히 작을 수록 실제 Curve와의 오차가 작아진다.

 

하지만 $\Delta t$가 너무 작으면 계산량이 크게 늘어나므로, 적절한 step size를 선택하는 것이 중요하다.

 

 

 

3. Example

실제 예시로, $x(t)$ 대신, $y$를, $t$ 대신 $x$를 사용해 1차 ODE 문제를 풀어봅시다.

 

간단한 형태의 다음 문제를 생각해봅시다.

 

$\frac{dy}{dx} = x + y$

 

$y(0) = 0$

 

이를 구간 [0,1]에서 5개의 step으로 나눈다고 가정하면, $\Delta x = 0.2$가 된다.

 

1. 초기 조건 $y_0 = y(0) = 0$
2. 첫 번째 근사 $y_1$:
   1. $y_1 = y_0 + [x_0 + y_0] \times \Delta x = 0 + (0 + 0) \times 0.2 = 0$
3. 두 번째 근사 $y_2$
   1. $y_2 = y_1 + [x_1 + y_1] \times \Delta y = 0 + (0.2 + 0) \times 0.2 = 0.04$
4. 이런 식으로 계속 반복하며 $y_5$까지 구합니다.

 

이 과정을 통해 얻은 최종값 $y_5$가, 이론적 해(Explicit Solution)를 적분으로 구했을 때의 $y(1)$ 값에 근접한다면, Euler's method가 성공적으로 근사했다고 볼 수 있습니다.

 

실제로, $\Delta x$를 더 작게 하거나, 더 정교한 방법 (Heun's methods,, ...)등을 사용하면 오차가 줄어듭니다.

 

 

 

4. Diffusion Model and Euler's Method

 

Diffusion Model or Score-based Generative Model에서, SDE 형태로 Forward process와 Reverse Process를 정의하는 경우가 많습니다.

 

예를 들어,

 

$d \mathbf{x} = f(\mathbf{x}, t) dt + g(\mathbf{x}, t) d\mathbf{w}(t)$

 

와 같은 SDE에서, Euler's method를 확장한 Euler-Maruyama Method로 각 step을 근사해 나가면서 Sampling을 진행합니다.

 

Euler-Maruyama Method는 확률적 항 $d\mathbf{w}(t)$를 Gaussian noise로 대체하는 방식으로, 오일러 기법의 아이디어를 그대로 가져가지만 SDE에 맞게 변형한 것입니다.

 

즉,

• Euler's method: ODE에 대한 기초적 수치해법
• Euler-Maruyama method: SDE에 대한 확장 기법

 

따라서, 오일러 기법을 이해해 두면, 확률 미분방정식을 이용한 Diffusion Model의 Sampling 단계가 어떻게 구성되는지 조금 더 쉽게 파악할 수 있습니다.

 

In Summary

 

이번 글에서는 가장 단순한 수치해석 기법인 Euler’s method를 살펴보았습니다.

Motivation : ODE를 직접 적분하기 어렵기 때문에 수치적 근사 방법이 필요
근사 방식 : 현재 시점에서의 기울기를 이용해 작은 스텝만큼 전진
예시 : 간단한 1차 ODE 문제를 작은 스텝으로 나누어 반복 계산
확장 : Euler–Maruyama Method로 SDE(특히 Diffusion Model) 해석에 활용

 

 

 

Ref

 

https://process-mining.tistory.com/208

 

 

Song, Y., & Ermon, S. (2019). “Generative Modeling by Estimating Gradients of the Data Distribution.” Advances in Neural Information Processing Systems (NeurIPS).

 

 

Ho, J., Jain, A., & Abbeel, P. (2020). “Denoising Diffusion Probabilistic Models.” arXiv:2006.11239.

 

 

Song, Y., Sohl-Dickstein, J., Kingma, D. P., Kumar, A., Ermon, S., & Poole, B. (2021). “Score-Based Generative Modeling through Stochastic Differential Equations.” International Conference on Learning Representations (ICLR).

 

Kloeden, P. E., & Platen, E. (1992). Numerical Solution of Stochastic Differential Equations. Springer.