PLAID Advent Calendar 2017 20日目です。
今日は人工知能と強化学習について @eshinji が簡単に触れてみます。
対象読者は人工知能とか強化学習に興味はあるけどよくわかってない人です。
人工知能とは
人工知能（以下AI）には強いAIと弱いAIという分類があるのをご存知でしょうか？強いAIは人間の脳そのものをシミュレートを目指しています。弱いAIは強いAIと違い、問題解決や推論を行うソフトウェアの実装つまり、特定の問題に対しての解決というのが目的となります。今回はその弱いAIについての話です。
強化学習とは
機械学習の一種で、行動の選択を取り扱うような問題を解く手法の一つです。本稿は強化学習について簡単な解説が趣旨となります。そもそも機械学習が何かというと、人間が自然に行っている学習能力と同等の機能をコンピュータで実現しようとするものです。機械学習はAIを構成する要素技術であり、ほぼAIと等価だと思って頂いて構いません。その中の強化学習は特定の問題に対する手法なので弱いAIに分類されます。
探索と活用
学習能力を実現することが目標なのですが、学習とは何なのでしょうか。辞書的には「人間も含めて動物が、生後に経験を通じて知識や環境に適応する態度・行動などを身につけていくこと。不安や嫌悪など好ましくないものの体得も含まれる。」とあります。端的に言うと経験を通じて適応していくということになるかと思います。ではどうやってコンピュータ上に実現していくかという話になっていくのですが、キーワードは探索と活用です。意味付けでいえば経験を探索、適応を活用と置き換えてみてください。問題を探索しその結果を活用するという流れが強化学習ということです。
多椀バンディッド
TD学習やQ学習の方が強化学習としてはメジャーなのですが、ABテストといえば多椀バンディッドアルゴリズムがよく比較されるということで、今回はこの多椀バンディッドについて解説していきます。なぜABテストかって言うと弊社プロダクトで提供してるからです。（ちなみに後述の強化学習も実装済みです）
問題設定
簡単に言うと以下のような問題があった時にどう効率よく攻略するかということになります。
- 複数台のスロットを独占して回す時に報酬を最大化したい
- 回せる回数には限りがある
- スロット毎に当たり期待値が異なるため期待値の高い台を多く回したい
期待値の高い台を探しながら報酬を最大にするにはどうすればよいかということになります。探索のためには台を評価しないといけないため、問題を解くには各台のその時の評価が重要ということになります。
以下が基本的な強化学習の流れになります。
- 台の評価
- 探索：いろんな台を試す
- 活用：良かった台を回す
探索と活用は同時だったり、片方だけ実行されたりします。
台の評価
期待値をそのまま使うのが一番簡単な方法になりますが問題を解くアルゴリズムに応じて評価方法が異なります。事項で簡単にですが解説します。
探索と活用
以下のアルゴリズムが一般的によく知られています。基本的にはどの台を回すかを決定するアルゴリズムです。
- ε-greedy
- softmax
- UBC(Upper Confidence Bounds)
- Thompson Sampling
ε-greedy
εの確率で探索を行いそれ以外で活用を行います。探索時は選択肢を同じ確率としてランダムに決定するのが一般的です。εを施行回数に応じて100から0にしていくことで台を固定させることができますがあまり一般的な方法ではありません。探索時の確率がこれまでの試行を無視して一定のため、探索時の活用が他の手法に比べ劣ります。
特殊なケースとしてε = 100%をABテストとみなすことができます。
softmax
評価から台の選択確率を計算して台を選択します。n台のうちiが選択される確率は以下のように計算されます。確率で台が選択されるため探索と活用を同時に行います。
\frac{exp(r_i/\tau)}{\sum_{k=1}^{n}exp(r_k/\tau)}
\\r_i は台iの期待値
パラメータ(τ)に応じて確率計算時の確率が異なります。τが小さければ小さいほどより期待値の高いものが選択されやすくなります。εと同様にτを0に近づけることによって台を固定することが可能です。
UCB
各台を以下の式で評価します。全試行回数（totalCount）に比べて、試行回数（count）が少ない台の評価が高くなるため選択されやすくなります。期待値部分が活用で回数考慮の部分が探索になります。
r_i + \frac{\sqrt{2log(totalCount)}}{count_i}
実行回数が増えていくと台が固定化されていきます。
Thompson Sampling
試行回数を報酬からβ分布に従った確率分布を求め、確率分布に従ったサンプリングによって確率的に評価をし回す台を決定します。同じ状態であってもランダムで評価が変化するため探索と活用を同時に行います。試行回数が増えていくことによって選択される台は固定されていきます。
多椀バンディッド問題まとめ
多椀バンディッド問題を例に、強化学習で用いられる手法について簡単に解説してみました。どの手法にも言えることですが、どのように正しい評価に効率よく近づけるかというのを考えて設計されています。ただし、必ずしも1番良い台に固定されることは保証されていません。2番目3番目に固定されていくことも原理的にはあり得ます。そのことも良し悪しで、全体の報酬を良くするという意味では探索を早めに切り上げてその時に1番良いと思うものだけを実行するとというのも大事な戦略です。
おわりに
強化学習を多椀バンディッドを例に簡単に解説してみました。結局そんな大したことしてないなとか思っていただけると幸いです。