역전파를 처음부터: Chain Rule, 계산 그래프, 위상 정렬

microgpt.py의 backward() 함수는 15줄입니다. 하지만 이 15줄이 딥러닝 전체를 떠받치는 핵심 알고리즘 -- 역전파(backpropagation) -- 의 완전한 구현입니다.

이 글에서는 "왜 위상 정렬이 필요한가?"와 "chain rule이 뭔가?"를 고등학교 미분부터 시작해 microgpt.py의 backward()까지 연결합니다.

딥러닝의 핵심 질문

신경망을 학습시킨다는 것은 이런 뜻입니다:

1. 입력을 넣고 출력을 계산한다 (forward pass)
2. 출력이 정답과 얼마나 다른지 측정한다 (loss)
3. 각 파라미터가 loss에 얼마나 기여했는지 계산한다 (gradient)
4. loss를 줄이는 방향으로 파라미터를 조금씩 수정한다 (update)

3번이 어렵습니다. 파라미터가 4,192개(microgpt.py)든 70억 개(LLaMA)든, 각각에 대해 "이 파라미터를 살짝 바꾸면 loss가 얼마나 변하는가?"를 계산해야 합니다.

이것을 효율적으로 하는 알고리즘이 역전파입니다. 그리고 역전파의 수학적 기반이 chain rule입니다.

Chain Rule: 합성 함수의 미분

고등학교 미분부터 시작합니다.

함수 f(x) = x^2의 미분은 f'(x) = 2x입니다. x가 3이면, f'(3) = 6. "x를 3에서 아주 조금 늘리면, f는 약 6배만큼 증가한다"는 뜻입니다.

그런데 함수가 중첩되면 어떨까요?

y = f(g(x))에서, x를 바꿨을 때 y가 얼마나 변하는지 알고 싶습니다.

chain rule은 이렇게 말합니다:

dy/dx = (dy/dg) * (dg/dx)

풀어 쓰면: "y가 g에 대해 변하는 비율"과 "g가 x에 대해 변하는 비율"을 곱하면, "y가 x에 대해 변하는 비율"이 된다.

구체적인 예시:

g(x) = 3x + 1
f(g) = g^2

y = f(g(x)) = (3x + 1)^2

chain rule 적용:

dg/dx = 3          (g는 x에 대해 기울기 3으로 변한다)
df/dg = 2g         (f는 g에 대해 기울기 2g로 변한다)

dy/dx = df/dg * dg/dx = 2g * 3 = 2(3x+1) * 3 = 6(3x+1)

x = 1이면: g = 4, dy/dx = 6 * 4 = 24.

검증: y(1) = 16, y(1.001) = (4.003)^2 = 16.024009. 변화량 = 0.024009, 변화율 = 24.009. 맞습니다.

왜 Chain Rule이 딥러닝의 핵심인가

신경망은 합성 함수의 연쇄입니다. microgpt.py의 forward pass를 추적하면:

입력 토큰
  -> 임베딩 조회 (행렬 인덱싱)
    -> 위치 임베딩 덧셈
      -> RMSNorm
        -> Q, K, V 선형 변환
          -> Attention score 계산
            -> Softmax
              -> 가중 합
                -> 출력 선형 변환
                  -> 잔차 연결
                    -> MLP (선형 -> ReLU -> 선형)
                      -> lm_head 선형 변환
                        -> Softmax
                          -> -log(정답 확률)
                            = loss

loss는 파라미터들의 깊은 합성 함수입니다. 특정 파라미터 w에 대한 gradient(dloss/dw)를 구하려면, 이 긴 체인을 따라 chain rule을 반복 적용해야 합니다.

이것을 손으로 하면? 각 파라미터마다 체인 전체를 다시 추적해야 합니다. 4,192개 파라미터가 있으면 4,192번.

역전파의 핵심 통찰은: 한 번의 역방향 순회로 모든 파라미터의 gradient를 동시에 구할 수 있다는 것입니다.

계산 그래프: 합성 함수를 그림으로

chain rule을 자동으로 적용하려면, 먼저 계산 과정을 그래프로 기록해야 합니다.

microgpt.py의 Value 클래스가 정확히 이것을 합니다. 예를 들어:

