Distributed Reasoning for Multiagent Simple Temporal Problems
マルチエージェントの単純な時間的問題に対する分散推論
This research focuses on building foundational algorithms for scheduling agents that assist people in managing their activities in environments where tempo and complex activity interdependencies outstrip people’s cognitive capacity. We address the critical challenge of reasoning over individuals’ interacting schedules to efficiently answer queries about how to meet scheduling goals while respecting individual privacy and autonomy to the extent possible. We formally define the Multiagent Simple Temporal Problem for naturally capturing and reasoning over the distributed but interconnected scheduling problems of multiple individuals. Our hypothesis is that combining bottom-up and top-down approaches will lead to effective solution techniques. In our bottom-up phase, an agent externalizes constraints that compactly summarize how its local subproblem affects other agents’ subproblems, whereas in our top-down phase an agent proactively constructs and internalizes new local constraints that decouple its subproblem from others’. We confirm this hypothesis by devising distributed algorithms that calculate summaries of the joint solution space for multiagent scheduling problems, without centralizing or otherwise redistributing the problems. The distributed algorithms permit concurrent execution to achieve significant speedup over the current art and also increase the level of privacy and independence in individual agent reasoning. These algorithms are most advantageous for problems where interactions between the agents are sparse compared to the complexity of agents’ individual problems.
本研究は、テンポや複雑な活動の相互依存性が人間の認知能力を凌駕する環境において、人々の活動管理を支援するスケジューリングエージェントのための基礎アルゴリズムの構築に焦点を当てています。我々は、個人のプライバシーと自律性を可能な限り尊重しながら、スケジューリング目標の達成方法に関する質問に効率的に回答するために、個人の相互作用するスケジュールを推論するという重要な課題に取り組みます。分散的でありながら相互に関連した複数の個人のスケジューリング問題を自然に捉え、推論するためのマルチエージェント単純時間問題（Multiagent Simple Temporal Problem）を正式に定義します。我々の仮説は、ボトムアップとトップダウンのアプローチを組み合わせることで効果的な解法が生まれるというものです。ボトムアップフェーズでは、エージェントは自身の局所的な部分問題が他のエージェントの部分問題にどのように影響するかを簡潔に要約する制約を外部化します。一方、トップダウンフェーズでは、エージェントは自身の部分問題を他のエージェントの部分問題から分離する新たな局所的制約を積極的に構築し、内部化します。我々は、問題を集中化したり再分散したりすることなく、マルチエージェントスケジューリング問題の共同解空間の要約を計算する分散アルゴリズムを考案することで、この仮説を検証します。分散アルゴリズムは同時実行を可能にし、現状技術に比べて大幅な高速化を実現するとともに、個々のエージェントの推論におけるプライバシーと独立性のレベルを向上させます。これらのアルゴリズムは、エージェント間の相互作用が個々のエージェントの問題の複雑さに比べて疎である問題に最も有利です。
Framing Image Description as a Ranking Task: Data, Models and Evaluation Metrics
画像記述をランキングタスクとしてフレーミングする：データ、モデル、評価指標
The ability to associate images with natural language sentences that describe what is depicted in them is a hallmark of image understanding, and a prerequisite for applications such as sentence-based image search. In analogy to image search, we propose to frame sentence-based image annotation as the task of ranking a given pool of captions. We introduce a new benchmark collection for sentence-based image description and search, consisting of 8,000 images that are each paired with five different captions which provide clear descriptions of the salient entities and events. We introduce a number of systems that perform quite well on this task, even though they are only based on features that can be obtained with minimal supervision. Our results clearly indicate the importance of training on multiple captions per image, and of capturing syntactic (word order-based) and semantic features of these captions. We also perform an in-depth comparison of human and automatic evaluation metrics for this task, and propose strategies for collecting human judgments cheaply and on a very large scale, allowing us to augment our collection with additional relevance judgments of which captions describe which image. Our analysis shows that metrics that consider the ranked list of results for each query image or sentence are significantly more robust than metrics that are based on a single response per query. Moreover, our study suggests that the evaluation of ranking-based image description systems may be fully automated.
画像と、そこに描かれているものを記述する自然言語文を関連付ける能力は、画像理解の特徴であり、文ベースの画像検索などのアプリケーションの前提条件です。画像検索と同様に、我々は文ベースの画像アノテーションを、与えられたキャプションのプールをランク付けするタスクとして捉えることを提案します。我々は、文ベースの画像記述と検索のための新しいベンチマークコレクションを導入します。これは、それぞれが5つの異なるキャプションとペアになっており、主要なエンティティとイベントを明確に記述する8,000枚の画像で構成されます。我々は、最小限の監督で得られる特徴に基づいているだけであるにもかかわらず、このタスクで非常に良いパフォーマンスを発揮するいくつかのシステムを紹介します。我々の結果は、画像ごとに複数のキャプションのトレーニングと、これらのキャプションの統語的（語順ベース）および意味的特徴を捕捉することの重要性を明確に示しています。我々はまた、このタスクに対する人間と自動の評価メトリクスの詳細な比較を行い、人間の判断を安価かつ非常に大規模に収集する戦略を提案し、どのキャプションがどの画像を説明しているかについての追加の関連性判断でコレクションを増強することができます。我々の分析は、各クエリ画像または文に対する結果のランク付けされたリストを考慮するメトリクスは、クエリごとに単一の応答に基づくメトリクスよりもはるかに堅牢であることを示す。さらに、我々の研究は、ランク付けに基づく画像記述システムの評価は完全に自動化できる可能性があることを示唆しています。
A Decidable Extension of SROIQ with Complex Role Chains and Unions
複雑な役割連鎖と結合を用いたSROIQの決定可能な拡張
We design a decidable extension of the description logic SROIQ underlying the Web Ontology Language OWL 2. The new logic, called SR+OIQ, supports a controlled use of role axioms whose right-hand side may contain role chains or role unions. We give a tableau algorithm for checking concept satisfiability with respect to SR+OIQ ontologies and prove its soundness, completeness and termination.
我々は、Webオントロジー言語OWL 2の基盤となる記述論理SROIQの決定可能な拡張を設計します。SR+OIQと呼ばれるこの新しい論理は、右辺に役割連鎖または役割和集合を含む可能性のある役割公理の制御された使用をサポートします。我々は、SR+OIQオントロジーに関して概念の充足可能性を検証するためのタブローアルゴリズムを提供し、その健全性、完全性、および停止性を証明した。
Acyclicity Notions for Existential Rules and Their Application to Query Answering in Ontologies
存在規則の非巡回性概念とオントロジーにおけるクエリ応答への応用
Answering conjunctive queries (CQs) over a set of facts extended with existential rules is a prominent problem in knowledge representation and databases. This problem can be solved using the chase algorithm, which extends the given set of facts with fresh facts in order to satisfy the rules. If the chase terminates, then CQs can be evaluated directly in the resulting set of facts. The chase, however, does not terminate necessarily, and checking whether the chase terminates on a given set of rules and facts is undecidable. Numerous acyclicity notions were proposed as sufficient conditions for chase termination. In this paper, we present two new acyclicity notions called model-faithful acyclicity (MFA) and model-summarising acyclicity (MSA). Furthermore, we investigate the landscape of the known acyclicity notions and establish a complete taxonomy of all notions known to us. Finally, we show that MFA and MSA generalise most of these notions.Existential rules are closely related to the Horn fragments of the OWL 2 ontology language; furthermore, several prominent OWL 2 reasoners implement CQ answering by using the chase to materialise all relevant facts. In order to avoid termination problems, many of these systems handle only the OWL 2 RL profile of OWL 2; furthermore, some systems go beyond OWL 2 RL, but without any termination guarantees. In this paper we also investigate whether various acyclicity notions can provide a principled and practical solution to these problems. On the theoretical side, we show that query answering for acyclic ontologies is of lower complexity than for general ontologies. On the practical side, we show that many of the commonly used OWL 2 ontologies are MSA, and that the number of facts obtained by materialisation is not too large. Our results thus suggest that principled development of materialisation-based OWL 2 reasoners is practically feasible.
存在規則で拡張された事実の集合に対する連言クエリ（CQ）への回答は、知識表現とデータベースにおける重要な問題です。この問題は、ルールを満たすように、与えられた事実の集合を新しい事実で拡張するチェイスアルゴリズムを用いて解決できます。チェイスが終了した場合、結果の事実の集合においてCQを直接評価することができます。しかし、チェイスは必ずしも終了するわけではなく、与えられたルールと事実の集合でチェイスが終了するかどうかをチェックすることは決定不能です。チェイスの終了に必要な条件として、数多くの非巡回性の概念が提案されています。本稿では、モデル忠実非巡回性（MFA）とモデル要約非巡回性（MSA）という2つの新しい非巡回性の概念を提示します。さらに、既知の非巡回性の概念のランドスケープを調査し、既知のすべての概念の完全な分類を確立します。最後に、MFAとMSAがこれらの概念のほとんどを一般化することを示します。存在規則は、OWL 2オントロジー言語のHornフラグメントと密接に関連しています。さらに、いくつかの有名なOWL 2推論システムは、すべての関連する事実を具体化するためにチェイスを使用してCQ回答を実装しています。終了問題を回避するために、これらのシステムの多くはOWL 2のOWL 2 RLプロファイルのみを処理します。さらに、一部のシステムはOWL 2 RLを超えていますが、終了保証はありません。この論文では、さまざまな非巡回性の概念がこれらの問題に対する原理的かつ実用的な解決策を提供できるかどうかも調査します。理論面では、非巡回オントロジーのクエリ回答は、一般的なオントロジーよりも複雑性が低いことを示します。実際面では、一般的に使用されているOWL 2オントロジーの多くがMSAであり、具体化によって取得される事実の数がそれほど多くないことを示します。したがって、私たちの結果は、具体化ベースのOWL 2推論システムの原理的な開発が実際に実現可能であることを示唆しています。
Identifying the Class of Maxi-Consistent Operators in Argumentation
議論における最大一貫性演算子のクラスの特定
Dungs abstract argumentation theory can be seen as a general framework for non-monotonic reasoning. An important question is then: what is the class of logics that can be subsumed as instantiations of this theory? The goal of this paper is to identify and study the large class of logic-based instantiations of Dungs theory which correspond to the maxi-consistent operator, i.e. to the function which returns maximal consistent subsets of an inconsistent knowledge base. In other words, we study the class of instantiations where very extension of the argumentation system corresponds to exactly one maximal consistent subset of the knowledge base. We show that an attack relation belonging to this class must be conflict-dependent, must not be valid, must not be conflict-complete, must not be symmetric etc. Then, we show that some attack relations serve as lower or upper bounds of the class (e.g. if an attack relation contains canonical undercut then it is not a member of this class). By using our results, we show for all existing attack relations whether or not they belong to this class. We also define new attack relations which are members of this class. Finally, we interpret our results and discuss more general questions, like: what is the added value of argumentation in such a setting? We believe that this work is a first step towards achieving our long-term goal, which is to better understand the role of argumentation and, particularly, the expressivity of logic-based instantiations of Dung-style argumentation frameworks.
Dungsの抽象論証理論は、非単調推論の一般的な枠組みと見なすことができます。そこで重要な疑問は、この理論のインスタンス化として包含され得る論理のクラスは何か、ということです。本論文の目的は、最大無矛盾演算子、すなわち、矛盾する知識ベースの最大無矛盾な部分集合を返す関数に対応する、Dungs理論の論理に基づくインスタンス化の大規模なクラスを特定し、研究することです。言い換えれば、我々は、議論システムの拡張そのものが知識ベースの最大一貫性部分集合のちょうど一つに対応するインスタンス化のクラスを研究します。このクラスに属する攻撃関係は、衝突依存的、妥当ではない、衝突完全ではない、対称的ではないなどであることを示す。次に、一部の攻撃関係がこのクラスの下限または上限として機能することを示す（例えば、攻撃関係が標準的なアンダーカットを含む場合、それはこのクラスのメンバーではない）。我々の結果を用いて、既存のすべての攻撃関係がこのクラスに属するかどうかを示す。また、このクラスのメンバーとなる新しい攻撃関係も定義します。最後に、我々の結果を解釈し、より一般的な疑問、例えば「このような状況における議論の付加価値とは何か？」といった疑問について議論します。この研究は、議論の役割、特にDung型議論フレームワークの論理に基づくインスタンス化の表現力をより深く理解するという、我々の長期目標の達成に向けた第一歩であると考えています。
Heuristic Search When Time Matters
時間的制約を考慮したヒューリスティック探索
In many applications of shortest-path algorithms, it is impractical to find a provably optimal solution; one can only hope to achieve an appropriate balance between search time and solution cost that respects the user’s preferences. Preferences come in many forms; we consider utility functions that linearly trade-off search time and solution cost. Many natural utility functions can be expressed in this form. For example, when solution cost represents the makespan of a plan, equally weighting search time and plan makespan minimizes the time from the arrival of a goal until it is achieved. Current state-of-the-art approaches to optimizing utility functions rely on anytime algorithms, and the use of extensive training data to compute a termination policy. We propose a more direct approach, called Bugsy, that incorporates the utility function directly into the search, obviating the need for a separate termination policy. We describe a new method based on off-line parameter tuning and a novel benchmark domain for planning under time pressure based on platform-style video games. We then present what we believe to be the first empirical study of applying anytime monitoring to heuristic search, and we compare it with our proposals. Our results suggest that the parameter tuning technique can give the best performance if a representative set of training instances is available. If not, then Bugsy is the algorithm of choice, as it performs well and does not require any off-line training. This work extends the tradition of research on metareasoning for search by illustrating the benefits of embedding lightweight reasoning about time into the search algorithm itself.
最短経路アルゴリズムの多くの応用において、証明可能な最適解を見つけることは現実的ではありません。ユーザーの嗜好を考慮しつつ、探索時間とコストの適切なバランスを達成することしか期待できません。嗜好は様々な形で現れます。本稿では、探索時間とコストを線形にトレードオフする効用関数を考察します。多くの自然な効用関数は、この形で表現できます。例えば、コストが計画の所要時間を表す場合、探索時間と計画の所要時間を均等に重み付けすることで、目標到達から目標達成までの時間を最小化できます。現在、効用関数を最適化する最先端の手法は、いつでも実行可能なアルゴリズムと、膨大な学習データを用いた終了ポリシーの計算に依存しています。本稿では、Bugsyと呼ばれるより直接的な手法を提案します。これは、効用関数を探索に直接組み込むことで、別途終了ポリシーを用意する必要がなくなります。本稿では、オフラインパラメータチューニングに基づく新しい手法と、プラットフォーム型ビデオゲームに基づく時間制約下での計画のための新たなベンチマークドメインについて説明します。次に、いつでもモニタリングをヒューリスティック探索に適用した、我々が考える初の実証研究を提示し、それを我々の提案と比較します。結果は、代表的な訓練インスタンスセットが利用可能な場合、パラメータ調整手法が最高のパフォーマンスを発揮できることを示唆しています。そうでない場合、優れたパフォーマンスを発揮し、オフライン訓練を必要としないBugsyアルゴリズムが最適な選択肢となります。本研究は、時間に関する軽量な推論を探索アルゴリズム自体に組み込むことの利点を示すことで、探索のためのメタ推論研究の伝統を拡張するものです。
Protecting Privacy through Distributed Computation in Multi-agent Decision Making
マルチエージェント意思決定における分散計算によるプライバシー保護
As large-scale theft of data from corporate servers is becoming increasingly common, it becomes interesting to examine alternatives to the paradigm of centralizing sensitive data into large databases. Instead, one could use cryptography and distributed computation so that sensitive data can be supplied and processed in encrypted form, and only the final result is made known. In this paper, we examine how such a paradigm can be used to implement constraint satisfaction, a technique that can solve a broad class of AI problems such as resource allocation, planning, scheduling, and diagnosis. Most previous work on privacy in constraint satisfaction only attempted to protect specific types of information, in particular the feasibility of particular combinations of decisions. We formalize and extend these restricted notions of privacy by introducing four types of private information, including the feasibility of decisions and the final decisions made, but also the identities of the participants and the topology of the problem. We present distributed algorithms that allow computing solutions to constraint satisfaction problems while maintaining these four types of privacy. We formally prove the privacy properties of these algorithms, and show experiments that compare their respective performance on benchmark problems.
企業サーバーからの大規模なデータ盗難がますます一般的になるにつれて、機密データを大規模データベースに集中させるパラダイムの代替案を検討することは興味深いものになっています。代わりに、暗号化と分散コンピューティングを使用して、機密データを暗号化された形式で提供および処理し、最終結果のみを公開することができます。本論文では、このようなパラダイムを使用して、リソース割り当て、計画、スケジューリング、診断など、幅広いAI問題を解決できる手法である制約充足をどのように実装できるかを検討します。制約充足におけるプライバシーに関するこれまでの研究のほとんどは、特定の種類の情報、特に特定の決定の組み合わせの実現可能性のみを保護することを試みてきました。本研究では、決定の実現可能性と最終的な決定、そして参加者の身元と問題のトポロジーを含む4種類のプライバシー情報を導入することで、これらの限定的なプライバシーの概念を形式化し拡張します。本研究では、これら4種類のプライバシーを維持しながら制約充足問題の解を計算する分散アルゴリズムを提示します。これらのアルゴリズムのプライバシー特性を正式に証明し、ベンチマーク問題におけるそれぞれのパフォーマンスを比較する実験を示します。
Asymmetric Distributed Constraint Optimization Problems
非対称分散制約最適化問題
Distributed Constraint Optimization (DCOP) is a powerful framework for representing and solving distributed combinatorial problems, where the variables of the problem are owned by different agents. Many multi-agent problems include constraints that produce different gains (or costs) for the participating agents. Asymmetric gains of constrained agents cannot be naturally represented by the standard DCOP model.The present paper proposes a general framework for Asymmetric DCOPs (ADCOPs). In ADCOPs different agents may have different valuations for constraints that they are involved in. The new framework bridges the gap between multi-agent problems which tend to have asymmetric structure and the standard symmetric DCOP model. The benefits of the proposed model over previous attempts to generalize the DCOP model are discussed and evaluated.Innovative algorithms that apply to the special properties of the proposed ADCOP model are presented in detail. These include complete algorithms that have a substantial advantage in terms of runtime and network load over existing algorithms (for standard DCOPs) which use alternative representations. Moreover, standard incomplete algorithms (i.e., local search algorithms) are inapplicable to the existing DCOP representations of asymmetric constraints and when they are applied to the new ADCOP framework they often fail to converge to a local optimum and yield poor results. The local search algorithms proposed in the present paper converge to high quality solutions. The experimental evidence that is presented reveals that the proposed local search algorithms for ADCOPs achieve high quality solutions while preserving a high level of privacy.
分散制約最適化（DCOP）は、問題の変数が複数のエージェントによって所有される分散型組合せ問題を表現および解くための強力なフレームワークです。多くのマルチエージェント問題には、参加エージェントに異なるゲイン（またはコスト）をもたらす制約が含まれます。制約付きエージェントの非対称ゲインは、標準的なDCOPモデルでは自然に表現できません。本論文では、非対称DCOP（ADCOP）のための一般的なフレームワークを提案します。ADCOPでは、異なるエージェントが、関与する制約に対して異なる評価を持つ場合があります。この新しいフレームワークは、非対称構造になりがちなマルチエージェント問題と、標準的な対称DCOPモデルとの間のギャップを埋めます。DCOPモデルの一般化を試みたこれまでの試みに対する、提案モデルの利点について考察し、評価します。提案ADCOPモデルの特殊な特性に適用される革新的なアルゴリズムについても詳細に示します。これらのアルゴリズムには、代替表現を使用する既存のアルゴリズム（標準的なDCOP用）と比較して、実行時間とネットワーク負荷の点で大幅な優位性を持つ完全なアルゴリズムが含まれます。さらに、標準的な不完全なアルゴリズム（すなわち、局所探索アルゴリズム）は、既存の非対称制約のDCOP表現には適用できず、新しいADCOPフレームワークに適用すると、局所最適解に収束せず、悪い結果をもたらすことがよくあります。本論文で提案する局所探索アルゴリズムは、高品質の解に収束します。提示された実験的証拠は、提案されたADCOPの局所探索アルゴリズムが、高いレベルのプライバシーを維持しながら高品質の解を達成することを示しています。
A Refined View of Causal Graphs and Component Sizes: SP-Closed Graph Classes and Beyond
因果グラフとコンポーネントサイズの洗練された視点：SP閉グラフクラスとその先へ
The causal graph of a planning instance is an important tool for planning both in practice and in theory. The theoretical studies of causal graphs have largely analysed the computational complexity of planning for instances where the causal graph has a certain structure, often in combination with other parameters like the domain size of the variables. Chen and Giménez ignored even the structure and considered only the size of the weakly connected components. They proved that planning is tractable if the components are bounded by a constant and otherwise intractable. Their intractability result was, however, conditioned by an assumption from parameterised complexity theory that has no known useful relationship with the standard complexity classes. We approach the same problem from the perspective of standard complexity classes, and prove that planning is NP-hard for classes with unbounded components under an additional restriction we refer to as SP-closed. We then argue that most NP-hardness theorems for causal graphs are difficult to apply and, thus, prove a more general result; even if the component sizes grow slowly and the class is not densely populated with graphs, planning still cannot be tractable unless the polynomial hierachy collapses. Both these results still hold when restricted to the class of acyclic causal graphs. We finally give a partial characterization of the borderline between NP-hard and NP-intermediate classes, giving further insight into the problem.
プランニングインスタンスの因果グラフは、理論と実践の両方においてプランニングを行うための重要なツールです。因果グラフの理論的研究は主に、因果グラフが特定の構造を持ち、多くの場合変数のドメインサイズなどの他のパラメータと組み合わされているインスタンスのプランニングの計算複雑性を分析してきました。ChenとGiménezは構造さえも無視し、弱連結成分のサイズのみを考慮しました。彼らは、成分が定数で制限され、それ以外は制御不能である場合にプランニングが制御可能であることを証明しました。しかし、彼らの制御不能性の結果は、標準的な制御不能性クラスとの有用な関係が知られていない、パラメータ化された制御不能性理論の仮定によって条件付けられていました。私たちは同じ問題に標準的な制御不能性クラスの観点からアプローチし、SP閉と呼ばれる追加の制約の下で、無制限の成分を持つクラスに対してプランニングがNP困難であることを証明します。次に、因果グラフのNP困難性定理のほとんどが適用困難であることを示し、より一般的な結果を証明します。たとえコンポーネントサイズがゆっくりと増加し、クラスがグラフで密集していない場合でも、多項式階層が崩壊しない限り、プランニングは依然として実行可能ではありません。これらの結果は、非巡回因果グラフのクラスに限定しても成立します。最後に、NP困難クラスとNP中間クラスの境界について部分的な特徴付けを行い、問題へのさらなる洞察を提供します。
Topic Segmentation and Labeling in Asynchronous Conversations
非同期会話におけるトピックのセグメンテーションとラベリング
Topic segmentation and labeling is often considered a prerequisite for higher-level conversation analysis and has been shown to be useful in many Natural Language Processing (NLP) applications. We present two new corpora of email and blog conversations annotated with topics, and evaluate annotator reliability for the segmentation and labeling tasks in these asynchronous conversations. We propose a complete computational framework for topic segmentation and labeling in asynchronous conversations. Our approach extends state-of-the-art methods by considering a fine-grained structure of an asynchronous conversation, along with other conversational features by applying recent graph-based methods for NLP. For topic segmentation, we propose two novel unsupervised models that exploit the fine-grained conversational structure, and a novel graph-theoretic supervised model that combines lexical, conversational and topic features. For topic labeling, we propose two novel (unsupervised) random walk models that respectively capture conversation specific clues from two different sources: the leading sentences and the fine-grained conversational structure. Empirical evaluation shows that the segmentation and the labeling performed by our best models beat the state-of-the-art, and are highly correlated with human annotations.
トピックのセグメンテーションとラベリングは、高レベル会話分析の前提条件とみなされることが多く、多くの自然言語処理（NLP）アプリケーションで有用であることが示されています。我々は、トピックが注釈された電子メールとブログの会話の新しいコーパスを2つ提示し、これらの非同期会話におけるセグメンテーションとラベル付けのタスクに対する注釈者の信頼性を評価します。非同期会話におけるトピックのセグメンテーションとラベル付けのための完全な計算フレームワークを提案します。我々のアプローチは、非同期会話の細粒度構造と、最近のNLPのグラフベース手法を適用した他の会話特徴を考慮することで、最先端の手法を拡張します。トピックセグメンテーションについては、細粒度会話構造を活用する2つの新しい教師なしモデルと、語彙、会話、トピックの特徴を組み合わせた新しいグラフ理論的教師ありモデルを提案します。トピックラベル付けについては、2つの異なるソース（リーディングセンテンスと細粒度会話構造）からそれぞれ会話固有の手がかりを捕捉する2つの新しい（教師なし）ランダムウォークモデルを提案します。実証的評価により、我々の最良のモデルによって実行されたセグメンテーションとラベル付けは最先端のものを上回り、人間による注釈と高い相関関係にあることが示されました。
On the Computation of Fully Proportional Representation
完全比例代表の計算について
We investigate two systems of fully proportional representation suggested by Chamberlin Courant and Monroe. Both systems assign a representative to each voter so that the “sum of misrepresentations” is minimized. The winner determination problem for both systems is known to be NP-hard, hence this work aims at investigating whether there are variants of the proposed rules and/or specific electorates for which these problems can be solved efficiently. As a variation of these rules, instead of minimizing the sum of misrepresentations, we considered minimizing the maximal misrepresentation introducing effectively two new rules. In the general case these “minimax” versions of classical rules appeared to be still NP-hard. We investigated the parameterized complexity of winner determination of the two classical and two new rules with respect to several parameters. Here we have a mixture of positive and negative results: e.g., we proved fixed-parameter tractability for the parameter the number of candidates but fixed-parameter intractability for the number of winners.For single-peaked electorates our results are overwhelmingly positive: we provide polynomial-time algorithms for most of the considered problems. The only rule that remains NP-hard for single-peaked electorates is the classical Monroe rule.
本研究では、Chamberlin CourantとMonroeによって提案された2つの完全比例代表制を検証します。どちらの制度も、「不当表示の合計」が最小化されるように、各有権者に代表者を割り当てます。両制度の勝者決定問題はNP困難であることが知られているため、本研究では、提案されたルールの変種や、これらの問題を効率的に解くことができる特定の選挙区が存在するかどうかを調査することを目的とします。これらの規則のバリエーションとして、誤表現の合計を最小化する代わりに、実質的に2つの新しい規則を導入することで、誤表現の最大化を最小化することを考えました。一般的なケースでは、これらの古典的な規則の「ミニマックス」版は依然としてNP困難であるように見えました。2つの古典的な規則と2つの新しい規則について、勝者決定のパラメータ化された複雑性をいくつかのパラメータに関して調査しました。ここでは、肯定的な結果と否定的な結果が混在しています。例えば、候補者数というパラメータについては固定パラメータで扱いやすいことを証明しましたが、勝者数については固定パラメータで扱いにくいことを証明しました。単峰性の選挙区については、私たちの結果は圧倒的に肯定的であり、検討した問題のほとんどに対して多項式時間アルゴリズムを提供します。単峰性の選挙区に対してNP困難のままである唯一の規則は、古典的なモンロー規則です。
Decentralized Anti-coordination Through Multi-agent Learning
マルチエージェント学習による分散型反協調
To achieve an optimal outcome in many situations, agents need to choose distinct actions from one another. This is the case notably in many resource allocation problems, where a single resource can only be used by one agent at a time. How shall a designer of a multi-agent system program its identical agents to behave each in a different way?From a game theoretic perspective, such situations lead to undesirable Nash equilibria. For example consider a resource allocation game in that two players compete for an exclusive access to a single resource. It has three Nash equilibria. The two pure-strategy NE are efficient, but not fair. The one mixed-strategy NE is fair, but not efficient. Aumann’s notion of correlated equilibrium fixes this problem: It assumes a correlation device that suggests each agent an action to take.However, such a “smart” coordination device might not be available. We propose using a randomly chosen, “stupid” integer coordination signal. “Smart” agents learn which action they should use for each value of the coordination signal.We present a multi-agent learning algorithm that converges in polynomial number of steps to a correlated equilibrium of a channel allocation game, a variant of the resource allocation game. We show that the agents learn to play for each coordination signal value a randomly chosen pure-strategy Nash equilibrium of the game. Therefore, the outcome is an efficient correlated equilibrium. This CE becomes more fair as the number of the available coordination signal values increases.
多くの状況において最適な結果を得るためには、エージェントは互いに異なる行動を選択する必要があります。これは、多くの資源配分問題において特に顕著で、単一の資源は一度に1つのエージェントしか利用できません。マルチエージェントシステムの設計者は、同一のエージェントがそれぞれ異なる行動をとるようにどのようにプログラムすればよいでしょうか？ゲーム理論の観点から見ると、このような状況は望ましくないナッシュ均衡をもたらします。例えば、2人のプレイヤーが単一の資源への排他的アクセスを競う資源配分ゲームを考えてみましょう。このゲームには3つのナッシュ均衡があります。2つの純粋戦略のナッシュ均衡は効率的ですが、公平ではありません。1つの混合戦略のナッシュ均衡は公平ですが、効率的ではありません。オーマンの相関均衡の概念は、この問題を解決します。これは、各エージェントに取るべき行動を提案する相関デバイスを前提としています。しかし、そのような「スマートな」調整デバイスは利用できない可能性があります。そこで、ランダムに選択された「愚かな」整数調整信号を使用することを提案します。「賢い」エージェントは、調整信号の各値に対して、どの行動を取るべきかを学習します。本研究では、資源配分ゲームの変種であるチャネル配分ゲームの相関均衡に多項式ステップで収束するマルチエージェント学習アルゴリズムを提示します。エージェントは、各調整信号値に対して、ゲームのランダムに選択された純粋戦略ナッシュ均衡をプレイすることを学習することを示します。したがって、結果は効率的な相関均衡となります。この相関均衡は、利用可能な調整信号値の数が増えるほど公平になります。
Lifted Variable Elimination: Decoupling the Operators from the Constraint Language
持ち上げられた変数の除去：演算子と制約言語の分離
Lifted probabilistic inference algorithms exploit regularities in the structure of graphical models to perform inference more efficiently. More specifically, they identify groups of interchangeable variables and perform inference once per group, as opposed to once per variable. The groups are defined by means of constraints, so the flexibility of the grouping is determined by the expressivity of the constraint language. Existing approaches for exact lifted inference use specific languages for (in)equality constraints, which often have limited expressivity. In this article, we decouple lifted inference from the constraint language. We define operators for lifted inference in terms of relational algebra operators, so that they operate on the semantic level (the constraints’ extension) rather than on the syntactic level, making them language-independent. As a result, lifted inference can be performed using more powerful constraint languages, which provide more opportunities for lifting. We empirically demonstrate that this can improve inference efficiency by orders of magnitude, allowing exact inference where until now only approximate inference was feasible.
リフトされた確率推論アルゴリズムは、グラフィカルモデルの構造における規則性を利用して、より効率的に推論を実行します。より具体的には、交換可能な変数のグループを識別し、変数ごとに1回ではなく、グループごとに1回推論を実行します。グループは制約によって定義されるため、グループ化の柔軟性は制約言語の表現力によって決まります。既存の正確なリフトされた推論のアプローチでは、（不）等式制約に特定の言語が使用されていますが、その表現力は限られていることがよくあります。本稿では、リフトされた推論を制約言語から分離します。リフトされた推論の演算子を関係代数演算子で定義することで、構文レベルではなく意味レベル（制約の拡張）で動作するようにし、言語に依存しないようにします。その結果、リフトされた推論はより強力な制約言語を使用して実行できるようになり、より多くのリフティングの機会が提供されます。これにより推論効率が桁違いに向上し、これまでは近似推論しか実行できなかった場合でも正確な推論が可能になることを経験的に実証しました。
Strong Equivalence of Qualitative Optimization Problems
定性最適化問題の強同値性
We introduce the framework of qualitative optimization problems (or, simply, optimization problems) to represent preference theories. The formalism uses separate modules to describe the space of outcomes to be compared (the generator) and the preferences on outcomes (the selector). We consider two types of optimization problems. They differ in the way the generator, which we model by a propositional theory, is interpreted: by the standard propositional logic semantics, and by the equilibrium-model (answer-set) semantics. Under the latter interpretation of generators, optimization problems directly generalize answer-set optimization programs proposed previously. We study strong equivalence of optimization problems, which guarantees their interchangeability within any larger context. We characterize several versions of strong equivalence obtained by restricting the class of optimization problems that can be used as extensions and establish the complexity of associated reasoning tasks. Understanding strong equivalence is essential for modular representation of optimization problems and rewriting techniques to simplify them without changing their inherent properties.
選好理論を表現するために、定性最適化問題（または単に最適化問題）の枠組みを導入します。この形式主義では、比較対象となる結果の空間（生成器）と結果に対する選好（選択器）を記述するために、別々のモジュールを使用します。本研究では2種類の最適化問題を考察します。これらは、命題理論によってモデル化された生成器の解釈方法が異なります。標準的な命題論理意味論と、均衡モデル（解集合）意味論です。後者の生成器の解釈では、最適化問題は、以前に提案された解集合最適化プログラムを直接一般化します。本研究では、最適化問題の強同値性を研究します。これは、あらゆるより大きな文脈においてそれらの互換性を保証します。拡張として使用できる最適化問題のクラスを制限することで得られる強同値の複数のバージョンを特徴付け、関連する推論タスクの複雑性を確立します。強同値性の理解は、最適化問題のモジュール表現と、その固有の特性を変えずに問題を単純化する書き換え手法にとって不可欠です。
Scheduling a Dynamic Aircraft Repair Shop with Limited Repair Resources
限られた修理リソースによる動的航空機修理工場のスケジューリング
We address a dynamic repair shop scheduling problem in the context of military aircraft fleet management where the goal is to maintain a full complement of aircraft over the long-term. A number of flights, each with a requirement for a specific number and type of aircraft, are already scheduled over a long horizon. We need to assign aircraft to flights and schedule repair activities while considering the flights requirements, repair capacity, and aircraft failures. The number of aircraft awaiting repair dynamically changes over time due to failures and it is therefore necessary to rebuild the repair schedule online. To solve the problem, we view the dynamic repair shop as successive static repair scheduling sub-problems over shorter time periods. We propose a complete approach based on the logic-based Benders decomposition to solve the static sub-problems, and design different rescheduling policies to schedule the dynamic repair shop. Computational experiments demonstrate that the Benders model is able to find and prove optimal solutions on average four times faster than a mixed integer programming model. The rescheduling approach having both aspects of scheduling over a longer horizon and quickly adjusting the schedule increases aircraft available in the long term by 10% compared to the approaches having either one of the aspects alone.
軍用機群管理の文脈において、長期にわたって航空機の完全な配備を維持することを目標とする動的修理工場スケジューリング問題を取り上げます。複数のフライトが既に予定されており、それぞれに特定の数と種類の航空機が必要です。フライトの要件、修理能力、および航空機の故障を考慮しながら、航空機をフライトに割り当て、修理活動をスケジュールする必要があります。修理を待つ航空機の数は故障により時間の経過とともに動的に変化するため、修理スケジュールをオンラインで再構築する必要があります。この問題を解決するために、動的修理工場を、より短い期間にわたる連続した静的修理スケジューリング部分問題と見なします。静的部分問題を解決するための論理ベースのベンダー分解に基づく完全なアプローチを提案し、動的修理工場のスケジュールを設定するためのさまざまな再スケジュールポリシーを設計します。計算実験により、ベンダーモデルは混合整数計画モデルよりも平均4倍高速に最適解を発見し、証明できることが実証されています。より長期的なスケジューリングと迅速なスケジュール調整という両方の側面を備えた再スケジュール手法は、どちらか一方の側面のみを備えた手法と比較して、長期的に利用可能な航空機数を10%増加させます。
Learning by Observation of Agent Software Images
エージェントソフトウェア画像の観察による学習
Learning by observation can be of key importance whenever agents sharing similar features want to learn from each other. This paper presents an agent architecture that enables software agents to learn by direct observation of the actions executed by expert agents while they are performing a task. This is possible because the proposed architecture displays information that is essential for observation, making it possible for software agents to observe each other. The agent architecture supports a learning process that covers all aspects of learning by observation, such as discovering and observing experts, learning from the observed data, applying the acquired knowledge and evaluating the agent’s progress. The evaluation provides control over the decision to obtain new knowledge or apply the acquired knowledge to new problems. We combine two methods for learning from the observed information. The first one, the recall method, uses the sequence on which the actions were observed to solve new problems. The second one, the classification method, categorizes the information in the observed data and determines to which set of categories the new problems belong. Results show that agents are able to learn in conditions where common supervised learning algorithms fail, such as when agents do not know the results of their actions a priori or when not all the effects of the actions are visible. The results also show that our approach provides better results than other learning methods since it requires shorter learning periods.
類似した特徴を持つエージェントが互いに学習したい場合、観察による学習は極めて重要となります。本論文では、タスク実行中のエキスパートエージェントのアクションを直接観察することでソフトウェアエージェントが学習できるようにするエージェントアーキテクチャを提示します。これは、提案するアーキテクチャが観察に不可欠な情報を表示し、ソフトウェアエージェントが互いを観察できるようにするため可能です。このエージェントアーキテクチャは、エキスパートの発見と観察、観察データからの学習、獲得した知識の適用、エージェントの進捗状況の評価など、観察による学習のあらゆる側面をカバーする学習プロセスをサポートします。評価は、新しい知識を獲得するか、獲得した知識を新しい問題に適用するかの決定を制御します。我々は、観察情報から学習するために2つの手法を組み合わせる。1つ目は想起法であり、アクションが観察された順序を用いて新しい問題を解決します。2つ目の分類法は、観測データ内の情報を分類し、新たな問題がどのカテゴリセットに属するかを決定します。結果は、エージェントが自身の行動の結果を事前に知らない場合や、行動のすべての効果が可視化されていない場合など、一般的な教師あり学習アルゴリズムが失敗する状況でも、エージェントが学習できることを示しています。また、このアプローチは学習期間が短いため、他の学習手法よりも優れた結果をもたらすことも示しています。
Sharing Rewards in Cooperative Connectivity Games
協力的接続ゲームにおける報酬の共有
We consider how selfish agents are likely to share revenues derived from maintaining connectivity between important network servers. We model a network where a failure of one node may disrupt communication between other nodes as a cooperative game called the vertex Connectivity Game (CG). In this game, each agent owns a vertex, and controls all the edges going to and from that vertex. A coalition of agents wins if it fully connects a certain subset of vertices in the graph, called the primary vertices.Power indices measure an agent’s ability to affect the outcome of the game. We show that in our domain, such indices can be used to both determine the fair share of the revenues an agent is entitled to, and identify significant possible points of failure affecting the reliability of communication in the network. We show that in general graphs, calculating the Shapley and Banzhaf power indices is #P-complete, but suggest a polynomial algorithm for calculating them in trees. We also investigate finding stable payoff divisions of the revenues in CGs, captured by the game theoretic solution of the core, and its relaxations, the epsilon-core and least core. We show a polynomial algorithm for computing the core of a CG, but show that testing whether an imputation is in the epsilon-core is coNP-complete. Finally, we show that for trees, it is possible to test for epsilon-core imputations in polynomial time.
利己的なエージェントが、重要なネットワークサーバー間の接続を維持することで得られる収益をどのように共有するかを検討します。あるノードの障害によって他のノード間の通信が中断される可能性のあるネットワークを、頂点連結ゲーム（CG）と呼ばれる協力ゲームとしてモデル化します。このゲームでは、各エージェントが頂点を所有し、その頂点との間のすべての辺を制御します。エージェント連合は、グラフ内の特定の頂点集合（主要頂点と呼ばれる）を完全に連結した場合に勝利します。パワーインデックスは、エージェントがゲームの結果に影響を与える能力を測定します。本領域において、このようなインデックスを用いることで、エージェントが受け取るべき収益の公平な分配を決定するだけでなく、ネットワークにおける通信の信頼性に影響を与える可能性のある重要な障害点を特定できることを示す。一般的なグラフにおいて、シャプレーとバンザフのパワーインデックスの計算は#P完全であることを示すが、ツリー構造においてそれらを計算するための多項式アルゴリズムを提案します。また、CGにおける収益の安定した利得分配を、コアとその緩和形であるイプシロンコアおよび最小コアのゲーム理論的解によって捉えることも検討します。我々はCGのコアを計算する多項式アルゴリズムを示すが、代入がイプシロンコアにあるかどうかをテストすることはcoNP完全であることを示す。最後に、木に対しては、イプシロンコア代入を多項式時間でテストできることを示す。
The Arcade Learning Environment: An Evaluation Platform for General Agents
アーケード学習環境：汎用エージェントの評価プラットフォーム
In this article we introduce the Arcade Learning Environment (ALE): both a challenge problem and a platform and methodology for evaluating the development of general, domain-independent AI technology. ALE provides an interface to hundreds of Atari 2600 game environments, each one different, interesting, and designed to be a challenge for human players. ALE presents significant research challenges for reinforcement learning, model learning, model-based planning, imitation learning, transfer learning, and intrinsic motivation. Most importantly, it provides a rigorous testbed for evaluating and comparing approaches to these problems. We illustrate the promise of ALE by developing and benchmarking domain-independent agents designed using well-established AI techniques for both reinforcement learning and planning. In doing so, we also propose an evaluation methodology made possible by ALE, reporting empirical results on over 55 different games. All of the software, including the benchmark agents, is publicly available.
本稿では、アーケード学習環境（ALE）を紹介します。ALEは、挑戦的な問題であると同時に、汎用的でドメインに依存しないAI技術の開発を評価するためのプラットフォームと方法論でもあります。ALEは、数百ものAtari 2600ゲーム環境へのインターフェースを提供します。これらの環境はそれぞれが異なり、興味深く、人間のプレイヤーにとって挑戦となるように設計されています。ALEは、強化学習、モデル学習、モデルベースプランニング、模倣学習、転移学習、そして内発的動機付けに関する重要な研究課題を提示します。最も重要なのは、これらの問題へのアプローチを評価・比較するための厳密なテストベッドを提供することです。私たちは、強化学習とプランニングの両方において確立されたAI技術を用いて設計されたドメインに依存しないエージェントを開発し、ベンチマークすることで、ALEの可能性を示します。その過程で、ALEによって可能になった評価方法論も提案し、55を超えるさまざまなゲームにおける実証結果を報告します。ベンチマークエージェントを含むすべてのソフトウェアは公開されています。
Analysis of Watson’s Strategies for Playing Jeopardy!
Jeopardy!におけるWatsonの戦略分析
Major advances in Question Answering technology were needed forIBM Watson to play Jeopardy! at championship level — the show requires rapid-fire answers to challenging natural language questions, broad general knowledge, high precision, and accurate confidence estimates. In addition, Jeopardy! features four types of decision making carrying great strategic importance: (1) Daily Double wagering; (2) Final Jeopardy wagering; (3) selecting the next square when in control of the board; (4) deciding whether to attempt to answer, i.e., “buzz in.” Using sophisticated strategies for these decisions, that properly account for the game state and future event probabilities, can significantly boost a player’s overall chances to win, when compared with simple “rule of thumb” strategies.This article presents our approach to developing Watson’s game-playing strategies, comprising development of a faithful simulation model, and then using learning and Monte-Carlo methods within the simulator to optimize Watson’s strategic decision-making. After giving a detailed description of each of our game-strategy algorithms, we then focus in particular on validating the accuracy of the simulator’s predictions, and documenting performance improvements using our methods. Quantitative performance benefits are shown with respect to both simple heuristic strategies, and actual human contestant performance in historical episodes. We further extend our analysis of human play to derive a number of valuable and counterintuitive examples illustrating how human contestants may improve their performance on the show.
IBM WatsonがJeopardy!でチャンピオンシップレベルの実力を発揮するには、質問応答技術の大幅な進歩が必要でした。この番組では、難解な自然言語の質問への素早い回答、幅広い一般知識、高い精度、そして正確な信頼度推定が求められます。さらに、Jeopardy!ワトソンには、戦略的に非常に重要な4種類の意思決定があります。(1)デイリーダブル賭け、(2)ファイナルジェパディ賭け、(3)盤面を支配しているときに次のマスを選択する、(4)回答を試みるかどうか、つまり「ブザーイン」するかどうかを決定することです。これらの意思決定において、ゲームの状態と将来のイベントの確率を適切に考慮した洗練された戦略を用いることで、単純な「経験則」に基づく戦略と比較して、プレイヤーの全体的な勝率を大幅に高めることができます。本稿では、忠実なシミュレーションモデルの開発、そしてシミュレータ内での学習法とモンテカルロ法を用いたワトソンの戦略的意思決定の最適化という、ワトソンのゲームプレイ戦略開発へのアプローチを紹介します。各ゲーム戦略アルゴリズムを詳細に説明した後、シミュレータの予測精度の検証と、その手法を用いたパフォーマンス向上の実証に焦点を当てます。単純なヒューリスティック戦略と、過去のエピソードにおける実際の人間の出場者のパフォーマンスの両方について、定量的なパフォーマンス向上を示します。私たちは人間のプレイの分析をさらに拡張し、人間の出場者が番組でのパフォーマンスをどのように向上させることができるかを示す、価値ある、かつ直感に反する多くの例を導き出しました。
A Survey on Latent Tree Models and Applications
潜在木モデルとその応用に関するサーベイ
In data analysis, latent variables play a central role because they help provide powerful insights into a wide variety of phenomena, ranging from biological to human sciences. The latent tree model, a particular type of probabilistic graphical models, deserves attention. Its simple structure – a tree – allows simple and efficient inference, while its latent variables capture complex relationships. In the past decade, the latent tree model has been subject to significant theoretical and methodological developments. In this review, we propose a comprehensive study of this model. First we summarize key ideas underlying the model. Second we explain how it can be efficiently learned from data. Third we illustrate its use within three types of applications: latent structure discovery, multidimensional clustering, and probabilistic inference. Finally, we conclude and give promising directions for future researches in this field.
データ分析において、潜在変数は生物学から人文科学に至るまで、多岐にわたる現象に対する強力な洞察を提供する上で中心的な役割を果たします。確率的グラフィカルモデルの一種である潜在木モデルは注目に値します。そのシンプルな構造（木）は、単純かつ効率的な推論を可能にすると同時に、潜在変数によって複雑な関係性を捉えます。過去10年間、潜在木モデルは理論的にも方法論的にも大きな発展を遂げてきました。本レビューでは、このモデルの包括的な研究を提案します。まず、このモデルの基礎となる主要なアイデアを要約します。次に、データから効率的に学習する方法を説明します。最後に、潜在構造の発見、多次元クラスタリング、確率的推論という3種類のアプリケーションにおけるその使用法を示します。最後に、結論として、この分野における将来の研究の有望な方向性を示します。
A Feature Subset Selection Algorithm Automatic Recommendation Method
特徴サブセット選択アルゴリズムによる自動推奨法
Many feature subset selection (FSS) algorithms have been proposed, but not all of them are appropriate for a given feature selection problem. At the same time, so far there is rarely a good way to choose appropriate FSS algorithms for the problem at hand. Thus, FSS algorithm automatic recommendation is very important and practically useful. In this paper, a meta learning based FSS algorithm automatic recommendation method is presented. The proposed method first identifies the data sets that are most similar to the one at hand by the k-nearest neighbor classification algorithm, and the distances among these data sets are calculated based on the commonly-used data set characteristics. Then, it ranks all the candidate FSS algorithms according to their performance on these similar data sets, and chooses the algorithms with best performance as the appropriate ones. The performance of the candidate FSS algorithms is evaluated by a multi-criteria metric that takes into account not only the classification accuracy over the selected features, but also the runtime of feature selection and the number of selected features. The proposed recommendation method is extensively tested on 115 real world data sets with 22 well-known and frequently-used different FSS algorithms for five representative classifiers. The results show the effectiveness of our proposed FSS algorithm recommendation method.
多くの特徴サブセット選択(FSS)アルゴリズムが提案されていますが、それらのすべてが特定の特徴選択問題に適しているわけではありません。同時に、これまでのところ、手元の問題に適したFSSアルゴリズムを選択するための良い方法はほとんどありません。そのため、FSSアルゴリズムの自動推奨は非常に重要で、実用的です。この論文では、メタ学習に基づくFSSアルゴリズムの自動推奨方法を紹介します。提案された方法では、まずk最近傍分類アルゴリズムによって手元のデータ セットに最も類似するデータ セットを識別し、これらのデータ セット間の距離を一般的に使用されるデータ セットの特性に基づいて計算します。次に、これらの類似データ セットでのパフォーマンスに従って候補となるすべてのFSSアルゴリズムをランク付けし、パフォーマンスが最も優れたアルゴリズムを適切なものとして選択します。候補となるFSSアルゴリズムのパフォーマンスは、選択された特徴に対する分類精度だけでなく、特徴選択の実行時間と選択された特徴の数も考慮した多基準メトリックによって評価されます。提案された推奨手法は、5つの代表的な分類器に対して、22種類のよく知られ、頻繁に使用されるFSSアルゴリズムを用いて、115の実世界データセットで広範囲にテストされました。その結果、提案されたFSSアルゴリズムの推奨手法の有効性が示されました。