論文の概要: Understanding Transformer Reasoning Capabilities via Graph Algorithms

• arxiv url: http://arxiv.org/abs/2405.18512v1
• Date: Tue, 28 May 2024 18:31:14 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-30 22:03:07.131506
• Title: Understanding Transformer Reasoning Capabilities via Graph Algorithms
• Title（参考訳）: グラフアルゴリズムによる変圧器推論能力の理解
• Authors: Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Halcrow, Bryan Perozzi, Vahab Mirrokni,
• Abstract要約: 我々は、トランスフォーマースケーリングレギュレーションがアルゴリズムの様々なクラスを完璧に解けるかを検討する。 その結果、トランスフォーマーは多くのグラフ推論タスクで優れており、特殊なグラフニューラルネットワークよりも優れています。
• 参考スコア（独自算出の注目度）: 25.08208816144745
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Which transformer scaling regimes are able to perfectly solve different classes of algorithmic problems? While tremendous empirical advances have been attained by transformer-based neural networks, a theoretical understanding of their algorithmic reasoning capabilities in realistic parameter regimes is lacking. We investigate this question in terms of the network's depth, width, and number of extra tokens for algorithm execution. Our novel representational hierarchy separates 9 algorithmic reasoning problems into classes solvable by transformers in different realistic parameter scaling regimes. We prove that logarithmic depth is necessary and sufficient for tasks like graph connectivity, while single-layer transformers with small embedding dimensions can solve contextual retrieval tasks. We also support our theoretical analysis with ample empirical evidence using the GraphQA benchmark. These results show that transformers excel at many graph reasoning tasks, even outperforming specialized graph neural networks.
• Abstract（参考訳）: どのトランスフォーマースケーリングレジームが、アルゴリズムのさまざまなクラスを完璧に解決できるのか? トランスフォーマーベースのニューラルネットワークによって、膨大な経験的進歩が達成されている一方で、現実的なパラメータ体系におけるアルゴリズム推論能力に関する理論的理解が欠如している。 本稿では,ネットワークの深さ,幅,アルゴリズム実行のための余分なトークン数の観点から,この問題を考察する。 我々の新しい表現階層は、9つのアルゴリズム的推論問題を、異なる現実的なパラメータスケーリング方式の変換器で解けるクラスに分離する。 グラフ接続のようなタスクには対数深さが必要で十分であることを示す一方、埋め込み次元の小さい単一層トランスは文脈的検索タスクを解くことができる。 また、GraphQAベンチマークを用いて、経験的証拠を多用した理論解析も支援している。 これらの結果は、トランスフォーマーが多くのグラフ推論タスクで優れており、特殊なグラフニューラルネットワークよりも優れていることを示している。

関連論文リスト

• Graph Transformers Dream of Electric Flow [72.06286909236827]
  グラフデータに適用された線形変換器は、正準問題を解くアルゴリズムを実装可能であることを示す。 そこで我々は,これらのグラフアルゴリズムをそれぞれ実装するための明示的な重み設定を提案し,基礎となるアルゴリズムの誤差によって構築したトランスフォーマーの誤差を限定する。
  論文  参考訳（メタデータ） (2024-10-22T05:11:45Z)
• Pruning By Explaining Revisited: Optimizing Attribution Methods to Prune CNNs and Transformers [14.756988176469365]
  計算要求の削減と効率の向上のための効果的なアプローチは、ディープニューラルネットワークの不要なコンポーネントを創り出すことである。 これまでの研究では、eXplainable AIの分野からの帰属法が、最も関係の低いネットワークコンポーネントを数ショットで抽出し、プルークする効果的な手段であることが示された。
  論文  参考訳（メタデータ） (2024-08-22T17:35:18Z)
• Simulation of Graph Algorithms with Looped Transformers [6.0465914748433915]
  理論的観点から, グラフ上のアルゴリズムをシミュレートするトランスフォーマーネットワークの能力について検討する。 このアーキテクチャは、Dijkstraの最も短い経路のような個々のアルゴリズムをシミュレートできることを示す。 付加的なアテンションヘッドを利用する場合のチューリング完全度を一定幅で示す。
  論文  参考訳（メタデータ） (2024-02-02T02:48:03Z)
• Deep Prompt Tuning for Graph Transformers [55.2480439325792]
  ファインチューニングはリソース集約型であり、大きなモデルのコピーを複数保存する必要がある。 ファインチューニングの代替として,ディープグラフプロンプトチューニングと呼ばれる新しい手法を提案する。 事前学習したパラメータを凍結し、追加したトークンのみを更新することにより、フリーパラメータの数を減らし、複数のモデルコピーを不要にする。
  論文  参考訳（メタデータ） (2023-09-18T20:12:17Z)
• Unsupervised Learning of Invariance Transformations [105.54048699217668]
  近似グラフ自己同型を見つけるためのアルゴリズムフレームワークを開発する。 重み付きグラフにおける近似自己同型を見つけるために、このフレームワークをどのように利用できるかについて議論する。
  論文  参考訳（メタデータ） (2023-07-24T17:03:28Z)
• Centered Self-Attention Layers [89.21791761168032]
  変圧器の自己保持機構とグラフニューラルネットワークのメッセージ通過機構を繰り返し適用する。 我々は、このアプリケーションが必然的に、より深い層での同様の表現に過剰なスムーシングをもたらすことを示す。 これらの機構の集約演算子に補正項を提示する。
  論文  参考訳（メタデータ） (2023-06-02T15:19:08Z)
• Faith and Fate: Limits of Transformers on Compositionality [109.79516190693415]
  3つの代表的構成課題にまたがる変圧器大言語モデルの限界について検討する。 これらのタスクは、問題をサブステップに分割し、これらのステップを正確な答えに合成する必要があります。 実験結果から,多段階合成推論を線形化部分グラフマッチングに還元することにより,トランスフォーマーLLMが構成課題を解くことが示唆された。
  論文  参考訳（メタデータ） (2023-05-29T23:24:14Z)
• The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization [8.424405898986118]
  本稿では,トランスフォーマーアーキテクチャ,コピーゲート,幾何学的アテンションの2つの改良を提案する。 我々の新しいニューラル・データ・ルータ(NDR)は、古典的な構成表検索タスクにおいて、100%長の一般化精度を実現する。 NDRの注意とゲーティングパターンは直感的な神経ルーティングとして解釈される傾向がある。
  論文  参考訳（メタデータ） (2021-10-14T21:24:27Z)
• Thinking Like Transformers [64.96770952820691]
  本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。 RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。 ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
  論文  参考訳（メタデータ） (2021-06-13T13:04:46Z)

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

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