Policy Iteration for Decentralized Control of Markov Decision Processes
マルコフ決定過程の分散制御のための方策反復
Coordination of distributed agents is required for problems arising in many areas, including multi-robot systems, networking and e-commerce. As a formal framework for such problems, we use the decentralized partially observable Markov decision process (DEC-POMDP). Though much work has been done on optimal dynamic programming algorithms for the single-agent version of the problem, optimal algorithms for the multiagent case have been elusive. The main contribution of this paper is an optimal policy iteration algorithm for solving DEC-POMDPs. The algorithm uses stochastic finite-state controllers to represent policies. The solution can include a correlation device, which allows agents to correlate their actions without communicating. This approach alternates between expanding the controller and performing value-preserving transformations, which modify the controller without sacrificing value. We present two efficient value-preserving transformations: one can reduce the size of the controller and the other can improve its value while keeping the size fixed. Empirical results demonstrate the usefulness of value-preserving transformations in increasing value while keeping controller size to a minimum. To broaden the applicability of the approach, we also present a heuristic version of the policy iteration algorithm, which sacrifices convergence to optimality. This algorithm further reduces the size of the controllers at each step by assuming that probability distributions over the other agents’ actions are known. While this assumption may not hold in general, it helps produce higher quality solutions in our test problems.
分散エージェントの協調は、マルチロボットシステム、ネットワーキング、電子商取引など、多くの分野で発生する問題において必要となります。このような問題の形式的な枠組みとして、我々は分散型部分観測マルコフ決定過程（DEC-POMDP）を用います。この問題の単一エージェント版に対する最適な動的計画法アルゴリズムについては多くの研究がなされてきたが、マルチエージェント版に対する最適なアルゴリズムは未だ見つかっていない。本稿の主な貢献は、DEC-POMDPを解くための最適な方策反復アルゴリズムです。このアルゴリズムは、確率的有限状態コントローラを用いて方策を表現します。この解法には相関デバイスを含めることができ、これによりエージェントは通信することなく行動を相関させることができます。このアプローチは、コントローラの拡張と、値を犠牲にすることなくコントローラを変更する値保存変換の実行を交互に行う。我々は、2つの効率的な値保存変換を提示します。1つはコントローラのサイズを縮小するもので、もう1つはサイズを固定したままコントローラの価値を向上させるものです。実験結果は、コントローラのサイズを最小限に抑えながら価値を向上させるという、値保存変換の有用性を示しています。このアプローチの適用範囲を広げるため、最適性への収束を犠牲にする、方策反復アルゴリズムのヒューリスティック版も提示します。このアルゴリズムは、他のエージェントの行動に関する確率分布が既知であると仮定することで、各ステップにおけるコントローラのサイズをさらに縮小します。この仮定は一般には成立しないかもしれないが、我々のテスト問題において、より高品質な解を生成するのに役立つ。
Conservative Inference Rule for Uncertain Reasoning under Incompleteness
不完全性下における不確実推論のための保守的推論規則
In this paper we formulate the problem of inference under incomplete information in very general terms. This includes modelling the process responsible for the incompleteness, which we call the incompleteness process. We allow the process’ behaviour to be partly unknown. Then we use Walley’s theory of coherent lower previsions, a generalisation of the Bayesian theory to imprecision, to derive the rule to update beliefs under incompleteness that logically follows from our assumptions, and that we call conservative inference rule. This rule has some remarkable properties: it is an abstract rule to update beliefs that can be applied in any situation or domain; it gives us the opportunity to be neither too optimistic nor too pessimistic about the incompleteness process, which is a necessary condition to draw reliable while strong enough conclusions; and it is a coherent rule, in the sense that it cannot lead to inconsistencies. We give examples to show how the new rule can be applied in expert systems, in parametric statistical inference, and in pattern classification, and discuss more generally the view of incompleteness processes defended here as well as some of its consequences.
本稿では、不完全情報下での推論の問題を非常に一般的な言葉で定式化します。これには、不完全性の原因となるプロセス（不完全性プロセスと呼ぶ）のモデル化が含まれます。プロセスの挙動は部分的に未知であるとします。次に、ベイズ理論を不正確さに一般化した、ウォーリーの首尾一貫した下方予測の理論を用いて、我々の仮定から論理的に導かれる、不完全性下での信念更新規則を導出します。この規則を我々は保守的推論規則と呼ぶ。この規則には注目すべき特性があります。それは、あらゆる状況や領域に適用できる抽象的な信念更新規則であること、不完全性プロセスについて過度に楽観的にも過度に悲観的にもなれない機会を与えてくれること、これは信頼性が高くかつ十分に強い結論を導き出すための必要条件であること、そして矛盾を生じないという意味で首尾一貫した規則であることです。本稿では、この新しい規則がエキスパートシステム、パラメトリック統計推論、パターン分類にどのように適用できるかを例を挙げて示し、ここで提唱する不完全性過程の観点とその帰結についてより一般的に考察します。
Efficient Informative Sensing using Multiple Robots
複数ロボットを用いた効率的な情報センシング
The need for efficient monitoring of spatio-temporal dynamics in large environmental applications, such as the water quality monitoring in rivers and lakes, motivates the use of robotic sensors in order to achieve sufficient spatial coverage. Typically, these robots have bounded resources, such as limited battery or limited amounts of time to obtain measurements. Thus, careful coordination of their paths is required in order to maximize the amount of information collected, while respecting the resource constraints. In this paper, we present an efficient approach for near-optimally solving the NP-hard optimization problem of planning such informative paths. In particular, we first develop eSIP (efficient Single-robot Informative Path planning), an approximation algorithm for optimizing the path of a single robot. Hereby, we use a Gaussian Process to model the underlying phenomenon, and use the mutual information between the visited locations and remainder of the space to quantify the amount of information collected. We prove that the mutual information collected using paths obtained by using eSIP is close to the information obtained by an optimal solution. We then provide a general technique, sequential allocation, which can be used to extend any single robot planning algorithm, such as eSIP, for the multi-robot problem. This procedure approximately generalizes any guarantees for the single-robot problem to the multi-robot case. We extensively evaluate the effectiveness of our approach on several experiments performed in-field for two important environmental sensing applications, lake and river monitoring, and simulation experiments performed using several real world sensor network data sets.
河川や湖沼の水質監視など、大規模な環境アプリケーションにおける時空間ダイナミクスの効率的な監視の必要性から、十分な空間カバレッジを実現するためにロボットセンサーが使用されます。通常、これらのロボットは、限られたバッテリーや測定値を取得するのに限られた時間など、限られたリソースしか持たない。したがって、リソースの制約を尊重しながら収集される情報量を最大化するために、経路を慎重に調整する必要があります。本稿では、このような有益な経路を計画するというNP困難な最適化問題を準最適に解く効率的なアプローチを提示します。具体的には、まず、単一ロボットの経路を最適化するための近似アルゴリズムであるeSIP (効率的な単一ロボット情報経路計画)を開発します。これにより、ガウス過程を使用して根本的な現象をモデル化し、訪問場所と空間の残りの部分との間の相互情報量を使用して、収集された情報の量を定量化します。eSIPを使用して取得した経路を使用して収集された相互情報量は、最適解によって取得される情報に近いことを証明します。次に、eSIPなどの単一ロボット計画アルゴリズムをマルチロボット問題に拡張するために使用できる一般的な手法であるシーケンシャル割り当てを提供します。この手順により、単一ロボット問題に対する保証がマルチロボットの場合に近似的に一般化されます。私たちは、2つの重要な環境センシング アプリケーション(湖と河川のモニタリング)を対象としたフィールド内で実行された複数の実験と、いくつかの実際のセンサー ネットワーク データ セットを使用して実行されたシミュレーション実験で、このアプローチの有効性を徹底的に評価します。
Planning over Chain Causal Graphs for Variables with Domains of Size 5 Is NP-Hard
ドメインサイズ5の変数に対する連鎖因果グラフ上の計画はNP困難
Recently, considerable focus has been given to the problem of determining the boundary between tractable and intractable planning problems. In this paper, we study the complexity of planning in the class C_n of planning problems, characterized by unary operators and directed path causal graphs. Although this is one of the simplest forms of causal graphs a planning problem can have, we show that planning is intractable for C_n (unless P = NP), even if the domains of state variables have bounded size. In particular, we show that plan existence for C_n^k is NP-hard for k>=5 by reduction from CNFSAT. Here, k denotes the upper bound on the size of the state variable domains. Our result reduces the complexity gap for the class C_n^k to cases k=3 and k=4 only, since C_n^2 is known to be tractable.
近年、扱いやすい計画問題と扱いにくい計画問題の境界を決定する問題にかなりの注目が集まっています。本論文では、単項演算子と有向パス因果グラフを特徴とする計画問題のクラスC_nにおける計画の複雑さを検討します。これは計画問題が持つことができる最も単純な因果グラフの1つであるが、状態変数のドメインのサイズが制限されている場合でも、C_nでは計画が扱いにくいことを示す(P = NPでない限り)。特に、CNFSATからの縮約により、k>=5に対してC_n^kの計画存在がNP困難であることを示す。ここで、kは状態変数ドメインのサイズの上限を表す。我々の結果は、C_n^2が扱いやすいことが知られているため、クラスC_n^kの計算量ギャップをk=3とk=4の場合のみに縮小します。
Sentence Compression as Tree Transduction
木構造伝達としての文圧縮
This paper presents a tree-to-tree transduction method for sentence compression. Our model is based on synchronous tree substitution grammar, a formalism that allows local distortion of the tree topology and can thus naturally capture structural mismatches. We describe an algorithm for decoding in this framework and show how the model can be trained discriminatively within a large margin framework. Experimental results on sentence compression bring significant improvements over a state-of-the-art model.
本論文では、文圧縮のためのツリーからツリーへの変換法を提示します。我々のモデルは同期ツリー置換文法に基づいており、これはツリートポロジの局所的な歪みを許容し、したがって構造上の不一致を自然に捉えることができる形式です。我々はこの枠組みにおけるデコードのためのアルゴリズムを説明し、大きなマージン枠組みの中でモデルを識別的に訓練する方法を示す。文圧縮の実験結果は、最先端のモデルに比べて大幅な改善をもたらす。
Asynchronous Forward Bounding for Distributed COPs
分散システムのための非同期フォワードバウンディングCOPs
A new search algorithm for solving distributed constraint optimization problems (DisCOPs) is presented. Agents assign variables sequentially and compute bounds on partial assignments asynchronously. The asynchronous bounds computation is based on the propagation of partial assignments. The asynchronous forward-bounding algorithm (AFB) is a distributed optimization search algorithm that keeps one consistent partial assignment at all times. The algorithm is described in detail and its correctness proven. Experimental evaluation shows that AFB outperforms synchronous branch and bound by many orders of magnitude, and produces a phase transition as the tightness of the problem increases. This is an analogous effect to the phase transition that has been observed when local consistency maintenance is applied to MaxCSPs. The AFB algorithm is further enhanced by the addition of a backjumping mechanism, resulting in the AFB-BJ algorithm. Distributed backjumping is based on accumulated information on bounds of all values and on processing concurrently a queue of candidate goals for the next move back. The AFB-BJ algorithm is compared experimentally to other DisCOP algorithms (ADOPT, DPOP, OptAPO) and is shown to be a very efficient algorithm for DisCOPs.
分散制約最適化問題（DisCOP）を解くための新しい探索アルゴリズムを提示します。エージェントは変数を順次割り当て、部分割り当ての境界を非同期的に計算します。非同期境界計算は、部分割り当ての伝播に基づいています。非同期フォワードバウンディングアルゴリズム（AFB）は、常に1つの一貫した部分割り当てを維持する分散最適化探索アルゴリズムです。このアルゴリズムは詳細に説明され、その正しさが証明されています。実験的評価では、AFBは同期分岐限定法よりも桁違いに優れた性能を示し、問題の厳密さが増すにつれて相転移が生じることが示されています。これは、局所的一貫性維持をMaxCSPに適用したときに観測された相転移に類似した効果です。AFBアルゴリズムは、バックジャンプメカニズムを追加することでさらに強化され、AFB-BJアルゴリズムとなります。分散バックジャンプは、すべての値の境界に関する蓄積された情報と、次の移動の候補となるゴールのキューを並行して処理することに基づいています。AFB-BJアルゴリズムは、他のDisCOPアルゴリズム（ADOPT、DPOP、OptAPO）と実験的に比較され、DisCOPにとって非常に効率的なアルゴリズムであることが示されています。
Inferring Shallow-Transfer Machine Translation Rules from Small Parallel Corpora
小規模並列コーパスからの浅い転送機械翻訳規則の推論
This paper describes a method for the automatic inference of structural transfer rules to be used in a shallow-transfer machine translation (MT) system from small parallel corpora. The structural transfer rules are based on alignment templates, like those used in statistical MT. Alignment templates are extracted from sentence-aligned parallel corpora and extended with a set of restrictions which are derived from the bilingual dictionary of the MT system and control their application as transfer rules. The experiments conducted using three different language pairs in the free/open-source MT platform Apertium show that translation quality is improved as compared to word-for-word translation (when no transfer rules are used), and that the resulting translation quality is close to that obtained using hand-coded transfer rules. The method we present is entirely unsupervised and benefits from information in the rest of modules of the MT system in which the inferred rules are applied.
本論文では、小規模な対訳コーパスから浅い変換機械翻訳（MT）システムで使用する構造変換規則を自動推論する手法について説明します。構造変換規則は、統計的MTで使用されるアライメントテンプレートに基づいています。アライメントテンプレートは、文がアライメントされた対訳コーパスから抽出され、MTシステムの対訳辞書から導出された一連の制約によって拡張され、変換規則としての適用を制御します。無料/オープンソースのMTプラットフォームApertiumで3つの異なる言語ペアを使用して実施した実験では、逐語訳（変換規則を使用しない場合）と比較して翻訳品質が向上し、結果として得られた翻訳品質は手動でコーディングされた変換規則を使用した場合に近いことが示されました。我々が提示する手法は完全に教師なし学習であり、推論された規則が適用されるMTシステムの他のモジュールの情報を活用します。
Learning Document-Level Semantic Properties from Free-Text Annotations
フリーテキスト注釈からの文書レベルの意味特性の学習
This paper presents a new method for inferring the semantic properties of documents by leveraging free-text keyphrase annotations. Such annotations are becoming increasingly abundant due to the recent dramatic growth in semi-structured, user-generated online content. One especially relevant domain is product reviews, which are often annotated by their authors with pros/cons keyphrases such as “a real bargain” or “good value.” These annotations are representative of the underlying semantic properties; however, unlike expert annotations, they are noisy: lay authors may use different labels to denote the same property, and some labels may be missing. To learn using such noisy annotations, we find a hidden paraphrase structure which clusters the keyphrases. The paraphrase structure is linked with a latent topic model of the review texts, enabling the system to predict the properties of unannotated documents and to effectively aggregate the semantic properties of multiple reviews. Our approach is implemented as a hierarchical Bayesian model with joint inference. We find that joint inference increases the robustness of the keyphrase clustering and encourages the latent topics to correlate with semantically meaningful properties. Multiple evaluations demonstrate that our model substantially outperforms alternative approaches for summarizing single and multiple documents into a set of semantically salient keyphrases.
本論文では、フリーテキストのキーフレーズアノテーションを活用して文書の意味特性を推定する新しい手法を提示します。近年、半構造化されたユーザー生成オンラインコンテンツの急激な増加に伴い、このようなアノテーションはますます豊富になっています。特に関連性の高い分野の一つが製品レビューであり、レビュー作成者は「本当にお買い得」や「お得」といった長所／短所を表すキーフレーズを用いてアノテーションを付与することが多い。これらのアノテーションは、根底にある意味特性を表すものであるが、専門家によるアノテーションとは異なり、ノイズが多い。つまり、素人の著者が同じ特性を表すのに異なるラベルを使用する可能性があり、また、一部のラベルが欠落している可能性もあります。このようなノイズの多いアノテーションを用いて学習するために、キーフレーズをクラスタ化する隠れたパラフレーズ構造を発見します。このパラフレーズ構造はレビューテキストの潜在トピックモデルとリンクされており、システムはアノテーションされていない文書の特性を予測し、複数のレビューの意味特性を効果的に集約することができます。本手法は、結合推論を用いた階層的ベイズモデルとして実装されています。共同推論はキーフレーズクラスタリングの堅牢性を高め、潜在トピックと意味的に意味のある特性との相関を促進することが分かりました。複数の評価により、本モデルは、単一および複数の文書を意味的に顕著なキーフレーズ集合に要約する他の手法よりも大幅に優れていることが実証されています。
An Anytime Algorithm for Optimal Coalition Structure Generation
最適な連携構造生成のためのいつでも利用可能なアルゴリズム
Coalition formation is a fundamental type of interaction that involves the creation of coherent groupings of distinct, autonomous, agents in order to efficiently achieve their individual or collective goals. Forming effective coalitions is a major research challenge in the field of multi-agent systems. Central to this endeavour is the problem of determining which of the many possible coalitions to form in order to achieve some goal. This usually requires calculating a value for every possible coalition, known as the coalition value, which indicates how beneficial that coalition would be if it was formed. Once these values are calculated, the agents usually need to find a combination of coalitions, in which every agent belongs to exactly one coalition, and by which the overall outcome of the system is maximized. However, this coalition structure generation problem is extremely challenging due to the number of possible solutions that need to be examined, which grows exponentially with the number of agents involved. To date, therefore, many algorithms have been proposed to solve this problem using different techniques ranging from dynamic programming, to integer programming, to stochastic search all of which suffer from major limitations relating to execution time, solution quality, and memory requirements.With this in mind, we develop an anytime algorithm to solve the coalition structure generation problem. Specifically, the algorithm uses a novel representation of the search space, which partitions the space of possible solutions into sub-spaces such that it is possible to compute upper and lower bounds on the values of the best coalition structures in them. These bounds are then used to identify the sub-spaces that have no potential of containing the optimal solution so that they can be pruned. The algorithm, then, searches through the remaining sub-spaces very efficiently using a branch-and-bound technique to avoid examining all the solutions within the searched subspace(s). In this setting, we prove that our algorithm enumerates all coalition structures efficiently by avoiding redundant and invalid solutions automatically. Moreover, in order to effectively test our algorithm we develop a new type of input distribution which allows us to generate more reliable benchmarks compared to the input distributions previously used in the field. Given this new distribution, we show that for 27 agents our algorithm is able to find solutions that are optimal in 0.175% of the time required by the fastest available algorithm in the literature. The algorithm is anytime, and if interrupted before it would have normally terminated, it can still provide a solution that is guaranteed to be within a bound from the optimal one. Moreover, the guarantees we provide on the quality of the solution are significantly better than those provided by the previous state of the art algorithms designed for this purpose. For example, for the worst case distribution given 25 agents, our algorithm is able to find a 90% efficient solution in around 10% of time it takes to find the optimal solution.
連携形成は、個々のエージェントまたは集団の目標を効率的に達成するために、明確に区別された自律的なエージェントを首尾一貫したグループにまとめる、基本的な相互作用の一種です。効果的な連携の形成は、マルチエージェントシステム分野における主要な研究課題です。この研究の中心となるのは、ある目標を達成するために、多くの可能な連携の中からどの連携を形成するかを決定する問題です。これは通常、あらゆる可能な連携について、連携価値と呼ばれる値を計算することを必要とします。これは、その連携が形成された場合にどれほど有益であるかを示します。これらの値が計算されると、エージェントは通常、すべてのエージェントが正確に1つの連携に属し、システム全体の成果が最大化されるような連携の組み合わせを見つける必要があります。しかし、この連携構造生成問題は、検討すべき可能な解の数が非常に多く、関与するエージェントの数に応じて指数関数的に増加するため、非常に困難です。そのため、これまでこの問題を解くために、動的計画法、整数計画法、確率的探索法など、様々な手法を用いた多くのアルゴリズムが提案されてきましたが、いずれも実行時間、解の質、メモリ要件に関する大きな制約を抱えています。この点を念頭に、我々は提携構造生成問題を解くためのいつでも利用可能なアルゴリズムを開発します。具体的には、このアルゴリズムは探索空間の新しい表現を用い、可能な解の空間を部分空間に分割することで、各部分空間における最適な提携構造の値の上限と下限を計算できるようにします。これらの上限と下限を用いて、最適解を含む可能性のない部分空間を特定し、それらを枝刈りします。そして、このアルゴリズムは、分枝限定法を用いて残りの部分空間を非常に効率的に探索し、探索された部分空間内のすべての解を検証することを避けます。この設定において、我々のアルゴリズムは冗長で無効な解を自動的に回避することで、すべての提携構造を効率的に列挙できることを証明します。さらに、私たちのアルゴリズムを効果的にテストするために、これまでこの分野で使用されていた入力分布に比べて、より信頼性の高いベンチマークを生成できる新しいタイプの入力分布を開発しました。この新しい分布を用いることで、27のエージェントに対して、私たちのアルゴリズムは文献で利用可能な最速のアルゴリズムで必要な時間の0.175%で最適なソリューションを見つけることができることを示しています。このアルゴリズムはいつでも実行でき、通常終了する前に中断された場合でも、最適なソリューションから一定の範囲内であることが保証されたソリューションを提供できます。さらに、私たちが提供するソリューションの品質の保証は、この目的のために設計された従来の最先端のアルゴリズムが提供する保証よりも大幅に優れています。たとえば、25のエージェントが与えられた最悪のケースの分布では、私たちのアルゴリズムは、最適ソリューションを見つけるのにかかる時間の約10%で、90%の効率のソリューションを見つけることができます。
Exploiting Single-Cycle Symmetries in Continuous Constraint Problems
連続制約問題における単一サイクル対称性の活用
Symmetries in discrete constraint satisfaction problems have been explored and exploited in the last years, but symmetries in continuous constraint problems have not received the same attention. Here we focus on permutations of the variables consisting of one single cycle. We propose a procedure that takes advantage of these symmetries by interacting with a continuous constraint solver without interfering with it. A key concept in this procedure are the classes of symmetric boxes formed by bisecting a n-dimensional cube at the same point in all dimensions at the same time. We analyze these classes and quantify them as a function of the cube dimensionality. Moreover, we propose a simple algorithm to generate the representatives of all these classes for any number of variables at very high rates. A problem example from the chemical field and the cyclic n-roots problem are used to show the performance of the approach in practice.
離散制約充足問題における対称性は近年調査・活用されてきたが、連続制約問題における対称性は同様の注目を集めてこなかった。ここでは、単一のサイクルを構成する変数の順列に焦点を当てる。連続制約ソルバーと干渉することなく対話することで、これらの対称性を活用する手順を提案します。この手順の鍵となる概念は、n次元立方体をすべての次元で同時に同じ点で二等分することによって形成される対称ボックスのクラスです。我々はこれらのクラスを分析し、立方体の次元数の関数として定量化します。さらに、任意の数の変数に対して、これらすべてのクラスの代表値を非常に高速に生成する単純なアルゴリズムを提案します。化学分野の問題例と巡回n根問題を使用して、このアプローチの実際のパフォーマンスを示します。
Wikipedia-based Semantic Interpretation for Natural Language Processing
自然言語処理のためのWikipediaベースの意味解釈
Adequate representation of natural language semantics requires access to vast amounts of common sense and domain-specific world knowledge. Prior work in the field was based on purely statistical techniques that did not make use of background knowledge, on limited lexicographic knowledge bases such as WordNet, or on huge manual efforts such as the CYC project. Here we propose a novel method, called Explicit Semantic Analysis (ESA), for fine-grained semantic interpretation of unrestricted natural language texts. Our method represents meaning in a high-dimensional space of concepts derived from Wikipedia, the largest encyclopedia in existence. We explicitly represent the meaning of any text in terms of Wikipedia-based concepts. We evaluate the effectiveness of our method on text categorization and on computing the degree of semantic relatedness between fragments of natural language text. Using ESA results in significant improvements over the previous state of the art in both tasks. Importantly, due to the use of natural concepts, the ESA model is easy to explain to human users.
自然言語の意味を適切に表現するには、膨大な量の常識とドメイン固有の世界知識へのアクセスが必要です。この分野におけるこれまでの研究は、背景知識を利用しない純粋に統計的な手法、WordNetなどの限定的な辞書式知識ベース、あるいはCYCプロジェクトのような膨大な手作業に基づいていました。本稿では、制約のない自然言語テキストをきめ細かく意味解釈するための、明示的意味解析（ESA）と呼ばれる新しい手法を提案します。この手法は、現存する最大の百科事典であるWikipediaから得られた概念の高次元空間において意味を表現します。あらゆるテキストの意味をWikipediaベースの概念で明示的に表現します。我々は、テキスト分類と自然言語テキストの断片間の意味的関連度の計算における本手法の有効性を評価します。ESAの使用により、両方のタスクにおいて従来の最先端技術に比べて大幅な改善が見られます。重要なのは、自然概念を使用しているため、ESAモデルは人間のユーザーに説明しやすいことです。
Solving #SAT and Bayesian Inference with Backtracking Search
バックトラッキング探索による#SATとベイズ推論の解決
Inference in Bayes Nets (BAYES) is an important problem with numerous applications in probabilistic reasoning. Counting the number of satisfying assignments of a propositional formula (#SAT) is a closely related problem of fundamental theoretical importance. Both these problems, and others, are members of the class of sum-of-products (SUMPROD) problems. In this paper we show that standard backtracking search when augmented with a simple memoization scheme (caching) can solve any sum-of-products problem with time complexity that is at least as good any other state-of-the-art exact algorithm, and that it can also achieve the best known time-space tradeoff. Furthermore, backtrackings ability to utilize more flexible variable orderings allows us to prove that it can achieve an exponential speedup over other standard algorithms for SUMPROD on some instances.The ideas presented here have been utilized in a number of solvers that have been applied to various types of sum-of-product problems. These systems have exploited the fact that backtracking can naturally exploit more of the problems structure to achieve improved performance on a range of probleminstances. Empirical evidence of this performance gain has appeared in published works describing these solvers, and we provide references to these works.
ベイズネット推論（BAYES）は、確率的推論において多くの応用を持つ重要な問題です。命題論理式を満たす割り当ての数を数える問題（#SAT）は、理論的に重要な基礎問題です。これらの問題とその他の問題は、積和（SUMPROD）問題の一種です。本論文では、標準的なバックトラッキング探索に単純なメモ化スキーム（キャッシュ）を追加することで、あらゆる積和問題を、他の最先端の厳密アルゴリズムと同等以上の時間計算量で解くことができ、また、既知の最良の時間と空間のトレードオフも達成できることを示します。さらに、バックトラッキングはより柔軟な変数順序付けを利用できるため、場合によってはSUMPRODの他の標準アルゴリズムに比べて指数関数的な高速化を実現できることが証明されています。ここで提示されたアイデアは、様々なタイプの積和問題に適用されてきた多くのソルバーで活用されています。これらのシステムは、バックトラッキングによって問題の構造をより自然に活用できるという事実を利用して、様々な問題インスタンスでパフォーマンスを向上させています。このパフォーマンス向上の実証的証拠は、これらのソルバーを説明した公開研究に示されており、本稿ではこれらの研究への参照を示します。
Identification of Pleonastic It Using the Web
Webを用いた冗長ITの識別
In a significant minority of cases, certain pronouns, especially the pronoun it, can be used without referring to any specific entity. This phenomenon of pleonastic pronoun usage poses serious problems for systems aiming at even a shallow understanding of natural language texts. In this paper, a novel approach is proposed to identify such uses of it: the extrapositional cases are identified using a series of queries against the web, and the cleft cases are identified using a simple set of syntactic rules. The system is evaluated with four sets of news articles containing 679 extrapositional cases as well as 78 cleft constructs. The identification results are comparable to those obtained by human efforts.
非常に少数のケースにおいて、特定の代名詞、特に代名詞「it」は、特定の実体を参照することなく使用できます。この冗長代名詞の使用現象は、自然言語テキストの浅い理解さえも目的とするシステムにとって深刻な問題となります。本稿では、このような「it」の使用を識別するための新しいアプローチを提案します。外置格はWebに対する一連のクエリを用いて識別し、分裂格は単純な統語規則を用いて識別します。このシステムは、679個の外置格と78個の分裂構造を含む4セットのニュース記事を用いて評価されました。識別結果は、人間の作業によるものと同等でした。
Monte Carlo Sampling Methods for Approximating Interactive POMDPs
インタラクティブなPOMDPを近似するためのモンテカルロサンプリング法
Partially observable Markov decision processes (POMDPs) provide a principled framework for sequential planning in uncertain single agent settings. An extension of POMDPs to multiagent settings, called interactive POMDPs (I-POMDPs), replaces POMDP belief spaces with interactive hierarchical belief systems which represent an agents belief about the physical world, about beliefs of other agents, and about their beliefs about others beliefs. This modification makes the difficulties of obtaining solutions due to complexity of the belief and policy spaces even more acute. We describe a general method for obtaining approximate solutions of I-POMDPs based on particle filtering (PF). We introduce the interactive PF, which descends the levels of the interactive belief hierarchies and samples and propagates beliefs at each level. The interactive PF is able to mitigate the belief space complexity, but it does not address the policy space complexity. To mitigate the policy space complexity sometimes also called the curse of history we utilize a complementary method based on sampling likely observations while building the look ahead reachability tree. While this approach does not completely address the curse of history, it beats back the curses impact substantially. We provide experimental results and chart future work.
部分観測マルコフ決定過程（POMDP）は、不確実な単一エージェント環境における逐次計画のための原理的な枠組みを提供します。POMDPをマルチエージェント環境へ拡張した対話型POMDP（I-POMDP）は、POMDPの信念空間を、エージェントの物理世界、他のエージェントの信念、そして他者の信念に関する自身の信念を表現する対話型階層的信念システムに置き換える。この変更により、信念空間と方策空間の複雑さに起因する解を得ることの困難さがさらに深刻化します。本稿では、粒子フィルタリング（PF）に基づいてI-POMDPの近似解を得るための一般的な手法について説明します。対話型PFは、対話型信念階層のレベルを降下させ、各レベルで信念をサンプリングして伝播します。対話型PFは信念空間の複雑さを軽減できるが、方策空間の複雑さには対処できない。「歴史の呪い」とも呼ばれる方策空間の複雑さを軽減するために、我々は、先読み到達可能性木を構築する際に、起こり得る観測をサンプリングする補完的な手法を用います。このアプローチは歴史の呪いを完全には解消できないものの、呪いの影響を大幅に軽減します。本稿では実験結果を示し、今後の課題を示します。
A Heuristic Search Approach to Planning with Continuous Resources in Stochastic Domains
確率領域における連続リソースを用いた計画のためのヒューリスティック探索アプローチ
We consider the problem of optimal planning in stochastic domains with resource constraints, where the resources are continuous and the choice of action at each step depends on resource availability. We introduce the HAO* algorithm, a generalization of the AO* algorithm that performs search in a hybrid state space that is modeled using both discrete and continuous state variables, where the continuous variables represent monotonic resources. Like other heuristic search algorithms, HAO* leverages knowledge of the start state and an admissible heuristic to focus computational effort on those parts of the state space that could be reached from the start state by following an optimal policy. We show that this approach is especially effective when resource constraints limit how much of the state space is reachable. Experimental results demonstrate its effectiveness in the domain that motivates our research: automated planning for planetary exploration rovers.
リソース制約のある確率領域における最適計画の問題を検討します。この場合、リソースは連続しており、各ステップでのアクションの選択はリソースの可用性に依存します。AO*アルゴリズムの一般化であるHAO*アルゴリズムを導入します。これは、離散状態変数と連続状態変数の両方を使用してモデル化されたハイブリッド状態空間で探索を実行します。連続変数は単調なリソースを表します。他のヒューリスティック探索アルゴリズムと同様に、HAO*は開始状態に関する知識と許容ヒューリスティックを活用して、最適なポリシーに従うことで開始状態から到達できる状態空間の部分に計算労力を集中させます。このアプローチは、リソース制約によって状態空間の到達可能な範囲が制限される場合に特に効果的であることを示します。実験結果は、私たちの研究の目的である惑星探査ローバーの自動計画という領域におけるその有効性を実証しています。
Unsupervised Methods for Determining Object and Relation Synonyms on the Web
Web上のオブジェクトと関係の同義語を決定するための教師なし手法
The task of identifying synonymous relations and objects, or synonym resolution, is critical for high-quality information extraction. This paper investigates synonym resolution in the context of unsupervised information extraction, where neither hand-tagged training examples nor domain knowledge is available. The paper presents a scalable, fully-implemented system that runs in O(KN log N) time in the number of extractions, N, and the maximum number of synonyms per word, K. The system, called Resolver , introduces a probabilistic relational model for predicting whether two strings are co-referential based on the similarity of the assertions containing them. On a set of two million assertions extracted from the Web, Resolver resolves objects with 78% precision and 68% recall, and resolves relations with 90% precision and 35% recall. Several variations of resolver’s probabilistic model are explored, and experiments demonstrate that under appropriate conditions these variations can improve F1 by 5%. An extension to the basic Resolver system allows it to handle polysemous names with 97% precision and 95% recall on a data set from the TREC corpus.
同義関係と同義オブジェクトを識別するタスク、つまり同義語解決は、高品質の情報抽出に不可欠です。この論文では、手動でタグ付けされたトレーニング例もドメイン知識も利用できない、教師なし情報抽出のコンテキストでの同義語解決を調査します。この論文では、抽出回数N、単語あたりの同義語の最大数KでO(KN log N)時間で実行される、スケーラブルで完全に実装されたシステムを紹介します。Resolverと呼ばれるこのシステムは、2つの文字列を含むアサーションの類似性に基づいて、それらの文字列が共参照であるかどうかを予測する確率的リレーショナル モデルを導入します。Webから抽出された200万のアサーションのセットに対して、Resolverは78%の精度と68%の再現率でオブジェクトを解決し、90%の精度と35%の再現率で関係を解決します。リゾルバの確率モデルのいくつかのバリエーションが検討され、適切な条件下ではこれらのバリエーションによってF1が5%向上することが実験で実証されています。基本的なリゾルバシステムを拡張することで、TRECコーパスのデータセットにおいて、多義語を97%の精度と95%の再現率で処理できるようになります。
Mechanisms for Making Crowds Truthful
群衆を真実にするメカニズム
We consider schemes for obtaining truthful reports on a common but hidden signal from large groups of rational, self-interested agents. One example are online feedback mechanisms, where users provide observations about the quality of a product or service so that other users can have an accurate idea of what quality they can expect. However, (i) providing such feedback is costly, and (ii) there are many motivations for providing incorrect feedback.Both problems can be addressed by reward schemes which (i) cover the cost of obtaining and reporting feedback, and (ii) maximize the expected reward of a rational agent who reports truthfully. We address the design of such incentive-compatible rewards for feedback generated in environments with pure adverse selection. Here, the correlation between the true knowledge of an agent and her beliefs regarding the likelihoods of reports of other agents can be exploited to make honest reporting a Nash equilibrium.In this paper we extend existing methods for designing incentive-compatible rewards by also considering collusion. We analyze different scenarios, where, for example, some or all of the agents collude. For each scenario we investigate whether a collusion-resistant, incentive-compatible reward scheme exists, and use automated mechanism design to specify an algorithm for deriving an efficient reward mechanism.
我々は、合理的かつ利己的なエージェントの大規模グループから、共通だが隠れたシグナルに関する真実の報告を得るためのスキームを検討します。一例として、オンラインフィードバックメカニズムが挙げられます。これは、ユーザーが製品やサービスの品質に関する観察を提供することで、他のユーザーが期待できる品質を正確に把握できるようにするものです。しかし、(i)こうしたフィードバックの提供にはコストがかかり、(ii)不正確なフィードバックを提供する動機も多々存在します。これらの問題は、(i)フィードバックの取得と報告にかかるコストを賄い、(ii)真実を報告する合理的エージェントの期待報酬を最大化する報酬スキームによって解決できます。我々は、純粋な逆選択が存在する環境で生成されるフィードバックに対する、このようなインセンティブ両立的報酬の設計について検討します。ここでは、エージェントの真の知識と、他のエージェントの報告確率に関する彼女の信念との相関関係を利用することで、正直な報告をナッシュ均衡とすることができます。本稿では、インセンティブ両立的報酬を設計するための既存の手法を拡張し、共謀も考慮します。例えば、エージェントの一部または全員が共謀するなど、様々なシナリオを分析します。各シナリオについて、共謀耐性があり、インセンティブと両立する報酬スキームが存在するかどうかを調査し、自動化されたメカニズム設計を使用して、効率的な報酬メカニズムを導出するためのアルゴリズムを指定します。
Behavior Bounding: An Efficient Method for High-Level Behavior Comparison
行動境界：高レベル行動比較のための効率的な手法
In this paper, we explore methods for comparing agent behavior with human behavior to assist with validation. Our exploration begins by considering a simple method of behavior comparison. Motivated by shortcomings in this initial approach, we introduce behavior bounding, an automated model-based approach for comparing behavior that is inspired, in part, by Mitchells Version Spaces. We show that behavior bounding can be used to compactly represent both human and agent behavior. We argue that relatively low amounts of human effort are required to build, maintain, and use the data structures that underlie behavior bounding, and we provide a theoretical basis for these arguments using notions of PAC Learnability. Next, we show empirical results indicating that this approach is effective at identifying differences in certain types of behaviors and that it performs well when compared against our initial benchmark methods. Finally, we demonstrate that behavior bounding can produce information that allows developers to identify and fix problems in an agents behavior much more efficiently than standard debugging techniques.
本稿では、検証を支援するために、エージェントの行動と人間の行動を比較する手法を探求します。私たちの探究は、まず単純な行動比較手法を検討することから始めます。この初期アプローチの欠点を踏まえ、ミッチェルのバージョン空間に一部着想を得た、モデルベースの自動化された行動比較手法である行動境界を導入します。行動境界を用いることで、人間とエージェントの両方の行動をコンパクトに表現できることを示します。行動境界の基盤となるデータ構造の構築、維持、使用には、比較的少ない人的労力しか必要としないことを主張し、PAC学習可能性の概念を用いてこれらの主張の理論的根拠を示します。次に、このアプローチが特定の種類の行動における差異を識別するのに効果的であり、当初のベンチマーク手法と比較して優れたパフォーマンスを発揮することを示す実証結果を示します。最後に、行動境界を用いることで、開発者が標準的なデバッグ手法よりもはるかに効率的にエージェントの行動における問題を特定し、修正できる情報を生成できることを実証します。
Generic Preferences over Subsets of Structured Objects
構造化オブジェクトのサブセットに対する一般的な選好
Various tasks in decision making and decision support systems require selecting a preferred subset of a given set of items. Here we focus on problems where the individual items are described using a set of characterizing attributes, and a generic preference specification is required, that is, a specification that can work with an arbitrary set of items. For example, preferences over the content of an online newspaper should have this form: At each viewing, the newspaper contains a subset of the set of articles currently available. Our preference specification over this subset should be provided offline, but we should be able to use it to select a subset of any currently available set of articles, e.g., based on their tags. We present a general approach for lifting formalisms for specifying preferences over objects with multiple attributes into ones that specify preferences over subsets of such objects. We also show how we can compute an optimal subset given such a specification in a relatively efficient manner. We provide an empirical evaluation of the approach as well as some worst-case complexity results.
意思決定および意思決定支援システムにおける様々なタスクでは、与えられたアイテム集合から好ましいサブセットを選択する必要があります。ここでは、個々のアイテムが特徴的な属性の集合を用いて記述され、汎用的な選好仕様、つまり任意のアイテム集合に適用できる仕様が求められる問題に焦点を当てる。例えば、オンライン新聞のコンテンツに対する選好は、次のような形式をとるべきです。新聞を閲覧するたびに、その新聞には現在利用可能な記事集合のサブセットが含まれています。このサブセットに対する選好仕様はオフラインで提供されるべきであるが、例えばタグに基づいて、現在利用可能な任意の記事集合のサブセットを選択できるようにすべきです。本稿では、複数の属性を持つオブジェクトに対する選好を指定する形式を、そのようなオブジェクトのサブセットに対する選好を指定する形式へと昇華させる一般的なアプローチを提示します。また、そのような仕様が与えられた場合に、比較的効率的に最適なサブセットを計算する方法も示す。本稿では、このアプローチの実証的評価と、最悪ケースの計算量に関する結果も示す。
Interactive Policy Learning through Confidence-Based Autonomy
信頼度に基づく自律性による対話型ポリシー学習
We present Confidence-Based Autonomy (CBA), an interactive algorithm for policy learning from demonstration. The CBA algorithm consists of two components which take advantage of the complimentary abilities of humans and computer agents. The first component, Confident Execution, enables the agent to identify states in which demonstration is required, to request a demonstration from the human teacher and to learn a policy based on the acquired data. The algorithm selects demonstrations based on a measure of action selection confidence, and our results show that using Confident Execution the agent requires fewer demonstrations to learn the policy than when demonstrations are selected by a human teacher. The second algorithmic component, Corrective Demonstration, enables the teacher to correct any mistakes made by the agent through additional demonstrations in order to improve the policy and future task performance. CBA and its individual components are compared and evaluated in a complex simulated driving domain. The complete CBA algorithm results in the best overall learning performance, successfully reproducing the behavior of the teacher while balancing the tradeoff between number of demonstrations and number of incorrect actions during learning.
本稿では、デモンストレーションから方策を学習する対話型アルゴリズムである信頼度に基づく自律性（CBA）を紹介します。CBAアルゴリズムは、人間とコンピュータエージェントの相補的な能力を活用する2つのコンポーネントで構成されています。1つ目のコンポーネントである「Confidence Execution（自信に基づく実行）」は、エージェントがデモンストレーションが必要な状態を識別し、人間の教師にデモンストレーションを要求し、取得したデータに基づいて方策を学習することを可能にします。このアルゴリズムは、行動選択の信頼度に基づいてデモンストレーションを選択します。私たちの研究結果によると、「Confident Execution」を使用すると、人間の教師がデモンストレーションを選択した場合よりも、エージェントが方策を学習するために必要なデモンストレーション回数が少なくなります。2つ目のアルゴリズムコンポーネントである「Corrective Demonstration（修正デモンストレーション）」は、教師が追加のデモンストレーションを通じてエージェントの誤りを修正し、方策と将来のタスクパフォーマンスを向上させることを可能にします。CBAとその個々のコンポーネントは、複雑な運転シミュレーション領域で比較・評価されます。完全なCBAアルゴリズムにより、学習中のデモンストレーションの数と誤ったアクションの数とのトレードオフのバランスを取りながら、教師の動作を正常に再現し、全体的な学習パフォーマンスが最良になります。