Journal of Artificial Intelligence Resarch: Volume 52の論文一覧

by

Journal of Artificial Intelligence Resarch Vol. 52 (2015)に記載されている内容を一覧にまとめ、機械翻訳を交えて日本語化し掲載します。

目次

論文

Coherent Predictive Inference under Exchangeability with Imprecise Probabilities

Coherent Predictive Inference under Exchangeability with Imprecise Probabilities / 不正確な確率を伴う交換可能性の下での一貫性のある予測推論

Coherent reasoning under uncertainty can be represented in a very general manner by coherent sets of desirable gambles. In a context that does not allow for indecision, this leads to an approach that is mathematically equivalent to working with coherent conditional probabilities. If we do allow for indecision, this leads to a more general foundation for coherent (imprecise-)probabilistic inference. In this framework, and for a given finite category set, coherent predictive inference under exchangeability can be represented using Bernstein coherent cones of multivariate polynomials on the simplex generated by this category set. This is a powerful generalisation of de Finetti’s Representation Theorem allowing for both imprecision and indecision.We define an inference system as a map that associates a Bernstein coherent cone of polynomials with every finite category set. Many inference principles encountered in the literature can then be interpreted, and represented mathematically, as restrictions on such maps. We discuss, as particular examples, two important inference principles: representation insensitivitya strengthened version of Walley’s representation invarianceand specificity. We show that there is an infinity of inference systems that satisfy these two principles, amongst which we discuss in particular the skeptically cautious inference system, the inference systems corresponding to (a modified version of) Walley and Bernard’s Imprecise Dirichlet Multinomial Models (IDMM), the skeptical IDMM inference systems, and the Haldane inference system. We also prove that the latter produces the same posterior inferences as would be obtained using Haldane’s improper prior, implying that there is an infinity of proper priors that produce the same coherent posterior inferences as Haldane’s improper one. Finally, we impose an additional inference principle that allows us to characterise uniquely the immediate predictions for the IDMM inference systems.



不確実性下における一貫した推論は、望ましい賭けの一貫した集合によって非常に一般的な方法で表現できます。優柔不断を許容しない状況では、これは数学的に一貫した条件付き確率を扱うことと等価なアプローチにつながります。優柔不断を許容する場合には、より一般的な、一貫性のある（不正確な）確率推論の基盤につながります。この枠組みにおいて、与えられた有限カテゴリ集合に対して、交換可能性下における一貫した予測推論は、このカテゴリ集合によって生成される単体上の多変数多項式のベルンシュタイン一貫性錐を用いて表現できます。これは、不正確さと優柔不断の両方を許容する、デ・フィネッティの表現定理の強力な一般化です。我々は推論システムを、あらゆる有限カテゴリ集合にベルンシュタイン一貫性錐を関連付ける写像として定義します。文献で見られる多くの推論原理は、そのような写像への制約として解釈され、数学的に表現することができます。具体的な例として、2つの重要な推論原理、すなわち、表現不感受性（Walleyの表現不変性の強化版）、および特異性について論じます。これらの2つの原理を満たす推論システムは無数に存在することを示します。その中でも、特に、懐疑的に慎重な推論システム、WalleyとBernardの不正確ディリクレ多項式モデル（IDMM）（の修正版）に対応する推論システム、懐疑的なIDMM推論システム、そしてHaldane推論システムについて論じます。また、後者はHaldaneの不適正な事前分布を用いた場合と同じ事後推論を生成することを証明します。これは、Haldaneの不適正な事前分布と同じ首尾一貫した事後推論を生成する適正な事前分布が無数に存在することを意味します。最後に、IDMM推論システムの即時予測を一意に特徴付けることを可能にする追加の推論原理を提示します。

Agnostic Pointwise-Competitive Selective Classification

Agnostic Pointwise-Competitive Selective Classification / 不可知論的点単位競合選択分類

Pointwise-competitive classifier from class F is required to classify identically to the best classifier in hindsight from F. For noisy, agnostic settings we present a strategy for learning pointwise-competitive classifiers from a finite training sample provided that the classifier can abstain from prediction at a certain region of its choice. For some interesting hypothesis classes and families of distributions, the measure of this rejected region is shown to be diminishing at a fast rate, with high probability. Exact implementation of the proposed learning strategy is dependent on an ERM oracle that can be hard to compute in the agnostic case. We thus consider a heuristic approximation procedure that is based on SVMs, and show empirically that this algorithm consistently outperforms a traditional rejection mechanism based on distance from decision boundary.



