Why does the machine learning algorithm need to learn a set of functions in the case of missing data?

Question

I am currently studying the textbook Deep Learning by Goodfellow, Bengio, and Courville. Chapter 5.1 Learning Algorithms says the following:

Classification with missing inputs: Classification becomes more challenging if the computer program is not guaranteed that every measurement in its input vector will always be provided. To solve the classification task, the learning algorithm only has to define a single function mapping from a vector input to a categorical output. When some of the inputs may be missing, rather than providing a single classification function, the learning algorithm must learn a set of functions. Each function corresponds to classifying $\mathbf{x}$ with a different subset of its inputs missing. This kind of situation arises frequently in medical diagnosis, because many kinds of medical tests are expensive or invasive. One way to efficiently define such a large set of functions is to learn a probability distribution over all the relevant variables, then solve the classification task by marginalizing out the missing variables. With $n$ input variables, we can now obtain all $2^n$ different classification functions needed for each possible set of missing inputs, but the computer program needs to learn only a single function describing the joint probability distribution. See Goodfellow et al. (2013b) for an example of a deep probabilistic model applied to such a task in this way. Many of the other tasks described in this section can also be generalized to work with missing inputs; classification with missing inputs is just one example of what machine learning can do.

I was wondering if people would please help me better understand this explanation. Why is it that, when some of the inputs are missing, rather than providing a single classification function, the learning algorithm must learn a set of functions? And what is meant by "each function corresponds to classifying $\mathbf{x}$ with a different subset of its inputs missing."?

I would greatly appreciate it if people would please take the time to clarify this.

Answer 1

Intuitively, this is similar to the case when you are making predictions but you don't have all the necessary information to make the most accurate prediction or maybe there isn't a single accurate prediction, so you have a set of possible predictions (rather than a single prediction).

For example, if you hadn't seen the last Liverpool game (in the Champions League) against Atlético Madrid, you would have probably said that Liverpool was the most likely team to win the CL this year (2020) too. However, after having seen their last game, you noticed that they are not unbeatable and they are not perfect, so, although they have shown you (during this and the previous season) that they are a very good team, they may also no be the best until the end of the season. So, at this point, you may have a set of two possible hypotheses: Liverpool will win the CL or Liverpool will not win the CL.

In general, if you had a dataset that is representative of your whole population, then the dataset alone should be sufficient to make accurate predictions (i.e. it contains all the information sufficient to make accurate predictions). If that's not the case (which is often true), then you will have to account for all possible values of the missing data or you will have to make assumptions (or introduce an inductive bias).

The authors also mention the concept of marginalization, which is used in probability theory to calculate marginal probabilities, e.g. $p(X=x)$ (or for short $p(x)$), when there's another random variable $Y$, by accounting for all possible values of $Y$. In other words, you're interested only in $p(x)$ and you may have the joint probability distribution $p(x, y)$, then marginalization allows you to compute $p(x)$ using e.g. $p(x, y)$ and all possible values that the random variable $Y$ can take.

In any case, I think their description is a little bit vague and using the concept of marginalization to convey the idea behind the "multiple hypotheses" isn't the most appropriate approach, IMHO. If you are interested in these concepts in the context of neural networks, I suggest you read something about Bayesian machine learning or Bayesian neural networks.

Answer 2

@The Pointer the $2^n$ came from the question: How many function do we need to have if each of the $n$ inputs can be missing? example: $f_1(\text{missing}, x_2, x_3, \dots, x_n)$ for $x_1$ missing $f_2(x_1, x_2, \text{missing}, x_4, \text{missing}, \dots, x_n)$ for $x_3$ and $x_5$ missing.

So this problem is a combinatorial one and the event for each $x_i$ is Missing or Not. Each function corresponds 1-by-1 with a possible set $(x_1, \text{missing}, x_2, \dots, x_n)$. So how many sets can you form $2^n$. Why?

This formula comes back to like tree developing. First variable $x_1$ missing or not (2 possbile events). Now after that, for EACH of these events 2 possbile events for $x_2$ so in total 2 \times 2 (2 for $x_1$ , 2 for $x_2$ for each $x_1$'s event) and etc., $2 \times 2 \times 2 \times \dots$ $n$ times = $2^n$.