Soft Constraints of Difference and Equality
差異と等価性のソフト制約
In many combinatorial problems one may need to model the diversity or similarity of assignments in a solution. For example, one may wish to maximise or minimise the number of distinct values in a solution. To formulate problems of this type, we can use soft variants of the well known AllDifferent and AllEqual constraints. We present a taxonomy of six soft global constraints, generated by combining the two latter ones and the two standard cost functions, which are either maximised or minimised. We characterise the complexity of achieving arc and bounds consistency on these constraints, resolving those cases for which NP-hardness was neither proven nor disproven. In particular, we explore in depth the constraint ensuring that at least k pairs of variables have a common value. We show that achieving arc consistency is NP-hard, however achieving bounds consistency can be done in polynomial time through dynamic programming. Moreover, we show that the maximum number of pairs of equal variables can be approximated by a factor 1/2 with a linear time greedy algorithm. Finally, we provide a fixed parameter tractable algorithm with respect to the number of values appearing in more than two distinct domains. Interestingly, this taxonomy shows that enforcing equality is harder than enforcing difference.
多くの組み合わせ問題では、ソリューション内の割り当ての多様性または類似性をモデル化する必要がある場合があります。たとえば、ソリューション内の異なる値の数を最大化または最小化したい場合があります。この種の問題を定式化するために、よく知られているAllDifferent制約とAllEqual制約のソフトな変種を用いることができます。本稿では、後者の2つの制約と、最大化または最小化される2つの標準的なコスト関数を組み合わせることで生成される、6つのソフトなグローバル制約の分類を提示します。これらの制約において、弧の一貫性と境界の一貫性を実現する複雑さを特徴付け、NP困難性が証明も反証もされていないケースを解決します。特に、少なくともk組の変数が共通の値を持つことを保証する制約を詳細に検討します。弧の一貫性を実現することはNP困難であるが、境界の一貫性は動的計画法を用いて多項式時間で実現できることを示す。さらに、等しい変数のペアの最大数は、線形時間の貪欲アルゴリズムを用いて1/2倍に近似できることを示す。最後に、2つ以上の異なるドメインに出現する値の数に関して、固定パラメータで扱いやすいアルゴリズムを提供します。興味深いことに、この分類は、等価性の強制が差異の強制よりも困難であることを示す。
Value of Information Lattice: Exploiting Probabilistic Independence for Effective Feature Subset Acquisition
情報格子の価値：確率的独立性を利用した効果的な特徴サブセット獲得
We address the cost-sensitive feature acquisition problem, where misclassifying an instance is costly but the expected misclassification cost can be reduced by acquiring the values of the missing features. Because acquiring the features is costly as well, the objective is to acquire the right set of features so that the sum of the feature acquisition cost and misclassification cost is minimized. We describe the Value of Information Lattice (VOILA), an optimal and efficient feature subset acquisition framework. Unlike the common practice, which is to acquire features greedily, VOILA can reason with subsets of features. VOILA efficiently searches the space of possible feature subsets by discovering and exploiting conditional independence properties between the features and it reuses probabilistic inference computations to further speed up the process. Through empirical evaluation on five medical datasets, we show that the greedy strategy is often reluctant to acquire features, as it cannot forecast the benefit of acquiring multiple features in combination.
私たちは、インスタンスの誤分類にはコストがかかりますが、欠落している特徴の値を取得することで、予想される誤分類コストを削減できる、コストに敏感な特徴取得問題に取り組んでいます。特徴の獲得にもコストがかかるため、特徴獲得コストと誤分類コストの合計が最小になるように適切な特徴セットを獲得することが目的です。ここでは、最適かつ効率的な特徴サブセット獲得フレームワークである情報価値格子(VOILA)について説明します。特徴を貪欲に獲得する一般的な方法とは異なり、VOILAは特徴のサブセットで推論できます。VOILAは、特徴間の条件付き独立性プロパティを発見して利用することで、可能な特徴サブセットの空間を効率的に検索し、確率的推論計算を再利用してプロセスをさらに高速化します。5つの医療データセットでの経験的評価により、貪欲戦略では複数の特徴を組み合わせて獲得する利点を予測できないため、特徴の獲得に消極的になることが多いことを示しています。
Controlling Complexity in Part-of-Speech Induction
品詞推定における複雑性の制御
We consider the problem of fully unsupervised learning of grammatical (part-of-speech) categories from unlabeled text. The standard maximum-likelihood hidden Markov model for this task performs poorly, because of its weak inductive bias and large model capacity. We address this problem by refining the model and modifying the learning objective to control its capacity via para- metric and non-parametric constraints. Our approach enforces word-category association sparsity, adds morphological and orthographic features, and eliminates hard-to-estimate parameters for rare words. We develop an efficient learning algorithm that is not much more computationally intensive than standard training. We also provide an open-source implementation of the algorithm. Our experiments on five diverse languages (Bulgarian, Danish, English, Portuguese, Spanish) achieve significant improvements compared with previous methods for the same task.
ラベルなしテキストからの文法（品詞）カテゴリの完全教師なし学習の問題を検討します。このタスクに対する標準的な最大尤度隠れマルコフモデルは、帰納的バイアスが弱く、モデル容量が大きいため、パフォーマンスが低下します。この問題に対処するため、モデルを改良し、学習目標を変更して、パラメトリック制約とノンパラメトリック制約を介してモデル容量を制御します。私たちのアプローチは、単語とカテゴリの関連のスパース性を強制し、形態素および綴りの特徴を追加し、まれな単語の推定が困難なパラメータを排除します。標準的なトレーニングよりも計算負荷がそれほど高くない、効率的な学習アルゴリズムを開発します。また、アルゴリズムのオープンソース実装も提供します。5つの異なる言語（ブルガリア語、デンマーク語、英語、ポルトガル語、スペイン語）での実験では、同じタスクに対する以前の方法と比較して大幅な改善が達成されました。
A Probabilistic Framework for Learning Kinematic Models of Articulated Objects
運動モデル学習のための確率的枠組み多関節物体の
Robots operating in domestic environments generally need to interact with articulated objects, such as doors, cabinets, dishwashers or fridges. In this work, we present a novel, probabilistic framework for modeling articulated objects as kinematic graphs. Vertices in this graph correspond to object parts, while edges between them model their kinematic relationship. In particular, we present a set of parametric and non-parametric edge models and how they can robustly be estimated from noisy pose observations. We furthermore describe how to estimate the kinematic structure and how to use the learned kinematic models for pose prediction and for robotic manipulation tasks. We finally present how the learned models can be generalized to new and previously unseen objects. In various experiments using real robots with different camera systems as well as in simulation, we show that our approach is valid, accurate and efficient. Further, we demonstrate that our approach has a broad set of applications, in particular for the emerging fields of mobile manipulation and service robotics.
家庭環境で動作するロボットは、一般的にドア、キャビネット、食器洗い機、冷蔵庫などの多関節物体と相互作用する必要があります。本研究では、多関節物体を運動学グラフとしてモデル化する、新しい確率的フレームワークを提示します。このグラフの頂点は物体の各部に対応し、それらの間のエッジはそれらの運動学的な関係をモデル化します。特に、パラメトリックおよびノンパラメトリックのエッジモデルのセットと、それらをノイズの多い姿勢観測からロバストに推定する方法を示します。さらに、運動学構造を推定する方法と、学習した運動学モデルを姿勢予測およびロボット操作タスクに使用する方法についても説明します。最後に、学習したモデルを新しい物体やこれまで見たことのない物体にどのように一般化できるかを示します。様々なカメラシステムを備えた実ロボットを用いた様々な実験とシミュレーションにより、このアプローチが有効で、正確かつ効率的であることを示します。さらに、このアプローチは、特にモバイルマニピュレーションやサービスロボティクスといった新興分野において、幅広い応用が可能であることを示します。
On the Intertranslatability of Argumentation Semantics
議論意味論の相互翻訳可能性について
Translations between different nonmonotonic formalisms always have been an important topic in the field, in particular to understand the knowledge-representation capabilities those formalisms offer. We provide such an investigation in terms of different semantics proposed for abstract argumentation frameworks, a nonmonotonic yet simple formalism which received increasing interest within the last decade. Although the properties of these different semantics are nowadays well understood, there are no explicit results about intertranslatability. We provide such translations wrt. different properties and also give a few novel complexity results which underlie some negative results.
異なる非単調な形式主義間の翻訳は、この分野において常に重要なトピックであり、特にそれらの形式主義が提供する知識表現能力を理解する上で重要です。我々は、抽象的な議論の枠組みのために提案された異なる意味論の観点からそのような調査を行う。これは、過去10年間で関心が高まっている非単調だが単純な形式主義です。今日ではこれらの異なる意味論の特性はよく理解されているが、相互翻訳可能性に関する明確な結果は得られていない。我々は、そのような翻訳を以下に関して提供します。異なる特性を持つロボットを設計し、いくつかの否定的な結果の根底にあるいくつかの新しい複雑性の結果も示しています。
Efficient Multi-Start Strategies for Local Search Algorithms
局所探索アルゴリズムのための効率的なマルチスタート戦略
Local search algorithms applied to optimization problems often suffer from getting trapped in a local optimum. The common solution for this deficiency is to restart the algorithm when no progress is observed. Alternatively, one can start multiple instances of a local search algorithm, and allocate computational resources (in particular, processing time) to the instances depending on their behavior. Hence, a multi-start strategy has to decide (dynamically) when to allocate additional resources to a particular instance and when to start new instances. In this paper we propose multi-start strategies motivated by works on multi-armed bandit problems and Lipschitz optimization with an unknown constant. The strategies continuously estimate the potential performance of each algorithm instance by supposing a convergence rate of the local search algorithm up to an unknown constant, and in every phase allocate resources to those instances that could converge to the optimum for a particular range of the constant. Asymptotic bounds are given on the performance of the strategies. In particular, we prove that at most a quadratic increase in the number of times the target function is evaluated is needed to achieve the performance of a local search algorithm started from the attraction region of the optimum. Experiments are provided using SPSA (Simultaneous Perturbation Stochastic Approximation) and k-means as local search algorithms, and the results indicate that the proposed strategies work well in practice, and, in all cases studied, need only logarithmically more evaluations of the target function as opposed to the theoretically suggested quadratic increase.
最適化問題に適用される局所探索アルゴリズムは、しばしば局所最適解に陥ってしまうという問題を抱えています。この問題に対する一般的な解決策は、進展が見られない場合にアルゴリズムを再起動することです。あるいは、局所探索アルゴリズムのインスタンスを複数起動し、インスタンスの挙動に応じて計算資源（特に処理時間）を割り当てる方法もあります。したがって、マルチスタート戦略では、特定のインスタンスに追加の資源を割り当てるタイミングと、新しいインスタンスを起動するタイミングを（動的に）決定する必要があります。本稿では、多腕バンディット問題と未知定数を用いたリプシッツ最適化に関する研究を参考に、マルチスタート戦略を提案します。この戦略は、局所探索アルゴリズムの収束速度を未知の定数までと仮定することで、各アルゴリズムインスタンスの潜在的性能を継続的に推定し、各フェーズにおいて、特定の定数範囲で最適解に収束する可能性のあるインスタンスに資源を割り当てます。この戦略の性能には漸近的な境界が与えられています。特に、最適値のアトラクション領域から開始される局所探索アルゴリズムの性能を達成するには、対象関数の評価回数が最大でも2乗の増加で済むことを証明します。局所探索アルゴリズムとしてSPSA（同時摂動確率近似）法とk平均法を用いた実験を行い、提案された戦略が実際にうまく機能し、研究されたすべてのケースにおいて、理論的に示唆された2乗の増加とは対照的に、対象関数の評価回数が対数的に増加するだけで済むことを示した。
Policy Invariance under Reward Transformations for General-Sum Stochastic Games
一般和確率ゲームにおける報酬変換下における方策不変性
We extend the potential-based shaping method from Markov decision processes to multi-player general-sum stochastic games. We prove that the Nash equilibria in a stochastic game remains unchanged after potential-based shaping is applied to the environment. The property of policy invariance provides a possible way of speeding convergence when learning to play a stochastic game.
ポテンシャルベースのシェーピング手法をマルコフ決定過程から多人数参加型一般和確率ゲームへと拡張します。確率ゲームにおけるナッシュ均衡は、ポテンシャルベースのシェーピングを環境に適用した後も変化しないことを証明した。方策不変性という特性は、確率ゲームのプレイ学習において収束を加速させる可能性のある方法を提供します。
The Opposite of Smoothing: A Language Model Approach to Ranking Query-Specific Document Clusters
平滑化の反対：クエリ固有の文書クラスターのランキングのための言語モデルアプローチ
Exploiting information induced from (query-specific) clustering of top-retrieved documents has long been proposed as a means for improving precision at the very top ranks of the returned results. We present a novel language model approach to ranking query-specific clusters by the presumed percentage of relevant documents that they contain. While most previous cluster ranking approaches focus on the cluster as a whole, our model utilizes also information induced from documents associated with the cluster. Our model substantially outperforms previous approaches for identifying clusters containing a high relevant-document percentage. Furthermore, using the model to produce document ranking yields precision-at-top-ranks performance that is consistently better than that of the initial ranking upon which clustering is performed. The performance also favorably compares with that of a state-of-the-art pseudo-feedback-based retrieval method.
上位に検索された文書の（クエリ固有の）クラスタリングから誘導された情報を利用することは、返される結果の最上位ランクでの精度を向上させる手段として長い間提案されてきました。クエリ固有のクラスターを、それに含まれる関連文書の推定割合に基づいてランク付けする、新たな言語モデル手法を提示します。従来のクラスターランク付け手法の多くはクラスター全体に焦点を当てているが、本モデルはクラスターに関連する文書から得られる情報も活用します。本モデルは、関連文書の割合が高いクラスターを特定する従来の手法を大幅に上回る性能を示す。さらに、本モデルを用いて文書ランク付けを行うことで、クラスタリングを行う初期ランク付けよりも一貫して優れた、上位ランクにおける精度が得られます。この性能は、最先端の疑似フィードバックベースの検索手法と比較しても遜色ない。
Sequential Diagnosis by Abstraction
抽象化による逐次診断
When a system behaves abnormally, sequential diagnosis takes a sequence of measurements of the system until the faults causing the abnormality are identified, and the goal is to reduce the diagnostic cost, defined here as the number of measurements. To propose measurement points, previous work employs a heuristic based on reducing the entropy over a computed set of diagnoses. This approach generally has good performance in terms of diagnostic cost, but can fail to diagnose large systems when the set of diagnoses is too large. Focusing on a smaller set of probable diagnoses scales the approach but generally leads to increased average diagnostic costs. In this paper, we propose a new diagnostic framework employing four new techniques, which scales to much larger systems with good performance in terms of diagnostic cost.First, we propose a new heuristic for measurement point selection that can be computed efficiently, without requiring the set of diagnoses, once the system is modeled as a Bayesian network and compiled into a logical form known as d-DNNF. Second, we extend hierarchical diagnosis, a technique based on system abstraction from our previous work, to handle probabilities so that it can be applied to sequential diagnosis to allow larger systems to be diagnosed. Third, for the largest systems where even hierarchical diagnosis fails, we propose a novel method that converts the system into one that has a smaller abstraction and whose diagnoses form a superset of those of the original system; the new system can then be diagnosed and the result mapped back to the original system. Finally, we propose a novel cost estimation function which can be used to choose an abstraction of the system that is more likely to provide optimal average cost. Experiments with ISCAS-85 benchmark circuits indicate that our approach scales to all circuits in the suite except one that has a flat structure not susceptible to useful abstraction.
システムが異常な動作をした場合、逐次診断では、異常の原因となっている障害が特定されるまでシステムの測定を連続的に行い、診断コスト（ここでは測定回数として定義）を削減することを目標とします。測定ポイントを提案するために、これまでの研究では、計算された診断セットのエントロピー削減に基づくヒューリスティックが採用されています。このアプローチは一般的に診断コストの点で優れた性能を示しますが、診断セットが大きすぎると大規模システムを診断できない可能性があります。可能性のある診断のより小さなセットに焦点を当てることでアプローチは拡張されますが、一般的に平均診断コストが増加します。本稿では、4つの新しい手法を採用した新しい診断フレームワークを提案します。このフレームワークは、診断コストの点で優れた性能を示しながら、はるかに大規模なシステムにも拡張できます。まず、システムをベイジアンネットワークとしてモデル化し、d-DNNFと呼ばれる論理形式にコンパイルすると、診断セットを必要とせずに効率的に計算できる、測定ポイント選択のための新しいヒューリスティックを提案します。第二に、我々は、これまでの研究で用いたシステム抽象化に基づく手法である階層診断を拡張し、確率を扱うことができるようにすることで、シーケンシャル診断に適用して、より大規模なシステムを診断できるようにします。第三に、階層診断でさえ失敗するような最大規模のシステムに対して、我々は、システムを、より抽象度が低く、診断が元のシステムの診断のスーパーセットを形成するシステムに変換する新しい手法を提案します。その後、新しいシステムを診断し、結果を元のシステムにマッピングすることができます。最後に、我々は、最適な平均コストを提供する可能性の高いシステムの抽象化を選択するために使用できる、新しいコスト推定関数を提案します。ISCAS-85ベンチマーク回路を用いた実験は、我々のアプローチが、有用な抽象化の影響を受けないフラットな構造を持つ回路を除く、スイート内のすべての回路に拡張可能であることを示しています。
Stackelberg vs. Nash in Security Games: An Extended Investigation of Interchangeability, Equivalence, and Uniqueness
セキュリティゲームにおけるStackelberg対Nash：互換性、同値性、および一意性の拡張調査
There has been significant recent interest in game-theoretic approaches to security, with much of the recent research focused on utilizing the leader-follower Stackelberg game model. Among the major applications are the ARMOR program deployed at LAX Airport and the IRIS program in use by the US Federal Air Marshals (FAMS). The foundational assumption for using Stackelberg games is that security forces (leaders), acting first, commit to a randomized strategy; while their adversaries (followers) choose their best response after surveillance of this randomized strategy. Yet, in many situations, a leader may face uncertainty about the followers surveillance capability. Previous work fails to address how a leader should compute her strategy given such uncertainty.We provide five contributions in the context of a general class of security games. First, we show that the Nash equilibria in security games are interchangeable, thus alleviating the equilibrium selection problem. Second, under a natural restriction on security games, any Stackelberg strategy is also a Nash equilibrium strategy; and furthermore, the solution is unique in a class of security games of which ARMOR is a key exemplar. Third, when faced with a follower that can attack multiple targets, many of these properties no longer hold. Fourth, we show experimentally that in most (but not all) games where the restriction does not hold, the Stackelberg strategy is still a Nash equilibrium strategy, but this is no longer true when the attacker can attack multiple targets. Finally, as a possible direction for future research, we propose an extensive-form game model that makes the defenders uncertainty about the attackers ability to observe explicit.
近年、セキュリティに対するゲーム理論的アプローチに大きな関心が寄せられており、最近の研究の多くはリーダー・フォロワー・スタックベルクゲームモデルの活用に焦点を当てています。主要な応用例としては、ロサンゼルス国際空港で展開されているARMORプログラムや、米国連邦航空保安官（FAMS）が使用しているIRISプログラムが挙げられます。スタックベルクゲームを用いる際の基本的な前提は、セキュリティ部隊（リーダー）が最初に行動し、ランダム化された戦略にコミットする一方で、敵対者（フォロワー）はこのランダム化された戦略を監視した上で最善の対応を選択するというものです。しかし、多くの状況において、リーダーはフォロワーの監視能力に関する不確実性に直面する可能性があります。これまでの研究では、このような不確実性を考慮した上で、リーダーがどのように戦略を策定すべきかについては触れられていない。我々は、一般的なセキュリティゲームを例として、5つの貢献を示す。まず、セキュリティゲームにおけるナッシュ均衡は交換可能であることを示し、均衡選択問題を軽減します。第二に、セキュリティゲームに対する自然な制約の下では、あらゆるスタックベルグ戦略はナッシュ均衡戦略でもあります。さらに、ARMORが重要な例であるセキュリティゲームのクラスにおいて、その解は唯一です。第三に、複数のターゲットを攻撃できる追随者に直面した場合、これらの特性の多くはもはや成立しない。第四に、制約が成立しないほとんどの（ただしすべてではない）ゲームにおいて、スタックベルグ戦略は依然としてナッシュ均衡戦略であるが、攻撃者が複数のターゲットを攻撃できる場合、これはもはや成立しないことを実験的に示す。最後に、将来の研究の方向性として、防御側が攻撃者の観察能力に関する不確実性を明示的に示す展開型ゲームモデルを提案します。
From ‘Identical’ to ‘Similar’: Fusing Retrieved Lists Based on Inter-Document Similarities
「同一」から「類似」へ：文書間類似性に基づく検索リストの融合
Methods for fusing document lists that were retrieved in response to a query often utilize the retrieval scores and/or ranks of documents in the lists. We present a novel fusion approach that is based on using, in addition, information induced from inter-document similarities. Specifically, our methods let similar documents from different lists provide relevance-status support to each other. We use a graph-based method to model relevance-status propagation between documents. The propagation is governed by inter-document-similarities and by retrieval scores of documents in the lists. Empirical evaluation demonstrates the effectiveness of our methods in fusing TREC runs. The performance of our most effective methods transcends that of effective fusion methods that utilize only retrieval scores or ranks.
クエリに応じて取得された文書リストを融合する方法では、多くの場合、リスト内の文書の検索スコアやランクが利用されます。我々は、文書間の類似性から得られる情報に加えて、文書間の類似性から得られる情報を使用することに基づく、新しい融合アプローチを提示します。具体的には、我々の手法では、異なるリストの類似文書が互いに関連性ステータスをサポートできるようにします。我々は、グラフベースの手法を用いて、文書間の関連性ステータスの伝播をモデル化します。この伝播は、文書間の類似性とリスト内の文書の検索スコアによって制御されます。実証的評価により、TREC実行の融合における我々の手法の有効性が実証されます。我々の最も効果的な手法の性能は、検索スコアやランクのみを利用する効果的な融合手法の性能を凌駕します。
Determining Possible and Necessary Winners Given Partial Orders
部分順序を与えられた場合の可能勝者と必要勝者の決定
Usually a voting rule requires agents to give their preferences as linear orders. However, in some cases it is impractical for an agent to give a linear order over all the alternatives. It has been suggested to let agents submit partial orders instead. Then, given a voting rule, a profile of partial orders, and an alternative (candidate) c, two important questions arise: first, is it still possible for c to win, and second, is c guaranteed to win? These are the possible winner and necessary winner problems, respectively. Each of these two problems is further divided into two sub-problems: determining whether c is a unique winner (that is, c is the only winner), or determining whether c is a co-winner (that is, c is in the set of winners). We consider the setting where the number of alternatives is unbounded and the votes are unweighted. We completely characterize the complexity of possible/necessary winner problems for the following common voting rules: a class of positional scoring rules (including Borda), Copeland, maximin, Bucklin, ranked pairs, voting trees, and plurality with runoff.
通常、投票ルールでは、エージェントが好みを線形順序で与える必要があります。しかし、場合によっては、エージェントがすべての選択肢に対して線形順序を与えることが非現実的です。代わりに、エージェントに部分順序を送信させることが提案されています。すると、投票ルール、部分順序のプロファイル、および選択肢(候補) cが与えられたときに、2つの重要な質問が生じます。1つ目は、cが勝つ可能性がまだあるかどうか、2つ目は、cが勝つことが保証されているかどうかです。これらは、それぞれ可能勝者問題と必要勝者問題です。これら2つの問題はそれぞれ、cが唯一の勝者であるかどうかを判断する問題、またはcが共同勝者であるかどうかを判断する問題(つまり、cが勝者のセットに含まれているかどうか)という2つのサブ問題に分割されます。選択肢の数が無制限で、投票に重み付けがない設定を検討します。我々は、以下の一般的な投票規則について、可能/必要な勝者問題の複雑さを完全に特徴付ける：位置スコアリング規則のクラス（ボルダを含む）、コープランド、マキシミン、バックリン、ランク付けされたペア、投票木、およびランオフを含む多数決。
Probabilistic Relational Planning with First Order Decision Diagrams
一階決定図を用いた確率的関係計画
Dynamic programming algorithms have been successfully applied to propositional stochastic planning problems by using compact representations, in particular algebraic decision diagrams, to capture domain dynamics and value functions. Work on symbolic dynamic programming lifted these ideas to first order logic using several representation schemes. Recent work introduced a first order variant of decision diagrams (FODD) and developed a value iteration algorithm for this representation. This paper develops several improvements to the FODD algorithm that make the approach practical. These include, new reduction operators that decrease the size of the representation, several speedup techniques, and techniques for value approximation. Incorporating these, the paper presents a planning system, FODD-Planner, for solving relational stochastic planning problems. The system is evaluated on several domains, including problems from the recent international planning competition, and shows competitive performance with top ranking systems. This is the first demonstration of feasibility of this approach and it shows that abstraction through compact representation is a promising approach to stochastic planning.
動的計画法アルゴリズムは、コンパクトな表現、特に代数的決定図を用いて領域のダイナミクスと価値関数を捉えることで、命題確率的計画問題にうまく適用されてきました。記号動的計画法に関する研究では、これらの考え方を複数の表現スキームを用いて一階述語論理にまで引き上げました。最近の研究では、一階述語決定図の変形（FODD）が導入され、この表現のための価値反復アルゴリズムが開発されました。本論文では、このアプローチを実用化するFODDアルゴリズムのいくつかの改良点について述べます。これらには、表現のサイズを縮小する新しい縮約演算子、いくつかの高速化手法、および値近似のための手法が含まれます。これらを組み入れ、本論文では、関係確率的プランニング問題を解くためのプランニングシステムFODD-Plannerを提示します。このシステムは、最近の国際プランニングコンペティションの問題を含む複数の領域で評価され、上位のシステムと互角の性能を示した。これは、このアプローチの実現可能性を初めて実証したものであり、コンパクトな表現による抽象化が確率的プランニングへの有望なアプローチであることを示すものです。
Analyzing Search Topology Without Running Any Search: On the Connection Between Causal Graphs and h+
検索を実行せずに検索トポロジーを分析する：因果グラフとh+の関係について
The ignoring delete lists relaxation is of paramount importance for both satisficing and optimal planning. In earlier work, it was observed that the optimal relaxation heuristic h+ has amazing qualities in many classical planning benchmarks, in particular pertaining to the complete absence of local minima. The proofs of this are hand-made, raising the question whether such proofs can be lead automatically by domain analysis techniques. In contrast to earlier disappointing results — the analysis method has exponential runtime and succeeds only in two extremely simple benchmark domains — we herein answer this question in the affirmative. We establish connections between causal graph structure and h+ topology. This results in low-order polynomial time analysis methods, implemented in a tool we call TorchLight. Of the 12 domains where the absence of local minima has been proved, TorchLight gives strong success guarantees in 8 domains. Empirically, its analysis exhibits strong performance in a further 2 of these domains, plus in 4 more domains where local minima may exist but are rare. In this way, TorchLight can distinguish “easy” domains from “hard” ones. By summarizing structural reasons for analysis failure, TorchLight also provides diagnostic output indicating domain aspects that may cause local minima.
削除リストを無視する緩和法は、満足度と最適計画の両方において極めて重要です。以前の研究において、最適緩和ヒューリスティックh+は、多くの古典的な計画ベンチマークにおいて、特に局所最小値の完全な不在に関して驚くべき特性を持つことが観察されました。この証明は手作業でなされており、このような証明がドメイン分析手法によって自動的に導かれるかどうかという疑問が生じる。以前の残念な結果（この分析手法は指数関数的な実行時間を必要とし、非常に単純な2つのベンチマークドメインでのみ成功した）とは対照的に、我々はここでこの疑問に肯定的に答える。我々は因果グラフ構造とh+トポロジーの関係を確立します。これにより、低次多項式時間分析手法が得られ、これはTorchLightと呼ぶツールに実装されています。局所最小値の不在が証明された12のドメインのうち、TorchLightは8つのドメインで強力な成功保証を与える。経験的に、その解析はこれらの領域のうちさらに2つ、さらに局所的最小値が存在する可能性はあるものの稀な4つの領域で優れた性能を示しています。このように、TorchLightは「簡単な」領域と「難しい」領域を区別することができます。TorchLightは、解析失敗の構造的理由を要約することにより、局所的最小値を引き起こす可能性のある領域の側面を示す診断出力も提供します。
Redistribution Mechanisms for Assignment of Heterogeneous Objects
異種オブジェクトの割り当てにおける再分配メカニズム
There are p heterogeneous objects to be assigned to n competing agents (n > p) each with unit demand. It is required to design a Groves mechanism for this assignment problem satisfying weak budget balance, individual rationality, and minimizing the budget imbalance. This calls for designing an appropriate rebate function. When the objects are identical, this problem has been solved which we refer as WCO mechanism. We measure the performance of such mechanisms by the redistribution index. We first prove an impossibility theorem which rules out linear rebate functions with non-zero redistribution index in heterogeneous object assignment. Motivated by this theorem, we explore two approaches to get around this impossibility. In the first approach, we show that linear rebate functions with non-zero redistribution index are possible when the valuations for the objects have a certain type of relationship and we design a mechanism with linear rebate function that is worst case optimal. In the second approach, we show that rebate functions with non-zero efficiency are possible if linearity is relaxed. We extend the rebate functions of the WCO mechanism to heterogeneous objects assignment and conjecture them to be worst case optimal.
p個の異種オブジェクトが、それぞれ単位需要を持つn個の競合エージェント（n > p）に割り当てられます。この割り当て問題に対して、弱予算均衡、個人合理性、予算不均衡の最小化を満たすグローブスメカニズムを設計する必要があります。そのためには、適切なリベート関数を設計する必要があります。オブジェクトが同一の場合、この問題は解決されており、これをWCOメカニズムと呼びます。このようなメカニズムのパフォーマンスを再分配指数によって測定します。まず、異種オブジェクトの割り当てにおいて、再分配指数がゼロでない線形リベート関数を排除する不可能性定理を証明します。この定理に基づき、この不可能性を回避するための2つのアプローチを検討します。最初のアプローチでは、オブジェクトの評価が特定の種類の関係を持つ場合、再分配指数がゼロでない線形リベート関数が可能であることを示し、最悪ケースに最適な線形リベート関数を持つメカニズムを設計します。2番目のアプローチでは、線形性が緩和された場合、効率がゼロでないリベート関数が可能であることを示します。WCOメカニズムのリベート関数を異種オブジェクト割り当てに拡張し、最悪ケース最適であると推測します。
Properties of Bethe Free Energies and Message Passing in Gaussian Models
ガウスモデルにおけるベーテ自由エネルギーとメッセージパッシングの特性
We address the problem of computing approximate marginals in Gaussian probabilistic models by using mean field and fractional Bethe approximations. We define the Gaussian fractional Bethe free energy in terms of the moment parameters of the approximate marginals, derive a lower and an upper bound on the fractional Bethe free energy and establish a necessary condition for the lower bound to be bounded from below. It turns out that the condition is identical to the pairwise normalizability condition, which is known to be a sufficient condition for the convergence of the message passing algorithm. We show that stable fixed points of the Gaussian message passing algorithm are local minima of the Gaussian Bethe free energy. By a counterexample, we disprove the conjecture stating that the unboundedness of the free energy implies the divergence of the message passing algorithm.
平均場近似と分数ベーテ近似を使用して、ガウス確率モデルにおける近似周辺分布を計算する問題に取り組みます。近似周辺分布のモーメントパラメータを用いてガウス分数ベーテ自由エネルギーを定義し、その下限値と上限値を導出し、下限値が下から有界となるための必要条件を確立します。この条件は、メッセージパッシングアルゴリズムの収束の十分条件として知られているペアワイズ正規化可能性条件と同一であることが判明した。ガウスメッセージパッシングアルゴリズムの安定な固定点は、ガウスベーテ自由エネルギーの局所的最小値であることを示す。反例を用いて、自由エネルギーの非有界性がメッセージパッシングアルゴリズムの発散を意味するという予想を反証します。