クラスFからの点単位競合分類器は、Fから事後的に得られた最良の分類器と全く同じ分類を行う必要があります。ノイズが多く、非依存的な設定において、分類器が選択した特定の領域で予測を控えることができるという条件で、有限のトレーニングサンプルから点単位競合分類器を学習する戦略を提示します。いくつかの興味深い仮説クラスと分布族において、この棄却領域の測度は高い確率で急速に減少することが示されます。提案された学習戦略の正確な実装は、非依存的な場合には計算が困難なERMオラクルに依存します。そこで、SVMに基づくヒューリスティックな近似手順を検討し、このアルゴリズムが決定境界からの距離に基づく従来の棄却メカニズムよりも一貫して優れていることを経験的に示す。

On the Subexponential-Time Complexity of CSP

On the Subexponential-Time Complexity of CSP / CSPの準指数時間計算量について

Not all NP-complete problems share the same practical hardness with respect to exact computation. Whereas some NP-complete problems are amenable to efficient computational methods, others are yet to show any such sign. It becomes a major challenge to develop a theoretical framework that is more fine-grained than the theory of NP-completeness, and that can explain the distinction between the exact complexities of various NP-complete problems. This distinction is highly relevant for constraint satisfaction problems under natural restrictions, where various shades of hardness can be observed in practice.Acknowledging the NP-hardness of such problems, one has to look beyond polynomial time computation. The theory of subexponential-time complexity provides such a framework, and has been enjoying increasing popularity in complexity theory. An instance of the constraint satisfaction problem with n variables over a domain of d values can be solved by brute-force in dn steps (omitting a polynomial factor). In this paper we study the existence of subexponential-time algorithms, that is, algorithms running in do(n) steps, for various natural restrictions of the constraint satisfaction problem. We consider both the constraint satisfaction problem in which all the constraints are given extensionally as tables, and that in which all the constraints are given intensionally in the form of global constraints. We provide tight characterizations of the subexponential-time complexity of the aforementioned problems with respect to several natural structural parameters, which allows us to draw a detailed landscape of the subexponential-time complexity of the constraint satisfaction problem. Our analysis provides fundamental results indicating whether and when one can significantly improve on the brute-force search approach for solving the constraint satisfaction problem.



NP完全問題のすべてが、正確な計算に関して同じ実際的な困難さを共有するわけではない。一部のNP完全問題は効率的な計算手法に適応できるが、他の問題はまだそのような兆候を示していない。NP完全性理論よりもきめ細かな理論的枠組みを開発し、さまざまなNP完全問題の正確な計算量の違いを説明できるようにすることが大きな課題となります。この区別は、実際にはさまざまな難易度が見られる自然な制約下の制約充足問題に非常に関連しています。このような問題のNP困難性を認識すると、多項式時間計算の先を見る必要があります。指数関数的時間計算量の理論はそのような枠組みを提供し、計算量理論で人気が高まっています。d値の領域上のn変数の制約充足問題のインスタンスは、dnステップ（多項式因数を省略）で総当たり法によって解くことができます。本稿では、制約充足問題のさまざまな自然な制約に対して、指数関数的時間アルゴリズム、つまりdo(n)ステップで実行されるアルゴリズムの存在を検討します。本稿では、すべての制約が外延的に表として与えられる制約充足問題と、すべての制約が内在的に大域制約として与えられる制約充足問題の両方を考察します。これらの問題の指数関数的時間計算量について、いくつかの自然な構造パラメータに関して厳密な特徴付けを行い、制約充足問題の指数関数的時間計算量の詳細なランドスケープを描くことを可能にします。本解析は、制約充足問題を解くための総当たり探索アプローチを大幅に改善できるかどうか、またいつ改善できるのかを示す基本的な結果を提供します。

Lazy Model Expansion: Interleaving Grounding with Search

