論文の概要: Applications of Littlestone dimension to query learning and to
compression
- arxiv url: http://arxiv.org/abs/2310.04812v1
- Date: Sat, 7 Oct 2023 14:04:18 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-12 15:29:17.755071
- Title: Applications of Littlestone dimension to query learning and to
compression
- Title（参考訳）: リトルストーン次元のクエリ学習と圧縮への応用
- Authors: Hunter Chase and James Freitag and Lev Reyzin
- Abstract要約: 我々は、ランダムな反例を持つ同値クエリによる学習のために、2017年のシアングルインのモデルを拡張した。
第二に、このモデルを無作為性のある無限の概念クラスに拡張する。
第三に、Littlestone次元と拡張$d$-compressionスキームを持つクラスとの関係に関する改善された結果を与える。
- 参考スコア（独自算出の注目度）: 1.9336815376402723
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In this paper we give several applications of Littlestone dimension. The
first is to the model of \cite{angluin2017power}, where we extend their results
for learning by equivalence queries with random counterexamples. Second, we
extend that model to infinite concept classes with an additional source of
randomness. Third, we give improved results on the relationship of Littlestone
dimension to classes with extended $d$-compression schemes, proving a strong
version of a conjecture of \cite{floyd1995sample} for Littlestone dimension.
- Abstract（参考訳）: 本稿では,リトルストーン次元の応用について述べる。
ひとつは \cite{angluin2017power} のモデルで、ランダムな反例を持つ同値クエリによる学習結果を拡張します。
第二に、このモデルを無作為性のある無限の概念クラスに拡張する。
第三に、Littlestone 次元と拡張 $d$-圧縮スキームを持つクラスとの関係に関する改善された結果を与え、Littlestone 次元に対するcite{floyd 1995sample} の予想の強いバージョンを証明した。
関連論文リスト
- Disentangled Representation Learning with the Gromov-Monge Gap [65.73194652234848]
乱れのないデータから歪んだ表現を学習することは、機械学習における根本的な課題である。
本稿では,2次最適輸送に基づく非交叉表現学習手法を提案する。
提案手法の有効性を4つの標準ベンチマークで示す。
論文 参考訳（メタデータ） (2024-07-10T16:51:32Z) - Optimal Multi-Distribution Learning [88.3008613028333]
マルチディストリビューション学習は、$k$の異なるデータ分散における最悪のリスクを最小限に抑える共有モデルを学ぶことを目指している。
本稿では, (d+k)/varepsilon2の順に, サンプルの複雑さを伴って, ヴァレプシロン最適ランダム化仮説を導出するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-12-08T16:06:29Z) - Learning with Explanation Constraints [91.23736536228485]
我々は、説明がモデルの学習をどのように改善するかを分析するための学習理論フレームワークを提供する。
我々は,多数の合成および実世界の実験に対して,我々のアプローチの利点を実証する。
論文 参考訳（メタデータ） (2023-03-25T15:06:47Z) - The unstable formula theorem revisited via algorithms [17.736645608595758]
我々は、シェラの有名な不安定なフォーミュラ定理の完全なアルゴリズム的類似体を開発する。
モデル理論における型の定義可能性に類似して、近似を用いてLittlestoneクラスを記述する。
論文 参考訳（メタデータ） (2022-12-09T18:53:34Z) - Improved Inapproximability of VC Dimension and Littlestone's Dimension
via (Unbalanced) Biclique [28.57552551316786]
我々は、VC次元とリトルストーン次元を近似するために、最大(アンバランス)双立問題から簡単な還元を与える。
この接続により、近似結果と時間的下界のランニングの難易度を導出する。
論文 参考訳（メタデータ） (2022-11-02T19:23:42Z) - Sample-efficient proper PAC learning with approximate differential
privacy [51.09425023771246]
近似微分プライバシーを持つリトルストーン次元のクラスを適切に学習するサンプル複雑性が$tilde o(d6)$であることを証明し、プライバシーパラメータと精度パラメータを無視する。
この結果は Bun et al の質問に答えます。
(FOCS 2020) サンプルの複雑さに$2O(d)$の上限で改善することによって。
論文 参考訳（メタデータ） (2020-12-07T18:17:46Z) - Near-tight closure bounds for Littlestone and threshold dimensions [59.245101116396555]
二つの仮説クラスのリトルストーンおよびしきい値次元の閉包特性について検討する。
我々の上界は、アロンらによって示される類似境界に対して指数的($k$で)改善を与える。
論文 参考訳（メタデータ） (2020-07-07T17:56:06Z) - Compressing Large Sample Data for Discriminant Analysis [78.12073412066698]
判別分析フレームワーク内での大きなサンプルサイズに起因する計算問題を考察する。
線形および二次判別分析のためのトレーニングサンプル数を削減するための新しい圧縮手法を提案する。
論文 参考訳（メタデータ） (2020-05-08T05:09:08Z) - Stein's Lemma for the Reparameterization Trick with Exponential Family Mixtures [23.941042092067338]
スタインの補題はスタインの方法において重要な役割を果たす。
我々はスタインの補題を指数列混合分布に拡張する。
論文 参考訳（メタデータ） (2019-10-29T16:59:22Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。