ESE 504-542 : Statistics for Data Science
Instructor: Hamed Hassani, Shirin Saeedi
Spring 2019
Final Examination
NAME
One two-sided note-sheet allowed.
Grade (y/n) Score Max. Score
Problem 1 40
Problem 2 40
Problem 3 20
TOTAL 100
Problem 1 (40 points) [Simple Linear Regression.]
Consider the following simple linear regression problem with the data set
(x1, y1), (x2, y2), . . . , (xn, yn).
yi = β0 + β1xi + i (1)
Assume all assumptions for linear regression are met. Particularly, i are
i.i.d. random variables where i ∼ N(0, σ2).
1. Derive the estimators βˆ1 and βˆ0 by minimizing the residual sum of
squares i.e., by solving
min
β0,β1
n∑
i=1
(yi − β0 − β1xi)2 .
2. Derive the estimators βˆ1 and βˆ0 using maximum likelihood estimation
i.e., by solving
max
β0,β1
log `(β0, β1),
where
`(β0, β1) =
n∏
i=1
Pr (yi | β0, β1, xi) .
Note that Pr (yi | β0, β1, xi) is the probability of observing yi given the
values of β0, β1 and xi. Compare the results with part 1.
3. Show that your estimates are unbiased i.e., show that
E
[
βˆ0
]
= β0, E
[
βˆ1
]
= β1.
4. Consider the case when heteroskedasticity is present, i.e., i ∼ N(0, σ2i ).
Repeat part 2 under heteroskedasticity.
Problem 2 (40 points) [Weighted K-Means Clustering.]
Consider data points x1, x2, · · · , xn ∈ Rd. For each data point xi we have
assigned a positive number wi ≥ 0 which indicates the importance of that
data point. Our goal is to provide an algorithm for the following weighted K-
Means clustering problem: Find K centers c1, c2, · · · , cK ∈ Rd that minimize
the objective
n∑
i=1
wi × min
j∈{1,··· ,K}
||xi − cj||2. (2)
1. Assume that K = 1. Find the optimal centroid that minimizes (2).
2. For a given K, Extend the K-Means algorithm taught in class to the
weighted setting. Explain precisely what the algorithm is and justify
your answer
Problem 3 (20 points) [Basic Questions about Learning Theory.]
1. Give a precise definition of “PAC Learnability”.
2. Explain briefly why finite hypothesis classes are PAC learnable.
3. What property should an infinite hypothesis class have in order to be
PAC learnable?