1. Often in binary classification we are interested in the differences in the output of our...

Transcribed Image Text:

1. Often in binary classification we are interested in the differences in the output of our current classifier 9 and an unknown function f that we are trying to learn. It is common in these cases to examine the quantity f(x)g(x). Let D be an arbitrary distribution on the domain {-1, 1}", and let fƒ, g: {−1,1}n → {−1, 1} be two Boolean functions. Prove that Pr~D[f(x) g(x)] - 1 – Ex~D[ƒ(x)g(x)] 2 Would this still be true if the domain were some other domain (such as R", where R denotes the real numbers, with say the Gaussian distribution) instead of {-1,1}"? If yes, justify your answer. If not, give a counterexample. Note only the domain is changing; the output is still Boolean. 1. Often in binary classification we are interested in the differences in the output of our current classifier 9 and an unknown function f that we are trying to learn. It is common in these cases to examine the quantity f(x)g(x). Let D be an arbitrary distribution on the domain {-1, 1}", and let fƒ, g: {−1,1}n → {−1, 1} be two Boolean functions. Prove that Pr~D[f(x) g(x)] - 1 – Ex~D[ƒ(x)g(x)] 2 Would this still be true if the domain were some other domain (such as R", where R denotes the real numbers, with say the Gaussian distribution) instead of {-1,1}"? If yes, justify your answer. If not, give a counterexample. Note only the domain is changing; the output is still Boolean.