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

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

論文

Knowledge-Based Textual Inference via Parse-Tree Transformations

Knowledge-Based Textual Inference via Parse-Tree Transformations / 構文木変換による知識ベーステキスト推論

Textual inference is an important component in many applications for understanding natural language. Classical approaches to textual inference rely on logical representations for meaning, which may be regarded as “external” to the natural language itself. However, practical applications usually adopt shallower lexical or lexical-syntactic representations, which correspond closely to language structure. In many cases, such approaches lack a principled meaning representation and inference framework. We describe an inference formalism that operates directly on language-based structures, particularly syntactic parse trees. New trees are generated by applying inference rules, which provide a unified representation for varying types of inferences. We use manual and automatic methods to generate these rules, which cover generic linguistic structures as well as specific lexical-based inferences. We also present a novel packed data-structure and a corresponding inference algorithm that allows efficient implementation of this formalism. We proved the correctness of the new algorithm and established its efficiency analytically and empirically. The utility of our approach was illustrated on two tasks: unsupervised relation extraction from a large corpus, and the Recognizing Textual Entailment (RTE) benchmarks.



テキスト推論は、自然言語を理解するための多くのアプリケーションにおいて重要な要素です。テキスト推論の古典的なアプローチは、意味の論理的表現に依存しており、これは自然言語自体の「外部」にあると見なすことができます。しかし、実用的なアプリケーションでは通常、言語構造に密接に対応する、より浅い語彙的または語彙統語的表現が採用されます。多くの場合、このようなアプローチには、原理的な意味表現と推論のフレームワークが欠けています。本稿では、言語ベースの構造、特に統語構文解析木に直接作用する推論形式について説明します。推論規則を適用することで新しい木が生成され、さまざまな種類の推論に統一された表現が提供されます。一般的な言語構造と特定の語彙ベースの推論をカバーするこれらの規則を生成するために、手動と自動の方法を使用します。また、この形式を効率的に実装できる、新しいパックデータ構造と対応する推論アルゴリズムも紹介します。新しいアルゴリズムの正しさを証明し、その効率性を分析的および経験的に確立しました。本手法の有用性は、大規模コーパスからの教師なし関係抽出と、テキスト含意認識（RTE）ベンチマークという2つのタスクで実証されました。

Achieving Goals Quickly Using Real-time Search: Experimental Results in Video Games

Achieving Goals Quickly Using Real-time Search: Experimental Results in Video Games / リアルタイム検索を用いた迅速な目標達成：ビデオゲームにおける実験結果

In real-time domains such as video games, planning happens concurrently with execution and the planning algorithm has a strictly bounded amount of time before it must return the next action for the agent to execute. We explore the use of real-time heuristic search in two benchmark domains inspired by video games. Unlike classic benchmarks such as grid pathfinding and the sliding tile puzzle, these new domains feature exogenous change and directed state space graphs. We consider the setting in which planning and acting are concurrent and we use the natural objective of minimizing goal achievement time. Using both the classic benchmarks and the new domains, we investigate several enhancements to a leading real-time search algorithm, LSS-LRTA*. We show experimentally that 1) it is better to plan after each action or to use a dynamically sized lookahead, 2) A*-based lookahead can cause undesirable actions to be selected, and 3) on-line de-biasing of the heuristic can lead to improved performance. We hope this work encourages future research on applying real-time search in dynamic domains.



ビデオゲームなどのリアルタイム領域では、計画は実行と並行して行われ、計画アルゴリズムはエージェントが実行すべき次の行動を返すまでの時間が厳密に制限されています。本研究では、ビデオゲームに着想を得た2つのベンチマーク領域において、リアルタイムヒューリスティック探索の適用について考察します。グリッドパスファインディングやスライディングタイルパズルといった従来のベンチマークとは異なり、これらの新しい領域は外生的変化と有向状態空間グラフを特徴としています。本研究では、計画と行動が並行して行われる設定を考慮し、目標達成時間の最小化という自然な目標を用います。従来のベンチマークと新しい領域の両方を用いて、主要なリアルタイム探索アルゴリズムであるLSS-LRTA*のいくつかの改良点を調査します。実験的に、1)各行動の後に計画を行うか、動的にサイズが変化する先読みを使用する方が効果的であること、2) A*ベースの先読みは望ましくない行動を選択する可能性があること、3)ヒューリスティックのオンラインバイアス除去によって性能が向上する可能性があることを示します。この研究が、動的な領域におけるリアルタイム検索の適用に関する将来の研究を促進することを期待しています。

