142 + (1,1) + to to +o to (0,0) + +• to 11
In this problem, we consider the class of n-dimensional axis-aligned boxes. Each function c in this class is specified by a
set of 2n values ℓ1, . . . , ℓn and u1, . . . , un in [0, 1], which defines an axis-aligned n-dimensional box. Given an n-dimensional
input vector x, c(x) is defined to be 1 (or ‘+’) if for every i ∈ {1, . . . , n} the i’th coordinate of x lies in [ℓi
, ui
]. Otherwise,
c(x) is defined to be 0 (or ‘-’) .
An example of a 2-dimensional axis-aligned box is shown in the figure below.
(a) Let C be the class of n-dimensional axis-aligned boxes, and c ∈ C be the unknown target function. State an efficient
algorithm that takes as input an arbitrary set of points x1, x2, . . . , xm each a point in n-dimensional space, and their
corresponding labels c(x1), c(x2), . . . , c(xm), and outputs a function h ∈ C that is consistent with this data. Your
algorithm should run in polynomial time in m, n and facilitate answering part (b) below.
Let D be an arbitrary, unknown distribution, and let c be an arbitrary, unknown n-dimensional axis-aligned box.
Suppose your algorithm from part (a) is given as input m points x1, x2, . . . , xm drawn i.i.d. from D and their
corresponding labels c(x1), c(x2), . . . , c(xm). Let h be the function output by your algorithm. Let δ and ϵ be fixed
parameters in (0, 1/2). Without referring to VC dimension, state and prove an upper bound for m to ensure accuracy
ϵ with confidence parameter δ? Don’t worry about getting the best possible constant factors in your bound, just focus on the important parameters (n, δ, ϵ).
Hint: you can use the fact that (1 − x)1/n ≤ 1 − x/n for any x ≤ 1 and positive integer n.
Step by step
Solved in 2 steps with 3 images
