論文の概要: Non-Uniformly Terminating Chase: Size and Complexity

• arxiv url: http://arxiv.org/abs/2204.10584v1
• Date: Fri, 22 Apr 2022 09:07:08 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-25 21:28:03.473374
• Title: Non-Uniformly Terminating Chase: Size and Complexity
• Title（参考訳）: 非一様終端チェイス:サイズと複雑さ
• Authors: Marco Calautti, Georg Gottlob, Andreas Pieris
• Abstract要約: 我々は、ロバストなルールベースの終了を形成する、ガード付き生成依存(TGD)に焦点を当てる。 主な発見の1つは、保護されたTGDに対する一様でない半出版的追跡が、データベースの時間内で実現可能であることである。 本稿では,従来のオントロジクエリ応答の文脈で導入された単純化や線形化といった基本的な手法が,チェイス終了問題に安全に適用可能であることを示す。
• 参考スコア（独自算出の注目度）: 8.250374560598493
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The chase procedure, originally introduced for checking implication of database constraints, and later on used for computing data exchange solutions, has recently become a central algorithmic tool in rule-based ontological reasoning. In this context, a key problem is non-uniform chase termination: does the chase of a database w.r.t. a rule-based ontology terminate? And if this is the case, what is the size of the result of the chase? We focus on guarded tuple-generating dependencies (TGDs), which form a robust rule-based ontology language, and study the above central questions for the semi-oblivious version of the chase. One of our main findings is that non-uniform semi-oblivious chase termination for guarded TGDs is feasible in polynomial time w.r.t. the database, and the size of the result of the chase (whenever is finite) is linear w.r.t. the database. Towards our results concerning non-uniform chase termination, we show that basic techniques such as simplification and linearization, originally introduced in the context of ontological query answering, can be safely applied to the chase termination problem.
• Abstract（参考訳）: チェイス手順は、もともとデータベース制約の含意をチェックするために導入され、後にデータ交換ソリューションの計算に使われるようになったが、最近、ルールベースのオントロジ推論の中心的なアルゴリズムツールとなった。 この文脈では、鍵となる問題は非一様チェイス終了である:データベースw.r.t.のチェイスは終了するか? もしそうなら、チェイスの結果のサイズは? 本稿では,厳密な規則に基づくオントロジー言語を構成するタプル生成依存性 (TGD) に注目し,上記の中心的課題について考察する。 主な発見の1つは、保護されたTGDに対する一様でない半盲検追跡終了は、データベースの多項式時間 w.r.t で実現可能であり、追跡結果(有限である場合)のサイズは、データベースの線形時間 w.r.t である。 非一様チェイス終了に関する結果に向けて,もともとオントロジクエリ応答の文脈で導入された単純化や線形化といった基本的な手法がチェイス終了問題に安全に適用できることを示す。

関連論文リスト

• ION-C: Integration of Overlapping Networks via Constraints [2.6068919473964893]
  本稿では,すべての入力グラフに整合した基底トラスDAGの最小同値クラスを,IONと呼ばれる局所的な独立関係を利用して列挙するアルゴリズムを提案する。 ION-Cアルゴリズムは、異なる大きさ、密度、サブグラフ間の重なり合いの度合いでランダムな合成グラフ上で実行された。 実世界のデータ上でION-Cを検証するために、欧州社会調査(ESS)の2回の反復から得られた重なり合うグラフに基づいてアルゴリズムを実行した。
  論文  参考訳（メタデータ） (2024-11-06T20:12:47Z)
• Truly No-Regret Learning in Constrained MDPs [61.78619476991494]
  未知のCMDPで学習するモデルベース原始双対アルゴリズムを提案する。 提案アルゴリズムは,誤差のキャンセルを伴わずにサブ線形後悔を実現する。
  論文  参考訳（メタデータ） (2024-02-24T09:47:46Z)
• Double-Bounded Optimal Transport for Advanced Clustering and Classification [58.237576976486544]
  本稿では,2つの境界内での目標分布の制限を前提としたDB-OT(Douubly bounded Optimal Transport)を提案する。 提案手法は,テスト段階における改良された推論方式により,良好な結果が得られることを示す。
  論文  参考訳（メタデータ） (2024-01-21T07:43:01Z)
