論文の概要: Fitting Description Logic Ontologies to ABox and Query Examples
- arxiv url: http://arxiv.org/abs/2508.08007v1
- Date: Mon, 11 Aug 2025 14:11:27 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-08-12 21:23:29.135805
- Title: Fitting Description Logic Ontologies to ABox and Query Examples
- Title（参考訳）: ABoxとクエリの例に記述論理オントロジーを適用する
- Authors: Maurice Funk, Marvin Grosser, Carsten Lutz,
- Abstract要約: 記述ロジックは$mathcalALC$と$mathcalALCI$をオントロジー言語と様々なクエリ言語とみなす。
得られた全ての適合問題に対して、有効な特徴付けを提供し、適合オントロジーが存在するかどうかを決定するための計算複雑性を決定する。
この問題は、AQとフルCQには$ Small CONP$、CQとUCQには$2E Small XPTsmall IME$-completeであることが判明した。
- 参考スコア（独自算出の注目度）: 9.25388936622029
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a fitting problem inspired by ontology-mediated querying: given a collection of positive and negative examples of the form $(\mathcal{A},q)$ with $\mathcal{A}$ an ABox and $q$ a Boolean query, we seek an ontology $\mathcal{O}$ that satisfies $\mathcal{A} \cup \mathcal{O} \vDash q$ for all positive examples and $\mathcal{A} \cup \mathcal{O}\not\vDash q$ for all negative examples. We consider the description logics $\mathcal{ALC}$ and $\mathcal{ALCI}$ as ontology languages and a range of query languages that includes atomic queries (AQs), conjunctive queries (CQs), and unions thereof (UCQs). For all of the resulting fitting problems, we provide effective characterizations and determine the computational complexity of deciding whether a fitting ontology exists. This problem turns out to be ${\small CO}NP$ for AQs and full CQs and $2E{\small XP}T{\small IME}$-complete for CQs and UCQs. These results hold for both $\mathcal{ALC}$ and $\mathcal{ALCI}$.
- Abstract（参考訳）: オントロジーを媒介とするクエリに着想を得た適合問題を研究する: $(\mathcal{A},q)$ with $\mathcal{A}$ an ABox and $q$ a Boolean query, we seek a ontology $\mathcal{O}$ that satisfies $\mathcal{A} \cup \mathcal{O} \vDash q$ for all positive example and $\mathcal{A} \cup \mathcal{O}\not\vDash q$ for all negative example。
我々は、オントロジー言語として$\mathcal{ALC}$と$\mathcal{ALCI}$と、原子クエリ(AQ)、結合クエリ(CQ)、それらの結合(UCQ)を含む様々なクエリ言語について考察する。
得られた全ての適合問題に対して、有効な特徴付けを提供し、適合オントロジーが存在するかどうかを決定するための計算複雑性を決定する。
この問題は、AQ と完全 CQ に対して${\small CO}NP$、CQ と UCQ に対して $2E{\small XP}T{\small IME}$-complete であることが判明した。
これらの結果は $\mathcal{ALC}$ と $\mathcal{ALCI}$ の両方に対して成り立つ。
関連論文リスト
- Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。
クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。
このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
論文 参考訳（メタデータ） (2026-01-07T22:07:44Z) - PREM: Privately Answering Statistical Queries with Relative Error [91.98332694700046]
合成データを生成する新しいフレームワークである$mathsfPREM$(Private Relative Error Multiplicative weight update)を紹介します。
我々はアルゴリズムをほぼ一致する下界で補完する。
論文 参考訳（メタデータ） (2025-02-20T18:32:02Z) - CSPs with Few Alien Constraints [12.330326247154968]
CSP$(mathcalA cup mathcalB)$ ここで$mathcalA$は構造、$mathcalB$は異方構造である。
我々は、以前分類の試みを免れたいくつかのよく研究された問題に対して、接続を確立し、転送可能な複雑性結果を得る。
論文 参考訳（メタデータ） (2024-08-23T08:34:13Z) - Quantum Sabotage Complexity [0.7812210699650152]
ここでは$mathsfQ(f_mathsfsab)$を示し、$f_mathsfsab$の量子クエリ複雑性を示す。
f$がインデックス関数であるとき、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsfsab)$は、$mathsfQ(f_mathsfsab)=Theta(sqrtmathsf)の可能性を除外する。
論文 参考訳（メタデータ） (2024-08-22T17:57:58Z) - Statistical Query Lower Bounds for Learning Truncated Gaussians [43.452452030671694]
この問題のSQアルゴリズムの複雑さは、$dmathrmpoly (1/epsilon)$であり、クラス$mathcalC$が単純である場合でも、$mathrmpoly(d/epsilon)が情報理論的に十分であることを示す。
論文 参考訳（メタデータ） (2024-03-04T18:30:33Z) - SQ Lower Bounds for Learning Bounded Covariance GMMs [46.289382906761304]
P= sum_i=1k w_i MathcalN(boldsymbol mu_i,mathbf Sigma_i)$ という形で、分離されたガウスの混合を $mathbbRd$ で学習することに焦点を当てる。
この問題に対する統計的クエリ(SQ)アルゴリズムは、少なくともdOmega (1/epsilon)$の複雑さを必要とすることを証明している。
論文 参考訳（メタデータ） (2023-06-22T17:23:36Z) - A Fast Algorithm for the Real-Valued Combinatorial Pure Exploration of Multi-Armed Bandit [55.2480439325792]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
本稿では,差分に基づく探索法 (CombGapE) アルゴリズムを提案する。
我々は,CombGapEアルゴリズムが,合成データセットと実世界のデータセットの両方において,既存の手法を大幅に上回っていることを数値的に示す。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - A Note on Target Q-learning For Solving Finite MDPs with A Generative
Oracle [11.154257789731467]
We show that the sample complexity of the target Q-learning algorithm in [Lee and He, 2020] is $widetildemathcal O(|mathcal S|2|mathcal A|2 (1-gamma)-5varepsilon-2)$。
バニラQ-ラーニングと比較すると、周期的に凍結したターゲットQ-関数の導入は、サンプルの複雑さを犠牲にしない。
論文 参考訳（メタデータ） (2022-03-22T06:53:42Z) - Low-degree learning and the metric entropy of polynomials [44.99833362998488]
少なくとも$Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon)は2辺の推定値$c(1-varepsilon)2dlogを満たす。
論文 参考訳（メタデータ） (2022-03-17T23:52:08Z) - Linear Bandits on Uniformly Convex Sets [88.3673525964507]
線形バンディットアルゴリズムはコンパクト凸作用集合上の $tildemathcalo(nsqrtt)$ pseudo-regret 境界を与える。
2種類の構造的仮定は、より良い擬似回帰境界をもたらす。
論文 参考訳（メタデータ） (2021-03-10T07:33:03Z) - StoqMA meets distribution testing [0.0]
We provide a novel connection between $mathsfStoqMA$ and distribution testing via reversible circuits。
いずれの変種も$mathsfStoqMA$は、任意の無作為な乱数ビットと完全音性を持たず、$mathsfNP$に含まれることを示す。
我々の結果は、$mathsfMA subseteq mathsfStoqMA subseteq mathsfSBP$ [BBT06]という階層構造を崩壊させる一歩を踏み出した。
論文 参考訳（メタデータ） (2020-11-11T12:30:42Z) - Proving Non-Inclusion of B\"uchi Automata based on Monte Carlo Sampling [19.09848789158933]
B"uchiautoa non-inclusion $mathcalL(mathcalA) notsubseteq mathcalL(mathcalB)$を証明するための具体的なアルゴリズムを提案する。
$mathsfIMC2$は、B"uchiautoaのインクルージョンに対する反例を見つける高速で信頼性の高い方法である。
論文 参考訳（メタデータ） (2020-07-05T10:17:02Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。