General ------- Marking the assessments was a positive experience for me since most students had got their heads round some challenging material. It's clear that many students put a lot of effort into this assessment and have consequently got good marks. Well done! Your individual feedback files contain the output of the Python profiler. I ran this on submitted answers just in case it helped me with the marking. In the event it didn't, but I haven't deleted it since I was worried about deleting some of the feedback by accident. Apologies for the extra crud. My model answers are available in this directory: http://www-users.cs.york.ac.uk/~jc/teaching/agm/assessment/09/ Concerning Python code, most solutions were considerably more complex and long than needed. Q1 -- The distribution in equation (1) can be written as a product of exp(-w_i) values. These values can be thought of as 'penalties' for 'breaking' the relevant clause. It remains to define a factored representation such that each instantiation gets the right product of penalties. Note that there is no need to compute the Z value, the question asks you to produce a FR object that represents the distribution. Once the factors are chosen a probability distribution is (almost always) defined, irrespective of whether you have bothered to compute the Z. If a clause is not a tautology then exactly one instantiation of its variables will break the clause. This instantiation should get the exp(-w_i) penalty. All others should get no penalty which means giving them the value 1. It follows that for each non-tautologious clause there should be a factor with the same variables as the clause and with all values set to 1 except for the 'breaking instantiation' which has value exp(-w_i). This latter value becomes 0 for a hard clause. For a tautology (eg "x or not x") students took one of two choices: not bothering to create any clause or creating one with all ones. Both are OK. I took the latter option out of laziness. There seems no particular reason to avoid two passes through the clauses: one to find the cost for hard clauses and one to actually create the factors. No distribution is defined in the special case that Z turns out to be 0. This happens if the hard clauses are unsatisfiable, since then every instantiation breaks at least one hard clause and thus gets a 0 in the product defining its (unnormalised) probability. It's not enough to say that Z is 0 when there are two contradictory clauses. Once can get unsatisfiable CNFs where no two clauses are contradictory, but all clauses together are. Q2 -- Most students put work into optimising a variable elimination approach. Some went for a join tree method. There were many reasonable to good answers in this direction. These are the algorithms studied in the module and students should be able to get good marks by employing them intelligently. However, there are reasons to take a different tack. For a join tree approach one problem is if the variables in the instantiation end up in different cliques/nodes of the tree. More generally both of these approaches manipulate factors (tables with attached numbers) which is a drawback when, at the end of the day, you only want a single number. To take an extreme example, if the instantiation happens to be a full instantiation then all we need to do is to find the appropriate number in each factor and multiply them all: no factor multiplication or marginalisation is required. This motivates using an algorithm called 'recursive conditioning' (RC) which breaks the problem down by working on instantiations of the *uninstantiated* variables and adding up the results. A number of students stated that conditional independence cannot be used for this problem. This is not the case and RC uses it. For example, suppose the variables are A, B, C, D, E and F and {A,B} is independent of {D,E,F} given C. If C is instantiated then the problem can be broken down into two smaller subproblems (that's the recursive bit in RC). If C is not instantiated then we can consider different instantiations of it in turn and sum the results. Few students considered RC and those who did rejected it, but it's a good fit to the problem. It is not true, as some claimed, that it only applies to BNs. My model answer is a direct implementation of a (with caching) version of RC as given by Darwiche in his 'Modeling and Reasoning with Bayesian networks'. Q3 -- The basic idea is to simulate trajectories from various starting points and see whether you end up at success or failure. Most students correctly identified the important trick here: each state the robot visits on a simulated trajectory can be counted as if the trajectory had started there. This is due to the Markov property. Doing so greatly increased the counts for reaching success/failure for each state and thus the speed with which a decent probability estimate can be found. A number of students talked about 'finding/computing probabilities' and then using these found probabilities to compute others. No probabilities are found, all are merely estimated. A number of students used a dynamic programming approach (similar to what is used in something called reinforcement learning) to estimate probabilities. Nothing wrong with this per se, but the question required you to implement a simulation-based approach. Some students correctly noticed that some states tend to get visited more than others and therefore adapted the sampler to compensate. This is a nice touch and more sophisticated than my approach. The sampler can be made much faster by finding and storing all neighbours of a cell before we start sampling and then just randomly choosing a neighbour at sample time. You don't want to be spending time working out permissible neighbours and adding numbers each time you make a move. Very few (I think 1 or 2) students did this caching. One who did reported a 75% speed up by doing this. There is no unique stationary distribution. The distribution with probability 1 of being at success is stationary, but then so is the one with all the probability at failure. So no unique one. Question 2 is the trickiest part of the assessment. No one got it right. We're dealing with a Markov chain with some fixed starting point s0 (which is not failure). Let Z(s0) be the probability of reaching success from this point. Then P(s0,s1,...success|reaches success) = P(s0,s1,...success,reaches success) / P(reaches success) = P(s0,s1,...success) / P(reaches success) = Z(s0)^{-1}P(s0,s1,...success). It follows that P'(s0,s1,...success) > P(s0,s1,...success) for *every* trajectory ending in success. It follows that it's not enough to alter the transition probabilities for the cells just next to failure so that you avoid the failure location. Because doing so does not increase the probability of trajectories ending in success which do not involved those cells. Instead let Z(s_i) be the probability of reaching success from s_i in the original situation (s_i != failure). Let p_ij be the probability of moving from s_i to s_j in one step. Define a new Markov chain with transition probabilities p'_ij where p'_ij = p_ij*(Z(s_j)/Z(s_i)). Doing this increases the probabilities of all success-ending trajectories by Z(s0)^{-1} as required.