論文の概要: How to Approximate Ontology-Mediated Queries

• arxiv url: http://arxiv.org/abs/2107.05369v1
• Date: Mon, 12 Jul 2021 12:29:50 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-13 15:50:25.450077
• Title: How to Approximate Ontology-Mediated Queries
• Title（参考訳）: オントロジーを媒介とするクエリの近似法
• Authors: Anneke Haga and Carsten Lutz and Leif Sabellek and Frank Wolter
• Abstract要約: ALC と ALCI の記述論理に基づいて,オントロジーによるクエリに対する近似のいくつかの概念を紹介し,研究する。 近似式は,(1) オントロジーを ELI や特定の TGD などのトラクタブル言語で定式化された1つに置き換える,(2) ツリー幅が定数で有界なデータベースのクラスのようなトラクタブルクラスの1つに置き換える,の2種類からなる。
• 参考スコア（独自算出の注目度）: 22.99749220980996
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We introduce and study several notions of approximation for ontology-mediated queries based on the description logics ALC and ALCI. Our approximations are of two kinds: we may (1) replace the ontology with one formulated in a tractable ontology language such as ELI or certain TGDs and (2) replace the database with one from a tractable class such as the class of databases whose treewidth is bounded by a constant. We determine the computational complexity and the relative completeness of the resulting approximations. (Almost) all of them reduce the data complexity from coNP-complete to PTime, in some cases even to fixed-parameter tractable and to linear time. While approximations of kind (1) also reduce the combined complexity, this tends to not be the case for approximations of kind (2). In some cases, the combined complexity even increases.
• Abstract（参考訳）: ALC と ALCI の記述論理に基づいて,オントロジーによるクエリに対する近似のいくつかの概念を紹介し,研究する。 近似式は,(1) オントロジーを ELI や特定の TGD などの抽出可能なオントロジー言語で定式化された1つに置き換える,(2) 木幅が定数で有界なデータベースのクラスのような抽出可能なクラスの1つに置き換える,の2種類からなる。 計算の複雑さと結果の近似の相対的完全性を決定する。 ほとんど)これらすべてが、conp完全からptimeへのデータの複雑さを削減します。 種数(1)の近似もまた複合複雑性を減少させるが、これは種数(2)の近似の場合ではない。 場合によっては、統合された複雑さはさらに増加する。

関連論文リスト

• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) は、質問回答(QA)のようなタスクにおける応答精度を高めるための有望なアプローチとして登場した。 本稿では,クエリの複雑さに基づいて,LLMの最適戦略を動的に選択できる適応型QAフレームワークを提案する。 オープンドメインのQAデータセットを用いて、複数のクエリの複雑さを網羅し、QAシステムの全体的な効率性と精度を高めることを示す。
  論文  参考訳（メタデータ） (2024-03-21T13:52:30Z)
• SCAFFLSA: Taming Heterogeneity in Federated Linear Stochastic Approximation and TD Learning [14.663513734368628]
  我々は,FedLSAの通信複雑性が,所望の精度の逆でスケールすることを示した。 重要な発見は、Scaffnewの既存の結果と比較して、サンプルの複雑さはエージェント数の逆でスケールするということである。
  論文  参考訳（メタデータ） (2024-02-06T16:06:59Z)
• The Computational Complexity of Concise Hypersphere Classification [49.57441416941195]
  本稿では,二元データに対する超球分類問題の複雑性理論による最初の研究である。 パラメータ化複雑性のパラダイムを用いて、入力データに存在する可能性のある構造特性の影響を分析する。
  論文  参考訳（メタデータ） (2023-12-12T09:33:03Z)
• Polynomial-Time Solutions for ReLU Network Training: A Complexity Classification via Max-Cut and Zonotopes [70.52097560486683]
  我々は、ReLUネットワークの近似の難しさがマックス・カッツ問題の複雑さを反映しているだけでなく、特定の場合において、それと完全に一致することを証明した。 特に、$epsilonleqsqrt84/83-1approx 0.006$とすると、目的値に関して相対誤差$epsilon$でReLUネットワーク対象の近似グローバルデータセットを見つけることはNPハードであることが示される。
  論文  参考訳（メタデータ） (2023-11-18T04:41:07Z)
• Tractable Bounding of Counterfactual Queries by Knowledge Compilation [51.47174989680976]
  本稿では, パール構造因果モデルにおいて, 因果関係などの部分的特定可能なクエリのバウンダリングの問題について議論する。 最近提案された反復EMスキームは初期化パラメータをサンプリングしてそれらの境界を内部近似する。 シンボルパラメータを実際の値に置き換えた回路構造を,単一のシンボル知識コンパイルによって得られることを示す。
  論文  参考訳（メタデータ） (2023-10-05T07:10:40Z)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
  論文  参考訳（メタデータ） (2021-04-18T07:46:28Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  近似問題に対する勾配に基づく手法のオラクル複雑性について検討する。 最悪のケースの複雑さではなく、インスタンス依存の複雑さに焦点を当てます。 提案アルゴリズムとその解析はモーメント推定の成功を理論的に正当化する。
  論文  参考訳（メタデータ） (2020-06-08T09:25:47Z)
• A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
  我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。 我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。 一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
  論文  参考訳（メタデータ） (2020-06-07T14:47:07Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)
• Sparse Generalized Canonical Correlation Analysis: Distributed Alternating Iteration based Approach [18.93565942407577]
  Sparse Canonical correlation analysis (CCA) はスパース構造を用いた潜伏情報検出に有用な統計ツールである。 本稿では,多視点データとスパース構造との潜在関係を検出可能な一般標準相関解析(GCCA)を提案する。
  論文  参考訳（メタデータ） (2020-04-23T05:53:48Z)
• When is Ontology-Mediated Querying Efficient? [10.971122842236024]
  関係データベース上でのオントロジーによるクエリの評価について検討する。 OMQ のクラスの特徴として,複雑な組み合わせによるトラクタブルなクラスを提供しています。 また、与えられた OMQ が有界木幅の OMQ に等しいかどうかを決定する複雑さについても検討する。
  論文  参考訳（メタデータ） (2020-03-17T16:32:00Z)

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

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