訳:レビュー論文

###### tags: `university` # 訳:レビュー論文 URL: https://arxiv.org/pdf/1709.08071.pdf 追加するタグ \#利得関数 \#モンテカルロツリー探索 \#最尤推定 \#最適化 \#条件付き分布 \#不完全情報ゲーム \#ディレクリ分布 \#決定論的有限オートマトン \#山登り法 \#ナッシュ均衡 \#標準形式ゲーム ## 議題現代の人工知能の研究の中心となっているのは他のエージェントと対話できる自律的なエージェントの開発である。この開発において重要な部分は他のエージェントの行動、目標、信念について推論する能力であり、この推論は他のエージェントのモデルを構築することで達成できる。一般的なモデルは観測された相互作用履歴の一部を入力として受け取り、モデル化されたエージェントへ関心のある特性の予測を返す関数であるといえる。Figure.1 ![](https://i.imgur.com/WCVehry.png) 例.サッカー選手は相互作用履歴(ボールの位置、速度、方向の変化)から他のエージェントの行動(ほかサッカー選手の動き)を推論し、自身のアクション(ボールを前に運ぶための動き)を選択する。この記事の目的は、自律エージェントが他のエージェントをモデル化できるようにする方法の包括的な調査を提供し、この分野における重要な未解決の問題を強調することである。以下に7つの主要なモデリング手法を説明する。 7つの主要なモデル - Policy Reconstruction - Type-Based Reasoning - Classification - Plan Recognition - Recursive Reasoning - Graphical Models - Group Modelling - Other Methods ## 関連研究従来のレビュー論文ではドメイン固有なもの(ゲームAIに使われている技術等)が多いが、本論文では文献全体で見られる主要なモデリング方法の一般的な調査を目的としている。 ## 基本的な前提モデリング手法を紹介する前に考え方の基礎となる前提を紹介する。この前提の理解によって手法の適用可能性と未解決問題を評価するのに役立つ。 ### 決定論的または確率的アクションの選択か？履歴に対して、アクションが毎度一つに定まる場合、エージェントは決定論的なアクションを選択するという。また確率的アクションの選択は選択可能なアクションが確率分布で表現されており、任意の確率で選択される。決定論的なアクション選択はある履歴に対して毎度同じアクションを選択するので簡素なモデル構築が期待できる。確率的なアクション選択は人間が行うようなランダム化やミスを起こせるため、より現実に即したモデル構築である。 ### エージェントは固定か変化するか？固定されたエージェントは最新の履歴のみに対してアクションを選択する。対して適応するエージェントは他のエージェントのモデルを学習し、それらに基づいたアクション選択を行う。初期のモデリングでは複雑さを排除するために固定されたエージェントが多かったが、今日では様々な適応性を獲得している。 ### 決断要因は既知か未知か？構築されたモデルは履歴からアクションに大きな影響をもたらすもの(決断要因)を抽出して用いる。これまでの手法では暗黙的に既知であると仮定していたが、未知であると仮定した場合、モデルの予測は信頼できない可能性が高くなる。今日、関連する可能性のある決断要因を推論する手法がいくつか議論されており、この問題の解決に近づいている。 ### 選択するアクションは独立的か相関的か？選択するアクションが独立的であるというのは他のエージェントがアクションを起こす際に別のエージェントから直接影響を受けていないということである。(選択するアクションは行動履歴を観測するため、他のエージェントの影響は間接的には受けている) 相関的であるというのはほかエージェントのアクションを考慮して、アクションを起こすということである。これまでの研究ではモデルを簡素にするために独立的なアクションであると仮定して開発が行われてきたが、近年ではサッカー個人ではなく、グループ全体をモデル化することで相関的なアクション選択を実現した例がある。 ### 目標は共通しているか、競合しているか？目標が達成するというのは観測環境が特定の状態に達するか、設定した目的関数が最適化されることを示す。他のエージェントから自身のアクションを選択する際、ほかエージェントの目標が自身と共通か、競合しているかによってアプローチを変える必要がある。近年、一部のモデリング手法では学習した他のモデルの利得関数まで考慮を行う ### 他前提についてチェスのように他エージェントの選択した行動か履歴として完全に観測できるゲームポーカーのように履歴から他エージェントの行動を推論するゲームサッカーのようにノイズの多い観測データから行動を選択するゲーム等があり、その時々においてモデルを考慮しなくてはならない ## 手法 ### Policy Reconstruction ポリシー再構築ポリシー再構築法は意思決定過程を再構築することにより、アクションについて明示的な予測を行うモデルを生成する。基本的には理想的なモデルから始め、モデル内部のパラメータを入力データに適合させることで学習する。たとえば、モンテカルロツリー検索（Browne et al。、2012）は、このようなモデルを自然に統合して、可能な相互作用履歴をサンプリングし、エージェントモデルに関する最適なアクションを見つけることができる。ポリシー再構築法において設計上の重要な課題は 1. 予測のために相互作用履歴のどの要素を使用するか 2. 使用する要素を予測にどのように用いるかとなっている #### 条件付き確率の頻度に関して一般的な手法で様々な対話モデルのもととなっている。政策再構築手法の典型的な例は「fictitious play」（Brown、1951）で、エージェントは互いのとる可能性のある行動を確率分布としてモデル化する。確率は、エージェントの観測されたアクションに対する最尤推定によって最適化される。この単純な方法は、マトリックスゲーム等でよく知られるような収束特性を持ち（Fudenberg and Levine、1998）、マルチエージェント強化学習の初期に採用された。（Claus and Boutilier、1998）ただ、上記のような単一の分布のみでは、履歴に複雑な依存関係があるエージェントの動作をモデル化するができない。これらのモデルをより機能的にするためには、履歴の要素のアクション分布を調整することが鍵となる。たとえば、Sen and Arora（1997）およびBanerjee and Sen（2007）は、モデリングエージェント自身のアクションを学習要因とした他のエージェントのアクション頻度を学習するエージェントを提案し、Davison and Hirsh（1998）は、条件付き確率を学習するユーザーモデルを提案した。より複雑な方法では、すべてのエージェントの最新の共同アクションなど、より多くの情報に基づいて分布を調整できる（Powers and Shoham、2005） --- 条件付きアクション分布の学習が難しい要因の一つとして、使用する履歴の質が悪いことが挙げられる。使用する履歴からの情報が少なすぎたり、間違ってたりする場合、履歴情報を直接利用して分布を調整すると、信頼できる予測を生成しない可能性が高まる。また、逆に情報が多すぎると、学習が遅すぎて非効率になる可能性が高まる。この問題に対処するために、調整を自動化する方法が開発された。 Jensen et al. (2005) らは特定の履歴に対して、予測精度の向上を見込めるものを選択する。データの組合せ爆発が起きないよう条件付き分布のエントロピーがしきい値を超えている場合一部のデータを考慮しない機構が含まれている。同様に、Chakraborty and Stone（2014）は、観測に条件付けられたアクション頻度を学習し、モデルを最もよく予測する「最小」条件付けを使用して独自のアクションを選択する方法を提案している。 *↑これは省くか引用論文を読む必要あり、意味わからんまた、これと本質的に同じ方法を使用して、履歴から導出された特徴ベクトルでデータ選択を条件付けるエージェントをモデル化できる手法もある。Chakraborty and Stone、2013 --- モデル化されたエージェントの条件付きアクション頻度を計算するアプローチは、ポーカーなどの不完全情報ゲームでもよく使用されている。（Mealing and Shapiro、2017; Ganzfried and Sandholm、2011; Southey et al。、2005; Billings et al。、2004）不完全ゲームの特徴は公開情報(ポーカーで言う場に出ているカード)と個人情報(ポーカーでいる自分が所持しているカード)があることである。エージェントはこの情報セットで判断を行う。他人の情報セットに関しては公開情報だけでは知りうることができない。ただ、他のエージェントの意思決定は、さまざまな情報セットでアクションを選択した観察頻度としてモデル化できる。 Southey et al. (2005)は情報セットごとに独立したディリクレ分布を関連付け、観察された各アクションの後に対応する分布を更新する。また、このような分布をゼロから学習するのではなく、合理的なベースラインに合わせて分布を初期化することもできる。Ganzfried and Sandholm（2011）はまず、各情報セットとエージェントのアクション分布を導出するゲームのナッシュ平衡解を計算する。この解を使用することで、エージェントモデルを初期化できる。プレイ中、モデル内の分布は、実際の動作を反映するために、モデル化されたエージェントの観察されたアクション頻度に適応していく。この方法の利点は、モデリングエージェントが、任意のモデルから開始するのではなく、合理的な（ナッシュ）相手モデルに対するアクションを最初に計画できることである。 Billings et al. (2004)はアクション履歴全体を用いる手法を提案している。これらを迅速に処理するために粗い抽象度のデータを用いるとともに減衰関数を利用して最近の観測値がより大きな重みを持つようにする。 #### 事例ベースの推論上記に示したような観察結果の考慮を制限する手法は過去や貢献度の大きいデータを組込むメカニズムが欠けている。これに対応するために事例ベースの推論(Kolodner、2014; Veloso、1994、Hammond、1986)がある。これは類似度関数を利用して事例を観測結果を関連付け、その事例でモデル化されたエージェントを用いる手法である。事例を推定するには、与えられた事例の類似性を測定する類似性関数を指定する必要がある。たとえば、ロボットサッカーでは、サッカーフィールドの状態によって事例が定義され、類似性はボールとプレーヤーの位置から測定できる。新しい事例が提示されると、メソッドは最も類似した既知の事例を検索し、これらの事例の関数としてアクションを予測する。 Albrecht and Ramamoorthy（2013）は、観測された事例（環境状態として定義）と、各事例でモデル化されたエージェントからアクションを保存する方法を提案している。新しい事例でアルゴリズムを実行すると、メソッドは、類似した事例を検索し、検索条件に指定された事例との相対的な類似性と観察されたアクションの最新性に基づいて予測を集計し、動作を変更できる、 Borck et al. (2015) and Hsieh and Sun (2008)は他のエージェントの振る舞いをモデリングするための同様の事例ベースの方法を提案している。上記に示された全ての方法で、事例は複数の属性を持つベクトルとして表され、ベクトル間の類似性はドメイン固有の差分計算を使用して測定できる。事例ベースの方法における重要な問題は、モデル化されたエージェントに対して類似度関数を自動的に最適化できるかどうかである（Steffens、2005、2004a; Ahmadi et al。、2003）たとえば、Steffens（2004a）は、類似度関数が、2つの与えられた事例の属性の違いの線形重み付けとして定義される方法を提案している。重み付けは、モデル化されたエージェントの目標と、サブ目標と事例属性の間の依存関係を指定する「目標依存ネットワーク」に基づいて学習される。事例ベースの方法におけるもう1つの重要な質問は、事例を効率的に保存および取得する方法である。たとえば、Denzinger and Hamdan (2004)はツリー検索に基づいた検索方法を提案し、Borck et al. (2015)は事例を整理して、保存された事例の数を減らす。 #### コンパクトなモデル表現条件付けと事例は観察可能な情報に基づいているため、頻度分布と事例ベースの推論に基づく方法は一般的である。しかし、この一般性は指数関数的な空間の複雑さを含むことになる。例えばモデル化されたエージェントのアクション分布がm個のアクションを取る可能性があり、かつそれがn個の観測値を条件とする場合、最大m×n個の確率分布を保存することになる。これを克服するためによりコンパクトなモデル表現を用いることが必要となる。たとえば、 (Carmel and Markovitch, 1998b, 1996c; Mor et al., 1995)は決定論的有限オートマトン（DFA）としてエージェントの意思決定をモデル化した。基本的に、エージェントが新しいアクションを観察するたにに、DFA の現在の状態を前提として、アクションを予測してみた上で現在のモデルが観察と一致しているかどうかをチェックする。チェックが通らなかった場合、DFAモデルは新しい観測を考慮して修正される。これは新しいノードとノード間のエッジを追加することで実現する。この方法の利点は、観測と一致する最小のDFAを検索できることで高速となる。エージェントのモデル化に使用されている他の表現には、決定木（Barrett et al。、2013）および人工ニューラルネットワーク（Silver et al。、2016; Davidson et al。、2000）も含まれる。 #### 効用の再構築上記の全ての共通点としてモデル化されたエージェントの設定自体をモデル化していないことが挙げられる。この設定はよくなにかしらの効用関数として表現される。しかし、エージェントの意思決定要因がわからないため、問題を一般化して解くことが難しくなっている。これに対処するため、問題をモデル化されたエージェントが、自身にとって未知の効用関数を最大化すると仮定する。この仮定によってモデリングエージェントは、観察されたアクションから効用関数の推論が可能になる。効用関数の推定値が得られたら、モデル化されたエージェントから効用関数を最大化することにより、エージェントのアクションを予測できるようになる。 Carmel and Markovitch (1996b, 1993)はこの考えに基づいて、様々な形式のゲームでの対戦相手のモデリングを検討し、対戦相手が使用する効用関数のモデルを定義する。効用関数は、ゲーム状態の特徴量の線形結合であると想定されており、目標は組み合わせの重みを学習することに落ち着く。ゲームの状態と各状態での対戦者の選択されたアクションで構成される一連の履歴が与えられると、提案された方法は、山登り探索を使用して複数の候補モデルを学習し、それ以上の改善が不可能になるまで重み推定を繰り返す。 Chajewska et al. (2001)は同様の設定を用いて、モデル化されたエージェントの効用関数が「サブ効用」の線形重み付けであると仮定した。重み付けは既知であり、目標はサブ効用関数を学習することである。観察された履歴を考えると、提案された方法は、逆強化学習の方法と同様に、可能な効用関数の空間に線形制約を生成する *↑意味わからん引用論文を読む必要あり（Ng and Russell、2000）は利用可能な関数の空間から効用関数を選択するために、観測されたアクションを条件とするベイジアン事前分布を使用することを提案し、結果の事後関数を使用して効用関数をサンプリングした。 Gal et al. (2004)は標準形式のゲームを問題設定し、人間のプレーヤーの効用を、社会福祉や公平性などの社会的要因の線形結合としてモデル化した。データは、人間の行動と効用の分析結果から収集された。他のエージェントの効用関数、または好みを学習することも自律対話モデルの主要な研究である。たとえば、Hindriks and Tykhonov（2008）は、二国間多国間交渉を検討し、効用関数を問題評価関数の加重和として定義した。各問題に起因するデータの重みと評価関数を学習するために、特別な機能形式を想定して、可能性のある重みと評価関数の空間を離散化する。これにより、効用関数の有限の仮説空間が得られ、ベイズ事前分布が定義される。これは新しい履歴情報を得た際に更新される。この結果、ほかエージェントのの効用関数を推定するために使用できます Coehoorn and Jennings（2004）は、線形加法的な効用関数も検討し、カーネル密度推定を使用することで重み学習を行った。 --- ### 型ベースの推論ポリシー再構築の新しいモデルのゼロからの学習は、モデル化プロセスが有用なモデルを生み出す前に多くの観察が必要となる可能性があるため、時間のかかるプロセスとなる。これは、エージェントが別のエージェントについて多くの観察収集できない事例において深刻な障壁となる場合がある。このとき、エージェントが他のエージェントとの以前の相互作用で学習したモデルを再利用できるならば,現在の相互作用でモデル化されたエージェントの観察された挙動に最も近いモデルを見つけるだけでよい。実際、モデル化されたエージェントが既知のモデルがいくつかの挙動を有することが先験的に知られている。以前に学習した型を用いることを型ベースの推論という上記をまとめると、型ベースの推論は、モデル化されたエージェントがいくつかの既知の型のうちの1つを有すると仮定する。型は、エージェントの動作の完全な仕様であり、観測された相互履歴を入力として受け取り、モデル化されたエージェントが利用できるアクションに確率を割り当てる。型は分野別の専門家が手動で指定できる。可能な型が与えられると、型ベースの推論は、相互作用履歴が観察される前に期待される型に事前確率を割り当てる。その後、新しい履歴が観測されるたびに、観測された行動を予測した型の信頼度を上げる。こうして、モデル化エージェントは、更新された型を使用して、型を用いて最適な動作を計算することができる。この方法の有用な特性は,もしモデル化されたエージェントの真の型が考慮された型の集合内にあるならば,わずか数回の観察でこの型を特定することができ,迅速な学習を導けることである。型ベースの推論は、最初はゲーム理論家によって研究され、すべてのプレイヤーが他のプレイヤーの可能な型(Harsanyi, 1967)の信頼度を維持するゲームを考察した。この研究での主な問題は,プレイヤーが相互作用履歴を通して正確な予測を学習できる程度と,相互作用履歴がNash平衡(Nash, 1950)のような解に収束するかどうかである。Kalai and Lehrer(1993)の結果によると、プレイヤーの方への信頼度に関するある仮定の下で、将来のプレイの予測はNash均衡への収束が現れた。後続研究は,均衡収束に及ぼす事前の信頼度の影響を検討し,もしプレーヤーが異なる事前の信頼度を有するならば,彼らのプレイはナッシュ均衡ではない主観的均衡に収束するかもしれないことを示した(Dekel et al., 2004; Nyarko, 1998)。最後に、特定のゲームと条件に関して、プレーヤーが正しい方の信頼度を有することができず、彼らの信頼度に基づいて最適にプレイすることができないことを示す結果がある(Nachbar, 2005; Foster and Young, 2001) AI研究において,型ベース推論は,事前調整なしのマルチエージェントによる相互作用(Albrecht et al., 2017; Stone et al., 2010)の問題において人気があることを見出した。この問題では,調整されたエージェントは,最初にその挙動が未知の他のエージェントと相互作用する。Albrechtら(2016)は,ベイズ-ナッシュ均衡(Harsanyi, 1968a)とBellman最適性方程式(Bellman, 1957)の再帰的結合をした型ベース推論法の簡潔で簡潔な定義をしている。この組合せは,すべての利用できる相互作用履歴と予測された確率および利得の木を形成し,確率は型の信頼度の変化を考慮する。以前と異なる信頼度の定式化を定義し,それらの収束特性(Albrecht and Ramamoorthy, 2014)を解析した。また、過去の信頼度は利得の最大化に長期的に大きな影響を与える可能性があり、一貫したパフォーマンス効果(Albrecht et al., 2015b)で自動的に計算できることを実証的に示した。Barrettら(2011)は、型に対する現在の信頼度に基づいて、UCT(Kocsis and Szepesvari, 2006)の各ロールアウトが互いに型をサンプリングするように、サンプリングベースのUCTを提案した。このアルゴリズムは,他のエージェントの真の型が考慮された型の集合内になくても,十分に類似した型が知られている限り,うまく実行できる「追跡」格子世界領域で評価される。その後の研究で、Barrettら(2013)は、以前の相互作用で学習した決定木のタイプを適応させるために、伝達学習がどのように使用できるかを示している。 Rovatsosら(2003)は,決定性有限オートマトンとして表現される複数の型を動的に学習する方法を提案する。新しいエージェントと対話するとき、このメソッドは最も近い既知のタイプを見つけるか、将来参照できるように新しいタイプを追加する。タイプに対する最適行動は,Q学習(Watkins and Dayan 1992)のような強化学習法を用いて計算される。Takahashiら(2002)は,各モジュールがエージェントタイプに対応し,「ゲート信号」を用いて各モジュールがどの程度現在のエージェントに一致するかを決定する「マルチモジュール」強化学習法を提案した。上記の方法は全て、モデル化されたエージェントの観察された動作を仮定して、型の相対的な可能性を決定するためにベイズの法則またはそのいくつかのアルゴリズムを使用する。ベイズの法則の代わりに、人工神経回路網のような機械学習法を用いることもできる。人工神経回路網は、観察された行動から型(重みベクトルとして表される)を学習することができる。例えば、Lockettら(2007)は、二つのニューラルネットワークからなる方法を提案している。一つのネットワークは、モデル化されたエージェントの観察された行動を入力として取り、混合された型を予測するように訓練されている。他方のネットワークは、利用可能なアクションに確率を割り当て、最初のネットワークからの観測されたアクションと予測された混合された型を入力として取ることによって、決定を行うように訓練される。同様に、Heら(2016)は、異なる型に対応するいくつかの「エキスパートネットワーク」の予測Q値を組み合わせる「ゲーティングネットワーク」を訓練している。多くの型ベース推論法は,各型が異なる決定関数である離散(通常有限)型空間を使用する。本質的に連続的な仮説空間でさえ、離散型空間を得るために離散化することができる(Hindriks and Tykhonov,2008)。また、他にも連続した型空間について直接推論することもできる。基本的に、いくつかの連続したパラメータを持つ単一の決定関数があり、その信頼度はパラメータ値の相対的な可能性を定量化し、特定のパラメータ設定を1つの型として表示できます。例えば、Southeyら(2005)は、Pokerについての指定されたプレーヤ関数の連続パラメータに関するガウス分布の信頼度を維持する手法を提案している。これは離散タイプスペースと連続タイプスペースを組み合わせることもできる。AlbrechtとStone(2017)は,型の有限集合の相対尤度とこれらの型内の任意の有界連続パラメータの値の両方を同時に推論する方法を提案する。この方法は各離散型の初期パラメータ推定から始まる。新しい動作が観察された後、型のサブセットが選択され、近似ベイズ更新および正確なグローバル最適化(Horstら、2000)などの方法を使用してパラメータ推定が更新される。タイプベース推論の興味深い側面は,エージェントのタイプに関する情報を意図的に選択することである。行動選択において偶発的ランダム化のようなスキームを使用することは可能であるが、そのようなスキームは探索行動がモデル化された薬物に意図しない影響を及ぼすリスク(Carmel and Markovitch、1999)を無視している。この点に関して,タイプベース推論は,自然に決定論的「情報の価値」(ハワード,1966)を行動の評価に統合することができる。例えば、CarmelとMarkovitch(1999)およびAlbrechtら(2016)によって提案された方法は、動作がモデル化されたエージェントのタイプについて明らかにする潜在的な情報と、これが将来の相互作用にどのように影響するかを再帰的に考慮する。Chalkiadakis and Boutilier(2003)は,行動の評価のために信頼度が一定に保たれる信頼度の変化の一つの再帰だけを考慮するこの種の推論の近似を提案した。Sadighら(2016)は、モデル化されたエージェントのタイプにおける不確実性を最小化することと、与えた利得関数を最大化することとの間のトレードオフを最適化するために、モデル予測制御の形態を使用する。これに関連して、Schmid et al.(2007)の「プロアクティブ実行モジュール」では、不確実性の最小化、期待される目標の達成、活動に割り当てられたリスク値の最小化など、いくつかの基準を行動の選択に取り入れている。 ### 分類ポリシー再構築と型ベース推論はモデル化されたエージェントの将来の行動を予測しようとするが,エージェントモデルが予測できる他の特性または関心量がある。例えば、エージェント・モデルは、モデル化されたエージェントのプレイスタイルが「攻撃的」であるか「防御的」であるか(Schadd et al.,2007)など、より抽象的な特性に関する予測を行うことができ、あるいはモデル化されたエージェントが特定のアクションを行う予想時間(e.g. Weber and Mateas, 2009)などの量を予測することができる。ラベルの1つを割り当てる前者のタスクは分類と呼ばれ、連続値を予測する後者のタスクは回帰と呼ばれる。このような予測をモデル化エージェントが利用する方法はいくつかある。例えば、割り当てられたラベルは、if-then-elseルールまたは決定木を使用して、モデル化エージェントの決定手順に自然に組み込むことができる。あるいは、クラスラベルが与えられた場合、エージェントは、その特定のクラスラベルに対して事前計算された確率分布を使用することができる。分類は、観察された相互作用からの情報に基づいて、モデル化されたエージェントにクラスラベルを割り当てるモデルを生成する。ポリシー再構築手法と同様に、分類手法には2つの設計上の中心的な問題がある。 1. 相互作用履歴からどのような観察結果を用い、分類のためにそれらをどのように表現すべきか 2. データ表現が与えられた場合にどのように分類を行うべきか複雑な戦略ゲームにおけるプレイヤーをモデル化するために,いくつかの分類法が提案されている。WeberとMateas(2009)は、Starcraftのゲームでプレイヤーの戦略と構築時間を予測する方法を提案している。モデルは、熟練した人間プレイヤーから収集したデータで訓練する。各データは6つの戦略のうちの1つとしてタグ付けされ、ゲーム内の様々な特徴ベクトルに変換される。多数の機械学習アルゴリズムをそれらデータで試験し,その結果、学習したモデルがプレーヤ戦略と構築時間を首尾よく予測できることを示した。SynnaeveとBessiere(2011)は同じ収集した熟練者のリプレイデータを用いて,期待値最大化とk平均法アルゴリズムを用いて,戦略の有限集合からStarcraftプレーヤの戦略を分類する方法を提案した。Schaddら(2007)は,Springゲームにおけるプレーヤのプレイスタイル(攻撃的か防御的か)を予測するための領域特異的分類器を提案する。プレイスタイルの変化を考慮するために,モデルは過去の観察よりも最近の観察を優先する。Spronckおよびden Teuling(2010)は、サポートベクトルマシン(SVM)を使用して、Civilization IVゲームでのプレーヤーの「環境設定」を予測する。トレーニング・データは、異なる設定を有する所定のAIプレーヤを互いに突き合わせることによって生成される。収集したデータはゲーム状態からなり,都市や単位の数などの属性を持つ特徴ベクトルに変換される。このデータを用いて,1つのSVM分類器を各好みに対して訓練した。結果、各プレーヤーは、軍事、文化、科学開発などの分野で選好を持つという特徴があった。 Laviersら(2009)は、SVMを使用して、フットボール・ゲームRush2008での対戦相手チームの防御プレイを分類する。このゲームでは、チームのフォーメーションと、攻防のためのプレイのセットが決定されている。これらのチーム編成とプレーのすべての組み合わせから生成されたゲームデータを用いて,一連のマルチラベルSVM分類器を,観測における長さの増加に対応して訓練した。Sukthankar and Sycara(2007)は,Dungeons&Dragonsのようなターンベース戦略ゲームを考察し,様々な役割のためのシミュレーションゲームデータを用いて,プレーヤーを有限集合の役割(偵察、メディア等)に分類するためにSVMを訓練する。分類法が研究されている複雑な領域にロボットサッカーもある。上記の方法との注目すべき違いは、モデルが現在のプレーヤーまたはチーム全体の戦略を予測することと、統計的機械学習方法に加えて記号的方法を使用することである。Steffens(2004b)は「特徴ベースの宣言」分類法を提案している。ここで、各モデルは、論理状態記述の対として定義される多数の特徴と、記述された状態で見られることが期待される1つ以上の対戦相手プレーヤの動作とからなる。 ↑意味不明、引用読む必要ありモデルのコンパクト性は、他のモデルと比べて相対的に強く、安定しているという特徴にモデルを限定することで達成される。これは、モデルで頻繁に発生することを意味する。ゲームの状態とプレーヤーの動作からなるゲームの観察履歴が与えられると、異なる記号的アプローチとベイズ的アプローチを使用して、特徴を観察に一致させることができる。モデルの特徴との一致が成功した場合、対戦相手が特定されたことを意味する。 Bombiniら(2010)は,与えられたチームのためのゲームイベントの時系列に作用する関係手続きを提案する。各シーケンスは、パスやドリブルなどの上位レベルのアクションで構成され、次に、キックや方向転換などの下位レベル(原始的な)のアクションで構成される。帰納論理プログラミング(Muggleton, 1991)を使用して、これらのシーケンスから特徴を自動的に選択する。特徴ベクトルが与えられると,この方法は特徴ベクトル間の距離関数を指定した最近接アルゴリズムを用いてチームを分類する。同様に、Iglesiasら(2008)は、ゲームイベントの記号シーケンスを抽出し、それらの周波数を「トライ」構造(フレドキン,1960)で表し、統計的仮説検定を用いて既知のモデルと比較する。このアプローチは、既存のモデルでは不十分であることが判明した場合に、基本的に新しいモデルを追加することによって、エージェントの動作を進化させるように拡張されています(Iglesiasら、2010)。ロボットサッカーの他の方法には、特定の地理的領域における特定の事象(ボール/プレーヤーポジション、パス/ドリブルイベントなど)の発生をカウントするために使用される競技場のグリッド離散化に基づいてチームを分類するRileyとVeloso(2000)、および決定木を学習してゴールキーパーの挙動および対戦相手プレーヤーの通過挙動を分類するVisserとWeland(2002)がある。「マルチエージェントシステムにおける信頼と評判」は,エージェントの信頼性をモデル化するために分類と回帰法を用いる研究分野である。信頼の定義の一つは、「エージェントが与えられたコンテクストの契約条件を実現する期待」である。信頼は、「モデル化されたエージェントとの相互作用からの自身の経験、システム内の他のエージェントから伝達された経験、ならびにモデル化されたエージェントの役割および他のエージェントに対するその相互関係を含む、多数の情報」である。例えば、Abdul-Rahman and Hailes(2000)は、エージェントに関する直接の経験と報告された経験に基づいて、エージェントを非常に信頼できる、信頼できる、信頼できない、または非常に信頼できないと分類している。他の多くの提案された方法は,信頼を、相対的重要性重み、信頼値、時間割引などを用いて種々の情報源を集約する連続値として定量化している(e.g. Huynh et al., 2006; Mui et al., 2002; Sabater and Sierra, 2001; Schillo et al., 2000)。信頼のこのような定性的または定量的予測は、モデル化エージェントがモデル化エージェントとの相互作用を調整するために使用することができ、重要なことに、信頼レベルを使用して、最初にどのエージェントと相互作用するかを決定することができる。 ### 計画認識計画の認識とは、エージェントの監視されたアクション(Carberry, 2001)に基づいて、エージェントの実行可能な目標と計画を特定するタスクである。ここでの焦点は、これまでに観察された作用の意図されたゴールと、作用がその目的を達成しようとする一連の段階を予測することである。他のエージェントの目標と計画に関する知識は、エージェントとの対話に非常に役立つ。例えば、適応型ユーザインタフェースは、人間のユーザが何を達成しようとしているかを知っている場合には、特定のアクションを提案し、他の関連情報を表示することができ(Oh et al., 2011; McTear, 1993)、侵入検知システムは、攻撃者の目標および計画を検出する場合には、特定の対抗手段を取ることができる(Geib and Goldman、2001)。多くの計画認識方法は、観測されたエージェントが追求する可能性のある計画と目標を記述する計画ライブラリを使用します。プランの表現はプラン認識法における重要な要素であり,多くの方法は「トップレベル」目標をさらに分解可能な部分プランに分解する階層10表現を使用する。この計画階層のリーフは、潜在的に観察可能なプリミティブ(非分解可能)アクションです。また、プラン・ライブラリには、プランのステップ間の時間順序や、特定のプラン・ステップを実行するために保持する必要がある環境状態の前提条件などの追加ルールを含めることもできます。このような計画ライブラリと観測された一連のアクションが与えられると、計画認識タスクは、計画ライブラリの規則を尊重し、観測されたすべてのアクションを説明(を含む)する可能な計画仮説を生成することになります。観察された行動を説明する複数の計画仮説が存在する場合、それらは、それらがどの程度妥当であるか、または可能性があるかのような付加的な要因によって区別されることがある計画の認識は、政策再構築(セクション4.1)やタイプベースの推論(セクション4.2)とは異なり、後者は所与の状況に対する行動を予測するが、モデル化されたエージェントが環境内で特定の目標状態に到達しようとするなど、これらの行動の意図された最終結果を予測しない。一方、計画の認識は将来の行動を予測するためにも使用できるが、その結果得られる予測は、政策再構築やタイプベースの推論によって生成されるモデルの予測よりも精度が低いことが多い(いくつかの注目すべき例外、例えばBui et al.(2002))。たとえば、計画では、一部の処理が他の処理の前に発生する必要があるなど、処理の一時的な順序を部分的に指定することがよくあります。この柔軟性は計画には役立ちますが、計画実行でのアクションの正確な順序と可能性は残されています。したがって、計画は可能な一連のアクションを予測できますが、必ずしも次のアクションが実行されるとは限りません。平面認識法は「鍵穴」法と「意図した」法に分類されることがある(Cohen et al.,1981)。違いは、モデリングされたエージェントがモデリングエージェントを認識していると想定されるかどうかです。現在の方法の大部分はキーホールプラン認識のために設計されており,そこではモデル化エージェントはモデル化エージェントを知らないと仮定されている。 #### 階層プランライブラリでのプランの認識 KautzとAllen(1986)は,計画が他の複雑で原始的な行動に分解する複雑な階層的行動を用いて表現される,計画認識の記号理論を提案する。この結果、エッジが平面図の分解を示し、グラフのルートノードが目標として解釈できる「トップレベルの計画」に対応するグラフ表現が得られます。認識問題は,著者らが外接(マッカーシー (1980歳))の概念を用いて定式化した,観察された(原始的な)行動をカバーするグラフの問題としてフレーム化される。TambeとRosenbloom(1995)は、計画ステップが環境の状態によって条件付けされる階層的な計画階層を使用します。提案した方法は単一計画仮説に早期にコミットし,この仮説の文脈で新しい観測を評価する。最新計画の仮説が新規の観察結果と矛盾する場合、このメソッドは、計画階層内の限定されたバックトラッキングを介して仮説の修復を試みます。Avrahami‐ZilberbrandとKaminka(2005)は,計画段階の分解,時間順序,適用条件を規定する有向非循環グラフとして計画ライブラリを表現する。計画認識は,新しい観測に一致し,時間的順序と適用可能条件を考慮した計画グラフ中の完全な経路をタイムスタンプする「怠惰な」手順を介して実行される。必要に応じて、計画仮説の完全なセットを抽出できます(したがって「怠惰な」)。この方法に対するいくつかの拡張が提案されています:アクションの継続時間、インターリーブされた計画の実行、および欠落した観測(Avrahami-Zilberbrand et al.,2005)を可能にします。;モデル化エージェント(Avrahami-Zilberbrand and Kaminka、2007年)へのそれらの期待される有用性によって計画仮説をランク付けする拡張;計画認識タスクにタイミング制約を組み込んだ拡張機能(Fagundesら、2014)があります。 CharniakとGoldman(1993)は,ベイジアンネットワーク(パール,1988)における確率的推論の問題としてフレームプラン認識を提案している。計画ライブラリは,ベイジアンネットワークの集合を構築することができる,分解可能な動作の集合として表現される。各ネットワークのルートは、事前確率を指定する必要がある上位レベルの計画に対応し、子ノードは計画分解に対応します。この計画仮説の「信仰」は、ルートノードの値が真である確率で表され、標準的な推論アルゴリズム(パール,1988)を使って計算することができる。Buiら(2002)は、プランを抽象ポリシーのK−depth階層として表し、ここで、深さkのポリシーは、深さk−1のポリシーを選択し、深さk=0のポリシーは、プリミティブなアクションである。他の定式化との顕著な違いは,政策が政策再構築(セクション4.1)および型ベース推論(セクション4.2)で学習したモデルに類似した環境状態で定義されることである。筆者らは,動的Bayesネットワークを用いて認識プロセスを構築する方法を示し,それらはRao‐Blackwellised粒子フィルタ(Doucetら、2000)を用いて推論を実行した。関連する方法は,プラン生成規則が状態情報(ピナダス・アンド・ウェルマン,2000#ピナダス・アンド・ウェルマン#)に依存することを可能にする確率的状態依存文法に基づく。GeibとGoldman(2009)は、AND/ORツリーに基づく計画を表します。この場合、ANDの子は時間的制約がある可能性のある計画で必要なステップであり、ORの子は、実行する必要がある計画の代替(選択)ステップです。この方法では,エージェントが特定の計画をどのように決定するか,および計画のステップがどのように実行されるかの確率を指定する計画実行の生成モデルを使用する。この計画実行モデルはシミュレート可能であり,著者らは観測に基づいて計画を推論するためにモデルがどのように使用できるかを示した。 #### ドメインモデルでのPlanningによるプラン認識プラン・ライブラリーを使用する場合の潜在的な欠点は、その仕様が面倒であることと、不完全であることです(つまり、観察されたエージェントは、プラン・ライブラリーでは構築できないプランを使用する可能性があります。)。RaḿırezとGeffner(2009)は,STRIPS計画言語(Fikes and Nilsson,1971歳)で規定されている領域モデルにおける計画問題として,計画認識の代替定式化を提案した。可能な目標のセットが与えられると、観察されたエージェントの潜在的な目標は、目標を達成する最適な計画が観察された順序で観察された行動を含む目標であるという考えである。この考えは、モデル化されたエージェントが、既知のコスト定義「有理の」に関して最適なプランのみを実行するという点で(ユーティリティの再構築方法と同様;cf．セクション4.1 .4)であると仮定する。著者らは,既存の厳密および近似計画法が,本質的には,解が観察された行動と一致するようにモデル化されたエージェントに対する計画問題を解くことにより,この目標の集合を計算するためにどのように採用できるかを示した。この研究は続いて,計画仮説(ラム・エレスとゲフナー、2010)上のBayes確率を計算するために拡張される。ここで、可能な各目標は特定の事前確率を有し、目標が与えられた観測された動作の尤度は、目標を最適に達成する計画と目標を最適に達成し、観測された動作と一致する計画との間のコスト差として定義される。この尤度定義は,エージェントが準最適プランよりも最適プランを追求する可能性が高いという仮定を符号化する。(また、信頼できない観察を可能にする代替の確率的拡張についてはSohrabi et al.(2016)の研究、および連続ドメインで機能する発見的拡張についてはVered and Kaminka(2017)の研究も参照されたい。)Bakerら(2009、2005)は、RaḿırezとGeffner(2009)に非常によく似た考え方を提案しているが、これはマルコフ決定過程(MDP)内で定式化している(ベルマン,1957)。MDPは状態遷移と行動選択における確率性を可能にするので,特定の目標を達成するMDPのための任意の最適政策は,目標を与えられて観測された行動の尤度を誘導し,それは代替目標に対するベイズ事後確率を計算するために使用できる。MDPを用いた同様の目標認識法はNguyenら(2011)およびFernとTadepalli(2010)によって提案された。その後の研究で、Baker et al.(2011)とRamırezとGeffner(2011)は、部分的に観測可能なMDP(Kaelblingら、1998)におけるエージェントの目標(そして信念)を推測する計画に基づく方法を提案した。Lesh and Etzioni(1995)とHong(2001、2000)は,STRIPS言語の拡張で指定されたドメインのための記号グラフベース手法を提案する。どちらの方法もドメインモデルと観測された行動に基づいてグラフ構造を構築し,この構造を利用して観測された行動と一致する目標のサブセットを見出す。 #### 過去の計画との類似による計画認識計画仮説は、過去に観測された計画との類似性に基づいて生成することもできる。このアイデアを,計画認識(KerkezおよびCox,2003#KerkezオヨビCox#;Fagan and Cunningham,2003歳;Bareら、1994)のための事例ベース推論法の文脈で探求した。たとえば、KerkezおよびCox'(2003)は、各状態の環境状態およびアクションのシーケンスとしてプランを表します。現在の状態,観測された行動の履歴,および以前に観測された計画から成る事例ベースを与えて,認識タスクは,現在の状況に類似した計画を事例ベースから検索することである。類似性を定義する1つの方法は、特定のプロパティを共有する状態をグループ化する状態抽象化を使用することです。このアプローチの有用な特性は、計画ライブラリ(ケースベース)を前もって完全に指定する必要がなく、新しい計画が観測された後に拡張できることです。 (政策再構築のための事例ベースの推論方法については、4.1 .2節も参照。)Tianら(2016)は,自然言語処理における文補完の問題として計画認識を定式化している。文(計画)は単語の並び(動作)であり、コーパス(プランライブラリ)は既に見た文からなる。コーパスに基づいて,単語がどのように他の単語を囲むかの確率分布を学習するために自然言語処理法を用いた。次いで、不完全文(計画)は、結果として得られる文の全体の確率が最大化されるように、欠落した単語を埋めることによって完成され得る。(計画認識と自然言語処理の関係については、Geib and Steedman(2007)も参照してください。)Albrechtら(1998、1997)は、プレーヤがオンラインアドベンチャーゲームにおいて何を追求しているか「探求」を認識することを求めており、このゲームでは、パラメータが歴史的プレイデータのコーパスを使用して学習される動的ベイジアンネットワーク(ディーン・アンド・金沢,1989)を使用する。同様に、Gold(2010)は、アクションアドベンチャーゲームにおけるプレーヤーのゴールを予測するために、入出力隠れマルコフモデル(ベンジオ・アンド・フラスコニ,1995)を訓練する。BlaylockとAllen(2004、2003)の研究は密接に関連しており、観察された計画実行のコーパスを使用して学習された条件付き動作確率の積として目標確率を計算する。この作業は後に階層的な下位目標(BlaylockおよびAllen、2006年)を認識するように拡張された。 --- ## 9つの未解決問題文献で十分に対処されておらず、将来の研究の実り多い道を提供する可能性がある9つの未解決の問題について議論する ### モデリング手法の相乗的組み合わせ今回の調査ではそれぞれの目的、長所、短所を含めた方法論の概要を説明したが、これらの方法を組み合わせて長所と短所を補間する方法はまだ十分に発展していない。これを実現するためにさまざまなモデリング機能を含む単一なアプローチを見つけることが重要になる。これが実現されれば、問題に合わせてこれまでのモデリング手法を適切に組み合わせたモデルを構築することができるようになる。 ### 部分的な観測によるポリシー再構築多くの問題では観測された履歴は不完全で不確実である。特に分類、計画認識、再帰的/認識論的推論、およびグラフィカルモデルではさまざまな記号的および確率的アプローチが提案されている、しかし部分的な観測履歴下でのエージェントの行動のモデルの学習(ポリシー再構築)はほとんど提案されていない。ポーカーなどをプレイするモデルはあるが、ドメイン知識に基づいた最適化が行われている。つまり、ドメイン知識無しで部分観測下でのポリシー再構築手法は追加の研究が必要である。 --- ### ここにのこり7つの未解決問題が乗る --- ## まとめ本論文では他のエージェントと対話できる自律的なエージェントの開発における5つの前提、主な7つの手法、9つの未解決問題を示した。この調査が、現在の研究状況を要約し、重要な未解決の問題を明らかにすることにより、この継続的な発展に貢献することを願っている。 # 深堀り要約ここまで --- ### Type-Based Reasoning タイプ前提の推定ポリシー再構築で新しいモデルを学習するプロセスは時間がかかる場合が多い。その対策として、以前に学習したモデルを再利用することを考える。Type-Based Reasonigはモデルがいくつかの既知のタイプ一つを持っていると仮定して、入力された履歴から利用可能なタイプに確率を割り当てる。 ### Classification 観察されたデータや行うべきアクションに関してクラスタリングを行うことでその特定のクラスラベルに対して効果的な事前計算された戦略を取ることができる。ある研究ではゲームプレイヤーが攻撃的か防御的かを判別し、その後の行動予測を行った。 ### Plan Recognition (+具体例) 計画認識はエージェントの観察されたアクションに基づいて、エージェントの達成可能な計画と目標を決定するタスクである。例えば、適応型ユーザーインターフェイスでは、人間のユーザーの行動から何を達成しようとしているのかを予測し、特定のアクションを提案したり、他の関連情報を表示できたりする。 ### Recursive Reasoning 再帰的推定再帰的推論の方法は、ネストされた信念の明示的な表現を使用し、他のエージェントの推論プロセスを「シミュレート」して、アクションを予測します。不完全情報ゲーム(ポーカー等)ではゲーム内で意思決定が再帰的に行われていることを前提として効果を挙げました。 ### Graphical Models グラフィカルモデル状態と行動が正確な依存関係にあることを利用して意思決定過程モデルをグラフィカルモデルに落とし込むことができる。状態をノード、行動をエッジとして表現することで効率的なアルゴリズムとなる場合がある。条件付き選好（CP）ネットワークを構築して、交渉の対話に基づいたプレイヤーの選好をモデル化した例もある。 ### Group Modelling エージェントがアクションの選択に大きなランダム化と相関を持っている場合、単一のモデルではそれらを表現できないため、グループモデル(同じモデルで同じ問題を解くグループ)を用いることで、それらの問題をとくことができる。ある研究では、初期位置とボールの動きを考慮して、対戦相手チームの各プレイヤーのフィールド位置の確率を指定する対戦相手モデルとシミュレーションロボットサッカーの方法を開発している。 ### Other Relevant Methods #### Hypothesis Testing for Agent Models モデルを仮説と見なし、観測に基づいてモデルを拒否するかどうかを決定するアルゴリズム。 #### Using Models Safely 使用されたモデルが不正確な場合、計算されたポリシーが他のエージェントによって悪用される可能性がある。この問題に対処するために、モデルに対する「安全な」最適応答ポリシーを計算するいくつかの方法が提案されている。 ## 9つの未解決問題 ## まとめ本論文では対話モデルができる主な7つの手法を紹介した。この調査が、現在の研究状況を要約し、重要な未解決の問題を明らかにすることにより、この継続的な発展に貢献することを願っている。