왜 Backprop이 그렇게 효율적인가 — 계산 복잡도와 Gradient 구조

난이도: 기초

태그: 기초수학,최적화,딥러닝기초

분류: foundations

타입: concept

선수지식: 있음 — 미분, gradient, 경사하강법

역전파의 기본 원리를 알았다면, 다음 질문은 "왜 수천억 파라미터 모델을 학습할 수 있는가"다. 이 문서는 그 이유를 세 가지 관점에서 설명한다.

문제 설정

신경망 학습에서는 손실함수 L을 각 파라미터 w에 대해 미분한 값 ∂L/∂w가 필요합니다.

하지만 신경망은 여러 층의 합성함수이므로, 이 미분을 효율적으로 계산하기 위해 역전파(backpropagation)를 사용합니다.

핵심 결론

Backprop은 파라미터가 몇 개든 관계없이 forward 비용의 약 2배로 모든 gradient를 계산한다. 이것이 딥러닝이 현실에서 가능해진 가장 근본적인 이유다.

이 문서에서 다루는 세 가지

  1. Backprop이 O(forward)인 수학적 이유
  2. Low effective rank gradient — gradient가 저차원 공간에 집중되는 현상 (LoRA의 근거)
  3. Gradient Noise Scale — optimal batch size를 결정하는 개념 (OpenAI)

처음 보는 사람용 핵심 용어

1단. Naïve 방법의 문제

파라미터 1억 개짜리 모델의 gradient를 수치 미분으로 구하려면:

# 수치 미분: 파라미터 하나씩 ε 만큼 바꾸고 loss 변화 측정
for i in range(n_params):  # n_params = 1억
    w[i] += ε
    loss_plus = forward(x, w)
    w[i] -= ε
    grad[i] = (loss_plus - loss) / ε
# 총 비용: n_params × forward_cost = 1억 × forward

파라미터가 1억 개면 forward pass를 1억 번 해야 한다. GPT-3(175B)라면 1750억 번. 완전히 불가능하다.

2단. Backprop이 O(forward)인 이유 — 재사용

핵심은 intermediate gradient(δ)를 한 번 계산하고 재사용한다는 것이다.

# Forward: 각 layer의 출력 저장
z1 = layer1(x)     # 저장
z2 = layer2(z1)    # 저장
z3 = layer3(z2)    # 저장
y  = z3

# Backward: 뒤에서부터, 이전 δ 재사용
δ3 = dL/dz3                    # 1번 계산
δ2 = δ3 @ W3.T                 # δ3 재사용
δ1 = δ2 @ W2.T                 # δ2 재사용

# 각 W의 gradient
dL/dW3 = δ3.T @ z2             # δ3 재사용
dL/dW2 = δ2.T @ z1             # δ2 재사용
dL/dW1 = δ1.T @ x             # δ1 재사용

파라미터가 3개든 3억 개든, δ를 한 번 계산해두면 모든 W의 gradient를 추가 계산 없이 구할 수 있다. 전체 비용 = forward 1번 + backward 1번 ≈ 2 × forward.

방법계산 비용파라미터 1억 개 시
수치 미분O(n × forward)1억 × forward
BackpropO(forward)≈ 2 × forward

핵심 수식 — 재사용의 수학

# Chain rule: L = f3(f2(f1(x)))
dL/dx = (dL/df3) * (df3/df2) * (df2/df1) * (df1/dx)
#         δ3       local        local        local

# δ3를 먼저 계산하면:
δ3 = dL/df3                          # 1번만 계산
δ2 = δ3 * (df3/df2)                  # δ3 재사용
δ1 = δ2 * (df2/df1)                  # δ2 재사용
# dL/dx = δ1 * (df1/dx)              # δ1 재사용

# 각 파라미터 gradient도 δ 재사용:
dL/dW3 = δ3 * (∂f3/∂W3)
dL/dW2 = δ2 * (∂f2/∂W2)
dL/dW1 = δ1 * (∂f1/∂W1)

local gradient (∂f/∂W)는 forward 때 이미 계산한 값들로 구할 수 있다. 새로운 forward pass가 필요 없다.

3단. Low Effective Rank Gradient

최근 딥러닝 이론에서 중요한 관찰: 파라미터 공간이 수십억 차원이어도 실제 학습 중 gradient가 움직이는 방향은 수백~수천 차원에 불과하다.

왜 이런 현상이 생기나

자연 데이터는 고차원처럼 보이지만 실제로는 저차원 manifold 위에 있다.

데이터의 내재 차원이 낮으면 → gradient도 소수 방향으로 집중된다.

실험적 관찰

# gradient covariance의 eigenvalue 분포
eigenvalues = torch.linalg.eigvalsh(grad_cov)

# 결과: 상위 몇 개의 eigenvalue가 전체의 대부분을 차지
top_k_ratio = eigenvalues[-100:].sum() / eigenvalues.sum()
# 보통 상위 100개가 전체의 90%+ 설명

실용적 의미 — LoRA의 이론적 근거

gradient가 실제로 low-rank 공간에서 움직이기 때문에, full matrix 대신 low-rank 행렬만 학습해도 비슷한 효과를 낸다.

# Full fine-tuning: ΔW ∈ R^(d × k) — d×k 전체 업데이트
ΔW_full = ...  # 파라미터 d×k개 학습

# LoRA: low-rank 근사
A = nn.Parameter(torch.randn(d, r))  # r << min(d, k)
B = nn.Parameter(torch.zeros(r, k))
ΔW_lora = A @ B  # rank-r 근사로 full update를 대체

r=8~64 정도의 작은 rank로도 full fine-tuning의 95%+ 성능. 메모리와 compute를 크게 절약.

4단. Gradient Noise Scale — Optimal Batch Size

OpenAI가 제안한 개념. 대형 모델 학습에서 batch size를 얼마로 설정할지 결정하는 원칙이다.

왜 noise가 생기나

g_batch = mean([∇L(x_i) for x_i in batch])
# = g_true + noise   (전체 데이터 gradient + sampling noise)
# batch가 작을수록 noise가 크다

Gradient Noise Scale

S = gradient_variance / (gradient_magnitude ** 2)
# signal 대비 noise 비율

핵심 결과

상황의미결과
batch B << Sgradient가 noisy. step마다 새로운 방향 탐색step당 효율 좋음
batch B ≈ Soptimal: 추가 compute가 새 정보를 줌가장 효율적
batch B >> Sgradient가 거의 같음. compute 낭비효율 하락
# 실제 활용 흐름 (GPT 계열)
S = measure_noise_scale(model, dataloader)
optimal_batch = S   # noise scale이 곧 optimal batch size
# 학습 진행에 따라 S가 변하므로 batch size도 조정 가능

5단. 세 가지 연결해서 보면

딥러닝이 수천억 파라미터 규모에서도 작동하는 이유:

요소의미실용적 활용
Backprop 효율gradient 계산 ≈ 2 × forward. n에 무관수천억 파라미터 학습 가능
Low-rank gradient실제 학습 차원 << 파라미터 수LoRA, PEFT의 이론적 근거
Gradient noise scaleoptimal batch size 존재compute 낭비 없는 학습

이 세 가지가 합쳐져 Scaling Law("파라미터↑, 데이터↑, compute↑ → 성능↑")가 성립하는 기반이 만들어진다.

예상 질문 5개와 답변

다음에 스스로 해볼 실습 2가지

관련 문서