ディープラーニングとツリー探索によるゼロからの高速学習と低速学習

[[211446]]

この記事では、ロンドン大学ユニバーシティ・カレッジ (UCL) の Thomas Anthony、Zheng Tian、David Barber によるディープラーニングとツリー検索の研究を紹介します。この論文はNIPS 2017カンファレンスに採択されました。

二重処理理論

「二重処理メカニズム」は、人間の推論には 2 つの異なるタイプの思考が関与していると主張します。下の図に示すように、システム 1 は高速で無意識の自動思考モードであり、直感とも呼ばれます。システム 2 は、ゆっくりとした、意識的な、明示的な、ルールに基づいた推論モードであり、進化的に最近発達したと考えられています。

画像ソース: https://www.slideshare.net/AshDonaldson/behaviour-design-predicting-irrational-decisions

難しい計画タスク（ボードゲームなど）を完了する方法を学習するとき、人間は両方の処理スタイルを同時に使用します。正確な直感により、好ましいルートをすばやく選択できるため、より遅い分析的推論がより効率的になります。継続的な詳細な学習により、直感が徐々に向上し、より正確な直感をより強力な分析にフィードバックして、閉じた学習ループを形成できます。言い換えれば、人間は速く考えることとゆっくり考えることの両方によって学習するのです[1]。

現在の深層強化学習の問題点は何ですか?

現在の深層強化学習アルゴリズム、例えばPolicy GradientやDQN3[3]では、ニューラルネットワークは行動を選択する際に先見性を持っておらず、これはシステム1に似ています。人間の直感とは異なり、これらの強化学習アルゴリズムには、トレーニング プロセス中に優れた戦略を推奨する「システム 2」がありません。

AlphaGoなどのAIアルゴリズムの限界の1つは、プロの人間プレイヤーのデータベースを使用することです[4]。トレーニングの初期段階では、強化学習エージェントは人間の専門家の行動を模倣します。そして、この初期段階を経た後で初めて、エージェントはより強力な超人的なプレイを学習し始める可能性があります。しかし、そのようなアルゴリズムは、特定の人間プレイヤーのスタイルに大きく偏り、潜在的に優れた戦略を無視する可能性があるため、ある意味では不十分です。同時に、ゲームの分野では人間の専門家のデータベースが利用できるかもしれませんが、他の状況で AI マシンをトレーニングしたい場合、そのようなデータベースが利用できない可能性があります。したがって、最先端のボードゲームプレイヤーをゼロからトレーニングすることは、AI にとって大きな課題です。

エキスパートイテレーション（ExIt）

Expert Iteration (ExIt) は、2017 年 5 月に導入された一般的な学習フレームワークです。人間の戦略を模倣することなく、強力な AI マシンをトレーニングできます。

ExIt は模倣学習の拡張版と見なすことができ、人間のトップエキスパートでも満足のいくパフォーマンスを達成できない領域にまで拡張できます。標準的な模倣学習では、見習いは専門家の行動を模倣するように訓練されます。 ExIt はこのアプローチを反復学習プロセスに拡張します。各反復では、エキスパート改善ステップを実行し、（高速な）見習い戦略を利用して（比較的低速な）エキスパートのパフォーマンスを改善します。

出口

チェスなどのボードゲームは、この概念をより直感的に理解するのに役立つかもしれません。このタイプのゲームでは、熟練者はスローチェス（各動きを決めるのに多くの時間を費やす）をプレイするチェスプレイヤーのようであり、一方、見習いはファストチェス（各動きを決めるのにほとんど時間を費やさない）をプレイするプレイヤーのようです。

別の研究では、プレイヤーは同じポジションで複数の可能な行動を考慮し、それぞれの可能な動きについて深く（そしてゆっくりと）考えていることが示されました。彼女は現在のポジションでどの動きが成功し、どの動きが失敗するかを分析します。将来、同様のチェスのゲームに遭遇したとき、彼女はこれまでの研究で培った直感によって、どの動きがより良いかをすぐに知ることになるでしょう。こうすることで、彼女は速いチェスの状況でも良いパフォーマンスを発揮することができます。彼女の直感は、深い思考と計算を通じて獲得した強力な戦略を模倣することから生まれます。人間がただ速くチェスをプレイするだけでは優れたチェスプレイヤーになることは不可能であり、より深い研究が学習プロセスの重要な部分です。

