確率的プログラミング-人工知能の鍵？

いくらかの水

1年半以上前、 「DARPAは機械学習に革命を起こすつもりである」というニュースが通りました。 もちろん、DARPAは確率的プログラミングに関連する研究プログラムにのみお金を割り当てました。 確率的プログラミング自体は、DARPAなしでかなり長い間存在し、開発されてきました。また、MITなどの主要な大学とMicrosoftなどの大企業の両方で研究が行われています。 そして、DARPA、Microsoft、MITなどは無駄ではありません。 機械学習、そしておそらく人工知能全般にとって非常に有望であるため、この領域に細心の注意を払ってください。 機械学習の確率的プログラミングは、通常のプログラミングの高水準言語と同じ役割を果たすと言われています。 私たちは別の類似点をもたらします-彼が古き良きAIのために演じたプロローグの役割を持ちます。 しかし、このトピックのRuNetでのみ、いくつかのリンクのみを見つけることができ、基本的に一般原則の説明のみが含まれています。 おそらく、これは確率的プログラミングの可能性が明らかになり始めたばかりであり、それが主な傾向になっていないという事実によるものです。 しかし、確率的言語には何が可能または可能ですか？



確率的プログラミング言語の2つの主要なクラスを区別できます。これらは、ベイジアンネットワーク（または他のグラフィカルな確率的モデル）の形式でのみ生成モデルを定義できる言語、またはチューリング完全言語です。



前者の代表的なものは、Microsoftで開発されたInfer.NETです。 その中で、生成モデルとしてベイジアンネットワークを使用しているおかげで、彼らに知られている効果的な出力方法を使用できることがわかりました。 当然、よく知られた推論方法を備えたよく知られたクラスのモデルを使用しても、いくつかの根本的に新しい問題を解決する可能性はありません（そして、限られたボルツマンマシンに基づくディープラーニングネットワークなどの生成モデルでさえ、そのような言語では表現できません）ツール。 開発者によると、このツールを使用すると、数十行のコードしか占有せず、通常の言語で効果的な出力手順を個別に実装する必要がある場合、主要コンポーネントの完全ベイジアンバージョンの分析など、数時間で非自明な確率モデルを実装することが可能です知識と数週間の仕事。 したがって、確率的プログラミングにより、グラフィカルモデルの使用ははるかに簡単で手頃な価格になります。



ただし、チューリング完全確率言語には、はるかに大きな可能性があります。 それらにより、既存の機械学習メソッドがすでに解決方法を知っているタスクのクラスを超えることができます。 当然、そのような言語では、出力効率の問題が発生しますが、これはまだ解決にはほど遠いため、実際の問題のスケーラビリティが低下します。 ただし、この方向は積極的に開発されており、確率的汎用言語の興味深い実用的な問題に対して効果的な出力を達成する方法を示す多くの研究があります。 近い将来、これらのソリューションが特定の言語で使用できるようになることが望まれます。 さらに、チューリング完全確率言語は、認知モデリングおよび一般的な人工知能に関連する研究で非常に有用であることがすでに証明されています。 これらの理由から、私たちはチューリング完全言語の例に基づいて確率的プログラミングの基本原理を正確に検討します。チューリング完全言語からは、Lisp言語（より具体的には方言-Scheme）の拡張であるChurchを選択しました。 この言語の利便性（少なくとも初めて知るため）は、その言語のWeb実装（Web教会）の存在にあり、追加のソフトウェアをインストールせずに実験できます。

だからポイントに

確率的言語のプログラムは、一見、通常の言語のプログラムと変わらないかもしれません。 それがまさに教会で行われたことです。 通常のLispと同様に、この言語変数では、関数を定義でき、確定的な計算が実行されます。 たとえば、次のプログラムは、1つの引数の関数を定義し、再帰式n！= N *（n – 1）！を使用して階乗を計算し、n = 10に対してこの関数を呼び出します。

(define (fn) (if (= n 0) 1 (* n (f (– n 1))))) (f 10)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

