Machine Learning Theory (CSC 482A/581A) Problem Set 1 Due on Friday, October 8th, 7pm Instructions: • You must write up your solutions individually. • You may have high-level discussions with 1 other...

machine learning, you must type up solution, not handwritten


Machine Learning Theory (CSC 482A/581A) Problem Set 1 Due on Friday, October 8th, 7pm Instructions: • You must write up your solutions individually. • You may have high-level discussions with 1 other student registered in the course. If you discuss problems with another student, include at the top of your submission: their name, V#, and the problems discussed. • Your must type up your solutions and are encouraged to use LaTeX to do this. For any problems where you only have a partial solution, be clear about any parts of your solution for which you have low confidence. • Please be sure to submit your solutions via Brightspace by the due date/time indicated above. This is a hard deadline. Questions: 1. Let X = R2 and take C to be the class of concentric circles C = {cr : r ≥ 0}, where, for each nonnegative real number r ≥ 0, we have cr(x) = 1 [ ‖x‖2 ≤ r ] . Prove that C is PAC learnable. In particular, show a PAC learning algorithm which, given a training sample of size n ≥ log 1 δ ε , finds with probability at least 1− δ a hypothesis f̂ ∈ C for which R(f̂) ≤ ε. 2. Devise an efficient mistake bound learner for the concept class k-term DNF over X = {0, 1}d. The runtime and mistake bound of your algorithm both should be polynomial in d; you may treat k as a constant. 3. Let X = {0, 1}d and consider PAC learning a finite concept class C. Assume that the inputs are drawn i.i.d. from an unknown distribution P over X , and the labels are generated via the rule Y = c(X) for some c ∈ C. Let’s call this problem the “clean” problem; so, in the clean problem, the training sample consists of random examples of the form (X,Y ) for X ∼ P and Y = c(X). Next, consider the following “corrupted” problem: Each time we request a random example (X,Y ), with probability α(X) ∈ [0, 1] the value of the label Y is flipped. Call the resulting label Ỹ . Thus, Ỹ = { −Y with probability α(X) Y with probability 1− α(X) In the corrupted problem, the examples are of the form (X, Ỹ ), and so the labels are noisy. 1 (a) Using c and α, derive an expression for the Bayes classifier for the corrupted problem. (b) For the remaining questions, assume that α(x) = 14 for all x ∈ X . What is the Bayes classifier for the corrupted problem? (c) What is the Bayes risk for the corrupted problem? (d) Let cε ∈ C be a hypothesis for which Pr(cε(X) 6= c(X)) = ε > 0. What is the risk (expected zero-one loss) of cε for the corrupted problem? (e) Design an algorithm for PAC learning C given access only to corrupted labeled examples (X1, Ỹ1), . . . , (Xn, Ỹn). That is, your algorithm should, with probability at least 1 − δ, output a concept f̂ ∈ C for which EX∼P [f̂(X) 6= c(X)] ≤ ε. Your algorithm should be statistically efficient (you should mention the sample size n required, and n should be polynomial in 1ε and 1 δ ), but it need not be computationally efficient. Please explain why your algorithm is correct. 2
Oct 05, 2021
SOLUTION.PDF

Get Answer To This Question

Related Questions & Answers

More Questions »

Submit New Assignment

Copy and Paste Your Assignment Here