演繹能力に制約があるもとでの推論を扱った新しい論文のプレプリント。スコット・ガラブラント、ツヴィ・ベンソン＝ティルセン、アンドリュー・クリッチ、ネイト・ソアレス、ジェシカ・テイラーの共著である。
論理的帰納 — プレプリント
要旨：与えられた形式言語のすべての論理的な文に確率を割り当て、その確率を時間とともに改善する、計算可能なアルゴリズムを提示する。たとえば言語がペアノ算術なら、双子素数予想に関する主張、実行に長時間を要する計算の出力に関する主張、さらには自分自身が割り当てる確率に関する主張も含め、すべての算術的な文に確率を割り当てる。
このアルゴリズムは、私たちが論理的帰納器と呼ぶものの一例であり、直観的に望ましいと考えられる多くの性質を満たすことを示す。（1）論理的な文の真偽に見られるパターンが多項式時間で記述できる限り、そのパターンを予測するよう学習する。しかも多くの場合、それらの文を評価するための計算資源が得られるより、はるかに前にそうできるようになる。（2）真理値が擬似ランダムに見える文の列について、適切な要約統計量を使って予測するよう学習する。（3）自己言及に伴う標準的なパラドックスを避けつつ、自分が現在もっている信念について正確な信念をもつよう学習する。たとえば、あるコンピュータプログラムが特定の範囲の値しか出力しないなら、論理的帰納器はその事実を適時に学習する。また、πの小数展開の遠い桁を予測するのが難しい場合、十分大きなnについて「πの第n桁は7である」に約10%の確率を割り当てるよう学習する。論理的帰納器は、現在の信念よりも将来の信念を信頼するようにも学習し、その信念は極限で整合的になる（φ → ψであれば常に、ℙ∞(φ) ≤ ℙ∞(ψ)が成り立つ、など）。さらに、論理的帰納器は極限で普遍半測度を厳密に支配する。
これらを含む多くの性質は、すべて単一の論理的帰納基準から導かれる。この基準の着想は、株式取引に関する一連の類比から得られた。大まかに言うと、各論理文φに、φが真なら1株あたり1ドル、そうでなければ無価値になる株式を対応させる。そして、論理的な不確実性を抱える推論主体の信念状態を、市場価格の集合として解釈する。Pn(φ) = 50%とは、n日目に、この推論主体を相手にφの株式を50セントで売買できるという意味である。論理的帰納基準は、ごく大まかに言えば、リスク許容度が有限で、多項式時間で計算可能な取引戦略によって、その市場で時間とともに上限のない利益を得られてはならない、という条件である。この基準は、期待効用理論（フォン・ノイマン、1944年1）とベイズ確率論（ラムゼイ、1931年2、デ・フィネッティ、1937年3）の双方を支える「ダッチブックが存在しない」という基準によく似ている。
論理的帰納 — 講演
アンドリュー・クリッチが論理的帰納器の性質のいくつかを解説する。同じ講演の、研究の動機や今後の方向性を含む長い版はこちら。
- Von Neumann, John, and Oskar Morgenstern. 1944. Theory of Games and Economic Behavior. 第1版。Princeton, NJ: Princeton University Press.
- Ramsey, Frank Plumpton. 1931. “Truth and Probability.” The Foundations of Mathematics and other Logical Essays, Richard Bevan Braithwaite編、156–198頁。New York: Harcourt, Brace.
- de Finetti, Bruno. 1937. “Foresight: Its Logical Laws, Its Subjective Sources.” Studies in Subjective Probability, Henry E. Kyburg and Howard E.K. Smokler編。Huntington, New York: Roger E. Kreiger Publishing Co.