On the expressivity of recurrent neural cascades with identity
Recurrent Neural Cascades (RNC) are the class of recurrent neural networks with no cyclic dependencies among recurrent neurons. Their subclass RNC+ with positive recurrent weights has been shown to be closely connected to the starfree regular languages, which are the expressivity of many well-establ...
| Main Authors: | , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
International Conference on Principles of Knowledge Representation and Reasoning
2024
|
| _version_ | 1811141285282578432 |
|---|---|
| author | Knorozova, NA Ronca, A |
| author_facet | Knorozova, NA Ronca, A |
| author_sort | Knorozova, NA |
| collection | OXFORD |
| description | Recurrent Neural Cascades (RNC) are the class of recurrent
neural networks with no cyclic dependencies among recurrent neurons. Their subclass RNC+ with positive recurrent
weights has been shown to be closely connected to the starfree regular languages, which are the expressivity of many
well-established temporal logics. The existing expressivity
results show that the regular languages captured by RNC+
are the star-free ones, and they leave open the possibility that
RNC+ may capture languages beyond regular. We exclude
this possibility for languages that include an identity element,
i.e., an input that can occur an arbitrary number of times without affecting the output. Namely, in the presence of an identity element, we show that the languages captured by RNC+
are exactly the star-free regular languages. Identity elements
are ubiquitous in temporal patterns, and hence our results apply to a large number of applications. The implications of our
results go beyond expressivity. At their core, we establish a
close structural correspondence between RNC+ and semiautomata cascades, showing that every neuron can be equivalently captured by a three-state semiautomaton. A notable
consequence of this result is that RNC+ are no more succinct
than cascades of three-state semiautomata. |
| first_indexed | 2024-09-25T04:35:27Z |
| format | Conference item |
| id | oxford-uuid:a78ea16c-50c8-4d6f-a69b-10e4528f0d5b |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-09-25T04:35:27Z |
| publishDate | 2024 |
| publisher | International Conference on Principles of Knowledge Representation and Reasoning |
| record_format | dspace |
| spelling | oxford-uuid:a78ea16c-50c8-4d6f-a69b-10e4528f0d5b2024-09-16T13:14:03ZOn the expressivity of recurrent neural cascades with identityConference itemhttp://purl.org/coar/resource_type/c_5794uuid:a78ea16c-50c8-4d6f-a69b-10e4528f0d5bEnglishSymplectic ElementsInternational Conference on Principles of Knowledge Representation and Reasoning2024Knorozova, NARonca, ARecurrent Neural Cascades (RNC) are the class of recurrent neural networks with no cyclic dependencies among recurrent neurons. Their subclass RNC+ with positive recurrent weights has been shown to be closely connected to the starfree regular languages, which are the expressivity of many well-established temporal logics. The existing expressivity results show that the regular languages captured by RNC+ are the star-free ones, and they leave open the possibility that RNC+ may capture languages beyond regular. We exclude this possibility for languages that include an identity element, i.e., an input that can occur an arbitrary number of times without affecting the output. Namely, in the presence of an identity element, we show that the languages captured by RNC+ are exactly the star-free regular languages. Identity elements are ubiquitous in temporal patterns, and hence our results apply to a large number of applications. The implications of our results go beyond expressivity. At their core, we establish a close structural correspondence between RNC+ and semiautomata cascades, showing that every neuron can be equivalently captured by a three-state semiautomaton. A notable consequence of this result is that RNC+ are no more succinct than cascades of three-state semiautomata. |
| spellingShingle | Knorozova, NA Ronca, A On the expressivity of recurrent neural cascades with identity |
| title | On the expressivity of recurrent neural cascades with identity |
| title_full | On the expressivity of recurrent neural cascades with identity |
| title_fullStr | On the expressivity of recurrent neural cascades with identity |
| title_full_unstemmed | On the expressivity of recurrent neural cascades with identity |
| title_short | On the expressivity of recurrent neural cascades with identity |
| title_sort | on the expressivity of recurrent neural cascades with identity |
| work_keys_str_mv | AT knorozovana ontheexpressivityofrecurrentneuralcascadeswithidentity AT roncaa ontheexpressivityofrecurrentneuralcascadeswithidentity |