AI ゲームをプレイするマシンの場合、たとえば、別の「マシンの専門家」が行った特定の動きに合わせてニューラル ネットワークを適合させることで、この種の模倣が可能になります。弟子は、専門家がこれまでに見てきた行動を真似することで、短期間で素早いチェス戦略を学ぶことができます。ここで重要な点は、ゲームの背後に基礎となる構造があると仮定すると、機械学習によって、見習いたちが直感をこれまで見たことのない状況に一般化し、迅速な意思決定を行えるようになるということです。つまり、弟子は、専門家の動きに関する有限で固定されたデータベースから動きの参照テーブルを単に作成するのではなく、学習した内容を他のゲーム状態に一般化することができます。つまり、ニューラル ネットワークは、熟練したプレイヤーの一般化と模倣の両方において役割を果たします。

弟子がこれまでに見た専門家の行動をすべて模倣することで素早い意思決定を学んだと仮定すると、専門家はその意思決定を活用できるようになります。専門家が行動を起こしたい場合、弟子はすぐにいくつかの代替行動を提案し、専門家はそれを深く検討します。そしておそらく、このゆっくりとした思考プロセスの間、専門家は弟子の鋭い直感に導かれ続けるでしょう。

この段階の終わりに、専門家は弟子の助けを借りていくつかの行動をとり、各行動は、専門家単独または弟子単独がとった場合よりも一般的に優れたものになります。

次に、弟子が（新しい）専門家によって推奨された行動を再び模倣することから始めて、上記のプロセスを繰り返すことができます。これにより、学習フェーズの 1 つの完全な反復が実行され、見習いが収束するまで継続されます。

バイナリ処理メカニズムの観点から見ると、模倣学習ステップは、人間が例題を研究することで直感を向上させることに似ており、専門家の改善ステップは、人間が向上した直感を使用して将来の分析を導くことに似ています。

ツリー探索とディープラーニング

ExIt は、見習いおよび専門家によってさまざまな形で具体化できる一般的な学習戦略です。ボードゲームでは、モンテカルロ木探索は強力なゲーム戦略[6]であり、専門家の役割に最適な候補です。ディープラーニングは強いプレイヤーを模倣するための効果的なアプローチであることが示されており[4]、私たちはそれを弟子として使います。

エキスパートの改善フェーズでは、見習いを使用してモンテカルロ ツリー検索アルゴリズムをより有望な方向に動作するように誘導し、ゲーム ツリー検索の幅と深さを効果的に削減します。このようにして、模倣学習で得た知識を計画アルゴリズムにフィードバックすることができます。

ボードゲーム HEX

Hex は、プレイヤーが n×n の六角形のグリッド上で競い合う、古典的な 2 人用ボード ゲームです。プレイヤーは黒と白に分かれ、空いているマスに自分の色の駒を交互に置きます。南から北まで黒の駒が一列に繋がっている場合は、黒側が勝ちます。東から西に白い駒が一列に繋がっている場合、白のプレイヤーが勝ちます。

5×5 六角形のチェス盤の例

上記は白が勝つ 5×5 のチェス盤です。 Hex は戦略が奥深く、機械にとっては非常に難しいゲームです。また、膨大な数の動きと接続ルールがあるため、囲碁と同じように人工知能にとっても課題となります。しかし、囲碁に比べるとルールは単純で、引き分けはありません。

Hexのルールは単純なので、数学的解析手法が非常に適しています。現在最も優れたマシンプレイヤーであるMoHex[7]は、モンテカルロ木探索と巧妙な数学的アイデアを使用しています。 2009 年以来、MoHex は Computer Gaming Olympiad Hex 大会ですべて優勝しています。 MoHex がロールアウト ポリシーのトレーニングに人間の専門家のデータベースを使用していることは注目に値します。

ExIt トレーニング戦略が、専門知識や人間の専門家のチェス記録 (ゲーム ルールを除く) を使用せずに、MoHex を上回る AI プレーヤーをトレーニングできるかどうかを確認しましょう。この目的のために、モンテカルロ ツリー探索をエキスパートとして使用し、見習いニューラル ネットワークがエキスパートをリードします。私たちのニューラルネットワークは、白と黒の2つの出力ポリシーを持つ深層畳み込みニューラルネットワークの形をしています（詳細については[5]を参照）。

修正されたモンテカルロ木探索式は、専門家の改善を達成できます。

ここで、s はチェスゲームの状態であり、a は状態 s で実行できるアクションです。 UCT(s,a)はモンテカルロ木探索[6]で使用される木の古典的な信頼上限であり、追加された項はニューラルネットワークの弟子が専門家により良い行動を探すよう導くのに役立ちます。ここで、π̂ は見習いの戦略（状態 s における各潜在的なアクション a の相対的な利点）、n(s,a) はアクション a を実行するために探索アルゴリズムが状態 s に現在訪問した回数、w は専門家の遅い思考と見習いの速い思考のバランスをとるために経験的に選択された重み係数です。この追加により、ニューラル ネットワークの見習いは、より有望なアクションを検索に導き、不適切なアクションをより迅速に拒否できるようになります。

