論文の概要: Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings

• arxiv url: http://arxiv.org/abs/2308.10041v1
• Date: Sat, 19 Aug 2023 14:57:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-08-22 18:07:35.822533
• Title: Computing the Vapnik Chervonenkis Dimension for Non-Discrete Settings
• Title（参考訳）: 非離散設定のためのVapnik Chervonenkis次元の計算
• Authors: Mohammed Nechba, Mouhajir Mohamed, Sedjari Yassine
• Abstract要約: 本稿では,概念クラスやドメインセットに制約を加えることなく,VC次元を近似的に計算する手法を開発した。 提案手法は,経験的リスク最小化(Empirical Risk Minimization,ERM)学習パラダイムが,概念クラスの破砕特性を特徴付ける新しいツールとして利用できることを示すものである。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In 1984, Valiant [ 7 ] introduced the Probably Approximately Correct (PAC) learning framework for boolean function classes. Blumer et al. [ 2] extended this model in 1989 by introducing the VC dimension as a tool to characterize the learnability of PAC. The VC dimension was based on the work of Vapnik and Chervonenkis in 1971 [8 ], who introduced a tool called the growth function to characterize the shattering property. Researchers have since determined the VC dimension for specific classes, and efforts have been made to develop an algorithm that can calculate the VC dimension for any concept class. In 1991, Linial, Mansour, and Rivest [4] presented an algorithm for computing the VC dimension in the discrete setting, assuming that both the concept class and domain set were finite. However, no attempts had been made to design an algorithm that could compute the VC dimension in the general setting.Therefore, our work focuses on developing a method to approximately compute the VC dimension without constraints on the concept classes or their domain set. Our approach is based on our finding that the Empirical Risk Minimization (ERM) learning paradigm can be used as a new tool to characterize the shattering property of a concept class.
• Abstract（参考訳）: 1984年、valiant [7 ]はboolean関数クラスのためのおそらくほぼ正しい(pac)学習フレームワークを導入した。 Blumerなど。 [2]1989年にPACの学習性を特徴付けるツールとしてVC次元を導入してこのモデルを拡張した。 VC次元は、1971年にVapnikとChervonenkisの業績に基づいており、彼は、破砕特性を特徴づけるために成長関数と呼ばれるツールを導入した。 研究者はその後、特定のクラスのVC次元を決定し、任意の概念クラスのVC次元を計算するアルゴリズムを開発する努力をしてきた。 1991年、Linial, Mansour, and Rivest [4] は、概念クラスとドメインセットの両方が有限であると仮定して、離散的な設定でVC次元を計算するアルゴリズムを提示した。 しかし,vc次元を一般設定で計算可能なアルゴリズムを設計する試みは行われておらず,本研究は概念クラスやドメイン集合に制約なくvc次元を近似的に計算する手法の開発に焦点を当てている。 提案手法は,経験的リスク最小化(Empirical Risk Minimization,ERM)学習パラダイムが,概念クラスの破砕特性を特徴付ける新しいツールとして利用できることを示すものである。

関連論文リスト

• On the Computability of Multiclass PAC Learning [9.507869508188266]
  最近導入された計算可能PAC(CPAC)学習フレームワークでは、学習者と出力する関数の両方が計算可能であることが求められている。 識別器の計算可能次元がCPAC学習を特徴付けることを示す。
  論文  参考訳（メタデータ） (2025-02-10T01:07:23Z)
• On Reductions and Representations of Learning Problems in Euclidean Spaces [15.07787640047213]
  多くの実用的な予測アルゴリズムはユークリッド空間における入力を表現し、離散的な0/1分類損失を真の自明な代理損失に置き換える。 我々は古典的トポロジカルアプローチと凸性を考慮したボルスク・ウラム理論の一般化を開発する。 また、ランダム性を利用して、より小さな次元で表現できる自然な分類タスクも提示する。
  論文  参考訳（メタデータ） (2024-11-16T12:09:37Z)
• Mathematical Algorithm Design for Deep Learning under Societal and Judicial Constraints: The Algorithmic Transparency Requirement [65.26723285209853]
  計算モデルにおける透過的な実装が実現可能かどうかを分析するための枠組みを導出する。 以上の結果から,Blum-Shub-Smale Machinesは,逆問題に対する信頼性の高い解法を確立できる可能性が示唆された。
  論文  参考訳（メタデータ） (2024-01-18T15:32:38Z)
• Human as Points: Explicit Point-based 3D Human Reconstruction from Single-view RGB Images [71.91424164693422]
  我々はHaPと呼ばれる明示的なポイントベース人間再構築フレームワークを導入する。 提案手法は,3次元幾何学空間における完全明示的な点雲推定,操作,生成,洗練が特徴である。 我々の結果は、完全に明示的で幾何学中心のアルゴリズム設計へのパラダイムのロールバックを示すかもしれない。
  論文  参考訳（メタデータ） (2023-11-06T05:52:29Z)
• A Geometric Notion of Causal Probing [91.14470073637236]
  言語モデルの表現空間では、動詞数のような概念に関するすべての情報が線形部分空間に符号化される。 理想線型概念部分空間を特徴づける内在的基準のセットを与える。 LEACEは概念情報の約半分を含む1次元の部分空間を返す。
  論文  参考訳（メタデータ） (2023-07-27T17:57:57Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。 オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
  論文  参考訳（メタデータ） (2023-07-07T21:39:25Z)
• A Characterization of List Learnability [15.368858716555888]
  我々は、$k$の予測リストを出力することを目標とするPAC学習について検討する。 最近のマルチクラス学習可能性の特徴を一般化すると、仮説クラスが$k$-list学習可能であることと、$k$-DS次元が有限であることは同値である。
  論文  参考訳（メタデータ） (2022-11-07T21:28:05Z)
• On Leave-One-Out Conditional Mutual Information For Generalization [122.2734338600665]
  残余条件付き相互情報(loo-CMI)の新しい尺度に基づく教師付き学習アルゴリズムのための情報理論の一般化境界を導出する。 他のCMI境界とは対照的に、我々のloo-CMI境界は容易に計算でき、古典的なout-out-out-cross-validationのような他の概念と関連して解釈できる。 ディープラーニングのシナリオにおいて予測された一般化ギャップを評価することにより,境界の質を実証的に検証する。
  論文  参考訳（メタデータ） (2022-07-01T17:58:29Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• A Characterization of Multiclass Learnability [18.38631912121182]
  DS次元はDanielyとShalev-Shwartz 2014によって定義された次元である。 リスト学習設定では、与えられた未知の入力に対して単一の結果を予測する代わりに、予測の短いメニューを提供することが目標である。 2つ目の主な成果は、多クラス学習の可能性を特徴づける中心的な候補であるナタラジャン次元に関するものである。
  論文  参考訳（メタデータ） (2022-03-03T07:41:54Z)

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

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