Overview A Latin Square of order N is a N × N matrix containing the integers 1, . . . , N, such that each value appears exactly once in a row, and exactly once in a column. Another way to express this is that each row and column is a permutation of the numbers 1, . . . , N. For example, the following is a Latin Square of order 5: 1 2 5 3 4 3 5 1 4 2 5 4 3 2 1 2 1 4 5 3 4 3 2 1 5 These are similar to the popular Sudoku puzzles (after the puzzle is nished), but a little simpler, as they do not have “block constraints.” As you may already have guessed, there are many Latin Squares of order N, and many dierent values of N we can use. If we take a Latin Square and erase some of the values, we create a kind of a puzzle (again, similar to a Sudoku puzzle). For example, here’s a partially lled in 5×5 matrix, with the _ symbol representing a blank cell: _ 2 _ _ 4 3 _ 1 _ _ _ 4 _ _ 1 2 _ _ _ 3 _ _ 2 1 _ This matrix was created by deleting values from the Latin Square, above, so we know it can be completed. We can call this an incomplete Latin Square. The Latin Square Completion Problem is to ll in the the blank cells of an incomplete Latin Square, using the values from 1, . . . , N, to create a complete Latin Square. This problem was often used by researchers as a source of solvable problem instances of various sizes (N) and di culty levels (the number of blanks), to test and evaluate the performance of their constraint satisfaction algorithms. Example problems A number of example les, containing one or more incomplete Latin Squares, are available to you on the Moodle page. All the examples given in the examples le are solvable (and were constructed by a program to generate solvable instances). Some of them may have more than one completion. All we need is to nd one of them. Some of the data les have just one example. One of the les has many examples. Each example has the same format, as follows. • The rst line in the le contains a single integer, indicating the number of examples in the le. The rest of the le consists of examples, as follows. • The rst line of an example is the order, i.e., the value for N. • Exactly N rows with N values, separated by spaces. The value _ indicates a blank. • There is always exactly one blank line after every example. You’ll be asked to apply your implementations to a le containing 56 examples, which are generally increasing in di culty. Once you notice your program is not solving problems of a certain size, you can terminate the program to save some of your time.Coding hints The simplest way to deal with the data les is to write a single function that can read in the le, and produce a list of “squares”, i.e., a 2-dimensional list (or array) of integers (or strings). Once you have one or more of these “squares” in a list, you have a lot of exibility. You can implement a Problem class code ti initialize a Problem given any single square. This will prevent a lot of needless recoding as you move from les with 1 example to les with several examples. The constraints in this problem are called “global” in the text, because they involve whole rows (and columns). For example, the constraint on a row is that each row is a permutation of the numbers 1, . . . , N. However, and this is important, all global constraints can be re-written using multiple binary constraints (i.e., constraints between 2 variables). In our case, a row is a sequence of cells, and each cell can be a variable. Furthermore, the permutation constraint can be rewritten as a so-called “all-dierent” constraint involving all the cells on the row, which in turn can be rewritten in terms of multiple “not equal to” constraints between all pairs of variables. The point is, don’t over think the constraints, and don’t over think the goal test. A problem made up entirely of not-equals constraints is as straightforward as it gets (it’s like searching a map with A∗ using straight-line distance as your heuristic — really well suited for the problem and a good teaching example, but not representative of the variety of problems to be solved). We can get a pretty good understanding of constraint solving using these simple constraints, but keep in mind that there are constraint problems involving other kinds of constraints. Execution instructions The markers may or may not wish to run your program, to verify your results. To help them, you should provide brief instructions on what to do to get your program running. Include: • Programming language used (including version, e.g., Java 8 or Python 3) • A simple example of compiling and/or running the code from a UNIX shell would be best. Keep it brief, and name it with the question number as the following example: a3q1_EXECUTION.txt. If your assignment uses third party libraries, they have to be included in your submission.Question 1 (15 points): Purpose: To apply the techniques of AIMA Chapter 3 (Assignment 1) to this problem. Degree of Di culty: Easy. To truly understand how bad the techniques of Chapter 3 (Assignment 1) are for this problem, we’re going to implement it. It should not take too long, provided you understand the interfaces involved. The result will be a fairly easy program to write, but it will be very slow, except for very small problem instances. You may use your own implementation of DFS from your search strategies for Assignment 1, or you can make use of the solutions provided (in Python only, sorry). In any case, your work should be focussed on the Problem classes, and none of what you do needs to aect the search strategies. DFS is not going to change! You’ll need to implement: • State: Represent the problem naively, as a 2-dimensional list (or array) of integers (the blank in the le could be stored as a zero). You could add a list of blank locations by giving the row and column as integer pairs (e.g., (2, 3) ). This would help speed up some of the other functions. • Problem is_goal(state): Checks if state array is a true Latin Square. Note that if there is a blank (a zero), it’s de nitely not a completed Latin Square; you don’t have to keep checking if there are any blanks in your list of blanks. • Problem actions(state): A blank can be lled in with any number 1, . . . , N. You can specify which blank to ll in, or you can assume it will be the rst blank in your list of blanks. But don’t actually ll in the blank yet. That’s the work of result(). • Problem result(state, action): Creates a new State object with the blank lled in, as described in action. Make sure you copy your lists/arrays, and change the copy. Note: Don’t try to add anything clever to the code to make it faster. Your program does not have to solve all the problems! Just implement the simplest version of actions() and result(). We’ll be more clever in later questions. This is a straw-man implementation of an idea that seemed pretty good in Chapter 3, but is really not very good here. You need to see it to believe it. So be quick about getting the simplest implementation of the above speci cation as possible. Questions to answer Apply your implementation to the examples in the given data le LatinSquares.txt. Use a time-limit of 10 seconds for each problem. Answer the following questions and submit them: 1. How many of the problems did your implementation solve within 10 seconds? 2. Consider the largest N that your implementation as able to solve. Do a rough, back-of-the-envelope calculation to predict how much time it would take to solve the next largest problem in the le, and the very largest problem in the le. Submit your rough calculations, and your predictions. What to Hand In • A le named a3q1_EXECUTION.txt containing brief instructions for compiling and/or running your code. See page 1. • A le named a3q1.LANG containing your implementation of the State and Problem classes. Use the le extension appropriate for your choice of programming language, e.g., .py or .java.• A le named a3q1.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the responses to the above questions. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 6 marks: Your implementation of the State and Problem class captures the problem in a way that re ects Chapter 3. Your program does not have to solve all problems. • 9 marks. Your answers to the questions are plausible and supported by evidence. Question 2 (15 points): Purpose: To implement the Constraint Satisfaction Problem concept of State as variables with domains. Degree of Di culty: Moderate. The transition from A3Q1 to A3Q2 will take the most time of all questions. In this question, you’ll replace the State from the previous question. It will involve making changes to your State and Problem classes, just to change the State representation from 2-dimensional lists/arrays, to a collection of CSP variables with domains. This is a preliminary step towards applying more advanced algorithms, but essentially, your implementation of a3q2 will explore the same set of combinations as the previous question. We won’t get advanced performance in this question. You should only need to change the Problem and State classes. • Variable: A variable should be an object with a current value, and a list or set of domain values. If the variable is not assigned a value yet, the current value can be NULL or None. When the variable is assigned a value, the domain should be set to an empty list or set. A variable does not need to know its own identi er, but it could. • State: In this question, your State should consist of a collection of Variables. – The collection could be a list, or a 2-dimensional list, or a dictionary indexed by variable identi ers. – Each variable needs an identi er, and for some problems a string would work ne. But here, it might be easiest to use a pair of numbers representing the row-column index of the variable’s location in the square. The identi er is used to nd the variable by name, without having to store multiple references (Using references as variable identi ers is possible but not advised. The programmer time spent debugging is not worth the speed increase you’d see. Leave that kind of optimization for your code that matters more. We’re experimenting.) – Remember that variables start out unassigned, and are assigned as the search goes on. Your state could have a list of unassigned variable identi ers to help avoid searching for unassigned variables. Don’t store your actual variables in two dierent lists, unless you enjoy headaches and frustration. • Problem is_goal(state): Checks if the State is a solution to the Latin Square completion problem. Note that if there is any unassigned variable, it’s de nitely not a completed Latin Square; you don’t have to keep checking if there are any variables still unassigned. You could adapt your code for A3Q1.is_goal(state) to implement this function. You may need to combine the information contained in the given “square” with the values assigned in your state. • Problem actions(state): Here, choose an unassigned variable and create an action for each allowable domain value. But don’t actually make the assignment yet. That’s still the work of result() • Problem result(state, action): Creates a new State, with the variable assigned the given value, as provided by action(). Make sure you copy the variables appropriately, and change the copy. Notes: • Your Problem class constructor should take a “square” as an input argument, and from that square. You can have another method called initial_state() that uses the square to create a State object. • For this question, the domain for every blank cell in the square should start out with all the values 1, . . . , N, i.e., don’t remove values that appear on the same row and column. We’ll x that in the next question. • In class we said it was possible to represent this problem 2 ways: Every cell ( lled or blank) could be a variable; or only the blank cells are variables. It’s slightly more advantageous to make variables for only the blank cells. It complicates the goal test a bit. • The is_goal(state) function is also a bit hard to get right, but test it with examples, not by applying your search algorithms. • The action() and result() functions should be straight-forward, once you have everything else settled. • Test your is_goal(state), action(), and result() functions before trying them out with search. A test script that you can re-run when you make changes to your code will save you lots of time! Questions to answer Apply your implementation to the examples in the given data le LatinSquares.txt. Use a time-limit of 10 seconds for each problem. Answer the following questions and submit them: 1. How many of the problems did your implementation solve within 10 seconds? How does this compare to the previous implementation (A3Q1)? 2. Consider the largest N that your implementation as able to solve. Do a rough, back-of-the-envelope calculation to predict how much time it would take to solve the next largest problem in the le, and the very largest problem in the le. Submit your rough calculations, and your predictions. What to Hand In • A le named a3q2_EXECUTION.txt containing brief instructions for compiling and/or running your code. See page 3. • A le named a3q2.LANG containing your implementation of the State and Problem classes. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a3q2.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the responses to the above questions. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 6 marks: Your implementation of the State and Problem class uses a collection of variables and domain values. Your program does not have to solve all problems. • 9 marks. Your answers to the questions are plausible and supported by evidence. Question 3 (5 points): Purpose: To demonstrate the power of the very simplest of improvements to the previous implementation. Degree of Di culty: Easy. In the previous question, the domains were deliberately left as the values 1, . . . , N. In this question, change your problem class code so that each variable’s domain is restricted to value that do not appear on the cell’s row and column. For example, consider the top left blank in the following square: _ 2 _ _ 4 3 _ 1 _ _ _ 4 _ _ 1 2 _ _ _ 3 _ _ 2 1 _ Since the values 2, 4 appear in the row, and the values 2, 3 appear in the column, the cell cannot take those values, and so the domain for the top left cell should be limited to just {1, 5}. Implement this restriction by creating variables whose domains are all feasible just looking at the row and column (probably in your initial_state() method). Don’t change anything else. Questions to answer Apply your implementation to the examples in the given data le LatinSquares.txt. Use a time-limit of 10 seconds for each problem. Answer the following questions and submit them: 1. How many of the problems did your implementation solve within 10 seconds? How does this compare to the previous implementation (A3Q2)? 2. Consider the largest N that your implementation as able to solve. Do a rough, back-of-the-envelope calculation to predict how much time it would take to solve the next largest problem in the le, and the very largest problem in the le. Submit your rough calculations, and your predictions. What to Hand In • A le named a3q3_EXECUTION.txt containing brief instructions for compiling and/or running your code. See page 3. • A le named a3q3.LANG containing your implementation of the State and Problem classes. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a3q3.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the responses to the above questions. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 2 marks: Your implementation of the domain restrictions is correct. Your program does not have to solve all problems. • 3 marks. Your answers to the questions are plausible and supported by evidence. Page 8 Question 4 (15 points): Purpose: To implement the Constraint Satisfaction Problem concept of forward checking. Degree of Di culty: Easy. Forward checking is a process of removing values from the domains of some unassigned variables, if those values can be determined to be inconsistent with the current partial assignment. The way it will work in the LSCP is as follows: When a cell X is assigned the value v, we know that no other variable in X’s row or column can also have the value v. So, if the value v is still a domain value in any unassigned variable on X’s row or column, we can remove it in advance, so that it is never tried. There are some complications. 1. The value v might not appear in the domain when you try to remove it. That’s perfectly ne; it might have been removed for some other reason. This removal is more like a prevention. Only remove it if it is still there. 2. Don’t try to remove a domain value from an assigned variable. 3. We’re exploring states that represent dierent partial assignments. You really need to make sure that your states and domain values are copies, and not references to a common list. When you remove a domain value in one state, it can’t aect other states by accident! 4. It could be that you’ll remove the very last possible domain value for some unassigned variable. When that happens, there is no consistent assignment for that variable, and so the current partial assignment (the state) is inconsistent. The best thing to do is to recognize when a domain goes empty as you’re removing the value. The easiest way to manage it is to have a Boolean ag in your state for consistent or inconsistent assignments. Set the ag as soon as possible. Starting with A3Q3, implement the forward checking for LSCP: • State: Include a boolean ag for to indicate if the state is known to be inconsistent. • Problem is_goal(state): With forward checking, every consistent partial assignment can be extended by one more variable (at least). That means when the assignment is complete (no unassigned variables), it must be consistent! This simpli es the goal test substantially! • Problem actions(state): Check if the current state is inconsistent. If it is not consistent, return an empty list of actions. This prevents inconsistent states from having children. • Problem result(state, action): The action is a variable X and a domain value v. Copy the state as usual, make the assignment, and then remove the value v from the domain of any unassigned variable in X’s row and column. See the note above about removing values. Questions to answer Apply your implementation to the examples in the given data le LatinSquares.txt, using a time-limit of 10 seconds for each problem in this le. Then apply your implementation to the examples in the given data le harder_examples.txt, using a time-limit of 200 seconds for each problem in this le. Answer the following questions and submit them: 1. How many of the problems did your implementation solve within the time limit? How does this compare to the previous implementation (A3Q3)? Page 9 What to Hand In • A le named a3q4_EXECUTION.txt containing brief instructions for compiling and/or running your code. See page 3. • A le named a3q4.LANG containing your implementation of the State and Problem classes. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a3q4.txt (other le formats like PDF, DOC, DOCX, RTF are also acceptable) with the responses to the above questions. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 10 marks: Your implementation of the domain restrictions is correct. Your program does not have to solve all problems. • 5 marks. Your answers to the questions are plausible and supported by evidence. Page 10 Tasks for the ambitious It seems that forward checking is a big improvement, but it has its limits. It works really well on toy kinds of problems (Latin squares, N-Queens). However, most CSP solvers use a stronger form of processing called arc consistency, which has higher complexity than forward-checking, but usually results in much more signi cant domain reductions for most real-world problems. Implement a version of the AC-3 algorithm. You can use it in initial_state() to make sure that the initial domains for your problem start o possibly highly reduced even compared to A3Q3, and in result() as in A3Q4, to keep your domains even smaller than forward-checking. The bigger your problem, the more the extra processing pays o! Page 11
Overview We start by de ning a simple calculating machine. The machine has one register, R, which can store a double precision oating point value (integers will be automatically converted). The machine has the following instructions: Instruction Eect NOP v R does not change ADD v R = R + v SUB v R = R − v MUL v R = R × v DIV v R = R/v ( oating point division) Notice that the NOP operation eectively tells the machine to ignore the given number. Here’s an example script with 5 instructions, listed horizontally for convenience: ✞ ☎ MUL 1, NOP 2 , ADD 3 , SUB 4 , DIV 5 ✝ ✆ This saves space on the page for examples. We will assume that the register R is initialized to 0.0 (zero) at the start of every script. With this assumption, after executing the above sequence of instructions, the register would contain a oating point value close to −0.2. Targeted Coding Problem The Targeted Coding Problem is stated as follows. You are given a oating point target value T, and a list of numbers, L, of any length. You are to nd a sequence of instructions for our simple machine above that calculates a value as close to T as possible, using all the numbers in L. You must use every number in L, and you cannot change the order. This means that the only thing you can do is gure out which operator to give to each value in the list. For example, given L = [1, 2, 3, 4, 5], you could try: ✞ ☎ MUL 1, ADD 2 , ADD 3 , DIV 4 , ADD 5 ✝ ✆ or ✞ ☎ ADD 1, NOP 2 , NOP 3 , SUB 4 , DIV 5 ✝ ✆ You may use any of the 5 operators any number of times. These restrictions are arti cial, but they allow us to explore the local search ideas without over-complicating the task. The objective is to minimize the dierence between the target, T, and the result of a sequence of instructions (as described above). To make this precise, let m(s) represent the value in the simple machine’s register after executing the instruction sequence s. The objective function is de ned as follows: f(s, t) = |t − m(s)| where s is any sequence of instructions, and t is the target value. Page 2 CMPT 317 Introduction to Artificial Intelligence Programming ideas The machine It’s easy to write a simple interpreter for this machine. In Python it would look something like this: ✞ ☎ def machine_exec ( seq ): register = 0 for instruction in seq : operator = instruction [0] operand = instruction [1] if operator == “ADD “: register += operand elif operator == ” SUB “: register -= operand elif operator == ” MUL “: register *= operand elif operator == ” DIV “: register = register / operand elif operator == ” NOP “: pass else : print (’unknown operator ’, operator ) return register ✝ ✆ You can implement the above function in any language. You don’t need to parse a text le containing a script. You can represent a script using lists or arrays. For example, in Python you might use something like this: ✞ ☎ [( ’MUL ’, 1) , (’ADD ’, 2) , (’MUL ’, 3) , (’SUB ’, 4) , (’MUL ’, 5)] ✝ ✆ For non-Python programmers, 2-dimensional arrays are completely acceptable. Once you are sure you’re getting correct results, you can even start using a compiled form, by turning operator strings to integers, to save space and save time. ✞ ☎ [(1 , 1) , (0 , 2) , (1 , 3) , (2 , 4) , (1 , 5)] ✝ ✆ It’s machine code now, and harder to read. But the rst value is the compiled operator, and the second is the operand. It may even be advantageous to split the operators and and operands into two lists (or arrays): ✞ ☎ operations = [1 , 0 , 1 , 2 , 1] operands = [1 , 2 , 3 , 4 , 5] ✝ ✆ This might be useful because we’ll be changing the operations, but not the operands. You’ll have to modify your machine_exec() program. Page 3 CMPT 317 Introduction to Artificial Intelligence Clari cation In Assignment 1, we explored a similar problem using a constructive approach: an expression was constructed from an initially empty expression. It’s rather like the textbook example of solving the 8- Queens problem starting from an empty board, and placing the queens on the board one at a time. This approach is what AIMA Ch 3 is all about. In Assignment 2, we want to explore AIMA Ch 4.1. We’ll take a mutative approach instead. It will be like the textbook example of solving 8-Queens, putting all 8 queens on the board to start, and then solving the problem by moving queens around, one at a time. To be clear, every question in Assignment 2 should start with a complete script that uses all the numbers in the given order, and has an operator for each one. For example, suppose our target is T = 40, and our list is L = [1, 2, 3, 4, 5]. You’d start every local search strategy with a random program using the numbers, perhaps: ✞ ☎ Add 1, Mul 2 , Add 3 , Nop 4 , Div 5 ✝ ✆ All the numbers are used, in the order given; the script is built all at once, not one step at a time as in A1. Your Problem class should have a method to create random scripts like this for lists L of any length. After that, your search algorithms will explore other complete scripts by various means. In Q1, you’ll just create completely random scripts like this. In Q2, you’ll make a random change to a scripts (by selecting one of the operations, and changing it at random. In Q3, you’ll look at all scripts that are exactly one operation change away, and keep the best one. Etc. Each time you have a complete script, and each script will have a value, namely its score according to the objective function de ned earlier. Software Design As in Assignment 1, it’s a good decision to separate the programming into loosely coupled modules. • A Problem State class. An ADT to contain information that changes as the search algorithm explores the problem space (also called the state space). Clari cation (04/10/2018) The problem state should contain a complete script, as explained above. • A Problem class. An ADT to contain particulars about the Problem. It should have a small number of standard methods. Clari cation (04/10/2018) The actions() result() model for AIMA Ch 3 is probably not the most convenient. Each Question gives a suggestion on what you’ll need. • A module to contain search algorithms. The search algorithms should interact with the Problem only through the standard methods. Assignment 1 Question 1 confused a lot of people, so I am leaving it out this time. You have to do similar work here, but it’s not o cially a “question.”Question 1 (6 points): Purpose: To implement the Random Guessing search strategy, and apply it to the Targeted Coding problem. Degree of Di culty: Moderate. This is where you have to get most of the problem class de ned, and do some thinking about design. The search algorithm itself will not be di cult. The Random Guessing search strategy can be described with the following pseudo-code: ✞ ☎ function random_guessing ( problem ) // Keep generating completely random states // Remember the best one best_guess = obtain a random state from the problem while there ’ s still time guess = obtain a random state from the problem if guess is better than best_guess : best_guess = guess return best_guess ✝ ✆ To control the time spent searching, implement a simple counter, limiting your algorithm to a given number of iterations of the main loop. Clari cation (10/10/2018) Ignore time. Just count iterations. More iterations means more time. An iteration-limit should probably be passed as an argument, meaning you’ll need another parameter in the implementation. Implement the search strategy, and demonstrate that your implementation works, by applying it to the Targeted Coding problem, maybe a few of the simple examples. Clari cation (04/10/2018) For this problem, your problem class should have a method that creates a complete script randomly. What to Hand In This assignment is broken into pieces, and the last question asks for all the source code, so you don’t have to hand in multiple copies. But pay attention to these requirements: • A le named a2q1.txt containing a demonstration of the output of your program, which is copy/paste from a console, or output le. You only need to show a few examples. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a2q1.LANG containing your implementation of the search algorithm. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. For this question, only submit the implementation of the search algorithm, not the problem state or problem class implementations. The markers will not attempt to run the code you submit. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 6 marks: Your implementation of Random Guessing is correct, and well-documented.Question 2 (6 points): Purpose: To implement the Random Search search strategy, and apply it to the Targeted Coding problem. Degree of Di culty: Easy. Hopefully, your problem class de nition can be extended easily! The Random Search search strategy can be described with the following pseudo-code: ✞ ☎ function random_search ( problem ) // Randomly generate successors from the current state // Move to it if it ’ s better than the current state best_guess = obtain a random state from the problem while there ’ s still time guess = obtain a random neighbour of best_guess if guess is better than best_guess best_guess = guess return best_guess ✝ ✆ To control the time spent searching, implement a simple counter, limiting your algorithm to a given number of iterations of the main loop. Clari cation (10/10/2018) Ignore time. Just count iterations. More iterations means more time. An iteration-limit should probably be passed as an argument, meaning you’ll need another parameter in the implementation. Implement the search strategy, and demonstrate that your implementation works, by applying it to the Targeted Coding problem, maybe a few of the simple examples. Clari cation (04/10/2018) For this problem, your problem class should have a method that creates a complete script by randomly making a change to a given script. Clari cation (10/10/2018) A “neighbour state” is any state you can get to from the current state. In this context, the neighbours if script S are all the scripts that are dierent from S by exactly one instruction. What to Hand In This assignment is broken into pieces, and the last question asks for all the source code, so you don’t have to hand in multiple copies. But pay attention to these requirements: • A le named a2q2.txt containing a demonstration of the output of your program, which is copy/paste from a console, or output le. You only need to show a few examples. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a2q2.LANG containing your implementation of the search algorithm. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. For this question, only submit the implementation of the search algorithm, not the problem state or problem class implementations. The markers will not attempt to run the code you submit. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 6 marks: Your implementation of Random Search is correct, and well-documented.Question 3 (6 points): Purpose: To implement the Hill-climbing Search search strategy, and apply it to the Targeted Coding problem. Degree of Di culty: Easy. You might need to refactor your code a bit, to make things nice, but the search algorithm is easy. The Hill-climbing Search search strategy can be described with the following pseudo-code: ✞ ☎ function hill_climbing_search ( problem ) // Starting from a random state // Obtain the state ’ s best neighbour // Move to it if it ’ s better than the current state // Stop if no neighbour is better best_guess = obtain a random state from the problem while there ’ s still time guess = obtain the best neighbour of best_guess if guess is better than best_guess best_guess = guess else if best_guess is better than guess return best_guess return best_guess ✝ ✆ To control the time spent searching, implement a simple counter, limiting your algorithm to a given number of iterations of the main loop. Clari cation (10/10/2018) Ignore time. Just count iterations. More iterations means more time. An iteration-limit should probably be passed as an argument, meaning you’ll need another parameter in the implementation. Implement the search strategy, and demonstrate that your implementation works, by applying it to the Targeted Coding problem, maybe a few of the simple examples. Clari cation (04/10/2018) For this problem, your problem class should have a method that returns the best neighbour of a given script. Here, a neighbour is any script that is exactly one change away from the given script. Clari cation (10/10/2018) A “neighbour state” is any state you can get to from the current state. In this context, the neighbours if script S are all the scripts that are dierent from S by exactly one instruction. What to Hand In This assignment is broken into pieces, and the last question asks for all the source code, so you don’t have to hand in multiple copies. But pay attention to these requirements: • A le named a2q3.txt containing a demonstration of the output of your program, which is copy/paste from a console, or output le. You only need to show a few examples. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a2q3.LANG containing your implementation of the search algorithm. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. For this question, only submit the implementation of the search algorithm, not the problem state or problem class implementations. The markers will not attempt to run the code you submit. Be sure to include your name, NSID, student number, and course number at the top of all documents.Evaluation • 6 marks: Your implementation of Hill-climbing Search is correct, and well-documented.Question 4 (6 points): Purpose: To implement the Random-Restart Hill-climbing Search search strategy, and apply it to the Targeted Coding problem. Degree of Di culty: Easy. The Random-Restart Hill-climbing Search search strategy simply repeats Hill-climbing a number of times. You should control the number of restarts and the number of steps that Hill-climbing is allowed, using separate parameters. Implement the search strategy, and demonstrate that your implementation works, by applying it to the Targeted Coding problem, maybe a few of the simple examples. What to Hand In This assignment is broken into pieces, and the last question asks for all the source code, so you don’t have to hand in multiple copies. But pay attention to these requirements: • A le named a2q4.txt containing a demonstration of the output of your program, which is copy/paste from a console, or output le. You only need to show a few examples. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a2q4.LANG containing your implementation of the search algorithm. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. For this question, only submit the implementation of the search algorithm, not the problem state or problem class implementations. The markers will not attempt to run the code you submit. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 6 marks: Your implementation of Random-Restart Hill-climbing Search is correct, and well-documented. Page 9 Question 5 (6 points): Purpose: To implement the Stochastic Hill-climbing Search search strategy, and apply it to the Targeted Coding problem. Degree of Di culty: Easy. The Stochastic Hill-climbing Search search strategy is a minor variation on Hill-climbing. Instead of requiring the best neighbour of the current state, you get a random choice from the neighbours that are better than the current state. The textbook suggests that the probability of choosing a state should depend on how much better the state is: better states have higher probability of being chosen. But that’s a tricky bit of code, so just choose any one of the better neighbours, with equal probability. Implement the search strategy, and demonstrate that your implementation works, by applying it to the Targeted Coding problem, maybe a few of the simple examples. What to Hand In This assignment is broken into pieces, and the last question asks for all the source code, so you don’t have to hand in multiple copies. But pay attention to these requirements: • A le named a2q5.txt containing a demonstration of the output of your program, which is copy/paste from a console, or output le. You only need to show a few examples. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a2q5.LANG containing your implementation of the search algorithm. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. For this question, only submit the implementation of the search algorithm, not the problem state or problem class implementations. The markers will not attempt to run the code you submit. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 6 marks: Your implementation of Stochastic Hill-climbing Search is correct, and well-documented. Page 10 Question 6 (20 points): Purpose: To measure the quality of the search algorithms in terms of error, and time, and make comparisons. Degree of Di culty: Moderate Now that you’ve got your search algorithms working, we’ll get some empirical results to demonstrate their relative performance. We want to assess the general quality of the solutions they provide, and the runtime costs. You should review the Overview section before reading this question. In order to quantify the quality of a single script s for target t, we’ll measure the relative error: err(s, t) = f(s, t) t This makes use of the objective function for the problem, but the error function is not part of the problem; it’s part of the analysis. To evaluate the quality of a search algorithm, we apply the algorithm to a collection of examples, and measure the average quality. One measure of average quality is called Root Mean Square Error. It’s calculated as follows: RMSE = sPN i=1 (err(si , ti))2 N where ti is the target for the ith example problem, si is a solution to the ith example problem, and N is the number of example problems. You’ll recognize the err function from above. You’re basically calculating the squared error for each example in the le, adding it all up, dividing to get an average square error, and then the square root. Using the square of the error emphasizes large errors, and prevents negative errors and positive errors from cancelling each other. On Moodle, you’ll nd two data les for this question, containing a number of problem instances, one per line. The target value T is the rst value on the line, a oating point value, and then a sequence of integers, which is the list L. Run your search algorithms on all the problems in both les, and produce the following table (one for each le): Strategy RMSE Ave Time Random Guessing Random Search Hill-climbing Stochastic Hill-climbing Random-Restart Hill-climbing (50 × 20) Random-Restart Hill-climbing (10 × 100) Limit your search to 1000 steps. In the case of Random-Restart, try two variations: 1. 50 restarts; limit each hill-climbing attempt to 20 steps (50 × 20 = 1000). 2. 10 restarts; limit each hill-climbing attempt to 100 steps (10 × 100 = 1000). Page 11 Answer the following questions about your results: 1. Which algorithm had the lowest RMSE? 2. Did random guessing work well? Explain why (or why not)? 3. Compare the two variations of Random-restart Hill-climbing. Is it better to have lots of short runs, or fewer long runs? 4. Do you think the RMSE would get bigger or smaller as the length of L increases? What to Hand In • A le named a2q6_EXECUTION.txt containing brief instructions for compiling and/or running your code. See page 1. • A le named a2q6.txt containing the tables required, and your answers to the questions above. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a2q6.LANG containing your implementation of the search algorithms. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. You may submit multiple les, provided that the lenames begin with a2q6_ Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 8 marks: Your two tables are plausible results from executing the search algorithms. • 12 marks: Your answers to the questions demonstrate understanding of the issues and concepts. Page 12 Extra work for the ambitious 1. Implement the Simulated Annealing search strategy, and demonstrate that your implementation works. Add a row to the table from Question 6 giving your results. 2. Implement the Genetic Algorithm search strategy, and demonstrate that your implementation works. Add a row to the table from Question 6 giving your results. Page 13
Overview In this assignment we’ll explore the ideas in AIMA Chapter 3 using a problem de ned as follows. Inverse Arithmetic Problem . You are given a nite list of integers, L, and a target integer, T. The problem is to determine an integer arithmetic expression E, using some or all of the integers in L, so that if E is evaluated according to the rules of integer arithmetic, the answer is T. Integer expressions will be constructed using only the operations +, −, ×, and integer division / (integer division means we ignore the remainder, and use only the quotient, e.g. 5/2 = 2). For example, the given information could be as follows: • L = [1, 2, 3, 4, 5, 7] • T = 47 There are several possible expressions we can construct: • ((2 × 4) × 5) + 7 • ((3 + 4) × 7) − 2 • (7 × 7) − 2 • (3 × 4) + (5 × 7) For pragmatic reasons, we will look for linear expressions only, e.g., ((2×4)×5)+7, and we will not be trying to nd non-linear expressions like (3 × 4) + (5 × 7). Restricting the shape makes your job easier, and including non-linear expressions does not increase the insight you gain from this exercise. For this assignment, assume that each value from L can be used at most once, but the operators can be used as many times as you need. We’re interested in nding the expression that uses the fewest operations. Most problems will not have a single unique shortest expressions, and almost all problems will have many much longer expressions. Programming You’ll have to do some programming here, and I’ll provide strong guidance about how to get things organized. You can use any programming language you like, as long as it’s Python, Java, or C/C++. If you want to use a dierent language, please let me know before proceeding. The arithmetic expressions are probably best represented by text strings. In Python, you have access to the function eval(), which is quite powerful, but we can use it to calculate the value of any expression represented as a string. If you’re using Java, you are permitted to use a third-party library to evaluate expression strings; there are a few I found by Googling. You’ll also be running your programs on a collection of examples. You’ll be expected to report on aspects of this exercise. Execution instructions The markers may or may not wish to run your program, to verify your results. To help them, you should provide brief instructions on what to do to get your program running. Include: • Programming language used (including version, e.g., Java 8 or Python 3) • A simple example of compiling and/or running the code from a UNIX shell would be best. Keep it brief, and name it with the question number as the following example: a1q2_EXECUTION.txt. If your assignment uses third party libraries, they have to be included in your submission.Question 1 (10 points): Purpose: To practice specifying problems, and to lay the groundwork for later questions. Degree of Di culty: Easy AIMA Chapter(s): 3.1, 3.2 Specify the problem. De ne: 1. The initial state. 2. The goal state. 3. The actions that can be applied to a given state. 4. The result of applying an action to a given state. 5. The path cost. You should draw at least a portion of the problem space de ned by the initial state and the actions in the speci cation, just to get a sense of what you’re dealing with. But you don’t need to hand your drawing in. Implement your speci cation using your programming language of choice. In particular, implement: 1. Problem State class 2. Problem class Be sure to test your implementations thoroughly. What to Hand In • A le named a1q1.txt containing your de nitions. • A le named a1q1.LANG containing your implementation. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. If you have more than one le to submit, you should use a1q1_ to pre x your lenames. Be sure to include your name, NSID, student number, and course number at the top of all documents.Evaluation • 5 marks: You de ned the initial state, the goal state, the actions, and results, and the path cost. Your le a1q1.txt describes: – The components of the data structure (or class) that stores the problem state. – The method is_goal(). – The method actions(), and how you represented your actions. – The method result(). – The path cost of sequences of actions (or sequences of states). You may copy/paste block comments from your source code, if you’ve documented it well. Pointform is ne. Full marks will be given if the description is short, and if it is complete. • 3 marks: Your implementation follows the suggested interface guidelines. Speci cally: – You have a function or method is_goal(state) that returns a Boolean. – You have a function or method actions(state) that returns a list of actions. – You have a function or method result(state, action) that returns a new state. • 2 marks: Your implementation is well-documented. Speci cally: – Every function or method has at least a brief description of its purpose. – Your name, NSID, and student number are in the le.Question 2 (10 points): Purpose: To build and apply uninformed search algorithms to the problem. Degree of Di culty: Moderate AIMA Chapter(s): 3.3, 3.4 Using the guidelines provided in the textbook, and in lectures 03 and 04, implement TreeSearch, with the following search strategies: • Breadth- rst • Depth- rst • Depth-limited • Iterative-deepening Remember that the rst two strategies dier only in the Frontier ADT implementation (queue, stack). Depthlimited search discards search nodes that exceed the depth-limit; iterative-deepening calls depth-limited search with increasing depth limits until a solution is found. Test your algorithms by applying them to the example problems found in the le simple_examples.txt. Question 5 gets you to put your algorithms to a more intensive test. Each line in the example les gives a target followed by the list of integers (separated by spaces). Demonstrate by copy/paste from your output that your program generates solutions to a few interesting problems, showing that the expression returned does evaluate to the target. What to Hand In • A le named a1q2_EXECUTION.txt containing brief instructions for compiling and/or running your code. See page 1. • A le named a1q2.txt containing a demonstration of the output of your program, which is copy/paste from a console, or output le. You only need to show a few examples for each search strategy. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a1q2.LANG containing your implementation of the search algorithms. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. You may submit multiple les, provided that the lenames begin with a1q2_ Be sure to include your name, NSID, student number, and course number at the top of all documents.Evaluation • 2 marks: Your le a1q2.txt contains a few examples of output from your program. • 4 marks: Your implementation follows the suggested interface guidelines. Speci cally: – You implemented tree search with a FIFO queue, i.e., breadth- rst search. – You implemented tree search with a LIFO queue, i.e., depth- rst search. – You implemented a version of depth- rst search that limits the depth of search , i.e., depth-limited search. – You implemented iterative-deepening search using repeated calls to a depth-limited search. The implementations may be separate functions, or they can be implemented by reusing a generalized treesearch algorithm. • 2 marks: Your treesearch algorithm(s) use the methods is_goal(), actions(), and result() to interface with the Problem class. • 2 marks: Your implementation is well-documented. Speci cally: – Every function or method has at least a brief description of its purpose. – Your name, NSID, and student number are in the le.Question 3 (10 points): Purpose: To practice the design of heuristic evaluation functions for informed search. Degree of Di culty: Moderate AIMA Chapter(s): 3.5, 3.6 Recall that a heuristic evaluation function is a measure attached to a given problem state; this measure estimates the cost of the path from the problem state to the goal state. In the text, it’s represented by the function h(n), where confusingly n is a search node containing a problem state. Recall also the lesson in AIMA Chapter 3, which is that one way to derive a heuristic function is to relax one or more constraints in the problem, and use the true future cost in the relaxed problem as an estimate for the future cost in the problem you’re trying to solve. Design a heuristic for the Inverse Arithmetic Problem. Give pseudo-code for calculating it, based on your problem state, and the goal state. In your description, explain how your function comes from a relaxed problem, and give two distinct examples of the heuristic evaluation function applied to a few simple problem states. Address the question of whether or not your heuristic function is admissible. Notes: • It’s more fun if your heuristic is good, but it doesn’t have to be good to get full marks. Make sure you can make a case that it estimates cost to goal, even if not very well. • You are not required to nd an admissible heuristic, but you need to know whether it is or not! What to Hand In • A le named a1q3.txt containing a brief description of your heuristic evaluation function, mentioning the points described above. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 2 marks: Your description is clear and generally well-written. • 3 marks: Your pseudocode description gives a clear picture of the heuristic function. • 2 marks: You gave at least two examples of the heuristic function to real problem states. • 3 marks: You addressed the question of admissibility clearly demonstrating that you understand the concept. It does not matter if your heuristic function is or is not admissible; just be sure you know which! Question 4 (10 points): Purpose: To build and apply informed search algorithms to the problem. Degree of Di culty: Easy AIMA Chapter(s): 3.5 Using the guidelines provided in the textbook, and in lecture, implement TreeSearch, with the following search strategies: • Uniform-cost search (UCS) • Greedy best- rst search (GBFS) • A ∗ Search Remember that these three strategies dier only the measure that the frontier ADT uses to organize the search nodes. UCS uses g(n) only; GBFS uses h(n) only; A∗ uses g(n) + h(n); here, g(n) is the path cost from the initial state to the state contained in node n, and h(n) is your heuristic evaluation function from the previous question. Test your algorithms by applying them to the example problems found in the le simple_examples.txt. Each line in the example les gives a target followed by the list of integers (separated by spaces). Demonstrate by copy/paste from your output that your program generates solutions to a few interesting problems, showing that the expression returned does evaluate to the target. What to Hand In • A le named a1q4_EXECUTION.txt containing brief instructions for compiling and/or running your code. See page 1. • A le named a1q4.txt containing a demonstration of the output of your program, which is copy/paste from a console, or output le. You only need to show a few examples for each search strategy. If this le is missing, the marker will assume your implementation is incomplete or not working. • A le named a1q4.LANG containing your implementation of the search algorithms. Use the le extension appropriate for your choice of programming language, e.g., .py or .java. You may submit multiple les, provided that they lenames begin with a1q4_ Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 2 marks: Your le a1q4.txt contains a few examples of output from your program. • 4 marks: Your implementation follows the suggested interface guidelines. Speci cally: – You implemented tree search with a priority queue. – You implemented UCS using treesearch with a priority queue, taking path-cost g(n) to order the priority queue. – You implemented UCS using treesearch with a priority queue, taking estimated cost to goal h(n) to order the priority queue. – You implemented UCS using treesearch with a priority queue, taking estimated solution cost f(n) = g(n) + h(n) to order the priority queue. The implementations may be separate functions, or they can be implemented by reusing a generalized treesearch algorithm. • 2 marks: Your treesearch algorithm(s) use the methods is_goal(), actions(), and result() to interface with the Problem class. • 2 marks: Your implementation is well-documented. Speci cally: – Every function or method has at least a brief description of its purpose. – Your name, NSID, and student number are in the le.Question 5 (10 points): Purpose: To apply your algorithms to more di cult problems, and draw conclusions from the results. Degree of Di culty: Moderate AIMA Chapter(s): 3 (all) In the les moderate_examples.txt and harder_examples.txt you’ll nd problems that should challenge some of your implementations, and will give you an idea about how well your heuristic evaluation function (Question 3) works. Run your algorithms (uninformed and informed) on these problems to gauge the quality of your implementations. Give a report on what you found. You might discuss all or any of the following criteria for empirical evaluation: • Which algorithms used the most time to solve the problems? • Which algorithms used the most memory to solve the problems? • How often did your algorithms nd an optimal solution? • Did any algorithms run so long that you terminated them before they returned an answer? If so, which algorithms did you terminate most frequently? To answer this question, you could consider any of the following modi cations to your search algorithms: • Add code to time the search. Use a clock twice: just before starting the search loop, and just before you return a solution. • Add a time threshold to your search algorithms, to terminate long-running searches. Set the threshold to short values until you are sure everything is working, and then set it longer to collect your data. • Count the number of nodes that your search generates, and the maximum size of your frontier over the course of solving a single problem. Both of these statistics can be insightful! • Don’t calculate average times (or memory) across the set of problems. An average isn’t really meaningful here, because the variation in problem di culty is too high. Instead, count the number of times one algorithm is faster than another, and by how much. • How well does your heuristic function from Question 3 work, compared to uninformed algorithms? Comment on your ndings. Include tables, plots, etc to support your ndings. What to Hand In • A le named a1q5.txt (other formats, DOC, DOCX, PDF, are acceptable) containing a discussion of your ndings in this question. Be sure to include your name, NSID, student number, and course number at the top of all documents.Evaluation • 5 marks: Your description is clear and generally well-written. • 5 marks: Your description is based on data (tables, plots), and not simply vague impressions you obtained while coding. – You summarized the behaviour of the dierent uninformed and informed search strategies on the collections of example problems provided. – Your summary mentioned issues related to completeness, optimality, as well as performance in terms of time (clock, or nodes expanded), and memory (maximum size of the frontier). – Your description included a discussion of the quality of your heuristic function from Question 3, by comparing your informed results to the uninformed results.Extra work for the ambitious 1. Implement the GraphSearch algorithm, and compare your results to the TreeSearch algorithm results. 2. Drop the assumption that a number can be used at most once. Ask Mike for example problems that are created by allowing multiple uses of some numbers. Compare your results to the other variation.
Overview The N-Queens problem is to put N Queens on a board (N × N) so that no queen attacks any other queen. (A queen can attack any square on the same row, same column, or same diagonal.) The following is a diagram of a game state with 2 queens on the board: Q Q We will make a 2-player game of the N-Queens problem as follows: Players alternate putting a piece on the board, and can only place a queen on a square that is not being attacked, i.e., there is no queen already on the board in the same row or column or diagonal. In the N-Queens game, the objective is to be the last player to have a legal place to put a queen. We will work with two variations of this game, which dier in 2 aspects: how players can play, and how the score is counted. Variation 1a The players must place a queen on the left-most unoccupied column: Player 1 plays on Column 1, Player 2 on Column 2, Player 1 on Column 3, etc). For example, in the above diagram, it’s Player 1’s turn to move, and Player 1 must place a queen somewhere in column 3 (counting from the left, starting at 1). The winner is the last player to put a queen on the board. For example, if it’s Player 1’s turn to play in Column 5, but all squares in Column 5 are being attacked, then Player 1 loses, and Player 2 wins. The utility function would return 1 for a win for Player 1, or -1 for a win for Player 2. For example, Player 1 can place a queen in the above position, but Player 2 would be unable to play after that, so Player 1 would be the winner. There are no draws. Note: If all N queens are on the board, then the last player to move is the winner: if N is even, then Player 2 wins, and the utility is 1 −1, and if odd, Player 1 wins, and the utility is −1 1.There are no draws. Variation 1b This variation is identical to Variation 1a, except for the score of the game. The utility value is calculated by counting how many queens are on the board at the end of a game: if there are k queens on the board, and it’s a win for Player 1, the utility is k (positive, odd number); if there are k queens on the board, and it’s a win for Player 2, the utility is −k (negative, even number). For example, the win for Player 1 (after playing one more queen on the board position above) counts for 3. There are no draws. Note: If all N queens are on the board, then the last player to move is the winner: if N is even, then Player 2 wins, and the utility is −N, and if odd, Player 1 wins, and the utility is N. Notes • The purpose of this assignment is not to implement a real game, but to understand the game-tree search algorithms. • These variations are games, but may not be interesting games to play as humans. • Some of the variations of this game may not seem fair or balanced, and that’s okay for our work. • For N < 3, the game is quite boring. • Draw out the game trees for N ≤ 4 before you start coding. You’ll need these trees to debug your code.Programming As in previous assignments, it’s advisable to separate the game-speci c code from the game-search code. The interface between your game-search code and your game-speci c code is as follows: • is_terminal(state): returns a Boolean, True if the given state has no more legal moves. • utility(state): returns a numeric value. The state must be a terminal state. • actions(state): returns a list of actions (i.e., moves) that are legal in the given state. The function needs to examine the state to determine whose turn it is to move. • result(state, action): returns a new game state which is the result of taking the given action in the given state. • Optional: is_maxs_turn(state): Returns a Boolean value, True if it’s Player 1’s turn (Max) in the given state. • Optional: is_mins_turn(state): Returns a Boolean value, True if it’s Player 2’s turn (Min) in the given state. Implementing the optional methods may not be necessary for all the questions, though it would be useful if you wanted to play the game interactively. We saw the use of these optional functions in Lecture 18. None of the coding is di cult, though nding a bug may be di cult. As always, you should write enough tests for your methods and functions that you can debug them using a test script. Debugging a whole application is more of a waste of your time than writing a test script. You’ll be developing a code base throughout this assignment, and we only want to see it once to grade it. Each question will ask you to hand in a script that performs a task; this script can import the code you’re developing, but don’t hand everything in multiple times. Execution instructions The markers may or may not wish to run your program, to verify your results. To help them, you should provide brief instructions on what to do to get your program running. Include: • Programming language used (including version, e.g., Java 8 or Python 3) • A simple example of compiling and/or running the code from a UNIX shell would be best. Keep it brief, and name it with the question number as the following example: a4q1_EXECUTION.txt. If your assignment uses third party libraries, they have to be included in your submission. Clari cation: You’ll submit one le documenting the execution instructions for all your scripts. Clari cation: What to Hand in instructions The rst version of this assignment required separate hand in les for questions 1-7,9. This pushes against Moodle’s very hard limit of 20 les maximum. To remedy this, the new requirements collect the requirements for these questions into 2 les: • A4_output.txt will contain tables output from your scripts for questions 1-7,9. Please mark each Question’s output clearly, so markers can easily identify which data belongs to which question. • A4_EXECUTION.txt will contain execution instructions for all your scripts for questions 1-7,9. Please mark each Question’s information clearly, so markers can easily identify which information belongs to which question. You should not hand in separate output and execution instructions!Question 1 (4 points): Purpose: To implement Minimax Search for Variation 1a. Degree of Di culty: Moderate. Minimax is easy; the game will be the only tricky part. Textbook: AIMA Chapter 5.1, 5.2 Implement Minimax search (with no bells or whistles) and apply it to Variation 1a, for game sizes N ∈ {1, · · · , 10}. Speci cally, write a loop to display the following table: Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 3.72e-05 2 1 (’X’, 0) 6.52e-05 3 1 (’X’, 1) 0.0001642 4 -1 (’X’, 0) 0.000388 . . . . . . . . . . . . Clari cation: In the above output, which is literally copy/paste from my computer, the Best Opening Move is represented by a pair (WHO, ROW); in my implementation, I used the symbol ’X’ to represent player 1 (answering WHO), and for ROW, I give an integer value. There is no need to imitate my output, as long as it’s clear. Your output should go all the way up to 10 (or 11, if that amuses you). Your output should have the correct Minimax values, though there may be more than one opening move to achieve that value; it does not matter which of the equally good opening moves your script returns. Your times will vary, but reasonably you should expect your implementation to take only a few seconds at most. Try a few larger sizes, e.g. N = 11, 12, and observe the exponential nature of the search problem (again). What to Hand In • A le named a4q1.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q1.LANG containing a script/app which, if executed, would produce the output submitted in a4q1.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q1_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary. • Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this le. Do not submit your entire codebase multiple times. Your script/app a4q1.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Clari cation: You’ll be developing your code-base as you work on Questions 1-9. You will hand in your whole code base in Question 10. Your script for Question 1 will import modules/classes/libraries from (or include, or compile with) your code base, of course! But you don’t need to hand in the game code or the search code in Question 1. Just hand in the script that creates the data above. When the marker runs your script, it should import or compile with the code you submit in Question 10. Be sure to include your name, NSID, student number, and course number at the top of all documents. Page 4 Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q1. • 1 mark: Your le a4q1.LANG contains a script/app that produces the output in A4_output.txt.Question 2 (4 points): Purpose: To implement Minimax Search for Variation 1b. Degree of Di culty: Easy. Minimax is done already; you have to modify the utility function for the new variation. Textbook: AIMA Chapter 5.1, 5.2 Implement Minimax search (with no bells or whistles) and apply it to Variation 1b, for game sizes N ∈ {1, · · · , 10}. Speci cally, write a loop to display the following table: Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 5.70e-05 2 1 (’X’, 0) 4.91e-05 3 1 (’X’, 1) 8.61e-05 4 -2 (’X’, 0) 0.000281 . . . . . . . . . . . . Your output should go all the way up to 10 (or 11, if that amuses you). Your output should have the correct Minimax values, though there may be more than one opening move to achieve that value; it does not matter which of the equally good opening moves your script returns. Your times will vary, but reasonably you should expect your implementation to take only a few seconds at most. Try a few larger sizes, e.g. N = 11, 12, and observe the exponential nature of the search problem (again). What to Hand In • A le named a4q2.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q2.LANG containing a script/app which, if executed, would produce the output submitted in a4q2.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q2_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary. • Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information. Do not submit your entire codebase multiple times. Your script/app a4q2.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q2. • 1 mark: Your le a4q2.LANG contains a script/app that produces the output in A4_output.txt. Question 3 (4 points): Purpose: To implement Minimax Search with Alpha-Beta Pruning for Variation 1a. Degree of Di culty: Moderate. Your implementation of Variation 1a is done; you have to implement AlphaBeta pruning. Textbook: AIMA Chapter 5.3 Implement Minimax Search with Alpha-Beta Pruning and apply it to Variation 1a, for game sizes N ∈ {1, · · · , 10}. Speci cally, write a loop to display the following table: Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 3.60e-05 2 1 (’X’, 0) 3.98e-05 3 1 (’X’, 1) 8.51e-05 4 -1 (’X’, 0) 0.000322 . . . . . . . . . . . . Your output should have the the same Minimax values as Question 2, though there may be more than one opening move to achieve that value; it does not matter which of the equally good opening moves your script returns. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N. Try a few larger sizes, e.g. N = 11, 12, and observe the exponential nature of the search problem (again). What to Hand In • A le named a4q3.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q3.LANG containing a script/app which, if executed, would produce the output submitted in a4q3.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q3_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary. • Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information. Do not submit your entire codebase multiple times. Your script/app a4q3.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q3. • 1 mark: Your le a4q3.LANG contains a script/app that produces the output in A4_output.txt.Question 4 (4 points): Purpose: To implement Minimax Search with Alpha-Beta Pruning for Variation 1b. Degree of Di culty: Moderate. Your implementation of Variation 1b is done; you have to implement AlphaBeta pruning. Textbook: AIMA Chapter 5.3 Implement Minimax Search with Alpha-Beta Pruning and apply it to Variation 1b, for game sizes N ∈ {1, · · · , 10}. Speci cally, write a loop to display the following table: Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 3.60e-05 2 1 (’X’, 0) 3.98e-05 3 1 (’X’, 1) 8.51e-05 4 -2 (’X’, 0) 0.000322 . . . . . . . . . . . . Your output should have the the same Minimax values as Question 3, though there may be more than one opening move to achieve that value; it does not matter which of the equally good opening moves your script returns. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N. Try a few larger sizes, e.g. N = 11, 12, and observe the exponential nature of the search problem (again). What to Hand In • A le named a4q4.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q4.LANG containing a script/app which, if executed, would produce the output submitted in a4q4.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q4_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary. • Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information. Do not submit your entire codebase multiple times. Your script/app a4q4.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q4. • 1 mark: Your le a4q4.LANG contains a script/app that produces the output in A4_output.txt.Question 5 (4 points): Purpose: To implement a depth-cuto and a heuristic evaluation function for Minimax Search, to allow play in Variation 1a larger than N = 10. Degree of Di culty: Easy. You have to modify your search algorithm, using the interface for imperfect real-time decisions. Textbook Chapter: AIMA 5.4 Implement a depth-cuto and heuristic evaluation function for Variation 1a. Apply your implementation with a cut-o at depth 4, for game sizes N ∈ {1, · · · , 20}. Speci cally, write a loop to display the following table: Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 3.60e-05 2 1 (’X’, 0) 8.92e-05 3 1 (’X’, 1) 0.000143 4 -1 (’X’, 0) 0.000280 . . . . . . . . . . . . Since the cut-o is at depth 4, the rst 4 rows in your output should have correct minimax values; after that, the minimax values will re ect your evaluation function, and probably won’t be optimal. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N. In particular, you should expect to run all examples in a few seconds at most. Additional functions for your interface. The textbook recommends that you 1. Replace your test for a terminal state with a function that determines whether to cut o search. 2. Replace the utility function with a function that estimates utility for any given state. I recommend otherwise! Add two new methods/functions to your Variations, as follows: • cutoff_test(state, depth): returns a Boolean, True if the search should be terminated at this state and depth. • eval(state): returns an estimate of the Minimax value of the given state. By introducing these two new functions into the interface, your search algorithms need to be modi ed as well. Use the cuto test and the evaluation function in combination, but only check for the cut-o after you’ve determined that the state is not an actual terminal state. This arrangement adds a few lines to the search algorithms, but helps keep your utility and estimated minimax functions independent, which is good for development. The heuristic evaluation function. Such a function might be di cult to invent for this game. You are welcome to try. You should remember that your estimate should return a value in the range of your utility function; a con dent estimate should be close to the true minimax value, and you can express uncertainty by producing estimates that are between the extremes, perhaps using fractional ( oating point) estimates within the range. Alternatively, your evaluation function can return a random utility value. This is easy to start with, in any case.What to Hand In • A le named a4q5.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q5.LANG containing a script/app which, if executed, would produce the output submitted in a4q5.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q5_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary. • Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this le. Do not submit your entire codebase multiple times. Your script/app a4q5.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q5. • 1 mark: Your le a4q5.LANG contains a script/app that produces the output in A4_output.txt.Question 6 (4 points): Purpose: To implement a depth-cuto and a heuristic evaluation function for Minimax Search, to allow play in Variation 1b larger than N = 10. Degree of Di culty: Easy. You have to implement a cuto and evaluation function for Variation 1b. Your changes to Minimax from Question 5 should already be nished. Textbook Chapter: AIMA 5.4 Implement a depth-cuto and heuristic evaluation function for Variation 1b. Apply your implementation with a cut-o at depth 4, for game sizes N ∈ {1, · · · , 20}. Speci cally, write a loop to display the following table: Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 4.70e-05 2 1 (’X’, 0) 3.89e-05 3 1 (’X’, 1) 8.30e-05 4 -2 (’X’, 0) 0.000338 . . . . . . . . . . . . Since the cut-o is at depth 4, the rst 4 rows in your output should have correct minimax values; after that, the minimax values will re ect your evaluation function, and probably won’t be optimal. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N. In particular, you should expect to run all examples in a few seconds at most. The notes about the interface, and the evaluation function, from Question 5, apply here as well. If you’ve adopted a good design, you may only need to over-ride the evaluation function from Question 5. What to Hand In • A le named a4q6.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q6.LANG containing a script/app which, if executed, would produce the output submitted in a4q6.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q6_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary. • Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this le. Do not submit your entire codebase multiple times. Your script/app a4q6.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Be sure to include your name, NSID, student number, and course number at the top of all documents.Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q6. • 1 mark: Your le a4q6.LANG contains a script/app that produces the output in A4_output.txt. Page 12 Department of Computer ScienceQuestion 7 (4 points): Purpose: To implement a depth-cuto and a heuristic evaluation function for Minimax Search with AlphaBeta pruning, to allow play in games larger than N = 10. Degree of Di culty: Easy. You’ll need to adapt your Alpha-Beta search algorithm similar to the way you adapted Minimax in Question 5. Textbook Chapter: AIMA 5.4 Adapt your Alpha-Beta search algorithm from Q4 similar to the way you adapted Minimax in Question 5. Apply your implementation with a cut-o at depth 4, for game sizes N ∈ {1, · · · , 20}. Speci cally, write a loop to display the following tables: Variation 1a Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 3.41e-05 2 1 (’X’, 0) 3.81e-05 3 1 (’X’, 1) 0.000106 4 -1 (’X’, 0) 0.000440 . . . . . . . . . . . . Variation 1b Size Minimax Value Best Opening Move Time in Seconds 1 1 (’X’, 0) 4.70e-05 2 1 (’X’, 0) 3.89e-05 3 1 (’X’, 1) 8.30e-05 4 -2 (’X’, 0) 0.000338 . . . . . . . . . . . . Since the cut-o is at depth 4, the rst 4 rows in your output should have correct minimax values; after that, the minimax values will re ect your evaluation function, and probably won’t be optimal. Your times will vary, but reasonably you should expect your implementation to take less time than for Question 2, especially for larger values of N. In particular, you should expect to run all examples in a few seconds at most. The notes about the interface, and the evaluation function, from Question 5, apply here as well. If you’ve adopted a good design, you may only need to over-ride the evaluation function from Question 5. What to Hand In • A le named a4q7.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q7.LANG containing a script/app which, if executed, would produce the output submitted in a4q7.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q7_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary.• Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this le. Do not submit your entire codebase multiple times. Your script/app a4q7.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q7. • 1 mark: Your le a4q7.LANG contains a script/app that produces the output in A4_output.txt. Page 14 Question 8 (10 points): Purpose: To compare the output gathered in the previous questions. Degree of Di culty: Easy. You’ll need to understand why the output is the way it is. Textbook Chapter: AIMA 5.1-4 Answer the following questions with a brief comment for each. 1. Compare the Minimax values for A4Q1 and A4Q2. The minimax value used a dierent scale (-1,1) versus a count of the number of queens, but did this change which player won the game? 2. Compare the runtimes for A4Q1 and A4Q2. Which variation seemed to be faster? Explain why. 3. Compare the Minimax values for A4Q1 and A4Q3. Were they the same? 4. Compare the runtimes for A4Q1 and A4Q3. How much faster was the search, for games with larger N? 5. Compare the Minimax values for A4Q2 and A4Q4. Were they the same? 6. Compare the runtimes for A4Q2 and A4Q4. How much faster was the search, for games with larger N? 7. Compare the Minimax values for A4Q1 and A4Q5. Were they the same? Explain. 8. Compare the runtimes for A4Q1 and A4Q5. How much faster was the search, for games with larger N? 9. Compare the Minimax values for A4Q5 and A4Q6 (Minimax with cut-o, two variations) with the results from A4Q7 (Alpha-Beta with cut-o, two variations). Were they the same? Explain. 10. Compare the runtimes for A4Q5 and A4Q6 (Minimax with cut-o, two variations) with the results from A4Q7 (Alpha-Beta with cut-o, two variations). How much faster was the search, for games with larger N? None of these questions is di cult. This is more about requiring you to consider what you’ve done, than it is about understanding anything deep or complex. What to Hand In • A le named a4q8.txt containing your comments to the above questions. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 10 marks: Your le a4q8.txt contains plausible responses to the above questions. Page 15 Question 9 (6 points): Purpose: To implement an interactive script/application that plays N-Queens. Degree of Di culty: Moderate. You’ll need to return actions, not just values, and you’ll need to distinguish between the scripts that plan moves for a single player (Q1-6), and scripts that take turns making moves in a real game. Textbook Chapter: AIMA 5.1-4 This is the fun part. Implement an interactive script/application that plays N-Queens. Make use of your implementations from the previous questions. Make sure you understand the dierence between what the search algorithms are doing (planning a single choice), and what you need to do here (allow two planning agents to take turns making moves). You might start by implementing human vs. computer (or computer vs. human), so that you can gure things out, then replace the human player with the computer. You should allow each player to use its own search algorithm, so you could play (plain) Minimax against Alpha-Beta, using equal depth cutos, or dierent depth cutos. You can model a weak player using a shallower cuto, and a stronger player using a deeper cuto. Play around with the cutos, so that the rst few moves of the game do not take longer than a minute or so (shorter is better for experimentation though). Try the following scenarios: 1. Try N = 10, equal cut-o value 4. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4). 2. Try N = 10, equal cut-o value 5. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4). Were these the same as when the cuto was 4? 3. Try N = 10, Player 1 cut-o 5, Player 2 cut-o 3. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4). Did the deeper cuto result in better decisions? 4. Try N = 10, Player 1 cut-o 3, Player 2 cut-o 5. Compare the outcome of your games with the known Minimax values (as you determined in Q1-Q4). Did the deeper cuto result in better decisions? 5. Repeat the above scenarios with N = 20. If you are using a random evaluation function, be sure to run each scenario a number of times (you don’t want to draw a conclusion about random eects based on one example)! If you are using a deterministic evaluation function, then there is no point to repeat the scenarios more than once. Report your results in a tabular format, e.g.: N Cut-o P1 Cut-o P2 Win/Loss P1 10 4 4 7W, 3L 10 3 5 2W, 8L . . . . . . . . . . . . Page 16 What to Hand In • A le named a4q9.txt containing your table, as above. • Revised: Your table, and any accompanying explanation, in your le A4_output.txt, which is a single le that will contain your output for all questions. Be sure to mark clearly the question number as you add information to this le. • A le named a4q9.LANG containing a script/app which, if executed, would produce the output submitted in a4q9.txt (except the timing information which will dier). Use the le extension appropriate for your choice of programming language, e.g., .py or .java. • A le named a4q9_EXECUTION.txt containing execution instructions for markers to run your script/app if they deem it necessary. • Revised: Execution instructions for markers to run your script/app if they deem it necessary, clearly presented in a the le A4_EXECUTION.txt, which is a single le that will contain your execution instructions for all questions. Be sure to mark clearly the question number as you add information to this le. Do not submit your entire codebase multiple times. Your script/app a4q9.LANG should run correctly, but it should not contain code for Minimax search, and should not contain the code for your implementation of Variation 1a (or any others). Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation Revised: • 3 marks: Your le A4_output.txt contains the required table, with correct Minimax values, and plausible times, clearly marked as a4q9. • 1 mark: Your le a4q9.LANG contains a script/app that produces the output in A4_output.txt. Page 17 Question 10 (16 points): Purpose: To obtain grades for your implementations. Degree of Di culty: Easy. Just make sure your code is well-documented, well-organized, and hand it in. Nothing new here! Textbook Chapter: AIMA 5.1-4 Hand in your code. All the scripts from the previous questions should be based on this code, by importing or compiling as necessary. All the scripts from previous questions must run using these les. Your code should be documented internally so that a reader can make sense of it. What to Hand In • Files named a4q10.LANG containing the code for your variations, and your search algorithms. If you have more than one le to submit (a good idea), you can name them appropriately, using a4q10 as a pre x. Do not submit your entire codebase multiple times. This is the only place where your variations and search algorithms are submitted. Be sure to include your name, NSID, student number, and course number at the top of all documents. Evaluation • 2 marks: Your implementation of Variation 1a includes functions/methods for the interfaces described throughout this assignment. • 2 marks: Your implementation of Variation 1a is well-documented. • 2 marks: Your implementation of Variation 1b includes functions/methods for the interfaces described throughout this assignment. • 2 marks: Your implementation of Variation 1b is well-documented. • 2 marks: Your implementation of Minimax Search makes use of the interface described through the assignment. • 2 marks: Your implementation of Minimax Search is well-documented. • 2 marks: Your implementation of Minimax Search with Alpha-Beta Pruning makes use of the interface described through the assignment. • 2 marks: Your implementation of Minimax Search with Alpha-Beta Pruning is well-documented. Page 18 Work for the ambitious We worked with two variations of the N-Queens game. There is a third, which I removed from the assignment. In Variation 2, the players are not restricted in their choice of column, but can play a queen in any rowcolumn position, so long as it is not currently attacked by any other queen already on the board. For example, in the above diagram, it’s Player 1’s turn to move, and Player 1 can place a queen in either of the two unoccupied columns. The winner is the last player to put a queen on the board. The utility function would return 1 for a win for Player 1, or -1 for a win for Player 2. There are no draws. Implement this variation, and try out your search algorithms on it. The branching factor is much higher, and moves are more strategic. This variation is a good opportunity to employ a transposition table, which stores board positions and utility values so that if the board position appears more than once in a search, the full search is not repeated. Use a hash table! Page 19
In this assignment you will analyze food webs. In order to do this you will need to load a description of predator-prey relationships from a file, store them in a data structure, and identify the relationships between the organisms.Predator-Prey File Format The predator prey information is stored in CSV (comma separated value) files. Each line in the file will be of the form ,,,…, where and are placeholders for specific animals. Each line will always begin with exactly one predator, followed by 1 or more prey.For example, lines in the file could be Whelk,Limpets,Mussels or Lion,Zebra. Note the predator and prey names may include a mixture of upper and lowercase letters, and may also include spaces. In order to make the files easier to work with you can assume that there will not be any spaces immediately before or after any of the commas.Your first task is to list everything that each predator eats on a single line with nice formatting. For example, if your file contains the line: Lion,Gazelle,Wildebeest ,Zebra then you should output a single line for Lion that reads Lion eats Gazelle, Wildebeest and Zebra Notice that commas appear after all items except the last and second last items, and that the word “and” appears between the last and second last items.You will be graded on correctly following this layout, but I have provided a module that includes a function that will do the formatting for you – all you need to do is import the function and call it. In order to complete this and subsequent tasks you must load all of the data from the food web file into a dictionary that describes the eats relationship.The keys in the dictionary will by the names of the predators. The values in the dictionary will be lists, where each element in the list is the name of a prey animal that the predator eats. The output for Part 1 for AquaticFoodWeb.txt should be: Predators and Prey: Bird eats Crab, Limpets, Mussels, Prawn and Whelk Crab eats Limpets and Mussels Fish eats Prawn Limpets eats Seaweed Lobster eats Crab, Limpets, Mussels and Whelk Mussels eats Phytoplankton and Zooplankton Prawn eats Zooplankton Whelk eats Limpets and Mussels Zooplankton eats PhytoplanktonNote: I have displayed my output in sorted order by using Python’s sorted function. However, the orders of the predators and prey aren’t important. You’ll receive full credit as long as all of the predators and their prey are identified successfully.We will define an apex predator to be any species in the food web that is not eaten by another organism. After displaying the predators and their prey your program should continue by displaying all of the apex predators with an appropriate heading.Hint: Apex predators are those animals that are keys in the dictionary that do not appear in any of the lists of animals eaten. The output for Part 2 for AquaticFoodWeb.txt should be: Apex Predators: Bird, Fish and LobsterWe will define a producer to be any species in the food web that does not eat another species. The output from your program should continue by displaying all of the producers with an appropriate heading. The output for Part 3 for AquaticFoodWeb.txt should be: Producers: Phytoplankton and SeaweedWe will define the most flexible eater as the organism that eats the greatest number of other organisms in the food web. Identify and display all of the most flexible eaters under an appropriate heading. The most flexible eaters in the aquatic food web are: Most Flexible Eaters: Bird Note: While the aquatic food web only has one most flexible eater, a food web may have several most flexible eaters that all eat the same number of organisms. When that situation occurs your program should display all of the most flexible eaters.We will define the tastiest organism as the member of the food web that is eaten by the most different members of the food chain. Identify and display all of the tastiest organisms under an appropriate heading. The tastiest organisms in the aquatic food web are: Tastiest: Limpets and Mussels Part 6: Determine the Height of Each Organism in the Food Web We will define the height of an organism as the longest path from that organism to a producer.Using this definition, all producers have height 0. Any animal that eats only producers has height 1. All other animals in the food web have a height which is one more than the animal they prey on with largest height value. The description of height above is recursive – it defines the height of a higher animal in terms of the height of a lower animal.As such, you may find yourself wanting to write a recursive function to assist you with determining the height of each animal in the food web. However, we will only cover recursion briefly in this course (if at all), and we will not discuss it until the final week of classes. As a result, if you choose to develop a recursive solution you should expect to do some independent study on recursion (Chapter 12 in the third or fourth edition of Starting Out with Python).If you don’t want to do some independent study on recursion then you can determine the heights of all the organisms in the food web using the following algorithm: set the heights of all organisms, including the producers, to 0 set changed to true while something has changed set changed to false for each animal, a, in the food web for each animal, p, that a preys on if the height of a is less than or equal to the height of p set the height of a to the height of p + 1 set changed to trueThe output for Part 4 for AquaticFoodWeb.txt should be: Heights: Bird: 4 Crab: 3 Fish: 3 Limpets: 1 Lobster: 4 Mussels: 2 Phytoplankton: 0 Prawn: 2 Seaweed: 0 Whelk: 3 Zooplankton: 1 Requirements • Your program must read the data file name as a command line argument. The food web file will be the first and only command line argument, appearing in sys.argv[1]. If no command line argument is provided then your program should read the name of the file from the user.If more than 1 command line argument is provided then your program should display an appropriate error message and quit. • Your program must perform basic error checking, such as ensuring that the file specified by the user exists. If an error is encountered while opening a file then your program should display an appropriate error message and exit.• You must store the predator-prey relationships in a dictionary where the keys are the predator names and the values are lists of prey eaten by each predator. • You must only read each file once. It is not acceptable to submit a solution that requires the file to be read several times to complete the analysis. • Close every file that you open. • Your program must make appropriate use of functions.Specifically, you should write one function for each part of the assignment for parts 2 through 6. (You can also write one or more functions for part 1 if you want to). Your solution will not receive full credit unless your code is divided into appropriate functions that make appropriate use of parameters and return values. A significant deduction will be made if your program is all in one function, even if it generates beautiful results.• The only lines of code in your program that should be outside of a function definition are constants (if any), import statements (if any) and the call to the main function (which is normally the last line in the file). • Do not define one function inside another function.• Your program must not use global variables (except for constant values that are never changed, and in this assignment you may not even find that you want any global constants). If you load some data inside a function then you must return it as a result so that it can be used in subsequent functions.• You may assume that the data in the files you are working with is correct. Once you open the file successfully you don’t need to worry about problems such as reading a number where a word is expected, a missing comma, a blank line, etc.• Your program must use good programming style. This includes things like appropriate variable names, good comments, minimizing the use of magic numbers, etc. Your program should begin with a comment that includes your name, student number, and a brief description of the program. Each function should begin with a comment that describes its purpose, parameters (if any) and return values (if any).• Break and continue are generally considered bad form. As a result, you are NOT allowed to use them when creating your solution to this assignment. In general, their use can be avoided by using a combination of if statements and writing better conditions on your while loops.Dealing with Command Line Parameter inside IDLE: If you are working in IDLE instead of directly from the command prompt, you might find yourself wondering how to provide command line parameters when running inside IDLE. Unfortunately IDLE doesn’t provide a good option for specifying command line parameters. Instead, the best strategy is probably to ‘fake it’ by adding the following line right after import sys: sys.argv = [“Assignment4.py”, “AquaticFoodWeb.txt”]This will overwrite whatever is in sys.argv with a list that has the name of your .py file as the first element and the name of the file that you want to process as your second element. You’ll need to take this out before you submit the assignment because your TA will run your submission from the command prompt, but you should be able to test all of the cases required for the assignment by changing the values in this list:• You can test different files (including files that don’t exist) by changing the second element in the list. • You can test the case where the user provides too many command line parameters by adding another element to the list. • You can test the case where the user doesn’t provide a command line parameter by removing the second element from the list. Hints: Develop an algorithm for Part 1 before trying to write the code. The algorithm should have “For each line in the file” as an outer loop, followed by a description of the steps that you are going to follow to process the line and get the predator and prey into the dictionary correctly.Then you’ll have a separate loop which will displays the relationships that you stored in the dictionary. Begin with Part 1 – all of the other parts rely on it. Don’t move on to the other parts until you have correct lists in Part 1. Parts 2 through 6 can be performed in any order.Part 4 is probably the easiest to complete. Part 6 is probably the most difficult. Having trouble formatting the output in Part 1? There’s a module on the course website that you can import to do the formatting for you. Looking for an A+? Identify the Herbivores, Omnivores and Carnivores: A herbivore is an animal that only eats plants. In this assignment, we will assume that all producers are plants and that all plants are producers.Display the herbivores under an appropriate heading. If there aren’t any herbivores then you should display the heading, followed by “(None)”. An omnivore is an animal that eats both plants and animals. Display the omnivores under an appropriate heading. If there aren’t any omnivores then you should display the heading, followed by “(None)”. A carnivore is an animal that only eats other animals. Display the carnivores under an appropriate heading.If there aren’t any carnivores then you should display the heading, followed by “(None)”. The herbivores, omnivores and carnivores for AquaticFoodWeb.txt are shown below: For an A+: Herbivores: Limpets and Zooplankton Omnivores: Mussels Carnivores: Bird, Crab, Fish, Lobster, Prawn and Whelk Grading: This assignment will be graded on a combination of functionality and style.A base grade will be determined from the general level of functionality of the program (Does it output the prey for each predator? Is it formatted correctly? Does it identify the apex predators and producers? Does it identify the most flexible eaters and the tastiest organisms?).The base grade will be recorded as a mark out of 12. Style will be graded on a subtractive scale from 0 to -3. For example, an assignment which receives a base grade of 12 (A), but has several stylistic problems resulting in a -2 adjustment will receive an overall grade of 10 (B+). Fractional grades will be rounded to the closest integer. Total Score (Out of 12) Letter Grade 12 A 11 A10 B+ 9 B 8 B7 C+ 6 C 5 C4 D+ 3 D 0-2 F
Taking photos of popular landmarks can be frustrating if one wants a picture that doesn’t have tourists in it. In fact, it often simply isn’t possible to get a shot without a person in it somewhere because of the number of visitors present at the sites. To solve this problem you are going to create a Python program that automatically removes tourists from photos so that only the landmark remains.You might have read the last sentence and thought “That’s impossible!”. While that might have been your initial reaction, the reality is that it can be achieved with the right input images. In particular, instead of just taking one picture of the landmark in question, one takes a series of images over some amount of time.During that time tourists come and go but the landmark stays in place. As a result, each pixel in the image will be a pixel from the landmark in most of the images and will only be a tourist in a few (or perhaps even none) of them.This means that the tourists can be eliminated by identifying the pixel color that is most common at each location in the image. While complex clustering techniques can be used to identify this color, we’ll simply compute the median of the red, green and blue components of all of the pixels at each location because doing so is reasonably straightforward and gives decent results.Three images of Delicate Arch (a very popular site in Arches National Park in Utah) are shown below. Notice that there are one or two people in each picture, but that they are in different locations in each image.Merging these images in the manner described previously generates the following result. In particular, notice that there are no tourists present in the result image because every pixel in the series of input images shows Delicate Arch in at least two of the three images. As a result, the median pixel is a pixel from Delicate Arch.This assignment is intended to teach you about functions and lists. As a result, you will provide the functionality described previously by writing 5 functions described in the following 3 sections. The starter code I have provided includes a main function that calls 3 of the functions that you will write, and empty implementations of those functions have also been provided.All of the data sets for this assignment consist of files named with an abbreviation that describes the subject of the photograph (such as “da” for Delicate Arch or “cb” for Capitol Building), followed by an underscore, an integer, a dot and the filename extension. The integers are sequential beginning with 1.The loadImages function will load all of the images used by the later parts of this assignment. It should begin by prompting the user for the abbreviation that describes the subject of the photograph and the number of photos to load. The abbreviation should be read as a string.You may assume that the abbreviation is correct – you do not need to do any error checking on it. When the number of photos is read you should verify that it is greater than or equal to 3 and less than or equal to 16. If not, your program should display an appropriate error message, close the graphics window by calling close(), and quit the program by calling quit(). If the entered number is within the required range then your program should load all of the images. The images must be stored in a list, and the list will contain n images, where n is the integer entered by the user.Once all of the images have been loaded the graphics window should be resized so that it is twice as wide as the loaded images and has the same height as the loaded images. The width of an image can be determined by passing it as an argument to the getWidth function. Similarly, the height of an image can be determined by passing it as an argument to the getHeight function.All of the code described previously should be in a function named loadImages. The loadImages function doesn’t take any parameters. It will return the list of images as its only result. Note that the loadImages function doesn’t generate any graphical output. You’ll write additional functions in later sections to do so.Specifically, Part 2 will discuss how to go about displaying the input images as thumbnails, and Part 3 will discuss how to construct and display the tourist-free image. My implementation of loadImages was 15 lines of code (plus blank lines and comments).Because there is limited space on the screen we’ll display the input images as “thumbnails” that have one quarter the width and one quarter the height (so one sixteenth the area) of the original image. Unfortunately SimpleGraphics doesn’t have a resize function for images, so you’ll have to write a function for creating the smaller image yourself, as described in the following paragraph.Write a function named createThumbnail that takes an image as its only parameter and returns an image as its only result. The body of your function should begin by calling createImage to create a new, blank image that is one quarter the width and one quarter the height of the image passed as the only parameter.Then it should use getPixel, putPixel and nested loops to retrieve every fourth pixel (both horizontally and vertically) from the input image and store them in the thumbnail image. Finally, your function should return the thumbnail image. Note that createImage, getPixel and putPixel require integer arguments for sizes and positions. As a result, you may find it helpful to perform division with the // operator and/or use the int type conversion function.Once you have createThumbnail working, write a second function named drawThumbnails and use it to create (by calling createThumbnail) and display thumbnails for all of the loaded images (which it will take as the function’s only parameter). The thumbnails will be displayed on the left side of the window using rows that each contain up to 4 images.Each row should be filled completely before starting the next row. This means that one row will be used if 3 or 4 images are being processed, two rows will be used if 5, 6, 7 or 8 images are being processed, three rows will be used if 9, 10, 11 or 12 images are being processed, and four rows will be used if 13, 14, 15 or 16 images are being processed.The thumbnail layouts for the Washington Monument (7 images) and Smithsonian Castle (13 images) are shown below. (Your loadImages function should have previously resized the window so that it has the same height as the images in the input set and so that it is wide enough to accommodate both the thumbnails and the result image). The drawThumbnails function does not return a result.My implementation of createThumbnail was 7 lines of code (plus blank lines and comments) and my implementation of drawThumbnails was less than 20 lines of code (plus blank lines and comments). It’s fine if your code is longer than mine, but recognize that these are tasks that you should be able to complete without writing a huge amount of code.Also, I’d recommend calling the update function (without any arguments) after drawing each thumbnail image so that you can see your program’s output as it is generated rather than having to wait for all of the thumbnails to be generated before you can see them.Part 3: Now that you have displayed all of the source images it’s time to create the tourist-free result. Write a function named removeTourists that performs this task. It will take the list of images as its only parameter. The removeTourists function does not return a result.The removeTourists function should begin by creating an image with the same dimensions as the input images and displaying it in the right half of the window. (Yes, you can and should display the image before any pixels have been stored in it). Then process every location in the result image using nested loops.Perform the following tasks at each location: • Build a list that contains the red value for the current location from every source image • Build a list that contains the green value for the current location from every source image • Build a list that contains the blue value for the current location from every source image • Compute the median value of each of the lists above• Store a pixel with median red, median green and median blue at the current location in the result image This is a relatively slow process for even modest-sized images because a large number of lists are being processed. As a result, you will likely find it desirable to call update() occasionally so that you can see that progress is being made.Calling update for every pixel is too slow so I’d recommend calling it either after each line is complete, or each column is complete, (depending on how you have your loops set up). This means that update() will be indented so that it is in the outer of your nested loops but not inside the inner of the nested loops.Write a function named median for computing the median and then call it 3 times – once for the list of red values, once for the list of green values, and once for the list of blue values. The median function will take a list of values as its only parameter and return the median of those values as its only result.Recall that we completed an example in class that computed the median of a collection of values entered by the user. You may find it helpful to use some of the code from that example when completing this part of the assignment (and you are welcome to do so). The expected result for the Capitol Building data set is shown below.• Include a comment at the top of your file that includes your name, student number and a brief description of the program that you have created. • You must use the provided main function without modifying it.• All lines of code that you write must be inside functions (except for the function definitions themselves, any constant definitions, and any import statements). • You must create and use the functions described previously in this document. • Do not define one function inside of another function. • You must make appropriate use of loops. In particular, your program should work for data sets that consist of anywhere between 3 and 16 images, and those images should be able to have any size.• Include appropriate comments for each of your functions. All of your functions should begin with a comment that briefly describes the purpose of the function, along with a description of every parameter and every return value. Functions that do not return a value should be explicitly marked as such.• Your program must not use global variables (except for constant values that are never changed). • Your program must use good programming style. This includes things like appropriate variable names, good comments, minimizing the use of magic numbers, etc.• Break and continue are generally considered bad form. As a result, you are NOT allowed to use them when creating your solution to this assignment. In general, their use can be avoided by using a combination of if statements and writing better conditions on your while loops.Image Formats: • I have provided the data sets as PNG, PPM and GIF files. On my machine the PNG files can be loaded by SimpleGraphics without any trouble, but I have encountered problems with them on other machines. Use the PNG files if you can. If not use either the PPM files or the GIF files.Both of these formats should be able to be loaded by SimpleGraphics on all machines without any trouble. The PPM files are preferable to the GIF files because they are true color images while the GIF files use only 256 colors. However the GIF files are a lot smaller, so they are preferable if you are working on a machine where storage space is at a premium.Hints: • The “sm” (stunt man) data set has very small images. As a result they are fast to load, process and display. I’d suggest working with this data set during development so that you can see the effect of changes that you make to your program quickly.• Don’t want to type the name of the data set and the number of images every time you run your program? Comment out your input statements and replace them with assignment statements that store the values that you would have typed. • Part 1 needs to be completed first. Parts 2 and 3 can be completed in either order.For an A+: Right now the program doesn’t do any error checking on the abbreviation entered by the user. It also forces the user to indicate how many images are in the data set when this could be determined by the computer.Improve the image loading portion of your program so that it only prompts the user for the abbreviation for an image set. Then your program should go on and load all of the images for that set (without requiring the user to enter the number of images). If the user enters an abbreviation for a data set that doesn’t exist it should report an error and quit.Similarly, if the number of images for the data set is less than 3 or more than 16 your program should report an error and quit. Note that you must be able to accommodate any set of images, not just the data sets on the course website. As a result, it is not acceptable to simply check if the abbreviation is one of “cb”, “da”, “sc”, “sm” or “wm” and then hard code the sizes of those data sets – such a solution will not receive any credit. Instead you must use appropriate Python functions / language constructs to determine whether or not the requested images exist and process them appropriately.If you complete the A+ portion of the assignment, please include a clear, highly conspicuous note indicating such at the top of your submission so that your TA knows to grade it.Grading: This assignment will be graded on a combination of functionality and style. A base grade will be determined from the general level of functionality of the program (Does it load all of the images into a list? Does it compute and display the thumbnails correctly? Does it generate the tourist-free image correctly? Etc.). The base grade will be recorded as a mark out of 12.Style will be graded on a subtractive scale from 0 to -3. For example, an assignment which receives a base grade of 12 (A), but has several stylistic problems (such as magic numbers, missing comments, etc.) resulting in a -2 adjustment will receive an overall grade of 10 (B+). Fractional marks will be rounded to the closest integer. Total Score (Out of 12) Letter Grade 12 A 11 A10 B+ 9 B 8 B7 C+ 6 C 5 C4 D+ 3 D 0-2 F
In this assignment you will create a program that plots a hurricane’s track through the Caribbean and surrounding areas. The user will enter latitude, longitude and wind speed data which your program will display on a map. Dots of different colors and sizes will be used to represent hurricanes of different strengths, and lines will be used to connect the dots to illustrate its path.Completing this assignment will require the use of loops and if statements. You do not need to write your own Python functions to complete this assignment, though you may if you would like to. If you choose to write your own functions you must use them properly, including thorough documentation. The following sections provide additional requirements and suggestions for implementing your program.A map of Caribbean can be found in map.gif on the course website. Your program should begin by resizing the graphics window so that it is the same size as the map (1022 pixels wide and 620 pixels high). Then the map should be displayed. This can be accomplished using the loadImage and drawImage functions.The loadImage function takes the name of the file to load (a string) as its only argument and returns an image as its result. This image can be drawn by passing it as the first argument to drawImage. The drawImage function also requires the x and y location where the image should be drawn as its second and third arguments.Once the map has been displayed your program should go on and add lines of latitude and longitude to it. These lines should both be 5 degrees apart and labelled with their latitude / longitude value (including the directional indicator). The left edge of the map is 95 degrees west while its right edge is at 50 degrees west.The bottom edge of the map is at 10 degrees north while its top edge is at 35 degrees north. For simplicity we will drawn the lines of longitude as vertical lines (rather than curves) and we will use equal spacing for all degrees of latitude rather than performing a complex projection. Use loops to draw these lines. It is not acceptable to use a (long) collection of line and text function calls to complete this task. After completing this step your program should display the following image:Once the map is drawn your program will read data about the hurricane’s location and wind speed from the user. The latitude will be entered first (as a floating-point number of degrees north of the equator), followed by the longitude (as a floating-point number of degrees east of the prime meridian), followed by the wind speed (as a floating-point number of miles per hour). Note that all of the longitude values entered will be negative because the Caribbean is west of the prime meridian.Latitude, longitude and wind speed values will continue to be entered until the user enters a latitude of 0 degrees. Each time a latitude and longitude value are read your program should plot a small gray circle with a width and height of 5 pixels on the map at the indicated location. For example, plotting the data for Emily (technically a tropical storm, not a hurricane) should draw several dots across Florida, as shown below:Hint: Every time you run your program you will need to enter several data values. You can automate this by using a feature known as I/O redirection, which will allow your program to read the values from a file instead of from the keyboard. For example, to use the values from the file named Emily.txt instead of reading values from the keyboard, enter the command: python Asn2.py < Emily.txtThe details of how I/O redirection works aren’t important within the scope of this course, but your ability to use it by following the pattern above will save you a significant amount of typing. Several sample data sets saved in the correct format are available on the course website. Feel free to get as much help as you need with I/O redirection from the TAs or instructor. I/O redirection can be used from the terminal / command prompt on Windows, MacOS and Linux.Hurricanes are divided into 5 categories based on their wind speed. These are summarized in the following table: Wind Speed Category Color Dot Diameter (pixels) >= 157 mph 5 Purple 15 130 mph to less than 157 mph 4 Red 13 111 mph to less than 130 mph 3 Orange 11 96 mph to less than 111 mph 2 Yellow 9 74 mph to less than 96 mph 1 Green 7The hurricane data plotted on the map will be more meaningful if different colors and sizes are used for different storm categories. Use the data in the preceding table to color the dots according to the storm’s wind speed, and use the dot diameters from the table so that more server storms occupy more space on the map. Storms with a wind speed below 74 miles per hour are classified as tropical storms (wind speeds of 39 mph or more) or tropical depressions (wind speeds less than 38 mph). Such storms should continue to be drawn in gray using a circle that is 5 pixels in diameter. The dots for Hurricane Irene is are shown below:Your next task is to connect the dots that you drew previously so that the hurricane’s track is a line instead of a collection of disconnected points. Two points are required to draw a line segment. As a result you will need the (x, y) location of the previous dot, as well as the (x, y) location of the current dot, in order to draw the line segment.The previous x and y values can be retained by storing them into appropriately named variables at the bottom of the loop. Then these variables can be read in the next loop iteration to draw the line segment, noting that such a line segment should not be drawn the first time the loop executes. The color of the line segment should match the color of the current dot. The connected track for Hurricane Andrew is shown below:After all of the dots and lines have been drawn your program should report the storm’s maximum category and maximum wind speed in the upper right corner of the window. Report a maximum category of 0 for tropical storms and tropical depressions. This data is shown for Hurricane Ike below. Note that the window has been cropped so that it will fit on this page.Your program should follow good programming practices. This includes using meaningful variable names, avoiding the use of magic numbers and including adequate comments. Magic numbers you should specifically avoid using include:• The gap between the lines of latitude and longitude drawn on the map • The dimensions of the map image • The latitude / longitude values for the boundary of the map.Ideally, if you wanted to use a different map then you should only need to change the image dimensions and boundary values in one place in your program and then every would continue to work correctly. You should also ensure that you include a comment at the top of the file with your name, student number and a brief description of the purpose of your program.Break and continue are generally considered bad form. As a result, you are NOT allowed to use them when creating your solution to this assignment. In general, their use can be avoided by using a combination of if statements and writing better conditions on your while loops.You do not need to perform any error checking in your program. In particular, you may assume that the user always enters valid floating-point numbers. Any latitude / longitude values that are outside of the window should be drawn just like values inside the window. SimpleGraphics will simply ignore any requests to draw outside of the window.Your program should leave the window open until the user closes it by clicking on the close button.Grading: This assignment will be graded on a combination of functionality and style. A base grade will be determined from the general level of functionality of the program (Does it draw the map successfully? Are the lines of latitude and longitude drawn correctly? Does it plot the dots in the correct location? Are the correct colors used for storms in different categories? Is the hurricane’s track connected properly?). The base grade will be recorded as a mark out of 12.Style will be graded on a subtractive scale from 0 to -3. For example, an assignment which receives a base grade of 12 (A) because it generates perfect output, but has several stylistic problems such as magic numbers, poor variable names and missing comments resulting in a -2 adjustment will receive an overall grade of 10 (B+). Total Score (out of 12) Letter Grade 12 A 11 A10 B+ 9 B 8 B7 C+ 6 C 5 C4 D+ 3 D 0-2 FLooking for an A+? Adjust the program so that the color of each line segment matches the stronger of the two storms at its end points. The revised track for Hurricane Andrew is shown below with the differences marked.
5/5 - (1 vote) The Challenge Automatic image processing is a key component to many AI systems, including facial recognition and video compression. One basic method for processing is segmentation, by which we divide an image into a fixed number of components in order to simplify its representation. For example, we can train a mixture of Gaussians to represent an image, and segment it according to the simplified representation as shown in the images below. In this assignment, you will learn to perform image segmentation. To this end, you will implement Gaussian mixture models and iteratively improve their performance. You will perform this segmentation on the “Bird” and “Party Spock” images included with the assignment. About the Assignment The tests for the assignment are provided in the notebook, so Bonnie is only for submission purposes. The tests on Bonnie will be similar to the ones provided here, but the images being tested against, and the values for calculations will be different. Thus, you will be allowed only 5 submissions on Bonnie. Make sure you test everything before submitting. Score for the last submission counts. The code will be allowed to run for not more than 2 hours per submission. In order for the code to run quickly, make sure to vectorize the code (more on this below). Your Mission (should you choose to accept it) Your assignment is to implement several methods of image segmentation, with increasing complexity. Implement k-means clustering to segment a color image. Build a Gaussian mixture model to be trained with expectation-maximization. Experiment with varying the details of the Gaussian mixture model’s implementation. Implement and test a new metric called the Bayesian information criterion, which guarantees a more robust image segmentation. Grading The grade you receive for the assignment will be distributed as follows: k-Means Clustering (20 points) Gaussian Mixture Model (40 points) Model Performance Improvements (20 points) Bayesian Information Criterion (20 points) Bonus Resources The em.pdf chapter in the assignment folder gives a good explanation of implementing and training mixture models, particularly 424-427 (k-means) and 435-439 (mixture models and EM). The book Elements of Statistical Learning, pages 291-295. Background A Gaussian mixture model is a generative model for representing the underlying probability distribution of a complex collection of data, such as the collection of pixels in a grayscale photograph. In the context of this problem, a Gaussian mixture model defines the joint probability f(x)f(x) as f(x)=∑i=1kmiNi(x|μi,σ2i)f(x)=∑i=1kmiNi(x|μi,σi2) where xx is a grayscale value [0,1], f(x)f(x) is the joint probability of that gray scale value, mimi is the mixing coefficient on component ii, NiNi is the ithith Gaussian distribution underlying the value xx with mean μiμi and variance σ2iσi2. We will be using this model to segment photographs into different grayscale regions. The idea of segmentation is to assign a component ii to each pixel xx using the maximum posterior probability componentx=argmaxi(miNi(x|μi,σ2i)componentx=argmaxi(miNi(x|μi,σi2) Then we will replace each pixel in the image with its corresponding μiμi to produce a result as below (original above, segmented with three components below). In [ ]: from __future__ import division import warnings warnings.simplefilter(action = "ignore", category = FutureWarning) import numpy as np import scipy as sp from matplotlib import image import matplotlib.pyplot as plt import matplotlib.cm as cm In [ ]: """Helper image-processing code. These have been added in a separate python file and added in to the repo. The functions below have all been imported in to your submission file""" def image_to_matrix(image_file, grays=False): """ Convert .png image to matrix of values. params: image_file = str grays = Boolean returns: img = (color) np.ndarray[np.ndarray[np.ndarray[float]]] or (grayscale) np.ndarray[np.ndarray[float]] """ img = image.imread(image_file) # in case of transparency values if(len(img.shape) == 3 and img.shape[2] > 3): height, width, depth = img.shape new_img = np.zeros([height, width, 3]) for r in range(height): for c in range(width): new_img[r,c,:] = img[r,c,0:3] img = np.copy(new_img) if(grays and len(img.shape) == 3): height, width = img.shape[0:2] new_img = np.zeros([height, width]) for r in range(height): for c in range(width): new_img[r,c] = img[r,c,0] img = new_img return img def matrix_to_image(image_matrix, image_file): """ Convert matrix of color/grayscale values to .png image and save to file. params: image_matrix = (color) numpy.ndarray[numpy.ndarray[numpy.ndarray[float]]] or (grayscale) numpy.ndarray[numpy.ndarray[float]] image_file = str """ # provide cmap to grayscale images cMap = None if(len(image_matrix.shape) 1 and image_matrix.shape[-1] != 1): depth = image_matrix.shape[-1] return image_matrix.reshape(height, width, depth) else: return image_matrix.reshape(height, width) def image_difference(image_values_1, image_values_2): """ Calculate the total difference in values between two images. Assumes that both images have same shape. params: image_values_1 = (color) numpy.ndarray[numpy.ndarray[numpy.ndarray[float]]] or (grayscale) numpy.ndarray[numpy.ndarray[float]] image_values_2 = (color) numpy.ndarray[numpy.ndarray[numpy.ndarray[float]]] or (grayscale) numpy.ndarray[numpy.ndarray[float]] returns: dist = int """ flat_vals_1 = flatten_image_matrix(image_values_1) flat_vals_2 = flatten_image_matrix(image_values_2) N, depth = flat_vals_1.shape dist = 0. point_thresh = 0.005 for i in range(N): if(depth > 1): new_dist = sum(abs(flat_vals_1[i] - flat_vals_2[i])) if(new_dist > depth * point_thresh): dist += new_dist else: new_dist = abs(flat_vals_1[i] - flat_vals_2[i]) if(new_dist > point_thresh): dist += new_dist return dist In [ ]: image_dir = 'images/' image_file = 'party_spock.png' values = image_to_matrix(image_dir + image_file) print(values) Part 0: Note on Vectorization The concept of Vectorization was introduced in the last section of Assignment 4. For this assignment, please vectorize your code wherever possible using numpy arrays, instead of running for-loops over the images being processed. For an example of how this might be useful, consider the following array: A = [12 34 1234 764 …(has a million values)… 91, 78] Now you need to calculate another array B, which has the same dimensions as A above. Say each value in B is calculated as follows: (each value in B) = square_root_of(some constants pi log(k) * (each value in A))/7 You might wish to use a for-loop to compute this. However, it will take really long to run on an array of this magnitude. Alternatively, you may choose to use numpy and perform this calculation in a single line. You can pass A as a numpy array and the entire calculation will be done in a line, resulting in B being populated with the corresponding values that come out of this formula. Part 1: K-means clustering 20 pts One easy method for image segmentation is to simply cluster all similar data points together and then replace their values with the mean value. Thus, we’ll warm up using k-means clustering. This will also provide a baseline to compare with your segmentation. Please note that clustering will come in handy later. Fill out k_means_cluster() to convert the original image values matrix to its clustered counterpart. Your convergence test should be whether the assigned clusters stop changing. Note that this convergence test is rather slow. When no initial cluster means are provided, k_means_cluster() should choose kk random points from the data (without replacement) to use as initial cluster means. For this part of the assignment, since clustering is best used on multidimensional data, we will be using the color image bird_color_24.png. You can test your implementation of k-means using our reference images in k_means_test(). Try to vectorize the code for it to run faster. Without vectorization it takes 25-30 minutes for the code to run. In [ ]: from random import randint from functools import reduce def k_means_cluster(image_values, k=3, initial_means=None): """ Separate the provided RGB values into k separate clusters using the k-means algorithm, then return an updated version of the image with the original values replaced with the corresponding cluster values. params: image_values = numpy.ndarray[numpy.ndarray[numpy.ndarray[float]]] k = int initial_means = numpy.ndarray[numpy.ndarray[float]] or None returns: updated_image_values = numpy.ndarray[numpy.ndarray[numpy.ndarray[float]]] """ # TODO: finish this function raise NotImplementedError() return updated_image_values In [ ]: def k_means_test(): """ Testing your implementation of k-means on the segmented bird_color_24 reference images. """ k_min = 2 k_max = 6 image_dir = 'images/' image_name = 'bird_color_24.png' image_values = image_to_matrix(image_dir + image_name) # initial mean for each k value initial_means = [ np.array([[0.90980393,0.8392157,0.65098041],[0.83137256,0.80784315,0.69411767]]), np.array([[0.90980393,0.8392157,0.65098041],[0.83137256,0.80784315,0.69411767],[0.67450982,0.52941179,0.25490198]]), np.array([[0.90980393,0.8392157,0.65098041],[0.83137256,0.80784315,0.69411767],[0.67450982,0.52941179,0.25490198],[0.86666667,0.8392157,0.70588237]]), np.array([[0.90980393,0.8392157,0.65098041],[0.83137256,0.80784315,0.69411767],[0.67450982,0.52941179,0.25490198],[0.86666667,0.8392157,0.70588237],[0,0,0]]), np.array([[0.90980393,0.8392157,0.65098041],[0.83137256,0.80784315,0.69411767],[0.67450982,0.52941179,0.25490198],[0.86666667,0.8392157,0.70588237],[0,0,0],[0.8392157,0.80392158,0.63921571]]), ] # test different k values to find best for k in range(k_min, k_max+1): updated_values = k_means_cluster(image_values, k, initial_means[k-k_min]) ref_image = image_dir + 'k%d_%s'%(k, image_name) ref_values = image_to_matrix(ref_image) dist = image_difference(updated_values, ref_values) print('Image distance = %.2f'%(dist)) if(int(dist) == 0): print('Clustering for %d clusters produced a realistic image segmentation.'%(k)) else: print('Clustering for %d clusters didn't produce a realistic image segmentation.'%(k)) In [ ]: k_means_test() Part 2: Implementing a Gaussian mixture model 40 pts Next, we will step beyond clustering and implement a complete Gaussian mixture model. Complete the below implementation of GaussianMixtureModel so that it can perform the following: Calculate the joint log probability of a given greyscale value. (5 points) Use expectation-maximization (EM) to train the model to represent the image as a mixture of Gaussians. (20 points) To initialize EM, set each component’s mean to the grayscale value of randomly chosen pixel and variance to 1, and the mixing coefficients to a uniform distribution. Note: there are packages that can run EM automagically, but please implement your own version of EM without using these extra packages. We’ve set the convergence condition for you in GaussianMixtureModel.default_convergence(): if the new likelihood is within 10% of the previous likelihood for 10 consecutive iterations, the model has converged. Calculate the log likelihood of the trained model. (5 points) Segment the image according to the trained model. (5 points) Determine the best segmentation by iterating over model training and scoring, since EM isn’t guaranteed to converge to the global maximum. (5 points) We have provided the necessary tests for this part. When multiplying lots of probabilities in sequence, you can end up with a probability of zero due to underflow. To avoid this, you should calculate the log probabilities for the entire assignment. The log form of the Gaussian probability of scalar value xx is: ln(N(x|μ,σ))=−0.5ln(2πσ2)−(x−μ)22σ2ln(N(x|μ,σ))=−0.5ln(2πσ2)−(x−μ)22σ2 where μμ is the mean and σσ is standard deviation. You can calculate the sum of log probabilities by using scipy.misc.logsumexp(). For example, logsumexp([-2,-3]) will return the same result as numpy.log(numpy.exp(-2)+numpy.exp(-3)). In other words, logsumexp(a, b) = log(e^a + e^b). Rather than using lists of lists, you will find it much easier to store your data in numpy.array arrays. You can instantiate them using the command matrix = numpy.zeros([rows, columns]) where rows is the number of rows and columns is the number of columns in your matrix. numpy.zeros() generates a matrix of the specified size containing 0s at each row/column cell. You can access cells with the syntax matrix[2,3] which will return the value in row 2 and column 3. Warning: You may lose all marks for this part if your code runs for too long. You will need to vectorize your code in this part. Specifically, the method train_model() needs to perform operations using numpy arrays, as does likelihood(), which calculates the log likelihood. These are time-sensitive operations and will be called over and over as you proceed with this assignment. For the assignment, focus on vectorizing the following: The calculations for the Expectation step, where you calculate joint probabilities The calculations where you update your means, variances and mixing coefficients in the Maximization step. Remember, these are fundamental operations and will be called a lot in the remainder of the assignment. So it is crucial you optimize these. For the synthetic data test which we provide to check if your training is working, the set is too small and it won’t make a difference. But with the actual image that we use ahead, for-loops won’t do good. Vectorized code would take under 30 seconds to converge which would typically involve about 15-20 iterations with the convergence function we have here. Inefficient code that uses loops or iterates over each pixel value sequentially, will take hours to run. You don’t want to do that because: You won’t have that much time to test to your code. You won’t be getting marks. We will be capping the run time and kill anything that takes over 2 minutes for each iteration. You will want to have your image pixel values as a one-dimensional array to perform these operations. We have provided a method to flatten the image for this purpose. In [ ]: def default_convergence(prev_likelihood, new_likelihood, conv_ctr, conv_ctr_cap=10): """ Default condition for increasing convergence counter: new likelihood deviates less than 10% from previous likelihood. params: prev_likelihood = float new_likelihood = float conv_ctr = int conv_ctr_cap = int returns: conv_ctr = int converged = boolean """ increase_convergence_ctr = (abs(prev_likelihood) * 0.9 = likelihood_thresh): print('Congrats! Your model's log likelihood improved by at least %d.'%(likelihood_thresh)) print( 'Synthetic example with 4 means:') num_components = 4 actual_means = [2,4,6,8] actual_variances = [1]*num_components actual_mixing = [.25]*num_components dataset_1 = generate_test_mixture(data_range, actual_means, actual_variances, actual_mixing) gmm = GaussianMixtureModel(dataset_1, num_components) gmm.initialize_training() # start off with faulty means gmm.means = [1,3,5,9] initial_likelihood = gmm.likelihood() gmm.train_model() final_likelihood = gmm.likelihood() # compare likelihoods likelihood_difference = final_likelihood - initial_likelihood likelihood_thresh = 200 if(likelihood_difference >= likelihood_thresh): print('Congrats! Your model's log likelihood improved by at least %d.'%(likelihood_thresh)) return gmm In [ ]: gmm_train_test() In [ ]: def gmm_segment_test(): """ Apply the trained GMM to unsegmented image and generate a segmented image. returns: segmented_matrix = numpy.ndarray[numpy.ndarray[float]] """ image_file = 'images/party_spock.png' image_matrix = image_to_matrix(image_file) num_components = 3 gmm = GaussianMixtureModel(image_matrix, num_components) gmm.initialize_training() gmm.train_model() segment = gmm.segment() segment_num_components = len(np.unique(segment)) if(segment_num_components == num_components): print('Congrats! Your segmentation produced an image '+ 'with the correct number of components.') return segment In [ ]: def gmm_best_segment_test(): """ Calculate the best segment generated by the GMM and compare the subsequent likelihood of a reference segmentation. Note: this test will take a while to run. returns: best_seg = np.ndarray[np.ndarray[float]] """ image_file = 'images/party_spock.png' image_matrix = image_to_matrix(image_file) image_matrix_flat = flatten_image_matrix(image_matrix) num_components = 3 gmm = GaussianMixtureModel(image_matrix, num_components) gmm.initialize_training() iters = 10 # generate best segment from 10 iterations # and extract its likelihood best_seg = gmm.best_segment(iters) matrix_to_image(best_seg, 'images/best_segment_spock.png') best_likelihood = gmm.likelihood() # extract likelihood from reference image ref_image_file = 'images/party_spock%d_baseline.png'%(num_components) ref_image = image_to_matrix(ref_image_file, grays=True) gmm_ref = GaussianMixtureModel(ref_image, num_components) ref_vals = ref_image.flatten() ref_means = list(set(ref_vals)) ref_variances = [0]*num_components ref_mixing = [0]*num_components for i in range(num_components): relevant_vals = ref_vals[ref_vals==ref_means[i]] ref_mixing[i] = float(len(relevant_vals)) / float(len(ref_vals)) ref_variances[i] = np.mean((image_matrix_flat[ref_vals==ref_means[i]] - ref_means[i])**2) gmm_ref.means = ref_means gmm_ref.variances = ref_variances gmm_ref.mixing_coefficients = ref_mixing ref_likelihood = gmm_ref.likelihood() # compare best likelihood and reference likelihood likelihood_diff = best_likelihood - ref_likelihood likelihood_thresh = 1e4 if(likelihood_diff >= likelihood_thresh): print('Congrats! Your image segmentation is an improvement over ' + 'the baseline by at least %.2f.'%(likelihood_thresh)) return best_seg In [ ]: best_segment = gmm_best_segment_test() matrix_to_image(best_segment, 'best_segment.png') Part 3: Model experimentation 20 points We’ll now experiment with a few methods for improving GMM performance. 3a: Improved initialization 12.5 points To run EM in our baseline Gaussian mixture model, we use random initialization to determine the initial values for our component means. We can do better than this! Fill in the below GaussianMixtureModelImproved.initialize_training() with an improvement in component initialization. Please don’t use any external packages for anything other than basic calculations (e.g. scipy.misc.logsumexp). Note that your improvement might significantly slow down runtime, although we don’t expect you to spend more than 10 minutes on initialization. Hint: you’ll probably want an unsupervised learning method to initialize your component means. Clustering is one useful example of unsupervised learning, and you may want to look at 1-dimensional methods such as Jenks natural breaks optimization. In [ ]: class GaussianMixtureModelImproved(GaussianMixtureModel): """A Gaussian mixture model for a provided grayscale image, with improved training performance.""" def initialize_training(self): """ Initialize the training process by setting each component mean using some algorithm that you think might give better means to start with, each component variance to 1, and each component mixing coefficient to a uniform value (e.g. 4 components -> [0.25,0.25,0.25,0.25]). [You can feel free to modify the variance and mixing coefficient initializations too if that works well.] """ # TODO: finish this raise NotImplementedError() In [ ]: def gmm_improvement_test(): """ Tests whether the new mixture model is actually an improvement over the previous one: if the new model has a higher likelihood than the previous model for the provided initial means. returns: original_segment = numpy.ndarray[numpy.ndarray[float]] improved_segment = numpy.ndarray[numpy.ndarray[float]] """ image_file = 'images/party_spock.png' image_matrix = image_to_matrix(image_file) num_components = 3 initial_means = [0.4627451, 0.20392157, 0.36078432] # first train original model with fixed means gmm = GaussianMixtureModel(image_matrix, num_components) gmm.initialize_training() gmm.means = np.copy(initial_means) gmm.train_model() original_segment = gmm.segment() original_likelihood = gmm.likelihood() # then train improved model gmm_improved = GaussianMixtureModelImproved(image_matrix, num_components) gmm_improved.initialize_training() gmm_improved.train_model() improved_segment = gmm_improved.segment() improved_likelihood = gmm_improved.likelihood() # then calculate likelihood difference diff_thresh = 1e3 likelihood_diff = improved_likelihood - original_likelihood if(likelihood_diff >= diff_thresh): print('Congrats! Improved model scores a likelihood that was at ' + 'least %d higher than the original model.'%(diff_thresh)) return original_segment, improved_segment In [ ]: best_segment, best_segment_improved = gmm_improvement_test() matrix_to_image(best_segment, 'best_segment_original.png') matrix_to_image(best_segment_improved, 'best_segment_improved.png') 3b: Convergence condition 7.5 points You might be skeptical of the convergence criterion we’ve provided in default_convergence(). To test out another convergence condition, implement new_convergence_condition() to return true if all the new model parameters (means, variances, and mixing coefficients) are within 10% of the previous variables for 10 consecutive iterations. This will mean re-implementing train_model(), which you will also do below in GaussianMixtureModelConvergence. You can compare the two convergence functions in convergence_condition_test(). In [ ]: def new_convergence_function(previous_variables, new_variables, conv_ctr, conv_ctr_cap=10): """ Convergence function based on parameters: when all variables vary by less than 10% from the previous iteration's variables, increase the convergence counter. params: previous_variables = [numpy.ndarray[float]] containing [means, variances, mixing_coefficients] new_variables = [numpy.ndarray[float]] containing [means, variances, mixing_coefficients] conv_ctr = int conv_ctr_cap = int return: conv_ctr = int converged = boolean """ # TODO: finish this function raise NotImplementedError() return conv_ctr, converged In [ ]: class GaussianMixtureModelConvergence(GaussianMixtureModel): """ Class to test the new convergence function in the same GMM model as before. """ def train_model(self, convergence_function=new_convergence_function): # TODO: finish this function raise NotImplementedError() In [ ]: def convergence_condition_test(): """ Compare the performance of the default convergence function with the new convergence function. return: default_convergence_likelihood = float new_convergence_likelihood = float """ image_file = 'images/party_spock.png' image_matrix = image_to_matrix(image_file) num_components = 3 initial_means = [0.4627451, 0.10196079, 0.027450981] # first test original model gmm = GaussianMixtureModel(image_matrix, num_components) gmm.initialize_training() gmm.means = np.copy(initial_means) gmm.train_model() default_convergence_likelihood = gmm.likelihood() # now test new convergence model gmm_new = GaussianMixtureModelConvergence(image_matrix, num_components) gmm_new.initialize_training() gmm_new.means = np.copy(initial_means) gmm_new.train_model() new_convergence_likelihood = gmm_new.likelihood() # test convergence difference convergence_diff = new_convergence_likelihood - default_convergence_likelihood convergence_thresh = 200 if(convergence_diff >= convergence_thresh): print('Congrats! The likelihood difference between the original ' + 'and the new convergence models should be at least %.2f'%(convergence_thresh)) return default_convergence_likelihood, new_convergence_likelihood Part 4: Bayesian information criterion 20 points In our previous solutions, our only criterion for choosing a model was whether it maximizes the posterior likelihood regardless of how many parameters this requires. As a result, the “best” model may simply be the model with the most parameters, which would be overfit to the training data. To avoid overfitting, we can use the Bayesian information criterion (a.k.a. BIC) which penalizes models based on the number of parameters they use. In the case of the Gaussian mixture model, this is equal to the number of components times the number of variables per component (mean, variance and mixing coefficient) = 3*components. 4a: Implement BIC 5 points Implement bayes_info_criterion() to calculate the BIC of a trained GaussianMixtureModel. In [ ]: def bayes_info_criterion(gmm): # TODO: finish this function raise NotImplementedError() return BIC In [ ]: def bayes_info_test(): """ Test for your implementation of BIC on fixed GMM values. Should be about 727045. returns: BIC = float """ image_file = 'images/party_spock.png' image_matrix = image_to_matrix(image_file) num_components = 3 initial_means = [0.4627451, 0.10196079, 0.027450981] gmm = GaussianMixtureModel(image_matrix, num_components) gmm.initialize_training() gmm.means = np.copy(initial_means) BIC = bayes_info_criterion(gmm) return BIC 4b: Test BIC 15 points Now implement BIC_model_test(), in which you will use the BIC and likelihood to determine the optimal number of components in the Party Spock image. Use the original GaussianMixtureModel for your models. Iterate from k=2 to k=7 and use the provided means to train a model that minimizes its BIC and a model that maximizes its likelihood. Then, fill out BIC_likelihood_question() to return the number of components in both the min-BIC and the max-likelihood model. In [ ]: def BIC_likelihood_model_test(): """Test to compare the models with the lowest BIC and the highest likelihood. returns: min_BIC_model = GaussianMixtureModel max_likelihood_model = GaussianMixtureModel """ # TODO: finish this method raise NotImplementedError() comp_means = [ [0.023529412, 0.1254902], [0.023529412, 0.1254902, 0.20392157], [0.023529412, 0.1254902, 0.20392157, 0.36078432], [0.023529412, 0.1254902, 0.20392157, 0.36078432, 0.59215689], [0.023529412, 0.1254902, 0.20392157, 0.36078432, 0.59215689, 0.71372563], [0.023529412, 0.1254902, 0.20392157, 0.36078432, 0.59215689, 0.71372563, 0.964706] ] return min_BIC_model, max_likelihood_model In [ ]: def BIC_likelihood_question(): """ Choose the best number of components for each metric (min BIC and maximum likelihood). returns: pairs = dict """ # TODO: fill in bic and likelihood raise NotImplementedError() bic = 0 likelihood = 0 pairs = { 'BIC' : bic, 'likelihood' : likelihood } return pairs Bonus 2 points A crucial part of machine learning is working with very large datasets. As stated before, using for loops over these datasets will result in the code taking many hours, or even several days, to run. Even vectorization can take time if not done properly, and as such there are certain tricks you can perform to get your code to run as fast as physically possible. For this part of the assignment, you will need to implement part of a k-Means algorithm. You are given two arrays – points_array with X n-dimensional points, and means_array with Y n-dimensional points. You will need to return an X x Y array containing the distances from each point in points_array to each point in means_array. Your code will be tested using two very large arrays, against our reference implementation, which was designed by Murtaza Dhuliawala. Thus, you’ll be competing against the Head TA! If your implementation returns the correct answer in time comparable to Murtaza’s implementation, you will receive 2 bonus points. For reference, the data used is in the order of thousands of points and hundreds of means, and Bonnie automatically kills a grading script that takes more than 500MB. So please test accordingly locally before submitting, as you may lose a submission for an inefficient solution. It is very likely that you could run out of memory if your implementation is inefficient. In [ ]: def bonus(points_array, means_array): """ Return the distance from every point in points_array to every point in means_array. returns: dists = numpy array of float """ # TODO: fill in the bonus function # REMOVE THE LINE BELOW IF ATTEMPTING BONUS raise NotImplementedError() return dists In [ ]: def bonus_test(): points = np.array([[ 0.9059608,0.67550357,0.13525533],[ 0.23656114,0.63624466,0.3606615 ],[ 0.91163215,0.24431103,0.33318504],[ 0.25209736,0.24600123,0.42392935],[ 0.62799146,0.04520208,0.55232494],[ 0.5588561, 0.06397713,0.53465371],[ 0.82530045,0.62811624,0.79672349],[ 0.50048147,0.13215356,0.54517893],[ 0.84725662,0.71085917,0.61111105],[ 0.25236734,0.25951904,0.70239158]]) means = np.array([[ 0.39874413,0.47440682,0.86140829],[ 0.05671347,0.26599323,0.33577454],[ 0.7969679, 0.44920099,0.37978416],[ 0.45428452,0.51414022,0.21209852],[ 0.7112214, 0.94906158,0.25496493]]) expected_answer = np.array([[ 0.90829883,0.9639127, 0.35055193,0.48575144,0.35649377],[ 0.55067427,0.41237201,0.59110637,0.29048911,0.57821151],[ 0.77137409,0.8551975, 0.23937264,0.54464354,0.73685561],[ 0.51484192,0.21528078,0.58320052,0.39705222,0.85652654],[ 0.57645778,0.64961631,0.47067874,0.60483973,0.95515036],[ 0.54850426,0.57663736,0.47862222,0.56358129,0.94064631],[ 0.45799673,0.966609,0.45458971,0.70173336,0.63993928],[ 0.47695785,0.50861901,0.46451987,0.50891112,0.89217387],[ 0.56543953,0.94798437,0.35285421,0.59357932,0.4495398 ],[ 0.30477736,0.41560848,0.66079087,0.58820896,0.94138546]]) if np.allclose(expected_answer,bonus(points,means),1e-7): print 'You returned the correct distances.' else: print 'Your distance calculation is incorrect.' bonus_test() You’re done with the requirements! Hope you have completed the functions in the mixture_models.py file and tested everything!
5/5 - (1 vote) Machine learning offers a number of methods for classifying data into discrete categories, such as k-means clustering. Decision trees provide a structure for such categorization, based on a series of decisions that led to separate distinct outcomes. In this assignment, you will work with decision trees to perform binary classification according to some decision boundary. Your challenge is to build and to train decision trees capable of solving useful classification problems. You will learn first how to build decision trees, then how to effectively train them and finally how to test their performance. This assignment is due on T-Square as decision_trees.py on March 19th midnight AOE (anywhere on Earth). Abstract You will build, train and test decision tree models to perform basic classification tasks. Motivation Classification is used widely in machine learning to figure out how to sort new data that comes through. Objectives Students should understand how decision trees and random forests work. Students should develop and intuition for how and why accuracy differs for training and testing data based on different parameters. Evaluation Evaluation is using the last submission on Bonnie. Datasets We have provided you with two datasets: part23_data.csv: 4 features, 1372 data points, binary classification (last column) challenge_train.csv: 30 features, 6636 datapoints, binary classification (first column) challenge_test.csv: not provided, similar to challenge_train but with 40% of the dataset Imports We are only allowing three imports: numpy, collections.Counter and time. We will be checking to see if any other libraries are used. You are not allowed to use any outside libraries especially for part 4 (challenge). Introduction For this assignment we’re going to need an explicit way to make structured decisions. The following is DecisionNode, representing a decision node as some atomic choice in a binary decision graph. It can represent a class label (i.e. a final decision) or a binary decision to guide the us through a flow-chart to arrive at a decision. Note that in this representation ‘True’ values for a decision take us to the left. This is arbitrary but matters for what comes next. In [ ]: import numpy as np from collections import Counter import time class DecisionNode(): """Class to represent a single node in a decision tree.""" def __init__(self, left, right, decision_function,class_label=None): """Create a node with a left child, right child, decision function and optional class label for leaf nodes.""" self.left = left self.right = right self.decision_function = decision_function self.class_label = class_label def decide(self, feature): """Return on a label if node is leaf, or pass the decision down to the node's left/right child (depending on decision function).""" if self.class_label is not None: return self.class_label elif self.decision_function(feature): return self.left.decide(feature) else: return self.right.decide(feature) Part 1a: Building a Binary Tree by Hand 5 pts. In build_decision_tree(), construct a tree of decision nodes by hand in order to classify the data below, i.e. map each datum xx to a label yy. Select tests to be as small as possible (in terms of attributes), breaking ties among tests with the same number of attributes by selecting the one that classifies the greatest number of examples correctly. If multiple tests have the same number of attributes and classify the same number of examples, then break the tie using attributes with lower index numbers (e.g. select A1A1 over A2A2) Datum A1A1 A2A2 A3A3 A4A4 y x1x1 1 0 0 0 1 x2x2 1 0 1 1 1 x3x3 0 1 0 0 1 x4x4 0 1 1 0 0 x5x5 1 1 0 1 1 x6x6 0 1 0 1 0 x7x7 0 0 1 1 1 x8x8 0 0 1 0 0 Hints: To get started, it might help to draw out the tree by hand with each attribute representing a node. To create the decision function to pass to your DecisionNode, you can create a lambda expression as follows: func = lambda feature : feature[2] == 0 in which we would choose the left node if the third attribute is 0. For example, if your tree looked like this: if A1=0 then class = 1; else class = 0 A1 / 1 0 You would write your code like this: decision_tree_root= DecisionNode(None, None, lambda a1: a1 == 0) decision_tree_root.left = DecisionNode(None, None, None, 1) decision_tree_root.right = DecisionNode(None, None, None, 0) return decision_tree_root Requirements: The tree nodes should be less than 10 nodes including the leaf (not the number of instances, but the actual nodes in the tree). In [ ]: examples = [[1,0,0,0], [1,0,1,1], [0,1,0,0], [0,1,1,0], [1,1,0,1], [0,1,0,1], [0,0,1,1], [0,0,1,0]] classes = [1,1,1,0,1,0,1,0] In [ ]: def build_decision_tree(): """Create decision tree capable of handling the provided data.""" # TODO: build full tree from root decision_tree_root = None return decision_tree_root In [ ]: decision_tree_root = build_decision_tree() Part 1b: Precision, Recall, Accuracy and Confusion Matrix 12 pts. Now that we have a decision tree, we’re going to need some way to evaluate its performance. In most cases we’d reserve a portion of the training data for evaluation, or use cross-validation. For now let’s just see how your tree does on the provided examples. In the stubbed out code below, fill out the methods to compute the confusion matrix, accuracy, precision and recall for your classifier output. classifier_output is just the list of labels that your classifier outputs, corresponding to the same examples as true_labels. You can refer to Wikipedia for calculating the true/false positive/negative. You should get 1.0 (float) for precision, recall and accuracy. You can create a simple example for the confusion matrix for testing purposes and count by hand. In [ ]: def confusion_matrix(classifier_output, true_labels): #TODO output should be [[true_positive, false_negative], [false_positive, true_negative]] #TODO output is a list raise NotImplemented() def precision(classifier_output, true_labels): #TODO precision is measured as: true_positive/ (true_positive + false_positive) raise NotImplemented() def recall(classifier_output, true_labels): #TODO: recall is measured as: true_positive/ (true_positive + false_negative) raise NotImplemented() def accuracy(classifier_output, true_labels): #TODO accuracy is measured as: correct_classifications / total_number_examples raise NotImplemented() classifier_output = [decision_tree_root.decide(example) for example in examples] p1_confusion_matrix = confusion_matrix(classifier_output, classes) p1_accuracy = accuracy( classifier_output, classes ) p1_precision = precision(classifier_output, classes) p1_recall = recall(classifier_output, classes) print p1_confusion_matrix, p1_accuracy, p1_precision, p1_recall Part 2a: Decision Tree Learning 6 pts. You will need to implement entropy() and information_gain() in order to do so (hints here) and here). Test cases have been provided. In [ ]: def entropy(class_vector): """Compute the entropy for a list of classes (given as either 0 or 1).""" # TODO: finish this raise NotImplemented() def information_gain(previous_classes, current_classes ): """Compute the information gain between the previous and current classes (a list of lists where each list has 0 and 1 values).""" # TODO: finish this raise NotImplemented() def test_information_gain(): """ Assumes information_gain() accepts (classes, [list of subclasses]) Feel free to edit / enhance this note with more tests """ restaurants = [0]*6 + [1]*6 split_patrons = [[0,0], [1,1,1,1], [1,1,0,0,0,0]] split_food_type = [[0,1],[0,1],[0,0,1,1],[0,0,1,1]] # If you're using numpy indexing add the following before calling information_gain() # split_patrons = [np.array(i) for i in split_patrons] #convert to np array # split_food_type = [np.array(i) for i in split_food_type] gain_patrons = information_gain(restaurants, split_patrons) gain_type = information_gain(restaurants, split_food_type) assert round(gain_patrons,3) == 0.541, "Information Gain on patrons should be 0.541" assert gain_type == 0.0, "Information gain on type should be 0.0" print "Information Gain calculations correct..." assert (information_gain([1,1,1,0,0,0],[[1,1,1],[0,0,0]])==1),"TEST FAILED" assert (round(information_gain([1,1,1,0,0,0],[[1,1,0],[1,0,0]]),2)==0.08),"TEST FAILED" def test_entropy(): assert (entropy([1,1,1,0,0,0])==1),"TEST FAILED" assert (entropy([1,1,1,1,1,1])==0),"TEST FAILED" assert (int(entropy([1,1,0,0,0,0])*100)==91),"TEST FAILED" test_information_gain() test_entropy() Part 2b: Decision Tree Learning 20 pts. File to use: part23_data.csv Grading: average test accuracy over 10 rounds should be >= 70% As the size of our training set grows, it rapidly becomes impractical to build these trees by hand. We need a procedure to automagically construct these trees. For starters, let’s consider the following algorithm (a variation of C4.5) for the construction of a decision tree from a given set of examples: 1) Check for base cases: a) If all elements of a list are of the same class, return a leaf node with the appropriate class label. b) If a specified depth limit is reached, return a leaf labeled with the most frequent class. 2) For each attribute alpha: evaluate the normalized information gain gained by splitting on attribute $alpha$ 3) Let alpha_best be the attribute with the highest normalized information gain 4) Create a decision node that splits on alpha_best 5) Recur on the sublists obtained by splitting on alpha_best, and add those nodes as children of node First, in the DecisionTree.__build_tree__() method implement the above algorithm. Next, in DecisionTree.classify() below, write a function to produce classifications for a list of features once your decision tree has been built. Some other helpful notes: 1) Your features and classify should be in numpy arrays where if the dataset was (m x n) then the features is (m x n-1) and classify is (m x 1). 2) These features are continuous features and you will need to split based on a threshold. How grading works: 1) We load part23_data.csv and create our cross-validation training and test set with a k=10 folds. 2) We classify the training data onto the three then fit the testing data onto the tree. 3) We check the accuracy of your results versus the true results and we return the average of this over 10 iterations. In [ ]: class DecisionTree(): """Class for automatic tree-building and classification.""" def __init__(self, depth_limit=float('inf')): """Create a decision tree with an empty root and the specified depth limit.""" self.root = None self.depth_limit = depth_limit def fit(self, features, classes): """Build the tree from root using __build_tree__().""" self.root = self.__build_tree__(features, classes) def __build_tree__(self, features, classes, depth=0): """Implement the above algorithm to build the decision tree using the given features and classes to build the decision functions.""" #TODO: finish this raise NotImplemented() def classify(self, features): """Use the fitted tree to classify a list of examples. Return a list of class labels.""" class_labels = [] #TODO: finish this raise NotImplemented() return class_labels Part 2c: Validation 10 pts. File to use: part23_data.csv Grading: average test accuracy over 10 rounds should be >= 70% In general, reserving part of your data as a test set can lead to unpredictable performance- a serendipitous choice of your train or test split could give you a very inaccurate idea of how your classifier performs. That’s where k-fold cross validation comes in. In generate_k_folds(), we’ll split the dataset at random into k equal subsections. Then iterating on each of our k samples, we’ll reserve that sample for testing and use the other k-1 for training. Averaging the results of each fold should give us a more consistent idea of how the classifier is doing across the data as a whole. How grading works: The same as 2b however, we use your generate_k_folds instead of ours. In [ ]: def load_csv(data_file_path, class_index): handle = open(data_file_path, 'r') contents = handle.read() handle.close() rows = contents.split('n') out = np.array([[float(i) for i in r.split(',')] for r in rows if r]) if(class_index == -1): # this is used for part23_data classes= map(int, out[:,class_index]) features = out[:,:class_index] return features, classes elif(class_index == 0): # this is used for challenge_train classes= map(int, out[:, class_index]) features = out[:, 1:] return features, classes else: # this is used for vectorize return out def generate_k_folds(dataset, k): #TODO this method should return a list of folds, # where each fold is a tuple like (training_set, test_set) # where each set is a tuple like (examples, classes) raise NotImplemented() dataset = load_csv('part23_data.csv', -1) ten_folds = generate_k_folds(dataset, 10) accuracies = [] precisions = [] recalls = [] confusion = [] for fold in ten_folds: train, test = fold train_features, train_classes = train test_features, test_classes = test tree = DecisionTree( ) tree.fit( train_features, train_classes) output = tree.classify(test_features) accuracies.append( accuracy(output, test_classes)) precisions.append( precision(output, test_classes)) recalls.append( recall(output, test_classes)) confusion.append( confusion_matrix(output, test_classes)) Part 3: Random Forests 30 pts. File to use: part23_data.csv Grading: average test accuracy over 10 rounds should be >= 75% The decision boundaries drawn by decision trees are very sharp, and fitting a decision tree of unbounded depth to a list of training examples almost inevitably leads to overfitting. In an attempt to decrease the variance of our classifier we’re going to use a technique called ‘Bootstrap Aggregating’ (often abbreviated ‘bagging’). A Random Forest is a collection of decision trees, build as follows: 1) For every tree we're going to build: a) Subsample the examples provided us (with replacement) in accordance with a provided example subsampling rate. b) From the sample in a), choose attributes at random to learn on (in accordance with a provided attribute subsampling rate) c) Fit a decision tree to the subsample of data we've chosen (to a certain depth) Classification for a random forest is then done by taking a majority vote of the classifications yielded by each tree in the forest after it classifies an example. Fill in RandomForest.fit() to fit the decision tree as we describe above, and fill in RandomForest.classify() to classify a given list of examples. Your features and classify should be in numpy arrays where if the dataset was (m x n) then the features is (m x n-1) and classify is (n x 1). To test, we will be using a forest with 5 trees, with a depth limit of 5, example subsample rate of 0.5 and attribute subsample rate of 0.5 How grading works: similar to 2b but with the call to Random Forest. In [ ]: class RandomForest(): """Class for random forest classification.""" def __init__(self, num_trees, depth_limit, example_subsample_rate, attr_subsample_rate): """Create a random forest with a fixed number of trees, depth limit, example sub-sample rate and attribute sub-sample rate.""" self.trees = [] self.num_trees = num_trees self.depth_limit = depth_limit self.example_subsample_rate = example_subsample_rate self.attr_subsample_rate = attr_subsample_rate def fit(self, features, classes): """Build a random forest of decision trees.""" # TODO implement the above algorithm raise NotImplemented() def classify(self, features): """Classify a list of features based on the trained random forest.""" # TODO implement classification for a random forest. raise NotImplemented() Part 4: Challenge Classifier 10 points. File to use: challenge_train.csv Grading: average training accuracy over 10 runs should be >= 80% and average ru accuracy over 10 runs should be >= 70% You should be implementing some sort of a tree structure, students in the past have been able to call their RandomForest with different parameters. We also encourage things like boosting. You’ve been provided with a sample of data from a research dataset in ‘challenge_train.csv’ while we have reserved a part of the dataset for testing called challenge_test.csv (which you do not have access to). To get full points for this part of the assignment, you’ll need to get at least an average accuracy of 80% on the training data you have (challenge_train.csv), and at least an average accuracy of 70% on the holdout/test set (challenge_test.csv). We do provide how long it takes for your training and testing to run. In [ ]: class ChallengeClassifier(): def __init__(self): # initialize whatever parameters you may need here- # this method will be called without parameters # so if you add any to make parameter sweeps easier, provide defaults raise NotImplemented() def fit(self, features, classes): # fit your model to the provided features raise NotImplemented() def classify(self, features): # classify each feature in features as either 0 or 1. raise NotImplemented() Part 5: Vectorization! 7 points. File to use: vectorize.csv Last semester, students struggled a lot with assignment 5 not because of the assignment but of the vectorization requirement so that it can run under the time limit we have. As a result, we are adding a small section to this assignment that will hopefully introduce you to vectorization and some of the cool tricks you can use in python. We encourage you to use any numpy function out there (on good faith) to do the following functions. For the three functions that we have, we are testing your code based on how fast it runs. It will need to beat the non-vectorized code to get full points. As a reminder, please don’t ask the TA’s for help regarding this section, we will not be able to assist you in any way. This section was created to help get you ready for assignment_5; feel free to ask other students on Piazza or use the Internet. How grading works: we run the non-vectorized code and your vectorized code 500 times, as long as the average time of your vectorized code is less than the average time of the non-vectorized code, you will get the points (given that your answer is correct). In [ ]: import time import resource import numpy as np class Vectorization(): def load_csv(self,data_file_path, class_index): handle = open(data_file_path, 'r') contents = handle.read() handle.close() rows = contents.split('n') out = np.array([[float(i) for i in r.split(',')] for r in rows if r]) if(class_index == -1): classes= map(int, out[:,class_index]) features = out[:,:class_index] return features, classes elif(class_index == 0): classes= map(int, out[:, class_index]) features = out[:, 1:] return features, classes else: return out # Vectorization #1: Loops! # This function takes one matrix, multiplies by itself and then adds to itself. # Output: return a numpy array # 1 point def non_vectorized_loops(self, data): non_vectorized = np.zeros(data.shape) for row in range(data.shape[0]): for col in range(data.shape[1]): non_vectorized[row][col] = data[row][col] * data[row][col] + data[row][col] return non_vectorized def vectorized_loops(self, data): # TODO vectorize the code from above # Bonnie time to beat: 0.09 seconds raise NotImplemented() def vectorize_1(self): data = self.load_csv('vectorize.csv', 1) start_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 real_answer = self.non_vectorized_loops(data) end_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 print 'Non-vectorized code took %s seconds' % str(end_time-start_time) start_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 my_answer = self.vectorized_loops(data) end_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 print 'Vectorized code took %s seconds' % str(end_time-start_time) assert np.array_equal(real_answer, my_answer), "TEST FAILED" # Vectorization #2: Slicing and summation # This function searches through the first 100 rows, looking for the row with the max sum # (ie, add all the values in that row together) # Output: return the max sum as well as the row number for the max sum # 3 points def non_vectorized_slice(self, data): max_sum = 0 max_sum_index = 0 for row in range(100): temp_sum = 0 for col in range(data.shape[1]): temp_sum += data[row][col] if (temp_sum > max_sum): max_sum = temp_sum max_sum_index = row return max_sum, max_sum_index def vectorized_slice(self, data): # TODO vectorize the code from above # Bonnie time to beat: 0.07 seconds raise NotImplemented() def vectorize_2(self): data = self.load_csv('vectorize.csv', 1) start_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 real_sum, real_sum_index = self.non_vectorized_slice(data) end_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 print 'Non-vectorized code took %s seconds' % str(end_time-start_time) start_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 my_sum, my_sum_index = self.vectorized_slice(data) end_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 print 'Vectorized code took %s seconds' % str(end_time-start_time) assert (real_sum==my_sum),"TEST FAILED" assert (real_sum_index==my_sum_index), "TEST FAILED" # Vectorization #3: Flattening and dictionaries # This function flattens down data into a 1d array, creates a dictionary of how often a # positive number appears in the data and displays that value # Output: list of tuples [(1203,3)] = 1203 appeared 3 times in data # 3 points def non_vectorized_flatten(self, data): unique_dict = {} flattened = np.hstack(data) for item in range(len(flattened)): if flattened[item] > 0: if flattened[item] in unique_dict: unique_dict[flattened[item]] += 1 else: unique_dict[flattened[item]] = 1 return unique_dict.items() def vectorized_flatten(self, data): # TODO vectorize the code from above # Bonnie time to beat: 15 seconds raise NotImplemented() def vectorize_3(self): data = self.load_csv('vectorize.csv', 1) start_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 answer_unique = self.non_vectorized_flatten(data) end_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 print 'Non-vectorized code took %s seconds'% str(end_time-start_time) start_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 my_unique = self.vectorized_flatten(data) end_time = resource.getrusage(resource.RUSAGE_SELF).ru_utime * 1000 print 'Vectorized code took %s seconds'% str(end_time-start_time) assert np.array_equal(answer_unique, my_unique), "TEST FAILED" In [ ]: vectorize = Vectorization() vectorize.vectorize_1() vectorize.vectorize_2() vectorize.vectorize_3() Bonus Note: this part will be changing. Official annoucements for this bonus will be made through Piazza We will be having a competition using your challenge classifier and a dataset of our choice. We will provide you with a portion of the dataset as well as the testing data (but without the labels) and you will upload your solution as a csv to Kaggle. Kaggle will evaluate your scores and the classifier with the highest accuracy will win the competiton. Any ties will be broken by the submission time. We are still figuring out all the details for this bonus so hopefully it will be out by the time the midterm period is over. We will keep the competition available for at least a few weeks. First place: 3 bonus points on your final grade Second place: 2 bonus points on your final grade Third place: 1 bonus point on your final grade In [ ]:
Abstract You will implement several Bayesian networks and sampling algorithms to gain a better understanding of probabilistic systems.Learning Objectives Students should be able to understand the importance of Bayesian networks to represent conditional dependencies. Also, be able learn the sampling methods, Gibbs and Metropolis-Hastings and develop an intuition for their convergence criteria (very “researchy”).Evaluation Evaluation is using the last submission on Bonnie. 1. The Challenge Many AI systems rely on probabilistic knowledge of the world, rather than absolute knowledge, to execute tasks efficiently: for example, motion planning in robots with unreliable sensors. One type of probabilistic system that is especially useful is the Bayesian network, which encodes a joint probability distribution among dependent variables as a network of conditional probabilities. Your challenge is to implement and test several of these networks, ultimately using a sampling method to approximate a probability distribution. Figure 1: Example Bayesian network (representing prediction for wet grass).Your task is to implement a few basic networks as well as several sampling algorithms. You will do this in probability notebook.ipynb, and there are tests along the way to help. Unlike previous assignments, we will not be grading on performance but rather on completion.We have provided the following additional classes and files: File/Folder Description probability_tests.py To test the models you’ve built. pbnt/combined Module to implement Bayesian networks (you’ll basically need BayesNode in Node.py and BayesNet in Graph.py). Also contains an example (ExampleModels.py) to help you get started. This is meant to be a shorter assignment, so there won’t be much testing required.3. Grading BASIC TASK (100 points) Warmup 1a: Build a basic Bayesian network representing a power plant. (10 points) Warmup 1b: Set the probabilities for the Bayes Net. (15 points) Warmup 1c: Use inference to calculate several marginal probabilities within the Net. (10points) Exercise 2a: Build a Bayesian network representing a sports competition. (10 points) Exercise 2b: Given the outcomes of 2 matches, calculate likelihoods for the 3rd match. (5 points) Exercise 2c: Implement single iteration of Gibbs sampling. (15 points) Exercise 2d: Implement single iteration of Metropolis-Hastings sampling.(15 points) Exercise 2e: Compare the performance of the 2 sampling methods. (20 points)4. Due date This assignment is due on Bonnie and T-Square by February 26th at 11:59PM UTC-12 (Anywhere on Earth). The deliverable for this assignment is a Python file : ● Probability_solution.py5. Resources IMPORTANT: If you want to know more about how pbnt works, check out exampleinference.py and water() in pbnt/combined/ExampleModels.py. Also here’s a clone of the library : https://github.com/achille/pbnt. Basics of Bayes nets and Conditional Probability: – https://www.mathsisfun.com/data/probability-events-conditional.html – https://ocw.mit.edu/courses/mathematics/18-05-introduction-to-probability-and-st atistics-spring-2014/class-slides/ Gibbs Sampling and convergence: – http://gandalf.psych.umn.edu/users/schrater/schrater_lab/courses/AI2/gibbs.pdf – https://en.wikipedia.org/wiki/Gibbs_sampling – https://www.youtube.com/watch?v=ol0l6aTfb_g – Section 14.5 in Russell and Norvig (pp. 535-538 for Gibbs sampling). Metropolis Hastings and convergence: – http://www.mit.edu/~ilkery/papers/MetropolisHastingsSampling.pdf – https://www.cs.cmu.edu/~scohen/psnlp-lecture6.pdf Although you don’t have to implement the inference algorithm (Junction tree) that you’ll use with your networks, you might be interested in knowing how it works. You can find details on pp. 529-530 of Russell and Norvig.
Your assignment is to write a generic double singly-linked list class with an iterator, and a generic sorted double singly-linked list class with an iterator that inherits from your generic double singly-linked list class. The GUI has been provided for you for this assignment to help you visualize your linked list. Your list classes will also be tested with Junit tests. Upload the initial files from Blackboard and your working files in a directory into the repository in GitHub you created in Lab 1 and take a screen shot of the files. Exception handlingGeneric ClassesDouble Linked ListOrdered Double Linked ListIteratorsComparators BasicDoubleLinkedList This generic double singly-linked list relies on a head (reference to first element of the list) and tail (reference to the last element of the list). Both the head and the tail are set to null when the list is empty. Both point to the same element when there is only one element in the list, and now the element’s “next” and “previous” references point to null. A node structure has only two fields: data and the next references. The class must only define the following entities: an inner class Node, an inner class that implements ListIterator (for the iterator method), head and tail references and an integer representing the list size. However only the next(), hasNext(), previous() and hasPrevious() methods of the ListIterator are you required to implement. The rest of the methods can throw the UnsupportedOperationException, such as:public void remove() throws UnsupportedOperationException{throw new UnsupportedOperationException();}All the entities are defined as protected so they can be accessed by the subclass. Follow the Javadoc that is provided. SortedDoubleLinkedListA generic sorted double linked list will be constructed using a provided Comparator to determine how the list is to be sorted. It extends BasicDoubleLinkedList class. The addToFront and the addToEnd methods will not be supported and an add method will be added that inserts to the double linked list in sorted order dependent on the Comparator. Follow the Javadoc that is provided. Exception Handling GUI driver (provided for you) A GUI driver has been provided for you to help you visualize your doubly-linked lists. Here is the minimum that must be in place to start using the GUI driver effectively. Testing Adding to a Basic List Adding to a Sorted List Removing Second from basic Removing Thomas from sorted Start the iterators for Basic and Sorted. Think of iterators being “in between” nodes. Example of selecting “Next” for Basic and then for Sorted list. Think of iterators being “in between” nodes. Example of “Next” for basic and “Previous” for Sorted. Think of iterators being “in between” nodes. Deliverables / Submissions: Design: UML class diagram with algorithm (pseudo-code) for methodsImplementation: Submit a compressed file containing the follow (see below): The Java application (it must compile and run correctly); Javadoc files in a directory; a write-up as specified below. Be sure to review the provided project rubric to understand project expectations. The write-up will include: Deliverable format: The above deliverables will be packaged as follows. Two compressed files in the following formats: This folder should contain Java source files only
Samuel F. B. Morse produced the first working telegraph set in 1836. This made transmission possible over any distance. The first Morse Code message, “What hath God wrought?”, was sent from Washington to Baltimore.Morse code was extensively used for early radio communication beginning in the 1890s.In the early part of the twentieth century, the majority of high-speed international communication was conducted in Morse code, using telegraph lines, undersea cables, and radio circuits. Morse code can also be transmitted using light which sometimes happens between ships at sea. It is used in emergencies to transmit distress signals when no other form of communication is available. The standard international distress signal is •••—••• (SOS). Write the classes required to create a Morse Code Converter Utility. Your Morse Code Converter Utility will be using a generic linked binary tree with generic TreeNodes to convert Morse Code into English. There is no GUI requirement for this assignment. You are supplied a GUI for testing purposes. Generic ClassesUtility Class (all static methods)Linked TreesBuilding a Tree for conversion purposes Data Element – TreeNode classThis generic class is used in the MorseCodeTree classes. The class consists of a reference to the data and a reference to the left and right child. Follow the Javadoc that is provided. The Javadoc only lists those public methods that are required to pass the Junit tests. You may add any private methods you need for your design. Data Structure – MorseCodeTree classA generic linked binary tree which inherits from the LinkedConverterTreeInterface. The class uses an external generic TreeNode class parameterized as a String: TreeNode. This class uses the private member of root. Nodes are added based on their morse code value. A ‘.’ (dot) means to traverse left and a ‘-‘ (dash) means to traverse right. The constructor will call the method to “build the tree”. Follow the Javadoc that is provided. The Javadoc only lists those public methods that are required to pass the Junit tests. You may add any private methods you need for your design.Utility class – MorseCodeConverterThe MorseCodeConverter contains a static MorseCodeTree object and constructs (calls the constructor for) the MorseCodeTree.This class has two static methods convertToEnglish to convert from morse code to English. One method is passed a string object (“.-.. — …- . / .-.. — — -.- …”). The other method is passed a file to be converted. These static methods use the MorseCodeTree to convert from morse code to English characters. Each method returns a string object of English characters.There is also a static printTree method that is used for testing purposes – to make sure the tree for MorseCodeTree was built properly.Use the Javadoc provided to make sure that your MorseCodeConverter class follows the method headers so that the MorseCodeConverterTest will run correctly.Testing – JUnit Test ClassesYou must add at least 1 test for MorseCodeConverter.convertToEnglish(String) and at least 1 test for MorseCodeConverter.convertToEnglish(File) to the MorseCodeConverterTest class. You must create a JUnit test for your MorseCodeTree class. Include your test files with your code files. This is a table for the conversion from Morse Code to alpha letters.Building the MorseCodeTree (method buildTree)Your MorseCodeTree is a 4 levels tree. Insert a mapping for every letter of the alphabet into the tree map. The root is a TreeNode with an empty string. The left node at level 1 stores letter ‘e’ (code ‘.’) and the right node stores letter ‘t’ (code ‘-‘). The 4 nodes at level 2 are ‘i’, ‘a’, ‘n’, ‘m’ (code ‘..’, ‘.-‘, ‘-.’, ‘—‘). Insert into the tree by tree level from left to right. A ‘.’ will take the branch to the left and a ‘-‘ will take the branch to the right. This is the structure of the tree.Using the MorseCodeTreeUse the MorseCodeTree to convert Morse Code to English by taking the code and finding it’s corresponding English letter by traversing the MorseCodeTree, ‘.’ branches to the left and ‘-‘ branches to the right. The code ‘.–.’ would branch to the left, then to the right, then to the right, then to the left to Fetch the letter ‘p’. Each letter is delimited by a space (‘ ‘). Each word is delimited by a ‘/’. Some suggestions:https://morsecode.scphillips.com/jtranslator.html This will help you build files and test cases for your JUnit Tests. Test Cases:Hello World How do I love thee let me count the ways Njs célébrer Deliverables / Submissions: Design: UML class diagram with algorithm (pseudo-code) for methodsImplementation: Submit a compressed file containing the follow (see below): The Java application (it must compile and run correctly); Javadoc files in a directory; a write-up as specified below. Be sure to review the provided project rubric to understand project expectations. The write-up will include: Deliverable format: The above deliverables will be packaged as follows. Two compressed files in the following formats: This folder should contain Java source files only
Concepts tested by this program:ExceptionsNew concepts tested by this programGeneric ClassesDoubly Linked ListOrdered Doubly Linked ListIteratorsComparatorsYour assignment is to write a generic doubly-linked list class and a generic sorted doubly-linked list class that inherits from your generic doubly-linked class. There is no additional GUI required for this assignment. Your list classes will be tested with Junit tests.BasicDoubleLinkedList classThis generic doubly-linked list relies on a head (reference to first element of the list) and tail (reference to the last element of the list). Both are set to null when the list is empty. Both point to the same element when there is only one element in the list. A node structure has only three fields: data and the prev and next references. The class must only define the following entities: an inner class Node, an inner class that implements ListIterator (for the iterator method), head and tail references and an integer representing the list size. However only the next(), hasNext(), previous() and hasPrevious() methods of the ListIterator that you are required to implement. The rest of the methods can return can throw the UnsupportedOperationException, such as:public void remove() throws UnsupportedOperationException{throw new UnsupportedOperationException();}All the entities are defined as protected so they can be accessed by the subclass. Follow the Javadoc that is provided.SortedDoubleLinkedList classA generic sorted doubly-linked list constructed using a provided Comparator. It extends BasicDoubleLinkedList class. Follow the Javadoc that is provided.Exception HandlingUnsupportedOperationException – this exception is a Java library exception and will be returned by the addtoFront and addToEnd implementations of the SortedLinkedList class and by the remove method of the iterator.NoSuchElementException – this exception is a Java library exception and will be returned by the next function within the iterator class when there are no more elements in the linked list.Deliverables:Java files – The src folder with your driver (javafx application), data element, data manager and Junit Test (.java) filesJavadoc files – The doc folder with your javadoc for student generated filesUML Class Diagram (an image, not the proprietary format, must be a .jpg)Deliverable format: The above deliverables will be packaged as follows. Two compressed files in the following formats:LastNameFirstName_AssignmentX_Complete.zip [a compressed file containing the following]UML.jpgAssignment 2 Checklist (filled in with YES or NO or ?)doc [a directory] please include the entire doc folder with the javadoc for studentgenerated filesfile1.html (example)file2.html (example)src [a directory] contains your driver (javafx application), enumerated class, dataelement, data manager and Junit Test (.java) filesFile1.java (example)File2.java (example)File_Test.java (example)LastNameFirstName_AssignmentX_Moss.zip [a compressed file containing only the following]contains .java file which includes the driver (javafx application), enumeratedclass, data element, data manager and Junit Test (.java) files – NO FOLDERS!!File1.java (example)File2.java (example)
File illinimensbb.csv, in comma-separated values (CSV) format, contains 2018–2019 season statistics and roster information for fifteen Illini men’s basketball players. The first column contains the jersey number, and the remaining columns contain player name, height (Ht, inches), position (Pos, C=center, F=forward, G=guard), minutes of playing time (MIN), field goals made (FGM), field goals attempted (FGA), and number of shots blocked (BLK). You will build a logistic regression model for field goals, and a Poisson loglinear regression model for shots blocked, using JAGS and rjags. 1. [2 pts] Using plot(Ht ~ Pos, data= · · · ), display box plots of height by position. Is there a relationship between height and position? (Such a relationship might cause substantial posterior correlations between regression coefficients if both height and position are used as explanatory variables.) 2. Let yi be the number of field goals made by player i out of ni attempts (i = 1, . . . , 15). Consider the following logistic regression (with implicit intercept) on player position and height: yi | pi ∼ indep. Bin(ni , pi) logit(pi) = βPos(i) + βHt Hi where Pos(i) = player i position (C, F, G) Hi = player i height after centering and scaling to sample standard dev. 0.5 Consider the prior βC, βF, βG ∼ iid t10, 102 βHt ∼ t10, 2.5 2 (a) [2 pts] List an appropriate JAGS model. Include nodes for the vector of binomial probabilities pi and a vector y rep of replicate responses. Now run your model using rjags. Make sure to use multiple chains with overdispersed starting points, check convergence, and monitor the regression coefficients, probabilities, and replicate responses (after convergence) long enough to obtain effective sample sizes of at least 4000 for each regression coefficient. (b) [2 pts] Display the coda summary of the results for the monitored regression coefficients. (c) [2 pts] With your posterior samples, display scatterplots of (i) βC versus βHt, (ii) βF versus βHt, and (iii) βG versus βHt. Do you see (posterior) correlations? (d) [2 pts] Consider the modeled probability that Ayo Dosunmu (No. 11) successfully makes an attempted field goal. Plot the (approximate) posterior density of this probability. (e) [2 pts] Approximate the posterior probability that βF > βG (i.e., that forwards have a higher probability of successfully making an attempted field goal than guards, after adjusting for height). Also, approximate the Bayes factor favoring βF > βG versus βF < βG. (Note that, by symmetry, βF > βG and βF < βG have equal prior probability.) What can you say about the data evidence that βF > βG? (f) [2 pts] Use the chi-square discrepancy to compute an approximate posterior predictive p-value. Does it indicate any evidence of problems (such as overdispersion)? (g) Now consider expanding the model to allow for overdispersion, as follows: logit(pi) = βPos(i) + βHt Hi + εi with εi | σε ∼ iid N 0, σ2 ε σε ∼ U(0, 10) and everything else the same as before. (i) [3 pts] List an appropriately modified JAGS model. Then run it using rjags, with all of the usual steps. (ii) [1 pt] Plot the (approximate) posterior density of σε. (iii) [2 pts] Repeat part (e) (not part (f)) under this expanded model. Does your conclusion change? 3. Let yi be the number of shots blocked by player i (i = 1, . . . , 15). Consider the following Poisson loglinear regression (with implicit intercept) on player position and height, using minutes of playing time as a rate (exposure) variable: yi | ri , ti ∼ indep. Poisson(tiri) log(ri) = βPos(i) + βHt H∗ i where ti = player i total minutes of playing time Pos(i) = player i position (C, F, G) H∗ i = player i height after standardizing (centering and scaling to sample standard dev. 1) (Note that the scaling of H∗ i is different than that of Hi in the previous part.) Consider the prior βC, βF, βG, βHt ∼ iid N 0, 1002 (a) [2 pts] List an appropriate JAGS model. Include nodes for the vector of Poisson means λi = tiri and a vector y rep of replicate responses. Now run your model using rjags. Make sure to use multiple chains with overdispersed starting points, check convergence, and monitor the regression coefficients, Poisson means, and replicate responses (after convergence) long enough to obtain effective sample sizes of at least 4000 for each regression coefficient. (b) [2 pts] Display the coda summary of the results for the monitored regression coefficients. (c) [2 pts] The sampling model implies that e βHt represents the factor by which the mean rate of blocking shots changes for each increase in height of one standard deviation (here, about 3.5 inches). (Under the model, this factor is the same for all positions.) Form an approximate 95% central posterior credible interval for this factor. According to your interval, does it seem that greater height is associated with a higher rate of blocking shots? (d) [2 pts] Use the chi-square discrepancy to compute an approximate posterior predictive p-value. Does it indicate any evidence of problems? (e) For each player (i), approximate Pr y rep i ≥ yi | y , which is a kind of marginal posterior predictive p-value. (i) [2 pts] Show your R code, and display a table with the player names and their values of this probability. (ii) [1 pt] Name any players for whom this probability is less than 0.05. (Any such player blocked notably more shots than the model would suggest, for his position and height.) (iii) [1 pt] Notice that the probability equals 1 for some players. Why is that actually not surprising? (Hint: How many shots were actually blocked by those players? How much playing time did they have?) Total: 32 pts
File usparkvisits.csv contains annual numbers of recreational visits to 30 different parks managed by the US National Park Service for the years 2006 through 2018.1 You will build and compare two different varying-coefficient hierarchical normal regression models for the log-scale numbers, using JAGS and rjags. (a) (i) [2 pts] On the same set of axes, plot segmented lines, one for each park, representing the number of visits versus the year (2006 through 2018). Distinguish the lines for different parks by using different colors or line types. (You should label the axes, but no legend is needed.) (ii) [2 pts] Repeat the previous part using the natural logarithm of the number of visits. Let yij be the natural logarithm of the number of visits to park j in year i (i = 1, . . . , 13, j = 1, . . . , 30). For each park, model the log-number as a simple linear regression on the centered year number: yij | β (j) , σ2 y , X ∼ indep. Nβ (j) 1 + β (j) 2 (xi − x¯), σ2 y where β (j) =β (j) 1 β (j) 2 ! j = 1, . . . , 30 xi = i i = 1, . . . , 13 Note that the coefficients are allowed to depend on the park, but the variance is not. (b) Let βˆ (j) 1 and βˆ (j) 2 be the ordinary least squares estimates of β (j) 1 and β (j) 2 , estimated for park j. You may use the lm function in R to compute these estimates. (For this part, the coefficient pairs are estimated completely separately for each park.) (i) [1 pt] Produce a scatterplot of the pairs βˆ (j) 1 , βˆ (j) 2 , j = 1, . . . , 30. (ii) [1 pt] Give the average (sample mean) of βˆ (j) 1 and also of βˆ (j) 2 . (iii) [1 pt] Give the sample variance of βˆ (j) 1 and also of βˆ (j) 2 . (iv) [1 pt] Give the sample correlation between βˆ (j) 1 and βˆ (j) 2 . (c) Consider the bivariate prior β (j) | µβ, Σβ ∼ iid N(µβ, Σβ) µβ =µβ1 µβ2 ! Σβ =σ 2 β1 ρ σβ1 σβ2 ρ σβ1 σβ2 σ 2 β2 ! with hyperpriors µβ ∼ N0, 10002 I Σ −1 β ∼ Wishart2Σ −1 0 /2 1Data from https://irma.nps.gov/STAT in the notation used in the lecture videos. For your analysis, use Σ0 =10 0 0 0.01! based on preliminary analyses. Let the prior on σ 2 y be σ 2 y ∼ Inv-gamma(0.0001, 0.0001) (i) [2 pts] List an appropriate JAGS model. Make sure to create nodes for Σβ, ρ, and σ 2 y . Remember that the numbers of visits are to be analyzed on the log scale. Now run your model using rjags. Make sure to use multiple chains with overdispersed starting points, check convergence, and monitor µβ, Σβ, σ 2 y , and ρ (after convergence) long enough to obtain effective sample sizes of at least 4000 for each parameter. (ii) [2 pts] Display the coda summary of the results for the monitored parameters. (iii) [2 pts] Give an approximate 95% central posterior interval for the correlation parameter ρ, and also produce a graph of its (estimated) posterior density. (iv) [2 pts] Approximate the posterior probability that ρ < 0. Also, compute the Bayes factor favoring ρ < 0 versus ρ > 0. (You may use the fact that ρ < 0 and ρ > 0 have equal prior probability.) Describe the level of data evidence for ρ < 0. (v) [1 pt] Your model implies that, over the 12 years from 2006 to 2018, the (population) median number of visits should have changed by a factor of e 12µβ2 Form an approximate 95% central posterior interval for this quantity. (vi) [2 pts] Use the rjags function dic.samples to compute the effective number of parameters (“penalty”) and Plummer’s DIC (“Penalized deviance”). Use at least 100,000 iterations. (d) Now consider a different model with “univariate” hyperpriors for the model coefficients, which do not allow for a coefficient correlation parameter: β (j) 1 | µβ1 , σβ1 ∼ iid N µβ1 , σ2 β1 β (j) 2 | µβ2 , σβ2 ∼ iid N µβ2 , σ2 β2 with hyperpriors µβ1 , µβ2 ∼ iid N 0, 10002 σβ1 , σβ2 ∼ iid U(0, 1000) Let the prior on σ 2 y be the same as in the previous model. (i) [4 pts] Draw a complete DAG for this new model. (ii) [2 pts] List an appropriate JAGS model. Make sure that there are nodes for σ 2 β1 , σ 2 β2 , and σ 2 y . Remember that the numbers of visits are to be analyzed on the log scale. Now run your model using rjags. Make sure to use multiple chains with overdispersed starting points, check convergence, and monitor µβ1 , µβ2 , σ 2 β1 , σ 2 β2 , σ 2 y (after convergence) long enough to obtain effective sample sizes of at least 4000 for each parameter. (iii) [2 pts] Display the coda summary of the results for the monitored parameters. (iv) [2 pts] Recall the (population) median change factor for the number of visits, e 12µβ2 as considered in the previous analysis. Form an approximate 95% central posterior interval for this quantity, and compare it with the previous results. (v) [2 pts] Use the rjags function dic.samples to compute the effective number of parameters (“penalty”) and Plummer’s DIC (“Penalized deviance”). Use at least 100,000 iterations. (vi) [1 pt] Compare the (Plummer’s) DIC values for this model and the previous one. Which is preferred? Total: 32 pts 3
1. Consider the two different hyperprior formulations for the binomial hierarchical model of Lesson 3.2: Hierarchical Modeling Fundamentals. This exercise shows how different those priors are. Note: Consult help(distributions) in R for the random number generators you will need. (You do not need JAGS.) (a) The first prior formulation was θj | α, β ∼ Beta(α, β) α, β ∼ iid Expon(0.001) (i) [2 pts] Independently simulate 1000 pairs (α, β) from their hyperprior, and produce a scatterplot of log(β) versus log(α). (ii) [2 pts] Using the simulated pairs (α, β), forward-simulate θj , and produce a histogram of the result (an approximation of its marginal prior). (b) The second prior formulation was θj | α, β ∼ Beta(α, β) α = φ1/φ2 2 β = (1 − φ1)/φ2 2 φ1 ∼ U(0, 1) φ2 ∼ U(0, 1000) (i) [2 pts] Independently simulate 1000 pairs (α, β) from their hyperprior, and produce a scatterplot of log(β) versus log(α). (ii) [2 pts] Using the simulated pairs (α, β), forward-simulate θj , and produce a histogram of the result (an approximation of its marginal prior). 2. Twelve separate case-control studies were run to investigate the potential link between presence of a certain genetic trait (the PlA2 polymorphism of the glycoprotein IIIa subunit of the fibrinogen receptor) and risk of heart attack.1 For the j th study, an estimated log-odds ratio, ψˆ j , and its (estimated) standard error, σj , were computed: j ψˆ j σj j ψˆ j σj j ψˆ j σj 1 1.055 0.373 5 1.068 0.471 9 0.507 0.186 2 -0.097 0.116 6 -0.025 0.120 10 0.000 0.328 3 0.626 0.229 7 -0.117 0.220 11 0.385 0.206 4 0.017 0.117 8 -0.381 0.239 12 0.405 0.254 1From Burr, et al. (2003), Statistics in Medicine, 22: 1741–1760. 1 Consider this Bayesian hierarchical model: ψˆ j | ψj ∼ indep. Nψj , σ2 j j = 1, …, 12 ψj | ψ0, σ0 ∼ iid N ψ0, σ2 0 j = 1, …, 12 ψ0 ∼ N0, 10002 σ0 ∼ U(0, 1000) with ψ0 and σ0 independent, and the values σj , j = 1, . . . , 12, regarded as fixed and known. (a) [2 pts] Specify improper densities that the proper hyperpriors given above are apparently intended to approximate. (Which parameters are the hyperparameters?) (b) [5 pts] Draw a directed acyclic graph (DAG) appropriate for this model. (Use the notation introduced in lecture, including “plates.”) You may draw it neatly by hand or use software. (c) [5 pts] Using the template asgn2template.bug provided on the course website, form a JAGS model statement (consistent with your graph). Also, set up any R (rjags) statements appropriate for creating a JAGS model. Be careful to name your data variables correctly. [Also remember: JAGS “dnorm” uses precisions, not variances!] (d) [5 pts] Run at least 10,000 iterations of burn-in, then 100,000 iterations to use for inference. For both ψ0 and σ 2 0 (not σ0), produce a posterior numerical summary and also graphical estimates of the posterior densities. Explicitly give the approximations of the posterior expected values, posterior standard deviations, and 95% central posterior intervals. (Just showing R output is not enough!) (e) Suppose a new case-control study is to be performed, and assume that its log-odds standard error (new σ) will be 0.125. Assume the ψ for the new study is exchangeable with those for the previous studies. (i) [2 pts] Re-draw your DAG, adding new nodes to represent the new ψˆ and new ψ. (ii) [2 pts] Correspondingly modify your JAGS model to answer the following parts. Show the modified JAGS and R code and output that you used. (iii) [3 pts] Estimate the posterior mean and posterior standard deviation, and form a 95% central posterior predictive interval for the estimated log-odds ratio that the new study will obtain. (Remember, this new estimated log-odds ratio will be the new ψˆ, not the new ψ.) (iv) [1 pt] Estimate the posterior predictive probability that the new estimated log-odds ratio will be at least twice its standard error, i.e., at least two standard errors (2σ) greater than zero. (This is roughly the posterior probability that the new study will find a statistically significant result, and in the positive direction.) Suggestion: Add an indicator variable to your JAGS model – one that equals 1 when the event occurs, and 0 otherwise. (What is its mean?) Use at least 10,000 iterations of burn-in, and 100,000 for inference as before. Total: 33 pts
1. (a) [2 pts] R script FlintGibbs.R implements a Gibbs sampler for the partially conjugate Flint data model. It is very similar to the example R code in Lesson 7.2: Gibbs Sampling. Use the script to simulate from the posterior for µ and σ 2 . Then use R function acf to produce an autocorrelation plot for the successive µ variates and an autocorrelation plot for the successive σ 2 variates. (b) R script FlintMetropolis.R implements a Metropolis sampler for the same Flint data model. It is very similar to the example R code in Lesson 7.3: Metropolis and Metropolis-Hastings. (i) [1 pt] Experiment with different settings for the proposal variance rho (by uncommenting its line and changing the value). Find a value of rho that gives an overall (average) acceptance rate of about 0.35.1 What value of rho did you find? [Warning: Using a value of rho that is too large may cause the R code to produce an error, due to numerical problems. Start with smaller values of rho.] (ii) [2 pts] With the value of rho that you found, use the script to simulate from the posterior for µ and σ 2 . Then use R function acf to produce an autocorrelation plot for the successive µ variates and an autocorrelation plot for the successive σ 2 variates. (c) [1 pt] Compare the autocorrelation plots from the previous two parts. Which method exhibited faster mixing: the Gibbs sampler or the Metropolis sampler? 2. Use the 2016 US presidential polls data in polls2016.txt to answer the following, running all parts using JAGS and R (rjags). Remember that you will have to create a variable sigma in R to represent the standard deviation of the polls, defined to be half of the margin of error. Refer to Lesson 4.2: Normal Hierarchical Model in R/JAGS. (a) Use the model in polls20161.bug for the following: (i) [2 pts] Create an initialization list (in R) supporting 4 chains, with a different initialization for each chain. Set initial values for mu to ±100 and values for tau to 100 or 0.01. Then use jags.model to create the JAGS model R object with these initializations. List all of the R code you used. (ii) [2 pts] Perform a burn-in of 2500 iterations, then monitor the mu and tau nodes for 5000 iterations (for each chain). List all of the R code you used. (iii) [3 pts] For the iterations you monitored, produce trace plots of mu and tau. Do there appear to be any convergence problems? Display the plots and R code that produced them. (iv) [2 pts] For the iterations you monitored, compute Gelman-Rubin statistics (potential scale reduction factors) for mu and tau. Do there appear to be any convergence problems? Show your R code and its output. 1This is approximately the “optimal” acceptance rate for a two-dimensional parameter. See Roberts, G. O., & Rosenthal, J. S. (2001). Optimal scaling for various Metropolis-Hastings algorithms. Statistical Science, 16, 351–367. 1 (v) [2 pts] For the iterations you monitored, display autocorrelation plots for mu and tau for one of the chains. (Hint: For example, to reference the first chain of an mcmc.list object named x, use x[[1]].) Comment on the apparent speed of mixing. (vi) [2 pts] For the iterations you monitored, compute effective sample sizes (over all chains) for mu and tau. Would they be considered adequate? Show your R code and its output. (b) Now consider a new model that uses an almost flat prior for tau on the log scale, as follows: Create a new JAGS model by modifying polls20161.bug to eliminate the current prior for tau, create a new parameter logtau with a U(−100, 100) prior distribution, and define tau to be equal to exp(logtau). (i) [2 pts] Display all of the code for your new JAGS model. (ii) [2 pts] Create an initialization list (in R) supporting 4 chains, with a different initialization for each chain. Set initial values for mu to ±100 and values for logtau to log 100 or log 0.01. Then use jags.model to create the JAGS model R object with these initializations. List all of the R code you used. (iii) [2 pts] Perform a burn-in of 2500 iterations, then monitor the mu and tau nodes for 5000 iterations (for each chain). List all of the R code you used. (iv) [3 pts] For the iterations you monitored, produce trace plots of mu and tau. Do there appear to be any convergence problems? Display the plots and R code that produced them. (v) [2 pts] For the iterations you monitored, compute Gelman-Rubin statistics (potential scale reduction factors) for mu and tau. Do there appear to be any convergence problems? Show your R code and its output. (vi) [2 pts] For the iterations you monitored, display autocorrelation plots for mu and tau for one of the chains.2 Comment on the apparent speed of mixing. (vii) [2 pts] What is wrong with this model that could explain any problems you noted? (Hint: What would happen if you used an improper flat prior on log τ?) Total: 34 pts 2Ordinarily, autocorrelation plots are not used for chains that have not converged, but you are asked to produce them here even if there was no convergence. 2
The groundbreaking 1929 paper1 by Edwin Hubble offered evidence for expansion of the universe. Astronomical observations showed that “extra-galactic nebulae” (other galaxies) tended to be moving away at a rate roughly proportional to their distance: v ≈ H0D where v is the radial velocity of the galaxy (away from us) in km/s, D is its proper distance in megaparsecs (Mpc), and H0 is called the Hubble constant. The relationship is not exact – each galaxy also has its own “peculiar velocity” that is unrelated to the expansion. File hubbledata.txt contains Hubble’s original data on 24 astronomical objects, with their assumed distance and radial velocity. (a) [2 pts] Plot the data points: radial velocity versus distance. (b) Consider a normal-theory simple linear regression model of radial velocity on distance of the form vi | β, σ2 , Di ∼ indep. Nβ1 + β2Di , σ2 i = 1, . . . , 24 Of course, the theory predicts that the intercept β1 will be exactly zero, but your initial model will not assume this. Also, according to theory, the slope β2 should be H0. Use independent priors β1, β2 ∼ iid N 0, 100002 σ 2 ∼ Inv-gamma(0.0001, 0.0001) Do not standardize or center any variables. (i) [2 pts] List an appropriate JAGS model. Now run your model. Make sure to use multiple chains with overdispersed starting points, check convergence, and monitor β1, β2, and σ 2 for at least 2000 iterations (per chain) after burn-in. (ii) [2 pts] List the coda summary of your results for β1, β2, and σ 2 . (iii) [2 pts] Give the approximate posterior mean and 95% posterior credible interval for the slope. (Does H0 appear to be positive?) (iv) [2 pts] Give the approximate posterior mean and 95% posterior credible interval for the intercept. (Does your interval contain zero?) (c) Consider the model of the previous part, but without the intercept (i.e., assuming the intercept is zero, as theory predicts). This is sometimes called regression through the origin. Use the same priors as before for the remaining parameters. 1Edwin Hubble, A Relation between Distance and Radial Velocity among Extra-Galactic Nebulae, Proceedings of the National Academy of Sciences, vol. 15, no. 3, pp. 168–173, March 1929 (i) [2 pts] List your modified JAGS model. Now run your model. Make sure to use multiple chains with overdispersed starting points, check convergence, and monitor parameters for at least 2000 iterations (per chain) after burn-in. (ii) [2 pts] List the coda summary of your results for all parameters. (iii) [2 pts] Give the approximate posterior mean and 95% posterior credible interval for the slope. (iv) [2 pts] Compare the change in the posterior mean of the slope (versus part (b)) to its posterior standard deviation. (Has it changed very much relative to the standard deviation?) Also, is its credible interval wider or narrower than before? (d) One way to check for evidence against the assumption that the intercept is zero is to produce a posterior predictive p-value based on the no-intercept model. Consider test quantity T(y, X, θ) = |cor( c ε, xD)| where cor( c ε, xD) is sample correlation between the error vector ε (not standardized) and the vector xD of distances D in the data. The larger this quantity is for the no-intercept model, the less well that model fits the data (since, if a regression model actually fits, the errors should ideally be uncorrelated with the predictor). Use your JAGS simulations from the previous part. (Suggestion: Apply as.matrix to the output of coda.samples to obtain a matrix of simulated parameter values.) (i) [2 pts] Show R code for computing the simulated error vectors ε (as rows of a matrix). (ii) [2 pts] Show R code for computing simulated replicate error vectors ε rep (as rows of a matrix), which are the error vectors for the replicate response vectors y rep . (iii) [2 pts] Show R code for computing the simulated values of T(y, X, θ) and the simulated values of T(y rep, X, θ). (iv) [2 pts] Plot the simulated values of T(y rep, X, θ) versus those of T(y, X, θ), with a reference line indicating where T(y rep, X, θ) = T(y, X, θ). (v) [2 pts] Compute the approximate posterior predictive p-value, and make an appropriate conclusion based on it. (Does it provide evidence that the no-intercept model does not fit?) Remark: Modern determinations of H0 vary around 70 (km/s)/Mpc, which is probably much different than what you obtained. Hubble’s distance data was systematically in error because he had no accurate way to measure extra-galactic distances. Total: 28 pts 2
