A Low-Energy Implementation of Finite Automata by Optimal-Size Neural Nets

Authors: Jiří Šíma
Publication year: 2013
Publication type: Konferenční příspěvek (mezinárodní konf.)
Periodical: Artificial Neural Networks and Machine Learning - ICANN 2013
Projects: NoSCoM: Non-Standard Computational Models and Their Applications in Complexity, Linguistics, and Learning
Bibliographic citation: ŠÍMA, Jiří. A Low-Energy Implementation of Finite Automata by Optimal-Size Neural Nets. In: MLADENOV, V., KOPRINKOVA-HRISTOVA, P, PALM, G., VILLA, A.E.P., APPOLLINI, B., KASABOV, N., eds. Artificial Neural Networks and Machine Learning - ICANN 2013. Berlin: Springer, 2013, S. 114-121. Lecture Notes in Computer Science, 8131. ISBN 978-3-642-40727-7. ISSN 0302-9743
Dostupné z: doi:10.1007/978-3-642-40728-4_15
DOI: 10.1007/978-3-642-40728-4_15
ID: 392404

Abstract

Recently, a new so-called energy complexity measure has been introduced and studied for feedforward perceptron networks. This measure is inspired by the fact that biological neurons require more energy to transmit a spike than not to fire and the activity of neurons in the brain is quite sparse, with only about 1% of neurons firing. We investigate the energy complexity for recurrent networks which bounds the number of active neurons at any time instant of a computation. We prove that any deterministic finite automaton with m states can be simulated by a neural network of optimal size s=Theta(sqrt{m}) with time overhead O(s/e) per one input bit, using the energy O(e), for any e=Omega(log s) and e=O(s), which shows the time-energy tradeoff in recurrent networks.