また、この言語では、（擬似）ランダム関数の呼び出しがある場合があります。 たとえば、確率0.3で呼び出し（フリップ0.3）を行うと、値#tが返され、確率0.7-#fで返されます。 このような関数は、Lispで次のように基本的に実装されます。

 (define (flip p) (< (random) p))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Churchは、他の確率的言語と同様に、特定の分布に従ってランダムな値を返す多くの組み込み関数を備えています。 たとえば、（gaussian x0 s）は、指定されたパラメーターでガウス分布した実数のランダム変数を返します。 他の実現された確率分布として、均一、多項、ディリクレ、ベータ、ガンマが通常存在します。 これらの配布はすべて、通常の言語で手動で実装するのがそれほど難しくなく、ChurchとLispの間に根本的な違いはありません。



ただし、通常のセマンティクスに加えて、教会プログラムには確率論的なセマンティクスがあり、その枠組みでは、ランダム関数の呼び出しを含むプログラムは、開始時にランダム変数の特定の値を生成するだけでなく、それらの確率分布を設定すると想定されています。 そのため、（gaussian x0 s）は、ガウス分布したランダム変数の特定の値を返すだけの関数ではなく、ガウス分布そのものです。



しかし、プログラムで定義されたこれらの確率分布を取得する方法は？ たとえば、プログラムを想像してください

 (if (flip 0.4) (flip 0.1) (flip 0.6))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、確率0.4では、この式の値はP（#t）= 0.1およびP（#f）= 0.9であり、確率0.6では、P（#t）= 0.6およびP（#f）= 0.4です。 この式によって与えられる最終的な分布は、P（#t）= 0.4およびP（#f）= 0.6からどこになりますか？ この確率論的なセマンティクスは、多くの場合、サンプリングプロセスによって実現されます。プログラムを何度も実行し、その実行結果の選択を構築することができます。 もちろん、このような手順は通常の言語で実装することも簡単です（実際、Simula-67は確率的プロセスをモデル化するためにこの方法で定期的に使用されていました）。



ただし、現代の確率言語はさらに進んで、プログラムの実行結果に課される条件をサンプリングプロセスに追加します。 この考え方は、最も単純な障害サンプリングにつながります。これは、教会では拒否クエリ機能によって実装されます。 この入力関数は、確率的プログラム（定義のセットとして）、戻り値を計算する最後から2番目の式、最後の式は条件（述部）であり、実行中にtrueになります。 プログラムを検討する

 (rejection-query (define A (flip 0.4)) (define B (flip 0.6)) B (or AB))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

reject-queryは、最後の条件（ここ（またはAB））が満たされるまで送信されたプログラムを実行し、最後から2番目の式の値（ここ）を返します（ここB）。値の選択を取得するには、repeat関数を使用できます。 教会には、ヒストグラムをプロットするための組み込み関数もあります。 少し高度なプログラムを検討してください。

 (define (get-sample) (rejection-query (define A (flip 0.4)) (define B (flip 0.6)) B (or AB))) (hist (repeat 1000 get-sample))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

起動時に、次の結果が得られます：#f-21％、＃t-79％（開始から開始までの数値はわずかに異なる場合があります）。 この結果は、Bの値が#tであり、確率が0.8よりわずかに小さいことを意味します。 プログラムBでP（#t）= 0.6のバイナリ確率変数である場合、この確率はどこから来ましたか？ 明らかに、ポイントは条件を課すことです：（またはAB）。 サンプリングプロセスでは、AまたはB自体が真であるようなBの値のみを受け入れ、実際には事後確率P（B | A + B）を考慮します。 Bayesianルールを使用して、この確率を手動で計算できます。

         P（B | A + B）= P（A + B | B）P（B）/ P（A + B）= 
         =（P（A | B）+ P（B | B）–P（A | B）P（B | B））P（B）/（P（A）+ P（B）–P（A）P （B））=
         =（P（A）+ 1 – P（A））P（B）/（P（A）+ P（B）–P（A）P（B））= 0.6 /（0.4 + 0.6–0.4 * 0.6 ）= 0.789。

ただし、このような基本プログラムの場合、ベイズ規則の手動適用には時間がかかり、重要なプログラムの場合は、値を分析的に計算できない場合があります。



