microcrad: スカラー自動微分エンジンとニューラルネットワークの実装

microcrad は、C 言語向けの小さなスカラー値を扱う自動微分エンジンであり、その上に構築された軽量なニューラルネットワークの実装を備えています。これは Andrej Karpathy 氏の「micrograd」の C 言語への再実装です。Python のオリジナルと同様に、テンソルではなくスカラーに基づいて動作します。

計算に携わるすべての数はグラフ上のノードとして扱われ、各操作が生成方法を記録（計算グラフ）します。その後方伝播パスでは、単一のパスで逆方向にグラフを走行し、出力に関する各入力への微分係数を計算します。ベクトル化や GPU は一切使用せず、スカラー単位で連鎖律を適用するだけです。

このエンジンの上には多層感知器（MLP）が構築されており、C 言語だけでネットワークの構築・順伝播・後方伝播・勾配降下法を実現できます。本リポジトリは主に教育目的の実装であり、生産環境向けの最適化や大規模データセットへの対応を最優先していません。

基本的な設計概念

全体は以下の二つの概念を中心に構築されています：

• Value：計算グラフ上の単一のノードを表します。
• 参照カウント（Reference counting）：

  Value

  のグラフから完全に外れたタイミングを知るための仕組みです。リソース解放を管理するために利用されます。

Value の仕組みについて

基本型は

Value

Value

n_prevs == 0

Value

prev

Value の構造体定義

typedef struct Value {
    uint32_t ref_count;   /* この Value を参照するポインターの数 */
    uint32_t n_prevs;     /* この Value を生成したオペランドの数 */
    double data;          /* このノードが保持するスカラー値 */
    double extra_data;    /* 演算のパラメータ（例：pow の指数）*/
    struct Value **prev;  /* オペランド（グラフ上の前のノード群）*/
    int32_t op_code;      /* この Value を生成した演算の種類 */
    uint32_t magic;       /* デバッグ用キャニワリ（無効ポインタ検出のため）*/
    double grad;          /* dLoss/dThisValue（backward で埋め込む値）*/
} Value;

これにより、計算グラフ（有向非巡回グラフ：DAG）が形成されます。何かを計算しその勾配を求める最小限の microcrad プログラムは以下の通りです：

Value *a = value_create_leaf(2.0);
Value *b = value_create_leaf(3.0);
Value *c = value_mul(a, b);   /* c = a * b = 6 */

value_backward(c);            /* 成功なら 0 を返すか、全ての grad フィールドを埋める */

printf("c    = %f\n", c->data);   /* 6.000000 */
printf("dc/da= %f\n", a->grad);   /* 3.000000  (== b) */
printf("dc/db= %f\n", b->grad);   /* 2.000000  (== a) */

value_release(c);             /* c を解放；a と b に対する保持も解放 */
value_release(a);             /* a を解放（もう一つの参照はあなたのものでした）*/
value_release(b);             /* b を解放                                     */

Value の作成方法

主要なコンストラクターは以下の通りです：

• Value *value_create(double data, int32_t n_prevs, Value **prev);

• Value *value_create_leaf(double data);

value_create_leaf

新規作成された

Value

演算子（Operations）

以下の関数は新しい

Value

data

prev

value_add(v1, v2)

v1 + v2

value_mul(v1, v2)

v1 * v2

value_pow(b, e)

b ** e

value_exp(v)

e ** v

value_log(v)

\ln(v)

value_relu(v)

\max(0, v)

※引数は非 NULL ポインターを期待します。堅牢性よりも学習パスの明確さを優先しています。

参照カウントに関する注意点： 演算関数はオペランドの参照カウントを増やし、結果ノードが必要とする間オペランドを維持します。しかし、呼び出し前にはもともと保持していた参照をあなたが依然として保有し、解放する責任があります（共有所有関係）。

