終末まであと何マイル? 〜強化学習一発芸!!!〜 RSSフィード

2016/08/26

[]バンディット問題の理論とアルゴリズム 20:27

 届いた。明日読む。

 目次だけ眺めた感じ、LinUCBというのが面白そう(だが、コンピュータ将棋への応用面では可能性は不明)。

トラックバック - http://d.hatena.ne.jp/Gasyou/20160826

2016/08/23

[]これだけ読めば分かる(かもしれない)強化学習コンピュータ将棋13:52

はじめに

 「強化学習 将棋」でググッてこのブログに来て貰う人が時々いますが、そう言えばちゃんとした概要を書いていなかったので、自分の復習がてら書いてみます。

 んで、まず検索すると出てくる二大キーワード。

 これは当面忘れてもらってOKです。つか、これらのせいで強化学習の本質が見えづらい入門記事が散見されます。

概要

 さて、じゃぁ「強化学習とはなんぞや」って話ですが、これは機械学習の一分野です。

 機械学習は大別して「教師あり学習」「強化学習」「教師なし学習」の3種類があります*1

 「教師あり学習」は文字通り「教師」のいる学習方式です。コンピュータ将棋で言えば、Bonanza Methodがこれにあたります。教師がいるので、比較的効率が良く学習可能です。

 「教師なし学習」は反対に「教師」のいない学習方式です。無理やりコンピュータ将棋に応用するなら、クラスタリングとかが出来そうです。「これとこれとこれは似た局面(例えば相矢倉)」「これとこれは別の似た局面(例えば居飛車振り飛車対抗型)」って感じで、似た者同士を分ける感じですね*2

 んで、本命の「強化学習」は、「教師」はいませんが「褒めたり叱ったりする人」のいる学習方式だと思って下さい。

 この「褒める・叱る」というのが、強化学習の文脈で言う「報酬」にあたります。

 「教師」と「報酬」の違いは、「教師」は全ての入力(局面等)に対して正解(指し手や評価値)を与えてくれるのに対して、「報酬」は時間的な遅延やノイズがある事です。

 コンピュータ将棋で素直に「報酬」の与え方を実装すると、「勝ったら+1、負けたら-1、引き分けなら0」になります。(一般的に、強化学習では目的を達成したらプラスの報酬を、出来なければマイナスの報酬を与えます。)

 つまり、「序盤で良い手を指した」直後にプラスの報酬が貰えるとは限りません。また、「終盤まで有利に進めていたのに、頓死して負けた」場合はマイナスの報酬が与えられます。

 強化学習の主体となるモジュールの事を「エージェント」と呼びますが、エージェントの目的は「報酬を最大化する為にはどうすれば良いか、試行錯誤して学習する」事です。

 言い方を変えると、「教師あり学習」では「手段」を「教師信号」として与え、それを模倣するのが学習の目的あるのに対し、「強化学習」では「目的」を「報酬」として与え、「手段」はエージェント自身が考えて決定します。

もうちょっと詳しく(TD法)

 強化学習将棋に応用する場合ですと、自己対局や他のプレイヤー*3との対局を通じて、「こういう局面でこう指せば勝率が高くなるな」というのを自律的に学習してくれます。

 まずは、「局面の良し悪し」を判断する「価値関数」というものを導入します。コンピュータ将棋に詳しい方は「評価関数」と同等のもの、と考えて下さい。

 これを使って、「この局面は何点位有利(不利)なのかな?」と判断します。(これは、一般的には「関数近似を用いた強化学習」になります。)

 次に、点数計算の取っ掛かりとして、さっき出てきた報酬を使います。つまり、「報酬の期待値」を「局面の価値」と見なします。

 例えば「自分が居飛車穴熊で、相手は棒銀に失敗して居玉のまま」だと「(自分から見て)+0.4点位かな*4」とか、そんな感じです。

 じゃぁ、どうやって期待値の計算をするか、ですがこれは実際の対局中の局面の価値と、最終的に得られた報酬から計算します。

 数式を書くと小難しく見えるので、不正確を承知で日本語で書くと「ある局面の価値は、それ以降の局面の価値・報酬に近いはずだ」という推測を元に計算します。

 例えば「終盤で飛車を切って金を取った」とします。で、その次の自分の手番で「頭金で詰んだ」場合を考えます。

 まず、「頭金で詰んだ」局面の価値は、その直後に貰えた報酬と等しいと考えて「+1」に近付けます(近付く様に価値関数のパラメータを修正します)。

 次に、「飛車を切った」局面の価値は、「頭金で詰んだ」局面の価値に近いと考えて、その時の価値に近付けます(同じく、価値関数のパラメータを修正)。

 これを、終局から初手まで遡って計算していくのが、「TD法」と呼ばれる手法です*5

 もちろん、一局だけだと正確に学習出来ませんので、沢山対局して何度もパラメータを修正していけば、どんどん正確な価値関数が出来上がります。

 (ちなみに、コンピュータチェスで提唱されたTDLeaf(λ)は、TD法とαβ探索を組み合わせた手法になっています。)


