FIT3080 Artificial Intelligence Assignment 2 2nd Semester 2022

This assignment is worth 24% of your final mark (subject to the hurdles described in the FIT3080 Unit Guide, Moodle preview and other locations). Among other things (see below), note the need to hit the `Submit button. Due Date: Wednesday 19th October 2022, 11:55pm (Melbourne, Australia time) Method of submission: Your submission should consist of at least 1 and at most 7 files: 1. A text-based .pdf file named:FamilyName-StudentId-2ndSem2022FIT3080_A2.pdf 2. A .dne Netical file named as: FamilyName-StudentId-2ndSem2022FIT3080_A2_Qu3a.dne 3. A .dne Netical file named as: FamilyName-StudentId-2ndSem2022FIT3080_A2_Qu3b.dne 4. A .dne Netical file named as: FamilyName-StudentId-2ndSem2022FIT3080_A2_Qu3d.dne (The Netica .dne files are only for Question 3. Question 3 would be answered both in the .pdf and in .dne files. The requested screenshots should be included in the .pdf file) 5. A .py Python file named as: FamilyName-StudentId-2ndSem2022FIT3080_A2_Qu4.py 6. A .py Python file named as: FamilyName-StudentId-2ndSem2022FIT3080_A2_Qu6.py (The Python .py files are only for Question 4 and Question 6. Question 4 and Question 6 would be answered both in the .pdf and in .py files.) 7. A .xls (or .xlsx) file named as: FamilyName-StudentId-2ndSem2022FIT3080_A2_Qu5.xls (or .xlsx) If you attempted Question 3, then submit 4 files ( one .pdf and three .dne). In that case, your answer to Question 3 should appear in both files. The requested screenshots should be included in the .pdf file. If you attempted Question 4, then submit both files (.pdf and .py). In that case, your answer to Question 4 should appear in both files. If you attempted Question 5, then submit both files (.pdf and .xls or .xlsx). In that case, your answer to Question 5 should appear in both files. If you attempted Question 6, then submit both files (.pdf and .py). In that case, your answer to Question 6 should appear in both files. If you did not attempt any of Question 4 and Question 5 and Question 6 (and attempted nothing other than Questions 1, 2, 3), then you can just submit the .pdf file. Total available marks: 16 + 16 + 27 + 15 + 15 + 16 = 105 marks, to a maximum of 100 marks. Anyone achieving 100 or more marks will be given 100 marks. All the files must be uploaded on the FIT3080 Moodle site by the due date and time. At the time you submit these files to Moodle, the text-based .pdf will undergo a similarity check by Turnitin. This is done at the time you upload your assignment to Moodle. It is also our intention to perform such a check on the other files at the same time if you submit it. The details of the submission instructions are possibly subject to change. In the event of any change, students will be notified. Read all of the instructions carefully, including the notes on the last page. ---- Question 1 [Markov Decision Process]: Modified Vacuum Cleaner World - (5 + 5 + (2+2+2) = 5 + 5 + 6 = 16 marks) Make sure to show your working and explain your answer to all parts of this question. Recall the modified vacuum cleaner world example discussed in lab 6. For this assignment, it is changed as follows: After any action, exactly one of the two blocks becomes randomly dirty - with probabilities and for the left block () and the right block (), respectively. (Notethat + = 1.) There are two actions: 1. stay in the current block and vacuum (abbreviated by S&V), 2. move to the other block and vacuum (abbreviated by M&V), Using these two actions, the vacuum cleaner should clean the dirt and receive a reward. The reward for staying in the same block and vacuuming, S&V, (if dirty) is 1.5 times more than moving to the other block and vacuum, M&V, (if dirty). If the block where the vacuum cleaner moves is not dirty, you will receive a zero reward and the game ends. The goal is to maximise the cumulative sum of discounted rewards. (Part a) Assuming the probabilities and and the rewards for M&V, 0 are given, formulate this modified vacuum cleaner world as a Markov Decision Process (an MDP), writing down the reward function (, , ') and the transition function (, , ') as tables. (5 marks) (Part b) Assume that the vacuum cleaner always starts from the right block, . Moreover, if at the beginning, the vacuum cleaner takes the M&V action, then assume that it receives a non-zero reward equal to 4 2or 2max( , ) (both are the same values). Based on the above, calculate the exact values for , , and the Transition and Reward matrices. (5 marks) Note: You can use a calculator and round the numbers to 3 decimal places, e.g., 2.4557 can be displayed as 2.456. (Part c) Considering 0 () = () = 0, and assuming that the discount factor for the Bellman equation is equal to = 0. 9, and starting from , (i) calculate the value iterations over the four iterations. (2 marks) (ii) Also, find the best policy after these four iterations. (2 marks) (iii) Can we assume that we achieve the optimal policy after 4 iterations? Please explain your answer. (2 marks) Note: You can use a calculator and round the numbers to 3 decimal places, e.g., 2.4557 can be replaced by 2.456. ---- Question 2 [Reinforcement Learning]: Multi-Armed Bandit, UCB and Q-learning ( 4 + 5 + 7 = 16 marks) (Part a) Consider the Multi-Armed Bandit algorithm. In -greedy action selection, for the case of four actions and = 0.72, what is the probability that the greedy action is selected? (The value may be rounded to two decimal places.) (4 marks) (Part b) If Qt(a) at t = 100 for 4 actions [a1, a2, a3, a4] is [0.7, 0.75, 0.55, 0.23] and the number of times which each action is selected, is equal to [55, 33, 11, 14], according to Upper Confidence Bound Action Selection, which action should be selected next? (Assume that c = 1.3.) (5 marks) (Part c) Consider the previous vacuum cleaner world example with two states {, } and two actions {Stay & Vacuum (S&V), Move & Vacuum (M&V)}. The agent (vacuum) performs collect experiences, i.e. <s, a ,r ,s>, for three steps listed below. T= 1: < ,S&V,-1, > T= 2: < ,M&V,2, > T= 3: < ,M&V,-1,> Perform Q-learning using a learning rate of = 0.2 and a discount factor of = 0.9 for each step. The Q-values are initialized to zero at the beginning. (7 marks) ---- Question 3 [Bayesian Network 1 & 2]: (6+5+4+8+4 = 27 marks) Suppose that we want to build a (simple) Bayesian network model for Covid19 (or simply Covid) risk assessment for someone who has been exposed to Covid. (Part a) Design and build in Netica a causal 6 node BN structure (nodes and arcs) that includes the following: A node to represent a persons Covid status following exposure, i.e. whether they will: not get infected, or experience only an asymptomatic infection, have only mild disease, or have a severe case of Covid. A node to represent a rapid antigen (RAT) Covid19 test result A node to represent a PCR Covid19 test result Nodes for two common Covid symptom: a cough, and a lost of sense of taste A node to represent the persons age, discretising in 5 age groups: under 20, 20 to under 50, 50 to under 65, 65 to under 80, 80 and older. Note: no node needed for exposed to Covid as the network will only be used to reason about people who have been exposed. Name your Netica BN file: FamilyName-StudentId-2ndSem2022FIT3080_A2_Q3a.dne (6 marks) (Part b) Parameterise your BN (i.e. construct the CPTs) based on the following advice from a medical expert: The risk of infection, given exposure, increases with age. False positive rates for both COVID tests are extremely low, 1 in 10,000. False negative results for PCR tests are also quite low, 1 in 50 for people with an asymptomatic infection, 1 in 100 for people with mild symptoms, and 1 in 1000 for people with severe illness. False negative results for RAT tests are more common: 30% for people with asymptomatic infection, 10% for those with mild symptoms and only 1% for those with severe illness. A cough is a common symptom, present in 50% of people with mild disease and 95 % of those with severe disease, while loss of taste is less common, occurring at roughly half those rates. The model needs to reflect the fact that even if the person doesnt have Covid, say 5% of people aged 20-80 will have a cough due to another illness or asthma, while 10% of the under 20 and over 80s will have a cough. But for simplicity, lets assume a person with an asymptomatic COVID infection wont have a cough. Similarly, say 1 in 10000 people in the population, who dont have Covid, will have lost their sense of taste. You can assume youll always know the age when doing a COVID risk assessment, so no need to add a prior distribution for the Age node (unless you want to!). Name your parameterised Netica BN file: FamilyName-StudentId-2ndSem2022FIT3080_A2_Q3b.dne (5 marks) (Part c) Use your Covid BN (saved in to answer the following questions: (include screenshots from Netica for each scenario with your written answers) (i) Suppose an 85 year old grandfather and his 3 year old grandson are exposed to Covid at the same time. Before you find out about any symptom or test results, how much more likely is the grandson to avoid a COVID infection than the grandfather? (ii) 3 days after exposure both have a cough, the grandfather has also lost his sense of smell but we dont know if the grandson has (he is too young to answer that question). How much more likely is the grandson to avoid a COVID infection than the grandfather? (iii) Suppose they both do a RAT and test negative. Now how much more likely is the grandson to avoid a COVID infection than the grandfather? (iv) Suppose instead that the RAT result for the grandfather was positive. What is the probability that he will have a severe case of Covid? (4 marks) (Part d) Next we want to extend your BN into a Bayesian decision network (BDN) to help with decisions as to whether to do a Covid test (RAT or PCR) or not and whether or not to give someone anti-viral treatment to reduce the impact of a severe infection. You want the BDN to be able to represent the cost of doing the Covid Test (with a PCR test costing 8 times as much as a RAT) and the cost of the anti-viral treatment, as well as the benefit to someone with severe Covid of receiving (timely) anti-viral treatment. (i) Extend your BN with two decision nodes, and 3 utility nodes, connected to the chance nodes in your existing network. You will also need to add a third state (no result) to the test nodes and adapt the CPTs for those nodes accordingly. Include a screenshot of your BDN in your written answer. (ii) Create utility tables for your utility nodes that result in the best decisions (i.e. with the highest expected utility) for someone 80+ being to have a PCR test, and if they test positive, to be given anti-viral treatment. Include the utility tables in your written answer and explain why you have chosen those values. Name your extended parameterised Netica BDN file: FamilyName-StudentId-2ndSem2022FIT3080_A2_Q3d.dne (8 Marks) (Part e) What are the expected utilities computed by your BDN for the DoTest decisions (ie. doing test, or not doing test), for the grandfather, at the point when he has a cough and has lost his sense of smell? Using the probabilities from your Bayesian decision network and the utilities in your table, in your written answer, do the expected utility computation for that DoTest decision node by hand, ie show the workings to compute EU(DoTest |Cough=True,LossOfTaste=True,Age=80plus). Include a screenshot of your BDN in Netica with evidence entered for this scenario and showing the expected utility values. (4 marks) ---- Question 4 [Machine Learning]: Linear Regression - (8 + 5 + 2 = 15 marks) Linear regression model is a commonly used supervised learning method for predictive data analysis. Given the Boston Housing Dataset, the goal is to predict the house price in Boston from house details. The dataset can be accessed from the following website: https://www.cs.toronto.edu/~delve/data/boston/bostonDetail.html The dataset consists of 506 instances/samples and 16 variables as follows CRIM ZN INDUS CHAS NOX RM AGE DIS RAD per capita crime rate by town proportion of residential land zoned for lots over 25,000 sq.ft. proportion of non-retail business acres per town Charles River dummy variable (= 1 if tract bounds river; 0 otherwise) nitric oxides concentration (parts per 10 million) average number of rooms per dwelling proportion of owner-occupied units built prior to 1940 weighted distances to five Boston employment centres index of accessibility to radial highways TAX full-value property-tax rate per $10,000 PTRATIO pupil-teacher ratio by town B LSTAT MEDV 1000(Bk - 0.63)^2 where Bk is the proportion of blacks by town % lower status of the population Median value of owner-occupied homes in $1000's Write a Python code to build a multivariate linear regression model to predict the median value of a home (i.e., MEDV) using the rest of the variables as predictors. (Part a) Divide the dataset into a training set (instances #1-#400) and a test set (instances #401-#506). Fit a linear regression model on the training set, using the median value of a home (i.e., MEDV) as target (or dependent) variable and all the other 15 variables as predictor (independent) variables. (8 marks) (Part b) Use the fitted model to predict the median values of homes in the test set. (5 marks) (Part c) Compute the mean squared error (MSE) between the predicted and the true median values of homes in the test set. (2 marks) Hint: You can use the scikit-learn library in Python. ---- Question 5 [Machine Learning]: K-means clustering- (11 + 4 = 15 marks) Consider a set of 10 three-dimensional data points , the Table below , as shown in i 1 2 3 4 5 6 7 8 9 10 5 4 1 8 7 6 10 2 9 3 3 2 2 7 9 5 9 1 8 1 xi3 4 2 1 9 8 4 8 3 7 2 We want to apply k-means clustering to this data. Assume the number of clusters is k = 2, and the initial centroids are chosen as: and . You are required to show your answers to the below questions in a spreadsheet (.xls or .xlsx) and to make your working clear. (Part a) Show the calculations for two iterations of the k-means algorithm, and write down the estimated centroids and cluster membership for each data point. Use Euclidean distance to compute the distance between two data points. (11 marks) (Part b) Using the estimated centroids in part (a) above, compute the sum of squared distances from each data point to its closest centroid, defined as follows (4 marks) Hint: You might wish to be guided by the template Excel file in Week 10 lecture resources. ---- Question 6 [Neural Network] - Training an artificial neuron from 3D point data (5 + 6 + 5 = 16 marks) Write an executable script (i.e., code in Python) to train an artificial neuron with The hyperbolic tangent (tanh) activation function in order to classify two classes of 3D (three-dimensional) point data from two Gaussian distributions as follows: 1. For the first Gaussian distribution, the x, y z variables are derived from i.i.d. Normal distributions which have the mean equal to -0.5, -1.0 and -0.7, respectively and standard deviation equal to 0.9 (zero correlation between the x, y and z dimensions - i.e., isotropic Gaussian). 2. For the second Gaussian distribution, the x, y z variables are derived from i.i.d. Normal distributions which have the mean equal to 0.7, 0.6 and 0.8, respectively and standard deviation equal to 0.7 (zero correlation between the x, y and z dimensions - i.e., isotropic Gaussian). From the above introductory description, we now provide some coding exercises. (Part a) Generate 200 samples randomly for each class and provide their output labels. Randomly initialize all the weights for the neuron between 0 and 1 and visualize the data points for each class using different colours/markers. (5 Marks) Hint: for the data point generation and the weights initialization, you can use the np.random.randn in NumPy Python for the random data point generation and, you can use np.random.rand in NumPy Python for the initialization of weights. (Part b) Assuming the learning rate is 0.1, train the model (using gradient descent - step 1, 2 and 3 in lecture materials from Lecture 11, approximately slides 17-20) for 30 iterations and report the final value of the weights and the total error (use the values at iteration 30, assuming that iteration 0 denotes the beginning). (6 Marks) (Part c) Report the output values of the model for the following 4 test data points (use the values at iteration 30, assuming that iteration 0 denotes the beginning) Data point 1 = (-1, -1,-1) Data point 2 = (0.1, 0.2,0.3) Data point 3 = (0.5, 0.5, 0.5) Data point 4 = (1.5, 2, 0.5) (5 Marks) -------- -------- This is the end of Assignment 2. Following are some Additional Remarks and Instructions. These give general strategies for tackling the questions and important considerations that you should keep in mind throughout. Additional Remarks and Instructions Late penalties: Work submitted after the deadline (possibly with a small amount of grace time) will be subject to late penalties in accordance with the FIT3080 Unit Guide and Faculty and University policies, possibly 10% per calendar day and certainly no less than 5% per calendar day. (This percentage is taken from the total marks for the Assignment, not from the students mark. So, as an example, if the student gets 70% and then gets a 10% late penalty then the mark becomes 70% - 10% = 60% and does not become 70% x 90% = 63%.) If you do not submit matching .pdf and .py files (e.g., if you submit two files but one is blank or unreadable, or if you only submit one file) and/or if you do not submit matching .pdf and .xls (or .xlsx) files, then any affected work will be deemed late - and will be subject to the relevant penalties, possibly receiving a mark of 0. Work submitted 10 or more calendar days after the deadline will possibly be given a 0 mark. Other important notes: Note 1: The details of the submission instructions are possibly subject to change. In that event, students will be notified. Note 2: And a reminder not to post even part of a proposed partial solution to a forum or other public location. If asking a question in public, you are advised to please make an effort to ensure that your question is asked in a way that does not contain even part of a proposed partial solution. It will often be helpful to find a way to post it as a general question (not directly pertaining to the Assignment) and then to put it in the General category at Ed Discussion. You are reminded that Monash University takes academic integrity very seriously. Note 3: It is your responsibility to be familiar with the special consideration policies and special consideration process. Note 4: As a general rule, please dont just give a number or an answer like `Yes or `No without at least some clear and sufficient explanation - or, otherwise, you risk possibly being awarded 0 marks for the relevant exercise. Make sure to explain your answer and show your working in all parts of all questions. Make it easy for the person marking your work to follow your reasoning. For Question 3, you can respond to any of the sections, However your .pdf should typically cross-reference any corresponding answer in your Netica .dne files. Without clear cross-reference between .pdf and .py, it is possible that any such exercise will be awarded 0 marks. In addition, your .pdf should typically cross-reference any corresponding answer in your (Question 4 and Question 6) Python .py files. Without clear cross-reference between .pdf and .py, it is possible that any such exercise will be awarded 0 marks. Your .pdf should typically also cross-reference any corresponding answer in your (Question 5) .xls (or .xlsx) spreadsheet file. Without clear cross-reference between .pdf and .xls (or .xlsx), it is possible that any such exercise will be awarded 0 marks. Note 5: As a general rule, if there is an elegant way of answering a question without unnecessary extra work, try to do it that way. More generally, more elegant solutions are preferable - and might at least sometimes be given more marks, possibly many more marks. Show your working and make your answers clear. (Another way to think of this is to try to put yourself in the markers situation.) Note 6: All of your submitted work should be and must be in machine readable form, and none of your submitted work should be hand-written - with all cases of handwritten work possibly resulting in 0 marks. Show your working and make your answers clear. Note 7: If you wish for your work to be marked and not to accrue (possibly considerable) late penalties, then make sure to upload the correct files and (not to leave your files as Draft but) also to hit `Submit to make sure that your work is submitted. Plagiarism declaration: You are required to state explicitly that you have done your own work, however the Moodle assignment submission details permit you to declare this. For example, if you are presented with an 'Assignment Electronic Plagiarism Statement', then you are required to complete the 'Assignment Electronic Plagiarism Statement' quiz on the FIT3080 Moodle site and accept the Student Statement (electronic version of the Assignment cover sheet). If you do not accept the Student Statement, then your assignment may not be marked, and you may be given a mark of 0. PLAGIARISM IS NOT ACCEPTABLE