論文の概要: How Does Machine Learning Manage Complexity?

• arxiv url: http://arxiv.org/abs/2604.07233v1
• Date: Wed, 08 Apr 2026 15:57:24 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-09 17:30:51.619492
• Title: How Does Machine Learning Manage Complexity?
• Title（参考訳）: 機械学習はどのように複雑さを管理するのか?
• Authors: Lance Fortnow,
• Abstract要約: 機械学習モデルのパワーを理解するための計算複雑性レンズを提供する。 機械学習モデルが暗号擬似乱数生成器が生成した分布に対する誤差を最小限に抑える分布を$$とするなら、$は均一にしなければならない。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: We provide a computational complexity lens to understand the power of machine learning models, particularly their ability to model complex systems. Machine learning models are often trained on data drawn from sampleable or more complex distributions, a far wider range of distributions than just computable ones. By focusing on computable distributions, machine learning models can better manage complexity via probability. We abstract away from specific learning mechanisms, modeling machine learning as producing P/poly-computable distributions with polynomially-bounded max-entropy. We illustrate how learning computable distributions models complexity by showing that if a machine learning model produces a distribution $μ$ that minimizes error against the distribution generated by a cryptographic pseudorandom generator, then $μ$ must be close to uniform.
• Abstract（参考訳）: 我々は、機械学習モデルのパワー、特に複雑なシステムをモデル化する能力を理解するために、計算複雑性レンズを提供する。 機械学習モデルは、単に計算可能なものよりもはるかに広い範囲の分布であるサンプリング可能な、あるいはより複雑な分布から引き出されたデータに基づいて訓練されることが多い。 計算可能な分散に集中することにより、機械学習モデルは確率によって複雑さを管理することができる。 我々は、特定の学習メカニズムを抽象化し、多項式有界最大エントロピーを持つP/poly計算可能な分布を生成する機械学習をモデル化する。 機械学習モデルが暗号擬似乱数生成器が生成する分布に対する誤差を最小限に抑えるために$μ$を生成すれば、$μ$は均一でなければならないことを示す。

関連論文リスト

• On Stronger Computational Separations Between Multimodal and Unimodal Machine Learning [0.0]
  Lu (NeurIPS '23, ALT '24) はマルチモーダル学習の理論を導入する。 特に、Lu(ALT '24)は、学習タスクのtextitworst-caseインスタンスに関連する計算分離を示す。 基礎的な条件下では、平均ケースのユニモーダルとマルチモーダルの学習タスク間の任意の計算的分離が対応する暗号鍵合意プロトコルを意味することを証明している。
  論文  参考訳（メタデータ） (2024-04-02T19:21:28Z)
• The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning [80.1018596899899]
  ニューラルネットワークモデルは、Kolmogorov複雑性を使って形式化された、同じ好みを共有している、と我々は主張する。 実験の結果、事前訓練された言語モデルでも、低複雑さのシーケンスを生成するのが好まれることがわかった。 これらの観察は、ますます小さな機械学習モデルで異なるように見える問題を統一する深層学習の傾向を正当化する。
  論文  参考訳（メタデータ） (2023-04-11T17:22:22Z)
• How Does Independence Help Generalization? Sample Complexity of ERM on Product Distributions [5.553167334488855]
  経験的リスク最小化(ERM)は製品分布を学習するために指数的なサンプル数を必要とするが,製品分布に特化して設計されたアルゴリズムが必要であることを示す。 これにより、製品配布自体が学習問題を容易なものにしないという結論が導かれる。
  論文  参考訳（メタデータ） (2022-12-13T08:14:32Z)
• On-Demand Sampling: Learning Optimally from Multiple Distributions [63.20009081099896]
  社会と現実世界の考察は、マルチディストリビューション学習パラダイムの台頭につながっている。 これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。 アルゴリズムの設計と解析は,ゼロサムゲーム解決のためのオンライン学習手法の拡張によって実現されている。
  論文  参考訳（メタデータ） (2022-10-22T19:07:26Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  この研究は、大規模構造化モデルの計算とメモリの複雑さを低減するための単純なアプローチを示す。 言語モデリング,ポリフォニック・ミュージック・モデリング,教師なし文法帰納法,ビデオ・モデリングのためのニューラルパラメータ構造モデルを用いた実験により,我々の手法は大規模状態空間における標準モデルの精度と一致することを示した。
  論文  参考訳（メタデータ） (2022-01-08T00:47:50Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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