Lazy Model Expansion: Interleaving Grounding with Search / 遅延モデル拡張：グラウンディングと探索のインターリーブ

Finding satisfying assignments for the variables involved in a set of constraints can be cast as a (bounded) model generation problem: search for (bounded) models of a theory in some logic. The state-of-the-art approach for bounded model generation for rich knowledge representation languages like ASP and FO(.) and a CSP modeling language such as Zinc, is ground-and-solve: reduce the theory to a ground or propositional one and apply a search algorithm to the resulting theory.An important bottleneck is the blow-up of the size of the theory caused by the grounding phase. Lazily grounding the theory during search is a way to overcome this bottleneck. We present a theoretical framework and an implementation in the context of the FO(.) knowledge representation language. Instead of grounding all parts of a theory, justifications are derived for some parts of it. Given a partial assignment for the grounded part of the theory and valid justifications for the formulas of the non-grounded part, the justifications provide a recipe to construct a complete assignment that satisfies the non-grounded part. When a justification for a particular formula becomes invalid during search, a new one is derived; if that fails, the formula is split in a part to be grounded and a part that can be justified. Experimental results illustrate the power and generality of this approach.



一連の制約に含まれる変数の満足のいく割り当てを見つけることは、（有界）モデル生成問題として表すことができます。つまり、何らかのロジックで理論の（有界）モデルを検索します。ASPやFO(.)などの豊富な知識表現言語やZincなどのCSPモデリング言語の有界モデル生成に対する最先端のアプローチは、グラウンディングアンドソルブです。つまり、理論をグラウンディングまたは命題理論に縮小し、結果の理論に検索アルゴリズムを適用します。重要なボトルネックは、グラウンディングフェーズによって引き起こされる理論のサイズの爆発です。検索中に理論を遅延グラウンディングすることは、このボトルネックを克服する方法です。FO(.)知識表現言語のコンテキストで理論的フレームワークと実装を紹介します。理論のすべての部分をグラウンディングするのではなく、理論の一部の正当性を導出します。理論の根拠部分に対する部分的な割り当てと、根拠のない部分の公式に対する有効な正当化が与えられた場合、それらの正当化は根拠のない部分を満たす完全な割り当てを構築するためのレシピを提供します。探索中に特定の公式に対する正当化が無効になった場合、新しい正当化が導出されます。それが失敗した場合、公式は根拠となる部分と正当化可能な部分に分割されます。実験結果は、このアプローチの威力と一般性を示しています。

Revision by History

Revision by History / 履歴による修正

This article proposes a solution to the problem of obtaining plausibility information, which is necessary to perform belief revision: given a sequence of revisions, together with their results, derive a possible initial order that has generated them; this is different from the usual assumption of starting from an all-equal initial order and modifying it by a sequence of revisions. Four semantics for iterated revision are considered: natural, restrained, lexicographic and reinforcement. For each, a necessary and sufficient condition to the existence of an order generating a given history of revisions and results is proved. Complexity is proved coNP complete in all cases but one (reinforcement revision with unbounded sequence length).



本稿では、信念修正を実行するために必要な妥当性情報を取得する問題に対する解決策を提案します。修正のシーケンスとその結果が与えられた場合、それらを生成した可能性のある初期順序を導出します。これは、すべて等しい初期順序から始めて、修正のシーケンスによってそれを修正するという通常の仮定とは異なります。反復修正の4つの意味論、すなわち自然、拘束、辞書式、強化が検討されます。それぞれについて、与えられた修正と結果の履歴を生成する順序の存在に対する必要十分条件が証明されます。計算量は、1つのケース（非有界シーケンス長の強化修正）を除くすべてのケースでcoNP完全であることが証明されています。

Scheduling Conservation Designs for Maximum Flexibility via Network Cascade Optimization

Scheduling Conservation Designs for Maximum Flexibility via Network Cascade Optimization / ネットワークカスケード最適化による柔軟性最大化のための保全設計のスケジューリング

