We want to learn an unknown function f that takes n input arguments x1, x2 , . . . , x n and produces one output y. The input variables are boolean, i.e. each xi can be either T (true) or F (false). The output variable y can take on one of k different values. An example is a healthcare scenario where each of the xi corresponds to a symptom (the patient has the symptom or not), and y corresponds to the diagnosis (there are k diseases that can be diagnosed).

(a) Lets consider the hypothesis space H consisting of all functions that take n such 2-valued input arguments and produce one k-valued output. How many hypotheses are there in H? Briefly explain your answer.

(b) Is the inductive bias in H high or low? What are the implications of this for a machine learning algorithm that tries to learn the unknown function f from training data?

(c) Say that you get a training dataset with p different training examples, each of the form ((x1, x2, . . . , xn), y). How many hypotheses in H are consistent with these training examples? Briefly explain your answer.