論文の概要: From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability

• arxiv url: http://arxiv.org/abs/2106.01382v3
• Date: Tue, 17 Oct 2023 03:47:29 GMT
• ステータス: 処理完了
• システム内更新日: 2023-10-19 01:02:21.368390
• Title: From Undecidability of Non-Triviality and Finiteness to Undecidability of Learnability
• Title（参考訳）: 未知の非決定性と有限性から学習可能性の不決定性へ
• Authors: Matthias C. Caro
• Abstract要約: 新たに提案したモデルが実際にデータから学べるかどうかを厳格に評価するための汎用的な手順は存在しないことを示す。 PACバイナリ分類、一様および普遍的なオンライン学習、教師と教師の相互作用による正確な学習では、学習性は一般に決定不可能である。 機械学習モデルが成功するかどうかを決定するのに、すべてに適したアルゴリズムは存在しない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Machine learning researchers and practitioners steadily enlarge the multitude of successful learning models. They achieve this through in-depth theoretical analyses and experiential heuristics. However, there is no known general-purpose procedure for rigorously evaluating whether newly proposed models indeed successfully learn from data. We show that such a procedure cannot exist. For PAC binary classification, uniform and universal online learning, and exact learning through teacher-learner interactions, learnability is in general undecidable, both in the sense of independence of the axioms in a formal system and in the sense of uncomputability. Our proofs proceed via computable constructions that encode the consistency problem for formal systems and the halting problem for Turing machines into whether certain function classes are trivial/finite or highly complex, which we then relate to whether these classes are learnable via established characterizations of learnability through complexity measures. Our work shows that undecidability appears in the theoretical foundations of artificial intelligence: There is no one-size-fits-all algorithm for deciding whether a machine learning model can be successful. We cannot in general automatize the process of assessing new learning models.
• Abstract（参考訳）: 機械学習の研究者や実践者は、さまざまな学習モデルを着実に拡大している。 彼らはこれを深い理論分析と経験的ヒューリスティックを通して達成した。 しかし、新たに提案されたモデルが実際にデータから学べるかどうかを厳格に評価するための汎用的な手順は知られていない。 そのような手続きは存在しないことを示す。 PACのバイナリ分類、一様および普遍的なオンライン学習、および教師と教師の相互作用による正確な学習においては、学習性は一般に、形式的なシステムにおける公理の独立性や計算不可能性の両方において決定不可能である。 我々の証明は、形式システムの一貫性問題とチューリングマシンの停止問題をエンコードした計算可能構成を通じて、ある関数クラスが自明かつ有限であるか、あるいは非常に複雑であるかを証明し、それらのクラスが、複雑度測定による学習可能性の確立された特性を通して学習可能かどうかに関連づける。 私たちの研究は、人工知能の理論的な基盤に決定不能が現れていることを示しています。 新しい学習モデルを評価するプロセスを一般的に自動化することはできません。

関連論文リスト

• Limits and Powers of Koopman Learning [0.0]
  力学系は様々な科学にまたがって複雑で変化する振る舞いを研究する包括的方法を提供する。 クープマン作用素は、線形手法を用いた非線形力学の研究を可能にするため、支配的なアプローチとして現れてきた。 テキスト 動的システムの軌道データからクープマン作用素のスペクトル特性を頑健に学習することは可能か?
  論文  参考訳（メタデータ） (2024-07-08T18:24:48Z)
• Identifiable Causal Representation Learning: Unsupervised, Multi-View, and Multi-Environment [10.814585613336778]
  因果表現学習は、機械学習のコアとなる強みと因果性を組み合わせることを目的としている。 この論文は、CRLが直接の監督なしに何が可能であるかを調査し、理論的基礎に寄与する。
  論文  参考訳（メタデータ） (2024-06-19T09:14:40Z)
• Incremental procedural and sensorimotor learning in cognitive humanoid robots [52.77024349608834]
  本研究は,手順を段階的に学習する認知エージェントを提案する。 各サブステージで必要とされる認知機能と, エージェントが未解決の課題に, 新たな機能の追加がどう対処するかを示す。 結果は、このアプローチが複雑なタスクを段階的に解くことができることを示している。
  論文  参考訳（メタデータ） (2023-04-30T22:51:31Z)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  ニューラルネットワークモデルは、Kolmogorov複雑性を使って形式化された、同じ好みを共有している、と我々は主張する。 実験の結果、事前訓練された言語モデルでも、低複雑さのシーケンスを生成するのが好まれることがわかった。 これらの観察は、ますます小さな機械学習モデルで異なるように見える問題を統一する深層学習の傾向を正当化する。
  論文  参考訳（メタデータ） (2023-04-11T17:22:22Z)
• Stabilizing Q-learning with Linear Architectures for Provably Efficient Learning [53.17258888552998]
  本研究では,線形関数近似を用いた基本的な$Q$-learningプロトコルの探索変種を提案する。 このアルゴリズムの性能は,新しい近似誤差というより寛容な概念の下で,非常に優雅に低下することを示す。
  論文  参考訳（メタデータ） (2022-06-01T23:26:51Z)
• Continual Learning for Real-World Autonomous Systems: Algorithms, Challenges and Frameworks [15.276951055528237]
  我々は、時間とともに計算モデルの継続的な学習を可能にする最先端の手法についてレビューする。 我々は、かなり大きな(あるいは無限の)シーケンシャルデータからオンライン形式で継続的学習を行う学習アルゴリズムに焦点を当てる。 我々は、自律現実システムにおける継続的学習に関連する重要な課題を批判的に分析する。
  論文  参考訳（メタデータ） (2021-05-26T07:38:20Z)
• Knowledge as Invariance -- History and Perspectives of Knowledge-augmented Machine Learning [69.99522650448213]
  機械学習の研究は転換点にある。 研究の関心は、高度にパラメータ化されたモデルのパフォーマンス向上から、非常に具体的なタスクへとシフトしている。 このホワイトペーパーは、機械学習研究におけるこの新興分野の紹介と議論を提供する。
  論文  参考訳（メタデータ） (2020-12-21T15:07:19Z)
• Verification of ML Systems via Reparameterization [6.482926592121413]
  確率的プログラムを定理証明器で自動的に表現する方法を示す。 また、ベイズ仮説テストで用いられるヌルモデルは、人口統計学的パリティ(英語版)と呼ばれる公平性基準を満たすことを証明した。
  論文  参考訳（メタデータ） (2020-07-14T02:19:25Z)
• Efficient Model-Based Reinforcement Learning through Optimistic Policy Search and Planning [93.1435980666675]
  最先端の強化学習アルゴリズムと楽観的な探索を容易に組み合わせることができることを示す。 我々の実験は、楽観的な探索が行動に罰則がある場合、学習を著しくスピードアップすることを示した。
  論文  参考訳（メタデータ） (2020-06-15T18:37:38Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

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