別の手法(方策勾配法

 前項のTD法は、「正確な価値関数を作る」→「価値関数が正確なので強くなる」という2段構えの手法です。

 これに対して、一発で「強い価値関数を作る」手法が有り、これが「方策勾配法」と呼ばれるものです。(芝浦将棋Jr.チームの五十嵐治一先生と私が共同で提案したPGLeafも、方策勾配法の一種です。)

 こっちは数式を書くと無茶苦茶ややこしく見えるので、将棋の場合に限定して(若干不正確な面もありますが)書いてみます。

 まず、指し手の選択の際に「良さそうな手(≒価値の高い手)ほど高確率で選ぶ」とします。強化学習ではSoftmax戦略(方策)と呼ばれるやり方です。

 次に、対局後に「今回は勝った(プラスの報酬が貰えた)から、本譜の手は良かったんだろう」「今回は負けた(マイナスの報酬を与えられた)から、本譜の手は悪かったんだろう」と推測します。

 そこで、勝った場合は「本譜の手の価値を上げ、それ以外の手の価値を下げる方向」に価値関数のパラメータを修正します。負けた場合は逆に「本譜の手を下げ、それ以外の手を上げる方向」に修正します。

 これも、TD法と同様に、何度も対局してその都度学習して行けば、どんどん「強い価値関数」が出来上がります。


最後に

 え〜、長々と書きましたが、一部(大部分?)不正確な記述が有ります。

 厳密な数式やら証明やらは、専門書にあたるのが手っ取り早いと思いますので、日本語の良書(だと思ってる)を2つ載せておきます。

強化学習

強化学習

 前者はTD法まで、後者は方策勾配法も記載があります。強化学習にどっぷり浸かるつもりなら、両方買っておくのが良いと思います。

 それから、不明瞭な点や分かりづらい部分など有りましたら、コメント頂けると有り難いです。可能な限り追記・修正していくつもりです。

 この記事を読んで強化学習クラスタの一員になって貰えれば、私としてはこれ以上の喜びはありません。

[]Efficient Exploration for Dialog Policy Learning with Deep BBQ Networks & Replay Buffer Spiking 20:30

 http://arxiv.org/pdf/1608.05081.pdf

 DQNの次はBBQらしいですよ!

*1:細かい話をすると、「半教師あり学習」等のホットな分野もありますが、それはとりあえずおいておきます

*2:教師なし学習には他にも色々ある様ですが、私はあまり詳しくないのでこの辺で

*3:人間でもコンピュータでも構いません

*4:報酬の期待値が+0.4なので、勝率としては70%という見込みになります

*5:若干不正確な記述ですが、あくまで概要ですので許して下さい

将棋好き将棋好き 2016/08/24 15:04 初めまして、将棋が好きでプログラミングにも興味があってこちらのブログを拝見させて頂きました。
初歩的な質問で恐縮ですが、こちらで挙げられている「強くなる」とは、「学習で用いた相手に勝ちやすくなる」ことであり、「将棋の必勝法に近づく」ことではないと解釈してもよろしいでしょうか。
それとも、同じ学習方法を取る別のプログラム(または自分自身)との無限回の対局で必勝法に到達することが保証されているのでしょうか。(直観的には教師あり学習?を用いずに局所最適解から抜け出すことが非常に困難に思えます)

GasyouGasyou 2016/08/24 19:25 はじめまして。興味を持ってもらえて嬉しいです。ありがとうございます。

ご質問の件ですが、場合分けして回答させて頂きます。

1. TD(λ)と線形の価値関数の場合
 これは、適切な方策と学習率を用いて無限に試行すれば、「将棋の必勝法に近づく」事が証明されています。

2. TDLeaf(λ)と線形の価値関数の場合
 これは、「TD(λ)と非線形の価値関数の場合」と同義になりますので、「将棋の必勝法に近づく」証明はなされていないはずです。(単に、私が証明を知らないだけ、という可能性もありますが。)

3. 方策勾配法の場合
 局所最適解にはまる可能性がありますので、「学習で用いた相手に勝ちやすくなる」方だと思います。

ご不明な点など有りましたら、追加でご質問頂ければ幸いです。

トラックバック - http://d.hatena.ne.jp/Gasyou/20160823

2016/08/17

[]まだまだまだデータ採取中 18:25

f:id:Gasyou:20160817181855p:image

 以前の先後で評価関数インスタンスを分けた場合のグラフに、先手のみ・後手のみ学習のログを追加したものです。

 んで、先手のみ学習の結果が異常に良いのが気になりますね。

 一旦勝率上がってから下がるのは、ベースラインの設定をしていないのが原因かもしれないので、現在はそこを修正したバージョンを走らせています。

 どういう事かというと、「ssp相手だと大体これ位の報酬が得られる」という値がベースラインで、パラメータ修正時は「報酬-ベースライン」を基準にパラメータ修正量を決めるのが良いらしいです。

 つまり、勝率9割の相手なら「報酬が+1」と「報酬が-1」はパラメータ修正量の絶対値が異なるはずです。(前者の方が、パラメータ修正量が小さくなるべき。)

 ただ、同じ設定で何回か走らせても、その都度結果が異なるので、一回の結果だけから判断するのも難しそうな感じです。

 …困った。

[]ここらで問題点を整理しとこう 19:10

  1. 先手と後手で共通の評価関数を使うと、何故か学習が上手く行かない。
  2. ssp勝率が、一旦9割を超えてから下がる現象が時々ある。
  3. ssp勝率が不安定(学習するたびに異なる)。

 …問題点だらけだな、こりゃ。

トラックバック - http://d.hatena.ne.jp/Gasyou/20160817

2016/08/15

[]まだまだデータ採取中 21:42

 先手と後手で評価関数インスタンスを分けて、別個に学習した結果です。

 まず、正則化無し・開発用マシンで実行。

f:id:Gasyou:20160815213717p:image

 次に、正則化有り・学習用マシンで実行。

f:id:Gasyou:20160815213718p:image

 正則化有りの方は何か結果が変ですが、とりあえずは無視して上の正則化無しの結果だけ検証。

 後手の勝率が一旦上がってから下がる現象が起きていますが、勝率は先後ともちゃんと上昇しています。

 という訳で、今度は先手のみ・後手のみの学習をさせてみて、それで同じ結果になるか検証してみます。

 例によって、結果は明日朝以降です。

トラックバック - http://d.hatena.ne.jp/Gasyou/20160815

2016/08/14

[]データ採取、少しだけ完了 17:47

 GA将対ssp勝率の推移です。「通算」とあるのが先手・後手トータルでの勝率で、後は先手だけ・後手だけの値。

 まず、正則化無し、開発用マシンで実行。

f:id:Gasyou:20160814173858p:image

 次に、正則化係数1E-4、学習用マシンで実行。

f:id:Gasyou:20160814173859p:image

 上は後手だけ、下は先手だけ勝率が高いです。

 んで、この事から「後手(あるいは先手)の学習ルーチンにバグが有る」という可能性は低いです。(仮にそうなら、両方共後手の勝率が低くなるはず。)

 という訳で、もう一つの可能性として「評価関数のキャパシティ不足」が考えられますが、三駒関係+αだからその可能性も低そうです。

 …低そうですが、本当にそうなのか実証出来ていないので、先手と後手で評価関数インスタンスを別にして学習させてみます。

 結果が出るのは、早くとも明日朝だと思われます。

トラックバック - http://d.hatena.ne.jp/Gasyou/20160814