Fugu-MT 論文翻訳(概要): On the equivalence of Occam algorithms

論文の概要: On the equivalence of Occam algorithms

arxiv url: http://arxiv.org/abs/2308.05906v1
Date: Fri, 11 Aug 2023 02:05:08 GMT
ステータス: 処理完了
システム内更新日: 2023-08-14 15:13:57.313105
Title: On the equivalence of Occam algorithms
Title（参考訳）: occamアルゴリズムの等価性について
Authors: Zaman Keinath-Esmail
Abstract要約: ボード・アンド・ピット(1990)は、例外リストの下で閉じた概念クラスに対して、PACが学習可能なクラスはオッカムアルゴリズムによって学習可能であることを示した。これらの部分的逆は、$delta$-independent complexities を持つ Occam アルゴリズムにも適用可能であることを示す。
参考スコア（独自算出の注目度）: 0.0
License: http://creativecommons.org/licenses/by-nc-nd/4.0/
Abstract: Blumer et al. (1987, 1989) showed that any concept class that is learnable by Occam algorithms is PAC learnable. Board and Pitt (1990) showed a partial converse of this theorem: for concept classes that are closed under exception lists, any class that is PAC learnable is learnable by an Occam algorithm. However, their Occam algorithm outputs a hypothesis whose complexity is $\delta$-dependent, which is an important limitation. In this paper, we show that their partial converse applies to Occam algorithms with $\delta$-independent complexities as well. Thus, we provide a posteriori justification of various theoretical results and algorithm design methods which use the partial converse as a basis for their work.
Abstract（参考訳）: Blumer et al. (1987, 1989) はオッカムアルゴリズムで学習可能な任意の概念クラスがPAC学習可能であることを示した。ボード・アンド・ピット(1990)は、例外リストの下で閉じた概念クラスに対して、PACが学習可能なクラスはオッカムアルゴリズムによって学習可能であることを示した。しかし、Occamアルゴリズムは複雑さが$\delta$-dependentであるという仮説を出力し、これは重要な制限である。本稿では,その部分的逆が$\delta$-independent complexitiesを持つOccamアルゴリズムにも適用されることを示す。そこで本論文では, 様々な理論結果の後部正当化と, 部分的逆を基礎としてアルゴリズム設計手法を提案する。

関連論文リスト

Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
論文参考訳（メタデータ） (2024-08-14T19:04:13Z)
Provable Advantage in Quantum PAC Learning [3.291862617649511]
PAC学習者は量子学習において汎用的な優位性を得ることができることを示す。多相性因子は古典的な学習サンプルの複雑さよりも正方形の改善である。
論文参考訳（メタデータ） (2023-09-19T19:26:20Z)
Efficiently Learning One-Hidden-Layer ReLU Networks via Schur Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文参考訳（メタデータ） (2023-07-24T14:37:22Z)
A Parameterized Theory of PAC Learning [19.686465068713467]
おそらく略正(PAC)学習は、サンプル複雑性理論の中核的な概念である。我々は、パラメータ化複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができるパラメータ化PAC学習の理論を開発した。
論文参考訳（メタデータ） (2023-04-27T09:39:30Z)
A Theory of PAC Learnability of Partial Concept Classes [30.772106555607458]
我々は、多種多様な学習タスクをモデル化できるように、PAC学習理論を拡張した。部分概念クラスのPAC学習性を特徴付け,古典的クラスと根本的に異なるアルゴリズム的ランドスケープを明らかにする。
論文参考訳（メタデータ） (2021-07-18T13:29:26Z)
Dynamic programming by polymorphic semiring algebraic shortcut fusion [1.9405875431318445]
動的プログラミング(動的プログラミング、英: Dynamic Programming、DP)は、難解問題の効率的かつ正確な解法のためのアルゴリズム設計パラダイムである。本稿では,セミリングに基づくDPアルゴリズムを体系的に導出するための厳密な代数形式について述べる。
論文参考訳（メタデータ） (2021-07-05T00:51:02Z)
Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文参考訳（メタデータ） (2021-06-02T22:03:36Z)
The Complexity of Adversarially Robust Proper Learning of Halfspaces with Agnostic Noise [67.27523616312428]
分布非依存型PACモデルにおけるハーフスペースの逆強正則学習の計算複雑性について検討する。この問題に対して,計算効率のよい学習アルゴリズムとほぼ一致する計算硬度結果を与える。
論文参考訳（メタデータ） (2020-07-30T04:18:51Z)
Algorithms and SQ Lower Bounds for PAC Learning One-Hidden-Layer ReLU Networks [48.32532049640782]
ガウス境界の下で, 1層ReLUネットワークを$k$の隠れ単位で学習する問題をmathbbRd$で研究する。正の係数の場合、この学習問題の初回アルゴリズムを$k$から$tildeOOmega(sqrtlog d)$まで与える。
論文参考訳（メタデータ） (2020-06-22T17:53:54Z)
Proper Learning, Helly Number, and an Optimal SVM Bound [29.35254938542589]
適切な学習アルゴリズムにより最適なサンプル複雑性を達成できるクラスを特徴付ける。双対ヘリー数が有界であることと、$epsilon$ と $delta$ に適切な合同依存が存在することを示せる。
論文参考訳（メタデータ） (2020-05-24T18:11:57Z)
Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
論文参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。