Q2. Comparison of deterministic prediction algorithms for sports betting ( 30 points). The fictional sport of Broomball commonly organizes tournaments in which two teams, Team A and Team B repeatedly compete for T=10 games, i.e. a "best-of-10" format. At the beginning of each game, you have access to the forecasts of n "sports bookies" who each make a prediction of the winner of the game. Your job is to aggregate these forecasts to make your own prediction for who will win the game. If your prediction is correct, you win $1; if your prediction is incorrect, you lose $1. Consider the following chart that depicts the predicted winner by each of the bookies as well as the actual winner (observed after the predictions were made). (a) (5 points) Formulate this as a binary prediction problem with expert advice by specifying the meaning of each of the values {0,1} and the loss function. Note: there are two ways to specify the meaning of the values {0,1}; either way is fine. (b) (5 points) Evaluate the total loss of the Weighted Majority Algorithm (WMA) with parameter =0.5. In all cases, break ties in favor of A. Would the halving algorithm have been suitable for this problem? Justify why. [Hint: what is the main assumption of the halving algorithm? Is this assumption satisfied here?] (c) (5 points) Re-run WMA but assuming the only available bookies are 1,3 , and 4 . Would the halving algorithm have been suitable here still? Explain why. (d) (5 points) A related deterministic algorithm (but one that we only briefly mentioned in class) is the Follow-the-Leader (FTL) algorithm, which picks at round t the expert i that minimizes s=1t1I[fi(t)= yt. I.e., at time t (today), the expert that has made the fewest mistakes so far, taking the whole history until yesterday (times 1 to t1 ) into account. Evaluate the performance of FTL on bookies 1,3 and 4 , and compare it with the performance of WMA. (e) (5 points) Now, keep only bookies 1 and 4 and repeat the execution of FTL and WMA. Compare the performance and output of the two algorithms on every round. (f) (5 points) Would the above comparison have changed if you ran WMA with a different value of = ? Justify your answer. Q2. Comparison of deterministic prediction algorithms for sports betting ( 30 points). The fictional sport of Broomball commonly organizes tournaments in which two teams, Team A and Team B repeatedly compete for T=10 games, i.e. a "best-of-10" format. At the beginning of each game, you have access to the forecasts of n "sports bookies" who each make a prediction of the winner of the game. Your job is to aggregate these forecasts to make your own prediction for who will win the game. If your prediction is correct, you win $1; if your prediction is incorrect, you lose $1. Consider the following chart that depicts the predicted winner by each of the bookies as well as the actual winner (observed after the predictions were made). (a) (5 points) Formulate this as a binary prediction problem with expert advice by specifying the meaning of each of the values {0,1} and the loss function. Note: there are two ways to specify the meaning of the values {0,1}; either way is fine. (b) (5 points) Evaluate the total loss of the Weighted Majority Algorithm (WMA) with parameter =0.5. In all cases, break ties in favor of A. Would the halving algorithm have been suitable for this problem? Justify why. [Hint: what is the main assumption of the halving algorithm? Is this assumption satisfied here?] (c) (5 points) Re-run WMA but assuming the only available bookies are 1,3 , and 4 . Would the halving algorithm have been suitable here still? Explain why. (d) (5 points) A related deterministic algorithm (but one that we only briefly mentioned in class) is the Follow-the-Leader (FTL) algorithm, which picks at round t the expert i that minimizes s=1t1I[fi(t)= yt. I.e., at time t (today), the expert that has made the fewest mistakes so far, taking the whole history until yesterday (times 1 to t1 ) into account. Evaluate the performance of FTL on bookies 1,3 and 4 , and compare it with the performance of WMA. (e) (5 points) Now, keep only bookies 1 and 4 and repeat the execution of FTL and WMA. Compare the performance and output of the two algorithms on every round. (f) (5 points) Would the above comparison have changed if you ran WMA with a different value of = ? Justify your
