HN 日本語サマリー

← 一覧へ戻る
プログラミング

NoiseLang: N = 5 がディラックのデルタ関数となる場所

NoiseLang: Where N = 5 is a Dirac delta (manualmeida.dev)

101 pointsby manucorporat48 コメント

要約

NoiseLangは、すべての値が確率分布であるという単一のアイデアに基づいた新しいプログラミング言語です。定数も単一の値に集中した分布(ディラックのデルタ関数)として扱われ、これにより定数と確率変数が同じオブジェクトとして扱われ、演算子も分布から分布へのマッピングとなります。この言語は、複雑な確率計算を簡潔に記述し、モンテカルロシミュレーションを効率的に実行することを目指しています。

全文翻訳

NoiseLang: N=5 がディラックのデルタ関数となる言語

大学の通信工学のコースで信号とノイズについて学んだ際、期待値や分散、確率変数が特定の領域に収まる確率などを手書きで計算することに多くの時間を費やしました。それをコンピュータで実行しようとすると、非常に多くの定型的なコードが必要で、いつも面倒でした。

その願いが NoiseLang として形になりました。約9年前に着手しましたが、完成には至りませんでした。最近になって、AIツールの助けを借りて、以前一人では実現できなかった、はるかに野心的なものとして復活させました。

すべては分布である

言語全体は一つのアイデアに基づいています。それは、「すべての値は確率分布である」という考え方です。通常の数値はディラックのデルタ関数(単一の値にすべての重みを持つ分布)として扱われます。定数と確率変数が同じ種類のオブジェクトであるため、言語内のすべての演算子は分布を分布にマッピングします。

純粋主義者は、ディラックのデルタ関数は連続密度に属し、6面ダイスには関係ないと言うでしょう。彼らは正しいです。私が意味するのは、一点にすべての重みを持つディラック測度であり、ダイスの上でもうまく機能します。NoiseLang は密度を評価するのではなく、サンプルを生成します。定数はグラフ上で通常の整数に戻るため、5 のコストはゼロです。

名前は常に一つの固定されたノードを参照します。数学のページ全体で X が同じ X であるのと同じようにです。したがって、X + X は 2X となり、X - X は正確に 0 になります。変数の独立性を得たい場合は、個別に描画を記述します。つまり、~ を複数回使用するか、~[N] を使用して N 個の独立した変数をベクトルに描画します。

X ~ unif_int(1, 6)
Y ~ unif_int(1, 6)
X + Y                 # 2つの独立したダイス、実際の 2d6 分布

結果を要求するまで何も実行されません。例えば P(X + Y < 10) を要求すると、ランタイムは数百万回のシミュレーションを実行し(利用可能な場合は全コアを使用)、標準誤差を付加した推定値を返します。

Bday = unif_int(1, 365)
days ~[23] Bday          # 部屋にいる 23 人
P(has_duplicates(days))  # 誕生日問題、約 0.507

これは説明するよりも見る方がはるかに簡単なので、いくつかのクールなデモを作成しました!

すべての値は分布である
A = 5D1 ~ unif_int(1, 6)D2 ~ unif_int(1, 6)S  = A + D1 + D2E(S)

図 1. 4つのステップを経る同じヒストグラム:定数は単一のスパイク、チルダはそれをダイスに広げ、2つのダイスを加えるとベルカーブに近づき、クエリは平均値を読み取ります。

数値は分布である

A = 5 は通常の定数のように見えますが、NoiseLang はそれを、すべての描画が 5 に着地する確率分布として認識します。統計学者はこれをディラックのデルタ関数、つまり単一の無限に細いスパイクと呼びます。

チルダはそれを広げる

D1 ~ unif_int(1, 6) は、公平なダイス、つまり 6 つの面がすべて等しく可能性のある離散一様分布を束縛します。スパイクは 6 つの平坦なバーに広がります。したがって、D1 は不確実になりますが、他の変数と同じように記述できます。

それらを結合するとベルが現れる

定数と 2 つの独立したダイスを S = A + D1 + D2 で加算します。平坦な形状は畳み込まれて三角形になり、12 でピークを迎え、すでにベルカーブに近づいています。さらにいくつか結合すると、真のガウス分布に鋭くなります。これは中心極限定理が無料で現れているのです!

クエリは数百万回の描画を収束させる

要求するまで何も実行されません。期待値 E(S) はモンテカルロパスを発火させ、数百万回のロールを平均して 1 つの数値にし、大数の法則により実行平均は 12 に収束します。数行の数式を記述しただけで、専門家レベルのカーネルがバックグラウンドで実行されました。

