Hypothesis space and inductive bias.

(4 points) We want to learn an unknown function

f

that takes

n

input arguments

x

1

, x

2

, . . . , x

n

and produces one output

y

. The input variables

are boolean, i.e. each

x

i

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

x

i

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 ((

x

1

, x

2

, . . . , x

n

)

, y

). How many hypotheses in

H

are consistent with these training

examples? Briefly explain your answer.