[SOLVED] CS433 Exercise 6- 1 Convexity

Recall that we say that a function f is convex if the domain of f is a convex set and

f(θx + (1 − θ)y) ≤ θf(x) + (1 − θ)f(y), for all x,y in the domain of f, 0 ≤ θ ≤ 1.

And strictly convex if

f(θx + (1 − θ)y) < θf(x) + (1 − θ)f(y), for all x =6 y in the domain of f, 0 < θ < 1.

Prove the following assertions.

1. The affine function f(x) = ax + b is convex, where a,b and x are scalars.
2. If multiple functions f_n(x) are convex over a fixed domain, then their sum g(x) = ^P_n f_n(x) is convex over the same domain.
3. Take f,g : R → R to be convex functions and g to be increasing. Then g ◦ f is also convex.

Note: A function g is increasing if a ≥ b ⇔ g(a) ≥ g(b). An example of a convex and increasing function is exp(x),x ∈ R.

4. If f : R → R is convex, then g : R^D → R, where g(x) := f(w^>x + b), is also convex. Here, w is a constant vector in R^D, b is a constant in R and x ∈ R^D.
5. Let f : R^D → R be strictly convex. Let x^? ∈ R^D be a global minimizer of f. Show that this global minimizer is unique. Hint: Do a proof by contradiction.

1           Extension of Logistic Regression to Multi-Class Classification

Suppose we have a classification dataset with N data example pairs {x_n,y_n}, n ∈ [1,N], and y_n is a categorical variable over K categories, y_n ∈ {1,2,…,K}. We wish to fit a linear model in a similar spirit to logistic regression, and we will use the softmax function to link the linear inputs to the categorical output, instead of the logistic function.

We will have K sets of parameters w_k, and define  and compute the probability distribution of the output as follows,

.

Note that we indeed have a probability distribution, as. To make the model identifiable, we will fix w_K to 0, which means we have K−1 sets of parameters to learn. As in logistic regression, we will assume that each y_n is i.i.d., i.e.,

.

1. Derive the log-likelihood for this model.
2. Derive the gradient with respect to each w_k.
3. Show that the negative of the log-likelihood is convex with respect to w_k.

2           Mixture of Linear Regression

In Project-I, you worked on a regression dataset with two or more distinct clusters. For such datasets, a mixture of linear regression models is preferred over just one linear regression model.

Consider a regression dataset with N pairs {y_n,x_n}. Similar to Gaussian mixture model (GMM), let r_n ∈ {1,2,…,K} index the mixture component. Distribution of the output y_n under the k^th linear model is defined as follows:

Here, w_k is the regression parameter vector for the k^th model with w being a vector containing all w_k. Also, x˜.

1. Define r_n to be a binary vector of length K such that all the entries are 0 except a k^th entry, i.e., r_nk = 1, implying that x_n is assigned to the k^th Rewrite the likelihood p(y_n|x_n,w,r_n) in terms of r_nk.
2. Write the expression for the joint distribution p(y|X,w,r) where r is the set of all r₁,r₂,…,r_N.
3. Assume that r_n follows a multinomial distribution p(r_n = k|π) = π_k, with π = [π₁,π₂,…,π_K]. Derive the marginal distribution p(y_n|x_n,w,π) obtained after marginalizing r_n
4. Write the expression for the maximum likelihood estimator L(w,π) := −logp(y|X,w,π) in terms of data y and X, and parameters w and π.
5. Is L jointly-convex with respect to w and π? Is the model identifiable? Prove your answers.

2