論文の概要: A packing lemma for VCN${}_k$-dimension and learning high-dimensional data

• arxiv url: http://arxiv.org/abs/2505.15688v1
• Date: Wed, 21 May 2025 16:03:12 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-05-22 15:42:59.761935
• Title: A packing lemma for VCN${}_k$-dimension and learning high-dimensional data
• Title（参考訳）: VCN${}_k$-次元のパッキング補題と高次元データの学習
• Authors: Leonardo N. Coregliano, Maryanthe Malliaris,
• Abstract要約: 本研究では,非認識型高アリティPAC学習性は,Husslerパッケージ特性の高アリティバージョンを意味することを示す。 これは古典的なPAC学習性は古典的なハウスラーパッキング特性を意味するという直接的な証明を得ることによってなされる。
• 参考スコア（独自算出の注目度）: 1.6114012813668932
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, the authors introduced the theory of high-arity PAC learning, which is well-suited for learning graphs, hypergraphs and relational structures. In the same initial work, the authors proved a high-arity analogue of the Fundamental Theorem of Statistical Learning that almost completely characterizes all notions of high-arity PAC learning in terms of a combinatorial dimension, called the Vapnik--Chervonenkis--Natarajan (VCN${}_k$) $k$-dimension, leaving as an open problem only the characterization of non-partite, non-agnostic high-arity PAC learnability. In this work, we complete this characterization by proving that non-partite non-agnostic high-arity PAC learnability implies a high-arity version of the Haussler packing property, which in turn implies finiteness of VCN${}_k$-dimension. This is done by obtaining direct proofs that classic PAC learnability implies classic Haussler packing property, which in turn implies finite Natarajan dimension and noticing that these direct proofs nicely lift to high-arity.
• Abstract（参考訳）: 筆者らは近年,グラフ,ハイパーグラフ,リレーショナル構造を学習するのに適した高純度PAC学習理論を導入した。 同じ初期の研究で、著者らは統計学習の基本定理の高次類似性を証明し、Vapnik--Chervonenkis--Natarajan (VCN${}_k$) $k$-dimension と呼ばれる組合せ次元で高次PAC学習のすべての概念をほぼ完全に特徴づけた。 本研究では,非パーティント非依存的高アリティPAC学習性はハウスラーパッキング特性の高アリティバージョンであり,VCN${}_k$-次元の有限性を意味することを証明して,この特性を完成させる。 これは古典的なPAC学習可能性(英語版)が古典的なハウスラーパッキング性(英語版)を暗示する直接証明を得ることによって得られる。

関連論文リスト

• Towards Efficient Contrastive PAC Learning [6.209600119671225]
  我々はPAC学習の枠組みの下で対照的な学習について研究する。 本稿では,線形表現の基本概念の対照的な学習について考察する。 我々は,Rademacherの複雑性に基づいた保証を確立し,それとPACの保証を,ある対照的な大マルジン条件下で接続する。
  論文  参考訳（メタデータ） (2025-02-21T21:51:01Z)
• Is Transductive Learning Equivalent to PAC Learning? [0.9012198585960443]
  PACモデルとトランスダクティブモデルは、本質的には非依存のバイナリ分類に等価であることを示す。 我々は,2番目の結果が2進分類を超えて拡張可能かどうかという興味深い疑問を残して,トランスダクティブモデルとPACモデルがより広範に等価であることを示す。
  論文  参考訳（メタデータ） (2024-05-08T16:26:49Z)
• High-arity PAC learning via exchangeability [1.6114012813668932]
  我々は「構造化相関」の存在下での統計的学習である高純度PAC学習の理論を開発する。 我々の主定理は、統計学習の基本的な定理の高次性(不可知性)バージョンを確立する。
  論文  参考訳（メタデータ） (2024-02-22T05:16:04Z)
• Optimal Learners for Realizable Regression: PAC Learning and Online Learning [52.37726841759983]
  本研究では,PAC学習環境とオンライン学習環境の両方において,実現可能な回帰の統計的複雑さを特徴付けることを目的とする。 まず,再現可能な回帰のためのミニマックスインスタンス最適学習器を導入し,実数値予測器のどのクラスが学習可能であるかを質的かつ定量的に特徴付ける新しい次元を提案する。 オンライン学習の文脈では、最小の最適インスタンス最適累積損失を一定要素まで特徴付ける次元を提供し、再現可能な回帰のための最適オンライン学習者を設計する。
  論文  参考訳（メタデータ） (2023-07-07T21:39:25Z)
• Multiclass Boosting: Simple and Intuitive Weak Learning Criteria [72.71096438538254]
  実現可能性の仮定を必要としない,単純かつ効率的なブースティングアルゴリズムを提案する。 本稿では,リスト学習者の向上に関する新たな結果と,マルチクラスPAC学習の特徴付けのための新しい証明を提案する。
  論文  参考訳（メタデータ） (2023-07-02T19:26:58Z)
• Understanding Augmentation-based Self-Supervised Representation Learning via RKHS Approximation and Regression [53.15502562048627]
  最近の研究は、自己教師付き学習とグラフラプラシアン作用素のトップ固有空間の近似との関係を構築している。 この研究は、増強に基づく事前訓練の統計的分析に発展する。
  論文  参考訳（メタデータ） (2023-06-01T15:18:55Z)
• Confident Sinkhorn Allocation for Pseudo-Labeling [40.883130133661304]
  半教師付き学習は、ラベル付きデータへの機械学習の依存を減らす重要なツールである。 本稿では,疑似ラベル作成における不確実性の役割を理論的に研究し,CSA(Confident Sinkhorn Allocation)を提案する。 CSAは、信頼度の高いサンプルのみへの最適な輸送を通して、最高の擬似ラベル割り当てを特定する。
  論文  参考訳（メタデータ） (2022-06-13T02:16:26Z)
• The Polynomial Method is Universal for Distribution-Free Correlational SQ Learning [9.036124518750732]
  Malach と Shalev-Shwartz (2022) を一般化し、学習公式に対する厳密な相関 SQ (CSQ) の下界を与えた。 任意の関数クラスのしきい値または近似次数に対する下限は、PACまたはDNF学習のためのCSQ下限を直接意味する。
  論文  参考訳（メタデータ） (2020-10-22T17:55:26Z)
• CSNE: Conditional Signed Network Embedding [77.54225346953069]
  署名されたネットワークは、友人/フォアや信頼/不信のようなエンティティ間の正と負の関係を符号化する。 サイン予測のための既存の埋め込み手法は、一般に最適化関数におけるステータスやバランス理論の異なる概念を強制する。 条件付き符号付きネットワーク埋め込み(CSNE)を導入する。 我々の確率論的アプローチは、きめ細かな詳細とは別途、ネットワーク内の記号に関する構造情報をモデル化する。
  論文  参考訳（メタデータ） (2020-05-19T19:14:52Z)

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

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