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

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

論文

Query and Predicate Emptiness in Ontology-Based Data Access

Query and Predicate Emptiness in Ontology-Based Data Access / オントロジーベースのデータアクセスにおけるクエリと述語の空性

In ontology-based data access (OBDA), database querying is enriched with an ontology that provides domain knowledge and additional vocabulary for query formulation. We identify query emptiness and predicate emptiness as two central reasoning services in this context. Query emptiness asks whether a given query has an empty answer over all databases formulated in a given vocabulary. Predicate emptiness is defined analogously, but quantifies universally over all queries that contain a given predicate. In this paper, we determine the computational complexity of query emptiness and predicate emptiness in the EL, DL-Lite, and ALC-families of description logics, investigate the connection to ontology modules, and perform a practical case study to evaluate the new reasoning services.



オントロジーベースのデータアクセス（OBDA）では、データベースクエリは、ドメイン知識とクエリ作成のための追加語彙を提供するオントロジーによって強化されます。この文脈において、クエリ空性と述語空性の2つが中心的な推論サービスであると認識しています。クエリ空性とは、与えられたクエリが、与えられた語彙で作成されたすべてのデータベースにおいて空の回答を持つかどうかを問うものです。述語空性も同様に定義されますが、与えられた述語を含むすべてのクエリを普遍的に定量化します。本稿では、EL、DL-Lite、およびALCファミリーの記述論理におけるクエリ空性と述語空性の計算複雑性を明らかにし、オントロジーモジュールとの関連性を調査し、新しい推論サービスを評価するための実践的なケーススタディを実施します。

Budgeted Optimization with Constrained Experiments

Budgeted Optimization with Constrained Experiments / 制約付き実験による予算最適化

Motivated by a real-world problem, we study a novel budgeted optimization problem where the goal is to optimize an unknown function f(.) given a budget by requesting a sequence of samples from the function. In our setting, however, evaluating the function at precisely specified points is not practically possible due to prohibitive costs. Instead, we can only request constrained experiments. A constrained experiment, denoted by Q, specifies a subset of the input space for the experimenter to sample the function from. The outcome of Q includes a sampled experiment x, and its function output f(x). Importantly, as the constraints of Q become looser, the cost of fulfilling the request decreases, but the uncertainty about the location x increases. Our goal is to manage this trade-off by selecting a set of constrained experiments that best optimize f(.) within the budget. We study this problem in two different settings, the non-sequential (or batch) setting where a set of constrained experiments is selected at once, and the sequential setting where experiments are selected one at a time. We evaluate our proposed methods for both settings using synthetic and real functions. The experimental results demonstrate the efficacy of the proposed methods.



実世界の問題に着想を得て、我々は新たな予算付き最適化問題を研究します。この問題は、与えられた予算に基づき、関数から一連のサンプルを要求することで、未知の関数f(.)を最適化することを目標とします。しかしながら、我々の設定では、厳密に指定された点で関数を評価することは、法外なコストがかかるため、実際には不可能です。代わりに、制約付き実験を要求することしかできない。制約付き実験（Qと表記）は、実験者が関数をサンプルするための入力空間のサブセットを指定します。Qの出力には、サンプルされた実験xとその関数出力f(x)が含まれます。重要なのは、Qの制約が緩くなるにつれて、要求を満たすコストは減少するが、xの位置に関する不確実性は増大するという点です。我々の目標は、予算内でf(.)を最適に最適化する制約付き実験のセットを選択することで、このトレードオフを管理することです。我々はこの問題を、制約付き実験のセットを一度に選択する非シーケンシャル（またはバッチ）設定と、実験​​を一度に1つずつ選択するシーケンシャル設定の2つの異なる設定で研究します。提案手法を合成関数と実関数の両方の設定で評価し、実験結果から提案手法の有効性を確認した。

Global Continuous Optimization with Error Bound and Fast Convergence

Global Continuous Optimization with Error Bound and Fast Convergence / 誤差限界と高速収束を伴う大域的連続最適化

This paper considers global optimization with a black-box unknown objective function that can be non-convex and non-differentiable. Such a difficult optimization problem arises in many real-world applications, such as parameter tuning in machine learning, engineering design problem, and planning with a complex physics simulator. This paper proposes a new global optimization algorithm, called Locally Oriented Global Optimization (LOGO), to aim for both fast convergence in practice and finite-time error bound in theory. The advantage and usage of the new algorithm are illustrated via theoretical analysis and an experiment conducted with 11 benchmark test functions. Further, we modify the LOGO algorithm to specifically solve a planning problem via policy search with continuous state/action space and long time horizon while maintaining its finite-time error bound. We apply the proposed planning method to accident management of a nuclear power plant. The result of the application study demonstrates the practical utility of our method.



本論文では、非凸かつ微分不可能なブラックボックスの未知の目的関数を持つ大域最適化について考察します。このような困難な最適化問題は、機械学習におけるパラメータ調整、工学設計問題、複雑な物理シミュレータを用いた計画など、多くの現実世界のアプリケーションで発生します。本論文では、実践的な高速収束と理論上の有限時間誤差の両立を目指す、局所指向大域最適化（LOGO）と呼ばれる新しい大域最適化アルゴリズムを提案します。この新しいアルゴリズムの利点と使用法は、理論分析と11個のベンチマークテスト関数を用いた実験によって示されます。さらに、LOGOアルゴリズムを改良し、有限時間誤差の上限を維持しながら、連続的な状態/行動空間と長い時間範囲を持つ方策探索による計画問題を具体的に解く。提案する計画手法を原子力発電所のアクシデントマネジメントに適用します。適用研究の結果は、本手法の実用性を示しています。

Two Aspects of Relevance in Structured Argumentation: Minimality and Paraconsistency

Two Aspects of Relevance in Structured Argumentation: Minimality and Paraconsistency / 構造化議論における関連性の2つの側面：最小性とパラコンシステンシー