One approach to conserving endangered species is to purchase and protect a set of land parcels in a way that maximizes the expected future population spread. Unfortunately, an ideal set of parcels may have a cost that is beyond the immediate budget constraints and must thus be purchased incrementally. This raises the challenge of deciding how to schedule the parcel purchases in a way that maximizes the flexibility of budget usage while keeping population spread loss in control. In this paper, we introduce a formulation of this scheduling problem that does not rely on knowing the future budgets of an organization. In particular, we consider scheduling purchases in a way that achieves a population spread no less than desired but delays purchases as long as possible. Such schedules offer conservation planners maximum flexibility and use available budgets in the most efficient way. We develop the problem formally as a stochastic optimization problem over a network cascade model describing a commonly used model of population spread. Our solution approach is based on reducing the stochastic problem to a novel variant of the directed Steiner tree problem, which we call the set-weighted directed Steiner graph problem. We show that this problem is computationally hard, motivating the development of a primal-dual algorithm for the problem that computes both a feasible solution and a bound on the quality of an optimal solution. We evaluate the approach on both real and synthetic conservation data with a standard population spread model. The algorithm is shown to produce near optimal results and is much more scalable than more generic off-the-shelf optimizers. Finally, we evaluate a variant of the algorithm to explore the trade-offs between budget savings and population growth.



絶滅危惧種を保護するための1つのアプローチは、将来の個体群拡散が最大化されるように土地区画を購入し保護することです。残念ながら、理想的な区画セットは、当面の予算制約を超えるコストを持つ場合があり、そのため段階的に購入する必要があります。これにより、個体群拡散による損失を抑制しつつ、予算使用の柔軟性を最大化するように区画購入のスケジュールを決定するという課題が生じます。本稿では、組織の将来の予算を知ることに依存しない、このスケジューリング問題の定式化を紹介します。特に、個体群拡散が望ましい値以下にならないようにしつつ、購入を可能な限り遅らせるような購入スケジュールを検討します。このようなスケジュールは、保全計画者に最大限の柔軟性を提供し、利用可能な予算を最も効率的に使用します。本稿では、この問題を、個体群拡散の一般的なモデルを記述するネットワークカスケードモデル上の確率最適化問題として正式に展開します。我々の解法は、確率的問題を有向シュタイナー木問題の新たな変種、すなわちセット重み付き有向シュタイナーグラフ問題へと縮減することに基づいています。この問題は計算的に困難であることを示し、実行可能解と最適解の質の上限の両方を計算するプライマル・デュアルアルゴリズムの開発の動機付けとなりました。我々は、標準的な個体群拡散モデルを用いて、実際の保全データと合成データの両方でこのアプローチを評価しました。このアルゴリズムはほぼ最適な結果を生み出し、より汎用的な市販の最適化ツールよりもはるかにスケーラブルであることが示されました。最後に、予算削減と個体群増加のトレードオフを調査するために、このアルゴリズムの変種を評価します。

Inferring Team Task Plans from Human Meetings: A Generative Modeling Approach with Logic-Based Prior

Inferring Team Task Plans from Human Meetings: A Generative Modeling Approach with Logic-Based Prior / 人間の会議からのチームタスクプランの推論：論理ベースの事前分布を用いた生成モデリングアプローチ

We aim to reduce the burden of programming and deploying autonomous systems to work in concert with people in time-critical domains such as military field operations and disaster response. Deployment plans for these operations are frequently negotiated on-the-fly by teams of human planners. A human operator then translates the agreed-upon plan into machine instructions for the robots. We present an algorithm that reduces this translation burden by inferring the final plan from a processed form of the human team’s planning conversation. Our hybrid approach combines probabilistic generative modeling with logical plan validation used to compute a highly structured prior over possible plans, enabling us to overcome the challenge of performing inference over a large solution space with only a small amount of noisy data from the team planning session. We validate the algorithm through human subject experimentations and show that it is able to infer a human team’s final plan with 86% accuracy on average. We also describe a robot demonstration in which two people plan and execute a first-response collaborative task with a PR2 robot. To the best of our knowledge, this is the first work to integrate a logical planning technique within a generative model to perform plan inference.



