NLP若手の会シンポジウム2012招待講演 鶴岡先生による「自然言語処理とAI」
-
- いいね！2
Mamoru B Komachi
@mamoruk
ゲームAIの進化3。Counterfactual Regret Minimization (Zinkevich et al., NIPS 2007)。これまで解けなかった大規模な不完全情報ゲームのナッシュ均衡を解いた。この手法は、ポーカーで大成功を収め、プロに勝利。#yans
2012-09-04 10:59:07
Daisuke Okanohara / 岡野原 大輔
@hillbig
CFR（Counterfactual Regret Minimization）は大規模な不完全情報ゲームのナッシュ均衡を求められ、ポーカープログラムの性能を大幅に向上し、人間の世界チャンピオンに勝利．Texas hold'em http://t.co/2ybBNudy #yans
2012-09-04 10:59:51
Daisuke Okanohara / 岡野原 大輔
@hillbig
ナッシュ均衡：どのプレイヤも自分だけが戦略を変更することで得をすることがない状態 例えばグーで買ったら3点, チョキで買ったら2点, パーで買ったら1点の場合のナッシュ均衡の戦略は（意外にも） グー1/3, チョキ 1/6, パー 1/2 #yans
2012-09-04 11:05:51
Mamoru B Komachi
@mamoruk
ナッシュ均衡求めるのは線形計画問題。持ち札に対して報酬が同じ場合は分かりやすいが、違う場合は直感に反する結果が出ることがある。たとえば理論的には、持ち札が強ければ当然ベットするが、持ち札が弱くてもベットするのが最適解。プロのプレイヤーも実は同じようなことをしている。#yans
2012-09-04 11:11:06
Daisuke Okanohara / 岡野原 大輔
@hillbig
ナッシュ均衡戦略ではブラフといったことも最適戦略としてでてくる．しかし現実的なポーカーの問題のナッシュ均衡を線形計画法で求めるのは9億行 x 9億列で相当厳しいのがこれまで． #yans
2012-09-04 11:18:05
Daisuke Okanohara / 岡野原 大輔
@hillbig
CFRはregret最小化にしたものの平均戦略がナッシュ均衡であることと、情報集合毎にregret matchingを行って最適化したものが全体のregretと関係していることを利用．実装はすごく簡単でポーカー世界チャンピオンにも勝った #yans
2012-09-04 11:21:31
Mamoru B Komachi
@mamoruk
これらのゲームAIでNLPでも使えるものはないだろうか？先読みは (Tsuruoka et al., CoNLL 2011) で、モンテカルロ木探索は2011年ころから使われてきている。今後もっと使われておかしくない。#yans
2012-09-04 11:22:24
Jiro Nishitoba
@jnishi
@mamoruk @hillbig あら、ナッシュ均衡を求めるのはもっと線形計画問題よりも難しいと思っていたんですが、ゲームの形が特殊なんですかね。
2012-09-04 11:22:58
Daisuke Okanohara / 岡野原 大輔
@hillbig
ゲームにおいては速度は力 計算パワーの向上＝性能向上 賢いコンピューター ゲームの問題設定は数学的な解を求めることで人で超えるというのは当然．しかし、NLPの場合の多くのタスクはアノテーションと同じ出力を出すことがゴールとなっており、ゴールが最善の解と違う可能性も #yans
2012-09-04 11:23:50
Mamoru B Komachi
@mamoruk
ゲームAIとNLPとの違いは？ゲームAIは速度が力。ゲームは数学的な解を求めたいので、計算パワーが向上すれば厳密解に近づき、性能は上がる。NLPは人手のアノテーションの再現が目標で、計算パワーの向上で性能が上がるのはある程度まで。#yans
2012-09-04 11:25:24
Jiro Nishitoba
@jnishi
@mamoruk @hillbig 一般的に(双行列ゲーム)はナッシュ均衡を求める問題が多項式時間でできるとP=NPになりますので。 http://t.co/HZtEsvH1
2012-09-04 11:30:16
Mamoru B Komachi
@mamoruk
最近のゲームAIの進歩は力技によるところが大きい。人間ができない全探索や特徴量の全展開などの力技を機械に任せるような手法が、ゲームでもNLPでも成功を収めるのではないか。#yans
2012-09-04 11:31:50
Mamoru B Komachi
@mamoruk
鶴岡さん、NLP (自然言語処理)若手の会シンポジウムでの招待講演、ありがとうございました！(((o(*ﾟ▽ﾟ*)o))) 参加者のみなさん、午後は国際会議参加報告と、ポスター発表2です。午後もよろしくお願いします！#yans
2012-09-04 11:34:39
しましま
@shima__shima
.@mamoruk モンテカルロ自体の利用はNLPの方が先を行っているかと．将棋みたいに時間制限があるとバンディットで枝刈りが必要になるけど，NLPのモデル生成はオフラインだからどうなのでしょう？デプロイしたときに高速にベイズ推論する必要のある処理って？
2012-09-04 11:35:51
NLP若手の会 (YANS)
@yans_official
鶴岡先生による招待公演『自然言語処理とAI』が終わりました。とても楽しい発表で、終った後に先生の周りには人が集まっています。鶴岡先生、どうもありがとうございました。 #yans http://t.co/AfnymwD7
2012-09-04 11:40:32
拡大
Daisuke Okanohara / 岡野原 大輔
@hillbig
@jnishi @mamoruk ナッシュ均衡を求めるという話は近似です。詳しくはこちら http://t.co/GqHNkr5r とてもスケールし実装は簡単だけど、証明は難しいという良い感じになってます #yans
2012-09-04 17:05:15