論文の概要: VC Dimension and Distribution-Free Sample-Based Testing

• arxiv url: http://arxiv.org/abs/2012.03923v1
• Date: Mon, 7 Dec 2020 18:50:46 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-18 07:58:26.830493
• Title: VC Dimension and Distribution-Free Sample-Based Testing
• Title（参考訳）: VC次元と分布自由サンプルベーステスト
• Authors: Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms
• Abstract要約: 関数のどのクラスが学習できるよりも効率的にテストできるかを決定するという問題を検討する。 PAC学習に必要なサンプル数よりもはるかに少ない多くのサンプルを用いて、2つの自然な関数クラス、ジャンタ関数とモノトン関数をテストできることが示される。
• 参考スコア（独自算出の注目度）: 0.8830479021890576
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider the problem of determining which classes of functions can be tested more efficiently than they can be learned, in the distribution-free sample-based model that corresponds to the standard PAC learning setting. Our main result shows that while VC dimension by itself does not always provide tight bounds on the number of samples required to test a class of functions in this model, it can be combined with a closely-related variant that we call "lower VC" (or LVC) dimension to obtain strong lower bounds on this sample complexity. We use this result to obtain strong and in many cases nearly optimal lower bounds on the sample complexity for testing unions of intervals, halfspaces, intersections of halfspaces, polynomial threshold functions, and decision trees. Conversely, we show that two natural classes of functions, juntas and monotone functions, can be tested with a number of samples that is polynomially smaller than the number of samples required for PAC learning. Finally, we also use the connection between VC dimension and property testing to establish new lower bounds for testing radius clusterability and testing feasibility of linear constraint systems.
• Abstract（参考訳）: 標準的なPAC学習環境に対応する分布自由サンプルベースモデルにおいて,どの関数のクラスを学習よりも効率的にテストできるかを決定する問題を考える。 我々の主な結果は、VC次元自体が、このモデルで関数のクラスをテストするのに必要なサンプル数に厳密な境界を与えるわけではないが、このモデルでは「より低いVC」(またはLVC)次元と呼ばれる近縁な不変量と組み合わせて、この複雑さの強い下界を得ることができることを示している。 この結果は強く、多くの場合、間隔、ハーフ空間、ハーフ空間の交叉、多項式しきい値関数、決定木の結合をテストするためのサンプル複雑性のほとんど最適な下界を得る。 逆に,PAC学習に必要なサンプル数よりも多項式的に小さい多くのサンプルを用いて,2種類の自然クラスであるユンタスとモノトン関数を検証可能であることを示す。 最後に、VC次元とプロパティテストの関連性を利用して、線形制約システムのクラスター性テストとテスト可能性をテストするための新しい下位境界を確立する。

関連論文リスト

• MulTi-Wise Sampling: Trading Uniform T-Wise Feature Interaction Coverage for Smaller Samples [4.337339380445765]
  既存のt-wiseサンプリングアルゴリズムは、すべての特徴に対するt-wise特徴相互作用を均一にカバーする。 本稿では,一様カバレッジの必要性を問う,T-wise特徴相互作用サンプリングに対する新しいアプローチを提案する。 我々のアプローチは、重要な特徴のサブセットに対する高いt値を考慮して、臨界特徴のサブセットと非臨界特徴のサブセットを優先順位付けする。
  論文  参考訳（メタデータ） (2024-06-28T10:16:10Z)
• Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests [5.3595271893779906]
  フェデレート学習は、さまざまな場所でデータが収集され分析される広範囲な設定で適用可能であることから、近年大きな注目を集めている。 分散差分プライバシー(DP)制約下でのホワイトノイズ・ウィズ・ドリフトモデルにおける非パラメトリック適合性試験について検討した。
  論文  参考訳（メタデータ） (2024-06-10T19:25:19Z)
• Optimal Multi-Distribution Learning [88.3008613028333]
  マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。 本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-08T16:06:29Z)
• Deep anytime-valid hypothesis testing [29.273915933729057]
  非パラメトリックなテスト問題に対する強力なシーケンシャルな仮説テストを構築するための一般的なフレームワークを提案する。 テスト・バイ・ベッティング・フレームワーク内で、機械学習モデルの表現能力を活用するための原則的なアプローチを開発する。 合成および実世界のデータセットに関する実証的な結果は、我々の一般的なフレームワークを用いてインスタンス化されたテストが、特殊なベースラインと競合することを示している。
  論文  参考訳（メタデータ） (2023-10-30T09:46:19Z)
• Testing properties of distributions in the streaming model [0.0]
  標準アクセスモデルと条件アクセスモデルにおける分散テストについて検討する。 目標は、メモリ制約を受けるサンプルの最適な数を使って、分散の特性をテストすることである。
  論文  参考訳（メタデータ） (2023-09-06T10:53:29Z)
• Non-generative Generalized Zero-shot Learning via Task-correlated Disentanglement and Controllable Samples Synthesis [20.34562156468408]
  これらの問題に対処する非生成モデルを提案する。 また、「Few-shot Seen Class and Zero-shot Unseen Class Learning」(FSZU)という新しいZSLタスクを定式化した。
  論文  参考訳（メタデータ） (2022-03-10T12:32:26Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  本研究では、半教師付きPACモデルにおいて、時間攻撃をテストするために、逆向きに頑健な予測器を学習する問題について検討する。 最悪の分布自由モデルにおいても,半教師付き頑健な学習には大きなメリットがあることが示されている。
  論文  参考訳（メタデータ） (2022-02-11T03:01:45Z)
• Sample-Efficient Reinforcement Learning Is Feasible for Linearly Realizable MDPs with Limited Revisiting [60.98700344526674]
  線形関数表現のような低複雑度モデルがサンプル効率のよい強化学習を可能にする上で重要な役割を果たしている。 本稿では,オンライン/探索的な方法でサンプルを描画するが,制御不能な方法で以前の状態をバックトラックし,再訪することができる新しいサンプリングプロトコルについて検討する。 この設定に合わせたアルゴリズムを開発し、特徴次元、地平線、逆の準最適ギャップと実際にスケールするサンプル複雑性を実現するが、状態/作用空間のサイズではない。
  論文  参考訳（メタデータ） (2021-05-17T17:22:07Z)
• Bilinear Classes: A Structural Framework for Provable Generalization in RL [119.42509700822484]
  Bilinear Classesは強化学習の一般化を可能にする新しい構造フレームワークである。 このフレームワークは、サンプルの複雑さが達成可能な、ほとんどすべての既存のモデルを取り込んでいる。 我々の主な成果は、双線形クラスのためのサンプル複雑性を持つRLアルゴリズムである。
  論文  参考訳（メタデータ） (2021-03-19T16:34:20Z)
• Bloom Origami Assays: Practical Group Testing [90.2899558237778]
  グループテストは、いくつかの魅力的なソリューションでよく研究されている問題である。 近年の生物学的研究は、従来の方法と相容れない新型コロナウイルスの実践的な制約を課している。 我々は,Bloomフィルタと信条伝搬を組み合わせた新しい手法を開発し,n(100以上)の大きい値に拡張し,良好な経験的結果を得る。
  論文  参考訳（メタデータ） (2020-07-21T19:31:41Z)
• Refined bounds for algorithm configuration: The knife-edge of dual class approximability [94.83809668933021]
  トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。 この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。 我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
  論文  参考訳（メタデータ） (2020-06-21T15:32:21Z)

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

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