9年間放置された理由

この言語のパーサーとツリーウォーカーインタープリターは週末で作成できるため、設計自体は難しい部分ではありませんでした。問題はそれ以外のすべて、つまり単純なインタープリターではなく効率的なモンテカルロランタイムの作成、条件付きベイズ推論などでした。

現在のバージョンは、GPUバックエンド(wgpu を介した WGSL)、WASM バックエンド、および慎重に作成された多数の数値コードを備えたコンパイラです。そのため、かわいい週末プロジェクトとしては、常に手の届かないところにありました。

エージェントによる野心的なバージョンの構築

日々の仕事やサイドプロジェクトで、今日の AI エージェントができることの限界を実験しています。例えば、15年前に Objective-C で作成したゲームを、現代的なゲームエンジンに移植しています(比較的成功しています)。

NoiseLang に関しては、AI は JIT 部分、ランタイム部分、数値部分の構築には優れていますが、言語設計のアイデアを出すことに関しては劣っています。多くの場合、異なる目的のために既存の言語機能を上書きしたり、非直交な機能のために異なる構文を考案したりします。

1つのIR、3つのバックエンド

最初の計画は、グラフを WASM にコンパイルし、WASM ランタイムに JIT させることでした。なぜなら、そのランタイムは私が書くコンパイラよりも確実に最適化してくれるはずだったからです。それを探求する中で、JIT オプティマイザーに直接アクセスできることに気づき、WASM ステップをスキップできることがわかりました。そのため、最初のネイティブバックエンドは Cranelift JIT でした。これはこのようなプロジェクトにとって画期的なライブラリであり、NoiseLang はネイティブ速度で実行され、コンパイラをほとんど書かずに済みました。その JIT は現在削除されています。読み進めてください。なぜなら、それが削除された理由が、プロジェクト全体で私のお気に入りの部分だからです。

~ と分布コンストラクタは、RvGraph と呼ばれる追記専用 DAG を構築します。このグラフは唯一の真実の情報源であり、その後 3 つの異なるコードパスに変換されます。

  • どこでも動作し、正しさのオラクルとして機能する列指向バッチインタープリター。
  • 式全体を 1 つの GPU コンピュートシェーダーに融合する WGSL エミッター。
  • ブラウザの CPU 用に同じ融合カーネルを実行する WASM エミッター。
fallback

fallback

X ~ unif(1, 6)

RvGraph

batch interpreter

WGSL emitter (GPU)

WASM emitter

1 つの共有モジュールがグラフの意味を定義しているため、2 つのコードジェネレータはスリムに保たれ、乖離することはありません。バックエンドが正常にコンパイルできないものはすべてインタープリターにフォールバックし、結果はバックエンドやコア数に関係なく同一になります。すべてのテストは 3 つのコードパスすべてで実行され、ビット単位で同一であることが比較されます。

エンジンはクエリごとにパスを選択します。これは SQL クエリプランナーが実行プランを選択するのと同じ方法です。コストモデルは、小さなクエリをベクトル化インタープリターに保持し、中規模のクエリをワークスティーリングリデューサーを使用して全コアに分散させ、大規模なクエリを 1 つの融合コンピュートシェーダーとして GPU に送信します。P(...) と入力すると、プランナーが残りを処理します。

モンテカルロループを安価にする

すべてのパフォーマンス作業は 1 つのループに関するものです。数百万のサンプルを描画し、各サンプルで式を評価し、結果を削減します。いくつかのテクニックがその大部分を担っており、結果を決定論的に保ちます(それが難しい部分でした)。

カーネル融合により、すべての途中値がレジスタに保持されるため、算術演算が多い式はレジスタ内に留まります。PRNG はカーネルにコンパイルされ、ln、sin、cos はインライン多項式近似となり、カーネルを 2 倍高速化します。

RNG にはかつてお気に入りのトリックがありました。元のジェネレータ(xoshiro256++)はシリアル依存チェーンであるため、それに逆らうのではなく、カーネルは 4 つの独立したストリームを同時に実行し、アウトオブオーダーコアにそれらをオーバーラップさせました。そのトリックは廃止されました。その理由は、トリックよりも優れています。RNG はカウンターベース(squares64)になりました。これは、各描画が(シード、レーン、ソース)の純粋関数であるミドルスクエアハッシュです。ループを通してスレッド化する状態がないため、サンプル空間のどのスライスでも任意のコアまたは GPU スレッドで実行でき、ビット単位で同一の結果が得られます。そして、それはランダムな選択ではありません(言葉遊びです)。エンジンが消費する正確なビットストリームは、PractRand の 1 TB を異常ゼロで通過しました。

