要旨: 本稿では、計算量の観点から機械学習モデルの力、特に複雑なシステムをモデル化する能力を理解するためのレンズを提示します。
機械学習モデルはしばしば、計算可能な分布に限らず、サンプル可能またはより複雑な分布から引き出されたデータで学習されます。ここで扱う分布の範囲は、計算可能なものにとどまらないはるかに広いものです。計算可能な分布に焦点を当てることで、機械学習モデルは確率を通じて計算量の複雑さをより適切に管理できるようになります。本稿では、特定の学習メカニズムから切り離し、機械学習を、最大エントロピーが多項式で上界付けられた P/poly 計算可能な分布を生成するものとして抽象化します。
計算可能な分布の学習が複雑さをどのように捉えるかを説明するために、機械学習モデルが、暗号学的擬似乱数生成器によって生成された分布に対して誤差を最小化する分布 \mu を出力するならば、\mu は一様分布に近くなければならないことを示します。
機械学習は複雑性をどのように管理するのか？
arXiv cs.LG / 2026/4/9
💬 オピニオンIdeas & Deep AnalysisModels & Research
要点
- 本論文は、機械学習モデルがなぜ複雑なシステムを効果的に表現し学習できるのかを理解するための計算複雑性の枠組みを提案する。
- 論文は、現実データにしばしば見られるより広い範囲のうちの一部である、計算可能な確率分布を対象とすることで、MLは確率的構造を用いてより体系的に複雑性を管理できると主張する。
- 著者らは、特定の学習メカニズムに焦点を当てるのではなく、MLの学習を抽象的に、最大エントロピーが多項式で上から抑えられる P/poly 計算可能な分布を生成するものとしてモデル化する。
- 例示的な結果として、学習されたモデルの出力分布が、暗号学的疑似乱数生成器によって生成された分布に対して予測誤差が小さいなら、学習された分布は一様分布に近いはずだことを示す。