This paper studies two issues concerning relevance in structured argumentation in the context of the ASPIC+ framework, arising from the combined use of strict and defeasible inference rules. One issue arises if the strict inference rules correspond to classical logic. A longstanding problem is how the trivialising effect of the classical Ex Falso principle can be avoided while satisfying consistency and closure postulates. In this paper, this problem is solved by disallowing chaining of strict rules, resulting in a variant of the ASPIC+ framework called ASPIC*, and then disallowing the application of strict rules to inconsistent sets of formulas. Thus in effect Rescher & Manor’s paraconsistent notion of weak consequence is embedded in ASPIC*.Another issue is minimality of arguments. If arguments can apply defeasible inference rules, then they cannot be required to have subset-minimal premises, since defeasible rules based on more information may well make an argument stronger. In this paper instead minimality is required of applications of strict rules throughout an argument. It is shown that under some plausible assumptions this does not affect the set of conclusions. In addition, circular arguments are in the new ASPIC* framework excluded in a way that satisfies closure and consistency postulates and that generates finitary argumentation frameworks if the knowledge base and set of defeasible rules are finite. For the latter result the exclusion of chaining of strict rules is essential.Finally, the combined results of this paper are shown to be a proper extension of classical-logic argumentation with preferences and defeasible rules.



本稿では、ASPIC+フレームワークの文脈において、厳密な推論規則と無効化可能な推論規則を組み合わせて使用​​することで生じる、構造化された議論における関連性に関する2つの問題について検討します。1つの問題は、厳密な推論規則が古典論理に対応する場合に生じる。長年の課題は、一貫性と閉包公理を満たしながら、古典的なEx Falso原理の自明化効果をどのように回避できるかです。本稿では、この問題は、厳密な規則の連鎖を禁止することで解決されます。その結果、ASPIC*と呼ばれるASPIC+フレームワークの変種が生まれ、矛盾する式の集合に厳密な規則を適用できなくなります。したがって、実質的に、Rescher & Manorの弱い帰結に関する矛盾した概念がASPIC*に組み込まれています。もう1つの問題は、議論の最小性です。議論が無効化可能な推論規則を適用できる場合、より多くの情報に基づく無効化可能な規則によって議論がより強力になる可能性があるため、議論にサブセット最小の前提を要求することはできない。本論文では、その代わりに、議論全体を通して厳密な規則の適用の最小性が要求されます。いくつかの妥当な仮定の下では、これは結論の集合に影響を与えないことが示されます。さらに、新しいASPIC*フレームワークでは、循環論法は、閉包性と一貫性の公理を満たし、知識ベースと無効化可能な規則の集合が有限である場合に有限論法フレームワークを生成する方法で排除されます。後者の結果を得るには、厳密な規則の連鎖の排除が不可欠です。最後に、本論文の総合的な結果は、選好と無効化可能な規則を用いた古典論理論法の適切な拡張であることが示されます。

Association Discovery and Diagnosis of Alzheimers Disease with Bayesian Multiview Learning

Association Discovery and Diagnosis of Alzheimers Disease with Bayesian Multiview Learning / ベイズ的マルチビュー学習によるアルツハイマー病の連想発見と診断

The analysis and diagnosis of Alzheimers disease (AD) can be based on genetic variations, e.g., single nucleotide polymorphisms (SNPs) and phenotypic traits, e.g., Magnetic Resonance Imaging (MRI) features. We consider two important and related tasks: i) to select genetic and phenotypical markers for AD diagnosis and ii) to identify associations between genetic and phenotypical data. While previous studies treat these two tasks separately, they are tightly coupled because underlying associations between genetic variations and phenotypical features contain the biological basis for a disease. Here we present a new sparse Bayesian approach for joint association study and disease diagnosis. In this approach, common latent features are extracted from different data sources based on sparse projection matrices and used to predict multiple disease severity levels; in return, the disease status can guide the discovery of relationships between data sources. The sparse projection matrices not only reveal interactions between data sources but also select groups of biomarkers related to the disease. Moreover, to take advantage of the linkage disequilibrium (LD) measuring the non-random association of alleles, we incorporate a graph Laplacian type of prior in the model. To learn the model from data, we develop an efficient variational inference algorithm. Analysis on an imaging genetics dataset for the study of Alzheimers Disease (AD) indicates that our model identifies biologically meaningful associations between genetic variations and MRI features, and achieves significantly higher accuracy for predicting ordinal AD stages than the competing methods.



アルツハイマー病（AD）の分析と診断は、一塩基多型（SNP）などの遺伝的変異と、磁気共鳴画像（MRI）の特徴などの表現型特性に基づいて行うことができます。我々は、2つの重要かつ関連するタスク、すなわち、i) AD診断のための遺伝子マーカーと表現型マーカーの選択、およびii)遺伝子データと表現型データ間の関連性の特定について考察します。これまでの研究ではこれら2つのタスクは別々に扱われてきたが、遺伝子変異と表現型特徴間の根底にある関連性が疾患の生物学的基盤を包含しているため、これらは密接に結びついています。本稿では、関連研究と疾患診断を統合するための新たなスパースベイズアプローチを提示します。このアプローチでは、スパース射影行列に基づいて異なるデータソースから共通の潜在的特徴を抽出し、複数の疾患重症度レベルを予測します。これにより、疾患状態はデータソース間の関係性発見の指針となります。スパース射影行列は、データソース間の相互作用を明らかにするだけでなく、疾患に関連するバイオマーカー群も選択します。さらに、アレル間の非ランダムな関連性を測定する連鎖不平衡（LD）を利用するため、グラフラプラシアン型の事前分布をモデルに組み込む。データからモデルを学習するために、効率的な変分推論アルゴリズムを開発します。アルツハイマー病(AD)の研究のための画像遺伝学データセットの分析により、私たちのモデルは遺伝的変異とMRI特徴との間の生物学的に意味のある関連性を識別し、競合方法よりも順序付けられたAD段階の予測において大幅に高い精度を達成することが示されました。

Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization

Combining the Delete Relaxation with Critical-Path Heuristics: A Direct Characterization / 削除緩和法とクリティカルパス・ヒューリスティックスの組み合わせ：直接的な特性評価

Recent work has shown how to improve delete relaxation heuristics by computing relaxed plans, i.e., the hFF heuristic, in a compiled planning task PiC which represents a given set C of fact conjunctions explicitly. While this compilation view of such partial delete relaxation is simple and elegant, its meaning with respect to the original planning task is opaque, and the size of PiC grows exponentially in |C|. We herein provide a direct characterization, without compilation, making explicit how the approach arises from a combination of the delete-relaxation with critical-path heuristics. Designing equations characterizing a novel view on h+ on the one hand, and a generalized version hC of hm on the other hand, we show that h+(PiC) can be characterized in terms of a combined hcplus equation. This naturally generalizes the standard delete-relaxation framework: understanding that framework as a relaxation over singleton facts as atomic subgoals, one can refine the relaxation by using the conjunctions C as atomic subgoals instead. Thanks to this explicit view, we identify the precise source of complexity in hFF(PiC), namely maximization of sets of supported atomic subgoals during relaxed plan extraction, which is easy for singleton-fact subgoals but is NP-complete in the general case. Approximating that problem greedily, we obtain a polynomial-time hCFF version of hFF(PiC), superseding the PiC compilation, and superseding the modified PiCce compilation which achieves the same complexity reduction but at an information loss. Experiments on IPC benchmarks show that these theoretical advantages can translate into empirical ones.



最近の研究では、事実の連言の集合Cを明示的に表現するコンパイル済みプランニングタスクPiCにおいて、緩和されたプラン、すなわちhFFヒューリスティックを計算することで、削除緩和ヒューリスティックを改善する方法が示されています。このような部分的な削除緩和のコンパイル的視点は単純かつ簡潔であるが、元のプランニングタスクに対するその意味は不明瞭であり、PiCのサイズは|C|に対して指数的に増加します。本稿では、コンパイルを伴わずに直接的な特性評価を行い、このアプローチが削除緩和とクリティカルパスヒューリスティックの組み合わせからどのように生じるかを明示的に示す。一方でh+に関する新しい視点を特徴付ける方程式を設計し、他方でhmの一般化版hCを特徴付ける方程式を設計することにより、h+(PiC)がhcplus方程式の組み合わせとして特徴付けられることを示す。これは、標準的な削除緩和フレームワークを自然に一般化します。つまり、そのフレームワークを、単一事実をアトミックサブゴールとして緩和するものとして理解することで、連言Cをアトミックサブゴールとして用いることで、緩和を洗練させることができます。この明示的な視点のおかげで、hFF(PiC)における計算量の正確な原因、すなわち緩和プラン抽出時のサポートされるアトミックサブゴール集合の最大化が特定されました。これは、シングルトンファクトサブゴールの場合は容易ですが、一般的な場合にはNP完全です。この問題を貪欲に近似することで、hFF(PiC)の多項式時間hCFFバージョンが得られ、PiCコンパイルを置き換え、情報損失を伴うが同じ計算量削減を実現する修正PiCceコンパイルを置き換えます。IPCベンチマークでの実験は、これらの理論的利点が実証的利点に変換できることを示しました。

DL-Lite Contraction and Revision

DL-Lite Contraction and Revision / DL-Liteの縮約と修正

Two essential tasks in managing description logic knowledge bases are eliminating problematic axioms and incorporating newly formed ones. Such elimination and incorporation are formalised as the operations of contraction and revision in belief change. In this paper, we deal with contraction and revision for the DL-Lite family through a model-theoretic approach. Standard description logic semantics yields an infinite number of models for DL-Lite knowledge bases, thus it is difficult to develop algorithms for contraction and revision that involve DL models. The key to our approach is the introduction of an alternative semantics called type semantics which can replace the standard semantics in characterising the standard inference tasks of DL-Lite. Type semantics has several advantages over the standard one. It is more succinct and importantly, with a finite signature, the semantics always yields a finite number of models. We then define model-based contraction and revision functions for DL-Lite knowledge bases under type semantics and provide representation theorems for them. Finally, the finiteness and succinctness of type semantics allow us to develop tractable algorithms for instantiating the functions.



記述論理知識ベースを管理する上で重要な2つのタスクは、問題のある公理の削除と、新たに形成された公理の組み込みです。このような削除と組み込みは、信念変更における縮約と修正の操作として形式化されます。本稿では、モデル理論的アプローチを用いてDL-Liteファミリーの縮約と修正を扱います。標準的な記述論理意味論では、DL-Lite知識ベースのモデルが無限に生成されるため、DLモデルを含む縮約および修正アルゴリズムの開発は困難です。本アプローチの鍵となるのは、DL-Liteの標準的な推論タスクを特徴付ける際に標準的な意味論に代わる、型意味論と呼ばれる代替意味論の導入です。型意味論は標準的な意味論に比べていくつかの利点があります。より簡潔であり、さらに重要な点として、有限のシグネチャを持つため、意味論は常に有限個のモデルを生成します。次に、型意味論に基づいてDL-Lite知識ベースのモデルベースの縮約および修正関数を定義し、それらの表現定理を提供します。最後に、型意味論の有限性と簡潔性により、関数をインスタンス化するための扱いやすいアルゴリズムを開発できます。

Generating Models of a Matched Formula With a Polynomial Delay

Generating Models of a Matched Formula With a Polynomial Delay / 多項式遅延を伴う一致式モデルの生成

A matched formula is a CNF formula whose incidence graph admits a matching which matches a distinct variable to every clause. Such a formula is always satisfiable. Matched formulas are used, for example, in the area of parametrized complexity. We prove that the problem of counting the number of the models (satisfying assignments) of a matched formula is #P-complete. On the other hand, we define a class of formulas generalizing the matched formulas and prove that for a formula in this class one can choose in polynomial time a variable suitable for splitting the tree for the search of the models of the formula. As a consequence, the models of a formula from this class, in particular of any matched formula, can be generated sequentially with a delay polynomial in the size of the input. On the other hand, we prove that this task cannot be performed efficiently for linearly satisfiable formulas, which is a generalization of matched formulas containing the class considered above.



