「トポロジカルソート」「再帰で計算グラフを並べる」が、プログラムの話に聞こえて入ってこない。
計算グラフを「子(入力)が先・親(出力)が後」に並べ替える手続き。順方向で値を計算し、逆順で勾配を流す。
会計の集計順序そのもの。仕訳 → 総勘定元帳 → 試算表 → 精算表 → 財務諸表。下流(F/S)を出すには、上流(仕訳)が先に確定していなければならない。
この「上流が先」という並びを機械的に作るのがトポロジカルソート。順番を守らないと、まだ確定していない数字を使ってしまう。
原因を遡るときは、この順序を逆にたどる。F/S の異常 → 試算表 → 元帳 → 仕訳、と下流から上流へ。逆伝播はこの逆順走査にあたる。
順方向は仕訳から F/S へ積み上げる集計(上流が先に確定していないと下流を出せない)。 逆方向は F/S の異常から仕訳へ原因を遡る = バックプロパゲーション。 この「上流が先」という並びを機械的に作るのがトポロジカルソートです。
⚠️ 計算グラフは木でなく DAG(合流あり)。ここは一直線の集計フローに単純化した例示。
この簿記アナロジーが、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 (本体は原文ママ、コメントのみ日本語に補足)