Fugu-MT 論文翻訳(概要): On the non-efficient PAC learnability of acyclic conjunctive queries

論文の概要: On the non-efficient PAC learnability of acyclic conjunctive queries

arxiv url: http://arxiv.org/abs/2208.10255v1
Date: Mon, 22 Aug 2022 12:29:02 GMT
ステータス: 処理完了
システム内更新日: 2022-08-23 12:47:57.824704
Title: On the non-efficient PAC learnability of acyclic conjunctive queries
Title（参考訳）: 非巡回共役クエリの非効率PAC学習性について
Authors: Balder ten Cate, Maurice Funk, Jean Christoph Jung, Carsten Lutz
Abstract要約: 本稿では,確率サイズフィッティング(PAC)モデルにおいて,接続型クエリが効率よく学習できないという事実を,自己完結型で表現する。我々は、多くの制限された接続型クエリ(CQ)に適用される強力な負のPAC学習性結果を確立する。我々は,CQ がメンバシップクエリで効率的に学習可能であることを示す。
参考スコア（独自算出の注目度）: 18.851061569487616
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: This note serves three purposes: (i) we provide a self-contained exposition of the fact that conjunctive queries are not efficiently learnable in the Probably-Approximately-Correct (PAC) model, paying clear attention to the complicating fact that this concept class lacks the polynomial-size fitting property, a property that is tacitly assumed in much of the computational learning theory literature; (ii) we establish a strong negative PAC learnability result that applies to many restricted classes of conjunctive queries (CQs), including acyclic CQs for a wide range of notions of "acyclicity"; (iii) we show that CQs are efficiently PAC learnable with membership queries.
Abstract（参考訳）: このメモは3つの目的を果たす。 (i)この概念クラスが多項式サイズの適合性に欠けており、これは計算学習理論の文献の多くで暗黙的に想定されている性質である、という複雑な事実に注意を払いながら、結合的問合せがおそらくは正しい(pac)モデルでは効率的に学習できないという事実を自己完結した表現を提供する。二) 連結クエリ(cqs)の多くの制限されたクラスに適用できる強い負のpac学習可能性(「非循環性」の幅広い概念に対する非循環的cqsを含む。)を確立する。 3) CQは, メンバーシップクエリで効率よくPACを学習可能であることを示す。

関連論文リスト

Controlled Query Evaluation through Epistemic Dependencies [7.502796412126707]
本稿では,このフレームワークの表現能力を示し,CQEの(一対の)結合クエリにおけるデータ複雑性について検討する。本稿では,非循環的依存関係の場合のトラクタビリティを,適切なクエリアルゴリズムを提供することにより証明する。
論文参考訳（メタデータ） (2024-05-03T19:48:07Z)
Answering from Sure to Uncertain: Uncertainty-Aware Curriculum Learning for Video Question Answering [63.12469700986452]
不確実性を考慮したカリキュラム学習(CL)の概念を導入する。ここで不確実性は、困難を動的に調整するための指針となる。実際に、我々は、ビデオQAモデルを我々のフレームワークにシームレスに統合し、包括的な実験を行う。
論文参考訳（メタデータ） (2024-01-03T02:29:34Z)
Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
論文参考訳（メタデータ） (2023-07-02T19:26:58Z)
Querying Circumscribed Description Logic Knowledge Bases [9.526604375441073]
循環は非単調な記述論理を定義する主要なアプローチの1つである。本研究は, (U)CQ 評価における DL KB の判定可能性を示す。また、より単純な原子クエリ(AQ)についても研究する。
論文参考訳（メタデータ） (2023-06-07T15:50:15Z)
PACIFIC: Towards Proactive Conversational Question Answering over Tabular and Textual Data in Finance [96.06505049126345]
我々はPACIFICという新しいデータセットを提案する。既存のCQAデータセットと比較すると、PACIFICは(i)活動性、(ii)数値推論、(iii)表とテキストのハイブリッドコンテキストの3つの重要な特徴を示す。質問生成とCQAを組み合わせたPCQA(Proactive Conversational Question Answering)に基づいて,新しいタスクを定義する。 UniPCQAはPCQAのすべてのサブタスク上でマルチタスク学習を行い、Seeq2Seqの上位$kのサンプルをクロスバリデーションすることで、マルチタスク学習におけるエラー伝搬問題を緩和するための単純なアンサンブル戦略を取り入れている。
論文参考訳（メタデータ） (2022-10-17T08:06:56Z)
Efficient Knowledge Compilation Beyond Weighted Model Counting [7.828647825246474]
このような問題に対する一般的なフレームワークとして,第2レベル代数モデルカウント (2AMC) を導入している。 KC(Knowledge Compilation)に基づく第1レベルのテクニックは、変数順序制約を課すことで、特定の2AMCインスタンスに適応している。 2AMC問題の論理構造を利用して、これらの制約の一部を省略し、負の効果を制限できることが示される。
論文参考訳（メタデータ） (2022-05-16T08:10:40Z)
Finite Entailment of UCRPQs over ALC Ontologies [0.82179684645881]
我々は、クエリ言語、結合正則経路クエリの結合(UCRPQ)を考える。記述論理 ALC を用いて,UCRPQ の包含のための厳密な 2EXP バウンドを示す。入力オートマトンの背後にある決定論的有限オートマトンによって誘導される解釈の階層化を導入する新しいオートマトンベースの技術がある。
論文参考訳（メタデータ） (2022-04-29T17:38:13Z)
Actively Learning Concepts and Conjunctive Queries under ELr-Ontologies [22.218000867486726]
EL概念はELIオントロジーの存在下では学習できないことを示す。また,EL概念はELIオントロジーの存在下では学習できないことを示す。
論文参考訳（メタデータ） (2021-05-18T07:45:37Z)
Counterfactual Variable Control for Robust and Interpretable Question Answering [57.25261576239862]
ディープニューラルネットワークに基づく質問応答(QA)モデルは、多くの場合、堅牢でも説明もできない。本稿では、因果推論を用いてQAモデルのこのような突発的な「能力」を検証する。本稿では,任意のショートカット相関を明示的に緩和する,CVC(Counterfactual Variable Control)という新しい手法を提案する。
論文参考訳（メタデータ） (2020-10-12T10:09:05Z)
Joint Contrastive Learning with Infinite Possibilities [114.45811348666898]
本稿では,新しい確率論的モデリングによるコントラスト学習における最近の発展の有用性について考察する。コントラスト学習(Joint Contrastive Learning, JCL)という,コントラスト学習の特定の形態を導出する。
論文参考訳（メタデータ） (2020-09-30T16:24:21Z)
Probably Approximately Correct Constrained Learning [135.48447120228658]
我々は、ほぼ正しい学習フレームワーク(PAC)に基づく一般化理論を開発する。 PAC学習可能なクラスも制約のある学習者であるという意味では,学習者の導入は学習問題を難しくするものではないことを示す。このソリューションの特性を分析し,制約付き学習が公平でロバストな分類における問題にどのように対処できるかを説明する。
論文参考訳（メタデータ） (2020-06-09T19:59:29Z)

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