Leveraging Online User Feedback to Improve Statistical Machine Translation

Leveraging Online User Feedback to Improve Statistical Machine Translation / オンラインユーザーフィードバックを活用した統計的機械翻訳の改善

In this article we present a three-step methodology for dynamically improving a statistical machine translation (SMT) system by incorporating human feedback in the form of free edits on the system translations. We target at feedback provided by casual users, which is typically error-prone. Thus, we first propose a filtering step to automatically identify the better user-edited translations and discard the useless ones. A second step produces a pivot-based alignment between source and user-edited sentences, focusing on the errors made by the system. Finally, a third step produces a new translation model and combines it linearly with the one from the original system. We perform a thorough evaluation on a real-world dataset collected from the Reverso.net translation service and show that every step in our methodology contributes significantly to improve a general purpose SMT system. Interestingly, the quality improvement is not only due to the increase of lexical coverage, but to a better lexical selection, reordering, and morphology. Finally, we show the robustness of the methodology by applying it to a different scenario, in which the new examples come from an automatically Web-crawled parallel corpus. Using exactly the same architecture and models provides again a significant improvement of the translation quality of a general purpose baseline SMT system.



本稿では、システム翻訳に対する自由編集という形で人間によるフィードバックを取り入れることで、統計的機械翻訳（SMT）システムを動的に改善するための3段階の方法論を提示します。本稿では、一般的に誤りが発生しやすい、一般ユーザーから提供されるフィードバックを対象とします。そこで、まず、より優れたユーザー編集翻訳を自動的に識別し、不要な翻訳を破棄するフィルタリングステップを提案します。2番目のステップでは、システムによって発生した誤りに焦点を当て、原文とユーザー編集文の間のピボットベースのアラインメントを作成します。最後に、3番目のステップで新しい翻訳モデルを作成し、元のシステムのモデルと線形結合します。Reverso.net翻訳サービスから収集した実際のデータセットを徹底的に評価し、本方法論の各ステップが汎用SMTシステムの改善に大きく貢献することを示します。興味深いことに、品質向上は語彙カバレッジの拡大だけでなく、語彙の選択、並べ替え、形態素解析の改善によってももたらされます。最後に、新しい用例が自動Webクロールされた並列コーパスから得られるという異なるシナリオに本手法を適用することにより、その堅牢性を示します。全く同じアーキテクチャとモデルを使用することで、汎用ベースラインSMTシステムの翻訳品質が大幅に向上します。

Expressiveness of Two-Valued Semantics for Abstract Dialectical Frameworks

Expressiveness of Two-Valued Semantics for Abstract Dialectical Frameworks / 抽象弁証法的枠組みにおける二値意味論の表現力

We analyse the expressiveness of Brewka and Woltran’s abstract dialectical frameworks for two-valued semantics. By expressiveness we mean the ability to encode a desired set of two-valued interpretations over a given propositional vocabulary A using only atoms from A. We also compare ADFs’ expressiveness with that of (the two-valued semantics of) abstract argumentation frameworks, normal logic programs and propositional logic. While the computational complexity of the two-valued model existence problem for all these languages is (almost) the same, we show that the languages form a neat hierarchy with respect to their expressiveness. We then demonstrate that this hierarchy collapses once we allow to introduce a linear number of new vocabulary elements. We finally also analyse and compare the representational succinctness of ADFs (for two-valued model semantics), that is, their capability to represent two-valued interpretation sets in a space-efficient manner.



BrewkaとWoltranによる二値意味論のための抽象弁証法的枠組みの表現力を分析します。ここでの表現力とは、与えられた命題語彙Aのアトムのみを用いて、A上の所望の二値解釈集合を符号化する能力を指します。また、ADFの表現力を、抽象議論枠組み、通常論理プログラム、命題論理（の二値意味論）の表現力と比較します。これらの言語すべてにおいて、二値モデル存在問題の計算量は（ほぼ）同じですが、これらの言語は表現力に関して明確な階層構造を形成することを示します。そして、この階層構造は、新しい語彙要素を線形数導入すると崩壊することを示します。最後に、ADF（2値モデルセマンティクス用）の表現の簡潔性、つまり、空間効率の高い方法で2値解釈セットを表現する能力についても分析および比較します。

