論文の概要: Can Transformers Reason Logically? A Study in SAT Solving

• arxiv url: http://arxiv.org/abs/2410.07432v1
• Date: Wed, 9 Oct 2024 21:01:52 GMT
• ステータス: 処理完了
• システム内更新日: 2024-10-31 17:06:37.667634
• Title: Can Transformers Reason Logically? A Study in SAT Solving
• Title（参考訳）: トランスフォーマーは論理的に推論できるか?SATソルビングの研究
• Authors: Leyan Pan, Vijay Ganesh, Jacob Abernethy, Chris Esposo, Wenke Lee,
• Abstract要約: 本研究では, LLMの論理的推論能力について, ブール満足度問題(SAT)の文脈で検討する。 まず,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いてSATを解くデコーダのみの変換器を構築する。 我々は、よく知られたDPLL SAT-solvingアルゴリズムにトレース等価性を示すことによって、その正当性を証明した。
• 参考スコア（独自算出の注目度）: 17.15701291424892
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We theoretically and empirically study the logical reasoning capabilities of LLMs in the context of the Boolean satisfiability (SAT) problem. First, we construct a decoder-only Transformer that can solve SAT using backtracking and deduction via Chain-of-Thought (CoT). We prove its correctness by showing trace equivalence to the well-known DPLL SAT-solving algorithm. Second, to support the implementation of this abstract construction, we design a compiler $\texttt{PARAT}$ that takes as input a procedural specification and outputs a transformer model implementing this specification. Third, rather than $\textit{programming}$ a transformer to reason, we evaluate empirically whether it can be $\textit{trained}$ to do so by learning directly from algorithmic traces ("reasoning paths") of the DPLL algorithm.
• Abstract（参考訳）: 本研究では, LLMの論理的推論能力について, ブール充足可能性(SAT)問題の観点から理論的, 実験的に検討した。 まず,Chain-of-Thought (CoT) によるバックトラックとデダクションを用いてSATを解くデコーダのみの変換器を構築する。 我々は、よく知られたDPLL SAT-solvingアルゴリズムにトレース等価性を示すことによって、その正当性を証明した。 第二に、この抽象的な構成の実装をサポートするために、手続き仕様を入力として取り込んだコンパイラ $\texttt{PARAT}$ を設計し、この仕様を実装したトランスフォーマーモデルを出力する。 第3に、$\textit{ programsming}$ a transformer to reasonというよりは、DPLLアルゴリズムのアルゴリズムトレース(推論パス)から直接学習することで、$\textit{trained}$が可能であるかどうかを経験的に評価する。

関連論文リスト

• Transformers Provably Solve Parity Efficiently with Chain of Thought [40.78854925996]
  この研究は、複雑な問題を解決するためのトレーニングトランスの最初の理論的解析を提供する。 我々は、基本的な$k$-parity問題を解くために、1層トランスを訓練することを検討する。
  論文  参考訳（メタデータ） (2024-10-11T08:55:17Z)
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis [82.51626700527837]
  チェーン・オブ・シフト(Chain-of-shift, CoT)は、複数の中間ステップを持つ例を用いてクエリを増強することにより、大規模言語モデルの推論能力を実現する効率的な手法である。 CoT の理論的成功にもかかわらず、CoT が成立しても正確な一般化が得られないことを示す。
  論文  参考訳（メタデータ） (2024-10-03T03:12:51Z)
• On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoning [87.73401758641089]
  CoT推論による現代言語モデル(LM)の性能向上 LMは弦上の分布の族を確率的チューリングマシンと同一に表現できることを示す。
  論文  参考訳（メタデータ） (2024-06-20T10:59:02Z)
• Learning Reliable Logical Rules with SATNet [7.951021955925275]
  我々は、入力出力の例から基礎となるルールを学習する差別化可能なMaxSATソルバSATNetの上に構築する。 基礎的真理規則に対して有効な検証手法をいくつか導入する。 ストリームトランスフォーメーションとスドク問題に関する実験は、デコードされたルールが信頼性が高いことを示している。
  論文  参考訳（メタデータ） (2023-10-03T15:14:28Z)
• Transformers as Statisticians: Provable In-Context Learning with In-Context Algorithm Selection [88.23337313766353]
  この研究はまず、変換器がICLを実行するための包括的な統計理論を提供する。 コンテクストにおいて、トランスフォーマーは、幅広い種類の標準機械学習アルゴリズムを実装可能であることを示す。 エンフィングル変換器は、異なるベースICLアルゴリズムを適応的に選択することができる。
  論文  参考訳（メタデータ） (2023-06-07T17:59:31Z)
• 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)
• Transformers as Algorithms: Generalization and Implicit Model Selection in In-context Learning [23.677503557659705]
  In-context Learning (ICL) は、トランスフォーマーモデルが一連の例で動作し、オンザフライで推論を行うプロンプトの一種である。 我々は,このトランスモデルを学習アルゴリズムとして扱い,推論時別のターゲットアルゴリズムを実装するためのトレーニングを通じて専門化することができる。 変換器は適応学習アルゴリズムとして機能し、異なる仮説クラス間でモデル選択を行うことができることを示す。
  論文  参考訳（メタデータ） (2023-01-17T18:31:12Z)
• Characterizing Intrinsic Compositionality in Transformers with Tree Projections [72.45375959893218]
  トランスのようなニューラルモデルは、入力の異なる部分間で情報を任意にルーティングすることができる。 3つの異なるタスクに対するトランスフォーマーは、トレーニングの過程でより木のようなものになることを示す。 これらの木はモデル挙動を予測し、より木のようなモデルは構成的一般化のテストにおいてより良く一般化する。
  論文  参考訳（メタデータ） (2022-11-02T17:10:07Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  低深度変換器は任意の有限状態オートマトンを計算できる。 我々は,$O(log T)$レイヤを持つ変換器が,長さ$T$の入力シーケンス上で,オートマトンを正確に再現可能であることを示す。 さらに、これらの解の脆性について検討し、潜在的な緩和を提案する。
  論文  参考訳（メタデータ） (2022-10-19T17:45:48Z)
• Transformer-based Machine Learning for Fast SAT Solvers and Logic Synthesis [63.53283025435107]
  CNFベースのSATとMaxSATは論理合成と検証システムの中心である。 そこで本研究では,Transformerアーキテクチャから派生したワンショットモデルを用いて,MaxSAT問題の解法を提案する。
  論文  参考訳（メタデータ） (2021-07-15T04:47:35Z)

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

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