Harmonic Analysis And The Complexity Of Computing With Threshold (Neural) Elements

Abstract

The main purpose of this talk is to introduce a useful tool for the analysis of discrete neural networks in which every node is a Boolean threshold gate. The difficulty in the analysis of neural networks arises from the fact that the basic processing elements (linear threshold gates) are nonlinear. The key idea in harmonic analysis of threshold functions is to represent the functions as polynomials over the field of real numbers. Answering different questions regarding neural networks becomes equivalent to answering questions related to the coefficients of these polynomials. We have applied these techniques and obtained many interesting and surprising results [1, 2, 3, 4]. The focus of this talk will be on presenting a theorem that characterizes-using spetral norms-the complexity of computing a Boolean function with threshold circuits [2, 3]. This result establishes the first known link between harmonic analysis and the complexity of computing with neural networks.

Files

Additional details