Decision Making with Dynamic Uncertain Events

Decision Making with Dynamic Uncertain Events / 動的な不確実なイベントを用いた意思決定

When to make a decision is a key question in decision making problems characterized by uncertainty. In this paper we deal with decision making in environments where information arrives dynamically. We address the tradeoff between waiting and stopping strategies. On the one hand, waiting to obtain more information reduces uncertainty, but it comes with a cost. Stopping and making a decision based on an expected utility reduces the cost of waiting, but the decision is based on uncertain information. We propose an optimal algorithm and two approximation algorithms. We prove that one approximation is optimistic – waits at least as long as the optimal algorithm, while the other is pessimistic – stops not later than the optimal algorithm. We evaluate our algorithms theoretically and empirically and show that the quality of the decision in both approximations is near-optimal and much faster than the optimal algorithm. Also, we can conclude from the experiments that the cost function is a key factor to chose the most effective algorithm.



不確実性を伴う意思決定問題において、いつ意思決定を行うかは重要な問題です。本稿では、情報が動的に到着する環境における意思決定を扱います。待機戦略と停止戦略のトレードオフを取り上げます。一方では、より多くの情報を得るために待機することで不確実性は低減しますが、それにはコストがかかります。停止して期待効用に基づいて意思決定を行うと待機コストは低減しますが、その意思決定は不確実な情報に基づいています。本稿では、最適なアルゴリズムと2つの近似アルゴリズムを提案します。1つの近似は楽観的（少なくとも最適なアルゴリズムと同じ時間待機する）であり、もう1つは悲観的（最適なアルゴリズムよりも遅くないうちに停止する）であることを証明します。本アルゴリズムを理論的および経験的に評価し、両方の近似における意思決定の質はほぼ最適であり、最適なアルゴリズムよりもはるかに高速であることを示します。また、実験から、コスト関数が最も効果的なアルゴリズムを選択するための重要な要素であることが結論付けられます。

Relations Between Spatial Calculi About Directions and Orientations

Relations Between Spatial Calculi About Directions and Orientations / 方向と向きに関する空間計算間の関係

Qualitative spatial descriptions characterize essential properties of spatial objects or configurations by relying on relative comparisons rather than measuring. Typically, in qualitative approaches only relatively coarse distinctions between configurations are made. Qualitative spatial knowledge can be used to represent incomplete and underdetermined knowledge in a systematic way. This is especially useful if the task is to describe features of classes of configurations rather than individual configurations.Although reasoning with them is generally NP-hard, relative directions are important because they play a key role in human spatial descriptions and there are several approaches how to represent them using qualitative methods. In these approaches directions between spatial locations can be expressed as constraints over infinite domains, e.g. the Euclidean plane. The theory of relation algebras has been successfully applied to this field. Viewing relation algebras as universal algebras and applying and modifying standard tools from universal algebra in this work, we (re)define notions of qualitative constraint calculus, of homomorphism between calculi, and of quotient of calculi. Based on this method we derive important properties for spatial calculi from corresponding properties of related calculi. From a conceptual point of view these formal mappings between calculi are a means to translate between different granularities.



定性的な空間記述は、測定ではなく相対的な比較に頼ることで、空間オブジェクトまたは構成の本質的な特性を特徴付けます。典型的には、定性的なアプローチでは、構成間の比較的粗い区別しか行われません。定性的な空間知識は、不完全で不確定な知識を体系的に表現するために使用できます。これは、個々の構成ではなく、構成のクラスの特徴を記述するタスクの場合に特に有用です。定性的な空間知識を用いた推論は一般的にNP困難ですが、相対方向は人間の空間記述において重要な役割を果たすため重要であり、定性的な方法を用いて相対方向を表現する方法はいくつかあります。これらのアプローチでは、空間位置間の方向は、例えばユークリッド平面などの無限領域上の制約として表現できます。関係代数の理論は、この分野にうまく適用されてきました。本研究では、関係代数を普遍代数と見なし、普遍代数の標準的なツールを適用および修正することで、定性制約計算、計算間の準同型性、および計算の商の概念を（再）定義します。この方法に基づいて、関連する計算の対応する特性から、空間計算の重要な特性を導き出します。概念的な観点から見ると、計算間のこれらの正式なマッピングは、異なる粒度間で変換するための手段です。

PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner

PAGOdA: Pay-As-You-Go Ontology Query Answering Using a Datalog Reasoner / PAGOdA：従量課金制オントロジークエリ回答データログ推論装置

Answering conjunctive queries over ontology-enriched datasets is a core reasoning task for many applications. Query answering is, however, computationally very expensive, which has led to the development of query answering procedures that sacrifice either expressive power of the ontology language, or the completeness of query answers in order to improve scalability. In this paper, we describe a hybrid approach to query answering over OWL 2 ontologies that combines a datalog reasoner with a fully-fledged OWL 2 reasoner in order to provide scalable `pay-as-you-go’ performance. The key feature of our approach is that it delegates the bulk of the computation to the datalog reasoner and resorts to expensive OWL 2 reasoning only as necessary to fully answer the query. Furthermore, although our main goal is to efficiently answer queries over OWL 2 ontologies and data, our technical results are very general and our approach is applicable to first-order knowledge representation languages that can be captured by rules allowing for existential quantification and disjunction in the head; our only assumption is the availability of a datalog reasoner and a fully-fledged reasoner for the language of interest, both of which are used as `black boxes’. We have implemented our techniques in the PAGOdA system, which combines the datalog reasoner RDFox and the OWL 2 reasoner HermiT. Our extensive evaluation shows that PAGOdA succeeds in providing scalable pay-as-you-go query answering for a wide range of OWL 2 ontologies, datasets and queries.



オントロジーが強化されたデータセットに対する連言クエリへの回答は、多くのアプリケーションにとって中核的な推論タスクです。しかし、クエリ回答は計算コストが非常に高いため、スケーラビリティを向上させるためにオントロジー言語の表現力やクエリ回答の完全性を犠牲にするクエリ回答手順が開発されてきました。本稿では、スケーラブルな「従量制」パフォーマンスを提供するために、データログ推論エンジンと本格的なOWL 2推論エンジンを組み合わせた、OWL 2オントロジーに対するクエリ回答のハイブリッドアプローチについて説明します。このアプローチの主な特徴は、計算の大部分をデータログ推論エンジンに委譲し、クエリに完全に回答するために必要な場合にのみ、高価なOWL 2推論を使用することです。さらに、私たちの主な目標はOWL 2オントロジーとデータに対するクエリに効率的に回答することですが、私たちの技術的結果は非常に汎用的であり、私たちのアプローチは、ヘッドで存在量化と選言を可能にする規則によって捉えることができる第一階知識表現言語に適用できます。私たちの唯一の前提は、データログ推論エンジンと対象言語用の本格的な推論エンジンが利用可能であることです。これらは両方とも「ブラックボックス」として使用されます。私たちは、データログ推論エンジンRDFoxとOWL 2推論エンジンHermiTを組み合わせたPAGOdAシステムに私たちの技術を実装しました。広範囲にわたる評価により、PAGOdAは幅広いOWL 2オントロジー、データセット、クエリに対して、スケーラブルな従量課金制のクエリ回答を提供できることが示されています。

Continuing Plan Quality Optimisation

Continuing Plan Quality Optimisation / 継続的な計画品質の最適化

Finding high quality plans for large planning problems is hard. Although some current anytime planners are often able to improve plans quickly, they tend to reach a limit at which the plans produced are still very far from the best possible, but these planners fail to find any further improvement, even when given several hours of runtime.We present an approach to continuing plan quality optimisation at larger time scales, and its implementation in a system called BDPO2. Key to this approach is a decomposition into subproblems of improving parts of the current best plan. The decomposition is based on block deordering, a form of plan deordering which identifies hierarchical plan structure. BDPO2 can be seen as an application of the large neighbourhood search (LNS) local search strategy to planning, where the neighbourhood of a plan is defined by replacing one or more subplans with improved subplans. On-line learning is also used to adapt the strategy for selecting subplans and subplanners over the course of plan optimisation.Even starting from the best plans found by other means, BDPO2 is able to continue improving plan quality, often producing better plans than other anytime planners when all are given enough runtime. The best results, however, are achieved by a combination of different techniques working together.



