論文の概要: Learning, Compression, and Meta-Complexity

• arxiv url: http://arxiv.org/abs/2610.16535v1
• Date: Mon, 12 Oct 2026 10:23:04 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-18 22:41:14.063176
• Title: Learning, Compression, and Meta-Complexity
• Title（参考訳）: 学習・圧縮・メタ複雑さ
• Abstract要約: 直観を数学的に正確にできるような設定に焦点をあてる。 中心的なテーマは、学習と複雑性の間の橋渡しとしてのデータ圧縮の役割である。
• 参考スコア（独自算出の注目度）: 0.6882042556551609
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The idea that learning is closely tied to compression has long served as both a powerful principle and, at times, an informal analogy across machine learning and learning theory. Here we focus on settings in which that intuition can be made mathematically precise, surveying formal connections among learning algorithms, data compression, and computational complexity theory, with an emphasis on recent progress and current frontiers. We describe how techniques from complexity theory can guide the design of both supervised and unsupervised learning algorithms with provable guarantees, and conversely, how learning algorithms can yield new insights and results in complexity theory. A central theme is the role of data compression as a bridge between learning and complexity, especially through an area called meta-complexity, which studies the computational difficulty of compression problems and time-bounded variants of Kolmogorov complexity.
• Abstract（参考訳）: 学習は圧縮と密接に結びついているという考えは、長い間強力な原理であり、機械学習と学習理論をまたいだ非公式なアナロジーとして機能してきた。 ここでは、その直観を数学的に正確にし、最近の進歩と現在のフロンティアに重点を置いて、学習アルゴリズム、データ圧縮、計算複雑性理論の間の公式な関係を調査する設定に焦点を当てる。 複雑性理論のテクニックは、教師付き学習アルゴリズムと教師なし学習アルゴリズムの両方の設計を証明可能な保証でガイドし、逆に、学習アルゴリズムが複雑性理論の新たな洞察と結果を得る方法を説明する。 中心的なテーマは、学習と複雑性の間の橋渡しとしてのデータ圧縮の役割であり、特にメタ複雑度と呼ばれる領域を通して、圧縮問題の計算困難さとコルモゴロフ複雑性の時間境界変量を研究する。

関連論文リスト

• Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis [33.73453802399709]
  本稿では,二元化ニューラルネットワーク(BNN)を第1のプロキシとして用いて,アルゴリズム情報理論へのシフトを提案する。 ブロック分解法 (BDM) を適用し, エントロピーよりもトレーニング中の構造変化をより綿密に追跡した。 これらの結果は、学習が構造化正規性の進行的内部化に対応するアルゴリズム圧縮の過程としてのトレーニングの観点を支持する。
  論文  参考訳（メタデータ） (2025-05-27T02:51:36Z)
• When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
  本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。 具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。 コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
  論文  参考訳（メタデータ） (2023-08-29T17:22:39Z)
• A Parameterized Theory of PAC Learning [19.686465068713467]
  おそらく略正(PAC)学習は、サンプル複雑性理論の中核的な概念である。 我々は、パラメータ化複雑性の要素を組み込んだ最近のPAC学習結果に新たな光を当てることができるパラメータ化PAC学習の理論を開発した。
  論文  参考訳（メタデータ） (2023-04-27T09:39:30Z)
• Evolutionary Training and Abstraction Yields Algorithmic Generalization of Neural Computers [26.829064000815272]
  知的行動の重要な特徴は、未知の問題にスケールして移行する抽象的な戦略を学ぶ能力である。 メモリ拡張型ネットワークベースのアーキテクチャであるNeural Harvard Computerを紹介する。 NHCは強力な一般化と抽象化を備えたアルゴリズム解を確実に学習することを示す。
  論文  参考訳（メタデータ） (2021-05-17T15:37:32Z)
• Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning [96.78504087416654]
  強化学習(RL)問題における効率的な探索に教師なし学習を用い,本パラダイムが有効であるかどうかを考察する。 本稿では,教師なし学習アルゴリズムと非線形表RLアルゴリズムという,2つのコンポーネント上に構築された汎用的なアルゴリズムフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-03-15T19:23:59Z)

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

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