そのため、サンプリングにより、特定の条件が課されている場合に、対象のランダム変数の事後確率を計算できます。 これは、モデルの選択や予測を行うための機械学習で広く使用されているベイジアンルールに代わるものです。 同時に、多くの人にとって確率的な言語でプログラムを書くことは、ベイズ規則を適用するよりもはるかに理解しやすいものです。 もちろん、ノッチサンプリング自体は一般的なプログラミング言語で非常に簡単に実装できますが、確率的な言語はこれに限定されません。

特に、教会では、サンプリングのための別の関数-enumeration-queryが実装されています。 プログラムを実行する

 (enumeration-query (define A (flip 0.4)) (define B (flip 0.6)) B (or AB))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

出力では、（（＃t #f）（0.7894736842105263 0.2105263157894737））が得られます。 確率Pの正確な値（B | A + B）はここで導き出されます（もちろん、有限のビットグリッドを割引します）。 enumeration-queryは、プログラムを何度も起動するだけでなく、実行パスを分析し、確率を考慮してランダム変数のすべての可能な値を反復処理します。 もちろん、このような「サンプリング」は、ランダム変数値の可能な組み合わせのセットが大きすぎない場合にのみ機能します。



教会では、MCMC（モンテカルロマルコフチェーン）に基づくノッチサンプリング、つまりメトロポリスヘイスティングスアルゴリズム、つまりプロシージャの名前-mh-queryのより高度な代替もあります。 このクエリプロシージャは、指定された数のサンプルをすぐに生成します（また、1つの追加パラメーター-lagを受け取ります）。 この手順も実装が自明ではないため、事前定義された確率言語を使用する（通常の言語で単純なサンプリング手順の独自の実装を使用するのではなく）ことは理にかなっています。



ただし、確率的プログラミングが提供する主なものは考え方です。

基本から応用まで

開発者が異なれば、確率的プログラミングのアプリケーションも異なります。 多くは機械学習の問題を解決するためにそれを直接適用しています。 教会の著者であるノア・D・グッドマンとジョシュア・B・テネンバウムは、彼らのウェブブック「認知の確率的モデル」で、認知モデリングのための確率的プログラミングの使用を示しています。 また、確率論的言語の推論の観点から計画問題の解決策を表すことがいかに便利であるかが知られています。 また、知識の表現とその導出、および機械認識のタスク（画像認識を含む）にも適用できることがわかりました。 これらのアプリケーションはすべて多かれ少なかれ断片化されていますが、それらすべてに共通のフレームワークが存在することは、確率的プログラミングがAIの「大統一理論」になり得ることを示唆しています。 可能な使用の最も単純な例を見てみましょう。



エキスパートシステムの最も典型的な例の1つは、医療診断です。 特に、MYCINシステムは、次の形式のルールシステムに基づいて構築されました。



ルール52：

もし

1. 文化の場所は血です
2. 組織のグラムはNEGです
3. 組織の形態はロッドです
4. 患者の火傷は深刻です

それから弱い示唆的な証拠があります（0.4）

1. 組織のアイデンティティはシュードモナスです

明らかに、この種の規則は教会のような言語でよく説明されています。 同時に、引き出し手続きも実装する必要はありません-ルールのシステムを書くだけです。 言及された本「認知の確率的モデル」の例を次に示します。

 (define samples (mh-query 1000 100 (define lung-cancer (flip 0.01)) (define TB (flip 0.005)) (define cold (flip 0.2)) (define stomach-flu (flip 0.1)) (define other (flip 0.1)) (define cough (or (and cold (flip 0.5)) (and lung-cancer (flip 0.3)) (and TB (flip 0.7)) (and other (flip 0.01)))) (define fever (or (and cold (flip 0.3)) (and stomach-flu (flip 0.5)) (and TB (flip 0.2)) (and other (flip 0.01)))) (define chest-pain (or (and lung-cancer (flip 0.4)) (and TB (flip 0.5)) (and other( flip 0.01)))) (define shortness-of-breath (or (and lung-cancer (flip 0.4)) (and TB (flip 0.5)) (and other (flip 0.01)))) (list lung-cancer TB) (and cough fever chest-pain shortness-of-breath))) (hist samples "Joint inferences for lung cancer and TB")
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このプログラムは、肺がん、結核、風邪などを発症している患者の事前確率を決定します。 次に、特定の病気で咳、発熱、胸痛、息切れを観察する確率を決定します。 戻り値は、患者が癌および/または結核を患っているかどうかのブール値のペアです。 最後に、条件は、観察された症状のセットです（つまり、すべての変数の値が咳熱胸痛、息切れ-#tである場合、サンプリングが実行されます）。