マッチドフォーミュラとは、発生グラフにおいてすべての節に異なる変数をマッチさせるマッチングが許容されるCNFフォーミュラです。このようなフォーミュラは常に充足可能です。マッチング式は、例えば、パラメータ化された複雑性の分野で使用されます。マッチング式のモデル（充足割り当て）の数を数える問題は#P完全であることを証明します。一方、マッチング式を一般化する式のクラスを定義し、このクラスの式に対して、式のモデルを探索するためのツリーを分割するのに適した変数を多項式時間で選択できることを証明します。結果として、このクラスの式、特に任意のマッチング式のモデルは、入力のサイズの遅延多項式で順次生成できます。一方、このタスクは、上で検討したクラスを含むマッチング式の一般化である線形充足式に対しては効率的に実行できないことを証明します。

On the Satisfiability Problem for SPARQL Patterns

On the Satisfiability Problem for SPARQL Patterns / SPARQLパターンの充足可能性問題について

The satisfiability problem for SPARQL 1.0 patterns is undecidable in general, since the relational algebra can be emulated using such patterns. The goal of this paper is to delineate the boundary of decidability of satisfiability in terms of the constraints allowed in filter conditions. The classes of constraints considered are bound-constraints, negated bound- constraints, equalities, nonequalities, constant-equalities, and constant-nonequalities. The main result of the paper can be summarized by saying that, as soon as inconsistent filter conditions can be formed, satisfiability is undecidable. The key insight in each case is to find a way to emulate the set difference operation. Undecidability can then be obtained from a known undecidability result for the algebra of binary relations with union, composition, and set difference. When no inconsistent filter conditions can be formed, satisfiability is decidable by syntactic checks on bound variables and on the use of literals. Although the problem is shown to be NP-complete, it is experimentally shown that the checks can be implemented efficiently in practice. The paper also points out that satisfiability for the so-called ‘well-designed’ patterns can be decided by a check on bound variables and a check for inconsistent filter conditions.



SPARQL 1.0パターンの充足可能性問題は、一般に決定不可能です。なぜなら、そのようなパターンを用いて関係代数をエミュレートできるからです。本論文の目的は、フィルタ条件で許容される制約に基づいて、充足可能性の決定可能性の境界を明確にすることです。検討対象となる制約のクラスは、境界制約、否定境界制約、等式、非等式、定数等式、および定数非等式です。本論文の主な結論は、矛盾するフィルタ条件が形成可能になると、充足可能性は決定不可能になる、という点に要約できます。それぞれのケースにおける重要な洞察は、差集合演算をエミュレートする方法を見つけることです。そして、和集合、合成集合、差集合を含む二項関係の代数に関する既知の決定不可能性の結果から、決定不可能性を得ることができます。矛盾するフィルタ条件を形成できない場合、充足可能性は束縛変数とリテラルの使用に関する構文的チェックによって決定できます。この問題はNP完全であることが示されるが、これらのチェックは実際には効率的に実装できることが実験的に示されています。本論文ではまた、いわゆる「適切に設計された」パターンの充足可能性は、束縛変数のチェックと矛盾するフィルタ条件のチェックによって決定できることも指摘しています。

Efficient Mechanism Design for Online Scheduling

Efficient Mechanism Design for Online Scheduling / オンラインスケジューリングのための効率的なメカニズム設計

This paper concerns the mechanism design for online scheduling in a strategic setting. In this setting, each job is owned by a self-interested agent who may misreport the release time, deadline, length, and value of her job, while we need to determine not only the schedule of the jobs, but also the payment of each agent. We focus on the design of incentive compatible (IC) mechanisms, and study the maximization of social welfare (i.e., the aggregated value of completed jobs) by competitive analysis. We first derive two lower bounds on the competitive ratio of any deterministic IC mechanism to characterize the landscape of our research. We then propose a deterministic IC mechanism and show that such a simple mechanism works very well for both the preemption-restart model and the preemption-resume model. We show the mechanism can achieve the optimal competitive ratio of 5 for equal-length jobs and a near optimal competitive ratio (within a constant factor) for unequal-length jobs.



本論文は、戦略的設定におけるオンラインスケジューリングのメカニズム設計に関するものです。この設定では、各ジョブは利己的なエージェントによって所有されており、エージェントはジョブのリリース時間、期限、長さ、および価値を誤って報告する可能性があります。一方、ジョブのスケジュールだけでなく、各エージェントへの報酬も決定する必要があります。本論文は、インセンティブ両立性（IC）メカニズムの設計に焦点を当て、競争分析によって社会的厚生（すなわち、完了したジョブの総価値）の最大化を研究します。まず、研究の全体像を特徴づけるために、決定論的ICメカニズムの競合比に関する2つの下限値を導出します。次に、決定論的ICメカニズムを提案し、このシンプルなメカニズムがプリエンプション・リスタートモデルとプリエンプション・レジュームモデルの両方で非常にうまく機能することを示します。このメカニズムは、等長ジョブに対して最適な競合比5を、不等長ジョブに対してはほぼ最適な競合比（定数倍以内）を達成できることを示します。

Computing Repairs of Inconsistent DL-Programs over EL Ontologies

Computing Repairs of Inconsistent DL-Programs over EL Ontologies / ELオントロジー上の矛盾したDLプログラムの修復計算

