Fugu-MT 論文翻訳(概要): On the Complexity of Inductively Learning Guarded Rules

論文の概要: On the Complexity of Inductively Learning Guarded Rules

arxiv url: http://arxiv.org/abs/2110.03624v1
Date: Thu, 7 Oct 2021 17:07:28 GMT
ステータス: 処理完了
システム内更新日: 2021-10-08 15:32:16.535562
Title: On the Complexity of Inductively Learning Guarded Rules
Title（参考訳）: 誘導学習型ルールの複雑さについて
Authors: Andrei Draghici, Georg Gottlob, Matthias Lanzinger
Abstract要約: 学習ガード付き節はNP完全であり,Horn階層上の学習節のP$完全タスクより1ステップ下にあることを示す。大規模データセットの実践的な応用によって、我々は問題の自然な抽出可能な断片を特定できる。
参考スコア（独自算出の注目度）: 7.99255035557979
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We investigate the computational complexity of mining guarded clauses from clausal datasets through the framework of inductive logic programming (ILP). We show that learning guarded clauses is NP-complete and thus one step below the $\sigma^P_2$-complete task of learning Horn clauses on the polynomial hierarchy. Motivated by practical applications on large datasets we identify a natural tractable fragment of the problem. Finally, we also generalise all of our results to $k$-guarded clauses for constant $k$.
Abstract（参考訳）: 本稿では,帰納的論理プログラミング(ILP)の枠組みを用いて,分類データセットから保護された節を抽出する際の計算複雑性について検討する。学習ガード付き節はNP完全であり、多項式階層上のホーン節を学習する$\sigma^P_2$-completeタスクより1ステップ下にあることを示す。大規模データセットの実践的な応用によって、我々は問題の自然な抽出可能な断片を特定できる。最後に、すべての結果を、定数$k$に対する$k$-guarded節に一般化します。

関連論文リスト

Data Complexity in Expressive Description Logics With Path Expressions [7.832189413179361]
本稿では,表現的記述論理ZOIQ(ALCHb Self reg OIQ)の準フォレスト上でのデータ複雑性について検討する。これにより、ZOIQの決定可能なフラグメントに対するデータ複雑性の展望が完成し、OWL2(SRファミリー)の決定可能なフラグメントに関する既知の結果が改善される。
論文参考訳（メタデータ） (2024-06-11T09:37:51Z)
When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
論文参考訳（メタデータ） (2023-08-29T17:22:39Z)
Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文参考訳（メタデータ） (2023-01-30T17:26:39Z)
The Complexity of Learning Linear Temporal Formulas from Examples [2.766648389933265]
我々は断片化のための近似アルゴリズムを構築し、硬度結果の証明を行う。特に、次の演算子と接続子のみを含むフラグメントの近似の厳密な境界を求め、多くのフラグメントに対してNP完全性を示す。
論文参考訳（メタデータ） (2021-02-01T14:34:46Z)
Learning Implicitly with Noisy Data in Linear Arithmetic [94.66549436482306]
PAC-セマンティックスにおける暗黙学習を拡張し、線形算術の言語における間隔としきい値の不確実性を扱う。最適線形プログラミング対象制約の学習に対する我々の暗黙的アプローチは、実際的な明示的アプローチよりも著しく優れていることを示す。
論文参考訳（メタデータ） (2020-10-23T19:08:46Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)
Strong Generalization and Efficiency in Neural Programs [69.18742158883869]
本稿では,ニューラルプログラム誘導の枠組みを強く一般化する効率的なアルゴリズムを学習する問題について検討する。ニューラルネットワークの入力/出力インターフェースを慎重に設計し、模倣することで、任意の入力サイズに対して正しい結果を生成するモデルを学ぶことができる。
論文参考訳（メタデータ） (2020-07-07T17:03:02Z)
Sample-Efficient Reinforcement Learning of Undercomplete POMDPs [91.40308354344505]
この研究は、これらの硬度障壁が、部分観測可能決定過程(POMDP)の豊かで興味深いサブクラスに対する効率的な強化学習を妨げないことを示している。提案手法は, 観測回数が潜伏状態の数よりも大きく, 探索が学習に不可欠であり, 先行研究と区別できるような, エピソード有限不完全POMDPに対するサンプル効率アルゴリズムOOM-UCBを提案する。
論文参考訳（メタデータ） (2020-06-22T17:58:54Z)
A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文参考訳（メタデータ） (2020-06-07T14:47:07Z)
Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
論文参考訳（メタデータ） (2020-01-13T13:16:13Z)

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