a = Value(2.0)
b = Value(3.0)
c = a * b        # c = 6.0, children: (a, b), local_grads: (3.0, 2.0)
d = c + a        # d = 8.0, children: (c, a), local_grads: (1, 1)

이것은 아래와 같은 그래프가 됩니다:

a(2.0) ---*---> c(6.0) ---+---> d(8.0)
b(3.0) --/                |
a(2.0) -------------------/

각 노드는 두 가지를 기록합니다:

1. 자식(children): 어떤 값들로부터 계산되었는가
2. 국소 기울기(local_grads): 자식에 대한 편미분 값

곱셈 c = a * b의 경우:

dc/da = b = 3.0   (a를 살짝 바꾸면, c는 b배만큼 변한다)
dc/db = a = 2.0   (b를 살짝 바꾸면, c는 a배만큼 변한다)

덧셈 d = c + a의 경우:

dd/dc = 1   (c를 1 늘리면, d도 1 늘어난다)
dd/da = 1   (a를 1 늘리면, d도 1 늘어난다)

이 국소 기울기는 forward pass 시점에 즉시 계산됩니다. 별도의 미분 공식을 나중에 적용하는 것이 아니라, 연산을 수행하는 순간 기울기도 함께 저장합니다.

역전파: 그래프를 거꾸로 걷기

이제 d에 대한 a의 gradient(dd/da)를 구해봅시다.

chain rule에 따르면:

dd/da = dd/dc * dc/da + dd/da(직접)
      = 1 * 3 + 1
      = 4

왜 두 항이 있을까요? a는 d에 두 가지 경로로 영향을 미칩니다:

1. a -> c -> d (곱셈을 거쳐서): 기여도 = 1 * 3 = 3
2. a -> d (직접 덧셈): 기여도 = 1

두 경로의 기여도를 더합니다(gradient accumulation). 이것이 역전파에서 child.grad += local_grad * v.grad의 +=가 =이 아닌 이유입니다.

검증: d(2.0, 3.0) = 2*3 + 2 = 8. d(2.001, 3.0) = 2.001*3 + 2.001 = 8.004. 변화율 = 4. 맞습니다.

역전파 순서를 추적합니다:

Step 0: d.grad = 1              (출발점: dd/dd = 1)

Step 1: d의 자식들에게 전파
  c.grad += 1 * 1 = 1          (local_grad=1, d.grad=1)
  a.grad += 1 * 1 = 1          (local_grad=1, d.grad=1)

Step 2: c의 자식들에게 전파
  a.grad += 3 * 1 = 3          (local_grad=3, c.grad=1)
  b.grad += 2 * 1 = 2          (local_grad=2, c.grad=1)

결과: a.grad = 1 + 3 = 4, b.grad = 2

이것이 역전파의 전부입니다. 출력에서 시작해서, 각 노드의 gradient를 자식에게 국소 기울기를 곱해 전달합니다.

위상 정렬: 왜 필요한가

위의 예에서 역전파가 올바르게 작동하려면, 반드시 d를 c보다 먼저 처리해야 합니다. c.grad가 확정되기 전에 c의 자식(a, b)에게 전파하면, 잘못된 gradient를 전달하게 됩니다.

간단한 규칙: 어떤 노드의 gradient를 자식에게 전파하려면, 그 노드를 가리키는 모든 부모 노드가 이미 처리되어 있어야 합니다.

이것을 보장하는 것이 위상 정렬(topological sort)입니다.

위상 정렬이란: 방향 그래프(DAG)에서, 모든 간선 u -> v에 대해 u가 v보다 먼저 나오도록 노드들을 일렬로 정렬하는 것.

microgpt.py의 구현:

def backward(self):
    topo = []
    visited = set()
    def build_topo(v):
        if v not in visited:
            visited.add(v)
            for child in v._children:
                build_topo(child)   # 자식을 먼저 방문
            topo.append(v)          # 자식이 모두 처리된 후 자신을 추가
    build_topo(self)
    # topo = [a, b, c, d] (자식이 먼저, 부모가 나중)
    # reversed(topo) = [d, c, b, a] (부모가 먼저, 자식이 나중)

