Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909371016937472 |
|---|---|
| author | Yang, Andy Chiang, David Angluin, Dana |
| author_facet | Yang, Andy Chiang, David Angluin, Dana |
| contents | The expressive power of transformers over inputs of unbounded size can be studied through their ability to recognize classes of formal languages. In this paper, we establish exact characterizations of transformers with hard attention (in which all attention is focused on exactly one position) and attention masking (in which each position only attends to positions on one side). With strict masking (each position cannot attend to itself) and without position embeddings, these transformers are expressively equivalent to linear temporal logic (LTL), which defines exactly the star-free languages. A key technique is the use of Boolean RASP as a convenient intermediate language between transformers and LTL. We then take numerous results known for LTL and apply them to transformers, showing how position embeddings, strict masking, and depth all increase expressive power. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_13897 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages Yang, Andy Chiang, David Angluin, Dana Formal Languages and Automata Theory Machine Learning Logic in Computer Science The expressive power of transformers over inputs of unbounded size can be studied through their ability to recognize classes of formal languages. In this paper, we establish exact characterizations of transformers with hard attention (in which all attention is focused on exactly one position) and attention masking (in which each position only attends to positions on one side). With strict masking (each position cannot attend to itself) and without position embeddings, these transformers are expressively equivalent to linear temporal logic (LTL), which defines exactly the star-free languages. A key technique is the use of Boolean RASP as a convenient intermediate language between transformers and LTL. We then take numerous results known for LTL and apply them to transformers, showing how position embeddings, strict masking, and depth all increase expressive power. |
| title | Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages |
| topic | Formal Languages and Automata Theory Machine Learning Logic in Computer Science |
| url | https://arxiv.org/abs/2310.13897 |