論文の概要: A Theory of Universal Learning
- arxiv url: http://arxiv.org/abs/2011.04483v1
- Date: Mon, 9 Nov 2020 15:10:32 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 00:51:40.188371
- Title: A Theory of Universal Learning
- Title(参考訳): 普遍的学習の理論
- Authors: Olivier Bousquet, Steve Hanneke, Shay Moran, Ramon van Handel, Amir
Yehudayoff
- Abstract要約: 普遍的な学習の確率は3つしかないことを示す。
任意の概念クラスの学習曲線は指数的あるいは任意に遅い速度で減衰することを示す。
- 参考スコア(独自算出の注目度): 26.51949485387526
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: How quickly can a given class of concepts be learned from examples? It is
common to measure the performance of a supervised machine learning algorithm by
plotting its "learning curve", that is, the decay of the error rate as a
function of the number of training examples. However, the classical theoretical
framework for understanding learnability, the PAC model of Vapnik-Chervonenkis
and Valiant, does not explain the behavior of learning curves: the
distribution-free PAC model of learning can only bound the upper envelope of
the learning curves over all possible data distributions. This does not match
the practice of machine learning, where the data source is typically fixed in
any given scenario, while the learner may choose the number of training
examples on the basis of factors such as computational resources and desired
accuracy.
In this paper, we study an alternative learning model that better captures
such practical aspects of machine learning, but still gives rise to a complete
theory of the learnable in the spirit of the PAC model. More precisely, we
consider the problem of universal learning, which aims to understand the
performance of learning algorithms on every data distribution, but without
requiring uniformity over the distribution. The main result of this paper is a
remarkable trichotomy: there are only three possible rates of universal
learning. More precisely, we show that the learning curves of any given concept
class decay either at an exponential, linear, or arbitrarily slow rates.
Moreover, each of these cases is completely characterized by appropriate
combinatorial parameters, and we exhibit optimal learning algorithms that
achieve the best possible rate in each case.
For concreteness, we consider in this paper only the realizable case, though
analogous results are expected to extend to more general learning scenarios.
- Abstract(参考訳): 特定の概念のクラスが例からどのくらい早く学べるのか?
教師付き機械学習アルゴリズムの「学習曲線」、すなわち、訓練例の数の関数としての誤差率の減衰をプロットすることにより、その性能を測定するのが一般的である。
しかしながら、学習可能性を理解するための古典的な理論的枠組みであるVapnik-ChervonenkisとValiantのPACモデルは、学習曲線の振る舞いを説明していない。
これは、典型的にはデータソースが任意のシナリオで固定される機械学習の実践と一致しないが、学習者は計算資源や所望の精度といった要因に基づいて、トレーニングサンプルの数を選択することができる。
本稿では,機械学習の実用的側面をよりよく捉えるための代替学習モデルについて検討するが,それでもpacモデルの精神における学習可能性の完全な理論を導出する。
より正確には、各データ分布における学習アルゴリズムの性能を理解することを目的とした普遍学習の問題を考えるが、分布の均一性は必要としない。
この論文の主な結果は注目すべき三分法である: 普遍学習の確率は3つしかない。
より正確には、任意の概念クラスの学習曲線が指数関数的、線形的、あるいは任意に遅い速度で崩壊することを示す。
さらに,これら各ケースは適切な組合せパラメータによって完全に特徴付けられ,各ケースにおいて最適な学習率が得られる最適学習アルゴリズムを示す。
具体的には、本論文では実現可能なケースのみを考えるが、類似した結果はより一般的な学習シナリオにまで拡張されることが期待される。
関連論文リスト
- Probably Approximately Precision and Recall Learning [62.912015491907994]
精度とリコールは機械学習の基本的な指標である。
一方的なフィードバック – トレーニング中にのみ肯定的な例が観察される – は,多くの実践的な問題に固有のものだ。
PAC学習フレームワークでは,各仮説をグラフで表現し,エッジは肯定的な相互作用を示す。
論文 参考訳(メタデータ) (2024-11-20T04:21:07Z) - A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
Hamiltonian Learningはニューラルネットワークを"時間とともに"学習するための新しい統合フレームワーク
i)外部ソフトウェアソルバを必要とせずに統合できる、(ii)フィードフォワードおよびリカレントネットワークにおける勾配に基づく学習の概念を一般化する、(iii)新しい視点で開放する、という微分方程式に基づいている。
論文 参考訳(メタデータ) (2024-09-18T14:57:13Z) - Reciprocal Learning [0.0]
我々は、機械学習アルゴリズムが1つのパラダイムの特定の例であることを示す。
本稿では,これらのアルゴリズムの一般化として,決定論の言語を用いた相互学習を紹介する。
相反学習アルゴリズムは、損失関数の比較的軽度な仮定の下で、線形速度でほぼ最適なモデルに収束する。
論文 参考訳(メタデータ) (2024-08-12T16:14:52Z) - Collaborative Learning with Different Labeling Functions [7.228285747845779]
我々は、$n$のデータ分布ごとに正確な分類器を学習することを目的とした、協調型PAC学習の亜種について研究する。
データ分布がより弱い実現可能性の仮定を満たす場合、サンプル効率の学習は依然として可能であることを示す。
論文 参考訳(メタデータ) (2024-02-16T04:32:22Z) - Ticketed Learning-Unlearning Schemes [57.89421552780526]
そこで我々は,学習のためのチケット付きモデルを提案する。
広義のコンセプトクラスに対して,空間効率のよいチケット付き学習スキームを提供する。
論文 参考訳(メタデータ) (2023-06-27T18:54:40Z) - Multiclass classification utilising an estimated algorithmic probability
prior [0.5156484100374058]
我々は,アルゴリズム情報理論,特にアルゴリズム的確率が,機械学習タスクにどのように役立つかを研究する。
この研究は、アルゴリズムの確率が具体的な実世界の機械学習問題にどのように役立つかを示す最初の1つである。
論文 参考訳(メタデータ) (2022-12-14T07:50:12Z) - Less is More: Rethinking Few-Shot Learning and Recurrent Neural Nets [2.824895388993495]
情報理論AEPに基づく信頼性学習の理論的保証を提供する。
次に、高効率なリカレントニューラルネット(RNN)フレームワークに焦点を当て、少数ショット学習のための縮小エントロピーアルゴリズムを提案する。
実験結果から,学習モデルのサンプル効率,一般化,時間的複雑さを向上する可能性が示唆された。
論文 参考訳(メタデータ) (2022-09-28T17:33:11Z) - Beyond spectral gap: The role of the topology in decentralized learning [58.48291921602417]
機械学習モデルのデータ並列最適化では、労働者はモデルの推定値を改善するために協力する。
本稿では、労働者が同じデータ分散を共有するとき、疎結合な分散最適化の正確な図面を描くことを目的とする。
我々の理論は深層学習における経験的観察と一致し、異なるグラフトポロジーの相対的メリットを正確に記述する。
論文 参考訳(メタデータ) (2022-06-07T08:19:06Z) - Characterizing and overcoming the greedy nature of learning in
multi-modal deep neural networks [62.48782506095565]
深層ニューラルネットワークにおける学習の欲張った性質から、モデルは一つのモダリティにのみ依存する傾向にあり、他のモダリティには不適合であることを示す。
本稿では,学習中のモーダル間の条件付き学習速度のバランスをとるアルゴリズムを提案し,グリージー学習の問題に対処できることを実証する。
論文 参考訳(メタデータ) (2022-02-10T20:11:21Z) - On the Theory of Reinforcement Learning with Once-per-Episode Feedback [120.5537226120512]
本稿では,エピソード終盤に一度だけフィードバックを受ける強化学習の理論を紹介する。
これは、学習者が毎回フィードバックを受け取るという従来の要件よりも、現実世界のアプリケーションの代表的です。
論文 参考訳(メタデータ) (2021-05-29T19:48:51Z) - The Shape of Learning Curves: a Review [14.764764847928259]
本稿では,この用語の起源を振り返り,学習曲線の形式的定義を提供し,その推定などの基礎を概説する。
電力法や指数の形状を持つよく行動する曲線をサポートする経験的および理論的証拠について議論する。
学習曲線の学習曲線の例に特に注意を払っており、トレーニングデータが増えると学習成績が悪化する。
論文 参考訳(メタデータ) (2021-03-19T17:56:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。