私の 14 コア M4 Pro では、1 行の P(...) は毎秒約 58 億サンプルを維持し、1 コアから全コアへのスケールは約 9.6 倍です。コアあたりでは、JIT カーネルは LLVM でコンパイルされた手書きの Rust より約 1.15 倍の範囲で実行され、CPU コード生成が天井に達したことを示していました。同じ融合ループを WASM としてエミットすると、V8 内でネイティブ速度の約半分から 3/4 で実行されます。

モンテカルロ法による π の推定
X ~ rand::unif(-1, 1)
Y ~ rand::unif(-1, 1)
C = X^2 + Y^2 < 1
4 * P(C)
darts 0 inside 0 π ≈ —

図 4. モンテカルロ π。円は正方形の π/4 をカバーするため、水色の部分の 4 倍が π に収束します。

2 つのランダムな描画

これは以前と同じ ~ を 2 回使用したものです。X ~ unif(-1, 1) と Y ~ unif(-1, 1) はそれぞれ
[-1, 1] の間の数値をランダムに抽出し、それらを合わせて正方形内のランダムな点をピックアップします。

1 つの Yes/No 質問をする

C = X² + Y² < 1 は、点が単位円内にある場合にのみ真となります。NoiseLang では、この比較自体が確率変数であり、各描画で真または偽になるベルヌーイ分布です。

ダーツを投げる

各ダーツは (X, Y) の 1 回の描画です。円内に着地した場合は水色、そうでない場合は灰色になります。一様分布の描画はどの点も偏らないため、均等に散らばります。

4 倍の割合が π

円の面積は正方形の π/4 をカバーするため、水色の割合は約 π/4 に収束し、4 * P(C) は π の推定値となります。ダーツを多く投げれば投げるほど、推定値はシャープになります。

GPU が JIT を食った

この記事を公開してから数週間後、JIT を削除しました。モンテカルロクエリはすでにコンピュートシェーダーのような形状をしていることに気づいたときに、アイデアが閃きました。数百万の独立したレーンで評価される 1 つの純粋なカーネル、そしてそれらを折りたたむためのリデュースです。これはまさに GPU コンピュートモデルなので、RvGraph に WGSL のローリングが追加され、wgpu のおかげで、同じエミッターがネイティブの Metal、Vulkan、DirectX 12、およびブラウザの WebGPU に到達できるようになりました。メンテナンスする GPU バックエンドは 1 つだけで、プラットフォームごとのバックエンドは不要になりました。

次に、M4 Pro で完全な例コーパスを測定しました。

backendcorpus totalspeedup
interpreter3854 ms1.00×
Cranelift JIT3274 ms1.18×
GPU923 ms4.17×
JIT + GPU843 ms4.57×

GPU が存在すると、JIT が追加するすべては 80 ms であり、それはネイティブでしか機能しませんでした。そのため、1,834 行と 4 つの依存関係が削除され、出荷された CLI はインタープリターからデフォルトで GPU にジャンプしました。バックエンドを削除したのは、これまでで最も速いリリースでした!

重い例は楽しい部分です。ランダムな回転行列を描画する量子化例は、1474 ms から 55 ms (26 倍) になりました。100 人の囚人のシミュレーションには、まず実際のコンパイラ作業が必要でした。エミッターがグラフを見る頃には、for ループは約 15,000 のデータ依存読み取りに展開されており、Metal シェーダーコンパイラはそれを処理するのに 2.2 秒かかります。修正したのは、ループを評価時に単一のノードとしてキャプチャし、それを実際の WGSL ループとしてエミットし直すことでした。これにより、シミュレーションは 59 ms から 2.8 ms に減少しました。

NoiseLang の位置づけ

NoiseLang はおもちゃの言語であり、真面目な用途にはおそらく使用すべきではありません。しかし、大学時代にこの言語が存在したらよかったと思います。

言語オタクにとっては、フォワードモンテカルロと拒否ベースの条件付けを備えた、静的な確率変数代数上の小さな式ベースの言語です。

NumPy や Stan とどう違うのか疑問に思うかもしれません。NumPy ではシミュレーションを自分で書く必要があり、Stan ではモデルを宣言してサンプラーを待つ必要があります。NoiseLang は、確率を数式として書きながら、モンテカルロシミュレーションをバックグラウンドで実行して答えを得ることができます。

