A Constraint Solver for Flexible Protein Model
柔軟なタンパク質モデルのための制約ソルバー
This paper proposes the formalization and implementation of a novel class of constraints aimed at modeling problems related to placement of multi-body systems in the 3-dimensional space. Each multi-body is a system composed of body elements, connected by joint relationships and constrained by geometric properties. The emphasis of this investigation is the use of multi-body systems to model native conformations of protein structures—where each body represents an entity of the protein (e.g., an amino acid, a small peptide) and the geometric constraints are related to the spatial properties of the composing atoms. The paper explores the use of the proposed class of constraints to support a variety of different structural analysis of proteins, such as loop modeling and structure prediction.The declarative nature of a constraint-based encoding provides elaboration tolerance and the ability to make use of any additional knowledge in the analysis studies. The filtering capabilities of the proposed constraints also allow to control the number of representative solutions that are withdrawn from the conformational space of the protein, by means of criteria driven by uniform distribution sampling principles. In this scenario it is possible to select the desired degree of precision and/or number of solutions. The filtering component automatically excludes configurations that violate the spatial and geometric properties of the composing multi-body system. The paper illustrates the implementation of a constraint solver based on the multi-body perspective and its empirical evaluation on protein structure analysis problems.
本論文では、3次元空間における多体系の配置に関する問題をモデリングすることを目的とした、新たな制約クラスの定式化と実装を提案します。各多体系とは、関節関係で接続され、幾何学的特性によって制約される、複数の要素から構成されるシステムです。本研究の重点は、多体系を用いてタンパク質構造のネイティブコンフォメーションをモデル化することにあります。各要素はタンパク質の実体（例えば、アミノ酸、小さなペプチド）を表し、幾何学的制約は構成原子の空間特性と関連しています。本論文では、提案された制約クラスを用いて、ループモデリングや構造予測など、タンパク質の様々な構造解析を支援する方法について検討します。制約ベースのエンコーディングの宣言的な性質は、精緻化に対する許容度と、解析研究においてあらゆる追加知識を活用する能力を提供します。提案された制約のフィルタリング機能により、均一分布サンプリング原理に基づく基準を用いて、タンパク質のコンフォメーション空間から抽出される代表解の数を制御することも可能となります。このシナリオでは、必要な精度や解の数を選択できます。フィルタリングコンポーネントは、構成する多体系の空間的および幾何学的特性に違反する構成を自動的に除外します。本論文では、多体系の観点に基づく制約ソルバーの実装と、タンパク質構造解析問題におけるその実証的評価について説明します。
A Smooth Transition from Powerlessness to Absolute Power
無力から絶対的な力へのスムーズな移行
We study the phase transition of the coalitional manipulation problem for generalized scoring rules. Previously it has been shown that, under some conditions on the distribution of votes, if the number of manipulators is o(sqrt{n}), where n is the number of voters, then the probability that a random profile is manipulable by the coalition goes to zero as the number of voters goes to infinity, whereas if the number of manipulators is omega(sqrt{n}), then the probability that a random profile is manipulable goes to one. Here we consider the critical window, where a coalition has size c*sqrt{n}, and we show that as c goes from zero to infinity, the limiting probability that a random profile is manipulable goes from zero to one in a smooth fashion, i.e., there is a smooth phase transition between the two regimes. This result analytically validates recent empirical results, and suggests that deciding the coalitional manipulation problem may be of limited computational hardness in practice.
一般化スコアリングルールの連合操作問題の相転移を研究します。これまで、投票の分配に関するある条件下では、操作者の数がo(sqrt{n})の場合（nは投票者数）、ランダム プロファイルが連合によって操作可能な確率は投票者数が無限大になるにつれて0に近づくが、操作者の数がomega(sqrt{n})の場合はランダム プロファイルが操作可能な確率は1に近づくことが示されていました。ここでは、連合のサイズがc*sqrt{n}である臨界ウィンドウを考慮し、cが0から無限大になるにつれて、ランダム プロファイルが操作可能である極限確率が0から1に滑らかに近づく、つまり2つの状態の間に滑らかな相転移があることを示します。この結果は最近の経験的結果を解析的に検証し、連合操作問題を決定することは実際には計算上の困難性が限られている可能性があることを示唆しています。
Exact Query Reformulation over Databases with First-order and Description Logics Ontologies
一階述語論理オントロジーと記述論理オントロジーを持つデータベースにおける正確なクエリ再定式化
We study a general framework for query rewriting in the presence of an arbitrary first-order logic ontology over a database signature. The framework supports deciding the existence of a safe-range first-order equivalent reformulation of a query in terms of the database signature, and if so, it provides an effective approach to construct the reformulation based on interpolation using standard theorem proving techniques (e.g., tableau). Since the reformulation is a safe-range formula, it is effectively executable as an SQL query. At the end, we present a non-trivial application of the framework with ontologies in the very expressive ALCHOIQ description logic, by providing effective means to compute safe-range first-order exact reformulations of queries.
データベースシグネチャ上の任意の一階述語論理オントロジーが存在する場合の、クエリ書き換えのための一般的なフレームワークを検討します。このフレームワークは、データベースシグネチャを用いてクエリの安全範囲一次等価再定式化の存在を判定する機能をサポートし、存在する場合、標準的な定理証明技術（例えば、Tableau）を用いた補間に基づいて再定式化を構築する効果的なアプローチを提供します。再定式化は安全範囲式であるため、SQLクエリとして効果的に実行可能です。最後に、非常に表現力豊かなALCHOIQ記述論理におけるオントロジーを用いたフレームワークの非自明な応用例を示し、クエリの安全範囲一次厳密再定式化を計算するための効果的な手段を提供します。
Scalable and Efficient Bayes-Adaptive Reinforcement Learning Based on Monte-Carlo Tree Search
モンテカルロ木探索に基づくスケーラブルで効率的なベイズ適応型強化学習
Bayesian planning is a formally elegant approach to learning optimal behaviour under model uncertainty, trading off exploration and exploitation in an ideal way. Unfortunately, planning optimally in the face of uncertainty is notoriously taxing, since the search space is enormous. In this paper we introduce a tractable, sample-based method for approximate Bayes-optimal planning which exploits Monte-Carlo tree search. Our approach avoids expensive applications of Bayes rule within the search tree by sampling models from current beliefs, and furthermore performs this sampling in a lazy manner. This enables it to outperform previous Bayesian model-based reinforcement learning algorithms by a significant margin on several well-known benchmark problems. As we show, our approach can even work in problems with an infinite state space that lie qualitatively out of reach of almost all previous work in Bayesian exploration.
ベイズ計画は、モデルの不確実性の下で最適な行動を学習するための、形式的にエレガントなアプローチであり、探索と活用を理想的な方法でトレードオフします。しかしながら、不確実性に直面した状況で最適な計画を立てることは、探索空間が膨大であるため、非常に負担が大きいことで知られています。本稿では、モンテカルロ木探索を活用する、扱いやすいサンプルベースの近似ベイズ最適計画法を紹介します。本手法は、現在の信念からモデルをサンプリングすることで、探索木内でのベイズ則のコストの高い適用を回避し、さらにこのサンプリングを遅延実行します。これにより、いくつかのよく知られたベンチマーク問題において、従来のベイズモデルベースの強化学習アルゴリズムを大幅に上回る性能を実現します。本稿で示すように、本手法は、ベイズ探索におけるこれまでのほぼすべての研究が定性的に及ばない、無限状態空間を持つ問題でも機能します。
Single Network Relational Transductive Learning
単一ネットワーク関係トランスダクティブ学習
Relational classification on a single connected network has been of particular interest in the machine learning and data mining communities in the last decade or so. This is mainly due to the explosion in popularity of social networking sites such as Facebook, LinkedIn and Google+ amongst others. In statistical relational learning, many techniques have been developed to address this problem, where we have a connected unweighted homogeneous/heterogeneous graph that is partially labeled and the goal is to propagate the labels to the unlabeled nodes. In this paper, we provide a different perspective by enabling the effective use of graph transduction techniques for this problem. We thus exploit the strengths of this class of methods for relational learning problems. We accomplish this by providing a simple procedure for constructing a weight matrix that serves as input to a rich class of graph transduction techniques. Our procedure has multiple desirable properties. For example, the weights it assigns to edges between unlabeled nodes naturally relate to a measure of association commonly used in statistics, namely the Gamma test statistic. We further portray the efficacy of our approach on synthetic as well as real data, by comparing it with state-of-the-art relational learning algorithms, and graph transduction techniques with an adjacency matrix or a real valued weight matrix computed using available attributes as input. In these experiments we see that our approach consistently outperforms other approaches when the graph is sparsely labeled, and remains competitive with the best when the proportion of known labels increases.
単一の連結ネットワーク上の関係分類は、過去10年ほど、機械学習とデータマイニングのコミュニティで特に関心を集めてきました。これは主に、Facebook、LinkedIn、Google+などのソーシャル ネットワーキング サイトの人気の爆発的な増加によるものです。統計的関係学習では、この問題に対処するために多くの手法が開発されてきました。この問題では、部分的にラベル付けされた、接続された重み付けされていない同質/異質グラフがあり、ラベルをラベルなしノードに伝搬することが目標です。本稿では、この問題にグラフ トランスダクション手法を効果的に使用できるようにすることで、異なる視点を提供します。したがって、関係学習の問題に対するこのクラスの手法の長所を活用します。これは、豊富なグラフ トランスダクション手法への入力として機能する重みマトリックスを作成するための簡単な手順を提供することで実現します。この手順には、複数の望ましい特性があります。たとえば、ラベルなしノード間のエッジに割り当てる重みは、統計で一般的に使用される関連の尺度、つまりガンマ テスト統計量に自然に関連します。さらに、最先端の関係学習アルゴリズム、および隣接行列または利用可能な属性を入力として計算した実数値の重み行列を用いたグラフ変換技術と比較することで、合成データと実データの両方における本手法の有効性を明らかにします。これらの実験では、グラフにラベルがまばらに付与されている場合、本手法は一貫して他の手法よりも優れており、既知のラベルの割合が増加しても最良の手法と遜色ない性能を維持することが確認されました。
The Complexity of Optimal Monotonic Planning: The Bad, The Good, and The Causal Graph
最適単調計画の複雑性：悪いもの、良いもの、そして因果グラフ
For almost two decades, monotonic, or “delete free,” relaxation has been one of the key auxiliary tools in the practice of domain-independent deterministic planning. In the particular contexts of both satisficing and optimal planning, it underlies most state-of-the-art heuristic functions. While satisficing planning for monotonic tasks is polynomial-time, optimal planning for monotonic tasks is NP-equivalent. Here we establish both negative and positive results on the complexity of some wide fragments of optimal monotonic planning, with the fragments being defined around the causal graph topology. Our results shed some light on the link between the complexity of general optimal planning and the complexity of optimal planning for the respective monotonic relaxations.
ほぼ20年間にわたり、単調緩和、すなわち「削除フリー」緩和は、ドメイン非依存の決定論的計画の実践における重要な補助ツールの一つでした。満足度化と最適計画の両方の特定の文脈において、これは最先端のヒューリスティック関数のほとんどの基礎となっています。単調タスクの満足度化計画は多項式時間ですが、単調タスクの最適計画はNP時間です。本稿では、因果グラフトポロジーを中心に定義された、最適な単調計画のいくつかの広範な断片の複雑性について、否定的な結果と肯定的な結果の両方を確立します。私たちの結果は、一般的な最適計画の複雑性と、それぞれの単調緩和に対する最適計画の複雑性との間の関連性に光を当てます。
Unsupervised Sub-tree Alignment for Tree-to-Tree Translation
木から木への翻訳のための教師なしサブツリーアライメント
This article presents a probabilistic sub-tree alignment model and its application to tree-to-tree machine translation. Unlike previous work, we do not resort to surface heuristics or expensive annotated data, but instead derive an unsupervised model to infer the syntactic correspondence between two languages. More importantly, the developed model is syntactically-motivated and does not rely on word alignments. As a by-product, our model outputs a sub-tree alignment matrix encoding a large number of diverse alignments between syntactic structures, from which machine translation systems can efficiently extract translation rules that are often filtered out due to the errors in 1-best alignment. Experimental results show that the proposed approach outperforms three state-of-the-art baseline approaches in both alignment accuracy and grammar quality. When applied to machine translation, our approach yields a +1.0 BLEU improvement and a -0.9 TER reduction on the NIST machine translation evaluation corpora. With tree binarization and fuzzy decoding, it even outperforms a state-of-the-art hierarchical phrase-based system.
本稿では、確率的サブツリーアライメントモデルと、そのツリー対ツリー機械翻訳への応用について述べる。先行研究とは異なり、表面ヒューリスティックスや高価な注釈付きデータに頼らず、2つの言語間の統語的対応を推測するための教師なしモデルを導出します。さらに重要なのは、開発されたモデルが統語論に基づいており、単語のアライメントに依存しないことです。副産物として、我々のモデルは統語構造間の多様なアライメントを多数エンコードしたサブツリーアライメント行列を出力し、機械翻訳システムはこの行列から、1-ベストアライメントのエラーによって除外されがちな翻訳規則を効率的に抽出することができます。実験結果では、提案手法が、アライメント精度と文法品質の両方において、3つの最先端のベースライン手法よりも優れていることが示されました。機械翻訳に適用した場合、我々の手法はNIST機械翻訳評価コーパスにおいて、BLEUが+1.0向上し、TERが-0.9低下した。ツリー二値化とファジーデコードを組み合わせることで、最先端の階層的フレーズベースシステムよりも優れた性能を発揮します。
A Case of Pathology in Multiobjective Heuristic Search
多目的ヒューリスティック探索における病理の事例
This article considers the performance of the MOA* multiobjective search algorithm with heuristic information. It is shown that in certain cases blind search can be more efficient than perfectly informed search, in terms of both node and label expansions.A class of simple graph search problems is defined for which the number of nodes grows linearly with problem size and the number of nondominated labels grows quadratically. It is proved that for these problems the number of node expansions performed by blind MOA* grows linearly with problem size, while the number of such expansions performed with a perfectly informed heuristic grows quadratically. It is also proved that the number of label expansions grows quadratically in the blind case and cubically in the informed case.
本稿では、ヒューリスティック情報を用いたMOA*多目的探索アルゴリズムの性能について考察します。特定のケースでは、ノード拡張とラベル拡張の両方において、ブラインド探索が完全情報探索よりも効率的であることを示す。ノード数が問題サイズに比例して線形に増加し、非劣ラベル数が2乗に比例して増加する単純なグラフ探索問題のクラスを定義します。これらの問題において、ブラインドMOA*によるノード拡張の回数は問題サイズに比例して線形に増加するのに対し、完全情報ヒューリスティックによるノード拡張の回数は2乗に比例することが証明されています。また、ラベル拡張の回数は、ブラインド探索の場合は2乗に比例し、情報探索の場合は3乗に比例することが証明されています。
Generating Natural Language Descriptions from OWL Ontologies: the NaturalOWL System
OWLオントロジーからの自然言語記述の生成：NaturalOWLシステム
We present NaturalOWL, a natural language generation system that produces texts describing individuals or classes of OWL ontologies. Unlike simpler OWL verbalizers, which typically express a single axiom at a time in controlled, often not entirely fluent natural language primarily for the benefit of domain experts, we aim to generate fluent and coherent multi-sentence texts for end-users. With a system like NaturalOWL, one can publish information in OWL on the Web, along with automatically produced corresponding texts in multiple languages, making the information accessible not only to computer programs and domain experts, but also end-users. We discuss the processing stages of NaturalOWL, the optional domain-dependent linguistic resources that the system can use at each stage, and why they are useful. We also present trials showing that when the domain-dependent llinguistic resources are available, NaturalOWL produces significantly better texts compared to a simpler verbalizer, and that the resources can be created with relatively light effort.
本稿では、OWLオントロジーの個体またはクラスを記述するテキストを生成する自然言語生成システムであるNaturalOWLを紹介します。より単純なOWL言語化システムは、通常、ドメイン専門家向けに、制御された、しばしば完全に流暢ではない自然言語で一度に1つの公理を表現します。これとは異なり、本稿では、エンドユーザー向けに流暢で一貫性のある複数文のテキストを生成することを目指す。NaturalOWLのようなシステムを用いれば、OWLで記述された情報を、複数の言語で自動生成された対応するテキストとともにWeb上に公開することができます。これにより、コンピュータプログラムやドメイン専門家だけでなく、エンドユーザーも情報にアクセスできるようになります。本稿では、NaturalOWLの処理段階、各段階でシステムが使用できるオプションのドメイン依存言語リソース、そしてそれらが有用である理由について議論します。また、ドメイン依存言語リソースが利用可能な場合、NaturalOWLはより単純な言語化システムと比較して大幅に優れたテキストを生成し、比較的少ない労力でリソースを作成できることを示す実験結果も示す。
A Survey of Multi-Objective Sequential Decision-Making
多目的逐次意思決定の概観
Sequential decision-making problems with multiple objectives arise naturally in practice and pose unique challenges for research in decision-theoretic planning and learning, which has largely focused on single-objective settings. This article surveys algorithms designed for sequential decision-making problems with multiple objectives. Though there is a growing body of literature on this subject, little of it makes explicit under what circumstances special methods are needed to solve multi-objective problems. Therefore, we identify three distinct scenarios in which converting such a problem to a single-objective one is impossible, infeasible, or undesirable. Furthermore, we propose a taxonomy that classifies multi-objective methods according to the applicable scenario, the nature of the scalarization function (which projects multi-objective values to scalar ones), and the type of policies considered. We show how these factors determine the nature of an optimal solution, which can be a single policy, a convex hull, or a Pareto front. Using this taxonomy, we survey the literature on multi-objective methods for planning and learning. Finally, we discuss key applications of such methods and outline opportunities for future work.
多目的逐次意思決定問題は、実践において自然に発生し、これまで主に単目的設定に焦点を当ててきた意思決定理論的計画・学習研究にとって、特有の課題を提起します。本稿では、多目的逐次意思決定問題向けに設計されたアルゴリズムを概説します。このテーマに関する文献は増加しているものの、多目的問題を解決するために特別な手法が必要となる状況を明確に示すものはほとんどない。そこで、本稿では、このような問題を単目的問題に変換することが不可能、実行不可能、または望ましくない3つの異なるシナリオを特定します。さらに、適用可能なシナリオ、スカラー化関数（多目的値をスカラー値に投影する関数）、および考慮される方策の種類に基づいて、多目的手法を分類する分類法を提案します。これらの要因が、単一方策、凸包、またはパレート解といった最適解の性質をどのように決定するかを示す。この分類法を用いて、計画・学習における多目的手法に関する文献を概説します。最後に、これらの手法の主要な応用例を議論し、今後の研究の可能性を概説します。
Reasoning about Explanations for Negative Query Answers in DL-Lite
DL-Liteにおける否定的なクエリ回答の説明に関する推論
In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for Description Logics, where research has focused on the explanation of both TBox reasoning and, more recently, query answering. Besides explaining the presence of a tuple in a query answer, it is important to explain also why a given tuple is missing. We address the latter problem for instance and conjunctive query answering over DL-Lite ontologies by adopting abductive reasoning; that is, we look for additions to the ABox that force a given tuple to be in the result. As reasoning tasks we consider existence and recognition of an explanation, and relevance and necessity of a given assertion for an explanation. We characterize the computational complexity of these problems for arbitrary, subset minimal, and cardinality minimalexplanations.
ユーザビリティ要件を満たすために、ほとんどのロジックベースのアプリケーションは推論サービスに説明機能を提供しています。これは記述論理にも当てはまり、研究はTBox推論と、より最近ではクエリ回答の両方の説明に焦点を合わせています。クエリ回答にタプルが存在することを説明するだけでなく、特定のタプルが欠落している理由も説明することが重要です。DL-Liteオントロジーにおけるインスタンスおよび連言クエリ応答における後者の問題に対し、我々はアブダクション推論を採用することで対処します。すなわち、与えられたタプルが結果に含まれるようにABoxへの追加を探す。推論タスクとして、説明の存在と認識、そして与えられたアサーションの説明に対する関連性と必要性を考慮します。これらの問題の計算複雑性を、任意の説明、部分集合最小の説明、そしてカーディナリティ最小の説明について特徴付ける。
Protecting Moving Targets with Multiple Mobile Resources
複数のモバイルリソースによる移動ターゲットの保護
In recent years, Stackelberg Security Games have been successfully applied to solve resource allocation and scheduling problems in several security domains. However, previous work has mostly assumed that the targets are stationary relative to the defender and the attacker, leading to discrete game models with finite numbers of pure strategies. This paper in contrast focuses on protecting mobile targets that leads to a continuous set of strategies for the players. The problem is motivated by several real-world domains including protecting ferries with escort boats and protecting refugee supply lines. Our contributions include: (i) A new game model for multiple mobile defender resources and moving targets with a discretized strategy space for the defender and a continuous strategy space for the attacker. (ii) An efficient linear-programming-based solution that uses a compact representation for the defender’s mixed strategy, while accurately modeling the attacker’s continuous strategy using a novel sub-interval analysis method. (iii) Discussion and analysis of multiple heuristic methods for equilibrium refinement to improve robustness of defender’s mixed strategy. (iv) Discussion of approaches to sample actual defender schedules from the defender’s mixed strategy. (iv) Detailed experimental analysis of our algorithms in the ferry protection domain.
近年、スタックベルク・セキュリティ・ゲームは、様々なセキュリティ分野における資源配分およびスケジューリング問題の解決に効果的に適用されてきました。しかし、これまでの研究では、標的が防御側と攻撃側に対して静止していると仮定することがほとんどであり、純粋戦略の数が有限である離散的なゲームモデルにつながっていました。本稿ではこれに対し、プレイヤーに連続的な戦略をもたらす移動標的の保護に焦点を当てています。この問題は、護衛船によるフェリーの保護や難民補給路の保護など、いくつかの現実世界の分野をモチーフとしています。我々の貢献は以下の通りです。(i)複数の移動防御側リソースと移動標的のための、防御側に離散化戦略空間、攻撃側に連続戦略空間を持つ新しいゲームモデル。(ii)防御側の混合戦略をコンパクトに表現し、攻撃側の連続戦略を新しい部分区間解析法を用いて正確にモデル化する、効率的な線形計画法に基づくソリューション。(iii)防御側の混合戦略の堅牢性を向上させるための均衡改良のための複数のヒューリスティック手法の議論と分析。(iv)防御側の混合戦略から実際の防御側のスケジュールをサンプリングするアプローチの議論。(iv)フェリー保護ドメインにおける我々のアルゴリズムの詳細な実験分析。
AI Methods in Algorithmic Composition: A Comprehensive Survey
アルゴリズム合成におけるAI手法：包括的なサーベイ
Algorithmic composition is the partial or total automation of the process of music composition by using computers. Since the 1950s, different computational techniques related to Artificial Intelligence have been used for algorithmic composition, including grammatical representations, probabilistic methods, neural networks, symbolic rule-based systems, constraint programming and evolutionary algorithms. This survey aims to be a comprehensive account of research on algorithmic composition, presenting a thorough view of the field for researchers in Artificial Intelligence.
アルゴリズム作曲とは、コンピュータを用いて音楽作曲のプロセスを部分的または完全に自動化することです。1950年代以降、文法的表現、確率的手法、ニューラルネットワーク、記号ルールベースシステム、制約プログラミング、進化アルゴリズムなど、人工知能に関連する様々な計算手法がアルゴリズム作曲に利用されてきました。本稿は、アルゴリズム作曲に関する研究を包括的に解説し、人工知能研究者にこの分野の全体像を示すことを目的としています。
Horn Clause Contraction Functions
ホーン節縮約関数
In classical, AGM-style belief change, it is assumed that the underlying logic contains classical propositional logic. This is clearly a limiting assumption, particularly in Artificial Intelligence. Consequently there has been recent interest in studying belief change in approaches where the full expressivity of classical propositional logic is not obtained. In this paper we investigate belief contraction in Horn knowledge bases. We point out that the obvious extension to the Horn case, involving Horn remainder sets as a starting point, is problematic. Not only do Horn remainder sets have undesirable properties, but also some desirable Horn contraction functions are not captured by this approach. For Horn belief set contraction, we develop an account in terms of a model-theoretic characterisation involving weak remainder sets. Maxichoice and partial meet Horn contraction is specified, and we show that the problems arising with earlier work are resolved by these approaches. As well, constructions of the specific operators and sets of postulates are provided, and representation results are obtained. We also examine Horn package contraction, or contraction by a set of formulas. Again, we give a construction and postulate set, linking them via a representation result. Last, we investigate the closely-related notion of forgetting in Horn clauses. This work is arguably interesting since Horn clauses have found widespread use in AI; as well, the results given here may potentially be extended to other areas which make use of Horn-like reasoning, such as logic programming, rule-based systems, and description logics. Finally, since Horn reasoning is weaker than classical reasoning, this work sheds light on the foundations of belief change
古典的なAGMスタイルの信念変化では、基礎となる論理に古典的な命題論理が含まれていると仮定されます。これは明らかに制限的な仮定であり、特に人工知能においては顕著です。そのため、最近では、古典的な命題論理の表現力を十分に発揮できないアプローチにおける信念変化の研究に関心が集まっています。本稿では、ホーン知識ベースにおける信念縮約について検討します。ホーン剰余集合を出発点とするホーンケースへの明らかな拡張には問題があることを指摘します。ホーン剰余集合には望ましくない特性があるだけでなく、このアプローチでは望ましいホーン縮約関数のいくつかが捉えられない。ホーン信念集合縮約については、弱剰余集合を含むモデル理論的特徴付けの観点から説明を展開します。マキシチョイスおよび部分的ホーン縮約を規定し、以前の研究で発生した問題がこれらのアプローチによって解決されることを示す。さらに、特定の演算子および公理集合の構成が提供され、表現結果が得られます。また、ホーンパッケージ縮約、つまり一連の式による縮約についても検討します。ここでも、構成と公理集合を示し、それらを表現結果で結び付ける。最後に、ホーン節における忘却という密接に関連する概念を検討します。ホーン節はAIで広く使用されているため、この研究はおそらく興味深いものです。また、ここで示された結果は、論理プログラミング、ルールベースシステム、記述論理など、ホーン型推論を利用する他の分野にも拡張できる可能性があります。最後に、ホーン型推論は古典的推論よりも弱いため、本研究は信念変化の基礎に光を当てています。
Defeasible Inheritance-Based Description Logics
破棄可能な継承に基づく記述論理
Defeasible inheritance networks are a non-monotonic framework that deals with hierarchical knowledge. On the other hand, rational closure is acknowledged as a landmark of the preferential approach to non-monotonic reasoning. We will combine these two approaches and define a new non-monotonic closure operation for propositional knowledge bases that combines the advantages of both. Then we redefine such a procedure for Description Logics (DLs), a family of logics well-suited to model structured information. In both cases we will provide a simple reasoning method that is built on top of the classical entailment relation and, thus, is amenable of an implementation based on existing reasoners. Eventually, we evaluate our approach on well-known landmark test examples.
破棄可能継承ネットワークは、階層的知識を扱う非単調な枠組みです。一方、合理的閉包は、非単調推論への優先的アプローチのランドマークとして認識されています。本稿では、これら2つのアプローチを組み合わせ、両者の利点を兼ね備えた命題知識ベースのための新しい非単調閉包操作を定義します。次に、構造化情報をモデル化するのに適した論理群である記述論理（DL）向けに、そのような手順を再定義します。どちらの場合も、古典的な含意関係を基盤として構築され、既存の推論システムに基づく実装に適したシンプルな推論手法を提供します。最終的には、よく知られているランドマークテスト例を用いて本手法を評価します。
Beth Definability in Expressive Description Logics
表現的記述論理におけるベス定義可能性
The Beth definability property, a well-known property from classical logic, is investigated in the context of description logics: if a general L-TBox implicitly defines an L-concept in terms of a given signature, where L is a description logic, then does there always exist over this signature an explicit definition in L for the concept? This property has been studied before and used to optimize reasoning in description logics. In this paper a complete classification of Beth definability is provided for extensions of the basic description logic ALC with transitive roles, inverse roles, role hierarchies, and/or functionality restrictions, both on arbitrary and on finite structures. Moreover, we present a tableau-based algorithm which computes explicit definitions of at most double exponential size. This algorithm is optimal because it is also shown that the smallest explicit definition of an implicitly defined concept may be double exponentially long in the size of the input TBox. Finally, if explicit definitions are allowed to be expressed in first-order logic, then we show how to compute them in single exponential time.
古典論理におけるよく知られた性質であるベス定義可能性を記述論理の文脈で考察します。すなわち、一般のL-TBoxが、与えられたシグネチャ（Lは記述論理）を用いてL概念を暗黙的に定義する場合、このシグネチャ上には必ずその概念のLにおける明示的定義が存在するか？この性質は以前にも研究されており、記述論理における推論の最適化に用いられてきた。本稿では、基本記述論理ALCの拡張に対し、任意の構造と有限構造の両方において、推移的役割、逆役割、役割階層、および／または機能制約を持つ拡張に対して、ベス定義可能性の完全な分類を提供します。さらに、最大で二倍指数的サイズの明示的定義を計算するテーブルベースのアルゴリズムを提示します。このアルゴリズムが最適である理由は、暗黙的に定義された概念の最小の明示的定義が、入力TBoxのサイズに対して二倍指数的になる可能性があることも示されているためです。最後に、明示的定義を一階述語論理で表現できる場合、それを一指数時間で計算する方法を示す。
A Global Model for Concept-to-Text Generation
概念からテキストへの生成のためのグローバルモデル
Concept-to-text generation refers to the task of automatically producing textual output from non-linguistic input. We present a joint model that captures content selection (“what to say”) and surface realization (“how to say”) in an unsupervised domain-independent fashion. Rather than breaking up the generation process into a sequence of local decisions, we define a probabilistic context-free grammar that globally describes the inherent structure of the input (a corpus of database records and text describing some of them). We recast generation as the task of finding the best derivation tree for a set of database records and describe an algorithm for decoding in this framework that allows to intersect the grammar with additional information capturing fluency and syntactic well-formedness constraints. Experimental evaluation on several domains achieves results competitive with state-of-the-art systems that use domain specific constraints, explicit feature engineering or labeled data.
概念テキスト生成とは、非言語入力からテキスト出力を自動的に生成するタスクを指します。本稿では、コンテンツ選択（「何を言うか」）と表層実現（「どのように言うか」）を、教師なしドメイン非依存の方法で捉える統合モデルを提示します。生成プロセスを局所的な決定のシーケンスに分割するのではなく、入力（データベースレコードのコーパスとそれらの一部を記述するテキスト）の固有の構造をグローバルに記述する確率文脈自由文法を定義します。生成を、データベースレコードの集合に対する最適な導出木を見つけるタスクとして再構成し、この枠組みにおいて、流暢性と構文整形式性制約を捕捉する追加情報と文法を交差させるデコードアルゴリズムを説明します。複数のドメインにおける実験的評価により、ドメイン固有の制約、明示的な素性エンジニアリング、またはラベル付きデータを使用する最先端のシステムと競合できる結果が得られました。
Optimizing SPARQL Query Answering over OWL Ontologies
OWLオントロジーに基づくSPARQLクエリ応答の最適化
The SPARQL query language is currently being extended by the World Wide Web Consortium (W3C) with so-called entailment regimes. An entailment regime defines how queries are evaluated under more expressive semantics than SPARQL’s standard simple entailment, which is based on subgraph matching. The queries are very expressive since variables can occur within complex concepts and can also bind to concept or role names.In this paper, we describe a sound and complete algorithm for the OWL Direct Semantics entailment regime. We further propose several novel optimizations such as strategies for determining a good query execution order, query rewriting techniques, and show how specialized OWL reasoning tasks and the concept and role hierarchy can be used to reduce the query execution time. For determining a good execution order, we propose a cost-based model, where the costs are based on information about the instances of concepts and roles that are extracted from a model abstraction built by an OWL reasoner. We present two ordering strategies: a static and a dynamic one. For the dynamic case, we improve the performance by exploiting an individual clustering approach that allows for computing the cost functions based on one individual sample from a cluster.We provide a prototypical implementation and evaluate the efficiency of the proposed optimizations. Our experimental study shows that the static ordering usually outperforms the dynamic one when accurate statistics are available. This changes, however, when the statistics are less accurate, e.g., due to nondeterministic reasoning decisions. For queries that go beyond conjunctive instance queries we observe an improvement of up to three orders of magnitude due to the proposed optimizations.
SPARQLクエリ言語は現在、World Wide Web Consortium (W3C)によって、いわゆる含意レジームを用いて拡張されています。含意レジームは、サブグラフマッチングに基づくSPARQLの標準的な単純含意よりも表現力豊かなセマンティクスに基づいてクエリを評価する方法を定義します。変数は複雑な概念内に出現し、概念名や役割名にバインドできるため、クエリは非常に表現力豊かです。本稿では、OWLダイレクトセマンティクス含意レジームのための健全かつ完全なアルゴリズムについて説明します。さらに、適切なクエリ実行順序を決定するための戦略、クエリ書き換え技術など、いくつかの新しい最適化手法を提案し、特殊なOWL推論タスクと概念および役割階層を用いてクエリ実行時間を短縮する方法を示します。適切な実行順序を決定するために、コストベースモデルを提案します。このモデルでは、OWL推論エンジンによって構築されたモデル抽象化から抽出された概念および役割のインスタンスに関する情報に基づいてコストが算出されます。静的と動的の2つの順序付け戦略を提示します。動的の場合、クラスタから1つの個別サンプルに基づいてコスト関数を計算できる個別クラスタリング手法を活用することで、パフォーマンスを向上させます。プロトタイプ実装を提供し、提案された最適化の効率を評価します。実験的研究の結果、正確な統計情報が利用可能な場合、静的順序付けは通常、動的順序付けよりも優れたパフォーマンスを示すことが示されました。しかし、統計情報の精度が低い場合（例えば、非決定論的な推論判断など）は、この傾向が変わります。結合インスタンスクエリを超えるクエリでは、提案された最適化により、最大3桁の改善が見られました。
Optimal Implementation of Watched Literals and More General Techniques
監視対象リテラルの最適実装とより一般的な手法
I prove that an implementation technique for scanning lists in backtracking search algorithms is optimal. The result applies to a simple general framework, which I present: applications include watched literal unit propagation in SAT and a number of examples in constraint satisfaction. Techniques like watched literals are known to be highly space efficient and effective in practice. When implemented in the `circular’ approach described here, these techniques also have optimal run time per branch in big-O terms when amortized across a search tree. This also applies when multiple list elements must be found. The constant factor overhead of the worst case is only 2. Replacing the existing non-optimal implementation of unit propagation in MiniSat speeds up propagation by 29%, though this is not enough to improve overall run time significantly.
バックトラッキング探索アルゴリズムにおけるリストの走査実装手法が最適であることを証明します。この結果は、私が提示する単純な一般フレームワークに適用できます。その応用例としては、SATにおける監視リテラルのユニット伝播や、制約充足におけるいくつかの例が挙げられます。監視リテラルのような手法は、実際に非常に空間効率が高く効果的であることが知られています。ここで説明する「循環」アプローチで実装すると、これらの手法は、探索木全体で償却した場合、ビッグOの観点から分岐あたりの実行時間も最適になります。これは、複数のリスト要素を見つけなければならない場合にも当てはまります。最悪のケースの定数倍オーバーヘッドはわずか2です。MiniSatにおけるユニット伝播の既存の非最適な実装を置き換えると、伝播速度が29%向上しますが、全体の実行時間を大幅に改善するには不十分です。
Learning Optimal Bayesian Networks: A Shortest Path Perspective
最適学習ベイジアンネットワーク：最短経路の観点
In this paper, learning a Bayesian network structure that optimizes a scoring function for a given dataset is viewed as a shortest path problem in an implicit state-space search graph. This perspective highlights the importance of two research issues: the development of search strategies for solving the shortest path problem, and the design of heuristic functions for guiding the search. This paper introduces several techniques for addressing the issues. One is an A* search algorithm that learns an optimal Bayesian network structure by only searching the most promising part of the solution space. The others are mainly two heuristic functions. The first heuristic function represents a simple relaxation of the acyclicity constraint of a Bayesian network. Although admissible and consistent, the heuristic may introduce too much relaxation and result in a loose bound. The second heuristic function reduces the amount of relaxation by avoiding directed cycles within some groups of variables. Empirical results show that these methods constitute a promising approach to learning optimal Bayesian network structures.
本稿では、与えられたデータセットに対するスコアリング関数を最適化するベイジアンネットワーク構造の学習を、暗黙的な状態空間探索グラフにおける最短経路問題として捉える。この観点から、最短経路問題を解決するための探索戦略の開発と、探索を導くヒューリスティック関数の設計という2つの研究課題の重要性が浮き彫りになります。本稿では、これらの問題に対処するためのいくつかの手法を紹介します。1つは、解空間の最も有望な部分のみを探索することで最適なベイジアンネットワーク構造を学習するA*探索アルゴリズムです。他の2つは、主に2つのヒューリスティック関数です。最初のヒューリスティック関数は、ベイジアンネットワークの非巡回制約の単純な緩和を表す。このヒューリスティックは許容可能かつ一貫性があるものの、過剰な緩和を導入し、結果として境界が緩くなる可能性があります。2つ目のヒューリスティック関数は、一部の変数グループ内の有向循環を回避することで、緩和の量を減らします。実験結果は、これらの手法が最適なベイジアンネットワーク構造を学習するための有望なアプローチであることを示しています。
An Online Mechanism for Multi-Unit Demand and its Application to Plug-in Hybrid Electric Vehicle Charging
複数ユニット需要のためのオンラインメカニズムとプラグインハイブリッド電気自動車の充電への応用
We develop an online mechanism for the allocation of an expiring resource to a dynamic agent population. Each agent has a non-increasing marginal valuation function for the resource, and an upper limit on the number of units that can be allocated in any period. We propose two versions on a truthful allocation mechanism. Each modifies the decisions of a greedy online assignment algorithm by sometimes cancelling an allocation of resources. One version makes this modification immediately upon an allocation decision while a second waits until the point at which an agent departs the market. Adopting a prior-free framework, we show that the second approach has better worst-case allocative efficiency and is more scalable. On the other hand, the first approach (with immediate cancellation) may be easier in practice because it does not need to reclaim units previously allocated. We consider an application to recharging plug-in hybrid electric vehicles (PHEVs). Using data from a real-world trial of PHEVs in the UK, we demonstrate higher system performance than a fixed price system, performance comparable with a standard, but non-truthful scheduling heuristic, and the ability to support 50% more vehicles at the same fuel cost than a simple randomized policy.
期限切れとなる資源を動的エージェント集団に割り当てるオンラインメカニズムを開発します。各エージェントは、資源に対する非増加の限界評価関数と、任意の期間に割り当て可能なユニット数の上限を持つ。我々は、真実の割り当てメカニズムの2つのバージョンを提案します。各バージョンは、資源の割り当てをキャンセルすることで、貪欲なオンライン割り当てアルゴリズムの決定を修正します。1つのバージョンは、割り当て決定後直ちにこの変更を行うが、もう1つのバージョンは、エージェントが市場から撤退するまで待機します。事前制約のないフレームワークを採用することで、2番目のアプローチは最悪ケースにおける割り当て効率が向上し、よりスケーラブルであることを示す。一方、最初のアプローチ（即時キャンセル）は、以前に割り当てられたユニットを回収する必要がないため、実際にはより容易である可能性があります。プラグインハイブリッド電気自動車（PHEV）の充電への応用について考察します。英国におけるPHEVの実世界試験データを用いて、固定価格システムよりも高いシステム性能、標準的だが真実ではないスケジューリングヒューリスティックと同等の性能、そして単純なランダム化ポリシーよりも同じ燃料コストで50%多くの車両をサポートできる能力を示す。
Taming the Infinite Chase: Query Answering under Expressive Relational Constraints
無限の追跡を制する：表現力豊かな関係制約下でのクエリ応答
The chase algorithm is a fundamental tool for query evaluation and for testing query containment under tuple-generating dependencies (TGDs) and equality-generating dependencies (EGDs). So far, most of the research on this topic has focused on cases where the chase procedure terminates. This paper introduces expressive classes of TGDs defined via syntactic restrictions: guarded TGDs (GTGDs) and weakly guarded sets of TGDs (WGTGDs). For these classes, the chase procedure is not guaranteed to terminate and thus may have an infinite outcome. Nevertheless, we prove that the problems of conjunctive-query answering and query containment under such TGDs are decidable. We provide decision procedures and tight complexity bounds for these problems. Then we show how EGDs can be incorporated into our results by providing conditions under which EGDs do not harmfully interact with TGDs and do not affect the decidability and complexity of query answering. We show applications of the aforesaid classes of constraints to the problem of answering conjunctive queries in F-Logic Lite, an object-oriented ontology language, and in some tractable Description Logics.
チェイスアルゴリズムは、クエリ評価、およびタプル生成依存関係（TGD）と等値生成依存関係（EGD）におけるクエリ包含のテストのための基本的なツールです。これまで、このトピックに関する研究のほとんどは、チェイス手順が終了するケースに焦点を当ててきました。本稿では、構文制約によって定義された表現力豊かなTGDのクラス、すなわちガード付きTGD（GTGD）と弱ガード付きTGD集合（WGTGD）を紹介します。これらのクラスでは、チェイス手順が終了することは保証されておらず、したがって無限の結果になる可能性があります。それでもなお、このようなTGDにおける連言クエリ応答とクエリ包含の問題が決定可能であることを証明します。これらの問題に対する決定手順と厳密な計算量境界を提供します。次に、EGDがTGDと有害な相互作用を起こさず、クエリ応答の決定可能性と計算量に影響を与えない条件を提供することで、EGDを結果に組み込む方法を示します。我々は、上述の制約クラスを、オブジェクト指向オントロジー言語であるF-Logic Liteと、いくつかの扱いやすい記述論理における連言クエリへの回答問題に適用します。
Natural Language Inference for Arabic Using Extended Tree Edit Distance with Subtrees
部分木を用いた拡張木編集距離を用いたアラビア語の自然言語推論
Many natural language processing (NLP) applications require the computation of similarities between pairs of syntactic or semantic trees. Many researchers have used tree edit distance for this task, but this technique suffers from the drawback that it deals with single node operations only. We have extended the standard tree edit distance algorithm to deal with subtree transformation operations as well as single nodes. The extended algorithm with subtree operations, TED+ST, is more effective and flexible than the standard algorithm, especially for applications that pay attention to relations among nodes (e.g. in linguistic trees, deleting a modifier subtree should be cheaper than the sum of deleting its components individually). We describe the use of TED+ST for checking entailment between two Arabic text snippets. The preliminary results of using TED+ST were encouraging when compared with two string-based approaches and with the standard algorithm.
多くの自然言語処理（NLP）アプリケーションでは、構文木または意味木のペア間の類似度の計算が必要です。多くの研究者がこのタスクに木編集距離を用いてきましたが、この手法は単一ノード操作しか処理できないという欠点があります。そこで我々は、標準の木編集距離アルゴリズムを拡張し、単一ノードだけでなくサブツリー変換操作も処理できるようにしました。サブツリー操作を含む拡張アルゴリズムTED+STは、特にノード間の関係性に注目するアプリケーション（例えば、言語木において、修飾子サブツリーを削除する方が、その構成要素を個別に削除するよりもコストがかからないはず）において、標準アルゴリズムよりも効果的で柔軟性に優れています。本稿では、2つのアラビア語テキストスニペット間の含意関係をチェックするためのTED+STの使用について説明します。TED+STを使用した予備的な結果は、2つの文字列ベースのアプローチおよび標準アルゴリズムと比較すると有望でした。