Fugu-MT 論文翻訳(概要): Fitting and Learning Basis-Restricted Propositional Formulas

論文の概要: Fitting and Learning Basis-Restricted Propositional Formulas

arxiv url: http://arxiv.org/abs/2609.08961v1
Date: Tue, 08 Sep 2026 16:15:00 GMT
ステータス: 翻訳完了
システム内更新日: 2026-09-10 19:44:08.691737
Title: Fitting and Learning Basis-Restricted Propositional Formulas
Title（参考訳）: 基底制限付き命題公式のフィッティングと学習
Abstract要約: 我々は、$O$の関数を用いて構築された命題公式のクラスを連結体として考える。私たちは、$O$の可能な選択ごとに、様々なフィッティングと学習問題の複雑さを判断します。
参考スコア（独自算出の注目度）: 2.436681150766912
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: For a finite set $O$ of Boolean functions, we consider the class of propositional formulas built using the functions in $O$ as connectives. We determine, for each possible choice of $O$, the complexity of various fitting and learning problems. These include: finding a formula that fits a given labeled sample, finding a small one (an Occam algorithm), minimizing the number of misclassified examples when the sample is not realizable (empirical risk minimization), and several forms of PAC learning. Our results apply both to formulas (represented as trees) and to circuits. We also briefly discuss the status of the same questions for other kinds of propositional fragments.
Abstract（参考訳）: ブール関数の有限集合 $O$ に対して、$O$ の関数を用いて構築された命題公式のクラスを連結として考える。私たちは、$O$の可能な選択ごとに、様々なフィッティングと学習問題の複雑さを判断します。与えられたラベル付きサンプルに適合する式を見つけること、小さなサンプル(オッカムアルゴリズム)を見つけること、サンプルが実現不可能な場合の誤分類例の数を最小化すること(経験的リスク最小化)、PAC学習のいくつかの形式である。この結果は、式(木として表現される)と回路の両方に適用できる。また、他の種類の命題的断片に対する同じ質問の状況についても簡単に議論する。

関連論文リスト

How (and when) can you fit examples to logic-based hypothesis classes over infinite structures? [2.012461155840431]
我々は、共通決定可能な構造における論理的に定義されたクラスに対する適合の計算的および記述的複雑さに焦点を当てる。サンプルが適合するかどうかを判断するために、サンプル上の自然言語でクエリを使用します。
論文参考訳（メタデータ） (2026-05-31T08:59:30Z)
Strategic PAC Learnability via Geometric Definability [69.34283267701421]
戦略分類は、個人が分類者の判断に影響を与えるために、コストで特徴を修正できる学習環境を研究する。中心的な問題は、帰納的(戦略的な)仮説クラスのサンプルの複雑さが、基礎となる仮説クラスの複雑さと、実現可能な操作を管理するコスト構造にどのように依存するかである。仮説クラスとコスト誘起近傍関係は、$mathbbR_mathtexp$上の一階式で定義することができる。難易度は, 複雑度によって制御され, 学習性は維持されていることを証明した。
論文参考訳（メタデータ） (2026-05-13T12:21:56Z)
Learning Compositional Functions with Transformers from Easy-to-Hard Data [63.96562216704653]
我々は、$k$入力置換と$k$隠れ置換のインターリーブ構成を計算しなければならない$k$フォールド合成タスクの学習可能性について検討する。この関数クラスは、$O(log k)$-depth変換器への勾配降下により、実行時とサンプルを$k$で効率的に学習できることを示す。
論文参考訳（メタデータ） (2025-05-29T17:22:00Z)
Homomorphisms and Embeddings of STRIPS Planning Models [4.594173051888471]
1つ目はGI完全であり、理論上は準多項式時間で解けることを示す。残りの問題はNP完全であることが証明されているが、可能であれば同型を構築するアルゴリズムを提案する。
論文参考訳（メタデータ） (2024-06-24T11:43:18Z)
Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文参考訳（メタデータ） (2023-12-08T16:06:29Z)
Information-Computation Tradeoffs for Learning Margin Halfspaces with Random Classification Noise [50.64137465792738]
ランダム分類ノイズを用いたPAC$gamma$-marginハーフスペースの問題について検討する。我々は、問題のサンプル複雑性と計算効率の良いアルゴリズムのサンプル複雑性との間に固有のギャップを示唆する情報計算トレードオフを確立する。
論文参考訳（メタデータ） (2023-06-28T16:33:39Z)
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)
On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
論文参考訳（メタデータ） (2022-10-22T19:07:26Z)
Active Learning for Contextual Search with Binary Feedbacks [2.6424064030995957]
第一価格オークションなどの応用によって動機付けられた文脈探索における学習問題について検討する。本稿では,三分探索手法とマージンに基づく能動学習手法を併用した三分探索手法を提案する。
論文参考訳（メタデータ） (2021-10-03T19:05:29Z)
Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
論文参考訳（メタデータ） (2021-03-19T16:34:20Z)
A Provably Efficient Sample Collection Strategy for Reinforcement Learning [123.69175280309226]
オンライン強化学習(RL)における課題の1つは、エージェントがその振る舞いを最適化するために、環境の探索とサンプルの活用をトレードオフする必要があることである。 1) 生成モデル(環境のスパースシミュレータなど)にアクセス可能な状態のサンプル数を規定する「対象別」アルゴリズム,2) 所定のサンプルをできるだけ早く生成する「対象別」サンプル収集。
論文参考訳（メタデータ） (2020-07-13T15:17:35Z)
Faster PAC Learning and Smaller Coresets via Smoothed Analysis [25.358415142404752]
PAC学習は通常、$n$アイテムから小さなサブセット(varepsilon$-sample/net)を計算することを目的としています。スムーズな解析から着想を得て、クエリに対する強調誤差(最悪のケースではなく)を近似する自然な一般化を提案する。
論文参考訳（メタデータ） (2020-06-09T18:25:34Z)
Theory and Algorithms for Shapelet-based Multiple-Instance Learning [5.08418565337126]
本稿では,データ単位がバッグと呼ばれるインスタンスから構成されるMultiple-Instance Learning(MIL)の新たな定式化を提案する。目標は、"shapelet"(またはパターン)との類似性に基づいて、バッグの優れた分類器を見つけることである。私たちの定式化では、すべての可能なので、したがって無限に多くのシェイプレットを使い、よりリッチな分類器のクラスを生み出す。
論文参考訳（メタデータ） (2020-05-31T17:10:59Z)

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