Description Logic (DL) ontologies and non-monotonic rules are two prominent Knowledge Representation (KR) formalisms with complementary features that are essential for various applications. Nonmonotonic Description Logic (DL) programs combine these formalisms thus providing support for rule-based reasoning on top of DL ontologies using a well-defined query interface represented by so-called DL-atoms. Unfortunately, interaction of the rules and the ontology may incur inconsistencies such that a DL-program lacks answer sets (i.e., models), and thus yields no information. This issue is addressed by recently defined repair answer sets, for computing which an effective practical algorithm was proposed for DL-Lite A ontologies that reduces a repair computation to constraint matching based on so-called support sets. However, the algorithm exploits particular features of DL-Lite A and can not be readily applied to repairing DL-programs over other prominent DLs like EL. compared to DL-Lite A , in EL support sets may neither be small nor only few support sets might exist, and completeness of the algorithm may need to be given up when the support information is bounded. We thus provide an approach for computing repairs for DL-programs over EL ontologies based on partial (incomplete) support families. The latter are constructed using datalog query rewriting techniques as well as ontology approximation based on logical difference between EL-terminologies. We show how the maximal size and number of support sets for a given DL-atom can be estimated by analyzing the properties of a support hypergraph, which characterizes a relevant set of TBox axioms needed for query derivation. We present a declarative implementation of the repair approach and experimentally evaluate it on a set of benchmark problems; the promising results witness practical feasibility of our repair approach.



記述論理（DL）オントロジーと非単調ルールは、様々なアプリケーションに不可欠な補完的な機能を備えた、2つの主要な知識表現（KR）形式主義です。非単調記述論理（DL）プログラムはこれらの形式主義を組み合わせることで、いわゆるDLアトムで表される明確に定義されたクエリインターフェースを用いて、DLオントロジー上でルールベース推論をサポートします。しかしながら、ルールとオントロジーの相互作用によって矛盾が生じ、DLプログラムに回答セット（つまりモデル）が欠落し、情報が生成されない場合があります。この問題は、最近定義された修復回答集合によって解決されます。この計算のために、DL-Lite Aオントロジーに対して、いわゆるサポート集合に基づく制約マッチングに修復計算を簡略化する、効果的で実用的なアルゴリズムが提案されています。しかし、このアルゴリズムはDL-Lite Aの特定の機能を利用しており、ELのような他の主要なDL上のDLプログラムの修復には容易に適用できません。DL-Lite Aと比較して、ELではサポート集合が小さくないか、少数しか存在しない可能性があり、サポート情報が制限されている場合、アルゴリズムの完全性を放棄する必要があるかもしれません。そこで、部分的（不完全）サポートファミリーに基づくELオントロジー上のDLプログラムの修復を計算するためのアプローチを提供します。後者は、データログクエリ書き換え技術と、EL用語間の論理的差異に基づくオントロジー近似を用いて構築されます。クエリ導出に必要なTBox公理の関連集合を特徴付けるサポートハイパーグラフの特性を分析することにより、特定のDLアトムのサポート集合の最大サイズと数を推定する方法を示します。私たちは修復アプローチの宣言的実装を提示し、それを一連のベンチマーク問題で実験的に評価します。有望な結果は、私たちの修復アプローチの実際的な実現可能性を証明しています。

Time-Sensitive Bayesian Information Aggregation for Crowdsourcing Systems

Time-Sensitive Bayesian Information Aggregation for Crowdsourcing Systems / クラウドソーシングシステムのための時間依存型ベイズ情報集約

Many aspects of the design of efficient crowdsourcing processes, such as defining workers bonuses, fair prices and time limits of the tasks, involve knowledge of the likely duration of the task at hand. In this work we introduce a new timesensitive Bayesian aggregation method that simultaneously estimates a tasks duration and obtains reliable aggregations of crowdsourced judgments. Our method, called BCCTime, uses latent variables to represent the uncertainty about the workers completion time, the tasks duration and the workers accuracy. To relate the quality of a judgment to the time a worker spends on a task, our model assumes that each task is completed within a latent time window within which all workers with a propensity to genuinely attempt the labelling task (i.e., no spammers) are expected to submit their judgments. In contrast, workers with a lower propensity to valid labelling, such as spammers, bots or lazy labellers, are assumed to perform tasks considerably faster or slower than the time required by normal workers. Specifically, we use efficient message-passing Bayesian inference to learn approximate posterior probabilities of (i) the confusion matrix of each worker, (ii) the propensity to valid labelling of each worker, (iii) the unbiased duration of each task and (iv) the true label of each task. Using two real- world public datasets for entity linking tasks, we show that BCCTime produces up to 11% more accurate classifications and up to 100% more informative estimates of a tasks duration compared to stateoftheart methods.



効率的なクラウドソーシングプロセスの設計には、作業員へのボーナス、公正な価格、タスクの制限時間の定義など、多くの側面において、当該タスクの所要時間に関する知識が求められます。本研究では、タスクの所要時間を推定すると同時に、クラウドソーシングによる判断の信頼性の高い集約値を取得する、時間依存型ベイズ集約法を新たに導入します。BCCTimeと呼ばれる本手法は、潜在変数を用いて、作業員の完了時間、タスクの所要時間、作業員の正確性に関する不確実性を表します。判断の質と作業員がタスクに費やす時間を関連付けるため、本モデルでは、各タスクが、真にラベリングタスクに挑戦する傾向を持つすべての作業員（つまり、スパマーではない作業員）が判断を提出すると予想される潜在時間枠内で完了すると仮定します。一方、スパマー、ボット、怠惰なラベラーなど、有効なラベリングを行う傾向が低い作業員は、通常の作業員に必要な時間よりも大幅に速く、または遅くタスクを実行すると仮定します。具体的には、効率的なメッセージパッシングベイズ推論を用いて、(i)各ワーカーの混同行列、(ii)各ワーカーの有効なラベル付け傾向、(iii)各タスクの偏りのない所要時間、(iv)各タスクの真のラベルの事後確率を近似的に学習します。エンティティリンクタスク用の2つの公開データセットを用いて、BCCTimeは、最先端の手法と比較して、分類精度が最大11%向上し、タスク所要時間の推定情報量が最大100%増加することを示します。

Time-Bounded Best-First Search for Reversible and Non-reversible Search Graphs

Time-Bounded Best-First Search for Reversible and Non-reversible Search Graphs / 可逆および非可逆検索グラフのための時間制限付き最良優先探索

