論文の概要: Extending Sticky-Datalog+/- via Finite-Position Selection Functions:
Tractability, Algorithms, and Optimization
- arxiv url: http://arxiv.org/abs/2108.00903v2
- Date: Tue, 3 Aug 2021 02:52:18 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-04 09:17:31.460837
- Title: Extending Sticky-Datalog+/- via Finite-Position Selection Functions:
Tractability, Algorithms, and Optimization
- Title(参考訳): 有限ポジション選択関数によるSticky-Datalog+/-の拡張:トラクタビリティ、アルゴリズム、最適化
- Authors: Leopoldo Bertossi, Mostafa Milani
- Abstract要約: 我々は,追跡手順の動作の観点から,Sticky と WS プログラムについて検討する。
クラスsch(S)におけるプログラムに対するボトムアップQAアルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 3.4621178017146543
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Weakly-Sticky(WS) Datalog+/- is an expressive member of the family of
Datalog+/- program classes that is defined on the basis of the conditions of
stickiness and weak-acyclicity. Conjunctive query answering (QA) over the WS
programs has been investigated, and its tractability in data complexity has
been established. However, the design and implementation of practical QA
algorithms and their optimizations have been open. In order to fill this gap,
we first study Sticky and WS programs from the point of view of the behavior of
the chase procedure. We extend the stickiness property of the chase to that of
generalized stickiness of the chase (GSCh) modulo an oracle that selects (and
provides) the predicate positions where finitely values appear during the
chase. Stickiness modulo a selection function S that provides only a subset of
those positions defines sch(S), a semantic subclass of GSCh. Program classes
with selection functions include Sticky and WS, and another syntactic class
that we introduce and characterize, namely JWS, of jointly-weakly-sticky
programs, which contains WS. The selection functions for these last three
classes are computable, and no external, possibly non-computable oracle is
needed. We propose a bottom-up QA algorithm for programs in the class sch(S),
for a general selection function S. As a particular case, we obtain a
polynomial-time QA algorithm for JWS and weakly-sticky programs. Unlike WS, JWS
turns out to be closed under magic-sets query optimization. As a consequence,
both the generic polynomial-time QA algorithm and its magic-set optimization
can be particularized and applied to WS.
- Abstract(参考訳): weakly-sticky(ws) datalog+/-は、粘着性と非循環性の条件に基づいて定義されるdatalog+/-プログラムクラスの表現力のあるメンバーである。
WS プログラム上での接続型クエリ応答 (QA) について検討し,データ複雑性のトラクタビリティを確立した。
しかし,実効的なQAアルゴリズムの設計と実装とその最適化は未完成である。
このギャップを埋めるために、私たちはまず、追跡手順の振る舞いの観点から、StickyとWSプログラムを研究します。
我々は、チェイスのスティッキネス特性を、チェイス中に有限の値が現れる述語位置を選択する(そして提供する)オラクルの一般化されたスティッキネス(gsch)モジュロに拡張する。
これらの位置のサブセットのみを提供する選択関数 S の粘度変調は、GSCh のセマンティックサブクラス sch(S) を定義する。
選択関数を持つプログラムクラスには、Sticky と WS と、WS を含むジョイント弱スティックプログラムの導入と特徴付けを行う別の構文クラス、すなわち JWS がある。
これら3つのクラスの選択関数は計算可能であり、外部の計算不可能なオラクルは必要ない。
本稿では,一般選択関数 s に対するクラス sch(s) におけるプログラムのボトムアップ qa アルゴリズムを提案する。
WSと異なり、JWSはマジックセットのクエリ最適化の下でクローズされている。
その結果、一般的な多項式時間QAアルゴリズムとマジックセット最適化の両方を具体化し、WSに適用することができる。
関連論文リスト
- Graph-Based Automatic Feature Selection for Multi-Class Classification
via Mean Simplified Silhouette [4.786337974720721]
本稿では,自動特徴選択のためのグラフベースの新しいフィルタ手法を提案する(略してGB-AFS)。
予測性能を維持するために必要な特徴の最小の組み合わせを決定する。
選択する機能の数など、ユーザ定義パラメータを一切必要としない。
論文 参考訳(メタデータ) (2023-09-05T14:37:31Z) - SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
本研究では,大規模言語モデル (LLM) の推論能力を向上させるために,新しい満足度支援言語モデリング (SatLM) 手法を提案する。
我々はLLMを用いて命令型プログラムではなく宣言型タスク仕様を生成し、既製の自動定理証明器を利用して最終解を導出する。
我々はSATLMを8つの異なるデータセット上で評価し、命令パラダイムにおいてプログラム支援されたLMよりも一貫して優れていることを示す。
論文 参考訳(メタデータ) (2023-05-16T17:55:51Z) - An Algorithm and Complexity Results for Causal Unit Selection [16.307996243413967]
単位選択問題は、刺激を受ける際に望ましい振る舞いを示す可能性が最も高い、単位と呼ばれる物体を特定することを目的としている。
本稿では,幅広い因果的目的関数のクラスと完全に定義された構造因果的モデルに与えられた最適単位を求めるための,最初の正確なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-28T08:46:51Z) - Explainable Model-specific Algorithm Selection for Multi-Label
Classification [6.442438468509492]
MLC(Multi-label classification)は、データインスタンスが同時に複数のクラスに属すことができる予測モデリングのMLタスクである。
いくつかのMLCアルゴリズムが文献で提案されており、メタ最適化の問題を引き起こしている。
本研究では,データセットの特性を利用した自動アプローチの品質について検討する。
論文 参考訳(メタデータ) (2022-11-21T07:42:11Z) - Multi-Task Option Learning and Discovery for Stochastic Path Planning [27.384742641275228]
本稿では,長距離経路計画問題の幅広いクラスを確実かつ効率的に解決する問題に対処する。
提案手法では,提案したオプションを構成する高レベルパスだけでなく,ポリシによる有用なオプションも計算する。
このアプローチが実行可能性と解決可能性の強い保証をもたらすことを示す。
論文 参考訳(メタデータ) (2022-09-30T19:57:52Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳(メタデータ) (2020-02-26T16:19:09Z) - Conditional Self-Attention for Query-based Summarization [49.616774159367516]
条件依存モデリング用に設計されたニューラルネットワークモジュールであるテキスト条件自己アテンション(CSA)を提案する。
DebatepediaとHotpotQAベンチマークデータセットの実験は、CSAがバニラトランスフォーマーを一貫して上回っていることを示している。
論文 参考訳(メタデータ) (2020-02-18T02:22:31Z) - Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
我々は,数千の候補アルゴリズムの固定セットを考慮に入れた,極端なアルゴリズム選択(XAS)の設定を提案する。
我々は、XAS設定に対する最先端のAS技術の適用性を評価し、Dyadic特徴表現を利用したアプローチを提案する。
論文 参考訳(メタデータ) (2020-01-29T09:40:58Z) - Multi-layer Optimizations for End-to-End Data Analytics [71.05611866288196]
代替アプローチを実現するフレームワークであるIFAQ(Iterative Functional Aggregate Queries)を紹介する。
IFAQは、特徴抽出クエリと学習タスクを、IFAQのドメイン固有言語で与えられた1つのプログラムとして扱う。
IFAQ の Scala 実装が mlpack,Scikit,特殊化を数桁で上回り,線形回帰木モデルや回帰木モデルを複数の関係データセット上で処理可能であることを示す。
論文 参考訳(メタデータ) (2020-01-10T16:14:44Z) - Options of Interest: Temporal Abstraction with Interest Functions [58.30081828754683]
一般関数近似に適した開始集合の一般化を、オプションに関連付けられた興味関数を定義することによって提供する。
我々は、関心関数に対する勾配に基づく学習アルゴリズムを導出し、新たな関心選択批判的アーキテクチャを創出する。
論文 参考訳(メタデータ) (2020-01-01T21:24:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。