NoiseNumPyStanPyMC
What it isRV algebra + Monte Carloarray numericsdeclarative Bayesian modelingBayesian modeling in Python
Core abstractionevery value is a distributionn-d arraysdata / parameters / model blockswith Model() context
Getting an answerP / E / Var / Q force samplingyou write the loopcompile → NUTS → summarizepm.sample() → arviz
Inferenceforward MC + rejection conditioningnone (you build it)HMC / NUTS at scaleHMC / NUTS, VI, SMC
Setup to first answerzero — type in a browserimport numpyinstall toolchain, compileinstall stack, build a context
Visualizationbuilt into the languagematplotlib (separate)bayesplot (external)arviz (separate)
Runs in the browseryes — WASM, no installnonono

表 1. NoiseLang の位置づけ。Stan と PyMC は、事後分布を大量のデータに適合させる点では NoiseLang を凌駕し、NumPy は生の配列処理では凌駕しますが、NoiseLang は確率的な質問から可視化された回答を得るまでの速度では、それらのいずれよりも優れています。

Stan と PyMC は、それらが構築された目的(HMC/NUTS サンプラーを使用した大量の連続データへの事後分布の適合)においては NoiseLang を凌駕し、NumPy は生の配列処理では凌駕します。NoiseLang での条件付けは拒否ベースであるため、少数の離散観測にはうまく機能しますが、10,000 件の連続測定には役に立たなくなり、状態付きシミュレーション(マルコフ連鎖)はまだありません。NoiseLang が勝つのは、確率的な質問があり、あまり手間をかけずに答えを知りたい場合です。

したがって、問題のホワイトボード段階で、書いたばかりの数式を実行したい場合に NoiseLang を使用し、真の事後分布が必要な場合は Stan や PyMC に、本番環境に移行する必要がある場合は NumPy や JAX に移行してください。

信号とノイズに戻る

大学時代に戻ると、「Señales Aleatorias Y Ruido」という科目がありました。これは「ランダム信号とノイズ」のスペイン語訳です。

[画像: Señales Aleatorias y Ruido の教科書の表紙]

栄光に満ちた教科書。

この科目は、私自身を含む多くの学生の悪夢でした。実際、私は一度落第しました。正直に言うと、1 年生のときは十分な努力をしませんでしたが、2 年生で同じ科目を再度受講したときに状況は変わりました。教授は素晴らしく、科目を面白くしてくれました。私を驚かせたのは、AM がノイズチャネルで生き残れないのに、FM が生き残れる理由をどのようにモデル化できるかということでした。

そこで、この科目に敬意を表して、AM がノイズチャネルで生き残れないのに FM が生き残れる理由をモデル化する、ワン画面の NoiseLang プログラムを作成しました。

AM vs FM
msg = 0.3 * signal::sine(3);
am_modulate(m)        = 1 + m;
fm_modulate(m, swing) = exp(i * swing * m);
static ~ signal::noise_white_complex(0.4);
rx_am = am_modulate(msg) + static;
rx_fm = fm_modulate(msg, 3) + static;

am_demodulate(c)        = abs(c) - 1;
fm_demodulate(c, swing) = arg(c) / swing;

rec_am = am_demodulate(rx_am);
rec_fm = fm_demodulate(rx_fm, 3);

Print("AM error", E(mse(rec_am, msg)));
Print("FM error", E(mse(rec_fm, msg)));
scroll through the steps →

図 3. AM vs FM のエンドツーエンド。キャリアはフェイザーであり、AM はメッセージをその長さに書き込み、FM は角度に書き込むため、同じ静電気が AM が読み取るものを破損させますが、FM が読み取るものにはほとんど触れません。

メッセージ

NoiseLang では、値は信号全体を運ぶことができます。ここでは、穏やかなトーン、ゆっくりとした 3 サイクルのサイン波です。これは、ノイズチャネルを通過してそのまま戻ってくることを期待するものです。

AM はメッセージを長さに置く

キャリアは複素数、つまり回転する矢印です。AM の変調器は、メッセージを矢印の長さに配置します。そのため、先端は内側と外側にスライドし、メッセージの上昇と下降に合わせて単位円を横切ります。

FM はそれを角度に置く

FM は同じメッセージを角度に配置します。そのため、先端は単位円に沿って移動しますが、長さは固定されたままです。情報は同一ですが、回転でエンコードされています。

