動的計画法は再帰で表せ

動的計画法の説明は常に再帰関数で書き表すことにしています．いやゆるメモ化再帰です．参照透過な関数は，同じ引数に対して同じ値を返すので，保存しておけばいいという感覚です．計算量の見積もりも簡単で，引数の異なり数に関数中のループの上限をかければおしまいです．特に再帰で書くことに慣れていれば自明に書けますし，テーブルを使ったDPと違って，ループの順番を意識する必要がありません．このテクニックは学部時代に@ohkuraに教えてもらいました．関数型言語に触れた今でこそ当たり前に見えますが，当時は目から鱗だったのを覚えています．
メモ化再帰と不動点に関する@kinabaさんの日記や，プログラミングコンテスト的には@chokudaiさんの記事が参考になります．

今更ですが，ちょっと例で説明します．フィボナッチ数を計算する関数fib(x)は再帰式で，fib(x) = fib(x - 1) + fib(x - 2)とかけます．このままプログラムにかくと，

def fib(x):
if x == 0 or x == 1:
return 1
else
return fib(x - 1) + fib(x - 2)

これで参照透過な関数はかけました．後はメモ化するだけ．

def fib(x):
if x in cache:
return cache[x]
elif x == 0 or x == 1:
return 1
else:
v = fib(x - 1) + fib(x - 2)
cache[x] = v
return v

これだけです．基本，再帰が書ければそこでおしまい．パフォーマンスがシビアにならない限り，基本的に全部これでプログラム書いています．

もっとNLPよりな例を出します．たとえば，linear-chain CRFのViterbiパスのスコアを求めてみましょう．



s(x, y)は素性ベクトルと重みベクトルの内積です．やはり再帰でかけますので，同じようにメモ化するだけです．メモ化したあとに，じっとにらめっこすると，いわゆるDPテーブルを使った動的計画法に変換できます．ただ，DPテーブルを使う場合は，計算の順番を考えないといけない点で面倒です．つまり，v[t][x]の計算にはv[t-1][・]が全部終わっている必要があります．関数呼び出しコストがなくなるので，実用上は速くなります．ただし，CRFやHMMくらいならいいですが，CKYの計算順序くらいになると直感ではわからなりません．再帰で書けば，計算されてなかったら計算する，計算済みならキャッシュを返す．それだけです．まぁ，依存関係を図示すれば多くの場合すぐわかりますが．


On Efficient Viterbi Decoding for Hidden semi-Markov Models.
Ritendra Datta, Jianying Hu, Bonnie Ray, ICPR 2008.

Semi-MarkovのViterbiがDPテーブルを2つ使うと高速になるよ，という論文を以前先輩に紹介されました．最初この論文は式が全然追えなくて，なんて複雑怪奇な計算をしているんだと思ったのですが，途中にある再帰式を眺めてたら気づきました．



Bの部分は一部省略してます．これの計算量はT * N引数で，T回ループとN回ループがあるのでO(N²T²)といってます．これをちょっと変形します．



単に内側のmaxを外だしにしました．相互再帰になりました．見えましたか？　どちらの関数もT * N引数で，ηはN回，δはT回のループです．これを素直にメモ化すれば，計算量はO(NT(N + T))です．恐ろしく簡単になりました．こう書けばいいのに・・・．

思うに，この程度まで複雑になってしまうとDPテーブルを使って考えるのは難しいです．まず，再帰で表す．そしてメモ化．速くしたければDPテーブル化．再帰で表すセンスは関数型言語で磨きましょう．リストや木やDAGを見ると再帰で表したくてうずうずしたくなりますよ．