License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.10
URN: urn:nbn:de:0030-drops-130882
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13088/
Hitron, Yael ;
Musco, Cameron ;
Parter, Merav
Spiking Neural Networks Through the Lens of Streaming Algorithms
Abstract
We initiate the study of biologically-inspired spiking neural networks from the perspective of streaming algorithms. Like computers, human brains face memory limitations, which pose a significant obstacle when processing large scale and dynamically changing data. In computer science, these challenges are captured by the well-known streaming model, which can be traced back to Munro and Paterson `78 and has had significant impact in theory and beyond. In the classical streaming setting, one must compute a function f of a stream of updates ? = {u₁,…,u_m}, given restricted single-pass access to the stream. The primary complexity measure is the space used by the algorithm.
In contrast to the large body of work on streaming algorithms, relatively little is known about the computational aspects of data processing in spiking neural networks. In this work, we seek to connect these two models, leveraging techniques developed for streaming algorithms to better understand neural computation. Our primary goal is to design networks for various computational tasks using as few auxiliary (non-input or output) neurons as possible. The number of auxiliary neurons can be thought of as the "space" required by the network.
Previous algorithmic work in spiking neural networks has many similarities with streaming algorithms. However, the connection between these two space-limited models has not been formally addressed. We take the first steps towards understanding this connection. On the upper bound side, we design neural algorithms based on known streaming algorithms for fundamental tasks, including distinct elements, approximate median, and heavy hitters. The number of neurons in our solutions almost match the space bounds of the corresponding streaming algorithms. As a general algorithmic primitive, we show how to implement the important streaming technique of linear sketching efficiently in spiking neural networks. On the lower bound side, we give a generic reduction, showing that any space-efficient spiking neural network can be simulated by a space-efficient streaming algorithm. This reduction lets us translate streaming-space lower bounds into nearly matching neural-space lower bounds, establishing a close connection between the two models.
BibTeX - Entry
@InProceedings{hitron_et_al:LIPIcs:2020:13088,
author = {Yael Hitron and Cameron Musco and Merav Parter},
title = {{Spiking Neural Networks Through the Lens of Streaming Algorithms}},
booktitle = {34th International Symposium on Distributed Computing (DISC 2020)},
pages = {10:1--10:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-168-9},
ISSN = {1868-8969},
year = {2020},
volume = {179},
editor = {Hagit Attiya},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13088},
URN = {urn:nbn:de:0030-drops-130882},
doi = {10.4230/LIPIcs.DISC.2020.10},
annote = {Keywords: Biological distributed algorithms, Spiking neural networks, Streaming algorithms}
}
|
Keywords: |
|
Biological distributed algorithms, Spiking neural networks, Streaming algorithms |
|
Collection: |
|
34th International Symposium on Distributed Computing (DISC 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
07.10.2020 |