軍事現場作戦や災害対応といった時間的制約が厳しい分野において、人間と連携して作業を行う自律システムのプログラミングと展開にかかる負担を軽減することを目指しています。これらの作戦における展開計画は、人間の計画担当者チームによって頻繁にオンザフライで交渉されます。その後、人間のオペレーターが合意された計画をロボット用の機械命令に変換します。本研究では、人間チームの計画会話を加工したものから最終計画を推論することで、この変換負担を軽減するアルゴリズムを提示します。このハイブリッドアプローチは、確率的生成モデリングと、可能な計画に対する高度に構造化された事前確率を計算する論理的計画検証を組み合わせたもので、チーム計画セッションからの少量のノイズデータのみを用いて、広大な解空間で推論を実行するという課題を克服します。本アルゴリズムを被験者実験により検証し、人間チームの最終計画を平均86%の精度で推論できることを示します。また、2人がPR2ロボットを用いて初動対応の協調タスクを計画・実行するロボットのデモンストレーションについても説明します。我々の知る限り、これは生成モデルに論理プランニング手法を統合し、計画推論を実行する初めての研究です。

Computing Convex Coverage Sets for Faster Multi-objective Coordination

Computing Convex Coverage Sets for Faster Multi-objective Coordination / 多目的コーディネーションの高速化のための凸被覆集合の計算

In this article, we propose new algorithms for multi-objective coordination graphs (MO-CoGs). Key to the efficiency of these algorithms is that they compute a convex coverage set (CCS) instead of a Pareto coverage set (PCS). Not only is a CCS a sufficient solution set for a large class of problems, it also has important characteristics that facilitate more efficient solutions. We propose two main algorithms for computing a CCS in MO-CoGs. Convex multi-objective variable elimination (CMOVE) computes a CCS by performing a series of agent eliminations, which can be seen as solving a series of local multi-objective subproblems. Variable elimination linear support (VELS) iteratively identifies the single weight vector, w, that can lead to the maximal possible improvement on a partial CCS and calls variable elimination to solve a scalarized instance of the problem for w. VELS is faster than CMOVE for small and medium numbers of objectives and can compute an ε-approximate CCS in a fraction of the runtime. In addition, we propose variants of these methods that employ AND/OR tree search instead of variable elimination to achieve memory efficiency. We analyze the runtime and space complexities of these methods, prove their correctness, and compare them empirically against a naive baseline and an existing PCS method, both in terms of memory-usage and runtime. Our results show that, by focusing on the CCS, these methods achieve much better scalability in the number of agents than the current state of the art.



本稿では、多目的コーディネーショングラフ（MO-CoG）のための新しいアルゴリズムを提案します。これらのアルゴリズムの効率性の鍵は、パレート被覆集合（PCS）ではなく凸被覆集合（CCS）を計算する点にあります。CCSは多くの問題に対して十分な解集合であるだけでなく、より効率的な解法を可能にする重要な特性も備えています。本稿では、MO-CoGにおけるCCSを計算するための2つの主要なアルゴリズムを提案します。凸多目的変数除去（CMOVE）は、一連のエージェント除去を実行することでCCSを計算します。これは、一連の局所多目的サブ問題を解くこととみなせる。変数除去線形サポート（VELS）は、部分CCSの最大改善をもたらす単一の重みベクトルwを反復的に特定し、wに対する問題のスカラー化されたインスタンスを解くために変数除去を呼び出す。VELSは、目的関数の数が少～中程度の場合、CMOVEよりも高速であり、ε近似CCSをわずかな実行時間で計算できます。さらに、変数除去の代わりにAND/OR木探索を用いてメモリ効率を向上させる、これらの手法の派生を提案します。これらの手法の実行時間と空間計算量を分析し、その正しさを証明し、メモリ使用量と実行時間の両方の観点から、単純なベースラインおよび既存のPCS手法と実験的に比較します。結果は、CCSに焦点を合わせることで、これらの手法が現在の最先端技術よりもはるかに優れたエージェント数に対するスケーラビリティを実現することを示しています。

Modeling the Lifespan of Discourse Entities with Application to Coreference Resolution

Modeling the Lifespan of Discourse Entities with Application to Coreference Resolution / 談話エンティティの寿命のモデリングと共参照解決への応用