大規模な計画問題に対する高品質な計画を見つけることは困難です。現在のいつでも実行可能なプランナーの中には、計画を迅速に改善できるものもありますが、生成された計画が最良のものからまだほど遠いという限界に達する傾向があります。しかし、これらのプランナーは、数時間の実行時間を与えても、それ以上の改善を見つけることができません。私たちは、より大きな時間スケールで計画品質の最適化を継続するアプローチと、BDPO2と呼ばれるシステムへの実装を紹介します。このアプローチの鍵となるのは、現在の最良の計画の部分を改善するサブ問題への分解です。分解は、階層的なプラン構造を識別するプランデオーダーリングの一種であるブロックデオーダーリングに基づいています。BDPO2は、大規模近傍探索(LNS)ローカルサーチ戦略を計画に応用したものと見なすことができます。この戦略では、プランの近傍は、1つ以上のサブプランを改善されたサブプランに置き換えることによって定義されます。オンライン学習は、プランの最適化の過程でサブプランとサブプランナーを選択する戦略を適応させるためにも使用されます。他の手段で見つかった最良のプランから始めても、BDPO2はプランの品質を継続的に向上させることができ、十分な実行時間が与えられれば、他のいつでもプランナーよりも優れたプランを生成することがよくあります。ただし、最良の結果は、さまざまな手法を組み合わせて連携させることで達成されます。

Constraining Information Sharing to Improve Cooperative Information Gathering

Constraining Information Sharing to Improve Cooperative Information Gathering / 協調的情報収集を改善するための情報共有の制約

This paper considers the problem of cooperation between self-interested agents in acquiring better information regarding the nature of the different options and opportunities available to them. By sharing individual findings with others, the agents can potentially achieve a substantial improvement in overall and individual expected benefits. Unfortunately, it is well known that with self-interested agents equilibrium considerations often dictate solutions that are far from the fully cooperative ones, hence the agents do not manage to fully exploit the potential benefits encapsulated in such cooperation. In this paper we introduce, analyze and demonstrate the benefit of five methods aiming to improve cooperative information gathering. Common to all five that they constrain and limit the information sharing process. Nevertheless, the decrease in benefit due to the limited sharing is outweighed by the resulting substantial improvement in the equilibrium individual information gathering strategies. The equilibrium analysis given in the paper, which, in itself is an important contribution to the study of cooperation between self-interested agents, enables demonstrating that for a wide range of settings an improved individual expected benefit is achieved for all agents when applying each of the five methods.



本稿では、利己的なエージェントが、利用可能なさまざまなオプションと機会の性質に関するより良い情報を取得するための協力の問題について考察します。個々の発見を他のエージェントと共有することで、エージェントは全体および個々の期待される利益を大幅に向上させる可能性があります。残念ながら、利己的なエージェントの場合、均衡を考慮すると、完全に協力的な解決策からはほど遠い解決策がしばしば指示されることがよく知られており、そのため、エージェントはそのような協力に内包されている潜在的な利益を十分に活用することができません。本稿では、協力的な情報収集を改善することを目指す5つの方法を紹介、分析し、その利点を実証します。これら5つの方法すべてに共通するのは、情報共有プロセスを制約し制限することです。しかし、共有が制限されることによる利益の減少は、均衡した個々の情報収集戦略の結果として生じる大幅な改善によって上回られます。本稿で示されている均衡分析は、それ自体が利己的なエージェント間の協力の研究への重要な貢献であり、さまざまな設定において、5つの方法のそれぞれを適用すると、すべてのエージェントに対して改善された個々の期待利益が達成されることを示すことができます。

Weighted Regret-Based Likelihood: A New Approach to Describing Uncertainty

Weighted Regret-Based Likelihood: A New Approach to Describing Uncertainty / 重み付きリグレットベースの尤度：不確実性を記述する新しいアプローチ

Recently, Halpern and Leung suggested representing uncertainty by a set of weighted probability measures, and suggested a way of making decisions based on this representation of uncertainty: maximizing weighted regret. Their paper does not answer an apparently simpler question: what it means, according to this representation of uncertainty, for an event E to be more likely than an event E’. In this paper, a notion of comparative likelihood when uncertainty is represented by a set of weighted probability measures is defined. It generalizes the ordering defined by probability (and by lower probability) in a natural way; a generalization of upper probability can also be defined. A complete axiomatic characterization of this notion of regret-based likelihood is given.



