[2301.10743] Tighter Bounds on the Expressivity of Transformer Encoders
source link: https://arxiv.org/abs/2301.10743
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 25 Jan 2023]
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.
| Subjects: | Machine Learning (cs.LG); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO) |
| Cite as: | arXiv:2301.10743 [cs.LG] |
| (or arXiv:2301.10743v1 [cs.LG] for this version) | |
| https://doi.org/10.48550/arXiv.2301.10743 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK