代数的エフェクトで確率的プログラミングを実装する

代数的エフェクトで 確率的プログラミングを 実装する 2024/11/9 lotz

速習モナド C を圏として、C 上のモナドは自己関手 T : C → C と自然変換 η : 1C → T と自然変換 μ : T2 → T の三つ組 (T, η, μ) であり以下の等式を満たすもの μ ○ Tμ = μ ○ μT μ ○ Tη = μ ○ ηT monad in nLab

• https://ncatlab.org/nlab/show/monad

確率モナド • Meas を対象に可測空間、射に可測関数を持つ圏とする • Meas の対象Xに対し GX を X 上の全ての確率測度の集合とすると、 これは再び可測空間になる • ηX : X → GX を X 上のディラック測度を与える関数とする • μX : GGX → GX を”確率分布の期待値”をとる操作と考える • (G, η, μ) はモナドとなり Giry Monad と呼ばれる Giry monad in nLab

• https://ncatlab.org/nlab/show/Giry monad

確率モナドの実装例 確率モナドをHaskellで実装する例 https://twitter.com/lotz84_/status/1852633696089899016

• https://twitter.com/lotz84_/status/1852633696089899016

確率モナドの応用 確率モナドを使えば確率変数の合成が容易になり 確率的プログラミングの記述が洗練される

確率的プログラミング • シミュレーションだけでなくパラメータの推定にも用いられる • プログラムの実行順序が逆転する van de Meent, Jan-Willem, et al. "An introduction to probabilistic programming." arXiv preprint arXiv:1809.10756 (2018). パラメータ パラメータ プログラム プログラム 出力 出力

• https://arxiv.org/abs/1809.10756

代数的エフェクト • 計算エフェクトを代数的に表現できる • 計算エフェクトの実行（実装）はハンドラに分離される • Haskell での実装として Freer と Open Union を使った Extensible Effects がある ff ff Algebraic E ectsとExtensible E ectsの違いってなんや? 関係あんの?

• https://nymphium.github.io/2020/03/15/ae-ee.html

ProbFX • 代数的エフェクトを使った確率的プログラミングの実装 • 同じコードでシミュレーションも推論もできるマルチモーダルな性質 を備えている • ProbFX2もあるが今回は触れない Nguyen, Minh, et al. "Modular probabilistic models via algebraic effects." Proceedings of the ACM on Programming Languages 6.ICFP (2022): 381-410.

• https://arxiv.org/abs/2203.04608

ProbFXの再実装 • ProbFXではエフェクトシステムとOpen Unionが自前で実装されている • 既存ライブラリを使って再実装を行い本質的な部分を抽出したい • 使用するライブラリは以下 • freer-simple • extensible https://github.com/min-nguyen/prob-fx

• https://hackage.haskell.org/package/freer-simple
• https://hackage.haskell.org/package/extensible
• https://github.com/min-nguyen/prob-fx

ProbFXによるモデルの記述 • coinFlip は表が出る確率 p のコインの裏表を表す確率モデル • 確率 p は [0, 1] の一様分布に従う

サンプリングの実行 • Model をどのように実行するかはハンドラが決める • runSimulate というハンドラを使用し確率モデルからサンプリングする

runSimulate • Model を Sampler に変換するためのハンドラ • runSimulate もまたいくつかのハンドラの合成として実装される

handleCore • Env はモデルの外からパラメータを与える拡張可能レコード • handleCore は Env を利用し Model の持つ二つのエフェクト （ObsReader, Dist ）を実行するためのハンドラ

handleRead • ObsReader はパラメータをリストから1つずつ取得するエフェクト • handleRead は Env から1ずつパラメータを取り出して Ask を実行する

handleDist • handleDist は Model における確率分布のエフェクト Dist を実行する • Env によって観測値が与えられている場合は Observe に、与えられ ていない場合は Sample に仕分けする

traceSamples • traceSamples は確率モデルの実行時に確率分布から値がサンプリン グされた場合、その情報を記録するためのハンドラ • Sample エフェクトの後に処理を差し込む動きをするため、エフェク トは消費しない

handleObs • Observe エフェクトを実行する • シミュレーションにおいては観測値をそのまま返すだけ

handleSamp • Sample エフェクトだけとなった Eff を Sampler に変換するハンドラ • 実態は PrimDist で指定された確率分布からサンプリングを行う実装

runSimulate（再掲） • Model を Sampler に変換するためのハンドラ • runSimulate もまたいくつかのハンドラの合成として実装される

推論の実行 • 同じ確率モデル coinFlip を使ってシミュレーションだけでなく推論も 実行できる • mh がMCMCによる推論を実行するためのハンドラになっている

MISC • 再実装した完全なコードは こちらのGist にある • Haskell による確率的プログラミングの実装にはモナドトランス フォーマーを利用した monad-bayes もある

• https://gist.github.com/lotz84/1c06c5c6bbac23a595621f46711e05dc
• https://github.com/tweag/monad-bayes

まとめ • 確率モナドは確率的プログラミングの実装に役立つ • 確率的プログラミングの実装に代数的エフェクトが使える • ハンドルによってシミュレーションと推論を切り替えられる マルチモーダルな性質を備えた確率モデルの実装が可能