最近、ハルパーンとレオンは、不確実性を重み付き確率尺度の集合で表現し、この不確実性の表現に基づいて意思決定を行う方法、すなわち重み付き後悔の最大化を提案した。彼らの論文は、一見単純な疑問、すなわち、この不確実性の表現によれば、事象Eが事象E’よりも起こりやすいとはどういう意味か、という疑問には答えていない。本論文では、不確実性が重み付き確率尺度の集合で表現される場合の比較尤度の概念を定義します。これは、確率（および下方確率）によって定義される順序を自然な方法で一般化します。上方確率の一般化も定義できます。この後悔に基づく尤度の概念の完全な公理的特徴付けが与えられています。

Possible and Necessary Winners of Partial Tournaments

Possible and Necessary Winners of Partial Tournaments / 部分トーナメントの可能な勝者と必要な勝者

We study the problem of computing possible and necessary winners for partially specified weighted and unweighted tournaments. This problem arises naturally in elections with incompletely specified votes, partially completed sports competitions, and more generally in any scenario where the outcome of some pairwise comparisons is not yet fully known. We specifically consider a number of well-known solution concepts—including the uncovered set, Borda, ranked pairs, and maximin—and show that for most of them, possible and necessary winners can be identified in polynomial time. These positive algorithmic results stand in sharp contrast to earlier results concerning possible and necessary winners given partially specified preference profiles.



我々は、部分的に指定された重み付きトーナメントと重みなしトーナメントにおける可能勝者と必要勝者を計算する問題を研究します。この問題は、不完全に指定された投票、部分的に完了したスポーツ競技、そしてより一般的には、いくつかの一対比較の結果がまだ完全には分かっていないあらゆるシナリオにおいて自然に生じる。我々は特に、未被覆集合、ボルダ、順位付けペア、マキシミンなど、いくつかのよく知られた解法概念を検討し、それらのほとんどについて、可能勝者と必要勝者を多項式時間で特定できることを示します。これらの肯定的なアルゴリズム結果は、部分的に指定された選好プロファイルを与えられた場合の可能勝者と必要勝者に関する以前の結果とは著しく対照的です。

Pay-As-You-Go Description Logic Reasoning by Coupling Tableau and Saturation Procedures

Pay-As-You-Go Description Logic Reasoning by Coupling Tableau and Saturation Procedures / タブローと飽和手順を組み合わせた従量課金制記述論理推論

Nowadays, saturation-based reasoners for the OWL EL profile of the Web Ontology Language are able to handle large ontologies such as SNOMED very efficiently. However, it is currently unclear how saturation-based reasoning procedures can be extended to very expressive Description Logics such as SROIQ–the logical underpinning of the current and second iteration of the Web Ontology Language. Tableau-based procedures, on the other hand, are not limited to specific Description Logic languages or OWL profiles, but even highly optimised tableau-based reasoners might not be efficient enough to handle large ontologies such as SNOMED. In this paper, we present an approach for tightly coupling tableau- and saturation-based procedures that we implement in the OWL DL reasoner Konclude. Our detailed evaluation shows that this combination significantly improves the reasoning performance for a wide range of ontologies.



現在、Webオントロジー言語のOWL ELプロファイル用の飽和ベース推論システムは、SNOMEDなどの大規模なオントロジーを非常に効率的に処理できます。しかし、飽和ベース推論手順を、Webオントロジー言語の現在のバージョンおよび第2バージョンの論理的基盤であるSROIQなどの非常に表現力豊かな記述論理にどのように拡張できるかは現在のところ不明です。一方、タブローベースの手順は特定の記述論理言語やOWLプロファイルに限定されませんが、高度に最適化されたタブローベースの推論システムでさえ、SNOMEDなどの大規模なオントロジーを処理するのに十分な効率性がない可能性があります。本稿では、OWL DL推論エンジンKoncludeに実装した、タブローベースと飽和ベースの手続きを緊密に連携させるアプローチを紹介します。詳細な評価により、この組み合わせにより、幅広いオントロジーにおいて推論性能が大幅に向上することが示されました。

Solving #SAT and MAXSAT by Dynamic Programming

Solving #SAT and MAXSAT by Dynamic Programming / 動的計画法による#SATとMAXSATの解法

