論文の概要: Learning Concepts Definable in First-Order Logic with Counting
- arxiv url: http://arxiv.org/abs/1909.03820v2
- Date: Sat, 23 Mar 2024 22:14:50 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-27 06:12:57.578879
- Title: Learning Concepts Definable in First-Order Logic with Counting
- Title（参考訳）: カウントを考慮した一階述語論理で定義可能な学習概念
- Authors: Steffen van Bergerem,
- Abstract要約: 次数構造のクラス上の FOCN は、線形時間で一貫した学習が可能であることを示す。
任意の定数$c$に対して少なくとも$(log log n)c$の次数の構造のクラスについて、ほぼ正しい(PAC)学習に拡張する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study Boolean classification problems over relational background structures in the logical framework introduced by Grohe and Tur\'an (TOCS 2004). It is known (Grohe and Ritzert, LICS 2017) that classifiers definable in first-order logic over structures of polylogarithmic degree can be learned in sublinear time, where the degree of the structure and the running time are measured in terms of the size of the structure. We generalise the results to the first-order logic with counting FOCN, which was introduced by Kuske and Schweikardt (LICS 2017) as an expressive logic generalising various other counting logics. Specifically, we prove that classifiers definable in FOCN over classes of structures of polylogarithmic degree can be consistently learned in sublinear time. This can be seen as a first step towards extending the learning framework to include numerical aspects of machine learning. We extend the result to agnostic probably approximately correct (PAC) learning for classes of structures of degree at most $(\log \log n)^c$ for some constant $c$. Moreover, we show that bounding the degree is crucial to obtain sublinear-time learning algorithms. That is, we prove that, for structures of unbounded degree, learning is not possible in sublinear time, even for classifiers definable in plain first-order logic.
- Abstract（参考訳）: 本稿では,Grohe と Tur\an (TOCS 2004) が導入した論理フレームワークにおける関係背景構造に対するブール分類問題について検討する。
Grohe and Ritzert, LICS 2017) は、多対数次数の構造上の一階述語論理で定義可能な分類器は、構造と実行時間の度合いをその構造の大きさの点で測るサブ線形時間で学べることが知られている。
FOCNは Kuske と Schweikardt (licS 2017) によって導入されたもので、様々な数え上げ論理を一般化した表現論理である。
具体的には,FOCNで定義可能な分類器が,線形時間で連続的に学習できることを証明した。
これは、機械学習の数値的な側面を含むように学習フレームワークを拡張するための第一歩と見なすことができる。
結果は、ある定数$c$に対して少なくとも$(\log \log n)^c$の次数の構造のクラスについて、ほぼ正しい(PAC)学習にまで拡張する。
さらに,次数境界は線形時間学習アルゴリズムの獲得に不可欠であることを示す。
すなわち,非有界次数構造では,一階述語論理で定義可能な分類器であっても,サブ線形時間では学習が不可能であることを示す。
関連論文リスト
- Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
形式言語理論は、特に認識者に関するものである。
代わりに、非公式な意味でのみ類似したプロキシタスクを使用するのが一般的である。
ニューラルネットワークを文字列のバイナリ分類器として直接訓練し評価することで、このミスマッチを補正する。
論文 参考訳（メタデータ） (2024-11-11T16:33:25Z) - Simulating Petri nets with Boolean Matrix Logic Programming [4.762323642506732]
本稿では,ハイレベルなシンボル操作の限界に対処する新しい手法を提案する。
本フレームワークでは,基本ネットとして知られるペトリネットのクラスに対して,2つの新しいBMLPアルゴリズムを提案する。
BMLPアルゴリズムは,表付きB-Prolog,SWI-Prolog,XSB-Prolog,Clingoの40倍の速度でこれらのプログラムを評価できることを示す。
論文 参考訳（メタデータ） (2024-05-18T23:17:00Z) - Improving Complex Reasoning over Knowledge Graph with Logic-Aware Curriculum Tuning [89.89857766491475]
大規模言語モデル(LLM)に基づくKG上の複雑な推論スキーマを提案する。
任意の一階論理クエリを二分木分解により拡張し、LLMの推論能力を刺激する。
広く使われているデータセットに対する実験では、LACTは高度な手法よりも大幅に改善されている(平均+5.5% MRRスコア)。
論文 参考訳（メタデータ） (2024-05-02T18:12:08Z) - Agnostic Membership Query Learning with Nontrivial Savings: New Results,
Techniques [0.0]
学習の最前線で授業の会員クエリによる学習を検討する。
このアプローチは、非自明な貯蓄を伴う線形学習の研究にインスパイアされ、継続する」。
ゲートのサブ線形数からなる回路の非依存学習アルゴリズムを確立する。
論文 参考訳（メタデータ） (2023-11-11T23:46:48Z) - LOGICSEG: Parsing Visual Semantics with Neural Logic Learning and
Reasoning [73.98142349171552]
LOGICSEGは、神経誘導学習と論理推論をリッチデータとシンボリック知識の両方に統合する、全体論的視覚意味論である。
ファジィ論理に基づく連続的な緩和の間、論理式はデータとニューラルな計算グラフに基礎を置いており、論理によるネットワークトレーニングを可能にする。
これらの設計によりLOGICSEGは、既存のセグメンテーションモデルに容易に統合できる汎用的でコンパクトなニューラル論理マシンとなる。
論文 参考訳（メタデータ） (2023-09-24T05:43:19Z) - Modeling Hierarchical Reasoning Chains by Linking Discourse Units and
Key Phrases for Reading Comprehension [80.99865844249106]
本稿では,論理的推論の基盤として,対話レベルと単語レベルの両方の文脈を扱う総合グラフネットワーク(HGN)を提案する。
具体的には、ノードレベルの関係とタイプレベルの関係は、推論過程におけるブリッジと解釈できるが、階層的な相互作用機構によってモデル化される。
論文 参考訳（メタデータ） (2023-06-21T07:34:27Z) - Principled and Efficient Motif Finding for Structure Learning of Lifted
Graphical Models [5.317624228510748]
構造学習は、ニューロシンボリックAIと統計リレーショナル学習の分野の中心となるAIの中核的な問題である。
昇降型グラフィカルモデルにおける構造モチーフのマイニングのための第一原理的アプローチを提案する。
我々は,最先端構造学習の手法を,精度で最大6%,実行時の最大80%で上回ることを示す。
論文 参考訳（メタデータ） (2023-02-09T12:21:55Z) - Discourse-Aware Graph Networks for Textual Logical Reasoning [142.0097357999134]
パッセージレベルの論理関係は命題単位間の係り合いまたは矛盾を表す(例、結論文)
論理的推論QAを解くための論理構造制約モデリングを提案し、談話対応グラフネットワーク(DAGN)を導入する。
ネットワークはまず、インラインの談話接続とジェネリック論理理論を利用した論理グラフを構築し、その後、エッジ推論機構を用いて論理関係を進化させ、グラフ機能を更新することで論理表現を学習する。
論文 参考訳（メタデータ） (2022-07-04T14:38:49Z) - Learning Gradual Argumentation Frameworks using Genetic Algorithms [5.953590600890214]
本稿では,議論型分類モデルの構造を同時に学習する遺伝的アルゴリズムを提案する。
本プロトタイプでは,学習性能と解釈可能性の観点から,決定木に匹敵する論証的分類モデルを学習する。
論文 参考訳（メタデータ） (2021-06-25T12:33:31Z) - Learning Concepts Described by Weight Aggregation Logic [0.0]
我々は、重みを集約し、それらの集合を比較し、より複雑な公式を構築するための一階述語論理の拡張を導入する。
重み付き背景構造上のFOWA1で定義可能な概念は, 擬似線形時間前処理後の多言語時間において, 不可知的にPAC学習可能であることを示す。
論文 参考訳（メタデータ） (2020-09-22T14:32:42Z) - Evaluating Logical Generalization in Graph Neural Networks [59.70452462833374]
グラフニューラルネットワーク(GNN)を用いた論理一般化の課題について検討する。
ベンチマークスイートであるGraphLogでは、学習アルゴリズムが異なる合成論理でルール誘導を実行する必要がある。
モデルが一般化し適応する能力は、トレーニング中に遭遇する論理規則の多様性によって強く決定される。
論文 参考訳（メタデータ） (2020-03-14T05:45:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。