A discourse typically involves numerous entities, but few are mentioned more than once. Distinguishing those that die out after just one mention (singleton) from those that lead longer lives (coreferent) would dramatically simplify the hypothesis space for coreference resolution models, leading to increased performance. To realize these gains, we build a classifier for predicting the singleton/coreferent distinction. The models feature representations synthesize linguistic insights about the factors affecting discourse entity lifespans (especially negation, modality, and attitude predication) with existing results about the benefits of surface (part-of-speech and n-gram-based) features for coreference resolution. The model is effective in its own right, and the feature representations help to identify the anchor phrases in bridging anaphora as well. Furthermore, incorporating the model into two very different state-of-the-art coreference resolution systems, one rule-based and the other learning-based, yields significant performance improvements.



談話には通常、多数のエンティティが含まれますが、複数回言及されることはほとんどありません。1回の言及で消滅するエンティティ(シングルトン)と、より長い寿命を持つエンティティ(共参照先)を区別することで、共参照解決モデルの仮説空間が大幅に簡素化され、パフォーマンスが向上します。この利点を実現するために、シングルトン/共参照先の区別を予測する分類器を構築します。モデルの特徴表現は、談話エンティティの寿命に影響を与える要因(特に否定、モダリティ、態度の述語)に関する言語的洞察と、共参照解決における表層(品詞およびnグラムベース)の特徴の利点に関する既存の結果を統合します。このモデルはそれ自体で効果的であり、特徴表現は橋渡し照応におけるアンカー フレーズの識別にも役立ちます。さらに、このモデルを、ルールベースと学習ベースの2つの非常に異なる最先端の共参照解決システムに組み込むことで、パフォーマンスが大幅に向上します。

A Case-Based Reasoning Framework to Choose Trust Models for Different E-Marketplace Environments

A Case-Based Reasoning Framework to Choose Trust Models for Different E-Marketplace Environments / 異なるEマーケットプレイス環境における信頼モデルを選択するための事例ベース推論フレームワーク

The performance of trust models highly depend on the characteristics of the environments where they are applied. Thus, it becomes challenging to choose a suitable trust model for a given e-marketplace environment, especially when ground truth about the agent (buyer and seller) behavior is unknown (called unknown environment). We propose a case-based reasoning framework to choose suitable trust models for unknown environments, based on the intuition that if a trust model performs well in one environment, it will do so in another similar environment. Firstly, we build a case base with a number of simulated environments (with known ground truth) along with the trust models most suitable for each of them. Given an unknown environment, case-based retrieval algorithms retrieve the most similar case(s), and the trust model of the most similar case(s) is chosen as the most suitable model for the unknown environment. Evaluation results confirm the effectiveness of our framework in choosing suitable trust models for different e-marketplace environments.



信頼モデルのパフォーマンスは、それが適用される環境の特性に大きく依存します。そのため、特定の電子市場環境に適した信頼モデルを選択することは困難であり、特にエージェント（買い手と売り手）の行動に関するグラウンドトゥルースが不明な場合（未知環境と呼ばれる）は困難です。本稿では、ある環境で信頼モデルが良好に機能すれば、他の類似環境でも良好に機能するという直感に基づき、未知の環境に適した信頼モデルを選択するための事例ベース推論フレームワークを提案します。まず、多数のシミュレートされた環境（グラウンドトゥルースが既知）と、それぞれに最適な信頼モデルを含む事例ベースを構築します。未知の環境が与えられると、事例ベース検索アルゴリズムが最も類似した事例を検索し、最も類似した事例の信頼モデルが未知の環境に最適なモデルとして選択されます。評価結果は、異なる電子市場環境に適切な信頼モデルを選択する上での本フレームワークの有効性を確認しています。

Weighted Electoral Control

Weighted Electoral Control / 重み付け選挙管理

Although manipulation and bribery have been extensively studied under weighted voting, there has been almost no work done on election control under weighted voting. This is unfortunate, since weighted voting appears in many important natural settings. In this paper, we study the complexity of controlling the outcome of weighted elections through adding and deleting voters. We obtain polynomial-time algorithms, NP-completeness results, and for many NP-complete cases, approximation algorithms. In particular, for scoring rules we completely characterize the complexity of weighted voter control. Our work shows that for quite a few important cases, either polynomial-time exact algorithms or polynomial-time approximation algorithms exist.



