论文笔记：The Expressive Power of Transformers with Chain of Thought

ICLR 2024 reviewer 评分 6888【但是chair 很不喜欢】

1 intro

  • 之前的研究表明，即使是具有理想参数的标准Transformer，也无法完美解决许多大规模的顺序推理问题，如模拟有限状态机、判断图中的节点是否相连，或解决矩阵等式问题
    • 这里的直觉是，Transformer缺乏递归连接，而解决这些顺序推理问题需要递归
    • 实证上，受这些结果启发的推理问题无法被最先进的变压器语言模型如ChatGPT和GPT-4所解决，且GPT-4的推理性能与问题的计算图深度负相关
    • ——>结果表明某些类型的顺序推理对变压器构成挑战，并激励了解决这一问题的扩展
  • 一种在提升Transformer顺序推理方面已经实证成功的方法是增加所谓的思考链（CoT）或草稿本
    • 这些方法允许Transformer在回答前输出一系列中间令牌，而不是在读入输入后立即回答
    • 直观上，这种方法可以在顺序推理问题上解锁更大的表现力，因为模型可以将每个中间令牌作为一种递归状态使用
  • 论文描述在生成答案前采取中间步骤的Transformer解码器的推理能力，并将其与没有中间步骤的Transformer进行比较
    • 提供了Transformer能力的上限和下限，取决于t(n)：允许的中间步骤数量作为输入大小n的函数。
      • 主要关注三种情况：
        • 对数步骤（当t(n) = Θ(log n)）
        • 线性步骤（当t(n) = Θ(n)）
        • 和多项式步骤
  • 无中间步骤
    • 没有任何中间步骤的Transformer解码器只能解决属于相当小的电路复杂度类TC^0和相关逻辑类的问题
      • ——>基本的Transformer远非图灵完备：它们甚至无法解决比TC^0更大的类的完备问题，如模拟自动机（NC1-完备）、决定有向图连通性（NL-完备）或解决线性等式（P-完备）
  • 对数步骤
    • 通过对数数量的中间步骤，我们展示了Transformer的上界从TC0略微扩展到L
    • ——>这意味着具有对数数量中间步骤的Transformer可能获得了一些能力，但它们仍然无法解决像有向图连通性这样的NL-完备问题或解决线性等式这样的P-完备问题
  • 线性步骤
    • 线性中间步骤允许具有预投影范数的Transformer模拟自动机（NC1-完备）
      • 如果没有中间步骤（除非TC0等于NC1），否则无法完成这一任务
  • 多项式步骤
    • 通过多项式数量的解码步骤，论文展示了具有严格因果注意力和预投影范数的Transformer等同于P类。
    • 据我们所知，这是Transformer类与标准复杂度类之间的首次等价。

2 主要结论

2.1 具有中间解码的Transformer的能力

  • TIME(t(n)) 为存在一个在时间 O(t(n)) 内运行并接受语言 L 的图灵机的语言类
  • \widetilde{TIME(t(n))}为在TIME(t(n)log^kn) 中的问题类
    • 对于某些 k，这是当 t(n) ≥ n 时有意义的
  • SPACE(s(n)) 为存在一个带宽受 O(s(n)) 限制的图灵机接受语言 L 的语言类
  • CoT(t(n)) 表示一些使用 t(n) 解码步骤的变压器识别的语言集

——>具有 t(n) 步骤的Transformer与标准时间/空间复杂性类之间的以下关系

2.2 具有思考链的Transformer的能力

  • 方程（1）的左侧表明，具有 Θ(n) 步骤的Transformer解码器可以模拟如自动机或计数机这类的实时计算模型
    • 在复杂性理论的标准假设下，没有解码步骤的Transformer无法模拟所有自动机
    • ——>线性数量的解码步骤显著增强了变压器的能力
  • 同样，方程（1）的左侧意味着具有二次数量步骤的Transformer可以实现线性时间算法（用于随机访问图灵机）来解决有向图连通性问题，这是一个超出标准Transformer能力范围的问题
  • 具有多项式数量解码步骤的变压器可以解决线性等式、霍恩子句满足性和通用上下文无关识别问题，这些都是 P-完备问题，标准变压器已知无法表达

2.3 具有思考链的Transformer的局限性

  • 方程（1）的右侧确定了依赖于 t(n) 和 n 的变压器解码器中间步骤的两个上界。
  • 论文探讨了这一总结果在不同 t(n) 情形下的含义：
    • 对数步骤：具有 O(log n) 中间步骤的变压器解码器只能识别 L = SPACE(log n) 中的语言
      • ——>具有 O(log n) 中间步骤的变压器无法解决如有向图连通性这样的 NL-或 P-完备问题，就像没有中间解码步骤的变压器一样
    • 线性步骤：具有 O(n) 中间步骤的变压器解码器只能识别同时位于\widetilde{TIME(n^2)}和 SPACE(n) 中的语言
      • 由于 SPACE(n) 属于上下文敏感语言——>具有线性步骤的变压器最多可以识别上下文敏感语言
      • 结合我们的下界，这表明具有 Θ(n) 步骤的变压器解码器在乔姆斯基层级结构中处于正则语言和上下文敏感语言之间
    • 多项式步骤：
      • 如果 t(n) = O(n^c) 对于某些 c，我们得到的上限是P= \bigcup_0^\infty TIME(n^c)
      • 结合我们的下界，这表明具有多项式数量步骤的变压器解码器精确地识别 P 类问题
      • ——>多项式数量的步骤将Transformer转化为强大的推理器，尽管在实践中使用大型Transformer运行多项式数量的前向传递可能是不切实际的

