1W-MINDS, March 5: Anastasis Kratsios (McMaster University), Neural Networks as Universal Circuits скачать в хорошем качестве

1W-MINDS, March 5: Anastasis Kratsios (McMaster University), Neural Networks as Universal Circuits

Neural Networks as Universal Circuits This talk is based on a recent series of papers showing (i) that standard neural network architectures can exactly encode any algorithm representable on a digital computer (equivalently, any function computable by essentially any circuit model). We show that, for any computable function, the required number of neurons (space complexity) is of the same order as the number of circuit gates (time complexity), and that the network’s computational graph is comparable to the circuit computing the function. We then note that these configurations are likely too particular to be learned by gradient descent, which we illustrate experimentally on Boolean functions. Next, we introduce a new class of neural networks that trainably parameterize distributions over Boolean circuits: for any parameter setting, the model always samples a circuit, and therefore admits a meaningful circuit decomposition. We prove universality of this model for the relevant class of Boolean circuits, and show that for $B$-bit $O(\log B)$-juntas, the number of neurons required to exactly represent the Boolean circuit is polynomial in $B$.