Description

Centre of Excellence in Artificial Intelligence
ANSWER ALL THE QUESTIONS
1. Let Pn(R) denote the set of all polynomials in indeterminate x with real coefficients.
(a) Prove that Pn(R) is a real vector space.
(b) Define a function F : Pn(R) → R as

In other words, the function assigns every polynomial with the value of its derivative at x = 0. Prove that this is a linear functional.
(c) Find an inner product representation for the linear functional in the above question.
2. Let x ∈ Rn and 1n be the n-vector with all entries 1. Let avg(x) and std(x) be as defined in the class. Then for any α,β ∈ R prove the following.
(a) avg(αx + β1n) = αavg(x) + β
(b) std(αx + β1n) = |α|std(x)
3. Let w ∈ Rn be a given vector with wi > 0 for i = 1,2,…,n. Then for any x ∈ Rn, define the function

v n
kxkw = uutXwix2i
i=1
Show that the function k · kw defines a norm called as weighted norm.
4. Consider k-means clustering algorithm as follows with the standard terminology and notation introduced in the class as follows.
Input: x1,x2,…,xN ∈ Rn. Initial list of k cluster representatives z1,…,zk.

Output: Cluster assignment c1,c2,…,cN

Repeat until convergence
1. Cluster assignment based on cluster representatives.
2. Update cluster representatives.
(a) In Step 1, what is the computational complexity?(b) In Step 2, what is the computational complexity?
(c) Assuming 10 iterations are performed, how many number of computations are involved to obtain the cluster assignment for the given data points?
1/2
5. Image Clustering: Consider the MNIST database of handwritten digits. Choose 100 images of each digit from this data set. In the notation of Problem 4, determine values N and n. Fix a reasonable convergence criterion. Perform the following exercises (a),(b) and (c) in two cases: case (i) random initialization of cluster representatives; case(ii) choose cluster representatives from the given data set.
(a) For k = 20, run the above algorithm to cluster the given images into 20 clusters. Plot the cluster representatives after the algorithm converges. Count the number of iterations.
(b) Choose 50 images (not chosen previously) from the MNIST data set randomly and assign the clusters to these test images. What is the accuracy of cluster assignment?
Does the choice of initial condition have any effect on the performance of k-means clustering algorithm?
****************** THE END ******************
2/2