Time-Bounded A* is a real-time, single-agent, deterministic search algorithm that expands states of a graph in the same order as A* does, but that unlike A* interleaves search and action execution. Known to outperform state-of-the-art real-time search algorithms based on Korf’s Learning Real-Time A* (LRTA*) in some benchmarks, it has not been studied in detail and is sometimes not considered as a “true” real-time search algorithm since it fails in non-reversible problems even it the goal is still reachable from the current state. In this paper we propose and study Time-Bounded Best-First Search (TB(BFS)) a straightforward generalization of the time-bounded approach to any best-first search algorithm. Furthermore, we propose Restarting Time-Bounded Weighted A* (TB_R(WA*)), an algorithm that deals more adequately with non-reversible search graphs, eliminating “backtracking moves” and incorporating search restarts and heuristic learning. In non-reversible problems we prove that TB(BFS) terminates and we deduce cost bounds for the solutions returned by Time-Bounded Weighted A* (TB(WA*)), an instance of TB(BFS). Furthermore, we prove TB_R(WA*), under reasonable conditions, terminates. We evaluate TB(WA) in both grid pathfinding and the 15-puzzle. In addition, we evaluate TB_R(WA*) on the racetrack problem. We compare our algorithms to LSS-LRTWA*, a variant of LRTA* that can exploit lookahead search and a weighted heuristic. A general observation is that the performance of both TB(WA*) and TB_R(WA*) improves as the weight parameter is increased. In addition, our time-bounded algorithms almost always outperform LSS-LRTWA* by a significant margin.



Time-Bounded A*は、リアルタイム、シングルエージェント、決定論的な探索アルゴリズムであり、A*と同じ順序でグラフの状態を拡張しますが、A*とは異なり、探索とアクション実行をインターリーブします。いくつかのベンチマークでは、KorfのLearning Real-Time A* (LRTA*)に基づく最先端のリアルタイム探索アルゴリズムよりも優れた性能を示すことが知られていますが、詳細な研究は行われておらず、現在の状態から目標に到達可能であっても不可逆な問題では失敗するため、「真の」リアルタイム探索アルゴリズムとは見なされないこともあります。本稿では、時間制限付きアプローチをあらゆる最良優先探索アルゴリズムに直接一般化した、時間制限付き最良優先探索(TB(BFS))を提案し、検討します。さらに、非可逆な探索グラフをより適切に処理し、「バックトラック動作」を排除し、探索の再開とヒューリスティック学習を組み込んだアルゴリズム、再開時間制限付き重み付きA* (TB_R(WA*))を提案します。不可逆な問題では、TB(BFS)が終了することを証明し、TB(BFS)のインスタンスである時間制限付き重み付きA* (TB(WA*))によって返される解のコスト境界を導出します。さらに、TB_R(WA*)が妥当な条件下で終了することを証明します。TB(WA)をグリッド経路探索と15パズルの両方で評価します。さらに、レーストラック問題でもTB_R(WA*)を評価します。私たちのアルゴリズムを、先読み探索と重み付きヒューリスティックを活用できるLRTA*の変種であるLSS-LRTWA*と比較します。一般的に、重みパラメータが増加すると、TB(WA*)とTB_R(WA*)の両方のパフォーマンスが向上します。さらに、時間制限のあるアルゴリズムは、ほぼ常にLSS-LRTWA*を大幅に上回ります。

A Study of Proxies for Shapley Allocations of Transport Costs

A Study of Proxies for Shapley Allocations of Transport Costs / 輸送費のShapley配分のためのプロキシの研究

We survey existing rules of thumb, propose novel methods, and comprehensively evaluate a number of solutions to the problem of calculating the cost to serve each location in a single-vehicle transport setting. Cost to serve analysis has applications both strategically and operationally in transportation settings. The problem is formally modeled as the traveling salesperson game (TSG), a cooperative transferable utility game in which agents correspond to locations in a traveling salesperson problem (TSP). The total cost to serve all locations in the TSP is the length of an optimal tour. An allocation divides the total cost among individual locations, thus providing the cost to serve each of them. As one of the most important normative division schemes in cooperative games, the Shapley value gives a principled and fair allocation for a broad variety of games including the TSG. We consider a number of direct and sampling-based procedures for calculating the Shapley value, and prove that approximating the Shapley value of the TSG within a constant factor is NP-hard. Treating the Shapley value as an ideal baseline allocation, we survey six proxies for it that are each relatively easy to compute. Some of these proxies are rules of thumb and some are procedures international delivery companies use(d) as cost allocation methods. We perform an experimental evaluation using synthetic Euclidean games as well as games derived from real-world tours calculated for scenarios involving fast-moving goods; where deliveries are made on a road network every day. We explore several computationally tractable allocation techniques that are good proxies for the Shapley value in problem instances of a size and complexity that is commercially relevant.



私たちは既存の経験則を調査し、新しい方法を提案し、単一車両輸送環境で各場所へのサービス提供コストを計算する問題に対するいくつかの解決策を包括的に評価します。サービス提供コスト分析は、輸送環境において戦略的にも運用的にも応用できます。この問題は、巡回セールスマンゲーム（TSG）として正式にモデル化されます。これは、エージェントが巡回セールスマン問題（TSP）における各拠点に対応する、協力的で移転可能な効用ゲームです。TSP内のすべての拠点へのサービス提供にかかる総費用は、最適な巡回距離となります。配分は、総費用を個々の拠点に分配することで、各拠点へのサービス提供にかかる費用を算出します。協力ゲームにおける最も重要な規範的分割法の一つであるシャプレー値は、TSGを含む様々なゲームにおいて、原理に基づいた公平な配分を与える。我々は、シャプレー値を計算するための直接法およびサンプリングに基づく様々な手順を検討し、TSGのシャプレー値を定数倍の範囲内で近似することがNP困難であることを証明します。シャプレー値を理想的なベースライン配分として扱い、比較的計算が容易な6つの代理変数を調査します。これらの代理変数には、経験則や国際配送会社が費用配分方法として用いる手順などがあります。我々は、合成ユークリッドゲームと、現実世界の巡回から導出したゲームを用いて実験的評価を行う。これらのゲームは、高速移動する商品を扱うシナリオ、すなわち道路網上で毎日配送が行われるシナリオを想定して計算されたものです。我々は、商業的に意味のある規模と複雑さを持つ問題インスタンスにおいて、シャプレー値の適切な代理指標となる、計算的に扱いやすい複数の割り当て手法を探求します。

