論文の概要: Spectra of Cardinality Queries over Description Logic Knowledge Bases
- arxiv url: http://arxiv.org/abs/2412.12929v1
- Date: Tue, 17 Dec 2024 14:07:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-18 13:57:12.513765
- Title: Spectra of Cardinality Queries over Description Logic Knowledge Bases
- Title（参考訳）: 記述論理知識に基づく心的問い合わせのスペクトル
- Authors: Quentin Manière, Marcin Przybyłko,
- Abstract要約: スペクトルを効果的に表現できるクエリをカウントするクラスを同定する。
有限モデル推論に用いる構造を洗練し,Hornフラグメントのサイクル回帰技術に依存する。
- 参考スコア（独自算出の注目度）: 1.9336815376402723
- License:
- Abstract: Recent works have explored the use of counting queries coupled with Description Logic ontologies. The answer to such a query in a model of a knowledge base is either an integer or $\infty$, and its spectrum is the set of its answers over all models. While it is unclear how to compute and manipulate such a set in general, we identify a class of counting queries whose spectra can be effectively represented. Focusing on atomic counting queries, we pinpoint the possible shapes of a spectrum over $\mathcal{ALCIF}$ ontologies: they are essentially the subsets of $\mathbb{N} \cup \{ \infty \}$ closed under addition. For most sublogics of $\mathcal{ALCIF}$, we show that possible spectra enjoy simpler shapes, being $[ m, \infty ]$ or variations thereof. To obtain our results, we refine constructions used for finite model reasoning and notably rely on a cycle-reversion technique for the Horn fragment of $\mathcal{ALCIF}$. We also study the data complexity of computing the proposed effective representation and establish the $\mathsf{FP}^{\mathsf{NP}[\log]}$-completeness of this task under several settings.
- Abstract（参考訳）: 最近の研究は、記述論理オントロジーと結合したクエリのカウントの利用について検討している。
知識ベースモデルにおけるそのようなクエリに対する答えは整数か$\infty$のいずれかであり、そのスペクトルはすべてのモデルに対するその答えの集合である。
このような集合を一般にどのように計算し、操作するかは定かではないが、スペクトルを効果的に表現できるクエリをカウントするクラスを同定する。
原子カウントクエリに着目して、$\mathcal{ALCIF}$オントロジー上のスペクトルの可能な形状をピンポイントする:それらは本質的に、$\mathbb{N} \cup \{ \infty \}$ の閉部分集合である。
$\mathcal{ALCIF}$ のほとんどの部分論において、可能なスペクトルはより単純な形を楽しみ、$[m, \infty ]$ またはその変種であることを示す。
この結果を得るために、有限モデル推論に使用される構造を洗練し、特に$\mathcal{ALCIF}$のホーンフラグメントのサイクル回帰技術に依存する。
また、提案した有効表現の計算の複雑さについて検討し、いくつかの設定で$\mathsf{FP}^{\mathsf{NP}[\log]}$完全性を確立する。
関連論文リスト
- Robust Learning of Multi-index Models via Iterative Subspace Approximation [36.138661719725626]
ガウス分布下でラベルノイズを伴うマルチインデックスモデル(MIM)の学習課題について検討する。
一定の正則性特性を満たす有限範囲の良好なMIMに着目する。
ランダムな分類ノイズが存在する場合、我々のアルゴリズムの複雑さは1/epsilon$と不可知的にスケールする。
論文 参考訳（メタデータ） (2025-02-13T17:37:42Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳（メタデータ） (2024-08-27T18:28:31Z) - CSPs with Few Alien Constraints [12.330326247154968]
CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。
我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
論文 参考訳（メタデータ） (2024-08-23T08:34:13Z) - An in-depth study of the power function $x^{q+2}$ over the finite field $\mathbb{F}_{q^2}$: the differential, boomerang, and Walsh spectra, with an application to coding theory [28.489574654566677]
有限体 $mathbbF_q2$ は$q2$ 要素からなる。
まず、いくつかの重要な単純化を取り入れた電力関数 $f(x) = xq+2$ on $mathbbF_q2$ の微分スペクトルを決定する方法を提案する。
論文 参考訳（メタデータ） (2024-07-08T14:01:06Z) - A Theory of Interpretable Approximations [61.90216959710842]
我々は、ある基底クラス $mathcalH$ の概念の小さな集合によってターゲット概念 $c$ を近似するという考え方を研究する。
任意の$mathcalH$と$c$のペアに対して、これらのケースのちょうど1つが成り立つ: (i) $c$を任意の精度で$mathcalH$で近似することはできない。
解釈可能な近似の場合、近似の複雑さに関するわずかに非自明なa-priori保証でさえ、定数(分布自由かつ精度)の近似を意味することを示す。
論文 参考訳（メタデータ） (2024-06-15T06:43:45Z) - Agnostically Learning Multi-index Models with Queries [54.290489524576756]
本稿では,ガウス分布下での非依存学習の課題に対するクエリアクセスのパワーについて検討する。
クエリアクセスは、MIMを不可知的に学習するためのランダムな例よりも大幅に改善されていることを示す。
論文 参考訳（メタデータ） (2023-12-27T15:50:47Z) - Gapped Clique Homology on weighted graphs is $\text{QMA}_1$-hard and contained in $\text{QMA}$ [0.0]
計算トポロジにおける古典問題の複雑性, ホモロジー問題について検討する。
複雑性は量子複雑性クラスによって特徴づけられる。
我々の結果は、ホモロジーと超対称量子力学の結びつきの側面と見なすことができる。
論文 参考訳（メタデータ） (2023-11-28T21:15:30Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Learning Finite Linear Temporal Logic Specifications with a Specialized
Neural Operator [0.0]
本稿では,システム動作のラベル付きトレースから,コンパクトな$mathsfLTL_f$式を学習する問題に対処する。
提案手法は, 時間演算子$mathsfLTL_f$をサブスクライブする特殊リカレントフィルタを含む。
ランダムに生成された$mathsfLTL_f$式の実験は、既存の手法よりも大きな公式サイズにスケールしたNeural$mathsfLTL_f$を示す。
論文 参考訳（メタデータ） (2021-11-07T18:51:02Z) - Average-case Complexity of Teaching Convex Polytopes via Halfspace
Queries [55.28642461328172]
平均的なケースの教えの複雑さは$Theta(d)$であり、最悪のケースの教えの複雑さは$Theta(n)$とは対照的である。
我々の洞察は、$phi$-separable dichotomiesの平均ケースの複雑さに厳密な拘束力を確立することを可能にする。
論文 参考訳（メタデータ） (2020-06-25T19:59:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。