How can "any process you can imagine" be thought of as function computation?

Question

I stumbled upon this passage when reading this guide.

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. 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.* Universality means that, in principle, neural networks can do all these things and many more.

How is this true? How can any process be thought of as function computation? How would one compute function in order to translate Chinese text to English?

Answer 1

A function is simply a procedure that maps a particular input to a particular output. You put in $X$, and the function computes $Y$. Those $X$ and $Y$ can take many different forms. It could be mapping one number to another number (convert miles to kilometres), mapping sound to text (name that tune), mapping text to text (translate languages), mapping a video to text (review this movie), or mapping text to an image (draw a picture of $X$). Anytime you have a procedure that produces a fixed output based on a fixed input, it's a function.

Universality theorems guarantee that a neural network can produce an arbitrarily good approximation of any possible function. That doesn't mean it's easy, though - finding the right function that maps $X$ to $Y$ is the hard part.

Answer 2

To speak to your question about how Chinese to English translation can be a computation, it first requires a way to turn the base units of translation (tokens) into something computable. One basic way is to define the set of your vocabulary terms and create a gigantic matrix (typically called an embedding) with each column representing a token as well as one-hot encoded matrices to perform a selection from the matrix.

Say, if my vocabulary is ("apple", "kiwi") and I want 2-dimensional vectors for the tokens (trivially small but manageable example), you'd need a 2x2 (two tokens in two dimensions) random matrix and two one-hot vectors:

• "apple" = [1 0]
• "kiwi" = [0 1]

Multiplying [1 0] for instance, by your 2x2 matrix, will "select" the vector in the first column, which represents the token "apple".

Once you have a randomly initialized embedding matrix, you have to train it to be useful. A relatively common method to do so is to make it the hidden layer in a neural network, mask tokens in the source data, and train the model with gradient descent to "guess" what token was removed. You can also just fully train the embedding as part of training a larger network, but that increases training time significantly.

If you have a lot of sentence pairs of English-Chinese translations, you could train an English/Chinese joint embedding and then further train a neural network that uses it to translate between sentence pairs (but this is not a state of the art method).

Every step of the process after text preparation here is a mathematical operation, so a forward pass of the trained model can be expressed as an equation (though one you could never fully write out by hand), and if we're careful to only choose differentiable operations, then the training of the model as well comes down to solving (many, massive) equations.