2010/12/20

プログラミングのための確率統計 in Haskell

まっとうなサイコロをふったときに出る目の確率は、こんな表にまとめられます。

目の値123456
確率1/61/61/61/61/61/6

こんな表のことを確率分布といいます。サイコロをふったときに起こるイベントの確率、たとえば「偶数の目が出る」確率を調べることは、この確率分布からこんな別の確率分布への変換だと考えられます。

目の値2,4,6(偶数)1,3,5(奇数)
確率1/21/2

この変換は、具体的にはこんな対応です。
P(偶数) = P(2) + P(4) + P(6)
P(奇数) = P(1) + P(3) + P(5)
P(X)がイベントXに対する確率を表しているわけですが、Pを「イベントの集合から[0,1]区間の実数への関数」だとみなすこともできます。確率分布から確率分布への変換は、関数に対する演算でもあるわけです。確率分布を連想リストで表せば、高階関数や代数型を使って、この変換をモデル化できそうです。

以前、このアイデアをSchemeで試してみたことがありました。当時は、そもそも確率についての理解が今よりもいっそうあやしかったし、実装もちゃちでしたが、このアイデアが特別なものでなかったことを最近になって知りました。その名も確率的関数プログラミング(Probabilistic Functional Programming)。PFPと呼ばれているようです。Haskellのライブラリが公開されているので、これで遊んでみます。



PFPでは、確率と確率分布をだいたいこんな感じに定義しています。
newtype Probabillity = P Float
Dist a = D [(a, Probability)]
確率分布(Probabilistic Distribution)は連想リスト以外のなにものでもありません。

さっそく例題をといてみましょう。次のような確率の問題を考えます。どこかで見たことがあるような問題ですね :)
とあるロールプレイングゲームではモンスターを倒すと宝箱が得られます。その宝箱には確率 2/3 で罠がかかっています。罠の気配は魔法で判定できますが、この判定は完璧ではなく、確率 1/10 で間違った判定結果がでてしまいます。
  • 問題1. モンスターを倒して得た宝箱に魔法をかけたとき気配なしと判定される確率は?
  • 問題2. 魔法をかけたら気配なしと判定された。このとき本当は罠がかかっている確率は?
なにはともあれ、宝箱をあらわす型を用意します。宝箱は、罠がかかっているか、安全か。
data TreasureBox = Trap | Safe
問題文を読むと、2つの確率分布があたえられていることがわかります。罠がかかっている確率をあらわす分布と、判定魔法の結果をあらわす確率分布です。PFPには、イベントを列挙したリストと、それに対応する確率を列挙したリストとから確率分布を生成するための関数enumが用意されているので、これを使います。
treasureOfMonster   :: TreasureBox -> Dist TreasureBox
treasureOfMonster _ = enum [2/3, 1/3] [Trap, Safe]

magicSpell :: TreasureBox -> Dist TreasureBox
magicSpell Safe = enum [1/10, 9/10] [Trap, Safe]
magicSpell Trap = enum [1/10, 9/10] [Safe, Trap]
いずれの関数も、引数として受け取るのは目の前にある宝箱です。目の前にある宝箱は、それがモンスターから得たtreasureOfMonsterであれば、とにかく 2/3 で罠がかかっています。その宝箱にmagicSpellをかけると、罠がかかっていなくても 10回に 1回は罠がかかっていると判定してしまうし、逆に 10回に 1回は罠がかかっているのに安全だと判定してしまいます。

では、目の前にあるtreasureOfMonsterな宝箱にmagicSpellをかけてみましょう。2つの確率分布を組み合わせればいいのですが、magicSpellの結果は、とうぜん、treasureOfMonsterな宝箱に罠がかかっているかどうかで変化します。分布Bが分布Aに依存するというなら、分布Bそのものではなく、Aから分布Bへの関数を組み合わせればいい。つまり、Distがモナドであればいいということです。実際、PFPではそのように実装されています。だから、こんなふうにすれば、モンスターの宝箱を魔法で調べた結果の確率分布が得られます。
check     :: TreasureBox -> Dist TreasureBox
check box = treasureOfMonster box >>= magicSpell
試してみましょう。宝箱はなんでもいいので、undefinedを与えておきます。
*RPG> check undefined
Trap 63.3%
Safe 36.7%
問題1の答は 36.7% だとわかりました。本来の安全な確率である 1/3 より若干多い値であることから、誤判定で罠を見抜けない危険性のほうが、罠がないのに罠があると間違えてしまう可能性よりも影響が大きいようです。

