Blog
本記事は、2018年インターンシップに参加された南條陽史さんによる寄稿です。
はじめまして。PFNの2018夏季インターンシップに参加した筑波大学の南條陽史です。 大学ではプログラム言語について研究しており, 型理論やプログラム検証に興味があります。
今回のインターンで“確率的なプログラムの型による静的検証”というテーマで研究開発を行いましたので、その紹介をいたします。
テーマの説明
確率的なプログラムの検証
確率的プログラム、というと色々な意味がありますがここでは確率分布からのサンプリングといった確率的な挙動を含むプログラムを指します。 研究の目的はこの確率的プログラムに対して“悪いことが起きる確率はいくら以下である”とか“よいことが起きる確率はいくら以上である”といった確率についての仕様検証をすることです。
確率的なプログラムの仕様検証の応用例として以下が挙げられます。
- 確率的に生じる観測誤差によってシステムが誤った判断をしてしまう確率がしきい値以下であることの検証
- クライアントに仕事を割り振るシステムについて、あるクライアントに捌き切れないほど多くの仕事を流してしまう確率がしきい値以下であることの検証
このように確率的なプログラムの検証は現実的な問題に直接結びついています。
型による検証
僕のテーマはこの確率的なプログラムの検証を“型”主導で行うというものです。 型というのはintとかcharとかstringとかのあの型です。 プログラムの仕様としての型という考えを推し進めると、例えば以下のように詳細な仕様を型として記述できます。
rand(0, 5) : {x:int|Prob(x%2=0) = 1/2}
これは0から5の整数を一様分布からサンプリングするプログラム (rand(0, 5)) に対して, その値が偶数である確率は1/2だという仕様 (Prob(x%2=0) = 1/2) を与えています。
型主導で検証することの利点として一般に以下が挙げられます
- 再利用性 : 検証が合成的なのであるプログラムの検証の結果をより大きなプログラムの検証に再利用することができます
- 網羅性 : 型による検証は数学的な証明に対応するので単体テストなどと違ってカバレッジ100%です
- 静的 : 検証がプログラムのコンパイル時に行われるので実際にプログラムを実行する必要はありません
既存研究
既存の確率的なプログラム検証のツールに確率的モデル検査器PRISM[1][2] があります。 これは確率的な状態遷移系に対して、悪い状態に到達する確率が十分低いことや良い状態に到達する確率が十分高いことを検証できます。
しかしPRISMを使うためには確率的状態遷移系を書き下す必要があり、人間が読み書きするには不向きでした。 一方で今回のテーマでは検証の対象をプログラムという形で与えることで、関数などのプログラム言語が持つ抽象化の手段を使うことにより検証の対象を人間が読みやすく記述することを可能にしています。
実装
インターンでは確率的なプログラムを記述できる小さなプログラミング言語のインタプリタとその型検査器を実装しました。ソースコードは[3]で公開しています。 この型検査器では型付可能性問題を既存ツールPRISMが扱える妥当性判定問題に帰着させて解いています。
実装したプログラミング言語では例えば次のプログラムの型検査が可能です。
(let a = rand(-10, 10) in
let b = a + rand(0, 10) in
not (b - a >= 10) /\ ((b + rand(0, 5)) - (a + rand(0, 5)) >= 10))
: {x:bool | Prob(x) <= 1/10}
このプログラムは“GPSに基づいてスピード違反を検出するシステムが観測誤差によって誤った判断をする確率がしきい値以下”であることの検証を簡単にモデル化したものです。
詳細に説明すると、 a はある時点での自動車の真の座標で b は微小時間後の自動車の真の座標として、 実際にはスピード違反していない (not (b - a >= 10)) のに観測誤差によってスピード違反と判定される ((a + rand(0, 5)) - (b + rand(0, 5)) >= 10) 確率が1/10以下である (Prob(x) <= 1/10) と言っています。
このプログラムと同等な検証をPRISMを使って行うと確率的状態遷移系は 1460 bytes ほどの非直感的なコードになり、確かに実装した言語上の方が簡潔にわかりやすく記述できることがわかります。
実装したプログラミング言語は一様な離散分布からのサンプリングのみを考えており言語機能も大きく制限されているので、現実的な問題を考えるためにはいくつかの機能拡張をする必要があります。 つまり
- 連続分布からのサンプリング
- 高階関数
- 条件付き確率
などです。 考えるべきことはまだまだ残っているので今後も開発を進めていきたいと考えています。
謝辞
インターンが始まった頃は機械学習について全く詳しくなかったのですが、メンターの方が僕にレベルを合わせてかなり初歩的なことから丁寧に説明をしてくださったのでとても助かりました。 メンターの方々以外にも多くの社員さんと交流する機会が用意されており、どの方のお話もとても楽しかったです。 社員の方々だけでなくインターン生にも優秀な方が多くとても刺激的で心地よい夏休みを過ごせました。 皆様に心から感謝いたします。貴重な経験をありがとうございました。
参考文献
- [1] PRISM : a probabilistic model checker
- [2] M Kwiatkowska, et al., “Stochastic Model Checking”
- [3] https://github.com/pfnet-research/pml
おまけ：メンターより
南條さんのメンターを担当したPFNの吉川と酒井です。
PFNは機械学習／深層学習そのものの研究開発のイメージが強いとは思いますが、フレームワークの開発などにおいてはプログラミング言語理論も含め幅広い分野の知識が必要となります。 今回南條さんに取り組んでもらったのも、現時点では非常に簡単なものではありますが、プログラミング言語理論的な知見を確率モデリング等に活かしていけないかと考えての試みです。お互いのバックグラウンドとなる知識の違いから苦労した部分もありましたが、最終的には簡単な言語の設計と実装までこぎつけることができました。
これに限らず、機械学習・深層学習にはプログラミング言語理論などで解決できる課題がまだまだあるのではないかと考えています。それらに興味をお持ちの皆さんも、ぜひ来年のPFNインターンシップへの応募をご検討ください。 また、もちろん中途・新卒の人材募集も通年で行っています。興味のある方はぜひご検討ください！PFNの人材募集のページはこちら https://www.preferred-networks.jp/ja/jobs です。