各模倣学習段階で見習いをトレーニングするためのデータを生成するために、バッチ方式では毎回データを再生成し、以前の反復で生成されたすべてのデータを破棄します。そのため、最近生成された限られたデータのみを保持するオンライン バージョンと、すべてのデータを保持するが、最強のプレイに対応する最近のエキスパートによって指数関数的に増加するオンライン バージョンも検討しました。下の図では、トレーニング時間の観点から各学習戦略ネットワークの強度を測定する（ELO スコアを測定）さまざまな方法を比較しています。

また、より伝統的な強化学習アプローチのみを使用して、自己プレイ（つまり、モンテカルロ木探索を使用せずに）でポリシーπ̂(a|s)を学習した結果も示します。これはまさに AlphaGo がポリシー ネットワークをトレーニングするために使用する方法です。上の図の結果は、ExIt トレーニング方法が従来の方法よりも効率的であることを証明しています。この例では、トレーニングがまだ完全に収束しておらず、十分なトレーニング時間があれば、見習いはさらに能力を向上させることができることに注目すべきです。

私たちの論文[5]では、チェスプレイヤーのパフォーマンスを向上させることができる別のメカニズム、つまり、弟子が一人でプレイしているときに勝つ確率を推定できるようにする価値ネットワークVπ̂(s)も使用しています。ポリシー ネットワークとバリュー ネットワークを組み合わせることで、最終的な見習い支援型 MCTS プレーヤーをガイドできます。政策ネットワークと価値ネットワークは、(1)に似た方程式を使用して最終的なMCTSプレイヤーを導きますが、この方程式は状態sにおける見習いの価値を含めるように修正されています。 （詳細は[5]を参照）

最終的な MCTS プレーヤーは、9X9 ゲームで 75% の勝率を達成し、最も有名な Hex マシン プレーヤーである MoHex を上回りました。トレーニングが完全に収束しなかったことを考慮すると、これはさらに注目すべき結果です。 [9]は、最先端のMoHexプレイヤーに対してExItトレーニングゲームを使用するゲーミングボットの例を示しています。同じ状態から開始する場合に、さまざまなアルゴリズムがどのように機能するかを比較しました。さらに多くの例は論文[5]に記載されている。

ExIt (黒) VS MoHex (白)

MoHex (黒) VS ExIt (白)

ExIt がなぜこれほど成功しているのでしょうか?

模倣学習は一般的に強化学習よりも簡単であるため、EXIT は REINFORCE のようなモデルフリー アルゴリズムよりも成功します。

さらに、検索中に他の選択肢に比べて不利にならないアクションのみが MCTS によって推奨されます。したがって、MCTS の選択は、ほとんどの潜在的な対戦相手の選択よりも優れていることになります。対照的に、通常のセルフプレイ（ネットワーク自体が対戦相手の役割を果たす）では、現在の唯一の対戦相手を倒すことに基づいてアクションが推奨されます（そのため、トレーニングを受けたプレイヤーは、現在の最適でない対戦相手に過剰適合する可能性があります）。これが、EXIT (MCTS をエキスパートとして使用した場合) が非常に成功している主な要因であると考えています。つまり、見習いが幅広い対戦相手に対して優れたパフォーマンスを発揮するという事実です。

ALPHAGO ZEROとの関係

AlphaGo Zero[10]（私たちの研究[11]の数か月後に発表）もExItスタイルのアルゴリズムを実装し、人間のプレイヤーの記録を一切使用せずに囲碁で最先端のパフォーマンスを達成できることを実証しました。詳細な比較は論文[5]に記載されている。

要約する

反復エキスパートトレーニングは、人間の思考のバイナリ処理メカニズムの理論にヒントを得た新しい強化学習アルゴリズムです。 ExIt は強化学習を一般化と計画という 2 つの独立したサブ問題に分解します。強力な戦略が見つかったら、具体的な分析と一般化に基づいて計画が実行されます。これにより、エージェントは長期的な計画を立て、より速く学習できるようになり、困難な問題でも高いレベルのパフォーマンスを達成できるようになります。このトレーニング戦略は、チェスやカードゲームの AI プレイヤーにとって非常に強力であり、人間の専門家のチェスの記録がなくても、現在の最高のパフォーマンスを達成できます。