Automatic Wordnet Development for Low-Resource Languages using Cross-Lingual WSD

Automatic Wordnet Development for Low-Resource Languages using Cross-Lingual WSD / 低リソース言語のための自動Wordnet開発クロスリンガルWSD

‎Wordnets are an effective resource for natural language processing and information retrieval‎, ‎especially for semantic processing and meaning related tasks‎. ‎So far‎, ‎wordnets have been constructed for many languages‎. ‎However‎, ‎the automatic development of wordnets for low-resource languages has not been well studied‎. ‎In this paper‎, ‎an Expectation-Maximization algorithm is used to create high quality and large scale wordnets for poor-resource languages‎. ‎The proposed method benefits from possessing cross-lingual word sense disambiguation and develops a wordnet by only using a bi-lingual dictionary and a mono-lingual corpus‎. ‎The proposed method has been executed with Persian language and the resulting wordnet has been evaluated through several experiments‎. ‎The results show that the induced wordnet has a precision score of 90% and a recall score of 35%‎.



ワードネットは、自然言語処理と情報検索、特に意味処理と意味関連タスクのための効果的なリソースです。これまで、多くの言語に対してワードネットが構築されてきました。しかし、リソースの少ない言語のワードネットの自動開発については十分に研究されていません。本稿では、期待最大化アルゴリズムを使用して、リソースの少ない言語用の高品質で大規模なワードネットを作成します。提案された方法は、言語間の語義の曖昧性解消の利点を活用し、バイリンガル辞書とモノリンガルコーパスのみを使用してワードネットを開発します。提案された方法はペルシャ語で実行され、結果として得られたワードネットはいくつかの実験を通じて評価されました。結果によると、誘導されたワードネットの精度スコアは90％、再現率スコアは35％でした。

Datalog+- Ontology Consolidation

Datalog+- Ontology Consolidation / Datalog+ – オントロジー統合

Knowledge bases in the form of ontologies are receiving increasing attention as they allow to clearly represent both the available knowledge, which includes the knowledge in itself and the constraints imposed to it by the domain or the users. In particular, Datalog± ontologies are attractive because of their property of decidability and the possibility of dealing with the massive amounts of data in real world environments; however, as it is the case with many other ontological languages, their application in collaborative environments often lead to inconsistency related issues. In this paper we introduce the notion of incoherence regarding Datalog± ontologies, in terms of satisfiability of sets of constraints, and show how under specific conditions incoherence leads to inconsistent Datalog± ontologies. The main contribution of this work is a novel approach to restore both consistency and coherence in Datalog± ontologies. The proposed approach is based on kernel contraction and restoration is performed by the application of incision functions that select formulas to delete. Nevertheless, instead of working over minimal incoherent/inconsistent sets encountered in the ontologies, our operators produce incisions over non-minimal structures called clusters. We present a construction for consolidation operators, along with the properties expected to be satisfied by them. Finally, we establish the relation between the construction and the properties by means of a representation theorem. Although this proposal is presented for Datalog± ontologies consolidation, these operators can be applied to other types of ontological languages, such as Description Logics, making them apt to be used in collaborative environments like the Semantic Web.



オントロジー形式の知識ベースは、利用可能な知識（知識自体を含む）と、ドメインまたはユーザーによって課せられる制約の両方を明確に表現できるため、ますます注目を集めています。特に、Datalog±オントロジーは、決定可能性の特性と、現実世界の環境における膨大な量のデータを処理する可能性のために魅力的です。しかし、他の多くのオントロジー言語の場合と同様に、コラボレーション環境への適用は、しばしば矛盾に関連する問題につながります。本稿では、制約セットの充足可能性の観点から、Datalog±オントロジーに関する矛盾の概念を紹介し、特定の条件下で矛盾がどのように矛盾したDatalog±オントロジーにつながるかを示します。本研究の主な貢献は、Datalog±オントロジーの一貫性と一貫性の両方を回復するための新しいアプローチです。提案されたアプローチはカーネル収縮に基づいており、削除する式を選択する切込み関数を適用することで回復が実行されます。しかしながら、オントロジーで遭遇する極小の矛盾/不整合集合を処理する代わりに、我々の演算子はクラスターと呼ばれる非極小構造に切り込みを入れます。我々は統合演算子の構成と、それらが満たすと期待される特性を提示します。最後に、表現定理を用いて構成と特性の関係を確立します。この提案はDatalog±オントロジー統合のために提示されていますが、これらの演算子は記述論理などの他の種類のオントロジー言語にも適用でき、セマンティックWebのような協調環境での使用に適しています。

The IBaCoP Planning System: Instance-Based Configured Portfolios

The IBaCoP Planning System: Instance-Based Configured Portfolios / IBaCoP計画システム：インスタンスベースの構成ポートフォリオ

Sequential planning portfolios are very powerful in exploiting the complementary strength of different automated planners. The main challenge of a portfolio planner is to define which base planners to run, to assign the running time for each planner and to decide in what order they should be carried out to optimize a planning metric. Portfolio configurations are usually derived empirically from training benchmarks and remain fixed for an evaluation phase. In this work, we create a per-instance configurable portfolio, which is able to adapt itself to every planning task. The proposed system pre-selects a group of candidate planners using a Pareto-dominance filtering approach and then it decides which planners to include and the time assigned according to predictive models. These models estimate whether a base planner will be able to solve the given problem and, if so, how long it will take. We define different portfolio strategies to combine the knowledge generated by the models. The experimental evaluation shows that the resulting portfolios provide an improvement when compared with non-informed strategies. One of the proposed portfolios was the winner of the Sequential Satisficing Track of the International Planning Competition held in 2014.