プログラムの結果は次のようになります：（#f #f）-4％、（#f #t）-58％、（#t #f）-37％、（#t #t）-1％

サンプルを症状のリストを提供する関数にすることは簡単です。これは、サンプリングのためにmh-queryで使用され、さまざまな患者の診断を可能にします。 もちろん、この例は非常に単純化されていますが、確率的プログラミングのスタイルでは、知識を表現し、それについて結論を出すことは非常に可能です。



当然、機械学習の問題を解決することは可能です。 それらの違いは、未知のパラメーターがモデル自体のパラメーターであり、このモデルによるトレーニングサンプルの生成がサンプリングの条件として機能することだけです。 たとえば、上記のプログラムでは、フォームの行の数字（define lung-cancer（flip 0.01））を、それ自体がランダムに設定される変数で置き換えることができます（define p-lung-cancer（uniform 0 1））そして、トレーニングサンプルの各患者について、肺がんの値はすでに肺がんの確率で決定されています。



点の集合から多項式のパラメーターを推定する簡単な例を使用して、この可能性を検討します。 次のプログラムでは、calc-polyはxでwsパラメーターを使用して多項式の値を計算します。 generate関数は、指定されたxsリストの各値にcalc-polyを適用し、対応する縦座標のリストを返します。 ノイズの多い手順？ 「近似的に」2つの与えられた値を比較します（これらの値が等しい場合、関数は確率1で#tを返します。等しくない場合、それらが異なるほど、＃tを返す可能性は低くなります）。

 (define (calc-poly x ws) (if (null? ws) 0 (+ (car ws) (* x (calc-poly x (cdr ws)))))) (define (generate xs ws) (map (lambda (x) (calc-poly x ws)) xs)) (define (noisy-equals? xy) (flip (exp (* -3 (expt (- xy) 2))))) (define (samples xs ys) (mh-query 1 100 (define n-coef 4) (define ws (repeat n-coef (lambda () (gaussian 0 3)))) ws (all (map noisy-equals? (generate xs ws) ys)))) (samples '(0 1 2 3 4) '(0.01 1.95 6.03 12.01 20.00))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

mh-query呼び出し内で、n-coefパラメーターは、多項式の係数の数（つまり、次数+ 1）を決定します。 wsは、正規分布に従って生成されたランダム変数で構成されるリストです。 戻り値は、多項式パラメーターのリストです。 サンプリングの条件は、ysの指定されたすべての値が、指定されたwsの多項式によって生成されたすべての縦座標と「近似」等しいことです。 ここでは、条件付きの実装を1つだけ要求します（パラメーターベクトルのヒストグラムを作成するのはあまり便利ではないため）。 このクエリの結果は、たとえば、多項式2.69 + 1.36x + 0.53x ^ 2–0.10x ^ 3を定義するリスト（2.69 1.36 0.53 -0.10）になります。



一般に、実際のパラメーターを使用したモデルに関する結論は、教会言語の最強の側面ではありません（ただし、これは一般的な確率的プログラミングのグローバルな不利益と見なされるべきではありません）。 ただし、この例では、mh-queryは何らかの形で機能します。 これを確認するには、クエリのパラメーター値を決定する代わりに、ある時点で予測を返すように依頼できます。 最後のコードを次のように書き直します。

 (define (samples xs ys) (mh-query 100 100 (define n-coef 4) (define ws (repeat n-coef (lambda () (gaussian 0 3)))) (calc-poly 5 ws) (all (map noisy-equals? (generate xs ws) ys)))) (hist (samples '(0 1 2 3 4) '(0.01 1.95 6.03 12.01 20.00)))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、x = 5で最も可能性の高い（利用可能なデータを含む）値を要求します。 異なる開始時に、残念ながら、ヒストグラムの最大値はわずかに異なる値に落ちます（理論的には、MCMCメソッドは真の分布への収束を保証しますが、限界にのみ）が、通常、これらの値は非常にわかりやすいでしょう。 ここで、「無料」で（1行を置換することで）完全なベイジアン予測を受け取ったことに注意してください：最良のモデルを選択して、それだけで予測する代わりに、x = 5で値の事後分布を受け取りました。 。

