result relates to deep neural networks.
To follow the material in the chapter, you do not need to have
read earlier chapters in this book. Instead, the chapter is
structured to be enjoyable as a self-contained essay. Provided
you have just a little basic familiarity with neural networks, you
should be able to follow the explanation. I will, however,
provide occasional links to earlier material, to help fill in any
gaps in your knowledge.
Universality theorems are a commonplace in computer science,
so much so that we sometimes forget how astonishing they are.
But it's worth reminding ourselves: the ability to compute an
arbitrary function is truly remarkable. Almost any process you
can imagine can be thought of as function computation.
Consider the problem of naming a piece of music based on a
short sample of the piece. That can be thought of as computing
a function. Or consider the problem of translating a Chinese
text into English. Again, that can be thought of as computing a
function*
*Actually, computing one of many functions, since there are often many
acceptable translations of a given piece of text.
. Or consider the problem of taking an mp4 movie file and
generating a description of the plot of the movie, and a
discussion of the quality of the acting. Again, that can be
thought of as a kind of function computation*
*Ditto the remark about translation and there being many possible functions.
. Universality means that, in principle, neural networks can do
all these things and many more.
Of course, just because we know a neural network exists that
can (say) translate Chinese text into English, that doesn't mean
we have good techniques for constructing or even recognizing
such a network. This limitation applies also to traditional
universality theorems for models such as Boolean circuits. But,
as we've seen earlier in the book, neural networks have
powerful algorithms for learning functions. That combination
of learning algorithms + universality is an attractive mix. Up to
now, the book has focused on the learning algorithms. In this
chapter, we focus on universality, and what it means.