Value *a = value_create_leaf(2.0);   /* a: ref_count 1 (あなたの所有) */
Value *b = value_create_leaf(3.0);   /* b: ref_count 1 (あなたの所有) */
Value *c = value_add(a, b);            /* a,b は現在 ref_count 2; c は ref_count 1 */

/* ... c を使用する間 ... */

value_release(c);   /* c を解放；a と b に対する保持も解放 */
value_release(a);   /* a を解放（もう一つの参照はあなたの所有でした）    */
value_release(b);   /* b を解放                                     */

※注記：引き算や除算は独立した演算ではありません。それぞれ符号反转された加算または逆数との乗算として実装されます。

後方伝播（Backpropagation）

int value_backward(Value *v);

value_backward

v

grad

1. グラフ全体（

   v

   を根として）に対して、**深さ優先順序（Topological Sort）**を実行します。共有ノードを二度訪問しないように注意しています。

2. v->grad = 1

   で種付けを行い、ソートされたリストを逆順に歩き回り、各ノードについて連鎖律に従って勾配をオペランドへ伝播させます。

成功時は 0 を、失敗時は -1 を返します。

重要な前提条件

• v

  は非 NULL で、有効な計算グラフのルートであることを指さしている必要があります。
• ループ内で学習を行う場合は、呼び出す前に蓄積させたくない勾配をゼロ化する必要があります。
• 勾配はオペランドに対して**累加（

  +=

  ）**されるため、複数の場所で使用された

  Value

  は各パスからの勾配を正しく受けます。

// 学習ループ内の処理例
for (size_t i = 0; i < parameters->size; i++)
    vector_get(parameters, i)->grad = 0.0;   /* 勾配をゼロにする */

value_backward(loss);                        /* 新しいものを蓄積する */

for (size_t i = 0; i < parameters->size; i++) {
    Value *p = vector_get(parameters, i);
    p->data -= learning_rate * p->grad;      /* 勾配降下法のステップ */
}

メモリ管理：参照カウント

C ランタイムにはガベージコレクターがないため、計算グラフの解放は共有ポインターの複雑な絡み合いです。参照カウントがこれを解決します。

• value_retain(Value *v)

  : リファレンスを取得（ref_count++）。新しい誰かが

  Value

  を保持していることを記録します。

• value_release(Value *v)

  : リファレンスを解放（ref_count--）。カウントがゼロに達した時、

  Value

  は解放され、まず自身のオペランドを解放して再帰的にグラフを下へと伝播させます。

ルール：

1. 全ての

   Value

   は参照カウント 1 で生まれます。
2. グラフのルート（損失や順伝播の出力）を解放すれば、参照カウントは下流へとカスケード状に伝わり、他の何もしない節点を正確に解放します。

value_release

value_release(maybe_null);   /* maybe_null が NULL なら何も起きない */

magic フィールド

各

Value

value_retain

value_release

Value *

この設計の利点と欠点

参照カウントは正しさと構文能力（composability）をもたらしますが、コストを伴います。

欠点

1. 手動のバランス：各参照を明示的に管理する必要があります。一つ忘れればメモリリークに陥り、一つ多すぎると不要な解放となります。
2. 共有所有関係：

   Value *c = value_add(a, b)

   の後、

   a

   と

   b

   は

   c

   によって保持され続けます。個別の Value のライフタイムを個別に議論せず、全体としてのグラフ Lifecycle を考える必要があります。

利点

1. 自動クリーンアップ：ルートだけを解放すれば、他に参照されていないサブグラフ全体が消滅します。
2. 共有が無料：重みや中間値は適切なタイミングで解放されます。

   value_backward

   が共有ノードを超えて適切に勾配を蓄積できるためです。

ニューラルネットワークの実装

自動微分エンジンの上に、順伝播（feed-forward）ネットワークに必要な三つの要素が提供されています。

Neuron *neuron_create(uint32_t nin);
Value  *neuron_forward(Neuron *n, Value **x);