后面的推导，感兴趣的可以看。。。实在是看不懂。。。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/544279.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

IOS 短信拦截插件

IOS 短信拦截插件

在使⽤iOS设备的时候, 我们经常会收到1069、1065开头的垃圾短信, 如果开了iMessage会更严重, 各种乱七⼋糟的垃圾信息会时不时地收到。 从iOS11开始, ⼿机可以⽀持恶短信拦截插件了. 我们可以通过该插件添加⼀些规则通过滤这些不需要的信息. ⼀. 使⽤xcode新建⼀个项⽬ 【1】…
阅读更多...
MongoDB 初识

MongoDB 初识

介绍 MongoDB是一种开源的文档型数据库管理系统，它使用类似于JSON的BSON格式（Binary JSON）来存储数据。与传统关系型数据库不同，MongoDB不使用表和行的结构，而是采用集合（Collection）(Mysql表)和…
阅读更多...
LabVIEW直流稳定电源自动化校准系统

LabVIEW直流稳定电源自动化校准系统

LabVIEW直流稳定电源自动化校准系统 直流稳定电源正向着智能化、高精度、多通道、宽量程的方向发展。基于LabVIEW开发环境，设计并实现了一种直流稳定电源自动化校准系统，以提升校准过程的整体效能，实现自动化设备替代人工进行电源校准工作。…
阅读更多...
【DNS】

【DNS】