問題2に答えるために、罠がかかっているのに罠がないと判定してしまって死に至る確率を考えてみましょう。そのような事態はこんな演算として表せます。
death           :: TreasureBox -> TreasureBox -> TreasureBox
death Safe Trap = Trap
death _ _ = Safe
magicSpellの結果とtreasureOfMonsterの結果のそれぞれに対して、このdeath演算を適用すれば、その一覧から死に至る確率がわかるでしょう。PFPでは、このような操作のために、joinWith :: (a -> b -> c) -> Dist a -> Dist b -> Dist cという関数が用意されています。
dead     :: TreasureBox -> Dist TreasureBox
dead box = joinWith death (magicSpell Trap) (treasureOfMonster box)
magicSpellに与えている引数がTrapなのは、ここで気にしている状況が「目の前にある宝箱に実際には罠がかかっている」場合だからです。ただ、魔法をかけるほうからすると、目の前にある宝箱がdeadか否かはわかりません。deadで評価する宝箱はundefinedです。
*RPG> dead undefined
Safe 93.3%
Trap 6.7%
宝箱を前にしてmagicSpellによる判定結果を盲信するというポリシーをつらぬくと、6.7%の確率で死んでしまうようです。

さて、問題2に戻りましょう。知りたいのは、magicSpellの判定結果で安全と出たときに、実際には罠がかかっていて死を招いてしまう確率です。これは、いわゆる条件つき確率の問題なので、教科書的には Bayesの公式で解く場面です。しかし、すでに「判定結果で安全と出る確率」も「死に至る確率」もわかっているので、これらの比率を求めれば答が得られます。
guessedSafeButTrap :: Probability
guessedSafeButTrap = (==Trap) ?? dead undefined |/ (==Safe) ?? check undefined

infix 7 |/
(|/) :: Probability -> Probability -> Probability
(|/) (P p) (P p') = P $ p/p'
(??)は、PFPに用意されている「確率分布からイベントの確率を求める」関数で、Event a -> Dist a -> Probabilityという型を持ちます。(|/)は、Probability型同士の確率の値について割り算をするために定義しました。infixを7にしたのは、??infixが8だからです。

コンパイルして評価すれば問題2の答がわかります。
*RPG> guessedSafeButTrap
18.2%
安全だという判定が出ても、誤判定が 1/10 もあると、まだまだ気を抜けないようです。

(PFPのソースをのぞくと conditional probability というコメントのついた関数(|||) :: Dist a -> Event a -> Dist aがあって、いかにも条件つき確率の計算に使えそうだけど、確率分布からイベントの確率をfilterするようにしか見えない。そんな型で大丈夫か?)



まとめ

HaskellとPFPを使うことで、確率の問題をうまく抽象化してエレガントに回答を導くことができます。そしてこの抽象化は、Haskellという言語の機能によるものではなく、確率論という数学によるものです。PFPにしても、特別なHaskellの機能はほとんど使っていないように思います(PFPには確率過程をシミュレーションする機能もあって、そちらはもしかしたら高度なHaskellの機能が満載かも)。そんな数学における抽象化をダイレクトにコードで使えることがHaskellの魅力のひとつなのはいわずもがな。

数学では、抽象化が漏れて台無しにならないように、厳密な論証や独特の表記を使います。そのため、数学による問題の抽象化を利用するには、少し勉強や訓練が必要です。とくに確率論は、漏れがないように抽象化された理論(公理的確率論とか呼ばれます)を勉強しようと思うと、高校までの数学経験だけではつまずいてしまう教材が多い。多少の漏れを棚に上げた感覚的な確率の話をもって「確率論」という教材もあって、それはそれでおもしろいとは思うのですが、抽象化の道具として使うにはちょっとねえ。

そこでおすすめの教科書はこれ。



『プログラミングのための確率統計』
PDFでも買えます

ここまで読んだ貴徳な方なら、この記事の例題が『プログラミングのための確率統計』のものであることに気がついているかもしれません。具体的には53ページの例題2.7。この本に書いてある図を見れば、条件付き確率は一目瞭然です。確率分布や確率変数がとてもよくできた確率の問題の抽象化であることを実感できると思います。

なお、この記事は Haskell Advent Calendar jp 2010 のために書いたものです。宣伝いうな。

No comments :