Description
Theory Questions
- Perceptron Lower Bound. Show that for any 0 < γ < 1 there exists a number d > 0, vector w? ∈ Rd and a sequence of examples (x1,y1),…,(xm,ym) such that:
.
(c) Perceptron makes mistakes on the sequence.
(Hint: Choose and let {xi}i be the standard basis of Rd)
- Halving Algorithm. Denote by AHal the Halving algorithm you have seen in class. Let d ≥ 6, X = {1,…,d} and let H = {hi,j : 1 ≤ i < j ≤ d} where
.
Show that M(AHal,H) = 2.
(Definition of mistake bound M(A,H): Let H be a hypothesis class and A an online algorithm. Given any sequence S = (x1,h?(x1)),…,(xm,h?(xm)) where m is an integer and h? ∈ H, let MA(S) be the number of mistakes A makes on the sequence S. Then M(A,H) = supS MA(S)).
- Interval growth function. The goal of this exercise is to compute the growth function of the interval hypothesis class H = {ha,b : a < b} where ha,b(x) = 1 if x ∈ [a,b] and 0 otherwise. In other words, your goal is to give an explicit expression to ΠH(m) = maxC😐C|=m |HC| where HC is the restriction of H on the set C.
- Sample complexity of agnostic PAC. Let H be a hypothesis class of functions from a domain X to {0,1} and let the loss function be the 0-1 loss. Assume that V Cdim(H) = d < ∞. Show that if
then
Pr[
To prove the above claim you can use the following lemma without proving it:
Lemma: Let a ≥ 1 and b > 0. Then: x ≥ 4alog(2a) + 2b → x ≥ alog(x) + b.
You can also assume that δ is as small as you desire.
- Prediction with Log-Loss. Consider a prediction setting with input X and true label Y ∈ {0,1} (i.e., it has two possible values: zero and one). The predictor h(x;θ) returns a number in [0,1] via the function
. (1)
Here θ(x) is a function of x which defines h. Note that this construction makes sure that h(x) ∈ [0,1].
Consider the loss function (this is an instance of the well-known cross-entropy loss, which we will learn more about):
∆(y,yˆ) = −y log(ˆy) − (1 − y)log(1 − yˆ) (2)
Find the value of θ(x) that minimizes E[∆(Y,h(X;θ))]. Use these to express h(x) as a simple function of E[Y |X].
