In this work, we bound a machine's ability to learn based on computational
limitations implied by physicality. We start by considering the information
processing capacity (IPC), a normalized measure of the expected squared error
of a collection of signals to a complete basis of functions. We use the IPC to
measure the degradation under noise of the performance of reservoir computers,
a particular kind of recurrent network, when constrained by physical
considerations. First, we show that the IPC is at most a polynomial in the
system size $n$, even when considering the collection of $2^n$ possible
pointwise products of the $n$ output signals. Next, we argue that this
degradation implies that the family of functions represented by the reservoir
requires an exponential number of samples to learn in the presence of the
reservoir's noise. Finally, we conclude with a discussion of the performance of
the same collection of $2^n$ functions without noise when being used for binary
classification.

该研究探讨了机器学习的计算限制、信息处理能力、水库计算机和二进制分类这些主要主题。

储层学习的限制

Limits to Reservoir Learning

Transformers are emerging as the new workhorse of NLP, showing great success
across tasks. Unlike LSTMs, transformers process input sequences entirely
through self-attention. Previous work has suggested that the computational
capabilities of self-attention to process hierarchical structures are limited.
In this work, we mathematically investigate the computational power of
self-attention to model formal languages. Across both soft and hard attention,
we show strong theoretical limitations of the computational abilities of
self-attention, finding that it cannot model periodic finite-state languages,
nor hierarchical structure, unless the number of layers or heads increases with
input length. These limitations seem surprising given the practical success of
self-attention and the prominent role assigned to hierarchical structure in
linguistics, suggesting that natural language can be approximated well with
models that are too weak for the formal languages typically assumed in
theoretical linguistics.

本文研究了自注意力在建模形式语言方面的计算能力，发现其在处理分层结构时存在强烈的理论限制，但在自然语言处理方面表现卓越。