이것은 DFS(깊이 우선 탐색)의 후위 순회(post-order traversal)입니다. 알고리즘:

1. 현재 노드를 방문 표시
2. 모든 자식 노드를 재귀적으로 먼저 방문
3. 자식이 모두 끝나면 자신을 리스트에 추가

결과: topo = [a, b, c, d]. 자식이 앞, 부모가 뒤.

이것을 뒤집으면: [d, c, b, a]. 부모가 앞, 자식이 뒤. 이 순서대로 gradient를 전파하면, 모든 노드의 gradient가 확정된 후에야 자식에게 전달됩니다.

위상 정렬이 없으면 어떻게 되는가

위상 정렬 없이 임의의 순서로 역전파하면 어떻게 될까요?

잘못된 순서: [c, d, a, b]

Step 1: c를 먼저 처리
  c.grad = 0 (아직 d로부터 전파받지 못함!)
  a.grad += 3 * 0 = 0   (잘못된 값)
  b.grad += 2 * 0 = 0   (잘못된 값)

Step 2: d를 처리
  c.grad += 1 * 1 = 1   (이제서야 c.grad가 설정됨)
  a.grad += 1 * 1 = 1

결과: a.grad = 0 + 1 = 1 (정답은 4), b.grad = 0 (정답은 2)

c를 d보다 먼저 처리했기 때문에, c.grad가 0인 상태에서 c의 자식에게 gradient를 전파했습니다. d -> c 경로의 기여가 완전히 사라졌습니다.

위상 정렬은 이 문제를 원천적으로 방지합니다. "부모가 모두 처리된 후에만 자식을 처리한다"는 순서를 보장합니다.

더 복잡한 예: microgpt.py의 실제 계산

microgpt.py에서 이름 "ab"를 학습하는 경우를 단순화합니다:

tokens: [BOS, a, b, BOS]

Position 0: 입력=BOS, 정답=a
  emb = wte[26] + wpe[0]          # 임베딩 덧셈
  x = rmsnorm(emb)                 # 정규화
  q, k, v = linear(x, Wq/Wk/Wv)  # QKV 투영
  attn_out = attention(q, k, v)    # 어텐션 (자기 자신에게만)
  x = attn_out + emb               # 잔차 연결
  mlp_out = relu(linear(x, W1))    # MLP 전반부
  x = linear(mlp_out, W2) + x      # MLP 후반부 + 잔차
  logits = linear(x, lm_head)      # 출력 logits
  probs = softmax(logits)          # 확률 분포
  loss_0 = -log(probs[a])          # a의 확률에 대한 음의 로그

이 계산에서 생성되는 Value 객체는 약 7,000개입니다. 이 7,000개의 노드로 이루어진 계산 그래프에서, loss_0으로부터 모든 파라미터까지 chain rule을 적용해야 합니다.

wte[26][0] (BOS 토큰의 첫 번째 임베딩 차원)의 gradient를 구하려면:

dloss/d(wte[26][0])
  = dloss/dprobs * dprobs/dlogits * dlogits/dx * dx/d(attn_out+emb)
    * d(attn_out)/dq * dq/dx * dx/d(emb) * demb/d(wte[26][0])

이것을 손으로 계산하면 실수가 불가피합니다. 위상 정렬 + 역순 순회로 자동화하면, 7,000개의 노드를 한 번 순회하는 것으로 모든 파라미터의 gradient가 정확하게 계산됩니다.

시간 복잡도: O(노드 수). forward pass에서 N개의 노드가 생겼으면, backward도 O(N)입니다. 파라미터 수에 관계없이 한 번의 역방향 순회면 충분합니다.

PyTorch에서도 같은 일이 일어난다

microgpt.py의 Value 클래스는 PyTorch의 autograd와 동일한 원리입니다. 차이는 규모뿐입니다.

microgpt.py:

a = Value(2.0)
b = Value(3.0)
c = a * b
c.backward()  # a.grad = 3.0, b.grad = 2.0

PyTorch:

a = torch.tensor(2.0, requires_grad=True)
b = torch.tensor(3.0, requires_grad=True)
c = a * b
c.backward()   # a.grad = 3.0, b.grad = 2.0

결과는 동일합니다. PyTorch가 다른 점:

