文献

J-GLOBAL ID：201802230926526360   整理番号：18A0195901

学習グラフゲームのサンプル計算量について【Powered by NICT】

On the sample complexity of learning graphical games

著者 (1件)： Honorio Jean (Computer Science, Purdue University, West Lafayette, IN 47907, USA)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： Allerton  ページ： 830-836  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： 純粋行動データからの学習グラフィカルゲームの試料の複雑性を解析した。選手の関節動作とその利得を観察できるだけであると仮定した。真のゲームの純粋戦略Nash均衡(PSNE)のセットの正確な回収のための試料の必要十分数を解析した。著者らの解析は,nノードを持つ有向グラフとノード当たり最もK両親に重点をおいた。スパースグラフはnに関してK∈O(1)に対応し,密グラフは,k∈O(n)に対応する。VC次元議論を用いて,著者らは,サンプルの数が密グラフのためのスパースグラフまたはO(n~2logn)のためのO(kN log~2N)よりも大きい場合,最尤推定は高い確率でPSNEを回復する正確であることを示した。情報理論的議論を用いて,著者らは,サンプルの数が密グラフのためのスパースグラフまたはQ(n~2logn)のためのQ(kn log~2N)よりも小さいならば,任意の考えられる方法は,任意の確率でPSNEを回復できないことを示した。Copyright 2018 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： *計算量 ,  最尤法 ,  利得 ,  情報理論 ,  有向グラフ ,  *学習 ,  *ゲーム ,  Nash均衡
準シソーラス用語： VC次元 ,  両親 ,  運動選手 ,  複雑性 , 【Automatic Indexing@JST】

分類 (1件)： 信号理論  (ND02020G)

タイトルに関連する用語 (5件)： 学習 ,  グラフ ,  ゲーム ,  サンプル ,  計算量