論文の概要: How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
- arxiv url: http://arxiv.org/abs/2606.01107v1
- Date: Sun, 31 May 2026 08:59:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-02 21:34:29.208935
- Title: How (and when) can you fit examples to logic-based hypothesis classes over infinite structures?
- Title（参考訳）: 無限の構造上の論理ベースの仮説クラスに対して、どのように(いつ)例を適合させることができますか?
- Abstract要約: 我々は、共通決定可能な構造における論理的に定義されたクラスに対する適合の計算的および記述的複雑さに焦点を当てる。
サンプルが適合するかどうかを判断するために、サンプル上の自然言語でクエリを使用します。
- 参考スコア（独自算出の注目度）: 2.012461155840431
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study fitting problems, sometimes called ``training problems'', where we have a finite sample consisting of inputs and outputs, and we want to know whether there is a function in a certain class that could produce these outputs, exactly or approximately, on the given inputs. We focus on the computational and descriptive complexity of fitting for logically-defined classes in common decidable structures, like the real ordered field and Presburger arithmetic, and also for broader classes defined via combinatorial or model-theoretic properties. We isolate the complexity of these fitting problems, with particular attention to cases where we can use queries in a natural query language over the sample to determine whether a sample is fittable.
- Abstract（参考訳）: ここでは、入力と出力からなる有限標本を持ち、与えられた入力に対してこれらの出力を正確にあるいはほぼ生成できるあるクラスに関数が存在するかどうかを知りたい。
我々は、実順序体やプレスバーグの算術のような一般的な決定可能な構造における論理的に定義されたクラスに対する適合の計算と記述の複雑さ、および組合せ的あるいはモデル理論的性質によって定義されるより広範なクラスに焦点をあてる。
我々はこれらの適合問題の複雑さを分離し、特にサンプルが適合するかどうかを判断するために、サンプル上の自然言語でクエリを使用できるケースに注目した。
関連論文リスト
- Fitting and Learning Basis-Restricted Propositional Formulas [2.436681150766912]
我々は、$O$の関数を用いて構築された命題公式のクラスを連結体として考える。
私たちは、$O$の可能な選択ごとに、様々なフィッティングと学習問題の複雑さを判断します。
論文 参考訳（メタデータ） (2026-09-08T16:15:00Z) - Causally Evaluating the Learnability of Formal Language Tasks [59.73001113068827]
データ周波数と学習可能性の関係を精査する。
特定のサブタスクの学習可能性を測定するために、Kullback-Leibler分散メトリクスを導出する。
実験の結果,因果介入を伴わない学習性の評価は誤結論につながることがわかった。
論文 参考訳（メタデータ） (2026-06-08T17:58:36Z) - Strategic PAC Learnability via Geometric Definability [69.34283267701421]
戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。
中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。
仮説クラスとコスト誘起近傍関係は、$mathbbR_mathtexp$上の一階式で定義することができる。
難易度は, 複雑度によって制御され, 学習性は維持されていることを証明した。
論文 参考訳（メタデータ） (2026-05-13T12:21:56Z) - Classical and Quantum Query Complexity of Boolean Functions under Indefinite Causal Order [0.8192907805418583]
計算モデルは一般に、操作が一定の順序で適用されると仮定する。
近年、固定因果構造を持たない計算を考慮し、この仮定を緩和する研究がいくつか行われている。
正確なクエリの複雑さの分離は、今のところ発見されていない。
論文 参考訳（メタデータ） (2025-06-05T16:00:36Z) - A Compositional Atlas for Algebraic Circuits [35.95450187283255]
クエリの大規模なクラスは、半環上の基本演算子(アグリゲーション、製品、および要素ワイドマッピング)の組み合わせに対応することを示す。
分析を応用して、このような多くの合成クエリに対して、新しいトラクタビリティ条件を導出する。
論文 参考訳（メタデータ） (2024-12-07T00:51:46Z) - The Hardness of Reasoning about Probabilities and Causality [5.190207094732672]
本研究では,定量的確率論的推論と因果的影響に対するdo-calculus推論を表現可能な言語について検討する。
この研究の主な貢献は、満足度問題の正確な計算複雑性を確立することである。
我々は、よく研究されたクラス $exists$R の簡潔な変種と見なすことができる Succ$exists$R という新しい自然複雑性クラスを導入する。
論文 参考訳（メタデータ） (2023-05-16T15:01:22Z) - Amortized Inference for Causal Structure Learning [72.84105256353801]
因果構造を学習することは、通常、スコアまたは独立テストを使用して構造を評価することを伴う探索問題を引き起こす。
本研究では,観測・干渉データから因果構造を予測するため,変分推論モデルを訓練する。
我々のモデルは、実質的な分布シフトの下で頑健な一般化能力を示す。
論文 参考訳（メタデータ） (2022-05-25T17:37:08Z) - Quantifying and Understanding Adversarial Examples in Discrete Input
Spaces [70.18815080530801]
我々は、任意の離散的な設定で適用される同義的逆例の概念を定式化し、そのような例を構成するための単純なドメインに依存しないアルゴリズムを記述する。
我々の研究は、連続入力と類似した離散逆例のドメインに依存しない処理への一歩である。
論文 参考訳（メタデータ） (2021-12-12T16:44:09Z) - Statistically Meaningful Approximation: a Case Study on Approximating
Turing Machines with Transformers [50.85524803885483]
本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。
回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
論文 参考訳（メタデータ） (2021-07-28T04:28:55Z) - Conjunctive Queries: Unique Characterizations and Exact Learnability [0.0]
接続型クエリのクラスに対して,より効率的な正確な学習アルゴリズムを提案する。
また、有限構造の準同型格子におけるフロンティアの構成についても論じる。
論文 参考訳（メタデータ） (2020-08-16T02:54:56Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。