「自然言語処理とAI」

NLP若手の会 (YANS) @yans_official

鶴岡先生による招待講演の資料をアップロードしました！ http://t.co/zZXIIZSh #yans ウェブサイトからダウンロードできます。貴重な資料と思いますので、ぜひご覧ください！

Daisuke Okanohara / 岡野原 大輔 @hillbig

鶴岡先生 http://t.co/yZj9UjWd による招待講演、「自然言語処理とAI」がはじまりました。鶴岡先生はNLPの研究者と同時に過去4度コンピュータ将棋世界大会を優勝した"激指"の開発者としても知られています。私のNLP, 機械学習の師でもあります #yans

Mamoru B Komachi @mamoruk

自然言語処理とゲームAIはいとこのような関係。現実問題は難しいので、解空間の狭いところでAI研究のテストベッドとして使われる。探索と学習と最適化。#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

近年のブレークスルー チェス・将棋：comparison training 評価関数の自動学習 囲碁 Monte-carlo Tree Search：評価関数が不要に ポーカー：Counterfactual Regret Minimization ナッシュ均衡解の計算 #yans

Mamoru B Komachi @mamoruk

ゲームAIの進化1。Comparison training (Tesauro 2001)。エキスパートの棋譜、たとえばプロ棋士の棋譜から学習。チェスではそこそこの効果だったが、コンピュータ将棋では絶大な効果があった。いわゆる Bonanzaメソッド。#yans

Mamoru B Komachi @mamoruk

ゲームで使われているミニマックス探索。相手が最善の手を指すと仮定。60年間ずっと使われている。難しいのは、評価関数を決めるところ。局面の特徴量選択と重みの設定。昔は数百個の重みを全部手調整！序盤のぼやっとしたところが扱いきれなかったのが常識だった。#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

評価関数（局面の良さ）を設計するためには線形モデルを使う、局面の特徴とそれらの重みの設定が必要。昔は職人芸で設定してたが序盤の良さをうまく評価することが困難であった。評価関数の設定は探索がなければ通常の多クラス分類, 構造学習でできるが、実際は先読みがあるので面倒　#yans

Mamoru B Komachi @mamoruk

探索 (先読み) がなければ多クラス分類で、NLPと同じ。SVMだろうがなんでもよい。ただ、プロ棋士はどう指しているか？先先まで読んだ局面の評価値で指し手を決めているはず。やってみたところ、劇的にうまく動いた (保木 2006)。 限界かと思っていたところを超えた。#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

先読み+学習で、数手先の評価関数の調整を学習で行う、2006年ごろbonanzaに導入されて以来、レーティングはあがりつづける。http://t.co/8RMpcXe5 今レーティングを見る限り、コンピューター将棋に勝てるのは羽生さん、渡辺さんぐらいでは　#yans

Mamoru B Komachi @mamoruk

NLP的な手法がゲームAIでも通用したので、逆にゲームAI的な手法をNLPに適用した。履歴に基づく解析で、現在までの履歴だけを使うのではなく、解析の先読みを使うとどんどん品詞付与精度がよくなる (Tsuruoka et al. 2011)。他のタスクにも適用可能。#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

モンテカルロ木探索（MTCS）は囲碁で大成功した後に、プランニング、制御、最適化問題への応用が進む。ドメイン知識が不要、評価関数が不要。囲碁は評価関数の設計が難しくコンピュータ囲碁は初段手前で停滞していた． 06年にMCTSが登場し、一気に強くなった　#yans

Mamoru B Komachi @mamoruk

ゲームAIの進化2。モンテカルロ木探索 (2006年ごろ)。囲碁で大成功。アマ初段程度からアマトップクラスに到達。コンピュータ将棋で必要だった、評価関数の設計のような分野知識が不要。囲碁は合法手が多く、評価関数の設計が難しかったため、停滞していたところにブレイクスルー。#yans

Mamoru B Komachi @mamoruk

原始モンテカルロ法は見込みのない手も読んでいたので非効率だった。これを解決したのが多腕バンディット問題。どのスロットマシンにお金を注ぎ込むべきか？儲かるマシンにだけ注ぎ込みたい。でも儲かるマシンを見つけるために、いろんなマシンを試したい。この問題はすでに解かれていた。#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

原始モンテカルロ法（各合法手からランダムプレイ、勝率の一番高い手を選ぶ）で手を決めるのはダメな手も多く試行するので効率悪．多腕バンディット問題（利用と探索のトレードオフ）と考えられるので、今問題でRegretが小さくて計算量も現実的なUCBと呼ばれる手法を利用する．#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

UCBは、手aのUCB値を"aの平均報酬 + (2 ln n / n_a) ^ {1/2} "とし、UCB値が大きいものを選択するようにする．n_aはaの手の試行回数、nは全体の試行回数．有望な手、試行回数が少ない手を優先して試行．#yans

Mamoru B Komachi @mamoruk

多腕バンディット問題の解法 (UCB) に従ってモンテカルロ木探索をすると、有望な手に多くの試行が可能。しかし、まだこれだけでは強くならない。なぜか？相手を考慮せず、指し手を選ぶから。この解決が ECML 2006。UCBを各ノードで適用。理論的にもminmaxに収束。#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

UCBは2手目以降のプレイアウトに無駄が多い．UCT（UCB applied to trees）は探索木の各ノードにUCBを適用し、最適な枝を選ぶ．minmax値に収束保証．探索木を各節店のUCB値に従い辿りながら、たまに候補を伸ばす．いつ伸ばすかで亜種がいろいろ．#yans

Mamoru B Komachi @mamoruk

囲碁では合法手が多いので、モンテカルロ木探索にもいろいろな亜種がある。囲碁に関する様々なヒューリスティックスを反映している。局所パターンを使ったり、評価関数の設計が難しいのを回避できるとはいえ、分野知識が不要というわけではない。#yans

Mamoru B Komachi @mamoruk

あと、Simulation balancing (Silver and Tessauro, ICML 2009) という手法は、プロ棋士の指し手をそのまま教師データに使うのではなく、プレイアウトの結果の期待値がプロ棋士の指し手に一致するよう学習する。#yans

Mamoru B Komachi @mamoruk

ゲームAIの進化3。Counterfactual Regret Minimization (Zinkevich et al., NIPS 2007)。これまで解けなかった大規模な不完全情報ゲームのナッシュ均衡を解いた。この手法は、ポーカーで大成功を収め、プロに勝利。#yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

CFR（Counterfactual Regret Minimization）は大規模な不完全情報ゲームのナッシュ均衡を求められ、ポーカープログラムの性能を大幅に向上し、人間の世界チャンピオンに勝利．Texas hold'em http://t.co/2ybBNudy #yans

Daisuke Okanohara / 岡野原 大輔 @hillbig

ナッシュ均衡：どのプレイヤも自分だけが戦略を変更することで得をすることがない状態　例えばグーで買ったら3点, チョキで買ったら2点, パーで買ったら1点の場合のナッシュ均衡の戦略は（意外にも） グー1/3, チョキ 1/6, パー 1/2 #yans

Mamoru B Komachi @mamoruk

ナッシュ均衡求めるのは線形計画問題。持ち札に対して報酬が同じ場合は分かりやすいが、違う場合は直感に反する結果が出ることがある。たとえば理論的には、持ち札が強ければ当然ベットするが、持ち札が弱くてもベットするのが最適解。プロのプレイヤーも実は同じようなことをしている。#yans