Layer  *layer_create(uint32_t nin, uint32_t nout);
Value **layer_forward(Layer *l, Value **x);

MLP    *mlp_create(uint32_t nin, uint32_t *nouts, uint32_t n_layers);
Value **mlp_forward(MLP *m, Value **x);

• Neuron:

  nin

  個の重みの

  Value

  とバイアスを保持し、

  relu(w·x + b)

  を計算して一つの出力

  Value

  を返します。
• Layer: 同じ入力を受ける

  nout

  個のニューロンからなるアレイで、

  nout

  個の出力

  Value

  のアレイを返します。
• MLP: 複数の層を連結し、各層の出力を次の層の入力として供給します。

※すべてのニューロン（出力層を含む）が ReLU を適用することに注意してください。これはエンジンを最小限に保つための意図的な簡略化です（結果：出力は常に非負）。

トレーニングするには、ネットワーク内のすべての重みとバイアスの平たいリストが必要です：

Vector *neuron_parameters(Neuron *n);
Vector *layer_parameters(Layer *l);
Vector *mlp_parameters(MLP *m);  // 全てのトレーニング可能なスカラーを含む Vector

統合方法（トレーニングステップ）

完全なトレーニングステップの形状は以下の通りです：

uint32_t nouts[] = {8, 1};
MLP *model = mlp_create(2, nouts, 2);     /* 2 -> 8 -> 1 のネットワーク       */
Vector *params = mlp_parameters(model);   /* すべての重みの平たいリスト         */

/* forward: グラフを構築する */
Value *inputs[] = { value_create_leaf(x1), value_create_leaf(x2) };
Value **out = mlp_forward(model, inputs);

/* ... out[...] から損失の Value を構築 ... */

/* backward + update */
for (size_t i = 0; i < params->size; i++) vector_get(params, i)->grad = 0.0;
value_backward(loss);
for (size_t i = 0; i < params->size; i++) {
    Value *p = vector_get(params, i);
    p->data -= learning_rate * p->grad;
}

/* cleanup */
value_release(loss);
/* ... out, inputs を解放 ... */
vector_free(params);
mlp_free(model);

examples/

toy_regression

mnist

examples/toy_regression/train_on_toy_regression.c

サポートするデータ構造

通常は直接操作しませんが、以下の二つの自己完結型のデータ構造を利用しています：

• Vector (

  vector.h

  ):

  Value

  ポインターからなる動的アレイです。

  vector_append

  は格納する

  Value

  を保持し、

  vector_free

  は解放します。
• SimpleSet (

  simpleset.h

  ): メモリアドレス（ポインタ同値）をキーとする最小限のセットです。挿入とメンバーシップテストしかサポートしておらず、

  value_backward

  の幅優先順序で共有ノードを二度訪問しないために必要な機能です。

ビルドとテスト

ビルドには C コンパイラ、C 標準ライブラリ、および

libm

テストスイートの実行

make test_value
make test_mlp

例プログラムの実行

# タINY な合成回帰分析（外部データ不要、推奨）
make example_toy_regression  

# MNIST データセットを利用した概念的なデモ
make example_mnist 

※

example_mnist

examples/mnist/download_data.sh

クリーンアップ

make clean   /* ビルドディレクトリを削除 */

次のステップ

• 最小限の完全なトレーニングプログラム：

  examples/toy_regression/train_on_toy_regression.c

• 構造的デモンストレーション（実際のデータセット接続）：

  examples/mnist/train_on_mnist.c

  • 注意：これは最適化や数値的に慎重な意図を持っていません。スカラーベースであり、ReLU 専用です。
• 関数の呼び出し方法及び保証：

  test/

  ディレクトリ内のテストコードを参照してください。
• ソースコード：

  src/value.c

  は短い注釈付きであり、順伝播演算と逆伝播ルールの各ケースが段階的に記述されています。

クレジット

microcrad は Andrej Karpathy 氏の

micrograd

Value