論文の概要: Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis
- arxiv url: http://arxiv.org/abs/2605.15551v1
- Date: Fri, 15 May 2026 02:44:25 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-05-18 21:22:26.151141
- Title: Characterizing Learning in Deep Neural Networks using Tractable Algorithmic Complexity Analysis
- Title（参考訳）: トラクタブルアルゴリズム複雑度解析を用いたディープニューラルネットワークの学習特性評価
- Authors: Pedram Bakhtiarifard, Sophia N. Wilson, Mahmoud Afifi, Jonathan Wenshøj, Raghavendra Selvan,
- Abstract要約: 我々はQuantized Block Decomposition法(QuBD)を導入し、アルゴリズムによる複雑性推定を任意の$k$-aryオブジェクトに拡張する。
理論的には、QuBDは二項化法よりも真のコルモゴロフ・シャイティン・ソロモノフ(KCS)複雑性に対して厳密な推定ギャップを生じる。
- 参考スコア（独自算出の注目度）: 9.735454755526954
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Training large-scale deep neural networks (DNNs) is resource-intensive, making model compression a practical necessity. The widely accepted ''learning as compression'' hypothesis posits that training induces structure in network weights, which enables compression. Measuring this structure through Kolmogorov-Chaitin-Solomonoff (KCS) complexity is appealing, but existing estimators based on the Coding Theorem Method (CTM) and the Block Decomposition Method (BDM) are limited to small binary objects and do not scale to modern DNNs. We introduce the Quantized Block Decomposition method (QuBD), which extends algorithmic complexity estimation to any $k$-ary object. QuBD first quantizes the network weights to a finite alphabet, then estimates the KCS complexity by aggregating per bit-plane CTM estimates. We show theoretically that QuBD yields a strictly tighter estimation gap with respect to true KCS complexity than binarization-based methods. Using QuBD, we study how the algorithmic complexity of neural network weights evolves during training, showing that it decreases as models learn, scales with data budget, increases during overfitting, follows the delayed generalization observed during grokking, and correlates with generalization performance. We further show that algorithmic information resides predominantly in the most significant bit-planes, which can serve as a practical diagnostic for determining appropriate post-training quantization levels. This work offers novel insights into learning mechanisms in DNNs by providing the first scalable, tractable estimates of KCS complexity for large, non-binary objects such as DNN weights.
- Abstract（参考訳）: 大規模ディープニューラルネットワーク(DNN)のトレーニングはリソース集約的であり、モデル圧縮が現実的に必要となる。
広く受け入れられている「圧縮としての学習」仮説は、トレーニングがネットワーク重みの構造を誘導し、圧縮を可能にするという仮説である。
この構造をKCS(Kolmogorov-Chaitin-Solomonoff)の複雑性によって測定することは魅力的であるが、Coding Theorem Method(CTM)とBlock Decomposition Method(BDM)に基づく既存の推定器は、小さなバイナリオブジェクトに限られており、現在のDNNには拡張されない。
我々はQuantized Block Decomposition法(QuBD)を導入し、アルゴリズムによる複雑性推定を任意の$k$-aryオブジェクトに拡張する。
QuBDはまず、ネットワークの重みを有限のアルファベットに量子化し、次にビット平面のCTM推定を集約することでKCSの複雑さを推定する。
理論的には、QuBD は二項化法よりも真の KCS の複雑性に対して厳密な推定ギャップを生じる。
QuBDを用いて、トレーニング中にニューラルネットワークの重みのアルゴリズム的複雑さがどのように進化するかを検証し、モデル学習時に減少し、データ予算でスケールし、オーバーフィッティング時に増大し、グルーキング時に観測される一般化の遅れに追従し、一般化性能と相関することを示す。
さらに、アルゴリズム情報は、主に最も重要なビットプレーンに存在し、トレーニング後の適切な量子化レベルを決定するための実用的な診断として役立てることができることを示す。
この研究は、DNNの重みのような大型で非バイナリなオブジェクトに対して、初めてスケーラブルでトラクタブルなKCS複雑性の推定を提供することによって、DNNの学習メカニズムに関する新たな洞察を提供する。
関連論文リスト
- Performance Analysis of Convolutional Neural Network By Applying Unconstrained Binary Quadratic Programming [0.0]
畳み込みニューラルネットワーク(CNN)は、コンピュータビジョンとビッグデータ分析において重要であるが、大規模なデータセットでトレーニングされた場合には、かなりの計算リソースを必要とする。
CNNトレーニングを高速化するために,Unconstrained Binary Quadratic Programming (UBQP) と Gradient Descent (SGD) を組み合わせたハイブリッド最適化手法を提案する。
提案手法は, BP-CNNベースラインの10-15%の精度向上を実現し, 同様の実行時間を維持する。
論文 参考訳（メタデータ） (2025-05-30T21:25:31Z) - 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) - Information Bottleneck Analysis of Deep Neural Networks via Lossy Compression [37.69303106863453]
Information Bottleneck(IB)原則は、ディープニューラルネットワーク(DNN)のトレーニングプロセスを分析するための情報理論フレームワークを提供する。
本稿では,一般NNのICB解析を行うためのフレームワークを提案する。
また,MI力学の新たな特徴を明らかにするため,実規模に近いISB解析を行う。
論文 参考訳（メタデータ） (2023-05-13T21:44:32Z) - Joint Edge-Model Sparse Learning is Provably Efficient for Graph Neural
Networks [89.28881869440433]
本稿では,グラフニューラルネットワーク(GNN)における結合エッジモデルスパース学習の理論的特徴について述べる。
解析学的には、重要なノードをサンプリングし、最小のマグニチュードでプルーニングニューロンをサンプリングすることで、サンプルの複雑さを減らし、テスト精度を損なうことなく収束を改善することができる。
論文 参考訳（メタデータ） (2023-02-06T16:54:20Z) - Gradient Descent in Neural Networks as Sequential Learning in RKBS [63.011641517977644]
初期重みの有限近傍にニューラルネットワークの正確な電力系列表現を構築する。
幅にかかわらず、勾配降下によって生成されたトレーニングシーケンスは、正規化された逐次学習によって正確に複製可能であることを証明した。
論文 参考訳（メタデータ） (2023-02-01T03:18:07Z) - A Comprehensive Survey on Model Quantization for Deep Neural Networks in
Image Classification [0.0]
有望なアプローチは量子化であり、完全な精度の値は低ビット幅の精度で保存される。
本稿では、画像分類に焦点をあてて、量子化の概念と方法に関する包括的調査を行う。
本稿では,量子化DNNにおける浮動小数点演算の低コストなビット演算への置き換えと,量子化における異なる層の感度について説明する。
論文 参考訳（メタデータ） (2022-05-14T15:08:32Z) - Compact representations of convolutional neural networks via weight
pruning and quantization [63.417651529192014]
本稿では、音源符号化に基づく畳み込みニューラルネットワーク(CNN)の新しいストレージフォーマットを提案し、重み付けと量子化の両方を活用する。
我々は、全接続層で0.6%、ネットワーク全体で5.44%のスペース占有率を削減し、最低でもベースラインと同じくらいの競争力を発揮する。
論文 参考訳（メタデータ） (2021-08-28T20:39:54Z) - Neural Complexity Measures [96.06344259626127]
本稿では,一般化を予測するメタラーニングフレームワークであるNeural Complexity(NC)を提案する。
我々のモデルは、データ駆動方式で、多くの異種タスクとの相互作用を通じてスカラー複雑性尺度を学習する。
論文 参考訳（メタデータ） (2020-08-07T02:12:10Z) - Understanding Generalization in Deep Learning via Tensor Methods [53.808840694241]
圧縮の観点から,ネットワークアーキテクチャと一般化可能性の関係について理解を深める。
本稿では、ニューラルネットワークの圧縮性と一般化性を強く特徴付ける、直感的で、データ依存的で、測定が容易な一連の特性を提案する。
論文 参考訳（メタデータ） (2020-01-14T22:26:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。