Problem 2 Consider the following variant of the Online Mistake-Bound Learning model, which we call the cut-to-the-chase OLMB model: At the start of each trial, If there exists an X e X such that the learner's current hypothesis h :X + {0,1} has h(x) = c(x) (where ce C is the target concept), then the learner is always provided with such an example. (In other words, the environment that the learner is interacting with always causes the learner to make a mistake at each trial whenever possible.) If h(x) = c(x) for every 3 e X, then the learner is heartily congratulated on a job well done and the learning process ends. 1 Suppose that the instance space is X = {1,...,N}, the concept class C contains M concepts C1, ...,CM, and you are learning an unknown target concept ce C in the cut-to-the-chase OLMB model. Give an algorithm that makes at most O(log M) mistakes and has total runtime O(M) (summing the total runtime of each trial across all trials). (Hint #1: Recall that as the learner you know" X and C; more precisely, you may suppose that you have access to an M x N binary matrix where the (i,j) entry of the matrix is ci(j), and that you can read an element x e X and access an element of this matrix in unit time. Hint #2: Take a look at the first few pages of Section 3 of the Littlestone paper.) Problem 2 Consider the following variant of the Online Mistake-Bound Learning model, which we call the cut-to-the-chase OLMB model: At the start of each trial, If there exists an X e X such that the learner's current hypothesis h :X + {0,1} has h(x) = c(x) (where ce C is the target concept), then the learner is always provided with such an example. (In other words, the environment that the learner is interacting with always causes the learner to make a mistake at each trial whenever possible.) If h(x) = c(x) for every 3 e X, then the learner is heartily congratulated on a job well done and the learning process ends. 1 Suppose that the instance space is X = {1,...,N}, the concept class C contains M concepts C1, ...,CM, and you are learning an unknown target concept ce C in the cut-to-the-chase OLMB model. Give an algorithm that makes at most O(log M) mistakes and has total runtime O(M) (summing the total runtime of each trial across all trials). (Hint #1: Recall that as the learner you know" X and C; more precisely, you may suppose that you have access to an M x N binary matrix where the (i,j) entry of the matrix is ci(j), and that you can read an element x e X and access an element of this matrix in unit time. Hint #2: Take a look at the first few pages of Section 3 of the Littlestone paper.)
