Consider an ensemble learning algorithm that uses simple majority voting among M learned hypotheses (you may assume M is odd). Suppose that each hypothesis has error & where 0.5 > >0 and that the errors made by each hypothesis are independent of the others'. Show your work. a. (5 pts) Calculate a formula for the error of the ensemble algorithm in terms of M and E. The ensemble makes an error just in case (M+1)/2 or more hypotheses make an error simultaneously. Recall that the probability that exactly k hypotheses make an error is P(exactly k hypotheses make an error) = (M) *(1-) (M-k) where (), read "M choose k," is the number of distinct ways of choosing k distinct objects from a set of M distinct objects, calculated as (1) where x!, read "x factorial," is x!= 1*2*3*...*x. Then, M! k!(M-k)! P(error) = E=(M+1)/2 P (exactly k hypotheses make an error) = E=(M+1)/2() Ek(1-E) (M-k) b. (5 pts) Evaluate it for the cases where M = 5, 11, and 21 and c = 0.1, 0.2, and 0.4. M=5 M=11 M=21 0.00856 2.98e-4 1.35e-6 0.0579 0.0117 9.70e-4 0.317 0.247 0.174 -0.1 0.2 -0.4 c. (5 pts) If the independence assumption is removed, is it possible for the ensemble error to be worse than &? Produce either an example or a proof that it is not possible. YES. Suppose M=3 and = 0.4 = 2/5. Suppose the ensemble predicts five examples el...e5 as follows. el: M1 and M2 are in error, so they out-vote M3 and the prediction of el is in error. e2: M1 and M3 are in error, so they out-vote M2 and the prediction of e2 is in error. e3: M2 and M3 are in error, so they out-vote M1 and the prediction of e3 is in error. e4, e5: None of the hypotheses make an error on e4 or e5, so the predictions of e4 and e5 are correct. The result is that each hypothesis has made 2 errors out of 5 predictions, for an error on each hypothesis of 2/5 = 0.4 = &, as stated. However, the ensemble has made 3 errors out of 5 predictions, for an error on the ensemble of 3/5=0.6>=0.4.