ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML 1. Principal Component Analysis – Consider a dataset that consists of data points {xi}5i=1 where xi 2 R2. We can represent this dataset using a matrix X 2 R5 2 where each row corresponds to a data point. X = 266664 1 2 0 0 1 2 2 4 2 4 377775 (a) Standardise this dataset to form a matrix Xs 2 R5 2 where each column has zero mean and unit variance. (b) Compute the principal components of Xs. These should have unit norm. (c) Use the first principal component to transform your standardised dataset down to 1 dimension. (d) Reconstruct your standardised dataset using the transpose of the first principal component. Compute the reconstruction error. Solution: (a) First, compute the means and standard deviations of each column. Both columns are zero mean, and the variances are 21 = (1 2 + 02 + (1)2 + (2)2 + (2)2)/5 = 2 22 = (2 2 + 02 + (2)2 + (4)2 + (4)2)/5 = 8 This means the standard deviations are 1 = p 2 and 2 = 2 p 2. We divide the values in each column by the column standard deviation (we don’t have to worry about dividing by zero here) to get our standardised data matrix: X = 1p 2 266664 1 1 0 0 1 1 2 2 2 2 377775 Notice that both columns are the same so we have a redundancy. (b) First, form the covariance matrix C = 1DX TX: Page 1 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML C = 1 4 1 0 1 2 2 1 0 1 2 2 266664 1 1 0 0 1 1 2 2 2 2 377775 = 5 2 5 2 5 2 5 2 Now we need to compute the eigenvalues 1,2 and eigenvectors w1, w2 of C. Recall that an eigenvalue/vector pair ,w satisfies w = Cw. This means we can write det(C I) = 0. 52 525 2 5 2 = 0 ( 5 2 )2 25 4 = 0 25 4 5+ 2 25 4 = 0 2 5 = 0 ( 5) = 0 This gives 1 = 5 and 2 = 0. Remember that we sort these by decreasing magnitude. We can now insert 1 into the equation 1w1 = Cw1 to compute the eigenvector w1: 5 w1,1 w1,2 = 5 2 1 1 1 1 w1,1 w1,2 This gives us 2w1,1 = w1,1 + w1,2 2w1,2 = w1,1 + w1,2 which is satisfied when w1,1 = w1,2 The scaling of eigenvectors is arbitrary, so we could have w1,1 = w1,2 = 1. However, this vector would have a norm of p 2 and we have been asked for unit-norm eigenvectors, so we must have: w1 = 1p 2 1 1 Page 2 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML This is the first principal component. We can now insert 2 into the equation 2w2 = Cw2 to compute the eigenvector w2. 0 w2,1 w2,2 = 5 2 1 1 1 1 w2,1 w2,2 This gives us 0 = w2,1 + w2,2 0 = w2,1 + w2,2 which is satisfied when w2,1 = w2,2. This gives us the 2nd principal component as w2 = 1p 2 1 1 (c) To project our data down to 1D, we can compute XD = Xw1 where X is our standardised data matrix. XD = 1 2 266664 1 1 0 0 1 1 2 2 2 2 377775 1 1 = 266664 1 0 1 2 2 377775 (d) We can reconstruct our data using X = XDwT1 X = 1p 2 266664 1 0 1 2 2 377775 1 1 = X. This perfectly reconstructs our data, so the reconstruction error is zero. 2. Dataset splits – Before learning a classifier, we first split our dataset into a training, validation, and test set. (a) Describe the purpose of each these sets. Page 3 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML (b) Explain what is meant by generalisation and overfitting in machine learning. Relate these to the dataset splits. Solution: (a) A training set is used to train our classifier. Non-parametric classifiers such as K-NN use this training set directly to classify new points. In parametric classifiers, the training data is used to learn its parameters and can be dis- carded afterwards. Validation sets are used to tune the hyper-parameters of a classifier. In K-NN we can tune K to this validation set. When we employ gradient descent, the learning rate is a hyper-parameter. We can tune this by e.g. training lots of di erent classifiers with di erent learning rates, and pick the one that does best on the validation set. The test set is used to evaluate the performance of a (tuned) classifier. (b) Generalisation is when a classifier trained on some data is able to successfully classify new, unseen data. We use a train/test split to capture how well a classifier generalises. Overfitting occurs if a classifier is very good at classifying the data it was trained on, but fails to generalise to new data. 3. K-Nearest Neighbours in 2D – We are given a training set of data points {xi}10i=1 where xi 2 R2. Each point has an associated class label yi 2 {0, 1}. These are depicted below, where dim1 and dim2 are the first and second element of each datum. (a) Use a K-NN classifier with K = 1 to classify a test point at 2 2 Page 4 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML (b) Use a K-NN classifier with K = 3 to classify a test point at 0 2 (c) Use a K-NN classifier with K = 5 to classify a test point at 2 0 (d) Use a K-NN classifier with K = 7 to classify a test point at 4 4 Solution: While it is possible to solve this problem by computing distances explicitly, the 2D plot let’s us perform K-NN visually in most cases. (a) K = 1 means we are only interested in the nearest point to 2,2 . This is the blue point in the lower-right corner, so this test point will be classified as class 1. (b) We have K = 3. The nearest three points are the blue to the left, and the red+blue to the right. We have more blues than reds, so our test point is classified as class 1. (c) We have K = 5. The four nearest points are the two blue above, and the two red below. The next nearest point is red, which breaks the tie, so our test point is classified as class 0. (d) We have K = 7 and our test point is in the lower right corner. The four nearest points are clearly two red and two blue, so we are interested in the three nearest points after those. It’s harder to determine the next few by eye, so we can compute some distances. The red point at (-2,-2) is p 40 away. The red point at (-3,-1) is p 58. The red point at (1,2) is p 45 and the blue point at (1,3) is p 58. The remaining two blue points are further. This gives us the 6 nearest points as 4 red and 2 blues. The 7th nearest point is tied, but red already has a majority, so our point is classified as class 0. 4. K-Nearest Neighbours in higher dimensions – We are given a training set of data points {xi}3i=1 where xi 2 R5. Each point has an associated class la
bel yi 2 {1,1}. x1 = 1 2 2 2 0 y1 = 1 x2 = 1 1 0 1 1 y2 = 1 x3 = 2 4 2 1 0 y3 = 1 (a) Use a K-NN classifier with K = 1 to classify a test point at 0 1 0 1 2 (b) Give an example of something that we could represent with a 5D data point. Page 5 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML Solution: (a) We can’t visualise these, but we can compute distances between the test points and each of the training points. We will compute square distances, as these are proportional to distances. ||x1 xt||22 = ((1 0)2 + (2 1)2 + (2 0)2 + (21)2 + (0 2)2) = 11 ||x2 xt||22 = ((1 0)2 + (1 1)2 + (0 0)2 + (11)2 + (1 2)2) = 10 ||x3 xt||22 = ((2 0)2 + (4 1)2 + (2 0)2 + (11)2 + (0 2)2) = 41 We have K = 1 and the nearest point belongs to class 1, so we classify our test point as class 1. (b) There are many answers to this, but you could for instance have the 4D iris dataset but with an additional measurement of e.g. stem length to make it 5D. 5. Linear Classification — Consider a training set of data points {xi}4i=1 where xi 2 R1, in which each datum has an associated class label yi 2 {0, 1}. x1 = 1 y1 = 0 x2 = 2 y2 = 0 x3 = 2 y3 = 1 x4 = 1 y4 = 1 Now consider a linear classifier zi = wxi+b where w and b are a learnable weight, and bias parameter respectively. We will use our classifier to classify points as belonging to class 1 if zi > 0.5, and as belonging to class 0 if zi < 0.5. To learn our parameters we can minimise the mean squared error loss (MSE) across our training data: L = 1 4 4X i=1 (zi yi)2 (a) Plot the training data. Annotate this plot with the classifier’s decision boundary for initial parameters w = 1 and b = 1. Page 6 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML (b) Determine which side of the decision boundary is allocated to which class, thence classify a test point at xt = 0.6. (c) Derive an expression for @L@w and @L @b and explain how these may be used in gradient descent to update the classifier’s parameters. (d) Perform a single iteration of gradient descent to update w and b. Use a learning rate = 0.1. (e) Determine where the decision boundary is after this update, and reclassify the test point at xt = 0.6. Solution: (a) In 1D, the decision boundary is a point, rather than a line. We can locate this point by considering the case where our classifier outputs 0.5. Points either side of this are classified di erently. We have zi = wxi + b, with w = 1 and b = 1. Let’s plug these values in, and consider a classifier output of 0.5. 0.5 = xd + 1. This gives us the point xd = 0.5. (b) Let’s see what happens to a point a small distance to the right of this. z = (0.5 + ) + 1 = 0.5 + > 0.5 So points to the right of the decision boundary will be put into class 1. xt = 0.6 is to the left of the decision boundary so will be classified as class 0. Page 7 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML (c) We have L = 1 N NX i=1 (zi yi)2 = 1 N NX i=1 (wxi + b yi)2 where N = 4. We can take the partial derivative of this wrt. w and wrt. b @L @w = 2 N NX i=1 xi(wxi + b yi) @L @b = 2 N NX i=1 (wxi + b yi) These quantities can be used in gradient descent to iterative update our w and b values across time steps: wt+1 = wt @L @wt bt+1 = bt @L @bt (d) Let’s start by computing these gradients for our current parameter values. @L @wt = 1 2 (2(1 0) +1(0 0) + 2(3 1) + 1(2 1)) = 3.5 @L @bt = 1 2 ((1 0) + (0 0) + (2 1) + (3 1)) = 1 We can now use these for an update wt+1 = wt @L @wt = 1 (0.1)(3.5) = 0.65 bt+1 = bt @L @bt = 1 (0.1)(1) = 0.9 Page 8 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML (e) We have zi = wxi + b, with w = 0.65 and b = 0.9. The boundary is when the classifier outputs 0.5. 0.5 = 0.65xd + 0.9 The boundary is at xd = 0.615. We can again see that points to the right of this will be classified as class 1. Our test point is now to the right of this, so will be classified as class 1 using our updated classifier. 6. Logistic Classification — We have a training set of 1D data points {xi}Ni=1 each with an associated class label yi. This label is 1 if xi belongs to class 1, and is 0 if xi belongs to class 0. Now consider a logistic classifier with a weight w and bias b that takes in a training point xi. It outputs zi, which is the probability that xi belongs to class 1 (yi = 1): zi = P(yi = 1|xi) = (wxi + b) where (wxi + b) = 1 1 + e(wxi+b) To learn our parameters w and b we can minimise the cross entropy loss averaged across data points: L = 1 N NX i=1 yi log zi (1 yi) log(1 zi) through e.g. gradient descent. (a) Show that d(a)da = (a)(1 (a)) for some variable a (b) Thence, show that @L@w = 1 N PN i=1 xi(zi yi) and @L@b = 1N PN i=1(zi yi) Solution: (a) We have (a) = 1 1 + ea = (1 + ea)1 We can di erentiate this using the chain rule: Page 9 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML d(a) da = (1)(ea)(1 + ea)2 = e a (1 + ea)2 We can now write d(a) da = ea (1 + ea)2 = 1 1 + ea ea 1 + ea = (a) ea 1 + ea Lastly we add and subtract 1 from the numerator on the RHS: d(a) da = (a) ea + 1 1 1 + ea = (a)( 1 + ea 1 + ea 1 1 + ea ) = (a)(1 (a)) (b) This is an exercise in the chain rule. We have L = 1 N NX i=1 yi log zi (1 yi) log(1 zi) But zi = (wxi + b) so let’s plug this in: L = 1 N NX i=1 yi log((wxi + b)) (1 yi) log(1 (wxi + b)) Now we can take the derivative wrt. w. Remember that di erentiation and summation are both linear, so the derivative of the sum is just the sum of the individual derivatives. This means we can pull out the sum and basically ignore it. @L @w = 1 N NX i=1 yixi (wxi + b) @(wxi + b) @(wxi + b) (1 yi)(xi) 1 (wxi + b) @(wxi + b) @(wxi + b) In the first part, we computed the derivative of a sigmoid so we can plug that in. Recall that zi = (wxi + b) so we will make this substitution as well. @L @w = 1 N NX i=1 yixizi(1 zi) zi + (1 yi)xizi(1 zi) 1 zi Lastly, we can cancel the denominators out, and simplify to get the desired expression. Page 10 of 11 Continued ELEE08021 Sensor Networks and Data Analysis 2 Exercise ML @L @w = 1 N NX i=1 yixi(1 zi) + (1 yi)xizi @L @w = 1 N NX i=1 xi(zi yi) For the derivative wrt. b things play out very similarly except di erentiating the expression inside the sigmoid yields 1 instead of xi. This yields @L @b = 1 N NX i=1 (zi yi) Page 11 of 11 END