シーケンシャルプランニングポートフォリオは、異なる自動プランナーの相補的な強みを活用する上で非常に強力です。ポートフォリオプランナーの主な課題は、どのベースプランナーを実行するかを定義し、各プランナーに実行時間を割り当て、プランニングメトリックを最適化するためにそれらをどのような順序で実行するかを決定することです。ポートフォリオ構成は通常、トレーニングベンチマークから経験的に導出され、評価フェーズでは固定されたままになります。本研究では、インスタンスごとに構成可能なポートフォリオを作成し、あらゆる計画タスクに適応できるようにします。提案システムは、パレート優位フィルタリング手法を用いて候補プランナーのグループを事前に選択し、予測モデルに基づいてどのプランナーを含めるか、また割り当てる時間を決定します。これらのモデルは、ベースプランナーが与えられた問題を解決できるかどうか、そして解決できる場合はどのくらいの時間がかかるかを予測します。モデルによって生成された知識を組み合わせるために、異なるポートフォリオ戦略を定義します。実験的評価により、結果として得られたポートフォリオは、情報提供を受けない戦略と比較して改善が見られることが示されました。提案されたポートフォリオの1つは、2014年に開催された国際計画コンペティションのシーケンシャル満足度トラックで優勝しました。

Qualitative Spatial Logics for Buffered Geometries

Qualitative Spatial Logics for Buffered Geometries / バッファ付きジオメトリのための定性的空間ロジック

This paper describes a series of new qualitative spatial logics for checking consistency of sameAs and partOf matches between spatial objects from different geospatial datasets, especially from crowd-sourced datasets. Since geometries in crowd-sourced data are usually not very accurate or precise, we buffer geometries by a margin of error or a level of tolerance, and define spatial relations for buffered geometries. The spatial logics formalize the notions of `buffered equal’ (intuitively corresponding to `possibly sameAs’), `buffered part of’ (`possibly partOf’), `near’ (`possibly connected’) and `far’ (`definitely disconnected’). A sound and complete axiomatisation of each logic is provided with respect to models based on metric spaces. For each of the logics, the satisfiability problem is shown to be NP-complete. Finally, we briefly describe how the logics are used in a system for generating and debugging matches between spatial objects, and report positive experimental evaluation results for the system.



本稿では、異なる地理空間データセット、特にクラウドソーシングされたデータセットの空間オブジェクト間のsameAsおよびpartOf一致の一貫性をチェックするための、一連の新しい定性的な空間ロジックについて説明します。クラウドソーシングされたデータのジオメトリは通常、それほど正確または精密ではないため、誤差範囲または許容レベルによってジオメトリをバッファリングし、バッファリングされたジオメトリの空間関係を定義します。空間ロジックは、「buffered equal」（直感的には「おそらくsameAs」に対応）、「buffered part of」（「おそらくpartOf」に対応）、「near」（「おそらく接続されている」）、「far」（「確実に切断されている」）という概念を形式化します。各ロジックは、計量空間に基づくモデルに関して健全かつ完全な公理化が提供されます。各ロジックについて、充足可能性問題がNP完全であることが示されます。最後に、空間オブジェクト間のマッチングを生成およびデバッグするシステムにおいて、これらのロジックがどのように使用されるかを簡単に説明し、システムの良好な実験評価結果を報告します。

Optimal Any-Angle Pathfinding In Practice

Optimal Any-Angle Pathfinding In Practice / 実践における最適任意角度経路探索

Any-angle pathfinding is a fundamental problem in robotics and computer games. The goal is to find a shortest path between a pair of points on a grid map such that the path is not artificially constrained to the points of the grid. Prior research has focused on approximate online solutions. A number of exact methods exist but they all require super-linear space and pre-processing time. In this study, we describe Anya: a new and optimal any-angle pathfinding algorithm. Where other works find approximate any-angle paths by searching over individual points from the grid, Anya finds optimal paths by searching over sets of states represented as intervals. Each interval is identified on-the-fly. From each interval Anya selects a single representative point that it uses to compute an admissible cost estimate for the entire set. Anya always returns an optimal path if one exists. Moreover it does so without any offline pre-processing or the introduction of additional memory overheads. In a range of empirical comparisons we show that Anya is competitive with several recent (sub-optimal) online and pre-processing based techniques and is up to an order of magnitude faster than the most common benchmark algorithm, a grid-based implementation of A*.



任意角度経路探索は、ロボット工学とコンピュータゲームにおける基本的な問題です。その目的は、グリッドマップ上の2点間の最短経路を、グリッド上の点に人為的に制約されない経路で見つけることです。これまでの研究は、近似的なオンラインソリューションに焦点を当ててきました。厳密な手法は数多く存在しますが、いずれも超線形空間と前処理時間を必要とします。本研究では、新しく最適な任意角度経路探索アルゴリズムであるAnyaについて説明します。他の研究では、グリッド上の個々の点を探索することで近似的な任意角度経路を見つけますが、Anyaは区間として表現された状態集合を探索することで最適経路を見つけます。各区間はオンザフライで識別されます。各区間からAnyaは単一の代表点を選択し、それを用いて集合全体の許容コスト推定値を計算します。Anyaは、最適経路が存在する場合は常にそれを返します。さらに、オフライン前処理や追加のメモリオーバーヘッドの導入なしにこれを行います。様々な実証的比較において、Anyaは最近の（最適ではない）オンラインおよび前処理ベースの手法と競合し、最も一般的なベンチマークアルゴリズムであるA*のグリッドベース実装よりも最大1桁高速であることを示す。

参考文献

• Journal of Artificial Intelligence Resarch Vol. 56 (2016)

関連情報

• Journal of Artificial Intelligence Research: 論文一覧