STEP 3・Autograd(自動微分)

再帰・トポロジカルソート ― 集計の依存順序

記事で詰まったところ

「トポロジカルソート」「再帰で計算グラフを並べる」が、プログラムの話に聞こえて入ってこない。

機械学習ではこう言う

計算グラフを「子(入力)が先・親(出力)が後」に並べ替える手続き。順方向で値を計算し、逆順で勾配を流す。

集計の依存順序(仕訳→F/S)

会計の集計順序そのもの。仕訳 → 総勘定元帳 → 試算表 → 精算表 → 財務諸表。下流(F/S)を出すには、上流(仕訳)が先に確定していなければならない。

この「上流が先」という並びを機械的に作るのがトポロジカルソート。順番を守らないと、まだ確定していない数字を使ってしまう。

原因を遡るときは、この順序を逆にたどる。F/S の異常 → 試算表 → 元帳 → 仕訳、と下流から上流へ。逆伝播はこの逆順走査にあたる。

言葉の対応表

microGPT(機械学習)
会計・簿記の言葉
トポロジカルソート
仕訳→元帳→試算表→F/S の集計順
順方向で値を計算
上流から積み上げて F/S を作る
逆順で勾配を流す
F/S の異常から仕訳へ原因を遡る

触って確かめる

仕訳取引を借方・貸方に記録
総勘定元帳科目ごとに集計
試算表残高を一覧化
精算表決算整理を反映
財務諸表(F/S)B/S・P/L を確定

順方向は仕訳から F/S へ積み上げる集計(上流が先に確定していないと下流を出せない)。 逆方向は F/S の異常から仕訳へ原因を遡る = バックプロパゲーション。 この「上流が先」という並びを機械的に作るのがトポロジカルソートです。

⚠️ 計算グラフは木でなく DAG(合流あり)。ここは一直線の集計フローに単純化した例示。

実際のコード(microgpt.py L60-70)

この簿記アナロジーが、Karpathy のオリジナル200行のどの行に当たるか。

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)
self.grad = 1
for v in reversed(topo):           # 逆順に勾配を流す

子(上流)を先に append して依存順に並べ(トポロジカルソート)、reversed で逆順に勾配を流す。仕訳→F/S の集計順とその逆走査。

出典: karpathy / microgpt.py (本体は原文ママ、コメントのみ日本語に補足)