Problem 5 In this problem you'll think about an OLMB type learning scenario in a setting where there are infinitely many possible target concepts. Let X be the infinite domain {1, 2, ... } of all natural numbers. Suppose that ci, C2, ... is an enumeration of some infinite set of computable 0/1-valued concepts over X. 1 Suppose you are learning an unknown function c, which is guaranteed to be one of the ci's, in the online mistake-bound model. (i) (easy) Give a learning algorithm which is guaranteed to make at most t prediction mistakes, where t is the least index such that c= ct. (ii) Now give a learning algorithm which is guaranteed to make at most O(log t) prediction mis- takes, where t is the least index such that c= ct. (iii) Now give a learning algorithm which is guaranteed to make at most O(log t) prediction mistakes, where t is the least index such that c=ct. (Hint: Think about how you can modify your solution from (ii).) Problem 5 In this problem you'll think about an OLMB type learning scenario in a setting where there are infinitely many possible target concepts. Let X be the infinite domain {1, 2, ... } of all natural numbers. Suppose that ci, C2, ... is an enumeration of some infinite set of computable 0/1-valued concepts over X. 1 Suppose you are learning an unknown function c, which is guaranteed to be one of the ci's, in the online mistake-bound model. (i) (easy) Give a learning algorithm which is guaranteed to make at most t prediction mistakes, where t is the least index such that c= ct. (ii) Now give a learning algorithm which is guaranteed to make at most O(log t) prediction mis- takes, where t is the least index such that c= ct. (iii) Now give a learning algorithm which is guaranteed to make at most O(log t) prediction mistakes, where t is the least index such that c=ct. (Hint: Think about how you can modify your solution from (ii).)