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

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.

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.

• @ThePointer In general, the typical machine learning models (i.e. typical neural networks) do not really or properly account for missing data, that's why I am suggesting you have a look at Bayesian neural networks, which could be used to solve this issue (i.e. learn multiple functions or distributions, if you want, to account for missing data, but not only). – nbro Feb 20 at 14:54
• As I say in my answer, their description is vague. They try to give an intuitive rather than rigorous description of the concept, but, in my opinion, this turns out to be confusing. Anyway, suppose your data is described by $n$ binary features $x_1, \dots x_n$. So, each of these features $x_i$ can actually be thought of as a realization of a binary random variable (i.e. a r.v. that can take 2 realizations) $X_i$. They say that you can simply learn $p(x_1, \dots, x_n)$ rather than learning $p(x_i)$, for all $i$, and then use marginalization to derive each of $p(x_i)$ from $p(x_1, \dots, x_n)$. – nbro Feb 20 at 15:04
• When you see $2^n$, you can think of it as a multiplication of $n$ 2 (of course!). Now, if you remember the basics of combinatorics, you will also remember that $2^n$ means that, in the 1st case (e.g. if you toss a coin) you have 2 possibilities, in the 2nd case you also have 2 possibilities, in the 3rd case you also have 2 possibilities, and so on. So, in total, you have $2^n$ combinations. They say that you can obtain $2^n$ classifications functions, I think, because, for each of the features, you have two possibilities, so you have $2^n$ possible combinations of these features. – nbro Feb 20 at 15:14
• If you look at how marginalization works, you will see that it is basically a sum or integral over all possible combinations of the other variables. Given that $x_i$ can have two values (e.g. $0$ or $1$), then you will have $2^n$ $p(x_i)$ (i.e. $p(0)$ and $p(1)$) for all $i$. I think that's what they mean by having $2^n$ classification functions. – nbro Feb 20 at 15:24
• @ThePointer I am pretty sure that they implicitly (or maybe explicitly, given that before or after this paragraph they may mention that they are considering binary random variables) assume that the features are binary, otherwise, I can't see where the $2^n$ comes from (off top of my head). – nbro Feb 20 at 15:42