We look at dynamic programming algorithms for propositional model counting, also called #SAT, and MaxSAT. Tools from graph structure theory, in particular treewidth, have been used to successfully identify tractable cases in many subfields of AI, including SAT, Constraint Satisfaction Problems (CSP), Bayesian reasoning, and planning. In this paper we attack #SAT and MaxSAT using similar, but more modern, graph structure tools. The tractable cases will include formulas whose class of incidence graphs have not only unbounded treewidth but also unbounded clique-width. We show that our algorithms extend all previous results for MaxSAT and #SAT achieved by dynamic programming along structural decompositions of the incidence graph of the input formula. We present some limited experimental results, comparing implementations of our algorithms to state-of-the-art #SAT and MaxSAT solvers, as a proof of concept that warrants further research.



我々は、命題モデルカウント（#SATとも呼ばれる）およびMaxSATのための動的計画法アルゴリズムを考察します。グラフ構造理論、特に木幅のツールは、SAT、制約充足問題(CSP)、ベイズ推論、プランニングなど、AIの多くのサブフィールドで扱いやすいケースを特定するために使用されてきた。本稿では、同様ではあるがより現代的なグラフ構造ツールを使用して#SATとMaxSATを検証します。扱いやすいケースには、接続グラフのクラスが木幅だけでなくクリーク幅も無制限である式が含まれます。我々のアルゴリズムは、入力式の接続グラフの構造分解に沿って動的計画法によって達成されたMaxSATおよび#SATのこれまでの結果をすべて拡張することを示す。我々は、更なる研究を正当化する概念実証として、我々のアルゴリズムの実装を最先端の#SATおよびMaxSATソルバーと比較する限定的な実験結果をいくつか示す。

Compressing Optimal Paths with Run Length Encoding

Compressing Optimal Paths with Run Length Encoding / ランレングス符号化による最適パスの圧縮

We introduce a novel approach to Compressed Path Databases, space efficient oracles used to very quickly identify the first edge on a shortest path. Our algorithm achieves query running times on the 100 nanosecond scale, being significantly faster than state-of-the-art first-move oracles from the literature. Space consumption is competitive, due to a compression approach that rearranges rows and columns in a first-move matrix and then performs run length encoding (RLE) on the contents of the matrix. One variant of our implemented system was, by a convincing margin, the fastest entry in the 2014 Grid-Based Path Planning Competition.We give a first tractability analysis for the compression scheme used by our algorithm. We study the complexity of computing a database of minimum size for general directed and undirected graphs. We find that in both cases the problem is NP-complete. We also show that, for graphs which can be decomposed along articulation points, the problem can be decomposed into independent parts, with a corresponding reduction in its level of difficulty. In particular, this leads to simple and tractable algorithms with linear running time which yield optimal compression results for trees.



圧縮パスデータベース（最短経路の最初の辺を非常に高速に特定するために使用される、空間効率の高いオラクル）への新たなアプローチを紹介します。本アルゴリズムは100ナノ秒単位のクエリ実行時間を実現し、文献で紹介されている最先端のファーストムーブオラクルよりも大幅に高速です。ファーストムーブ行列の行と列を並べ替え、行列の内容に対してランレングス符号化（RLE）を実行する圧縮アプローチにより、空間消費量は競争力があります。実装したシステムの1つのバリエーションは、2014年のグリッドベースパスプランニングコンペティションにおいて、圧倒的な差で最速のエントリーとなりました。本アルゴリズムで用いられる圧縮方式の、初めての計算可能性分析を行います。一般的な有向グラフおよび無向グラフについて、最小サイズのデータ​​ベースを計算する複雑さを検証します。どちらの場合も、問題はNP完全であることがわかりました。また、連結点に沿って分解できるグラフの場合、問題を独立した部分に分解でき、それに応じて難易度が低減することも示します。特に、これは線形実行時間で木構造の最適な圧縮結果をもたらす、単純で扱いやすいアルゴリズムにつながる。

On a Practical, Integer-Linear Programming Model for Delete-Free Tasks and its Use as a Heuristic for Cost-Optimal Planning

On a Practical, Integer-Linear Programming Model for Delete-Free Tasks and its Use as a Heuristic for Cost-Optimal Planning / 削除不要タスクのための実用的な整数線形計画モデルと、コスト最適計画のためのヒューリスティックとしての利用について