1. 텐서: 스칼라 대신 다차원 배열 단위로 연산. 한 번의 행렬 곱셈이 수천 개의 스칼라 곱셈을 대체.
2. GPU 커널: 텐서 연산을 GPU의 수천 코어에서 병렬 실행.
3. Fused kernels: 여러 연산을 하나의 커널로 합쳐 메모리 왕복을 줄임.
4. 그래프 최적화: 불필요한 중간 노드를 제거하거나, 계산 순서를 재배치.

하지만 핵심 알고리즘은 동일합니다: 계산 그래프 구축 -> 위상 정렬 -> 역순 chain rule 적용.

왜 역전파인가? (다른 방법은 없는가)

gradient를 구하는 다른 방법도 있습니다.

수치 미분(Numerical differentiation): 각 파라미터를 아주 조금 바꿔보고, loss의 변화를 관찰합니다.

dloss/dw ≈ (loss(w + epsilon) - loss(w)) / epsilon

문제: 파라미터가 N개이면, forward pass를 N+1번 수행해야 합니다. microgpt.py의 4,192개 파라미터면 4,193번의 forward pass. GPT-2의 124M 파라미터면 1.24억 번. 불가능합니다.

순방향 미분(Forward-mode AD): chain rule을 순방향으로 적용합니다. 하나의 입력 파라미터에 대한 모든 중간값의 gradient를 forward pass 한 번에 구합니다.

문제: 한 번에 하나의 파라미터에 대한 gradient만 구할 수 있습니다. N개 파라미터면 N번의 forward pass.

역전파(Reverse-mode AD): chain rule을 역방향으로 적용합니다. 하나의 출력(loss)에 대한 모든 파라미터의 gradient를 backward pass 한 번에 구합니다.

딥러닝에서는 출력이 하나(loss)이고 입력(파라미터)이 많으므로, 역방향이 압도적으로 효율적입니다. 한 번의 forward + 한 번의 backward = 모든 gradient.

이것이 역전파가 딥러닝의 핵심인 이유입니다. 파라미터가 10개든 100억 개든, forward 1번 + backward 1번이면 충분합니다.

microgpt.py의 backward() 다시 보기

이제 원래 코드로 돌아갑니다:

def backward(self):
    # 1. 위상 정렬: 자식 -> 부모 순서
    topo = []
    visited = set()
    def build_topo(v):
        if v not in visited:
            visited.add(v)
            for child in v._children:
                build_topo(child)
            topo.append(v)
    build_topo(self)

    # 2. 시드 설정: dloss/dloss = 1
    self.grad = 1

    # 3. 역순 순회: 부모 -> 자식 순서로 chain rule 적용
    for v in reversed(topo):
        for child, local_grad in zip(v._children, v._local_grads):
            child.grad += local_grad * v.grad

각 줄의 의미:

build_topo: DFS 후위 순회로 위상 정렬을 만듭니다. 자식이 먼저, 부모가 나중에 리스트에 추가됩니다.

self.grad = 1: 역전파의 출발점. "loss에 대한 loss의 기울기는 1"이라는 자명한 사실에서 시작합니다.

reversed(topo): 위상 정렬을 뒤집어 부모 -> 자식 순서로 순회합니다. 이것이 모든 노드의 gradient가 확정된 후에야 자식에게 전달되는 것을 보장합니다.

child.grad += local_grad * v.grad: chain rule의 핵심. local_grad는 "이 연산의 국소 기울기"(순방향에서 미리 계산), v.grad는 "loss에서 이 노드까지의 누적 기울기"(역방향에서 전파됨). 이 둘을 곱하면 "loss에서 자식까지의 기울기 기여분"이 됩니다. +=는 여러 경로의 기여를 누적합니다.

15줄. 이것이 딥러닝의 학습을 가능하게 하는 전부입니다.

핵심 정리

참고 자료

• Karpathy, "microgpt.py." GitHub Gist, 2025.
• Karpathy, "micrograd: A tiny scalar-valued autograd engine." GitHub, 2020.
• Rumelhart, Hinton, Williams, "Learning representations by back-propagating errors." Nature, 1986.
• Baydin et al., "Automatic Differentiation in Machine Learning: a Survey." JMLR, 2018.