按年被提到
20212021 · 1 次2026
大模型与语言模型›模型表达力与计算理论·arXiv:2107.13163 · cs.LG

Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers

Colin Wei, Yining Chen, Tengyu Ma · 2021
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2021-08-04 · 最近 2024-10-02
2不同的人
2活跃月份
2讨论串
8被引(OpenAlex)
arXiv 摘要(候选层不写导读)

A common lens to theoretically study neural net architectures is to analyze the functions they can approximate. However, constructions from approximation theory may be unrealistic and therefore less meaningful. For example, a common unrealistic trick is to encode target function values using infinite precision. To address these issues, this work proposes a formal definition of statistically meaningful (SM) approximation which requires the approximating network to exhibit good statistical learnability. We study SM approximation for two function classes: boolean circuits and Turing machines. We show that overparameterized feedforward neural nets can SM approximate boolean circuits with sample complexity depending only polynomially on the circuit size, not the size of the network. In addition, we show that transformers can SM approximate Turing machines with computation time bounded by $T$ with sample complexity polynomial in the alphabet size, state space size, and $\log (T)$. We also introduce new tools for analyzing generalization which provide much tighter sample complexities than the typical VC-dimension or norm-based bounds, which may be of independent interest.

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论DannyBee · 2024-10

“This whole silly post seems to have been written so they can make this statement, which they seem to believe is profound: "This failure is not surprising, because any machine learning model, no matter how many magic parameters it has, is only capable of ex ecuting a fixed pipeline of mathematical operations. In algorithmic complexity terms it is O(1). Su…”

Johnny LLM Can't Read Code原评论 ↗
被提交为 story · 1 次