Computer Engineering - Machine Learning

Full exam

DIPARTIMENTO DI ELETTRONICA, INFORMAZIONE E BIOINGEGNERIA Politecnico di Milano Machine Learning (Code: 097683)September 10, 2024 Surname: Name: Student ID: Row: Column:Time:2hoursMaximumMarks:33 •The following exam is composed of8 exercises(one per page). The first page needs to be filled with yourname, surname and student ID. The following pages should be used only in the large squarespresent on each page. Any solution provided either outside these spaces orwithout a motivationwill not be considered for the final mark. •During this exam you arenot allowed to use electronic devices, such as laptops, smartphones, tablets and/or similar. As well, you are not allowed to bring with you any kind of note, book, written scheme, and/or similar. You are also not allowed to communicate with other students during the exam. •The first reported violation of the above-mentioned rules will be annotated on the exam and will be considered for the final mark decision. The second reported violation of the above-mentioned rules will imply the immediate expulsion of the student from the exam room and theannulment of the exam. •You are allowed to write the exam either with a pen (black or blue) or a pencil. It is your responsibility to provide a readable solution. We will not be held accountable for accidental partial or total cancellation of the exam. •The exam can be written either inEnglishorItalian. •You are allowed to withdraw from the exam at any time without any penalty. You are allowed to leave the room not early than half the time of the duration of the exam. You are not allowed to keep the text of the exam with you while leaving the room. •Three of the points will be given on the basis on how quick you are in solving the exam.If you finish earlier than 30 min before the end of the exam you will get 3 points, if you finish earlier than 20 min you will get 2 points and if you finish earlier than 10 min you will get 1 point (the points cannot be accumulated). •The box on Page 10 can only be used to complete the Exercises 7, and/or 8.Ex. 1Ex. 2Ex. 3Ex. 4Ex. 5Ex. 6Ex. 7Ex. 8TimeTot. / 7/ 7/ 2/ 2/ 2/ 2/ 4/ 4/ 3/ 33 Student’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 2 of 10 Exercise 1 (7marks) Describe the processes of training, validation, and testing in supervised learning. Explain how to manage the dataset and what common mistakes should be avoided.Student’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 3 of 10 Exercise 2 (7marks) Compare the advantages and disadvantages of Monte Carlo methods and Temporal Difference methods in the context of model-free prediction problems.Student’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 4 of 10 Exercise 3 (2marks) Consider the following snippet of code:1 w = n p . o n e s ( X . s h a p e [ 1 ] + 1 ) # X . s h a p e [ 1 ] i s t h e n u m b e r o f f e a t u r e s2 e r r o r s = T r u e3 w h i l e e r r o r s :4 e r r o r s = F a l s e5 f o r i , ( x _ i , t _ i ) i n e n u m e r a t e ( z i p ( X , t ) ) :6 c o r r _ t _ i = 1 i f t _ i e l s e - 17 e x t _ x = n p . c o n c a t e n a t e ( [ n p . o n e s ( 1 ) , x _ i . f l a t t e n ( ) ] )8 i f n p . s i g n ( w . d o t ( e x t _ x ) ) ! = c o r r _ t _ i :9 e r r o r s = T r u e10 w = w + e x t _ x * c o r r _ t _ i 1.What kind of machine learning problem is this code trying to solve? What method is beingused? 2.Are there any issues with the solution implemented here? If so, propose a fix. 3.When is the procedure guaranteed to terminate for a generic training dataset (X,t)? 1.The code is trying to solve a binary classification problem using the perceptron. 2.The update at line 10 should be performed for the samples that are misclassified only. Wecan fix this issue by moving line 10 inside the if statement. 3.The procedure is guaranteed to terminate when the dataset (X,t) is linearly separable.Student’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 5 of 10 Exercise 4 (2marks) Tell if the following statements on the bias-variance tradeoff in regression are true or false. Motivate your answers. 1.With the same amount of data, simplifying the model reduces the bias at the cost of morevariance 2.Adding more data reduces variance and bias 3.A smaller hypothesis space can have the same bias as a larger one 4.Adding more data reduces the mean-squared error 1.FALSE, it reduces the variance and increases the bias 2.FALSE, it only reduces the variance, bias is unaffected 3.TRUE, for example if the smaller space has zero bias and is contained in the larger one 4.TRUE, since it reduces the variance and MSE is the sum of variance, squared bias andirreducible errorStudent’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 6 of 10 Exercise 5 (2marks) Tell if the following statements are true or false. Motivate your answers. 1.A multi-armed bandit problem is a Markov decision process with no transition model. 2.Theϵ-greedy policy with a fixed value ofϵprovides sub-linear cumulative regret in any multi-armed bandit problem. 3.The Thompson sampling algorithm makes use of Bayesian updates. 4.The UCB1 algorithm can be applied only if the rewards are Bernoulli random variables.1.FALSE: The multi-armed bandit problem is a Markov decision process with a single states and a self-loop as transition modelP(s|s, a) = 1. 2.FALSE: Theϵ-greedy policy may suffer from linear regret in some bandit instances. For sure, ifϵis not set as a function of the learning horizonT, we have that in any bandit theϵ-greedy policy will sufferϵT∆ cumulative regret, where ∆ =µ i∗ −max i̸ =i∗ µ i. 3.TRUE: The Thompson sampling algorithm uses Bayesian prior-posterior updates. Forinstance, Beta-Bernoulli. 4.FALSE: The UCB1 algorithm can be applied even to non-Bernoulli random variables,provided that a suitable concentration inequality is available for building the upper confidence bound. For instance, for any bounded random variable, we can use the Hoeffding’s inequality.Student’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 7 of 10 Exercise 6 (2marks) You work as a data scientist for a chocolate factory and you want to predict the quality, in terms oftaste, of chocolate bars based on some measurements that do not require human evaluation (like color, density, reflectance...). These predictions should happen at a very fast rate, and the company has limited computational power, but you have plenty of data labeled by professional chocolate tasters. For each of the following scenarios, tell how you would model this task as a machine learning problem and what solution you would propose. 1.The company standards define taste as a percentage, where 0% means disgusting and 100%means delicious. 2.The company standards define taste as ”disgusting”, ”unpleasant”, ”bland”, ”pleasant”, or”delicious”. 1.This is a regression problem, where the target (taste) is a real number (between zero andone) and the input variables are the measurements. Since the prediction of test data must be fast, with limited computational power but many training data, a parametric method is recommended, for example linear regression. It is also acceptable to interpret the target as a probability of being delicious and use logistic regression. 2.This instead is a multi-class classification problem. For the same computational reasons asbefore, a parametric method like logistic regression with cross-entropy loss should be used.Student’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 8 of 10 Exercise 7 (4marks) Consider the tra jectory below obtained in an MDP with three statesS={x, y, z}, two actions A={a, b}, and discount factorγ= 1. (x, a,4)→(y, b,3)→(x, b,−1)→(z, a,1)→(y) 1.Starting from zero initialization and using learning rateα= 1, compute the Q-function obtained by applying Q-learning to this tra jectory. 2.Starting from zero initialization and using learning rateα= 1, compute the Q-function obtained by applying SARSA to this tra jectory. 3.What is the policy that SARSA will play in the next tra jectory? What about Q-learning? Motivate all answers and report all necessary computations.1.Q-learning update rule: Q(s t, a t) ←Q(s t, a t) + α rt+ γmax a′ ∈AQ (s t+1, a′ )−Q(s t, a t) •Transition 1: (x, a,4)→(y):Q(x, a) = 0 + 1·(4 + 1·0−0) = 4 •Transition 2: (y, b,3)→(x):Q(y, b) = 0 + 1·(3 + 1·max(4,0)−0) = 7 •Transition 3: (x, b,−1)→(z):Q(x, b) = 0 + 1·(−1 + 1·0−0) =−1 •Transition 4: (z, a,1)→(y):Q(z, a) = 0 + 1·(1 + 1·max(7,0)−0) = 8 Thus, the final Q-values are:Q(x, a) = 4, Q(x, b) =−1, Q(y, b) = 7, Q(z, a) = 8 and all other Q-values remain at 0. 2.SARSA update rule: Q(s t, a t) ←Q(s t, a t) + α[r t+ γ Q(s t+1, a t+1) −Q(s t, a t)] •Transition 1: (x, a,4)→(y, b):Q(x, a) = 0 + 1·(4 + 1·0−0) = 4 •Transition 2: (y, b,3)→(x, b):Q(y, b) = 0 + 1·(3 + 1·0−0) = 3 •Transition 3: (x, b,−1)→(z, a):Q(x, b) = 0 + 1·(−1 + 1·0−0) =−1 •Transition 4: (z, a,1)→(y):Q(z, a) = 0 + 1·(1 + 1·0−0) = 1 Thus, the final Q-values are:Q(x, a) = 4, Q(x, b) =−1, Q(y, b) = 3, Q(z, a) = 1 and all other Q-values remain at 0. 3.SARSA will play anϵ-greedy policy defined in terms of the estimated Q-function: π(a|x) = 1−ϵ, π(b|x) =ϵ, π(a|y) =ϵ, π(b|y) = 1−ϵ, π(a|z) = 1−ϵ, π(b|z) =ϵ. We do not know which policy will Q-learning play, but, for sure, it will be a policy that plays with non-zero probability all the actions (if we want the algorithm to converge toQ∗ ).Student’s name: Please go on to the next page. . . Computer Science Computer Science — Machine Learning Page 9 of 10 Exercise 8 (4marks) An annulus is the region between two concentric circles. A spherical shell is the region between two concentric spheres. 1.Show that the VC dimension of an origin-centered annulus inR2 is 2. 2.What is the VC dimension of an origin-centered spherical shell inR3 ? Justify your answer. 1.V C≥2: it is easy to see that any two points at different distances from the origin can be correctly classified by an annulus whatever their labeling: an annulus either including only the closest point, only the farthest point, both, or neither. V C