論文の概要: Ask, and it shall be given: Turing completeness of prompting

• arxiv url: http://arxiv.org/abs/2411.01992v1
• Date: Mon, 04 Nov 2024 11:26:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 21:27:24.727088
• Title: Ask, and it shall be given: Turing completeness of prompting
• Title（参考訳）: Ask, and it shall given: Turing completeness of prompting
• Authors: Ruizhong Qiu, Zhe Xu, Wenxuan Bao, Hanghang Tong,
• Abstract要約: 大規模言語モデル(LLM)は機械学習に革命をもたらし、いわゆるLLMプロンプトパラダイムを開始した。 本稿では, LLMプロンプトパラダイムに関する最初の理論的研究を, 我々の知識を最大限活用するために提示する。 有限サイズの変換器が存在し、計算可能な任意の関数に対して、変換器が関数を演算する対応するプロンプトが存在することを示す。
• 参考スコア（独自算出の注目度）: 47.08833920586575
• License:
• Abstract: Since the success of GPT, large language models (LLMs) have been revolutionizing machine learning and have initiated the so-called LLM prompting paradigm. In the era of LLMs, people train a single general-purpose LLM and provide the LLM with different prompts to perform different tasks. However, such empirical success largely lacks theoretical understanding. Here, we present the first theoretical study on the LLM prompting paradigm to the best of our knowledge. In this work, we show that prompting is in fact Turing-complete: there exists a finite-size Transformer such that for any computable function, there exists a corresponding prompt following which the Transformer computes the function. Furthermore, we show that even though we use only a single finite-size Transformer, it can still achieve nearly the same complexity bounds as that of the class of all unbounded-size Transformers. Overall, our result reveals that prompting can enable a single finite-size Transformer to be efficiently universal, which establishes a theoretical underpinning for prompt engineering in practice.
• Abstract（参考訳）: GPTの成功以来、大規模言語モデル(LLM)は機械学習に革命をもたらし、いわゆるLLMプロンプトパラダイムを開始した。 LLMの時代には、1つの汎用LSMをトレーニングし、異なるタスクを実行するための異なるプロンプトを提供する。 しかし、このような経験的な成功は理論的な理解を欠いている。 本稿では, LLMプロンプトパラダイムに関する最初の理論的研究を, 我々の知識を最大限活用するために提示する。 本稿では、プロンプトが実際にチューリング完全であることを示し、計算可能な任意の関数に対して、その関数を演算する対応するプロンプトが存在するような有限サイズのトランスフォーマーが存在する。 さらに、有限サイズの変換器を1つだけ使うとしても、すべての非有界サイズの変換器のクラスとほぼ同じ複雑性境界を達成できることが示される。 以上の結果から,1つの有限サイズの変圧器を効率よく汎用化することが可能であることが明らかとなった。

関連論文リスト

• Provably Transformers Harness Multi-Concept Word Semantics for Efficient In-Context Learning [53.685764040547625]
  トランスフォーマーベースの大規模言語モデル(LLM)は、卓越した創造力と出現能力を示している。 この研究は、トランスフォーマーが単語のマルチコンセプトセマンティクスをどのように活用し、強力なICLと優れたアウト・オブ・ディストリビューションICL能力を実現するかを示すための数学的解析を提供する。
  論文  参考訳（メタデータ） (2024-11-04T15:54:32Z)
• Supervised Chain of Thought [5.389461633686935]
  Chain of Thought (CoT)は複雑な推論タスクを解決するための有望なアプローチを提供する。 ワンプロンプト・フォー・オールアプローチは、正しい推論ステップを生成するためにモデルに重大な課題をもたらす。 タスク固有の監督が、プロンプト空間を正確にナビゲートし、最適な性能を達成するためにいかに重要であるかを示す。
  論文  参考訳（メタデータ） (2024-10-18T06:25:27Z)
• Can Transformers Learn $n$-gram Language Models? [77.35809823602307]
  2種類のランダムな$n$-gram LMを学習するトランスフォーマーの能力について検討する。 例えば、$n$-gram LMに対する古典的な推定手法として、add-$lambda$ smoothing outperform transformerがある。
  論文  参考訳（メタデータ） (2024-10-03T21:21:02Z)
• Large Language Models and the Extended Church-Turing Thesis [0.0]
  本稿では,計算可能性理論と計算複雑性理論を用いて,大規模言語モデル(LLM)の計算能力について検討する。 固定的な(非適応的な) LLM は、計算量的に a, probably large, deterministic finite-state transducer と同値であることを示す。 本研究は,いくつかの関連分野と哲学の幅広い文脈における知見のメリットについて論じる。
  論文  参考訳（メタデータ） (2024-09-11T03:09:55Z)
• In-Context Learning with Representations: Contextual Generalization of Trained Transformers [66.78052387054593]
  In-context Learning (ICL) は、事前訓練された大規模言語モデルの能力を指し、推論中にいくつか例を挙げると、新しいタスクを学習できる。 本稿では,非線形回帰タスクのレンズによる勾配降下による変圧器のトレーニングダイナミクスについて検討する。
  論文  参考訳（メタデータ） (2024-08-19T16:47:46Z)
• Universal Approximation Theory: The Basic Theory for Transformer-based Large Language Models [9.487731634351787]
  大規模トランスフォーマーネットワークは、自然言語処理アルゴリズムの進歩において、急速に主要なアプローチとなっている。 本稿では,大規模言語モデル(LLM)の理論的基礎について考察する。 理論的な背景を提供し、これらの進歩を支えるメカニズムに光を当てている。
  論文  参考訳（メタデータ） (2024-07-01T04:29:35Z)
• Sumformer: Universal Approximation for Efficient Transformers [2.4832703558223725]
  本稿では,シーケンス・ツー・シーケンス関数を普遍的に近似できる新しいシンプルなアーキテクチャであるSumformerを紹介する。 我々はトランスフォーマーの新しい証明を導き、一つの注意層だけが普遍的な近似に十分であることを示す。
  論文  参考訳（メタデータ） (2023-07-05T13:59:35Z)
• Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspective [39.47116013338394]
  CoT(Chain-of-Thought prompting)は,大規模言語モデル(LLM)の性能を劇的に向上させる 我々は、CoTが動的プログラミング(Dynamic Programming)として知られる一般的な意思決定問題に対処できることを示します。
  論文  参考訳（メタデータ） (2023-05-24T17:59:21Z)
• Your Transformer May Not be as Powerful as You Expect [88.11364619182773]
  連続列列列関数を近似できるかどうかに関して, RPE ベースの変換器のパワーを数学的に解析する。 RPEをベースとしたトランスフォーマーでは,ニューラルネットワークの深さや幅がどんなに深くても近似できない連続列列列列関数が存在することを示す。 我々は,その条件を満たす,Universal RPE-based (URPE) Attentionと呼ばれる新しいアテンションモジュールを開発する。
  論文  参考訳（メタデータ） (2022-05-26T14:51:30Z)
• Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations [51.77000472945441]
  Long Short-Term Memory (LSTM) と Transformer は、自然言語処理タスクに使用される2つの一般的なニューラルネットワークアーキテクチャである。 実際には、トランスフォーマーモデルの方がLSTMよりも表現力が高いことがよく見られる。 本研究では,LSTMとTransformerの実践的差異について検討し,その潜在空間分解パターンに基づく説明を提案する。
  論文  参考訳（メタデータ） (2021-12-16T19:56:44Z)

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

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