1

(PO)MDP 用のツールボックスを作成していますが、悪いパターンが発生しています。特に強化学習アルゴリズムを実装するときは、同じことを繰り返す傾向があります。次の疑似アルゴリズムを参照してください。

arguments: epsilon

v <- initial V values
c <- initial C values

while not good-enough
   delta <- 0.0
   if in-place
        v_old <- copy(v)
    else
        v_old <- reference to v
    for s in ss
        a = some_value(s,old_v)
        old_v <- v_old[s]
        v[s] = c*a*v_old[s]
        delta = max(delta,old_v-v[s])
    if delta < epsilon
        good-enough <- true

return v

このほぼ同一のアルゴリズムを見てください。

arguments: epsilon,gamma

v <- initial V values
c <- initial C values

while not good-enough
    delta <- 0.0
    if in-place
        v_old <- copy(v)
    else
        v_old <- reference to v
    for s in ss
        a,o = get_a_and_o(s)
        old_v <- v_old[s]
        v[s] = c*v_old[s]*exp(o-a)
        delta = max(delta,old_v-v[s])
    if delta < epsilon(/1-gamma)
        good-enough <- true

return v

これらのアルゴリズムにはいくつかの単純な違いがありますが、かなり繰り返しています。ここで私の質問は次のとおりです。これら 2 つのサンプル アルゴリズムの共通部分(実際のアルゴリズムに適用可能) をどのように抽象化しますか?

私は（Pythonで）1つのアプローチを見てきました。アルゴリズムに前、後、および反復ごとにそれぞれ呼び出される前、後、およびループ関数を与え、変数を保持するためにアルゴリズム状態辞書を渡しました。しかし、このアプローチはあまり良いものではありませんでした。助言がありますか？

4

3 に答える 3

1

オブジェクト指向のアプローチは、アルゴリズムの共通部分を含み、アプリケーション固有の部分 (つまり、プリ、ポスト、またはループ関数) を含まない基本クラスを作成することです。代わりに、それ自体が実装していない仮想メソッドへの呼び出しがあるだけです。

次に、実際のユースケースをインスタンス化する場合は、基本クラスのコードが呼び出す必要がある仮想メソッドの実装のみを含む、その基本クラスのサブクラスを作成します。

于 2012-11-30T18:09:14.613 に答える
1

明らかに、2 つのアルゴリズムには多くの共通点があります。全体的なワークフロー/ステップは実質的に同じですが、唯一の違いは、ステップで何が起こっているかの詳細です。これは、関数型アプローチが輝く場所の 1 つです。全体的な構造をそのまま維持しながら、特定の関数/評価を置き換えたいと考えています。

詳細に入ることなく、コードを見ると、次のことがわかります。

  1. それらは同じ入力 V を使用します
  2. 各反復で、V といくつかのパラメーターを使用して、V の更新された値が生成されます。
  3. 各反復で、新旧の V といくつかのパラメーターを使用して、条件が評価されます。新しい V で十分かどうか、またはアルゴリズムを続行する必要があるかどうか。

重複を避けるためにどのようにアプローチできるかについてのスケッチを次に示します。

2. を次のように言い換えることができます。「各反復で、V の現在の値に関数を適用し、更新された値 V' を返します」 - そして明らかに、その関数には署名がありますUpdater: fun 't -> 't(Updater 関数はt と入力し、同じタイプの出力を返します)。

同様に、ステップ 3 は、「各ステップで、ペア (V, V') に関数を適用します。これは、はいまたはいいえで十分かどうかを教えてくれます」と述べることができます。この関数には、次のような署名が必要です。Finished: fun ('t * 't) -> bool. (タイプ 't の 2 つの項目のタプルが与えられた場合、評価して真/偽の答えを返します)。

Updater 関数と Finished 関数の詳細を抽出し、引数としてメイン アルゴリズム (ループ Search と呼びましょう) に渡すことができます。

let Search (Updater: fun 't -> 't) 
           (Finished: fun ('t * 't) -> bool) 
           currentV: 't =
    v' = v
    while not Finished (v, v')
        v' <- Updater v
    return v

(上記の例は実際にはまったく正しくありませんが、その精神を伝えています。通常、これを関数型スタイルの再帰として記述します。これは次のようになります。

let rec Search (Updater: fun 't -> 't) 
               (Finished: fun ('t * 't) -> bool) 
               currentV: 't =
    if Finished (v, v') 
        then return v'
    else
        Search Updater Finished v'

ループ全体を書き直す代わりに、更新ステップと終了ステップに適用する特定の関数を定義できます。コードの重複はなくなりました。ループ/構造全体は変更されず、完全に機能する関数を記述するだけです。当面の問題に固有のもの。

ここでたくさん手を振ったので、これが役立つことを願っています。興味があれば、F# または C# のコード サンプルを提供して、実際のコードのアイデアを示します。

于 2012-11-30T20:00:27.627 に答える
0

ファーストクラス関数を使用する：さまざまな引数タイプを別のクラス（配列、タプルなど）にカプセル化し、おそらく呼び出された関数を関数に渡してcalculateDeltaFunctionから呼び出します。

def oneDeltaWay(s, myAlgorithmArgs) : 
  ...first example...

def anotherDeltaWay(s, myAlgorithmArgs) : 
  ...second example...

def commonStructure(calculateDeltaFunction, functionSpecificArgs) :
  ... common code ...  
  for s in ss
    delta = calculateDeltaFunction(s, functionSpecificArgs)
    if delta < epsilon(/1-gamma)
       good-enough <- true
  ...etc...

commonStructure(oneDeltaWay, firstTypeOfArgs)
commonStructure(anotherDeltaWay, secondTypeOfArgs)
于 2012-11-30T20:16:11.667 に答える