加重投票における操作と賄賂は広く研究されてきましたが、加重投票における選挙制御に関する研究はほとんど行われていません。これは残念なことです。なぜなら、重み付け投票は多くの重要な自然状況に現れるからです。本稿では、投票者の追加と削除を通じて重み付け選挙の結果を制御する複雑さを考察します。多項式時間アルゴリズム、NP完全性の結果、そして多くのNP完全ケースに対する近似アルゴリズムを得ます。特に、スコアリングルールについて、重み付け投票者制御の複雑さを完全に特徴付けます。私たちの研究は、かなりの数の重要なケースにおいて、多項式時間厳守アルゴリズムまたは多項式時間近似アルゴリズムのいずれかが存在することを示しています。

Distributed Evaluation of Nonmonotonic Multi-context Systems

Distributed Evaluation of Nonmonotonic Multi-context Systems / 非単調なマルチコンテキストシステムの分散評価

Multi-context Systems (MCSs) are a formalism for systems consisting of knowledge bases (possibly heterogeneous and non-monotonic) that are interlinked via bridge rules, where the global system semantics emerges from the local semantics of the knowledge bases (also called contexts) in an equilibrium. While MCSs and related formalisms are inherently targeted for distributed set- tings, no truly distributed algorithms for their evaluation were available. We address this short- coming and present a suite of such algorithms which includes a basic algorithm DMCS, an ad- vanced version DMCSOPT that exploits topology-based optimizations, and a streaming algorithm DMCS-STREAMING that computes equilibria in packages of bounded size. The algorithms be- have quite differently in several respects, as experienced in thorough experimental evaluation of a system prototype. From the experimental results, we derive a guideline for choosing the appropriate algorithm and running mode in particular situations, determined by the parameter settings.



マルチコンテキストシステム（MCS）は、ブリッジルールを介して相互にリンクされた知識ベース（異種かつ非単調である可能性もある）で構成されるシステムの形式主義であり、均衡状態にある知識ベース（コンテキストとも呼ばれる）のローカルな意味論から、グローバルなシステムの意味論が出現します。MCSおよび関連する形式主義は本質的に分散環境を対象としていますが、それらを評価するための真に分散的なアルゴリズムは存在しませんでした。我々はこの欠点を克服し、基本アルゴリズムDMCS、トポロジーベースの最適化を活用する拡張版DMCS-STREAMING、そして有限サイズのパッケージ内で平衡点を計算するストリーミングアルゴリズムDMCS-STREAMINGを含む一連のアルゴリズムを提示します。システムプロトタイプの徹底的な実験評価において、これらのアルゴリズムはいくつかの点で全く異なる動作を示すことが確認されました。実験結果から、パラメータ設定によって決定される特定の状況において適切なアルゴリズムと実行モードを選択するためのガイドラインを導出します。

A Compositional Framework for Grounding Language Inference, Generation, and Acquisition in Video

A Compositional Framework for Grounding Language Inference, Generation, and Acquisition in Video / ビデオにおける言語推論、生成、獲得のグラウンディングのための構成的フレームワーク

We present an approach to simultaneously reasoning about a video clip and an entire natural-language sentence. The compositional nature of language is exploited to construct models which represent the meanings of entire sentences composed out of the meanings of the words in those sentences mediated by a grammar that encodes the predicate-argument relations. We demonstrate that these models faithfully represent the meanings of sentences and are sensitive to how the roles played by participants (nouns), their characteristics (adjectives), the actions performed (verbs), the manner of such actions (adverbs), and changing spatial relations between participants (prepositions) affect the meaning of a sentence and how it is grounded in video. We exploit this methodology in three ways. In the first, a video clip along with a sentence are taken as input and the participants in the event described by the sentence are highlighted, even when the clip depicts multiple similar simultaneous events. In the second, a video clip is taken as input without a sentence and a sentence is generated that describes an event in that clip. In the third, a corpus of video clips is paired with sentences which describe some of the events in those clips and the meanings of the words in those sentences are learned. We learn these meanings without needing to specify which attribute of the video clips each word in a given sentence refers to. The learned meaning representations are shown to be intelligible to humans.