しかし、それだけではありません。 繰り返しますが、1行-（define n-coef 4）->（define n-coef（random-integer 5））を置き換えることにより、異なる数のパラメーターを持つモデル間で自動選択を行うことができます。 さらに、n-coefの値をサンプリングすると（非常に安定しているわけではありませんが）、最も可能性の高い値はn-coef = 3（つまり、特定のポイントセットに埋め込まれた放物線）であることがわかります。 この変更により、予測がより安定します。 つまり、再トレーニングの効果はありません！ それでは、より高い次数の多項式が選択されないのはなぜですか。それらは与えられた点により正確に行くことができるからです。 事実、サンプリング時に、多項式のパラメーターの適切な値を「推測」することは、高次の多項式よりも単純ではありません。したがって、テストに合格するパラメーターを生成する確率は、3番目よりも2番目の多項式の方が高くなります。 同時に、一次の多項式は大きな偏差を与えます。 大幅に低下します。



確率的プログラミングのフレームワークでは予想外のように見えるかもしれない別のアプリケーションを見てみましょう。 これが「演ductive的」問題の解決策です。 最初に与えられた階乗計算関数を使用しますが、固定値で呼び出す代わりに、引数はランダム変数であると仮定しますが、階乗自体の値に制限が課されます：

 (define (fn) (if (= n 0) 1 (* n (f (- n 1))))) (enumeration-query (define n (random-integer 20)) n (equal? (fn) 120))
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

答えとして、n = 5で確率1が表示されます。120の代わりに100を設定すると、プログラムはサイクルに入らず（rejection-queryまたはmh-queryを使用しますが、これは欠点と考えられます） 。 厳密な平等ではなく、その他の制限を条件として設定することができます。



同様に、より複雑な問題も解決できます。 サブセットの合計の問題を解決したいとします：その中で、与えられた数のセットから、合計が与えられた数に等しいサブセットを見つける必要があります（通常、この数として0が取られ、サブセットが空でないことが必要です;しかし、チェックを取り除くために解の非自明性、非ゼロの合計を取ります）。 確率的プログラミングはどこで行われるのでしょうか？ しかし、ランダム変数は単に未知の量です（事前確率が与えられます）。 どんな問題でも、サブセットの合計の問題を含め、未知のものを見つける必要があります。 次の基本プログラムを見てみましょう（summをfoldで書くことで簡単にできます）。

 (define (solution xs v) (rejection-query (define ws (repeat (length xs) flip)) (define (summ xs ws) (if (null? xs) 0 (+ (if (car ws) (car xs) 0) (summ (cdr xs) (cdr ws))))) ws (equal? (summ xs ws) v))) (solution '(-1 3 7 5 -9 -1) 1)
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ここで、wsはランダムなブール値のリストです。 summプロシージャは、リストwsの対応する要素がtrueであるリストxsの要素の合計を計算します。 次に、結果の合計が指定された数vに等しいという条件が満たされるwsの値を要求します。 このプログラムを実行すると、次の結果を得ることができます：（#f #t #t #f #t #f）、これはもちろん正しい（3 + 7-9 = 1以降）。



当然、教会は奇跡を起こさず、この仕事の次元を大きくすると、それに対処することができなくなります。 ただし、同じ言語を使用して、このような異なるAIタスクを少なくとも提示（および部分的に解決）できることは驚くに値しません。 さて、効果的な撤退の問題は今までも現在も残っています。 確率的言語では、少なくとも最も純粋な形で際立っています。