On the Use of Automatically Acquired Examples for All-Nouns Word Sense Disambiguation
全名詞語義の曖昧性解消における自動獲得例の利用について
This article focuses on Word Sense Disambiguation (WSD), which is a Natural Language Processing task that is thought to be important for many Language Technology applications, such as Information Retrieval, Information Extraction, or Machine Translation. One of the main issues preventing the deployment of WSD technology is the lack of training examples for Machine Learning systems, also known as the Knowledge Acquisition Bottleneck. A method which has been shown to work for small samples of words is the automatic acquisition of examples. We have previously shown that one of the most promising example acquisition methods scales up and produces a freely available database of 150 million examples from Web snippets for all polysemous nouns in WordNet. This paper focuses on the issues that arise when using those examples, all alone or in addition to manually tagged examples, to train a supervised WSD system for all nouns. The extensive evaluation on both lexical-sample and all-words Senseval benchmarks shows that we are able to improve over commonly used baselines and to achieve top-rank performance. The good use of the prior distributions from the senses proved to be a crucial factor.
本稿では、情報検索、情報抽出、機械翻訳など、多くの言語技術アプリケーションにとって重要と考えられる自然言語処理タスクである単語意味曖昧性解消（WSD）に焦点を当てています。WSD技術の導入を阻む主な課題の一つは、機械学習システムのトレーニング例の不足、つまり知識獲得ボトルネックです。少量の単語サンプルに対して有効であることが示されている手法の一つは、例の自動取得です。私たちは以前、最も有望な例取得手法の一つが、WordNetに含まれるすべての多義名詞について、Webスニペットから1億5000万例の無償データベースをスケールアップして生成できることを示しました。本稿では、これらの例を単独で、または手動でタグ付けされた例に加えて使用して、すべての名詞を対象とした教師ありWSDシステムをトレーニングする際に生じる問題に焦点を当てます。語彙サンプルと全単語を対象としたSensevalベンチマークの両方を用いた広範な評価により、一般的に使用されているベースラインを上回り、最高ランクのパフォーマンスを達成できることが示されています。感覚から得られる事前分布の適切な活用が重要な要素であることが判明しました。
The Latent Relation Mapping Engine: Algorithm and Experiments
潜在的関係マッピングエンジン：アルゴリズムと実験
Many AI researchers and cognitive scientists have argued that analogy is the core of cognition. The most influential work on computational modeling of analogy-making is Structure Mapping Theory (SMT) and its implementation in the Structure Mapping Engine (SME). A limitation of SME is the requirement for complex hand-coded representations. We introduce the Latent Relation Mapping Engine (LRME), which combines ideas from SME and Latent Relational Analysis (LRA) in order to remove the requirement for hand-coded representations. LRME builds analogical mappings between lists of words, using a large corpus of raw text to automatically discover the semantic relations among the words. We evaluate LRME on a set of twenty analogical mapping problems, ten based on scientific analogies and ten based on common metaphors. LRME achieves human-level performance on the twenty problems. We compare LRME with a variety of alternative approaches and find that they are not able to reach the same level of performance.
多くのAI研究者や認知科学者は、類推が認知の中核であると主張してきました。類推作成の計算モデル化に関する最も影響力のある研究は、構造マッピング理論（SMT）と、その構造マッピングエンジン（SME）への実装です。SMEの限界は、複雑な手作業による表現が必要になることです。私たちは、SMEと潜在関係分析（LRA）のアイデアを組み合わせることで手作業による表現の必要性を排除する潜在関係マッピングエンジン（LRME）を紹介します。LRMEは、大規模な生のテキストコーパスを使用して単語リスト間の類推マッピングを構築し、単語間の意味関係を自動的に検出します。私たちは、科学的類推に基づく10問と一般的なメタファーに基づく10問の計20問の類推マッピング問題でLRMEを評価しました。LRMEは、20問の問題で人間レベルのパフォーマンスを達成しました。私たちはLRMEをさまざまな代替アプローチと比較し、同じレベルのパフォーマンスには達できないことを発見しました。
On the Value of Correlation
相関の価値について
Correlated equilibrium generalizes Nash equilibrium to allow correlation devices. Correlated equilibrium captures the idea that in many systems there exists a trusted administrator who can recommend behavior to a set of agents, but can not enforce such behavior. This makes this solution concept most appropriate to the study of multi-agent systems in AI. Aumann showed an example of a game, and of a correlated equilibrium in this game in which the agents’ welfare (expected sum of players’ utilities) is greater than their welfare in all mixed-strategy equilibria. Following the idea initiated by the price of anarchy literature this suggests the study of two major measures for the value of correlation in a game with nonnegative payoffs:1. The ratio between the maximal welfare obtained in a correlated equilibrium to the maximal welfare obtained in a mixed-strategy equilibrium. We refer to this ratio as the mediation value.2. The ratio between the maximal welfare to the maximal welfare obtained in a correlated equilibrium. We refer to this ratio as the enforcement value.In this work we initiate the study of the mediation and enforcement values, providing several general results on the value of correlation as captured by these concepts. We also present a set of results for the more specialized case of congestion games, a class of games that received a lot of attention in the recent literature.
相関均衡は、相関デバイスを可能にするためにナッシュ均衡を一般化します。相関均衡とは、多くのシステムにおいて、エージェントの集合に対して行動を推奨できるものの、その行動を強制することはできない、信頼できる管理者が存在するという考え方です。このため、このソリューション コンセプトはAIにおけるマルチエージェント システムの研究に最適です。Aumannは、あるゲームの例と、そのゲームにおける相関均衡の例を示しました。このゲームでは、混合戦略均衡において、エージェントの福祉(プレイヤーの効用値の期待値の合計)が各プレイヤーの福祉よりも大きくなります。無政府状態の代償に関する文献で提唱されたアイデアに倣い、これは、非負の報酬を持つゲームにおける相関の価値を評価する2つの主要な尺度を研究することを示唆しています。1.相関均衡で得られる最大福祉と、混合戦略均衡で得られる最大福祉の比率。この比率を仲介値と呼びます。2.相関均衡で得られる最大福祉と、最大福祉の比率。この比率を強制値と呼ぶ。本研究では、媒介値と強制値の研究を開始し、これらの概念によって捉えられる相関の価値に関するいくつかの一般的な結果を提示します。また、近年の文献で大きな注目を集めているゲーム群である混雑ゲームという、より特殊なケースに関する一連の結果も提示します。
Learning to Reach Agreement in a Continuous Ultimatum Game
連続最後通牒ゲームにおける合意形成学習
It is well-known that acting in an individually rational manner, according to the principles of classical game theory, may lead to sub-optimal solutions in a class of problems named social dilemmas. In contrast, humans generally do not have much difficulty with social dilemmas, as they are able to balance personal benefit and group benefit. As agents in multi-agent systems are regularly confronted with social dilemmas, for instance in tasks such as resource allocation, these agents may benefit from the inclusion of mechanisms thought to facilitate human fairness. Although many of such mechanisms have already been implemented in a multi-agent systems context, their application is usually limited to rather abstract social dilemmas with a discrete set of available strategies (usually two). Given that many real-world examples of social dilemmas are actually continuous in nature, we extend this previous work to more general dilemmas, in which agents operate in a continuous strategy space. The social dilemma under study here is the well-known Ultimatum Game, in which an optimal solution is achieved if agents agree on a common strategy. We investigate whether a scale-free interaction network facilitates agents to reach agreement, especially in the presence of fixed-strategy agents that represent a desired (e.g. human) outcome. Moreover, we study the influence of rewiring in the interaction network. The agents are equipped with continuous-action learning automata and play a large number of random pairwise games in order to establish a common strategy. From our experiments, we may conclude that results obtained in discrete-strategy games can be generalized to continuous-strategy games to a certain extent: a scale-free interaction network structure allows agents to achieve agreement on a common strategy, and rewiring in the interaction network greatly enhances the agents’ ability to reach agreement. However, it also becomes clear that some alternative mechanisms, such as reputation and volunteering, have many subtleties involved and do not have convincing beneficial effects in the continuous case.
古典的ゲーム理論の原則に従って個人が合理的に行動すると、社会的ジレンマと呼ばれる種類の問題において、最適解に至らない場合があることはよく知られています。対照的に、人間は一般的に社会的ジレンマにそれほど困難を感じません。なぜなら、個人的利益と集団的利益のバランスをとることができるからです。マルチエージェントシステムのエージェントは、例えば資源配分といったタスクにおいて、社会的ジレンマに日常的に直面するため、人間の公平性を促進すると考えられるメカニズムを組み込むことで、これらのエージェントは恩恵を受ける可能性があります。こうしたメカニズムの多くは既にマルチエージェントシステムのコンテキストに実装されていますが、その適用範囲は通常、利用可能な戦略が離散的なセット（通常は2つ）を持つ、比較的抽象的な社会的ジレンマに限定されています。現実世界の社会的ジレンマの例の多くは実際には連続的な性質を持つことから、我々はこの先行研究を、エージェントが連続的な戦略空間で行動する、より一般的なジレンマへと拡張します。ここで研究対象となる社会的ジレンマは、よく知られた最後通牒ゲームであり、エージェントが共通の戦略に合意すれば最適解が達成されます。スケールフリー相互作用ネットワークが、特に望ましい結果（例えば人間）を表す固定戦略エージェントが存在する場合に、エージェントの合意形成を促進するかどうかを調査します。さらに、相互作用ネットワークにおける再配線の影響を調査します。エージェントは連続行動学習オートマトンを備え、共通戦略を確立するために多数のランダムペアワイズゲームをプレイします。実験から、離散戦略ゲームで得られた結果は、ある程度連続戦略ゲームに一般化できると結論付けることができます。スケールフリー相互作用ネットワーク構造は、エージェントが共通戦略で合意することを可能にし、相互作用ネットワークの再配線はエージェントの合意形成能力を大幅に向上させる。しかし、評判やボランティア活動といった代替メカニズムには多くの微妙な点があり、連続的な場合には説得力のある有益な効果をもたらさないことも明らかになった。
A Multiagent Reinforcement Learning Algorithm with Non-linear Dynamics
非線形ダイナミクスを用いたマルチエージェント強化学習アルゴリズム
Several multiagent reinforcement learning (MARL) algorithms have been proposed to optimize agents’ decisions. Due to the complexity of the problem, the majority of the previously developed MARL algorithms assumed agents either had some knowledge of the underlying game (such as Nash equilibria) and/or observed other agents actions and the rewards they received.We introduce a new MARL algorithm called the Weighted Policy Learner (WPL), which allows agents to reach a Nash Equilibrium (NE) in benchmark 2-player-2-action games with minimum knowledge. Using WPL, the only feedback an agent needs is its own local reward (the agent does not observe other agents actions or rewards). Furthermore, WPL does not assume that agents know the underlying game or the corresponding Nash Equilibrium a priori. We experimentally show that our algorithm converges in benchmark two-player-two-action games. We also show that our algorithm converges in the challenging Shapley’s game where previous MARL algorithms failed to converge without knowing the underlying game or the NE. Furthermore, we show that WPL outperforms the state-of-the-art algorithms in a more realistic setting of 100 agents interacting and learning concurrently.An important aspect of understanding the behavior of a MARL algorithm is analyzing the dynamics of the algorithm: how the policies of multiple learning agents evolve over time as agents interact with one another. Such an analysis not only verifies whether agents using a given MARL algorithm will eventually converge, but also reveals the behavior of the MARL algorithm prior to convergence. We analyze our algorithm in two-player-two-action games and show that symbolically proving WPL’s convergence is difficult, because of the non-linear nature of WPL’s dynamics, unlike previous MARL algorithms that had either linear or piece-wise-linear dynamics. Instead, we numerically solve WPL’s dynamics differential equations and compare the solution to the dynamics of previous MARL algorithms.
エージェントの意思決定を最適化するために、複数のマルチエージェント強化学習（MARL）アルゴリズムが提案されています。問題の複雑さから、これまで開発されたMARLアルゴリズムの大半は、エージェントがゲームに関する知識（ナッシュ均衡など）を有しているか、他のエージェントの行動と彼らが受け取る報酬を観察していると仮定していた。本稿では、重み付けポリシー学習器（WPL）と呼ばれる新しいMARLアルゴリズムを紹介します。このアルゴリズムにより、エージェントはベンチマークとなる2プレイヤー2アクションゲームにおいて、最小限の知識でナッシュ均衡（NE）に到達できます。WPLを用いると、エージェントが必要とするフィードバックは自身のローカル報酬のみとなり、他のエージェントの行動や報酬を観察しない。さらに、WPLは、エージェントがゲームや対応するナッシュ均衡を事前に知っていることを前提としない。本アルゴリズムがベンチマークとなる2プレイヤー2アクションゲームにおいて収束することを実験的に示す。また、従来のMARLアルゴリズムではゲームやNEを知らないと収束できなかった、困難なシャプレーゲームにおいても、本アルゴリズムが収束することを示した。さらに、100のエージェントが同時に相互作用して学習するというより現実的な設定において、WPLが最先端のアルゴリズムよりも優れていることを示します。MARLアルゴリズムの動作を理解する上で重要な側面は、アルゴリズムのダイナミクス、つまり、エージェントが互いに相互作用するにつれて、複数の学習エージェントのポリシーが時間の経過とともにどのように進化するかを分析することです。このような分析では、特定のMARLアルゴリズムを使用するエージェントが最終的に収束するかどうかを検証するだけでなく、収束前のMARLアルゴリズムの動作も明らかにします。私たちは、2プレイヤー2アクション ゲームでアルゴリズムを分析し、線形または区分線形ダイナミクスを持つ以前のMARLアルゴリズムとは異なり、WPLのダイナミクスの非線形性のために、WPLの収束を記号的に証明することが難しいことを示します。代わりに、WPLのダイナミクス微分方程式を数値的に解き、その解を以前のMARLアルゴリズムのダイナミクスと比較します。
AND/OR Multi-Valued Decision Diagrams (AOMDDs) for Graphical Models
グラフィカルモデルのためのAND/OR多値決定図（AOMDD）
Inspired by the recently introduced framework of AND/OR search spaces for graphical models, we propose to augment Multi-Valued Decision Diagrams (MDD) with AND nodes, in order to capture function decomposition structure and to extend these compiled data structures to general weighted graphical models (e.g., probabilistic models). We present the AND/OR Multi-Valued Decision Diagram (AOMDD) which compiles a graphical model into a canonical form that supports polynomial (e.g., solution counting, belief updating) or constant time (e.g. equivalence of graphical models) queries. We provide two algorithms for compiling the AOMDD of a graphical model. The first is search-based, and works by applying reduction rules to the trace of the memory intensive AND/OR search algorithm. The second is inference-based and uses a Bucket Elimination schedule to combine the AOMDDs of the input functions via the the APPLY operator. For both algorithms, the compilation time and the size of the AOMDD are, in the worst case, exponential in the treewidth of the graphical model, rather than pathwidth as is known for ordered binary decision diagrams (OBDDs). We introduce the concept of semantic treewidth, which helps explain why the size of a decision diagram is often much smaller than the worst case bound. We provide an experimental evaluation that demonstrates the potential of AOMDDs.
最近導入されたグラフィカルモデルのためのAND/OR探索空間のフレームワークに着想を得て、関数分解構造を捉え、これらのコンパイルされたデータ構造を一般的な重み付きグラフィカルモデル（例えば、確率モデル）に拡張するために、ANDノードを用いて多値決定図（MDD）を拡張することを提案します。我々は、グラフィカルモデルを多項式（解のカウント、確信の更新など）または定数時間（グラフィカルモデルの同値性など）のクエリをサポートする標準形式にコンパイルするAND/OR多値決定図（AOMDD）を紹介します。グラフィカルモデルのAOMDDをコンパイルするための2つのアルゴリズムを提供します。1つ目は検索ベースで、メモリ集約型のAND/OR検索アルゴリズムのトレースに縮約規則を適用することで機能します。2つ目は推論ベースで、バケット削除スケジュールを使用して、入力関数のAOMDDをAPPLY演算子を介して結合します。両方のアルゴリズムのコンパイル時間とAOMDDのサイズは、最悪の場合、順序付き2値決定図（OBDD）で知られているパス幅ではなく、グラフィカルモデルのツリー幅に対して指数関数的になります。我々は、決定図のサイズが最悪のケースの境界よりもはるかに小さくなることが多い理由を説明するために、意味ツリー幅の概念を導入します。AOMDDの可能性を示す実験的評価を提供します。
An Ordinal Bargaining Solution with Fixed-Point Property
固定小数点特性を持つ順序交渉解
Shapley’s impossibility result indicates that the two-person bargaining problem has no non-trivial ordinal solution with the traditional game-theoretic bargaining model. Although the result is no longer true for bargaining problems with more than two agents, none of the well known bargaining solutions are ordinal. Searching for meaningful ordinal solutions, especially for the bilateral bargaining problem, has been a challenging issue in bargaining theory for more than three decades. This paper proposes a logic-based ordinal solution to the bilateral bargaining problem. We argue that if a bargaining problem is modeled in terms of the logical relation of players’ physical negotiation items, a meaningful bargaining solution can be constructed based on the ordinal structure of bargainers’ preferences. We represent bargainers’ demands in propositional logic and bargainers’ preferences over their demands in total preorder. We show that the solution satisfies most desirable logical properties, such as individual rationality (logical version), consistency, collective rationality as well as a few typical game-theoretic properties, such as weak Pareto optimality and contraction invariance. In addition, if all players’ demand sets are logically closed, the solution satisfies a fixed-point condition, which says that the outcome of a negotiation is the result of mutual belief revision. Finally, we define various decision problems in relation to our bargaining model and study their computational complexity.
シャプレーの不可能性結果は、2人交渉問題には伝統的なゲーム理論的交渉モデルによる非自明な順序解が存在しないことを示しています。この結果は2人以上のエージェントとの交渉問題には当てはまりませんが、よく知られている交渉解はどれも順序解ではありません。特に双務交渉問題において、意味のある順序解の探索は、30年以上にわたり交渉理論における難題でした。本稿では、双務交渉問題に対する論理ベースの順序解を提案します。交渉問題をプレイヤーの物理的交渉商品の論理的関係でモデル化すれば、交渉者の選好の順序構造に基づいて意味のある交渉解を構築できると主張します。交渉者の要求を命題論理で、交渉者の要求に対する選好を全順序で表します。この解は、個人合理性（論理版）、一貫性、集団合理性といった最も望ましい論理特性に加え、弱パレート最適性や縮小不変性といったゲーム理論的に典型的な特性もいくつか満たしていることを示す。さらに、すべてのプレイヤーの需要集合が論理的に閉じている場合、この解は不動点条件を満たす。これは、交渉の結果は相互の信念の修正の結果であるという条件です。最後に、この交渉モデルに関連して様々な意思決定問題を定義し、それらの計算複雑性について考察します。
The Computational Complexity of Dominance and Consistency in CP-Nets
CPネットにおける支配性と一貫性の計算複雑性
We investigate the computational complexity of testing dominance and consistency in CP-nets. Previously, the complexity of dominance has been determined for restricted classes in which the dependency graph of the CP-net is acyclic. However, there are preferences of interest that define cyclic dependency graphs; these are modeled with general CP-nets. In our main results, we show here that both dominance and consistency for general CP-nets are PSPACE-complete. We then consider the concept of strong dominance, dominance equivalence and dominance incomparability, and several notions of optimality, and identify the complexity of the corresponding decision problems. The reductions used in the proofs are from STRIPS planning, and thus reinforce the earlier established connections between both areas.
我々は、CPネットにおける優位性と一貫性のテストの計算複雑性を調査します。これまで、優位性の複雑さは、CPネットの依存グラフが非巡回である制限されたクラスに対して決定されてきた。しかし、巡回依存グラフを定義する興味深い選好があり、これらは一般的なCPネットでモデル化されます。我々の主な結果では、一般的なCPネットの優位性と一貫性の両方がPSPACE完全であることを示す。次に、強い支配性、支配性の同値性、支配性の非比較不可能性、そしていくつかの最適性の概念を考察し、対応する意思決定問題の複雑さを明らかにします。証明に用いられる縮約はSTRIPS計画からのものであり、両分野間のこれまでの関連性を補強するものです。
Learning Partially Observable Deterministic Action Models
部分観測可能な決定論的行動モデルの学習
We present exact algorithms for identifying deterministic-actions’ effects and preconditions in dynamic partially observable domains. They apply when one does not know the action model(the way actions affect the world) of a domain and must learn it from partial observations over time. Such scenarios are common in real world applications. They are challenging for AI tasks because traditional domain structures that underly tractability (e.g., conditional independence) fail there (e.g., world features become correlated). Our work departs from traditional assumptions about partial observations and action models. In particular, it focuses on problems in which actions are deterministic of simple logical structure and observation models have all features observed with some frequency. We yield tractable algorithms for the modified problem for such domains. Our algorithms take sequences of partial observations over time as input, and output deterministic action models that could have lead to those observations. The algorithms output all or one of those models (depending on our choice), and are exact in that no model is misclassified given the observations. Our algorithms take polynomial time in the number of time steps and state features for some traditional action classes examined in the AI-planning literature, e.g., STRIPS actions. In contrast, traditional approaches for HMMs and Reinforcement Learning are inexact and exponentially intractable for such domains. Our experiments verify the theoretical tractability guarantees, and show that we identify action models exactly. Several applications in planning, autonomous exploration, and adventure-game playing already use these results. They are also promising for probabilistic settings, partially observable reinforcement learning, and diagnosis.
我々は、動的な部分観測領域における決定論的行動の効果と前提条件を特定するための正確なアルゴリズムを提示します。これらは、ドメインのアクションモデル（アクションが世界に与える影響）がわからず、時間とともに変化する部分的な観察からそれを学習する必要がある場合に適用されます。このようなシナリオは、現実世界のアプリケーションでは一般的です。扱いやすさの基盤となる従来のドメイン構造（条件付き独立性など）がそこで機能しない（世界の特徴が相関するなど）ため、AIタスクにとっては困難です。私たちの研究は、部分的な観察とアクションモデルに関する従来の仮定から逸脱しています。特に、アクションが単純な論理構造で決定論的であり、観察モデルにすべての特徴がある頻度で観察される問題に焦点を当てています。私たちは、そのようなドメインの修正された問題に対して扱いやすいアルゴリズムを生み出します。私たちのアルゴリズムは、時間とともに変化する部分的な観察のシーケンスを入力として受け取り、それらの観察につながる可能性のある決定論的なアクションモデルを出力します。アルゴリズムは（選択に応じて）それらのモデルのすべてまたは1つを出力し、観察が与えられた場合にモデルが誤分類されないという点で正確です。我々のアルゴリズムは、AIプランニングの文献で検討されているいくつかの従来のアクションクラス（例えば、STRIPSアクション）に対して、時間ステップ数と状態特徴数に関して多項式時間を要します。対照的に、HMMや強化学習に対する従来のアプローチは、そのような領域では不正確で指数関数的に扱いにくい。我々の実験は、理論的な扱いやすさの保証を検証し、我々がアクションモデルを正確に識別できることを示す。プランニング、自律探索、アドベンチャーゲームのプレイにおけるいくつかのアプリケーションでは、既にこれらの結果が利用されています。また、確率的設定、部分観測強化学習、診断にも有望です。
ICE: An Expressive Iterative Combinatorial Exchange
ICE：表現力豊かな反復的組合せ交換
We present the design and analysis of the first fully expressive, iterative combinatorial exchange (ICE). The exchange incorporates a tree-based bidding language (TBBL) that is concise and expressive for CEs. Bidders specify lower and upper bounds in TBBL on their value for different trades and refine these bounds across rounds. These bounds allow price discovery and useful preference elicitation in early rounds, and allow termination with an efficient trade despite partial information on bidder valuations. All computation in the exchange is carefully optimized to exploit the structure of the bid-trees and to avoid enumerating trades. A proxied interpretation of a revealed-preference activity rule, coupled with simple linear prices, ensures progress across rounds. The exchange is fully implemented, and we give results demonstrating several aspects of its scalability and economic properties with simulated bidding strategies.
我々は、初めて完全に表現力豊かな反復的組合せ交換（ICE）の設計と解析を提示します。この交換は、簡潔でCE（コンセンサス）に適した表現力豊かなツリーベース入札言語（TBBL）を採用しています。入札者は、異なる取引における自身の価値の下限と上限をTBBLで指定し、ラウンドをまたいでこれらの境界を精緻化します。これらの境界により、初期ラウンドでの価格発見と有用な選好の引き出しが可能になり、入札者の評価に関する情報が部分的であっても効率的な取引で終了することが可能になります。交換におけるすべての計算は、入札ツリーの構造を活用し、取引の列挙を回避するように慎重に最適化されています。顕在化された選好活動ルールの代理解釈と単純な線形価格の組み合わせにより、ラウンドをまたいでの進捗が保証されます。交換は完全に実装されており、シミュレーションによる入札戦略を用いて、そのスケーラビリティと経済特性のいくつかの側面を示す結果を示す。
Computational Logic Foundations of KGP Agents
KGPエージェントの計算論理的基礎
This paper presents the computational logic foundations of a model of agency called the KGP (Knowledge, Goals and Plan model. This model allows the specification of heterogeneous agents that can interact with each other, and can exhibit both proactive and reactive behaviour allowing them to function in dynamic environments by adjusting their goals and plans when changes happen in such environments. KGP provides a highly modular agent architecture that integrates a collection of reasoning and physical capabilities, synthesised within transitions that update the agent’s state in response to reasoning, sensing and acting. Transitions are orchestrated by cycle theories that specify the order in which transitions are executed while taking into account the dynamic context and agent preferences, as well as selection operators for providing inputs to transitions.
本論文では、KGP（知識、目標、計画モデル）と呼ばれるエージェンシーモデルの計算論理的基礎を提示します。このモデルは、相互に作用し、積極的かつ受動的な行動の両方を示す異種エージェントの仕様指定を可能にし、環境の変化に応じて目標と計画を調整することで、動的な環境で機能することを可能にします。KGPは、推論能力と身体能力の集合を統合した高度にモジュール化されたエージェントアーキテクチャを提供し、推論、感知、行動に応じてエージェントの状態を更新する遷移の中で合成されます。遷移は、動的コンテキストとエージェントの好みを考慮しながら遷移が実行される順序を指定するサイクル理論、および遷移への入力を提供する選択演算子によって調整されます。
On Similarities between Inference in Game Theory and Machine Learning
ゲーム理論と機械学習における推論の類似点について
In this paper, we elucidate the equivalence between inference in game theory and machine learning. Our aim in so doing is to establish an equivalent vocabulary between the two domains so as to facilitate developments at the intersection of both fields, and as proof of the usefulness of this approach, we use recent developments in each field to make useful improvements to the other. More specifically, we consider the analogies between smooth best responses in fictitious play and Bayesian inference methods. Initially, we use these insights to develop and demonstrate an improved algorithm for learning in games based on probabilistic moderation. That is, by integrating over the distribution of opponent strategies (a Bayesian approach within machine learning) rather than taking a simple empirical average (the approach used in standard fictitious play) we derive a novel moderated fictitious play algorithm and show that it is more likely than standard fictitious play to converge to a payoff-dominant but risk-dominated Nash equilibrium in a simple coordination game. Furthermore we consider the converse case, and show how insights from game theory can be used to derive two improved mean field variational learning algorithms. We first show that the standard update rule of mean field variational learning is analogous to a Cournot adjustment within game theory. By analogy with fictitious play, we then suggest an improved update rule, and show that this results in fictitious variational play, an improved mean field variational learning algorithm that exhibits better convergence in highly or strongly connected graphical models. Second, we use a recent advance in fictitious play, namely dynamic fictitious play, to derive a derivative action variational learning algorithm, that exhibits superior convergence properties on a canonical machine learning problem (clustering a mixture distribution).
本論文では、ゲーム理論と機械学習における推論の同等性を明らかにします。その目的は、両分野の交差点における発展を促進するために、両分野間で同等の語彙を確立することです。そして、このアプローチの有用性を証明するため、それぞれの分野における最近の進歩を用いて、他方の分野に有用な改善を加える。具体的には、架空プレイにおける滑らかな最善反応とベイズ推論手法の類似性を検討します。まず、これらの知見を用いて、確率的モデレーションに基づくゲーム学習のための改良アルゴリズムを開発し、その有効性を実証します。つまり、単純な経験的平均を取る（標準的な架空プレイで使用されるアプローチ）のではなく、対戦相手の戦略の分布を積分する（機械学習内のベイズ的アプローチ）ことで、新たな緩和された架空プレイアルゴリズムを導出し、単純な調整ゲームにおいて、標準的な架空プレイよりも、利得優位かつリスク優位のナッシュ均衡に収束する可能性が高くなることを示します。さらに、逆のケースを検討し、ゲーム理論からの洞察をどのように使用して、2つの改良された平均場変分学習アルゴリズムを導出できるかを示します。まず、平均場変分学習の標準的な更新規則が、ゲーム理論におけるクールノー調整に類似していることを示します。次に、架空プレイとの類推で、改良された更新規則を提案し、これが高度または強く連結されたグラフィカルモデルでより良好な収束を示す改良された平均場変分学習アルゴリズムである架空変分プレイにつながることを示します。第二に、我々は、仮想プレイにおける最近の進歩、すなわち動的仮想プレイを用いて、標準的な機械学習問題（混合分布のクラスタリング）において優れた収束特性を示す派生行動変分学習アルゴリズムを導出します。
Completeness and Performance Of The APO Algorithm
APOアルゴリズムの完全性と性能
Asynchronous Partial Overlay (APO) is a search algorithm that uses cooperative mediation to solve Distributed Constraint Satisfaction Problems (DisCSPs). The algorithm partitions the search into different subproblems of the DisCSP. The original proof of completeness of the APO algorithm is based on the growth of the size of the subproblems. The present paper demonstrates that this expected growth of subproblems does not occur in some situations, leading to a termination problem of the algorithm. The problematic parts in the APO algorithm that interfere with its completeness are identified and necessary modifications to the algorithm that fix these problematic parts are given. The resulting version of the algorithm, Complete Asynchronous Partial Overlay (CompAPO), ensures its completeness. Formal proofs for the soundness and completeness of CompAPO are given. A detailed performance evaluation of CompAPO comparing it to other DisCSP algorithms is presented, along with an extensive experimental evaluation of the algorithms unique behavior. Additionally, an optimization version of the algorithm, CompOptAPO, is presented, discussed, and evaluated.
非同期部分オーバーレイ（APO）は、協調的仲介を用いて分散制約充足問題（DisCSP）を解決する探索アルゴリズムです。このアルゴリズムは、探索をDisCSPの異なる部分問題に分割します。APOアルゴリズムの完全性は、元々、部分問題のサイズの増加に基づいて証明されていました。本論文では、この部分問題の予想される増加が状況によっては発生せず、アルゴリズムの停止問題につながることを実証しています。APOアルゴリズムにおいてその完全性を妨げる問題部分が特定され、これらの問題部分を修正するために必要なアルゴリズムの変更が示されています。結果として得られるアルゴリズムのバージョンであるComplete Asynchronous Partial Overlay (CompAPO)は、その完全性を保証します。CompAPOの健全性と完全性の形式的証明が示されています。他のDisCSPアルゴリズムと比較したCompAPOの詳細なパフォーマンス評価が提示され、アルゴリズム固有の動作の広範な実験評価も示されています。さらに、アルゴリズムの最適化バージョンであるCompOptAPOが提示され、議論され、評価されています。
A Rigorously Bayesian Beam Model and an Adaptive Full Scan Model for Range Finders in Dynamic Environments
動的環境におけるレンジファインダーのための厳密なベイズビームモデルと適応型フルスキャンモデル
This paper proposes and experimentally validates a Bayesian network model of a range finder adapted to dynamic environments. All modeling assumptions are rigorously explained, and all model parameters have a physical interpretation. This approach results in a transparent and intuitive model. With respect to the state of the art beam model this paper: (i) proposes a different functional form for the probability of range measurements caused by unmodeled objects, (ii) intuitively explains the discontinuity encountered in te state of the art beam model, and (iii) reduces the number of model parameters, while maintaining the same representational power for experimental data. The proposed beam model is called RBBM, short for Rigorously Bayesian Beam Model. A maximum likelihood and a variational Bayesian estimator (both based on expectation-maximization) are proposed to learn the model parameters.Furthermore, the RBBM is extended to a full scan model in two steps: first, to a full scan model for static environments and next, to a full scan model for general, dynamic environments. The full scan model accounts for the dependency between beams and adapts to the local sample density when using a particle filter. In contrast to Gaussian-based state of the art models, the proposed full scan model uses a sample-based approximation. This sample-based approximation enables handling dynamic environments and capturing multi-modality, which occurs even in simple static environments.
本稿では、動的環境に適応した測距儀のベイジアンネットワークモデルを提案し、実験的に検証します。すべてのモデリング仮定は厳密に説明されており、すべてのモデルパラメータには物理的な解釈が与えられています。このアプローチにより、透明で直感的なモデルが実現されます。最先端のビームモデルに関して、本稿は(i)モデル化されていない物体によって引き起こされる測距確率の異なる関数形を提案し、(ii)最先端のビームモデルで発生する不連続性を直感的に説明し、(iii)実験データに対する表現力を維持しながら、モデルパラメータの数を削減します。提案されたビームモデルは、Rigorously Bayesian Beam Model（RBBM）と呼ばれます。モデルパラメータを学習するために、最大尤度と変分ベイズ推定量（どちらも期待最大化に基づく）が提案されています。さらに、RBBMは2段階に分けてフルスキャンモデルに拡張されます。まず、静的環境用のフルスキャンモデル、次に一般的な動的環境用のフルスキャンモデルです。フルスキャンモデルは、ビーム間の依存関係を考慮し、粒子フィルタを使用する際に局所的なサンプル密度に適応します。ガウスベースの最先端モデルとは対照的に、提案されたフルスキャンモデルはサンプルベースの近似を使用します。このサンプルベースの近似により、動的環境の処理と、単純な静的環境でも発生するマルチモーダル性の捕捉が可能になります。
Complexity of Strategic Behavior in Multi-Winner Elections
複数当選者選挙における戦略的行動の複雑性
Although recent years have seen a surge of interest in the computational aspects of social choice, no specific attention has previously been devoted to elections with multiple winners, e.g., elections of an assembly or committee. In this paper, we characterize the worst-case complexity of manipulation and control in the context of four prominent multi-winner voting systems, under different formulations of the strategic agentâs goal.
近年、社会選択の計算論的側面への関心が高まっているものの、議会や委員会の選挙など、複数の勝者がいる選挙についてはこれまで特に注目されてこなかった。本稿では、戦略エージェントの目標を異なる定式化で定式化した場合、4つの主要な複数勝者投票システムの文脈において、操作と制御の最悪ケースの複雑性を特徴付ける。
Networks of Influence Diagrams: A Formalism for Representing Agents’ Beliefs and Decision-Making Processes
影響ネットワーク図：エージェントの信念と意思決定プロセスを表現するための形式論
This paper presents Networks of Influence Diagrams (NID), a compact, natural and highly expressive language for reasoning about agents’ beliefs and decision-making processes. NIDs are graphical structures in which agents’ mental models are represented as nodes in a network; a mental model for an agent may itself use descriptions of the mental models of other agents. NIDs are demonstrated by examples, showing how they can be used to describe conflicting and cyclic belief structures, and certain forms of bounded rationality. In an opponent modeling domain, NIDs were able to outperform other computational agents whose strategies were not known in advance. NIDs are equivalent in representation to Bayesian games but they are more compact and structured than this formalism. In particular, the equilibrium definition for NIDs makes an explicit distinction between agents’ optimal strategies, and how they actually behave in reality.
本稿では、エージェントの信念と意思決定プロセスを推論するための、コンパクトで自然かつ表現力豊かな言語であるネットワーク影響図(NID)を紹介します。NIDは、エージェントのメンタルモデルをネットワーク内のノードとして表現するグラフィカル構造です。エージェントのメンタルモデル自体が、他のエージェントのメンタルモデルの記述を使用できます。NIDは、矛盾する信念構造や循環的な信念構造、特定の限定合理性を記述するためにどのように使用できるかを示す例を用いて実証されます。対戦相手モデリング領域では、NIDは事前に戦略がわからない他の計算エージェントよりも優れたパフォーマンスを発揮しました。NIDはベイズゲームと表現上は同等ですが、この形式よりもコンパクトで構造化されています。特に、NIDの均衡定義は、エージェントの最適戦略と、エージェントが現実にどのように行動するかを明確に区別します。
Anytime Induction of Low-cost, Low-error Classifiers: a Sampling-based Approach
低コスト・低エラー分類器の常時誘導：サンプリングに基づくアプローチ
Machine learning techniques are gaining prevalence in the production of a wide range of classifiers for complex real-world applications with nonuniform testing and misclassification costs. The increasing complexity of these applications poses a real challenge to resource management during learning and classification. In this work we introduce ACT (anytime cost-sensitive tree learner), a novel framework for operating in such complex environments. ACT is an anytime algorithm that allows learning time to be increased in return for lower classification costs. It builds a tree top-down and exploits additional time resources to obtain better estimations for the utility of the different candidate splits. Using sampling techniques, ACT approximates the cost of the subtree under each candidate split and favors the one with a minimal cost. As a stochastic algorithm, ACT is expected to be able to escape local minima, into which greedy methods may be trapped. Experiments with a variety of datasets were conducted to compare ACT to the state-of-the-art cost-sensitive tree learners. The results show that for the majority of domains ACT produces significantly less costly trees. ACT also exhibits good anytime behavior with diminishing returns.
機械学習技術は、不均一なテストと誤分類コストを伴う複雑な実世界アプリケーション向けの幅広い分類器の作成において普及しつつあります。これらのアプリケーションの複雑さが増すにつれて、学習と分類中のリソース管理は真の課題となります。本研究では、このような複雑な環境で動作するための新しいフレームワークであるACT（いつでもコストセンシティブな木学習器）を紹介します。ACTは、学習時間を長くすることで分類コストを低減できるいつでも利用可能なアルゴリズムです。トップダウンで木を構築し、追加の時間リソースを活用して、さまざまな候補分割の効用をより正確に推定します。ACTはサンプリング技術を用いて、各候補分割の下のサブツリーのコストを近似し、コストが最小のものを優先します。ACTは確率的アルゴリズムであるため、貪欲法が陥りやすい局所最小値から脱出できると期待されています。様々なデータセットを用いた実験により、ACTと最先端のコスト感応型木学習器を比較しました。その結果、ACTはほとんどの領域において、大幅にコストの低い木を生成することが示されました。また、ACTは収穫逓減を伴う良好な常時挙動を示します。