NLP若手の会シンポジウム2012招待講演 鶴岡先生による「自然言語処理とAI」
-
- いいね！2
Daisuke Okanohara / 岡野原 大輔
@hillbig
鶴岡先生 http://t.co/yZj9UjWd による招待講演、「自然言語処理とAI」がはじまりました。鶴岡先生はNLPの研究者と同時に過去4度コンピュータ将棋世界大会を優勝した"激指"の開発者としても知られています。私のNLP, 機械学習の師でもあります #yans
2012-09-04 10:05:09
Mamoru B Komachi
@mamoruk
自然言語処理とゲームAIはいとこのような関係。現実問題は難しいので、解空間の狭いところでAI研究のテストベッドとして使われる。探索と学習と最適化。#yans
2012-09-04 10:08:38
Daisuke Okanohara / 岡野原 大輔
@hillbig
近年のブレークスルー チェス・将棋：comparison training 評価関数の自動学習 囲碁 Monte-carlo Tree Search：評価関数が不要に ポーカー：Counterfactual Regret Minimization ナッシュ均衡解の計算 #yans
2012-09-04 10:09:13
Mamoru B Komachi
@mamoruk
ゲームAIの進化1。Comparison training (Tesauro 2001)。エキスパートの棋譜、たとえばプロ棋士の棋譜から学習。チェスではそこそこの効果だったが、コンピュータ将棋では絶大な効果があった。いわゆる Bonanzaメソッド。#yans
2012-09-04 10:10:41
Mamoru B Komachi
@mamoruk
ゲームで使われているミニマックス探索。相手が最善の手を指すと仮定。60年間ずっと使われている。難しいのは、評価関数を決めるところ。局面の特徴量選択と重みの設定。昔は数百個の重みを全部手調整！序盤のぼやっとしたところが扱いきれなかったのが常識だった。#yans
2012-09-04 10:14:46
Daisuke Okanohara / 岡野原 大輔
@hillbig
評価関数（局面の良さ）を設計するためには線形モデルを使う、局面の特徴とそれらの重みの設定が必要。昔は職人芸で設定してたが序盤の良さをうまく評価することが困難であった。評価関数の設定は探索がなければ通常の多クラス分類, 構造学習でできるが、実際は先読みがあるので面倒 #yans
2012-09-04 10:17:22
Mamoru B Komachi
@mamoruk
探索 (先読み) がなければ多クラス分類で、NLPと同じ。SVMだろうがなんでもよい。ただ、プロ棋士はどう指しているか？先先まで読んだ局面の評価値で指し手を決めているはず。やってみたところ、劇的にうまく動いた (保木 2006)。 限界かと思っていたところを超えた。#yans
2012-09-04 10:19:40
Daisuke Okanohara / 岡野原 大輔
@hillbig
先読み+学習で、数手先の評価関数の調整を学習で行う、2006年ごろbonanzaに導入されて以来、レーティングはあがりつづける。http://t.co/8RMpcXe5 今レーティングを見る限り、コンピューター将棋に勝てるのは羽生さん、渡辺さんぐらいでは #yans
2012-09-04 10:21:47
Mamoru B Komachi
@mamoruk
NLP的な手法がゲームAIでも通用したので、逆にゲームAI的な手法をNLPに適用した。履歴に基づく解析で、現在までの履歴だけを使うのではなく、解析の先読みを使うとどんどん品詞付与精度がよくなる (Tsuruoka et al. 2011)。他のタスクにも適用可能。#yans
2012-09-04 10:22:57
Daisuke Okanohara / 岡野原 大輔
@hillbig
モンテカルロ木探索（MTCS）は囲碁で大成功した後に、プランニング、制御、最適化問題への応用が進む。ドメイン知識が不要、評価関数が不要。囲碁は評価関数の設計が難しくコンピュータ囲碁は初段手前で停滞していた． 06年にMCTSが登場し、一気に強くなった #yans
2012-09-04 10:27:57
Mamoru B Komachi
@mamoruk
ゲームAIの進化2。モンテカルロ木探索 (2006年ごろ)。囲碁で大成功。アマ初段程度からアマトップクラスに到達。コンピュータ将棋で必要だった、評価関数の設計のような分野知識が不要。囲碁は合法手が多く、評価関数の設計が難しかったため、停滞していたところにブレイクスルー。#yans
2012-09-04 10:28:53
Mamoru B Komachi
@mamoruk
原始モンテカルロ法は見込みのない手も読んでいたので非効率だった。これを解決したのが多腕バンディット問題。どのスロットマシンにお金を注ぎ込むべきか？儲かるマシンにだけ注ぎ込みたい。でも儲かるマシンを見つけるために、いろんなマシンを試したい。この問題はすでに解かれていた。#yans
2012-09-04 10:34:24
Daisuke Okanohara / 岡野原 大輔
@hillbig
原始モンテカルロ法（各合法手からランダムプレイ、勝率の一番高い手を選ぶ）で手を決めるのはダメな手も多く試行するので効率悪．多腕バンディット問題（利用と探索のトレードオフ）と考えられるので、今問題でRegretが小さくて計算量も現実的なUCBと呼ばれる手法を利用する．#yans
2012-09-04 10:37:38
Daisuke Okanohara / 岡野原 大輔
@hillbig
UCBは、手aのUCB値を"aの平均報酬 + (2 ln n / n_a) ^ {1/2} "とし、UCB値が大きいものを選択するようにする．n_aはaの手の試行回数、nは全体の試行回数．有望な手、試行回数が少ない手を優先して試行．#yans
2012-09-04 10:40:42
Mamoru B Komachi
@mamoruk
多腕バンディット問題の解法 (UCB) に従ってモンテカルロ木探索をすると、有望な手に多くの試行が可能。しかし、まだこれだけでは強くならない。なぜか？相手を考慮せず、指し手を選ぶから。この解決が ECML 2006。UCBを各ノードで適用。理論的にもminmaxに収束。#yans
2012-09-04 10:44:12
いっくん
@ikkn
なんで @mamoruk さんが囲碁の話をしているんだろうと思っていたら、つるおかさんかー。囲碁クラスタに入ったのかと思った。 #yans #やんず
2012-09-04 10:45:29
Daisuke Okanohara / 岡野原 大輔
@hillbig
UCBは2手目以降のプレイアウトに無駄が多い．UCT（UCB applied to trees）は探索木の各ノードにUCBを適用し、最適な枝を選ぶ．minmax値に収束保証．探索木を各節店のUCB値に従い辿りながら、たまに候補を伸ばす．いつ伸ばすかで亜種がいろいろ．#yans
2012-09-04 10:47:28
Mamoru B Komachi
@mamoruk
囲碁では合法手が多いので、モンテカルロ木探索にもいろいろな亜種がある。囲碁に関する様々なヒューリスティックスを反映している。局所パターンを使ったり、評価関数の設計が難しいのを回避できるとはいえ、分野知識が不要というわけではない。#yans
2012-09-04 10:51:08
Mamoru B Komachi
@mamoruk
あと、Simulation balancing (Silver and Tessauro, ICML 2009) という手法は、プロ棋士の指し手をそのまま教師データに使うのではなく、プレイアウトの結果の期待値がプロ棋士の指し手に一致するよう学習する。#yans
2012-09-04 10:53:10
Yuya Unno
@unnonouno
このグラフ本当にすごい。同期の荒木くんが囲碁やってたのが2007年。当時でもアマチュア段持ち程度だったと記憶してる #yans
2012-09-04 10:53:29