Tighter Bounds on the Expressivity of Transformer Encoders
Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform $TC^0$. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Variational autoencoders trained with q-deformed lower bounds
Variational autoencoders (VAEs) have been successful at learning a low-dimensional manifold from high-dimensional data with complex dependencies. At their core, they consist of a powerful Bayesian probabilistic inference…
Variational InferenceImportance Weighted Hierarchical Variational Inference
Variational Inference is a powerful tool in the Bayesian modeling toolkit, however, its effectiveness is determined by the expressivity of the utilized variational distributions in terms of their ability to match the tru…
Variational InferenceSpectrum-Aware Bounds on Invertibility for Privacy-Enhancing Instance Encoding
Instance encoding is a popular empirical technique for privacy enhancement when sharing data to an untrusted server. It transforms sensitive data through an encoding process before sharing, with the hope that the encodin…
Counting Like Transformers: Compiling Temporal Counting Logic Into Softmax Transformers
Deriving formal bounds on the expressivity of transformers, as well as studying transformers that are constructed to implement known algorithms, are both effective methods for better understanding the computational power…
Debiasing Evidence Approximations: On Importance-weighted Autoencoders and Jackknife Variational Inference
The importance-weighted autoencoder (IWAE) approach of Burda et al. defines a sequence of increasingly tighter bounds on the marginal likelihood of latent variable models. Recently, Cremer et al. reinterpreted the IWAE b…
Computational EfficiencyVariational Inference