COMP3670/6670 Introduction to Machine Learning
Introduction to Machine Learning
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
COMP3670/6670 Introduction to Machine Learning
Final Exam
• Write your name and UID on the first page (you will be fine if you forget to write them).
• This is an open book exam. You may bring in any materials including electronic and paper-
based ones. Any calculators (programmable included) are allowed. No communication devices
are permitted during the exam.
• Reading time: 30 minutes
• Writing time: 180 minutes
• For all the questions, write your answer CLEARLY on papers prepared by yourself.
• There are totally 9 pages (including the cover page)
• Points possible: 100
• This is not a hurdle.
• When you are asked to provide a justification to your answer, if your justification is incorrect,
you will get 0.
1
• Section 1. Linear Algebra and Matrix Decomposition (13 points)
1. (6 points) Show that it is impossible to have a set of 3 orthogonal non-zero vectors
{v1,v2,v3} in R2.
(Hint: Write v1 = [x1, y1]
T and first assume that x1 = 0. Then, prove it for the case where
x1 ̸= 0, using the first case to help you.)
Solution. We write
v1 =
[
x1
y1
]
v2 =
[
x2
y2
]
v3 =
[
x3
y3
]
As the hint suggests, we first assume that x1 = 0. Then since v1 ·v2 = 0, we have y1y2 = 0.
Since y1 cannot be zero (otherwise v1 = 0) we must have y2 = 0. Since v1 · v3 = 0,
we have x1x3 + y1y3 = y1y3 = 0, and y1 ̸= 0, so y3 = 0. Since v2 · v3 = 0, we have
x2x3 + y2y3 = x2x3 = 0. Now, y2 = 0, so x2 ̸= 0 (else v2 = 0), so x3 = 0. We have that
x3 = 0 and y3 = 0, so v3 = 0, a contradiction.
Now, if any of the x1, x2, x3, y1, y2, y3 were zero, this would also result in a contradiction
in the same way, as by symmetry we can reorder the vectors so the zero was somewhere in
the first vector, and since x1y1 + x2y2 = y1x1 + y2x2, we could swap the x and y values in
all vectors so that x1 = 0, from which the contradiction follows by above.
Now, assume that x1 ̸= 0. v1 · v2 gives
v1 · v2 = 0
x1x2 + y1y2 = 0
x2 =
−y1y2
x1
and similarly
v1 · v3 = 0
x1x3 + y1y3 = 0
x3 =
−y1y3
x1
Then v2 · v3 = 0, so
x2x3 + y2y3 = 0(−y1y2
x1
)(−y1y3
x1
)
+ y2y3 = 0
y21y2y3
x21
+ y2y3 = 0
y2y3
(
y21
x21
+ 1
)
= 0
Then either y2 = 0 (contradiction), or y3 = 0 (contradiction) or
y21
x21
+1 = 0, giving y21 = −x21.
Since the left hand side is non-negative, and the right hand side is non-positive, the only
way to satisfy this equation is y1 = x1 = 0, a contradiction.
2. (7 points) Consider an arbitrary matrix A ∈ R2×2
A =
[
a b
c d
]
We would like A to satisfy the following properties:
(a) A is non-invertible.
(b) A is symmetric.
2
(c) All the entries of A are positive.
(d) A has a positive eigenvalue λ = p > 0.
Find the set of all matrices A (as a function of p) that satisfy all the above constraints.
Solution. A is symmetric, so b = c. We can eliminate c and consider only matricies of the
form
A =
[
a b
b d
]
.
A is non-invertible, so ad − b2 = 0. Also, a, b, d > 0. We have that p > 0 is an eigenvalue,
so we find all eigenvalues using the characteristic polynomial.
(a− λ)(d− λ)− b2 = 0
ad− aλ− dλ+ λ2 − b2 = 0
−aλ− dλ+ λ2 = 0
λ(λ− a− d) = 0
So λ = 0 or λ = a+ d. Since 0 cannot be positive, we have that p = a+ d, or d = p− a. We
can eliminate d.
A =
[
a b
b p− a
]
Finally, since ad − b2 = 0, we have a(p − a) = b2, and hence b = ±√a(p− a). Since all
entries need to be positive, we take the positive root, b =
√
a(p− a). For the square root
to be defined (and not zero), we need a(p − a) > 0, which implies that 0 < a < p. Hence,
the set of all possible A is given by{[
a
√
a(p− a)√
a(p− a) p− a
]
: 0 < a < p
}
as required.
3
• Section 2. Analytic Geometry and Vector Calculus (12 points)
1. (6 points) Find all matrices T ∈ R2×2 such that for any v ∈ R2,
vTv = (Tv)Tv = (Tv)TTv
Solution. Consider v · v = T (v) · v. Let v = [x, y]T . Then
v · v = T (v) · v
x2 + y2 = x(ax+ by) + y(cx+ dy)
x2 + y2 = ax2 + (b+ c)xy + dy2
By choosing x = 0, y = 1, we obtain d = 1, and by choosing x = 1, y = 0 we obtain a = 1.
Then, we choose x = 1 and leave y arbitrary for the moment. Substituting, we obtain
1 + y2 = 1 + (b+ c)y + y2
from which we obtain (b+ c)y = 0 for all y, so c = −b. We now consider the other equation
v · v = T (v) · T (v)
x2 + y2 = (ax+ by)2 + (cx+ dy)2
x2 + y2 = (a2 + c2)x2 + (b2 + d2)y2 + 2(ab+ cd)xy
x2 + y2 = (1 + b2)x2 + (1 + b2)y2 + 2(b− b)xy
x2 + y2 = (1 + b2)(x2 + y2)
1 = 1 + b2
b = 0
So a = 1, b = 0, c = −b = 0, d = 1. So the only matrix that satisfies this property is the
identity.
T =
[
1 0
0 1
]
2. (6 points) Let x,a ∈ Rn×1, and define f : Rn×1 → R as
f(x) = 3 exp(2xTAx)
where exp(x) := ex, the exponential function. Compute ∇xf(x).
Solution. We apply the chain rule. Note that f(x) = g(h(x)), where g : R → R, g(h) =
3 exp(2h) and h : Rn → R, h(x) = xTAx. We have by lectures/assignment that ∇xh(x) =
xT (A+AT ), and by calculus we have that ∇hg(h) = 6 exp(2h). Therefore
df
dx
=
dg
dh
dh
dx
= 6 exp(2h)xT (A+AT ) = 6 exp 2(xTAx)xT (A+AT )
4
• Section 3. Probability (15 points)
Consider the following scenario. I have two boxes, box A and box B. In their initial configuration,
Box A contains 3 red balls and 3 white balls; Box B contains 6 red balls.
We swap the balls in boxes via the following procedure.
Procedure 1:We draw a ball xA uniformly at random from box A, and draw a ball xB uniformly
at random from box B. We place ball xA into box B and place ball xB into box A.
Let RA and RB be random variables representing the number of red balls in box A and box B
respectively.
1. (3 points) Describe the probability mass functions p(Ra = n) and p(Rb = n) for all integers
n ≥ 0 for the initial configuration of the boxes.
Solution. Clearly, box A contains 3 red balls, so
p(RA = n) =
{
1 n = 3
0 n ̸= 3
and box B contains 6 red balls, so
p(RB = n) =
{
1 n = 6
0 n ̸= 6
2. (3 points) After performing Procedure 1, what is the new joint probability mass functions
p(RA = na, RB = bn)?
Solution. We are guaranteed to move a red ball from box B into box A, it is equally likely
that the ball xA chosen from A is red. So, we have a 0.5 probability of nothing changing.
and a probability of 0.5 of adding a red ball to box A and loosing a red ball from box B.
Hence,
p(RA = na, RB = nb) =
0.5 (na, nb) = (3, 6)
0.5 (na, nb) = (4, 5)
0 else