論文の概要: Refined Kolmogorov Complexity of Analog, Evolving and Stochastic
Recurrent Neural Networks
- arxiv url: http://arxiv.org/abs/2309.17032v1
- Date: Fri, 29 Sep 2023 07:38:50 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-02 15:05:21.853791
- Title: Refined Kolmogorov Complexity of Analog, Evolving and Stochastic
Recurrent Neural Networks
- Title（参考訳）: アナログ, 進化, 確率的リカレントニューラルネットワークの精製コルモゴロフ複素性
- Authors: J\'er\'emie Cabessa, Yann Strozecki
- Abstract要約: 我々は, 実重のコルモゴロフ複雑性, 進化重み, 実確率に基づいて, アナログ, 進化, ニューラルネットワークの超チューリング計算能力の洗練された特徴付けを行う。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We provide a refined characterization of the super-Turing computational power
of analog, evolving, and stochastic neural networks based on the Kolmogorov
complexity of their real weights, evolving weights, and real probabilities,
respectively. First, we retrieve an infinite hierarchy of classes of analog
networks defined in terms of the Kolmogorov complexity of their underlying real
weights. This hierarchy is located between the complexity classes $\mathbf{P}$
and $\mathbf{P/poly}$. Then, we generalize this result to the case of evolving
networks. A similar hierarchy of Kolomogorov-based complexity classes of
evolving networks is obtained. This hierarchy also lies between $\mathbf{P}$
and $\mathbf{P/poly}$. Finally, we extend these results to the case of
stochastic networks employing real probabilities as source of randomness. An
infinite hierarchy of stochastic networks based on the Kolmogorov complexity of
their probabilities is therefore achieved. In this case, the hierarchy bridges
the gap between $\mathbf{BPP}$ and $\mathbf{BPP/log^*}$. Beyond proving the
existence and providing examples of such hierarchies, we describe a generic way
of constructing them based on classes of functions of increasing complexity.
For the sake of clarity, this study is formulated within the framework of echo
state networks. Overall, this paper intends to fill the missing results and
provide a unified view about the refined capabilities of analog, evolving and
stochastic neural networks.
- Abstract（参考訳）: 本稿では,実重み,重み,実確率のコルモゴロフ複雑性に基づく,アナログ,進化,確率的ニューラルネットワークの超チューリング計算能力の洗練された特性について述べる。
まず、基礎となる実重みのコルモゴロフ複雑性の観点から定義されるアナログネットワークのクラスの無限階層を取得する。
この階層は複雑性クラス $\mathbf{P}$ と $\mathbf{P/poly}$ の間に位置する。
そして、この結果を進化するネットワークのケースに一般化する。
進化するネットワークのコロモゴロフベースの複雑性クラスの類似した階層が得られた。
この階層はまた、$\mathbf{P}$と$\mathbf{P/poly}$の間にある。
最後に,実確率をランダム性源とする確率ネットワークの場合には,これらの結果を拡張する。
したがって、その確率のコルモゴロフ複雑性に基づく確率ネットワークの無限階層が達成される。
この場合、階層構造は$\mathbf{bpp}$と$\mathbf{bpp/log^*}$の間のギャップを橋渡しする。
このような階層の存在の証明と実例を提供する以外に、複雑性を増大させる関数のクラスに基づいてそれらを構築する一般的な方法を記述する。
明確にするために、この研究はエコー状態ネットワークの枠組みの中で定式化されている。
本研究の目的は, アナログ, 進化, 確率的ニューラルネットワークの洗練された能力に関する統一的な視点を提供することである。
関連論文リスト
- Pruning is Optimal for Learning Sparse Features in High-Dimensions [15.967123173054535]
本研究では,勾配勾配勾配で学習したプルーンドニューラルネットワークを用いて,統計モデルのクラスを最適に学習可能であることを示す。
ニューラルネットワークのプルーニングが$boldsymbolV$のスパーシリティレベルに比例すると、未切断ネットワークと比較してサンプルの複雑さが向上することを示す。
論文 参考訳（メタデータ） (2024-06-12T21:43:12Z) - Defining Neural Network Architecture through Polytope Structures of Dataset [53.512432492636236]
本稿では, ニューラルネットワーク幅の上下境界を定義し, 問題となるデータセットのポリトープ構造から情報を得る。
本研究では,データセットのポリトープ構造を学習したニューラルネットワークから推定できる逆条件を探索するアルゴリズムを開発した。
MNIST、Fashion-MNIST、CIFAR10といった一般的なデータセットは、顔の少ない2つ以上のポリトップを用いて効率的にカプセル化できることが確立されている。
論文 参考訳（メタデータ） (2024-02-04T08:57:42Z) - Structural Balance and Random Walks on Complex Networks with Complex
Weights [13.654842079699458]
近年、エッジの重みが複素数である場合、ネットワーク科学のツールを拡張することへの関心が高まっている。
ここでは、重み行列がエルミート行列である場合に注目し、多くの応用において妥当な仮定である。
構造バランスの概念に基づいて,複素重み付きネットワークの分類を導入し,各タイプの共有スペクトル特性を示す。
論文 参考訳（メタデータ） (2023-07-04T16:39:52Z) - Polyhedral Complex Extraction from ReLU Networks using Edge Subdivision [0.0]
ニューラルネットワークは、完全接続層やReLUアクティベーションなど、断片的にアフィン構造ブロックで構成されている。
この複合体は、ニューラルネットワークの理論的性質を特徴づけるために以前に研究されてきた。
本稿では,各ニューロンによって誘導される超平面との交点を介して領域を分割することを提案する。
論文 参考訳（メタデータ） (2023-06-12T16:17:04Z) - Computational Complexity of Learning Neural Networks: Smoothness and
Degeneracy [52.40331776572531]
ガウス入力分布下での学習深度3$ReLUネットワークはスムーズな解析フレームワークにおいても困難であることを示す。
この結果は, 局所擬似乱数発生器の存在についてよく研究されている。
論文 参考訳（メタデータ） (2023-02-15T02:00:26Z) - Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
単純複体は多方向順序関係を明示的にエンコードするグラフの高次元一般化と見なすことができる。
単体錯体の$k$-homological特徴によってパラメータ化された関数のグラフ畳み込みモデルを提案する。
論文 参考訳（メタデータ） (2021-10-28T14:59:41Z) - Dive into Layers: Neural Network Capacity Bounding using Algebraic
Geometry [55.57953219617467]
ニューラルネットワークの学習性はそのサイズと直接関連していることを示す。
入力データとニューラルネットワークのトポロジ的幾何学的複雑さを測定するためにベッチ数を用いる。
実世界のデータセットMNISTで実験を行い、分析結果と結論を検証した。
論文 参考訳（メタデータ） (2021-09-03T11:45:51Z) - The Separation Capacity of Random Neural Networks [78.25060223808936]
標準ガウス重みと一様分布バイアスを持つ十分に大きな2層ReLUネットワークは、この問題を高い確率で解くことができることを示す。
我々は、相互複雑性という新しい概念の観点から、データの関連構造を定量化する。
論文 参考訳（メタデータ） (2021-07-31T10:25:26Z) - On Function Approximation in Reinforcement Learning: Optimism in the
Face of Large State Spaces [208.67848059021915]
強化学習のコアにおける探索・探索トレードオフについて検討する。
特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。
私たちの後悔の限界はエピソードの数とは無関係です。
論文 参考訳（メタデータ） (2020-11-09T18:32:22Z) - Consistency of Spectral Clustering on Hierarchical Stochastic Block
Models [5.983753938303726]
実世界のネットワークにおけるコミュニティの階層構造について,汎用ブロックモデルを用いて検討する。
本手法の強い一貫性を,幅広いモデルパラメータで証明する。
既存のほとんどの研究とは異なり、我々の理論は接続確率が桁違いに異なるかもしれないマルチスケールネットワークをカバーしている。
論文 参考訳（メタデータ） (2020-04-30T01:08:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。