編集可能
2012年9月4日

NLP若手の会シンポジウム2012招待講演 鶴岡先生による「自然言語処理とAI」

2012年 NLP (自然言語処理) 若手の会シンポジウムにおける鶴岡慶雅先生による「自然言語処理と AI」の講演内容のまとめです。 アブストラクト 自然言語処理は、知的なシステムの実現を目指すという点で人工知能(AI)と深いかかわりを持っているが、両研究分野の交流は意外なほどに少ない。 続きを読む
9
Mamoru Komachi @mamoruk

今日は鶴岡さんの招待講演ですね。楽しみ!#yans

2012-09-04 08:07:10
Daisuke Okanohara @hillbig

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

2012-09-04 10:05:09
Yuya Unno @unnonouno

今日は鶴岡さんのゲームAIの話! #yans

2012-09-04 10:05:13
Mamoru 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 Komachi @mamoruk

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

2012-09-04 10:10:41
Mamoru Komachi @mamoruk

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

2012-09-04 10:14:46
Daisuke Okanohara @hillbig

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

2012-09-04 10:17:22
Mamoru 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 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 Komachi @mamoruk

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

2012-09-04 10:28:53
柳瀬徹 @cockeye246

面白い人にはめちゃくちゃ面白いこのハッシュタグ。 #yans

2012-09-04 10:33:32
Mamoru Komachi @mamoruk

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

2012-09-04 10:34:24
Daisuke Okanohara @hillbig

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

2012-09-04 10:37:38
nushio @nushio

@mamoruk N腕バンディット問題がそこで噛んでいたのか

2012-09-04 10:38:22
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 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 Komachi @mamoruk

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

2012-09-04 10:51:08
Mamoru 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
残りを読む(19)

コメント

コメントがまだありません。感想を最初に伝えてみませんか?