強化学習・MDP
昨日黒橋研・河原研合同の勉強会で強化学習について話しました。話している中でわかったこともあるので、整理をするため、そのメモなど。
強化学習とは
一般的に言語処理で用いられる教師あり機械学習とは少し異なります。教師あり学習では入力(観測データ)x と出力(正解ラベル)y が与えられ、P(y|x)をどう解くかという問題になります(雑な説明
一方、強化学習においては、入力(観測データ)x に対してモデルからの出力(action)u があり、それによって観測データx がx' へと変化します。その変化に対する報酬関数(reward function)を定義し、その報酬関数を最大化することによってモデルの振る舞いを決定する、というアプローチになります。
強化学習はモデルの振る舞いの系列と、それに対するデータの変化を扱うことができるので、ロボット制御や対話制御などによく用いられます。
強化学習全体を図にするとこんな感じになります。モデルは周囲の環境x を計測し、その計測結果をz として保持します。これを観測モデル(Perception Model)と呼びます(p(z|x))。
さらに、そのz からどのアクションu を選ぶか、そのアクション選んだ結果どのような変化が周囲の環境に起こったかをモデル化します。これを行動モデル(Action Model)と呼びます(p(x'|x,u))。
これら２つのモデルをどう扱うかが強化学習のバリエーションになるわけですが、一般的にロボット制御・対話制御などで使われるMDP(Markov Decision Process)・POMDP(Partially Observed Markov Decision Process)では、Action Modelはいずれの場合も確率的に扱います。これは、モデルが環境に与える影響を、必ずしも100%予想できないということに起因します。これはどういうことかというと、対話において相手が何と答えるか100%正しく予測することはできない、ということです。
前者の観測モデルの扱いはMDPとPOMDPで異なり、MDPではこれを決定的に扱うのに対して、POMDPでは確率的に扱います。つまり、MDPではさきほどのx からz は写像として扱いますが、POMDPではこれを確率分布として扱います。これによってPOMDPは、対話の例では対話理解の誤り、音声認識の誤りなどの可能性をモデル化することができますが、その分実装は難しくなります。*1
つまりMDPとPOMDPの概要はこんな感じになるわけです（上がMDPで下がPOMDP）。
MDPは連続値、離散値共に扱えるようになっていますが、ここでは話をわかりやすくするために離散値を仮定して話をすすめます。
先ほどから報酬関数(reward function: r(x,u))がたな晒しになってるわけですが、これはシステムにおけるタスク達成とコストを表すものです。例えばタスク達成対話なら、
- r(x,u) += 100 where ありがとうと言われたとき
- r(x,u) += -100 where タスク失敗
- r(x,u) += -1 where 1ターン経過
- r(x,u) += -5 where 聞き返し
のような感じでActionに対してrewardを定義するわけです。
強化学習では、この報酬をどれくらい先まで見るか、ということを定義できます。Vを報酬の総和と考えると、
という雰囲気のイタレーションをまわして、将来までの報酬を計算するわけです。ここでγとは割引率をさし、将来の報酬の方が影響が少なくなるよう、１以下に設定します（逆にいうとγを設定しないとイタレーションを打ち切る範囲を決めない限り、収束しません。打ち切る範囲を決めた場合は、その範囲がどれくらい将来までの報酬を計算したか、ということになります）。maxはu についてとります。*2
この例では、p(x'|u,x)の行動モデルをMDPとして確率的に扱う場合、V(x')p(x'|u,x)がx'という次の状態の期待値になります。MDPにおいてx からz までは写像となり、その結果状態がx' となった場合の次の報酬は決定的に求めることができます。
POMDPを扱おうとする場合、x → z を写像ではなく確率分布として定義することになる*3ので、連続時間の各時間において確率分布で定義される状態を扱う必要があるため、状態が無限となり計算できなくなります*4。離散値で扱う場合でも、MDPと比較してかなり計算量のオーダがかわってくるので、探索範囲をオントロジーを使って絞り込むというのが対話でよくあるアプローチです。
NLPでの強化学習のチュートリアルが途中で終わってしまったので、補完するために勉強会でやってみました。
とはいいつつ、まだ実装してないので、式が間違っているかもしれませんが…（弱気
4/18追記: 何点かご指摘を頂いたので修正しました。指摘頂いた方、ありがとうございます。
