Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Measuring The Complexity of Neural Network Algorithms
event speaker icon
Yara Shamshoum (M.Sc. Thesis Seminar)
event date icon
Thursday, 01.06.2023, 11:00
event location icon
Zoom Lecture: 93993434972 and Taub 601
event speaker icon
Advisor: Prof. Assaf Schuster
Substantial efforts have been devoted into improving the capabilities of neural networks to solve algorithmic tasks. Through training, these networks learn to mimic algorithmic behaviour, enabling them to handle tasks such as sorting, navigating, and managing complex data structures like graphs. However, classic algorithms and neural networks are fundamentally different, making it challenging to analyze the complexity of an algorithm learned by a neural network. First, it is necessary to establish that the model has indeed learned an abstract solution resembling algorithmic behaviour. Additionally, while the complexity of classic algorithms is measured asymptotically, the complexity of an algorithm learned by a neural network must be measured within the finite input space supported by the model. This evaluation should also factor into consideration potential degradation in the model’s accuracy on unseen data. To this end, we will discuss these challenges and their implications, and propose methods for measuring the complexity of algorithms learned by neural networks. Finally, we will present experimental results on graph problems.