文章目录 DNS域名解析系统（Domain Name System）DNS系统需要解决的问题DNS域名解析系统（Domain Name System）问题1：DNS名字空间(The DNS Name Space）DNS名字空间(The DNS Name Space)DNS名字空间(The DNS Na…
阅读更多...
oracle 19c 主备 补丁升级19.22

oracle 19c 主备 补丁升级19.22

补丁升级流程 备库升级 备库备份$ORALCE_HOME du -sh $ORACLE_HOME ​​​​​​​ 备份目录将dbhome_1压缩 cd $ORACLE_HOME cd .. Ls tar -cvzf db_home.tar.gz db_home_1 /opt/oracle/product/19c ​​​​​​​​​​​​​​ 关闭监听关闭数据库查看sq…
阅读更多...
基于表面势的增强型p-GaN HEMT器件模型

基于表面势的增强型p-GaN HEMT器件模型

来源：电子学报 22年 摘要 为了满足功率电路及系统设计对p-GaN HEMT（High Electron Mobility Transistor）器件模型的需求，本文建立了一套基于表面势计算方法的增强型p-GaN HEMT器件SPICE（Simulation Program with Int…
阅读更多...
【opencv】示例-travelsalesman.cpp 使用模拟退火算法求解旅行商问题

【opencv】示例-travelsalesman.cpp 使用模拟退火算法求解旅行商问题

// 载入 OpenCV 的核心头文件 #include <opencv2/core.hpp> // 载入 OpenCV 的图像处理头文件 #include <opencv2/imgproc.hpp> // 载入 OpenCV 的高层GUI(图形用户界面)头文件 #include <opencv2/highgui.hpp> // 载入 OpenCV 的机器学习模块头文件 #includ…
阅读更多...
数据库：SQL分类之DQL详解

数据库：SQL分类之DQL详解

1.DQL语法 select 字段列表 from 表名列表 where 条件列表 group by 分组字段列表 having 分组后条件列表 order by 排序字段列表 limit 分页参数 基本查询 条件查询&#xff08;where&#xff09; 聚合函数&#xff08;count、max、min、avg、sum &#xff09; 分组查询&…
阅读更多...
Linux网络基础 (二) ——(IP、MAC、端口号、TCPUDP协议、网络字节序)

Linux网络基础 (二) ——(IP、MAC、端口号、TCPUDP协议、网络字节序)

文章目录 IP 地址基本概念源IP地址 & 目的IP地址 MAC 地址基本概念源MAC地址 & 目的MAC地址 端口号基本概念源端口号 & 目的端口号 TCP & UDP 协议基本概念TCP 与 UDP 的抉择 网络字节序大端、小端字节序 &#x1f396; 博主的CSDN主页&#xff1a;Ryan.Alask…
阅读更多...
OLTP 与 OLAP 系统说明对比和大数据经典架构 Lambda 和 Kappa 说明对比——解读大数据架构（五）

OLTP 与 OLAP 系统说明对比和大数据经典架构 Lambda 和 Kappa 说明对比——解读大数据架构（五）

文章目录 前言OLTP 和 OLAPSMP 和 MPPlambda 架构Kappa 架构 前言 本文我们将研究不同类型的大数据架构设计&#xff0c;将讨论 OLTP 和 OLAP 的系统设计&#xff0c;以及有效处理数据的策略包括 SMP 和 MPP 等概念。然后我们将了解经典的 Lambda 架构和 Kappa 架构。 OLTP …
阅读更多...
杰发科技AC7840——CAN通信简介(5)_可变波特率设置

杰发科技AC7840——CAN通信简介(5)_可变波特率设置

0. 简介 设置可变波特率时候&#xff0c;遇到2个坑&#xff0c;在此记录下来 使用该函数即可 can_time_segment_t bitrate2 s_canBitrate[CAN_BITRATE_250K]; CAN_DRV_SetBitrate(instance, &bitrate2); 1. 波特率指针注意不要空 查看设置波特率的接口&#xff0c;发现…
阅读更多...
Pytest精通指南（09）利用Fixture给函数设置别名

Pytest精通指南（09）利用Fixture给函数设置别名

文章目录 前言测试用例默认显示传递一个参数传递多个参数 利用Fixture修改测试函数名称传递一个参数传递多个参数 验证ids和params长度不一致修改Fixture函数名称 前言 在 pytest 中&#xff0c;pytest.fixture 装饰器用于定义可以在多个测试函数中重用的设置和清理代码。 name…
阅读更多...
C/C++基础----内存相关

C/C++基础----内存相关

malloc分配内存 用法 参数为要开辟内存的大小&#xff08;字节为单位&#xff09;返回值为void*,所以要强转一下语法&#xff1a;malloc()动态开辟20个字节的内存&#xff0c;代码&#xff1a;#include <iostream>using namespace std;int main() {int *a (int *) mal…
阅读更多...
安全加速SCDN带的态势感知能为网站安全带来哪些帮助

安全加速SCDN带的态势感知能为网站安全带来哪些帮助

随着安全加速SCDN被越来越多的用户使用&#xff0c;很多用户都不知道安全加速SCDN的态势感知是用于做什么的&#xff0c;德迅云安全今天就带大家来了解下什么是态势感知&#xff0c;态势感知顾名思义就是对未发生的事件进行预知&#xff0c;并提前进行防范措施的布置&#xff0…
阅读更多...
内网渗透-Earthworm的简单使用（内网穿透工具）

内网渗透-Earthworm的简单使用（内网穿透工具）

Earthworm的简单介绍&#xff08;一&#xff09; 文章目录 EarthWorm下载地址1. 普通网络 1.1 跳板机存在公网IP 1.1.1 网络环境1.1.2 使用方法1.1.3 流量走向 1.2 跳板机不存在公网IP&#xff0c;可出网 1.2.1 网络环境1.2.2 使用方法1.2.3 流量走向 2. 二级网络 2.1 一级跳…
阅读更多...
系统架构最佳实践 -- 金融企业的资损问题介绍

系统架构最佳实践 -- 金融企业的资损问题介绍

什么是资损 资损通常来讲是指支付场景下的资金损失&#xff0c;这里可以从两个维度看 用户角度&#xff1a;多扣用户款导致用户资金损失&#xff0c;此问题一般需要通过客服等渠道反馈&#xff0c;可以把多的钱退给用户&#xff0c;但是很大程度上损失了用户体验&#xff1b; …
阅读更多...
ESP32 S3音频开发

ESP32 S3音频开发

1. 音频硬件框架 Codec&#xff1a;音频编解码芯片&#xff0c;一种低功耗单声道音频编解码器&#xff0c;包含单通道 ADC、单通道 DAC、低噪声前置放大器、耳机驱动器、数字音效、模拟混音和增益功能。它通过 I2S 和 I2C 总线与 ESP32-S3-WROOM-1 模组连接&#xff0c;以提供独…
阅读更多...
计算机视觉实验五——图像分割

计算机视觉实验五——图像分割

计算机视觉实验五——图像分割 一、实验目标二、实验内容1.了解图割操作&#xff0c;实现用户交互式分割&#xff0c;通过在一幅图像上为前景和背景提供一些标记或利用边界框选择一个包含前景的区域&#xff0c;实现分割①图片准备②代码③运行结果④代码说明 2.采用聚类法实现…
阅读更多...
64B/66B GT Transceiver 配置

64B/66B GT Transceiver 配置

一、前言 前一篇文章已经讲述了64B/66B的编码原理&#xff0c;此篇文章来配置一下7系列GT的64B/66B编码。并讲述所对应的例子工程的架构&#xff0c;以及部分代码的含义。 二、IP核配置 1、打开7 Series FPGAs Transceiver Wizards&#xff0c;选择将共享逻辑放置在example …
阅读更多...
全局代理导致JetBrains IDE CPU占用高，jdk.internal.net.http.common

全局代理导致JetBrains IDE CPU占用高，jdk.internal.net.http.common

GoLand版本&#xff1a;2022.3.4 解决办法&#xff1a; 使用SOCKS代理代替HTTP代理 禁用Space和Code With Me插件 禁用 TLS V1.3&#xff0c;参考&#xff1a;https://stackoverflow.com/questions/54485755/java-11-httpclient-leads-to-endless-ssl-loop 参考 https://…
阅读更多...
最新文章

Copyright @ 2022~2023