論文の概要: Universal Length Generalization with Turing Programs

• arxiv url: http://arxiv.org/abs/2407.03310v1
• Date: Wed, 3 Jul 2024 17:53:44 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-04 13:05:47.105896
• Title: Universal Length Generalization with Turing Programs
• Title（参考訳）: チューリングプログラムを用いた普遍長一般化
• Authors: Kaiying Hou, David Brandfonbrener, Sham Kakade, Samy Jelassi, Eran Malach,
• Abstract要約: 本稿では,アルゴリズムタスクをチューリングマシンを模倣するステップに分解する手法であるチューリングプログラムを提案する。 チューリングプログラムを用いることで,アルゴリズム的タスクの領域におけるロバストな長さの一般化が得られる。 次に,確率的チューリングプログラムにおいて,トランスフォーマーが長さ一般化を実現することを実証し,任意のアルゴリズムタスクに対して長さ一般化が可能であることを示唆する。
• 参考スコア（独自算出の注目度）: 24.077722969687898
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Length generalization refers to the ability to extrapolate from short training sequences to long test sequences and is a challenge for current large language models. While prior work has proposed some architecture or data format changes to achieve length generalization, these proposals typically apply to a limited set of tasks. Building on prior scratchpad and Chain-of-Thought (CoT) techniques, we propose Turing Programs, a novel CoT strategy that decomposes an algorithmic task into steps mimicking the computation of a Turing Machine. This framework is both universal, as it can accommodate any algorithmic task, and simple, requiring only copying text from the context with small modifications. We show that by using Turing Programs, we obtain robust length generalization on a range of algorithmic tasks: addition, multiplication and in-context SGD. We then demonstrate that transformers achieve length generalization on random Turing Programs, suggesting that length generalization is possible for any algorithmic task. Finally, we theoretically prove that transformers can implement Turing Programs, constructing a simple RASP (Weiss et al.) program that simulates an arbitrary Turing machine.
• Abstract（参考訳）: 長さ一般化は、短いトレーニングシーケンスから長いテストシーケンスへの外挿が可能であり、現在の大規模言語モデルの課題である。 以前の作業では、長さの一般化を実現するためにいくつかのアーキテクチャやデータフォーマットの変更が提案されていたが、これらの提案は典型的には限られたタスクに適用される。 従来のスクラッチパッドとCoT(Chain-of-Thought)技術に基づいて,アルゴリズムタスクをチューリングマシンの計算を模倣するステップに分解する新しいCoT戦略であるTuring Programsを提案する。 このフレームワークは、任意のアルゴリズム的タスクに対応できるため、普遍的であり、最小限の変更でコンテキストからテキストをコピーするだけでよい。 チューリングプログラムを用いることで,加法,乗算,文脈内SGDといったアルゴリズム上のタスクに対して,ロバストな長さの一般化が得られることを示す。 次に,確率的チューリングプログラムにおいて,トランスフォーマーが長さ一般化を実現することを実証し,任意のアルゴリズムタスクに対して長さ一般化が可能であることを示唆する。 最後に、任意のチューリングマシンをシミュレートするシンプルな RASP (Weiss et al ) プログラムを構築して、トランスフォーマーがチューリングプログラムを実装できることを理論的に証明する。

関連論文リスト

• What Algorithms can Transformers Learn? A Study in Length Generalization [23.970598914609916]
  アルゴリズムタスクにおける長さ一般化の具体的設定におけるトランスフォーマーの能力の範囲について検討する。 具体的には、Transformerの計算モデル用に設計されたプログラミング言語であるRASPを利用する。 我々の研究は、構成一般化のメカニズムとトランスフォーマーのアルゴリズム能力に関する新しい視点を提供する。
  論文  参考訳（メタデータ） (2023-10-24T17:43:29Z)
• Compositional Program Generation for Few-Shot Systematic Generalization [59.57656559816271]
  コンポジションプログラムジェネレータ(CPG)と呼ばれるニューロシンボリックアーキテクチャに関する研究 CPGには3つの重要な特徴がある: 文法規則の形で、テキストモジュラリティ、テキストコンポジション、テキストタストラクションである。 SCAN と COGS のベンチマークでは,SCAN の14例と COGS の22例を使用して,完全な一般化を実現している。
  論文  参考訳（メタデータ） (2023-09-28T14:33:20Z)
• ExeDec: Execution Decomposition for Compositional Generalization in Neural Program Synthesis [54.18659323181771]
  プログラム合成において望ましいいくつかの異なる構成一般化形式を特徴付ける。 本稿では,ExeDecを提案する。ExeDecは,実行サブゴールを予測し,各ステップでプログラム実行によって段階的に通知される問題を解くための,新しい分解ベースの戦略である。
  論文  参考訳（メタデータ） (2023-07-26T01:07:52Z)
• Planning with Large Language Models for Code Generation [100.07232672883897]
  Planning-Guided Transformer Decoding (PG-TD) は、計画アルゴリズムを用いてルックアヘッド検索を行い、トランスフォーマーを誘導してより良いプログラムを生成する。 我々は、公開コーディングチャレンジベンチマークのバックボーンとして、いくつかの大きな言語モデルを用いて、我々のフレームワークを実証的に評価する。
  論文  参考訳（メタデータ） (2023-03-09T18:59:47Z)
• A Divide-Align-Conquer Strategy for Program Synthesis [8.595181704811889]
  本稿では,大規模プログラムの探索を複数の小さなプログラム合成問題に分割する例によって,構成セグメント化がプログラミングに応用可能であることを示す。 入力と出力における構成部品の構造的アライメントは、プログラム探索を導くのに使用されるペアワイズ対応に繋がる。
  論文  参考訳（メタデータ） (2023-01-08T19:10:55Z)
• Compositional Generalization and Decomposition in Neural Program Synthesis [59.356261137313275]
  本稿では,学習プログラムシンセサイザーの合成一般化能力の測定に焦点をあてる。 まず、プログラム合成法が一般化されるであろういくつかの異なる軸を特徴付ける。 2つの一般的な既存のデータセットに基づいて、これらの能力を評価するためのタスクのベンチマークスイートを導入する。
  論文  参考訳（メタデータ） (2022-04-07T22:16:05Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。 実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
  論文  参考訳（メタデータ） (2021-09-14T20:52:55Z)
• Thinking Like Transformers [64.96770952820691]
  本稿では,プログラミング言語の形式で変換器エンコーダの計算モデルを提案する。 RASPは、トランスフォーマーによって確実に学習できるタスクの解決策をプログラムするのにどのように使えるかを示す。 ヒストグラム、ソート、ダイク言語のためのRASPプログラムを提供する。
  論文  参考訳（メタデータ） (2021-06-13T13:04:46Z)
• Quantum circuit design for universal distribution using a superposition of classical automata [2.4192504570921622]
  この回路は、因果生成モデルを発見するために、データ中のアルゴリズム構造の推論を加速することができる。 オートマトン上の全ての可能なプログラムの古典的な総括列挙は、いくつかの例に対して示される。 量子計算の回路モデルに古典的オートマタの重ね合わせが実装されたのはこれが初めてである。
  論文  参考訳（メタデータ） (2020-06-01T14:47:28Z)

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

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