We propose a new integer-linear programming model for the delete relaxation in cost-optimal planning. While a straightforward IP for the delete relaxation is impractical, our enhanced model incorporates variable reduction techniques based on landmarks, relevance-based constraints, dominated action elimination, immediate action application, and inverse action constraints, resulting in an IP that can be used to directly solve delete-free planning problems. We show that our IP model is competitive with previous state-of-the-art solvers for delete-free problems. The LP-relaxation of the IP model is often a very good approximation to the IP, providing an approach to approximating the optimal value of the delete-free task that is complementary to the well-known LM-cut heuristic. We also show that constraints that partially consider delete effects can be added to our IP/LP models. We embed the new IP/LP models into a forward-search based planner, and show that the performance of the resulting planner on standard IPC benchmarks is comparable with the state-of-the-art for cost-optimal planning.



コスト最適計画における削除緩和のための新しい整数線形計画モデルを提案します。削除緩和のための単純なIPは実用的ではないが、我々の拡張モデルは、ランドマークに基づく変数削減手法、関連性に基づく制約、支配行動除去、即時行動適用、および逆行動制約を組み込んでおり、削除を必要としない計画問題を直接解くために使用できるIPを実現しています。我々のIPモデルは、削除を必要としない問題に対する従来の最先端のソルバーと競合可能であることを示す。IPモデルのLP緩和は、多くの場合IPの非常に良い近似であり、よく知られているLMカットヒューリスティックを補完する、削除を必要としないタスクの最適値を近似する手法を提供します。また、削除効果を部分的に考慮した制約をIP/LPモデルに追加できることも示す。新しいIP/LPモデルをフォワード検索ベースのプランナーに組み込み、結果として得られるプランナーの標準IPCベンチマークでのパフォーマンスが、コスト最適プランニングの最先端のものと匹敵することを示します。

Word vs. Class-Based Word Sense Disambiguation

Word vs. Class-Based Word Sense Disambiguation / 単語ベースとクラスベースの語義曖昧性解消

As empirically demonstrated by the Word Sense Disambiguation (WSD) tasks of the last SensEval/SemEval exercises, assigning the appropriate meaning to words in context has resisted all attempts to be successfully addressed. Many authors argue that one possible reason could be the use of inappropriate sets of word meanings. In particular, WordNet has been used as a de-facto standard repository of word meanings in most of these tasks. Thus, instead of using the word senses defined in WordNet, some approaches have derived semantic classes representing groups of word senses. However, the meanings represented by WordNet have been only used for WSD at a very fine-grained sense level or at a very coarse-grained semantic class level (also called SuperSenses). We suspect that an appropriate level of abstraction could be on between both levels. The contributions of this paper are manifold. First, we propose a simple method to automatically derive semantic classes at intermediate levels of abstraction covering all nominal and verbal WordNet meanings. Second, we empirically demonstrate that our automatically derived semantic classes outperform classical approaches based on word senses and more coarse-grained sense groupings. Third, we also demonstrate that our supervised WSD system benefits from using these new semantic classes as additional semantic features while reducing the amount of training examples. Finally, we also demonstrate the robustness of our supervised semantic class-based WSD system when tested on out of domain corpus.



前回のSensEval/SemEval演習における語義曖昧性解消（WSD）タスクで実証的に実証されたように、文脈における語義の適切な割り当ては、これまであらゆる試みによって成功裏に解決されてきませんでした。多くの研究者は、その原因の一つとして不適切な語義集合の使用が挙げられると主張しています。特に、WordNetはこれらのタスクのほとんどにおいて、語義の事実上の標準リポジトリとして利用されてきました。そのため、WordNetで定義された語義を使用する代わりに、語義のグループを表す意味クラスを導出するアプローチもいくつかありました。しかし、WordNetによって表現される意味は、WSDにおいて、非常に細分化された語義レベル、または非常に粗粒度の意味クラスレベル（SuperSensesとも呼ばれる）でのみ利用されてきました。適切な抽象化レベルは、両レベルの間にあると考えられます。本論文の貢献は多岐にわたります。まず、WordNetの名詞的および動詞的意味をすべて網羅する、中間的な抽象化レベルで意味クラスを自動的に導出する簡便な手法を提案します。第二に、自動的に導出された意味クラスが、語義やより粗い意味のグループ化に基づく従来のアプローチよりも優れていることを実証的に示します。第三に、教師ありWSDシステムが、これらの新しい意味クラスを追加の意味特徴として使用することで、トレーニング例の量を削減できるという利点も示します。最後に、ドメイン外コーパスでテストした際に、教師あり意味クラスベースのWSDシステムの堅牢性も示します。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 54 (2015)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