机器学习如何用概率管理复杂系统？
How Does Machine Learning Manage Complexity?
- 将学习过程抽象为生成低最大熵的P/poly可计算分布
- 在密码学伪随机生成器下，模型输出趋近均匀分布
- 揭示了机器学习处理复杂性的内在机制，适合理论研究者
我们从计算复杂性视角理解机器学习模型的能力，特别是其建模复杂系统的能力。机器学习模型通常在可采样的或更复杂的分布上训练，远超可计算分布的范围。通过聚焦于可计算分布，机器学习可通过概率更好地管理复杂性。我们抽象掉具体学习机制，将机器学习建模为生成具有多项式有界最大熵的P/poly可计算分布。通过示例说明：若机器学习模型生成的分布μ对密码学伪随机生成器产生的分布误差最小，则μ必须接近均匀分布。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。