Week 5 | Solve With Instructors
Q1) Suppose you are given three training instance (x 1 , y 1 ), (x 2 , y 2 ) and (x 3 , y 3 ) as follows:
1 1 x y 0 1 x y 1 0
(x 1 , y 1 ) = , , ( 2, 2) = , , ( 3, 3) = , ,
0 1 1
where each x i is a data point and y i is its corresponding label. Your goal is to predict the output y based on the features where
1
T w1 2
y = X w where w = . Find the w that minimizes ‖y - y‖ where y = 1 .
w2
0
Hint: Use the below formula to calculate the inverse of a 2 × 2 matrix
-1
a b 1 d -b
=
c d det(A) -c a
Solution:
1
Given matrix X =
1 0 1 and label vector y
= 1 ,
0 1 1
0
1 0
XX T
1 0 1 2 1
= 0 1 =
0 1 1 1 2
1 1
-1 1 2 -1
XX T =
3 -1 2
Using normal equations
-1
w = XX T Xy
1 2 -1 1 1 1
1 0 1
= 1 =
3 -1 2 0 1 1 3 1
0
Q2) For the dataset given below
2
1 2 3 4 y 3
Xd×n = , =
2 1 4 3 1
3
0
Initialize w 0 = be the initial vector with learning rate 𝜂 = 0.01. Let w gd be the updated weight after one iteration of gradient
0
descent and w sgd be the updated weight after one full iteration of Stochastic gradient descent by taking first two and then next
1 T 2
two data point for the sample. Compute ‖w gd - w sgd ‖. For all the calculations, consider ⏰ X w - y ⏰ as your loss function.
2⏰ ⏰
Solution:
Gradient Descent
w gd = w 0 - 𝜂 XX T w 0 - Xy
1 2 2
0 1 2 3 4 2 1 0 1 2 3 4 3
= - 0.01 -
0 2 1 4 3 3 4 0 2 1 4 3 1
4 3 3
0 0 23
= - 0.01 -
0 0 20
0 0.23 0.23
= + =
0 0.20 0.20
Stochastic Gradient Descent
➔ For the first two data points
(1 ) T
w sgd = w0 - 𝜂 Xbatch1 Xbatch1 w 0 - Xbatch1 y
0 1 2 1 2 0 1 2 2
= - 0.01 -
0 2 1 2 1 0 2 1 3
0 8
= + 0.01
0 7
0.08
=
0.07
➔ For the next two data points
(2 ) (1 ) (1 )
w sgd = wsgd - 𝜂 Xbatch2 Xbatch2 T w sgd - Xbatch2 y
0.08 3 4 3 4 0.08 3 4 1
= - 0.01 -
0.07 4 3 4 3 0.07 4 3 3
0.08 3.68 15
= - 0.01 -
0.07 3.67 13
0.08 11.32
= + 0.01
0.07 9.33
0.1932
=
0.1632
1 (1 ) (2 )
Final w sgd is given by w sgd + w sgd .
2
1 (1 ) (2 )
w sgd = w sgd + w sgd
2
1 0.08 0.1932
= +
2 0.07 0.1632
0.1366
=
0.1166
Computing ‖w gd - w sgd ‖
⏰ 0.23 0.1366 ⏰
-
⏰ 0.20 0.1166 ⏰
⏰ ⏰
≈ 0.073
Q3) Consider the following data-points for a regression problem:
{(c1 · u, y1 ), ⋯ , (cn ⋅ u, yn )}
Here, c i is some real number and u ∈ R d and u ≠ 0. Fit a linear regression model for this dataset and find the predicted value
for the test-point x test = 5 ⋅ u. You can assume that c i ≠ 0 for some i. The following values are given to you:
n n
∑ ci ⋅ yi = 20, ∑ ci2 = 100
i=1 i=1
Solution: The loss is
n
L( w ) = ∑ w T x i - y i
2
i=1
The gradient is
n
∇ L( w ) = 2 · ∑ w T x i - y i x i
i=1
Replace x i with c i · u
n
∇ L( w ) = 2 · ∑ w T c i · u - y i c i · u
i=1
n
= 2·∑ w T u ci2 - ci yi u
i=1
On setting ∇L(w) to zero, we get
n
∑ cy
i=1 i i
wTu =
∑ n ci2
i=1
= 0.2
Now, the prediction for a point 5 · u is w T (5 · u) which turn out to be 1.
Q4) Kernel regression with a polynomial kernel of degree 3 is applied on a dataset { X, y }. Let the weight vector be given by
T
w = 𝜙(X) 1.3 0.6 -0.2 -0.7
th T
Here 𝜙(X) is the transformed data matrix whose i column is 𝜙(x i ). What will be the prediction for the data point 0 0 0 0
?
Solution:
The prediction of test data point in kernel regression is
n
∑ 𝛼 i · k(x test , xi )
i=1
Given kernel function is
3
k ( x , y) = 1 + x T y
T
Now, as our test point is 0 0 0 0 , the dot product term in kernel function will be zero with each data point. So, for each
data
point x i the value of kernel function would be just 1. Hence, prediction will be
n
∑ 𝛼 i · k(x test , xi ) = 1.3(1) + 0.6(1) - 0.2(1) - 0.7(1)
i=1
=1
Q5) Consider the following data points.
{(1, 2), (3, 1), (-1, 4)}
The projection of the label vector onto the span of the feature vectors of the data points is (2, 11, -8). Predict the label of for
(7, 3) using linear regression.
ANSWER : 25
The projection of the label vectors onto the span of the feature vectors of the data points is also the prediction for the labels of the
data points.
X T w = ypred
1 2 2
w1
3 1 × = 11
w2
-1 4 -8
Solve the linear equations to get w 1 = 4 and w 2 = - 1.
The prediction of label for (7, 3) is given as :
(7, 3) · (4, -1) = 25
Q6) We have the following data points
D = {(x1 , y1 ),..., (xn , yn )}
x1 ,..., xn ∈ R d
y1 ,..., yn ∈ R
We get a w after linear regression such that :
n
∑ (yi - f(xi )) 2 = 0
i=1
T
where f(x i ) = w x i
Which of the following options are true
A. w is a result of overfitting
B. Every datapoint in D is on some hyperplane in R d
C. Every datapoint in D is on some hyperplane in R d+1
D. Let Y = (y 1 ,..., y n ) T and let Y p be the projection of Y onto the span of the feature vectors of x 1 ,..., x n . Then
||Y - YP || > 0
ANSWER : C
It is given that the squared error for linear regression is 0. This would mean that there is actually a linear relationship between the
features and the labels. Here, f(x i ) is not memorizing the labels of every data point. Therefore, we cannot say that w is a result
of overfitting.
Since the error is zero, every point in D will be on a hyperplane in R d+1 .
The projection of labels onto the feature space is the prediction for the labels. Since the error is 0, Y p will be the same as Y,
therefore, ||Y - Y P || = 0
Q7) f(x) = x 2 - 2x + 1. We are trying to find an x at which the function's value is minimum. We will use gradient descent by
initializing x 0 = 0. After how many iterations does the algorithm stop? Use 𝜂 = 0.5
ANSWER : 2
f'(x) = 2x - 2
ITERATION 1
x 1 = x 0 - 𝜂 ▽ f( x 0 )
= 0 - 0.5 × f'(0)
= 0 - 0.5 × (-2)
=1
ITERATION 2
x 2 = x 1 - 𝜂 ▽ f( x 1 )
= 1 - 0.5 × f'(1)
= 1 - 0.5 × 0
=1
x2 = x1
The algorithm stops after two rounds.
Q8) We have n data points x1 ,..., xn ∈ R. y1 ,..., yn ∈ R are the corresponding labels. We form a new dataset of n points given
as :
D = {(x1 , y1 ),..., (xn , yn )}
On running PCA on D, we get l 1 as the line along the first principal component.
On running Linear regression on D, we get l 2 which is of the form y = wx.
n
Assume ∑ (x i , y i ) = (0, 0). Choose the correct options.
i=1
Abbreviations
• SSPD - Sum Squared Perpendicular Distance
• SSVD - Sum Squared Vertical distance
A. The SSPD from the data points in D to l 1 is the minimum possible SSPD to any line in R 2
B. The SSPD from the data points in D to l 2 is the minimum possible SSPD to any line in R 2
C. The SSVD from the data points in D to l 1 is the minimum possible SSVD to any line in R 2
D. The SSVD from the data points in D to l 2 is the minimum possible SSVD to any line in R 2
ANSWERS : A,D
PCA minimizes ||X - X t w w|| 2
Linear Regression minimizes ||X T w - Y|| 2
Left : Error minimization by PCA
Right : Error minimization by Linear Regression
QUESTION 9
QUESTION 10