論文の概要: Computable universal online learning

• arxiv url: http://arxiv.org/abs/2510.18352v1
• Date: Tue, 21 Oct 2025 07:21:32 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-25 03:08:13.117616
• Title: Computable universal online learning
• Title（参考訳）: 計算可能なユニバーサルオンライン学習
• Authors: Dariusz Kalociński, Tomasz Steifer,
• Abstract要約: 普遍的なオンライン学習は、計算可能な普遍的なオンライン学習を含まないことを示す。 また、適切なユニバーサルオンライン学習のバリエーションを検討し、それがいつ可能かを正確に示す。
• 参考スコア（独自算出の注目度）: 1.7961752949636303
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Understanding when learning is possible is a fundamental task in the theory of machine learning. However, many characterizations known from the literature deal with abstract learning as a mathematical object and ignore the crucial question: when can learning be implemented as a computer program? We address this question for universal online learning, a generalist theoretical model of online binary classification, recently characterized by Bousquet et al. (STOC'21). In this model, there is no hypothesis fixed in advance; instead, Adversary -- playing the role of Nature -- can change their mind as long as local consistency with the given class of hypotheses is maintained. We require Learner to achieve a finite number of mistakes while using a strategy that can be implemented as a computer program. We show that universal online learning does not imply computable universal online learning, even if the class of hypotheses is relatively easy from a computability-theoretic perspective. We then study the agnostic variant of computable universal online learning and provide an exact characterization of classes that are learnable in this sense. We also consider a variant of proper universal online learning and show exactly when it is possible. Together, our results give a more realistic perspective on the existing theory of online binary classification and the related problem of inductive inference.
• Abstract（参考訳）: 学習可能なときの理解は、機械学習の理論における基本的な課題である。 しかし、文献から知られている多くの特徴は、抽象的な学習を数学的対象として扱い、重要な疑問を無視している。 本稿では,Bousquet et al (STOC'21) を特徴とするオンライン二項分類の一般理論モデルであるユニバーサルオンライン学習について考察する。 このモデルでは、事前に固定された仮説は存在しない。代わりに、自然の役割を果たす逆説は、与えられた仮説のクラスとの局所的な整合性を維持する限り、彼らの心を変えることができる。 我々は,コンピュータプログラムとして実装可能な戦略を用いて,学習者が有限個の誤りを犯す必要がある。 計算可能性理論の観点から、仮説のクラスが比較的容易であっても、普遍的なオンライン学習は計算可能な普遍的なオンライン学習を暗示しないことを示す。 次に、計算可能なユニバーサルオンライン学習の非依存的変種について研究し、この意味で学習可能なクラスを正確に評価する。 また、適切なユニバーサルオンライン学習のバリエーションを検討し、それがいつ可能かを正確に示す。 その結果,既存のオンライン二項分類理論と帰納的推論の問題に関して,より現実的な視点が得られた。

関連論文リスト

• A Theory of Optimistically Universal Online Learnability for General Concept Classes [15.830099254570955]
  我々は、0, 1$ラベルで楽観的にオンライン学習可能な概念クラスの完全な特徴付けを提供する。 楽観的に普遍的なオンライン学習の概念は[Hanneke, 2021]で定義され, 最小限の仮定の下で学習可能性を理解する。
  論文  参考訳（メタデータ） (2025-01-15T03:20:16Z)
• A Unified Framework for Neural Computation and Learning Over Time [56.44910327178975]
  Hamiltonian Learningはニューラルネットワークを"時間とともに"学習するための新しい統合フレームワーク i)外部ソフトウェアソルバを必要とせずに統合できる、(ii)フィードフォワードおよびリカレントネットワークにおける勾配に基づく学習の概念を一般化する、(iii)新しい視点で開放する、という微分方程式に基づいている。
  論文  参考訳（メタデータ） (2024-09-18T14:57:13Z)
• Ticketed Learning-Unlearning Schemes [57.89421552780526]
  そこで我々は,学習のためのチケット付きモデルを提案する。 広義のコンセプトクラスに対して,空間効率のよいチケット付き学習スキームを提供する。
  論文  参考訳（メタデータ） (2023-06-27T18:54:40Z)
• Learnability with Time-Sharing Computational Resource Concerns [65.268245109828]
  本稿では,学習理論における計算資源の影響を考慮した理論的枠組みを提案する。 このフレームワークは、入ってくるデータストリームが潜在的に無限であるようなストリーム学習に自然に適用できる。 これはまた、インテリジェントなスーパーコンピュータオペレーティングシステムの設計に対する理論的視点を提供するかもしれない。
  論文  参考訳（メタデータ） (2023-05-03T15:54:23Z)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  ニューラルネットワークモデルは、Kolmogorov複雑性を使って形式化された、同じ好みを共有している、と我々は主張する。 実験の結果、事前訓練された言語モデルでも、低複雑さのシーケンスを生成するのが好まれることがわかった。 これらの観察は、ますます小さな機械学習モデルで異なるように見える問題を統一する深層学習の傾向を正当化する。
  論文  参考訳（メタデータ） (2023-04-11T17:22:22Z)
• Universal Online Learning: an Optimistically Universal Learning Rule [0.0]
  本研究では,非i.d.プロセスを用いたユニバーサルオンライン学習の課題について検討する。 k-nearest neighbor algorithm (kNN) は楽観的に普遍的ではなく, 1NN の新たな変種を示す。
  論文  参考訳（メタデータ） (2022-01-16T02:13:47Z)
• From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability [0.0]
  新たに提案したモデルが実際にデータから学べるかどうかを厳格に評価するための汎用的な手順は存在しないことを示す。 PACバイナリ分類、一様および普遍的なオンライン学習、教師と教師の相互作用による正確な学習では、学習性は一般に決定不可能である。 機械学習モデルが成功するかどうかを決定するのに、すべてに適したアルゴリズムは存在しない。
  論文  参考訳（メタデータ） (2021-06-02T18:00:04Z)
• Exploring Bayesian Deep Learning for Urgent Instructor Intervention Need in MOOC Forums [58.221459787471254]
  大規模なオープンオンラインコース(MOOC)は、その柔軟性のおかげで、eラーニングの一般的な選択肢となっている。 多くの学習者とその多様な背景から、リアルタイムサポートの提供は課税されている。 MOOCインストラクターの大量の投稿と高い作業負荷により、インストラクターが介入を必要とするすべての学習者を識別できる可能性は低いです。 本稿では,モンテカルロドロップアウトと変分推論という2つの手法を用いて,学習者によるテキスト投稿のベイジアン深層学習を初めて検討する。
  論文  参考訳（メタデータ） (2021-04-26T15:12:13Z)
• A Theory of Universal Learning [26.51949485387526]
  普遍的な学習の確率は3つしかないことを示す。 任意の概念クラスの学習曲線は指数的あるいは任意に遅い速度で減衰することを示す。
  論文  参考訳（メタデータ） (2020-11-09T15:10:32Z)

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

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