同じ静電気を追加する

今、同じホワイトノイズが両方の先端に当たります。それは AM を読み取る半径に沿って正確に広げますが、FM を円周上でわずかにずらすだけで、角度はほとんど変更しません。2 つの雲の形で見ることができます。

回復

復調:AM の場合は長さを、FM の場合は角度を読み取り、元のメッセージの上に重ねます。すでにわかりますが、AM のトレースはギザギザに戻るのに対し、FM のトレースは元の線に沿っています。

同じ嵐、非常に異なるダメージ

mse は波形全体のエラーを平均し、E は静電気の多くの描画にわたってそれを平均します。信号エネルギーとノイズエネルギーは同じですが、FM は約 5 倍クリーンになり、微小ノイズの極限では利点は swing² = 9 に近づきます。これは角度に費やされた帯域幅が成果を上げているのです。

1 つの注意点があります。Hacker News の roger_ さんが私よりも先に指摘してくれました。上記のプログラムは位相変調であり、周波数変調ではありません。したがって、技術的には PM です。送信している単一トーンの場合、PM と FM はスケールファクターとシフトを除いて同じですが、デモは私が示したいことをまだ示しています。しかし、実際の FM はメッセージを位相に入る前に微分するでしょう。メッセージが単一トーンでなくなるにつれて、FM はさらに差をつけるはずなので、そのバージョンを書きたいと思っています。

ブラウザで NoiseLang を実行する

上記のすべては、Rust エンジンが WebAssembly にコンパイルされたおかげで、@noiselang/core で実行できます。

npm install @noiselang/core
import { run } from "@noiselang/core";

const result = await run(`
  X ~ rand::unif(-1, 1);
  Y ~ rand::unif(-1, 1);
  4 * P(X^2 + Y^2 < 1)
`);

console.log(result.value); // "3.1415…" — 最後のステートメントの値
console.log(result.output); // Print(...) がエミットしたすべて

run は決して例外をスローせず、エラーは result.error にソーススパンと共に返されます。また、noiselang.com の変数インスペクタの背後にある API である runWithIntrospection もあります。

そして、ページに WebGPU が利用可能な場合、重いクエリはネイティブと同じ WGSL シェーダーを使用して GPU で実行されます。それ以外はすべて WASM カーネル上で実行されるため、WebGPU を持たないブラウザでも問題なく動作します。

NoiseLang は noiselang.com でブラウザでプレイ可能です。開いて、X ~ unif(-1, 1); Y ~ unif(-1, 1); 4 * P(X^2 + Y^2 < 1) と入力し、数百万回の描画がブラウザタブから π を推定するのを見てください。

付録: 先行研究

この記事を Hacker News に投稿したところ、スレッドは読書リストになり、これはおもちゃの言語をリリースしたときに起こりうる最良のことです。NoiseLang は、確率をファーストクラスの値として扱う最初の言語ではありません。それどころか、人々が私に指摘してくれたのは以下の通りです。

  • monad-bayes、同じ「すべては分布である」というアイデアがモナドから派生する Haskell ライブラリ。bradrn によるものです。Haskell がこれをこれほど直接的に表現できるとは知りませんでした。
  • webppl、Anglican、Stan、PyMC、実際の確率的プログラミング言語。chrisra によって提案されました。適合させる実際のモデルがある場合は、こちらに行ってください。こちらではありません。
  • diceplots.com by qdotme。分布を各ステップで正確に解析的に保ち、サンプリングしません。私のトレードオフとは逆の、楽しいものです。
  • Ruckdeschel と Kohl による “General Purpose Convolution Algorithm in S4-Classes by means of FFT”。data-ottawa によって送信されました。これは R パッケージ distr の背後にある論文であり、サンプリングするのではなく FFT を使用して畳み込みを計算することにより、分布に対して +、-、*、/ をオーバーロードします。まさに私が望んでいた演算子代数であり、反対方向から到達しました。
  • kccqzy の確率的プログラム推論に関する研究。モンテカルロ法なしでループを処理します。彼はまた、NoiseLang がループをどのように処理するかという、私が誰も尋ねないことを期待していた質問をしました。答えは、処理しないということです。

また、RNG トリックを私が自分のベンチマークをよりよく理解するまでプッシュしてくれた RossBencina と thrtythreeforty、そして私の FM デモが実際には位相変調を行っていることに気づいた roger_ にも感謝します。だからおもちゃを投稿するのです!