計算可能性と確率的プログラミング
- haskellをやっていて、いまさらながらにラムダ関数とか、その背景としての計算可能性とかが気になって来ました。
- たとえば、一階述語論理（すべての...、ある...)の決定不能性、とか。
- ということで
- Computability, inference and modeling in probabilistic programming(これは長い)
- ON THE COMPUTABILITY OF CONDITIONAL PROBABILITY(これは短め。こちらをまずは読んだ。以下はそのサマリー)
- ただし、さらにこちらの方が簡潔
- 1. イントロ
- 確率を使って考えることが増えている。確率計算自体が計算機タスクとして整備されてきている。では確率(分布)の計算可能性ということが問題になるだろう
- 確率分布計算の分野での計算可能性を考えると、計算可能な同時分布と計算不可能な同時分布というものがあることがわかる。それを記載するのがこのペイパー。ただし、確率(分布)計算の一般化アルゴリズムが(まだ)ないので、厳密に計算可能性・不可能性を証するレベルではない
- 1.1 確率的プログラミングの現状。色々な言語があるが、記載可能な分布というものを持つ。これが計算可能性の存在と関係があるようだ。特に(無限パラメタ数である)ノンパラメトリックベイズで考えることが計算可能性と関連しそうだ
- 1.2 計算可能な分布。確率的な考え方で言うところのチューリングマシン(確率計算用チューリングマシン)というものの(概念的導入)が確率変数・分布の計算可能性を説明するだろう。計算可能な測度空間(computable metric space)、計算可能な解析(computable analysis)とかを使って考えることにする
- 1.3 条件付き確率。確率的プログラミングでは確率分布を高階オブジェクトで扱うので、ナイーブな意味での条件付き確率(確率の比、割合
)という捉え方ではうまく行かない。Measure zero setまでしか定義されていない可測関数として条件付き確率が定義されると言う点からも課題が生じる。実際条件付き確率の算出には、課題シナリオごとにad hoc な計算法が提唱されている、という感じであって、計算可能性を明らかにするために重要な一般化、という課題もあるらしい。
- 1.4 その他。離散集合か連続集合化。identifiability in the limit. 乱数発生。計算機での数え上げ。計算可能なランダムな変数の計算機的条件付き分布生成と、条件付き分布の計算可能性は、異なる問題。条件付き確率はRadon-Nikodym微分として(関数的に)書けることになっている(確率なので、１次元の単調関数と結び付けられるとかそんな話)のだが、Radom-Nikodym微分が、その１次元空間で計算可能性が云々というような理論的な計算可能性とも関係する。
- 1.5 このペイパーの結果のまとめ
- 計算可能な関数は連続。逆に言うと不連続関数が出てくると計算不可能になる。条件付き確率の関数には不連続なものがあるのでそれらは計算不可能
- では連続な関数となる条件付き確率なら計算可能か、というと、答えは否
- 連続な条件付き確率関数の計算不可能性問題はチューリングの停止性問題並みかそれ以上に難しい問題であることの例示ができる
- 条件付き確率が計算不可能かと言えば、一般にはそうではないわけだけれど、現実的には(近似として)計算する。有限回サンプリング・離散化して考える、とそういう近似。
