Description
f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y)
for all x,y ∈ R and θ ∈ [0,1]. Since the function is linear, we get an equality
a(θx + (1 − θ)y) + b = θ (ax + b) + (1 − θ)(ay + b)
2. For any elements x,y in the common fixed domain we have that
g(θx + (1 − θ)y)) = Xfi(θx + (1 − θ)y)
i
≤ X[θfi(x) + (1 − θ)fi(y)]
i
= θ Xfi(x) + (1 − θ)Xfi(y)
i i
= θg(x) + (1 − θ)g(y).
3. Using convexity of f, we know that
f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y).
Further since g is increasing, we can apply g on both sides of the above equation to get
g(f(θx + (1 − θ)y)) ≤ g(θf(x) + (1 − θ)f(y)).
Finally, using the convexity of g we get
g(f(θx + (1 − θ)y)) ≤ g(θf(x) + (1 − θ)f(y))
≤ θg(f(x)) + (1 − θ)g(f(y)).
4. Let x and y be two elements in the domain. Let x = w⊤x+b and y = w⊤y +b. Let θ ∈ [0,1]. We need to show that
f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y),
which follows since by assumption f was convex.
5. Assume that it has two global minima at x⋆ and y⋆. Let z⋆ = (x⋆ +y⋆)/2. Then, since f is strictly convex, we have , which means neither points x⋆ and y⋆ are global minima. This contradicts the initial assumption and proves that a strictly convex function has a unique global minimizer.
2 Extension of Logistic Regression to Multi-Class Classification
1. We will use W = w1,…,wK to avoid heavy notation. We have that
N
logP[yˆ = y|X,W] = log YP[yˆn = yn|xn,W]
n=1
Where yˆ are our predictions and y represent the ground truth for our samples. We can rewrite the equation as follow, dividing the samples in groups based on their class.
logP[yˆ = y|X,W] = log Y P[yˆn = 1|xn,W]… Y P[yˆn = K|xn,W]
n:yn=1 n:yn=K
We introduce the following notation to simplify the expression. Let 1yn=k be the indicator function for yn = k, i.e., it is equal to one if yn = k and 0 otherwise. Notice that we can write that
K
P[yˆn = k|xn,W] = YP[yˆn = j|xn,W]1yn=j,
j=1
as P[yˆn = j|xn,W]1yn=j is 1 when j ≠ k (elevating to 0), whereas P[yˆn = k|xn,W] is left unchanged.
K N
logP[yˆ = y|X,W] = log YYP[yˆn = k|xn,W]1yn=k
k=1 n=1
N K
= XX1yn=k logP[yˆn = k|xn,W]
n=1 k=1
N K K
= XX1yn=k wk⊤xn − logXexp(wj⊤xn)
n=1 k=1 j=1
N K N K K
= XX1yn=kwk⊤xn − XX1yn=k logXexp(wj⊤xn)
n=1 k=1 n=1 k=1 j=1
N K N k
= XX1yn=kwk⊤xn − X logXexp(wk⊤xn).
n=1 k=1 n=1 k=1
The last step is obtained by .
2. We get
softmax(n,k)xn.
Where softmax .
3. The negative of the log-likelihood is
N K N K
− XX1yn=kwkxn + X logXexp(wk⊤xn).
n=1 k=1 n=1 k=1
We have already shown that a sum of convex functions is convex, so we only need to show that the following is convex.
K K
−X1yn=kwkxn + logXexp(wk⊤xn).
k=1 k=1
The first part is a linear function, which is convex. We only need to prove that the following is convex.
K logXexp(wk⊤xn) k=1
To prove: We want to show that for all sets of weights A = a1,…,aK,B = b1,…,bK, we have that
.
Simplifying the expression: First, we define uk = ea⊤k x and vk = ebk⊤ x, where uk > 0 and vk > 0. Thus,
,
and we would like to prove
.
From H¨older’s inequality:
,
where .
We can apply this inequality with and to ,i.e.,
,
where the right formula can be reduced to:
.
As a result,
,
which concludes the proof.
3 Mixture of Linear Regression
1. Likelihood: .
2. Joint likelihood: .
3. Write the joint, then the conditional, and plug in.
4.
N K
−logp(y|X,w,π) = −log YXN(yn|w⊤k x˜n,σ2)πk
n=1 k=1
N K
= − X logXN(yn|w⊤k x˜n,σ2)πk n=1 k=1
5. (a) The model is not convex in general. E.g., consider the case when N = 1, K = 2. Then negative
log-likelihood is equal to
The first term is a constant, we will look only at the second term and prove that it is not convex.
Define
In order to prove that f(w1,w2,π1) is not convex we will construct two points and such that .
Let
,
note that x ̸= 0 since its first coordinate is equal to 1 as stated in the exercise. Then
This proves that negative log-likelihood is not convex in general.
(b) The given model is not identifiable by permutation of indexes of mixture components.
Assume that the model is identifiable and true solution is w is found my MLE when the data size grows to infinity, i.e.
w⋆,π⋆ = argmin[L(w,π) := −logp(y|X,w,π)]
w,π
Then we will construct the second point wˆ, such that L(wˆ,πˆ) = L(w⋆,π⋆). This would mean that wˆ,πˆ is also a solution of MLE and there is no way to distinguish between the true solution w⋆,π⋆ and a point wˆ,πˆ, so MLE doesn’t always give a true solution.
We define wˆ,πˆ as follows
wˆ πˆ1 = π⋆2 wˆ πˆ2 = π⋆1
wˆ πˆi = π⋆i ,i ≥ 3,
i.e. vectors corresponding to the first two mixture components are permuted. (We assume that w as they represent two different components). Then indeed the losses at these two points are equal,
N K N K
L(wˆ,πˆ) = − X logXN(yn|wˆ⊤k x˜n,σ2)πˆk = − X logXN(yn|w⋆⊤k x˜n,σ2)π⋆k = L(w⋆,π⋆).
n=1 k=1 n=1 k=1
This ends the proof.