本稿では、ビデオクリップと自然言語文全体を同時に推論する手法を提示します。言語の合成特性を利用し、述語項関係を符号化する文法を介して、文中の単語の意味から構成される文全体の意味を表現するモデルを構築します。これらのモデルは文の意味を忠実に表現し、参加者（名詞）の役割、参加者の特性（形容詞）、実行される動作（動詞）、その動作の様態（副詞）、参加者間の空間関係の変化（前置詞）が、文の意味とビデオにおける文の根拠にどのような影響を与えるかを敏感に捉える。本手法は3つの方法で活用します。1つ目は、ビデオクリップと文を入力として取り、そのクリップが複数の類似した同時発生を描写している場合でも、文で説明されるイベントの参加者を強調表示します。2つ目は、文を含まないビデオクリップを入力として取り、そのクリップ内のイベントを説明する文を生成します。3つ目の手法では、ビデオ クリップのコーパスと、クリップ内のイベントの一部を記述する文を組み合わせ、文中の単語の意味を学習します。各文中の単語がビデオ クリップのどの属性を指しているかを指定する必要なく、これらの意味を学習します。学習された意味表現は人間にとって理解可能であることが示されています。

Deterministic Oversubscription Planning as Heuristic Search: Abstractions and Reformulations

Deterministic Oversubscription Planning as Heuristic Search: Abstractions and Reformulations / ヒューリスティック探索としての決定論的オーバーサブスクリプションプランニング：抽象化および再定式化

While in classical planning the objective is to achieve one of the equally attractive goal states at as low total action cost as possible, the objective in deterministic oversubscription planning (OSP) is to achieve an as valuable as possible subset of goals within a fixed allowance of the total action cost. Although numerous applications in various fields share the latter objective, no substantial algorithmic advances have been made in deterministic OSP. Tracing the key sources of progress in classical planning, we identify a severe lack of effective domain-independent approximations for OSP. With our focus here on optimal planning, our goal is to bridge this gap. Two classes of approximation techniques have been found especially useful in the context of optimal classical planning: those based on state-space abstractions and those based on logical landmarks for goal reachability. The question we study here is whether some similar-in-spirit, yet possibly mathematically different, approximation techniques can be developed for OSP. In the context of abstractions, we define the notion of additive abstractions for OSP, study the complexity of deriving effective abstractions from a rich space of hypotheses, and reveal some substantial, empirically relevant islands of tractability. In the context of landmarks, we show how standard goal-reachability landmarks of certain classical planning tasks can be compiled into the OSP task of interest, resulting in an equivalent OSP task with a lower cost allowance, and thus with a smaller search space. Our empirical evaluation confirms the effectiveness of the proposed techniques, and opens a wide gate for further developments in oversubscription planning.



従来の計画では、目標とする目標状態のうち、同等に魅力的な目標状態を、可能な限り低い総行動コストで達成することが目的ですが、決定論的過剰サブスクリプション計画(OSP)では、総行動コストの一定の許容範囲内で、可能な限り価値の高い目標のサブセットを達成することが目的です。様々な分野で多数のアプリケーションが後者の目的を共有していますが、決定論的OSPのアルゴリズムにおける大幅な進歩は見られません。従来の計画における進歩の主要な源泉を辿ると、OSPに対する有効なドメイン非依存近似が著しく不足していることがわかります。ここでは最適計画に焦点を当て、このギャップを埋めることが目標です。近似手法には、状態空間抽象化に基づくものと、目標到達可能性の論理ランドマークに基づくものの2種類があり、これらは特に最適な古典的計画の文脈において有用であることが分かっています。本稿で検討する問題は、OSPに対して、精神は類似しているものの数学的には異なる可能性のある近似手法を開発できるかどうかです。抽象化の文脈では、OSPに対する加法的な抽象化の概念を定義し、豊富な仮説空間から有効な抽象化を導出する複雑さを研究し、経験的に重要な、重要な扱いやすい領域を明らかにします。ランドマークの文脈では、特定の古典的計画タスクの標準的な目標到達可能性ランドマークを、対象のOSPタスクにコンパイルする方法を示します。これにより、コスト許容度が低く、したがって探索空間が小さい、同等のOSPタスクが得られます。本実証的評価は、提案手法の有効性を確認し、オーバーサブスクリプション計画のさらなる発展への大きな扉を開きます。

参考文献

関連情報