論文の概要: Characterizing Boundedness in Chase Variants
- arxiv url: http://arxiv.org/abs/2004.10030v1
- Date: Tue, 21 Apr 2020 14:07:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-11 07:23:46.654659
- Title: Characterizing Boundedness in Chase Variants
- Title（参考訳）: カオス変数の有界性評価
- Authors: Stathis Delivorias, Michel Lecl\`ere, Marie-Laure Mugnier, Federico
Ulliana
- Abstract要約: 与えられた規則の集合に対する追跡の深さが整数 k で有界かどうかを問う k-有界性問題の決定可能性について検討する。
主な追尾変種は,その特性,すなわち,難読性,半報知性,制限された追尾性,および幅優先バージョンを満足することを示す。
- 参考スコア（独自算出の注目度）: 1.7033055327465234
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existential rules are a positive fragment of first-order logic that
generalizes function-free Horn rules by allowing existentially quantified
variables in rule heads. This family of languages has recently attracted
significant interest in the context of ontology-mediated query answering.
Forward chaining, also known as the chase, is a fundamental tool for computing
universal models of knowledge bases, which consist of existential rules and
facts. Several chase variants have been defined, which differ on the way they
handle redundancies. A set of existential rules is bounded if it ensures the
existence of a bound on the depth of the chase, independently from any set of
facts. Deciding if a set of rules is bounded is an undecidable problem for all
chase variants. Nevertheless, when computing universal models, knowing that a
set of rules is bounded for some chase variant does not help much in practice
if the bound remains unknown or even very large. Hence, we investigate the
decidability of the k-boundedness problem, which asks whether the depth of the
chase for a given set of rules is bounded by an integer k. We identify a
general property which, when satisfied by a chase variant, leads to the
decidability of k-boundedness. We then show that the main chase variants
satisfy this property, namely the oblivious, semi-oblivious (aka Skolem), and
restricted chase, as well as their breadth-first versions. This paper is under
consideration for publication in Theory and Practice of Logic Programming.
- Abstract（参考訳）: 既存の規則は、関数のないホーン規則を一般化する一階述語論理の正の断片である。
この言語群は、オントロジーによるクエリ応答の文脈において、最近大きな関心を集めている。
フォワード・チェイン(フォワード・チェイン、フォワード・チェイン、フォワード・チェイン)は、知識基盤の普遍的なモデルを計算するための基本的なツールである。
いくつかのチェイス変種が定義されており、冗長性を扱う方法が異なる。
存在規則の組は、いかなる事実の組とも独立に、チェイスの深さに束縛が存在することを保証すれば、有界である。
ルールの集合が有界かどうかを決定することは、すべてのチェイス変種に対して決定不能な問題である。
それでも、普遍モデルを計算するとき、あるチェイス変種に対して規則の集合が有界であることを知ることは、境界が未知あるいは非常に大きいままである場合、実際にはあまり役に立たない。
そこで,与えられた規則集合に対するチェイスの深さが整数 k で有界かどうかを問う k-境界問題の決定可能性について検討する。
チェイス変量によって満たされた場合、k-有界性の決定可能性をもたらす一般的な性質を同定する。
次に、主なチェイス変種が、この性質を満たすことを示し、すなわち、曖昧で半曖昧な(別名Skolem)と制限されたチェイスと、その幅優先のバージョンである。
本稿では,論理プログラミングの理論と実践について考察する。
関連論文リスト
- Contextual Multinomial Logit Bandits with General Value Functions [47.06746975822902]
MNL(Contextual multinomial logit)バンドレットは、オンライン小売や広告など、現実のアソシエーションレコメンデーション問題の多くをキャプチャする。
我々は、文脈的盗賊の研究の最近の動向からアイデアを借りて、基礎的真理を含む一般値関数クラスを持つ文脈的MNL盗賊を考察する。
具体的には、計算と逆の設定の両方を考慮し、それぞれが異なるトレードオフを持つ一連のアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-12T23:50:44Z) - ChatRule: Mining Logical Rules with Large Language Models for Knowledge
Graph Reasoning [107.61997887260056]
そこで我々は,知識グラフ上の論理ルールをマイニングするための大規模言語モデルの力を解き放つ新しいフレームワークChatRuleを提案する。
具体的には、このフレームワークは、KGのセマンティック情報と構造情報の両方を活用するLLMベースのルールジェネレータで開始される。
生成されたルールを洗練させるために、ルールランキングモジュールは、既存のKGから事実を取り入れてルール品質を推定する。
論文 参考訳（メタデータ） (2023-09-04T11:38:02Z) - Semi-Oblivious Chase Termination for Linear Existential Rules: An
Experimental Study [5.936402320555635]
チェイス手順は、制約のある推論を可能にする、データベースの基本的なアルゴリズムツールである。
データベースと一連の制約を入力として取り、制約によって決定されたデータベースを反復的に完了します。
しかし、重要な課題は、それが終了しないかもしれないという事実であり、それが与えられたデータベースと一連の制約を終了するかどうかをチェックする問題に繋がる。
論文 参考訳（メタデータ） (2023-03-22T18:21:01Z) - Machine Learning with Probabilistic Law Discovery: A Concise
Introduction [77.34726150561087]
Probabilistic Law Discovery (PLD) は、確率論的ルール学習の変種を実装した論理ベースの機械学習手法である。
PLDはDecision Tree/Random Forestメソッドに近いが、関連するルールの定義方法に大きく異なる。
本稿はPLDの主な原則を概説し、その利点と限界を強調し、いくつかのアプリケーションガイドラインを提供する。
論文 参考訳（メタデータ） (2022-12-22T17:40:13Z) - Normalisations of Existential Rules: Not so Innocuous! [7.260554897161947]
本研究では,既存のルールが追跡(非)終了とFO-rewritability(FO-rewritability)に与える影響について検討した。
これはまた、独立した関心の追跡終了に関連するオープンな問題の研究にも繋がる。
論文 参考訳（メタデータ） (2022-06-07T09:01:56Z) - Non-Uniformly Terminating Chase: Size and Complexity [8.250374560598493]
我々は、ロバストなルールベースの終了を形成する、ガード付き生成依存(TGD)に焦点を当てる。
主な発見の1つは、保護されたTGDに対する一様でない半出版的追跡が、データベースの時間内で実現可能であることである。
本稿では,従来のオントロジクエリ応答の文脈で導入された単純化や線形化といった基本的な手法が,チェイス終了問題に安全に適用可能であることを示す。
論文 参考訳（メタデータ） (2022-04-22T09:07:08Z) - Discovering Useful Compact Sets of Sequential Rules in a Long Sequence [57.684967309375274]
COSSUは、小さな、意味のある一連の規則をマイニングするアルゴリズムである。
COSSUは、長いシーケンスから、関連するクローズド・シーケンシャル・ルールの集合を検索できることを示す。
論文 参考訳（メタデータ） (2021-09-15T18:25:18Z) - Parallelisable Existential Rules: a Story of Pieces [2.20439695290991]
実存則の並列化可能な集合を導入し、任意のインスタンスから単一の幅優先のステップでチェイスを計算できる。
並列化可能な規則集合は、追跡のために有界かつ新しいルールのクラスに属するような規則集合であることを示す。
論文 参考訳（メタデータ） (2021-07-13T13:09:14Z) - Causal Expectation-Maximisation [70.45873402967297]
ポリツリーグラフを特徴とするモデルにおいても因果推論はNPハードであることを示す。
我々は因果EMアルゴリズムを導入し、分類的表現変数のデータから潜伏変数の不確かさを再構築する。
我々は、反事実境界が構造方程式の知識なしにしばしば計算できるというトレンドのアイデアには、目立たずの制限があるように思える。
論文 参考訳（メタデータ） (2020-11-04T10:25:13Z) - RNNLogic: Learning Logic Rules for Reasoning on Knowledge Graphs [91.71504177786792]
本稿では知識グラフに基づく推論のための論理規則の学習について研究する。
論理規則は、予測に使用されるときに解釈可能な説明を提供するとともに、他のタスクに一般化することができる。
既存の手法は、検索スペースの検索の問題や、スパース報酬による非効率な最適化に悩まされている。
論文 参考訳（メタデータ） (2020-10-08T14:47:02Z) - Oblivious and Semi-Oblivious Boundedness for Existential Rules [5.875276459237496]
正存在規則の文脈における有界性の概念について考察する。
難解なチェイス変種と半報知なチェイス変種に注意を集中させることで、有界性の特徴づけを与える。
ルールの集合が複数のクラスに束縛されているかどうかを判断し、問題の複雑さを概説することが決定可能であることを示す。
論文 参考訳（メタデータ） (2020-06-15T15:18:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。