論文の概要: PAC-learning gains of Turing machines over circuits and neural networks

• arxiv url: http://arxiv.org/abs/2103.12686v1
• Date: Tue, 23 Mar 2021 17:03:10 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-24 17:05:17.972168
• Title: PAC-learning gains of Turing machines over circuits and neural networks
• Title（参考訳）: チューリングマシンの回路およびニューラルネットワークによるPAC学習ゲイン
• Authors: Brieuc Pinon and Jean-Charles Delvenne and Rapha\"el Jungers
• Abstract要約: 私達は最低記述の長さの原則を持って来ることができるサンプル効率の潜在的な利益を研究します。 我々はチューリングマシンを用いて普遍的なモデルと回路を表現する。 回路の複雑さと密接性における古典的オープン問題との密接な関係を浮き彫りにする。
• 参考スコア（独自算出の注目度）: 1.4502611532302039
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A caveat to many applications of the current Deep Learning approach is the need for large-scale data. One improvement suggested by Kolmogorov Complexity results is to apply the minimum description length principle with computationally universal models. We study the potential gains in sample efficiency that this approach can bring in principle. We use polynomial-time Turing machines to represent computationally universal models and Boolean circuits to represent Artificial Neural Networks (ANNs) acting on finite-precision digits. Our analysis unravels direct links between our question and Computational Complexity results. We provide lower and upper bounds on the potential gains in sample efficiency between the MDL applied with Turing machines instead of ANNs. Our bounds depend on the bit-size of the input of the Boolean function to be learned. Furthermore, we highlight close relationships between classical open problems in Circuit Complexity and the tightness of these.
• Abstract（参考訳）: 現在のDeep Learningアプローチの多くのアプリケーションに注意すべき点は、大規模なデータが必要であることだ。 コルモゴロフの複雑性の結果から示唆される改善の1つは、最小記述長原理を計算的普遍モデルに適用することである。 このアプローチが原則としてもたらすことのできるサンプル効率の潜在的な向上について検討する。 多項式時間チューリングマシンを用いて計算の普遍的モデルとブール回路を表現し,有限精度桁に作用する人工ニューラルネットワーク(anns)を表現する。 我々の分析は、質問と計算複雑性の直接的な関係を解明する。 ANNの代わりにチューリングマシンで適用したMDL間のサンプル効率の潜在利得について, 下位および上位境界を提供する。 私たちの境界は、学習すべきブール関数の入力のビットサイズに依存する。 さらに,回路の複雑度における古典的オープン問題の密接な関係を浮き彫りにする。

関連論文リスト

• Learning Linear Attention in Polynomial Time [115.68795790532289]
  線形注意を持つ単層変圧器の学習性に関する最初の結果を提供する。 線形アテンションは RKHS で適切に定義された線形予測器とみなすことができる。 我々は,すべての経験的リスクが線形変換器と同等のトレーニングデータセットを効率的に識別する方法を示す。
  論文  参考訳（メタデータ） (2024-10-14T02:41:01Z)
• Symbolic Regression on FPGAs for Fast Machine Learning Inference [2.0920303420933273]
  高エネルギー物理コミュニティは、FPGA(Field-Programmable Gate Arrays)上に機械学習ベースのソリューションをデプロイする可能性を探っている シンボリックレグレッション(SR)と呼ばれる機械学習技術を利用した新しいエンドツーエンドプロシージャを提案する。 提案手法は,最大で5 nsまでの実行時間を最大13倍に抑えながら,90%以上の近似精度を維持した推論モデルを用いて3層ニューラルネットワークを近似できることを示す。
  論文  参考訳（メタデータ） (2023-05-06T17:04:02Z)
• Pathfinding Neural Cellular Automata [23.831530224401575]
  Pathfindingは、ロボットパス計画、トランスポートルーティング、ゲームプレイなど、幅広い複雑なAIタスクの重要なサブコンポーネントである。 我々は, Breadth-First Search (BFS) のモデル,すなわち最短経路探索のハンドコードと学習を行う。 本稿では、Depth-First Search(DFS)のニューラル実装を提案し、グラフの直径を計算するためのNAAを生成するために、ニューラルネットワークBFSと組み合わせる方法について概説する。 我々は,これらの手書きNCAに触発されたアーキテクチャ変更を実験し,グリッド迷路の直径問題を解くためにゼロからネットワークをトレーニングし,高い能力の一般化を示した。
  論文  参考訳（メタデータ） (2023-01-17T11:45:51Z)
• Power and limitations of single-qubit native quantum neural networks [5.526775342940154]
  量子ニューラルネットワーク(QNN)は、機械学習、化学、最適化の応用を確立するための主要な戦略として登場した。 量子ニューラルネットワークのデータ再アップロードの表現能力に関する理論的枠組みを定式化する。
  論文  参考訳（メタデータ） (2022-05-16T17:58:27Z)
• Deep Architecture Connectivity Matters for Its Convergence: A Fine-Grained Analysis [94.64007376939735]
  我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。 接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
  論文  参考訳（メタデータ） (2022-05-11T17:43:54Z)
• Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers [50.85524803885483]
  本研究は,統計的学習性を示すために近似ネットワークを必要とする統計有意(SM)近似の形式的定義を提案する。 回路とチューリングマシンの2つの機能クラスに対するSM近似について検討する。
  論文  参考訳（メタデータ） (2021-07-28T04:28:55Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  強化学習のコアにおける探索・探索トレードオフについて検討する。 特に、関数クラス $mathcalF$ の複雑さが関数の複雑さを特徴づけていることを証明する。 私たちの後悔の限界はエピソードの数とは無関係です。
  論文  参考訳（メタデータ） (2020-11-09T18:32:22Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  本稿では,ニューラルネットワークを用いた大規模AUCのための分散変数について検討する。 我々のモデルは通信ラウンドをはるかに少なくし、理論上はまだ多くの通信ラウンドを必要としています。 いくつかのデータセットに対する実験は、我々の理論の有効性を示し、我々の理論を裏付けるものである。
  論文  参考訳（メタデータ） (2020-05-05T18:08:23Z)
• Exposing Hardware Building Blocks to Machine Learning Frameworks [4.56877715768796]
  我々は、そのようなニューロンをユニークな関数として補完するトポロジーを設計する方法に焦点をあてる。 我々は、カスタムの空間性と量子化によるニューラルネットワークのトレーニングを支援するライブラリを開発する。
  論文  参考訳（メタデータ） (2020-04-10T14:26:00Z)
• Belief Propagation Reloaded: Learning BP-Layers for Labeling Problems [83.98774574197613]
  最も単純な推論手法の1つとして、切り詰められた最大積のBelief伝播を取り上げ、それをディープラーニングモデルの適切なコンポーネントにするために必要となるものを加えます。 このBP-Layerは畳み込みニューラルネットワーク(CNN)の最終ブロックまたは中間ブロックとして使用できる このモデルは様々な密集予測問題に適用可能であり、パラメータ効率が高く、ステレオ、光フロー、セマンティックセグメンテーションにおける堅牢な解を提供する。
  論文  参考訳（メタデータ） (2020-03-13T13:11:35Z)

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

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