[SOLVED] CSE176 HomeWork#2

Exercise 1: Euclidean distance classifier (10 points). A Euclidean distance classifier represents each class k = 1,…,K by a prototype vector _µk ∈ R^D and classifies a pattern x ∈ R^D as the class of its closest prototype: k^∗ = argmin_k=1,…,K kx − _µkk. Prove that a Gaussian classifier with shared isotropic covariances (i.e., of the form Σ_k = σ²I for k = 1,…,K, where σ > 0) and equal class priors (i.e., p(C₁) = ··· = p(C_K) = _K¹ ) is equivalent to a Euclidean distance classifier. Prove the class discriminant functions g₁(x),…,g_K(x) are linear and give the expression that defines them.

Exercise 2: bias and variance of an estimator                  Assume we have a sample X =

{x₁,…,x_N} ⊂ R of N iid (independent identically distributed) scalar random variables, each of which is drawn from a Gaussian distribution N(µ,σ²) with µ ∈ R and σ > 0. We want to estimate the mean µ of this Gaussian by computing a statistic of the sample X. Consider the following four different statistics of the sample:

1. φ₁(X) = 7.
2. φ₂(X) = x₁.
3. φ3(X) = N1 PNn=1 xn.
4. φ₄(X) = x₁x₂.

For each statistic φ, compute:

•  Its bias b_µ(φ) = E_X {φ(X)} − µ.
•  Its variance var {φ} = E_X {(φ(X) − E_X {φ(X)})²}.
•  Its mean square error e(φ,µ) = E_X {(φ(X) − µ)²}.

Based on that, answer the following for each estimator (statistic): is it unbiased? is it consistent? Hint: expectations wrt the distribution of the N-point sample X are like this one:

E_X {φ(X)} = Z φ(x₁,…,x_N)p(x₁,…,x_N)dx₁ …dx_N ^iid= Z φ(x₁,…,x_N)p(x₁)…p(x_N)dx₁ …dx_N.

Exercise 3: PCA and LDA  Consider 2D data points coming from a mixture of two Gaussians with equal proportions, different means, and equal, diagonal covariances (where µ,σ₁,σ₂ > 0):

x ∈ R²: p(x) = π₁ p(x|1) + π₂ p(x|2)            p(x|1) ∼ N(_µ1,Σ₁),         p(x|2) ∼ N(_µ2,Σ₂),

, µ.

1.  Compute the mean _µ and covariance Σ of the mixture distribution p(x).

Hint: let ) for x ∈ R^D be a mixture of K densities, where π₁,…,π_K ∈ [0,1] and = 1 are the component proportions (prior probabilities) and p(x|k), for k = 1,…,K, the component densities (e.g. Gaussian, but not necessarily). Let _µ be the mean and covariance of component density k, for k = 1,…,K.

Then, the mean and covariance of the mixture are (you should be able to prove this statement):

µ.

2.  Compute the eigenvalues λ₁ ≥ λ₂ ≥ 0 and corresponding eigenvectors u₁,u₂ ∈ R² of Σ. Can we have λ₂ > 0?
3.  Find the PCA projection to dimension 1.
4. Compute the within-class and between-class scatter matrices S_W , S_B of p.
5.  Compute the eigenvalues ν₁ ≥ ν₂ ≥ 0 and corresponding eigenvectors v₁,v₂ ∈ R² of S⁻_W¹S_B. Can we have ν₂ > 0?
6.  Compute the LDA projection.
7.  When does PCA find the same projection as LDA? Give a condition and explain it.

Exercise 4: variations of k-means clustering ).         Consider the k-means error function:

N          K

E({_µk}^K_k=1,Z) = XXz_nkkx_n − _µkk²                          s.t.        Z ∈ {0,1}^NK, Z1 = 1

n=1 k=1

over the centroids _µ1,…,_µK and cluster assignments Z_N×K, given training points x₁,…,x_N ∈ R^D.

• Variation 1: in k-means, the centroids can take any value in R^D: _µk ∈ R^D ∀k = 1,…,K. Now we want the centroids to take values from among the training points only: _µk ∈ {x₁,…,x_N} ∀k = 1,…,K.
  1. (8 points) Design a clustering algorithm that minimizes the k-means error function but respecting the above constraint. Your algorithm should converge to a local optimum of the error function. Give the steps of the algorithm explicitly.
  2. (2 points) Can you imagine when this algorithm would be useful, or preferable to k-means?
• Variation 2: in k-means, we seek K clusters, each characterized y by a centroid _µk. Imagine we seek instead K lines (or hyperplanes, in general), each characterized by a weight vector w_k ∈ R^D and bias w_k0 ∈ R, given a supervised dataset (see figure). Data points assigned to line k should have minimum least-squares error Pn∈line k (yn − wkT xn − wk0)2. x
  1. (8 points) Give an error function that allows us to learn the lines’ parameters.
  2. (12 points) Give an iterative algorithm that minimizes that error function.

Exercise 5: mean-shift algorithm (10 points).         Consider a Gaussian kernel density estimate

         x ∈ RD.

Derive the mean-shift algorithm, which iterates the following expression:

x       where

until convergence to a maximum of p (or, in general, a stationary point of p, satisfying ∇p(x) = 0). Hint: take the gradient of p wrt x, equate it to zero and rearrange the resulting expression.

Bonus exercise: nonparametric regression (20 points).       Consider the Gaussian kernel smoother

g   where

estimated on a training set .

1. (7 points) What is g(x) if the training set has only one point (N = 1)? Explain.

Sketch the solution in 1D (i.e., when both x_n,y_n ∈ R). Compare with using a least-squares linear regression.

2. (13 points) Prove that, with N = 2 points, we can write g(x) = α(x)y₁ + (1 − α(x))y₂ where α(x) can be written using the logistic function. Give the detailed expression for α(x).

Sketch the solution in 1D.

Compare with using a least-squares linear regression.