• Semi-Oblivious Chase Termination for Linear Existential Rules: An Experimental Study [5.936402320555635]
  チェイス手順は、制約のある推論を可能にする、データベースの基本的なアルゴリズムツールである。 データベースと一連の制約を入力として取り、制約によって決定されたデータベースを反復的に完了します。 しかし、重要な課題は、それが終了しないかもしれないという事実であり、それが与えられたデータベースと一連の制約を終了するかどうかをチェックする問題に繋がる。
  論文  参考訳（メタデータ） (2023-03-22T18:21:01Z)
• Forward LTLf Synthesis: DPLL At Work [1.370633147306388]
  有限トレース(LTLf)上での線形時間論理の合成のための新しいAND-ORグラフ探索フレームワークを提案する。 このようなフレームワーク内では、Davis-Putnam-Logemann-Loveland (DPLL)アルゴリズムにインスパイアされたプロシージャを考案し、次に利用可能なエージェント環境の動きを生成する。 また,状態公式の構文的等価性に基づく探索ノードの等価性チェックも提案する。
  論文  参考訳（メタデータ） (2023-02-27T14:33:50Z)
• Crake: Causal-Enhanced Table-Filler for Question Answering over Large Scale Knowledge Base [11.888045774125787]
  意味解析を2段階に分類する。 第一段階では、シークエンスモデリングの問題を克服し、内部因果関係を学習するための因果拡張テーブルフィラーを提案する。 第2段階では、大規模KB上で複雑なクエリをスケールするための効率的なビーム探索アルゴリズムが提示される。
  論文  参考訳（メタデータ） (2022-07-08T04:21:26Z)
• Understanding Deep Learning via Decision Boundary [81.49114762506287]
  決定境界(DB)の変動が低いニューラルネットワークはより一般化可能であることを示す。 アルゴリズムDBの変数と$(epsilon, eta)$-data DBの変数という2つの新しい概念が、決定境界の変数を測定するために提案されている。
  論文  参考訳（メタデータ） (2022-06-03T11:34:12Z)
• A2Log: Attentive Augmented Log Anomaly Detection [53.06341151551106]
  異常検出は、ITサービスの信頼性とサービス性にとってますます重要になる。 既存の教師なし手法は、適切な決定境界を得るために異常な例を必要とする。 我々は,異常判定と異常判定の2段階からなる教師なし異常検出手法であるA2Logを開発した。
  論文  参考訳（メタデータ） (2021-09-20T13:40:21Z)
• Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Games [102.23975166536326]
  tree-form sequential decision making (tfsdm) は、エージェントと潜在的に敵対的な環境の間のツリー形式の相互作用をモデル化することで、古典的なワンショット意思決定を拡張する。 これは、各プレイヤーが幅広い形式のゲームで直面するオンライン意思決定問題、およびマルコフ決定プロセス、およびエージェントが観測された履歴を条件とする部分観察可能なマルコフ決定プロセスをキャプチャする。 本稿では, (i) 線形時間損失と (ii) $o(sqrtt)$ cumulative regret の両方を提供する拡張dmのバンディット線形最適化問題に対する最初のアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-08T05:00:13Z)
• Characterizing Boundedness in Chase Variants [1.7033055327465234]
  与えられた規則の集合に対する追跡の深さが整数 k で有界かどうかを問う k-有界性問題の決定可能性について検討する。 主な追尾変種は,その特性,すなわち,難読性,半報知性,制限された追尾性,および幅優先バージョンを満足することを示す。
  論文  参考訳（メタデータ） (2020-04-21T14:07:10Z)
• Lagrangian Decomposition for Neural Network Verification [148.0448557991349]
  ニューラルネットワーク検証の基本的なコンポーネントは、出力が取ることのできる値のバウンダリの計算である。 ラグランジアン分解に基づく新しい手法を提案する。 ランニングタイムのごく一部で、既成の解法に匹敵するバウンダリが得られることを示す。
  論文  参考訳（メタデータ） (2020-02-24T17:55:10Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。