Page 4 EC$708P/U/D (2015) (2015) Question 3: K-Means (a) Describe the difference between supervised and unsupervised learning. Give an example of a supervised learning problem and an example of an unsupervised learning problem. [4 marks] (b) Describe in detail the steps of the K-means algorithm. Make sure that you define the input to the algorithm, the output, and the dimensionality of all the variables that you use. [8 marks] (c) Give the formula that defines the quantity that is optimised by the K-means algorithm. [4 marks] (d) What is the optimisation method used by K-means? Using a sketch show that this general method is warranted to converge. Show that it might converge to a local minimum. [4 marks] (e) The K-Means algorithm terminates at local minimum. Describe a practical way to deal with this problem. [5 marks] [Total 25 Marks] ECS708P/U/D (2015) Page 5 Question 4: Markov Models (a) With a help of a diagram explain the main principles of the first-order Markov Model. Explain what is meant by the term "first-order". What are the differences with a hidden Markov model (HMM)? In your answer, define the states 0,, the symbols y, and the matrices A = [4] and B =[hy]. [6 marks) (b) The decoding problem can be stated as follows: Given an HMM and a sequence of observation symbols V determine the most likely sequence of hidden states o" What are the other two types of problems considered in the context of HMMs? [6 marks] (c) What is the name of the algorithm that is used to solve the decoding problem described in 4.b). Give a brief description of the algorithm using pseudo code. [13 marks] End of Paper