COMP0036
LSA - Assignment 1
September 16, 2019
1
1 Question 1
1.1 Answer for (a)
Using the ordinal least squares(OLS) method to find such a curve model is not feasible.
Because the OLS leads to no unique solution.
A cubic function to model the relationship between x and y takes the following format:
y =
∑
ni>=0,n1+n2+n3+n4+n5=3
w
∏
1≤i≤5
xnii
The real number of the independent variable in the model is C38 = 56, which is larger
than the sample number 50. Assuming Z is the real design matrix of this model, then
the OLS solution takes the form:
W = (ZTZ)−1ZTy
As mentioned before, Z is a matrix of 50 × 56, thus ZTZ is non-invertible. That is to
say, we don’t have enough equations to specify the number of unknowns.
1.2 Answer for (b)
If one of the attributes is discarded from the cubic model,then the number of the inde-
pendent variables in the model is C37 = 35 ,and the dimension of the design matrix is
50× 35. We now have enough equations to determine the unknown parameters. So the
problem in (a) can be solved.
1.3 Answer for (c)
In (a) we indeed encountered an over fitting problem, the model pays much more at-
tention to the performance of the in-sample data and shows poor performance to the
out-of-sample data. To improve this, we need to consider a shrinkage method that
could control the complexity of the model. Ridge regression can do this by adding some
penalty to the weights in the model. Ridge regression adds the `2 penalty to the weights
by adding a threshold t as ‖ w ‖22 < t. Using the theory of Lagrange Multipliers, we can
rewrite the objective function as:
argmin
w
1
2
n∑
i=1
(y(i) − wx(i))2 + λ
2
‖ w ‖22
By finding the optimal weight, we can get the following solution:w = (XTX+λI)−1XTy.
In this question, our design matrix is Z, so we change X to Z.The rank of ZTZ + λI is
always 56, so ZTZ + λI is invertible and we can find a unique solution for the model.
2
1.4 Answer for (d)
If we need to do some feature selection and only hold the most important features, Ridge
regression would be quite limited. We should use the LASSO method. Different from
the Ridge regression, Lasso uses the `1 − norm to shrikage some weight to 0. So if we
want to hold some important features in our model and discard those unimportant, we
can add a `1-norm regularization to our objective function and use a gradient descent
method to find the optimal solution. Finally, we just need to keep the features with
nonzero weight.
3
2 Question 2
2.1 Answer for (a)
As ∼ N(0, α) and x are independent variables, so y ∼ N(wx, α).
P (S|w) =
n∏
i=1
P ((x(i), y(i))|w) =
n∏
i=1
(2piα2)−
1
2 exp(−(y
(i) − wx(i))2
2α2
) = (2piα2)−
n
2 exp(−
∑n
i=1(y
(i) − wx(i))2
2α2
)
So we can get A and B as, A = (2piα2)−
n
2 and B = −
∑n
i=1(y
(i)−wx(i))2
2α2
2.2 Answer for (b)
Considering the Bayesian theory, w is now a random variable and w ∼ N(0, β).As said
before y ∼ N(wx, α), so we can get the posterior distribution of w as:
P (w|x, y) = P (x, y, w)
P (x, y)
=
P (y|x,w)P (w)
P (x, y)
We can see P (x, y) is a constant that is not related to w, we assume P (x, y) = Z,then
P (w|x, y) = 1
Z
P (y|x,w)P (w)
=
1
Z
(2piα2)−
1
2 exp(−(y − wx)
2
2α2
)(2piβ2)−
1
2 exp(− w
2
2β2
)
= (2piα2)−
1
2 (2piβ2)−
1
2 exp(−((y − wx)
2
2α2
+
w2
2β2
))
2.3 Answer for (c)
The Maximum A Posteriori estimation(MAP) can be derived by the following equation:
argmax
w
P (w|x, y)⇔ argmax
w
P (y|x,w)P (w)
Then we use the log likelihood to find this solution, the log likelihood takes the following
form:
L = argmax
w
ln(
n∏
i=1
P (y(i)|x(i), w)P (w))
= − 1
2α2
n∑
i=1
(y(i) − wx(i))2 − 1
2β2
w2 + const
Taking the derivative of the above function, we can get the MAP estimate of w as:
wMAP =
∑n
i=1 x
(i)y(i)
α2
× (
∑n
i=1(x
(i))2
α2
+
1
β2
)−1
4
2.4 Answer for (d)
No, this solution is not unique. Because MAP estimation is only a point estimate of w,
while in Bayesian theory, w is a random variable. We only use MAP to do a sort of
halfway house in Bayesian inference.
2.5 Answer for (e)
The MAP estimation of w reminds me of the MLE(Maximum Likelihood Estimator)
method. From the analysis(c) we can find, the biggest difference between MAP estima-
tion and MLE methods is that MAP takes the prior distribution of w into consideration.
So if the prior distribution of w is a uniform distribution, then these two method will
give the same result.
5
3 Question 3
3.1 Answer for (a)
Discriminative Classification, also known as the distribution-free method, is to learn a
classifier by giving the optimal loss function directly. Like SVM, it just tries to learn
a suitable loss function that can minimize the classification loss. This is different from
Generative Classification methods. As Generative Classification always makes use of the
probability distribution of the sample, and give the optimal result by maximizing the
posterior probability that a sample belonged to a class.
3.2 Answer for (b)
The main purpose of classification is to find a relationship between the observed sample x
and the classification y. Due to y being a binary variable, we introduce a latent variable
y∗ and map the latent variable to y by:
y =
{
1, if y∗ ≥ 0
0, if y∗ < 0
We assume y∗ has the following relationship with x: y∗ = wx+, and ∼ Logsitic(0, 1)
PY (y = 1|x) = P (y∗ ≥ 0|x)
= P (wx+ ≥ 0)
= P ( ≥ −wx)
= 1− P ( < −wx)
= 1− 1
1 + ewx
=
ewx
1 + ewx
=
1
1 + e−wx
And this is equivalent to the posterior probability described in question(b)
3.3 Answer for (c)
If we allow the Logistic parameters to take more general values a ∈ R and b > 0, the
final logistic regression model will take the form: PY (y = 1|x) = 11+exp(−wx+a
b
)
.
Then, unlike the logistic regression model stated in (b), we will get a differnt linear
discriminant separating hyperplane. The hyperplane in this situation is defined as:
wx+ a = 0
6
3.4 Answer for (d)
When we use a Gaussian Noise Latent Variable Model, that is we assume ∼ N(0, 1),
then similar to (b), we can describe the posterior of PY (y|x) as:
PY (y = 1|x) = P (y∗ ≥ 0|x)
= P (wx+ ≥ 0)
= P ( ≥ −wx)
= 1− P ( < −wx)
= 1− Φ(−wx)
= Φ(wx)
=
1√
2pi
∫ wx
−∞
e−
t2
2 dt
And PY (y = 0|x) = 1− PY (y = 1|x).
3.5 Answer for (e)
There indeed exists some difference between these two models when it comes to outliers
in the sample. If we compare the distribution, we will find out that the the rising slope
of the model derived in(d) is steeper than the model derived in (b). So Gaussian Noise
Latent Variable Model will be more robust to outliers than the Logistic Noise Latent
Variable Model.
3.6 Answer for (f)
When k=2, there are two classes. In order to make it comform to our previous notation,
we assume the two classes are 0 and 1.
PY (y = 1|x) = e
w1x
ew0x + ew1x
=
1
1 + e−(w1−w0)x
Let w = w1 − w0, then we can see that this is a logistic regression.
3.7 Answer for (g)
For the Multinomial Logistic Regression, when K > 2, the sample belonging to class
j(1 ≤ j < K) must satisfy PY (y = j|x) > PY (y = i|x), ∀i, i 6= j, where 1 ≤ i < K. That
is:
exp(wjx)∑K
k=1 exp(wkx)
>
exp(wix)∑K
k=1 exp(wkx)
⇒ exp(wjx) > exp(wix)
⇒ wjx > wix
⇒ (wj − wi)x > 0
7
So we can get the classification boundary for Multinomial Logistic Regression, and we
can see the classification boundary is a series linear discriminant separating hyperplane.
8