python autograder.py -q q2 --no-graphics

Question 3 (2 points): Exact Inference with Time Elapse

In the previous question you implemented belief updates for Pacman based on his observations. Fortunately, Pacman’s observations are not his only source of knowledge about where a ghost may be. Pacman also has knowledge about the ways that a ghost may move; namely that the ghost can not move through a wall or more than one space in one time step.

To understand why this is useful to Pacman, consider the following scenario in which there is Pacman and one Ghost. Pacman receives many observations which indicate the ghost is very near, but then one which indicates the ghost is very far. The reading indicating the ghost is very far is likely to be the result of a buggy sensor. Pacman’s prior knowledge of how the ghost may move will decrease the impact of this reading since Pacman knows the ghost could not move so far in only one move.

In this question, you will implement the elapseTime method in ExactInference. The elapseTime step should, for this problem, update the belief at every position on the map after one time step elapsing. Your agent has access to the action distribution for the ghost through self.getPositionDistribution. In order to obtain the distribution over new positions for the ghost, given its previous position, use this line of code:

newPosDist = self.getPositionDistribution(gameState, oldPos)

Where oldPos refers to the previous ghost position. newPosDist is a DiscreteDistribution object, where for each position p in self.allPositions, newPosDist[p] is the probability that the ghost is at position p at time t + 1, given that the ghost is at position oldPos at time t. Note that this call can be fairly expensive, so if your code is timing out, one thing to think about is whether or not you can reduce the number of calls to self.getPositionDistribution.

Before typing any code, we suggest you write down the equation of the inference problem you are trying to solve. The task here is a little different from the generic HMM problem described in the slides and text in that you are tracking multiple objects. However, you can think of each ghost as a separeate HMM, i.e., you don't need to tack their joint distribution.

In order to test your predict implementation separately from your update implementation in the previous question, this question will not make use of your update implementation.

Since Pacman is not observing the ghost’s actions, these actions will not impact Pacman’s beliefs. Over time, Pacman’s beliefs will come to reflect places on the board where he believes ghosts are most likely to be given the geometry of the board and ghosts’ possible legal moves, which Pacman already knows.

For the tests in this question we will sometimes use a ghost with random movements and other times we will use the GoSouthGhost. This ghost tends to move south so over time, and without any observations, Pacman’s belief distribution should begin to focus around the bottom of the board. To see which ghost is used for each test case you can look in the .test files.

You may find the diagram below showing Bayes Net/ Hidden Markov model for what is happening helpful in organizing your thoughts. Still, you should rely on the above description for implementation because some parts are implemented for you (i.e. getPositionDistribution is abstracted to be $P(G_{t+1} \mid gameState, G_t))$.

To run the autograder for this question and visualize the output:

python autograder.py -q q3

If you want to run this test (or any of the other tests) without graphics you can add the following flag:

python autograder.py -q q3 --no-graphics

As you watch the autograder output, remember that lighter squares indicate that pacman believes a ghost is more likely to occupy that location, and darker squares indicate a ghost is less likely to occupy that location. For which of the test cases do you notice differences emerging in the shading of the squares? Can you explain why some squares get lighter and some squares get darker?

Question 4 (1 point): Exact Inference Full Test

Now that Pacman knows how to use both his prior knowledge and his observations when figuring out where a ghost is, he is ready to hunt down ghosts on his own. We will use your observeUpdate and elapseTime implementations together to keep an updated belief distribution, and your simple, greedy agent will choose an action based on the latest ditsibutions at each time step. In the simple greedy strategy, Pacman assumes that each ghost is in its most likely position according to his beliefs, then moves toward the closest ghost. Up to this point, Pacman has moved by randomly selecting a valid action.

Implement the chooseAction method in GreedyBustersAgent in bustersAgents.py. Your agent should first find the most likely position of each remaining uncaptured ghost, then choose an action that minimizes the maze distance to the closest ghost.

To find the maze distance between any two positions pos1 and pos2, use self.distancer.getDistance(pos1, pos2). To find the successor position of a position after an action:

successorPosition = Actions.getSuccessor(position, action)

You are provided with livingGhostPositionDistributions, a list of DiscreteDistribution objects representing the position belief distributions for each of the ghosts that are still uncaptured.

If correctly implemented, your agent should win the game in q8/3-gameScoreTest with a score greater than 700 at least 8 out of 10 times. Note: the autograder will also check the correctness of your inference directly, but the outcome of games is a reasonable sanity check.

We can represent how our greedy agent works with the following modification to the previous diagram. The arc from the previous time step obseravtions to the pacman state reflects how Pacman is making his action choices. (Not everybody will find this sort of visualization helpful, so don't let it confuse you if you alread feel confident in how you are thinking about this problem.)

To run the autograder for this question and visualize the output:

python autograder.py -q q4

If you want to run this test (or any of the other tests) without graphics you can add the following flag:

python autograder.py -q q4 --no-graphics

ML Introduction

This part of the assignment is a brief introduction to machine learning; you will build a neural network for nonlinear regression and handwritten digit classification.

The code for this part of the assignment contains the following files, available as a zip archive.

Files to Edit and Submit: You will fill in portions of models.py during the assignment. Please do not change the other files in this distribution or submit any of our original files other than this file.

Discussion: Please be careful not to post spoilers.

Installation

If the following runs and you see the below window pop up where a line segment spins in a circle, you can skip this section. You should use the conda environment for this since conda comes with the libraries we need.

python autograder2.py --check-dependencies

For this assignment, you will need to install the following two libraries:

• numpy, which provides support for fast, large multi-dimensional arrays.
• matplotlib, a 2D plotting library.

If you have a conda environment, you can install both packages on the command line by running:

conda activate [your environment name]

pip install numpy
pip install matplotlib

You will not be using these libraries directly, but they are required in order to run the provided code and autograder.

If your setup is different, you can refer to numpy and matplotlib installation instructions. You can use either pip or conda to install the packages; pip works both inside and outside of conda environments.

After installing, try the dependency check.

Provided Code (Part I)

For this part of the assignment, you have been provided with a neural network mini-library (nn.py) and a collection of datasets (backend.py).

The library in nn.py defines a collection of node objects. Each node represents a real number or a matrix of real numbers. Operations on node objects are optimized to work faster than using Python’s built-in types (such as lists).

Here are a few of the provided node types:

• nn.Constant represents a matrix (2D array) of floating point numbers. It is typically used to represent input features or target outputs/labels. Instances of this type will be provided to you by other functions in the API; you will not need to construct them directly.
• nn.Parameter represents a trainable parameter of a perceptron or neural network.
• nn.DotProduct computes a dot product between its inputs. Additional provided functions:

nn.as_scalar can extract a Python floating-point number from a node. When training a perceptron or neural network, you will be passed a dataset object. You can retrieve batches of training examples by calling dataset.iterate_once(batch_size):

for x, y in dataset.iterate_once(batch_size):
    ...

For example, let’s extract a batch of size 1 (i.e., a single training example) from the perceptron training data:

>>> batch_size = 1
>>> for x, y in dataset.iterate_once(batch_size):
...     print(x)
...     print(y)
...     break
...
<Constant shape=1x3 at 0x11a8856a0>
<Constant shape=1x1 at 0x11a89efd0>

The input features x and the correct label y are provided in the form of nn.Constant nodes. The shape of x will be batch_size x num_features, and the shape of y is batch_size x num_outputs. So, each row of x is a point/ sample, and a column is the same feature of some samples. Here is an example of computing a dot product of x with itself, first as a node and then as a Python number.

>>> nn.DotProduct(x, x)
<DotProduct shape=1x1 at 0x11a89edd8>
>>> nn.as_scalar(nn.DotProduct(x, x))
1.9756581717465536

Finally, here are some formulations of matrix multiplication (you can do some examples by hand to verify this). Let $\mathbf A$ be an $m \times n$ matrix and $\mathbf B$ be $n \times p$; matrix multiplication works as follows:

• As a sanity check, the dimensions are what we expect them to be, and the inner dimension of $n$ is preserved for any remaining matrix multiplications.
• This is useful to see what happens when we multiply a batch matrix $X$ by a weight matrix $W$, we are just multiplying each sample one at a time by the entire weight matrix via the first formulation. Within each sample times weights, we are just getting different linear combinations of the sample to go to each result column via the second formulation. Note that as long as the dimensiosn match, $A$ can be a row vector and $B$ a column vector.

Neural Network Tips

To implement the neural networks for this assignment, you will need to to implement the following models:

• Q5: Non-linear Regression
• Q6: Handwritten Digit Classification

Building Neural Nets

For the remainder of this assignment, you’ll use the framework provided in nn.py to create neural networks to solve a variety of machine learning problems. A simple neural network has linear layers, where each linear layer performs a linear operation (just like perceptron). Linear layers are separated by a non-linearity, which allows the network to approximate general functions. We’ll use the ReLU operation for our non-linearity, defined as $\text{relu}(x)=\max(x,0)$. For example, a simple one hidden layer/ two linear layers neural network for mapping an input row vector $\mathbf x$ to an output vector $\mathbf f(\mathbf x)$ would be given by the function:

where we have parameter matrices $\mathbf{W_1}$ and $\mathbf{W_2}$ and parameter vectors $\mathbf{b_1}$ and $\mathbf{b_2}$ to learn during gradient descent. $\mathbf{W_1}$ will be an $i \times h$ matrix, where $i$ is the dimension of our input vectors $\mathbf{x}$, and $h$ is the hidden layer size. $\mathbf{b_1}$ will be a size $h$ vector. We are free to choose any value we want for the hidden size (we will just need to make sure the dimensions of the other matrices and vectors agree so that we can perform the operations). Using a larger hidden size will usually make the network more powerful (able to fit more training data), but can make the network harder to train (since it adds more parameters to all the matrices and vectors we need to learn), or can lead to overfitting on the training data.

We can also create deeper networks by adding more layers, for example a three-linear-layer net:

Or, we can decompose the above and explicitly note the 2 hidden layers:

Note that we don’t have a $\text{relu}$ at the end because we want to be able to output negative numbers, and because the point of having $\text{relu}$ in the first place is to have non-linear transformations, and having the output be an affine linear transformation of some non-linear intermediate can be very sensible.

Batching

For efficiency, you will be required to process whole batches of data at once rather than a single example at a time. This means that instead of a single input row vector $\mathbf{x}$ with size $i$, you will be presented with a batch of $b$ inputs represented as a $b \times i$ matrix $\mathbf{X}$. We provide an example for linear regression to demonstrate how a linear layer can be implemented in the batched setting.

Randomness

The parameters of your neural network will be randomly initialized, and data in some tasks will be presented in shuffled order. Due to this randomness, it’s possible that you will still occasionally fail some tasks even with a strong architecture – this is the problem of local optima! This should happen very rarely, though – if when testing your code you fail the autograder twice in a row for a question, you should explore other architectures.

Designing Architecture

Designing neural nets can take some trial and error. In the questions below, we give you some specific tips that should work pretty well, but we also include here some general tips for how to think about this issue:

• Be systematic. Keep a log of every architecture you’ve tried, what the hyperparameters (layer sizes, learning rate, etc.) were, and what the resulting performance was. As you try more things, you can start seeing patterns about which parameters matter. If you find a bug in your code, be sure to cross out past results that are invalid due to the bug.
• Start with a shallow network (just one hidden layer, i.e. one non-linearity). Deeper networks have exponentially more hyperparameter combinations, and getting even a single one wrong can ruin your performance. Use the small network to find a good learning rate and layer size; afterwards you can consider adding more layers of similar size.
• If your learning rate is wrong, none of your other hyperparameter choices matter. You can take a state-of-the-art model from a research paper, and change the learning rate such that it performs no better than random. A learning rate too low will result in the model learning too slowly, and a learning rate too high may cause loss to diverge to infinity. Begin by trying different learning rates while looking at how the loss decreases over time.
• Smaller batches require lower learning rates. When experimenting with different batch sizes, be aware that the best learning rate may be different depending on the batch size.
• Refrain from making the network too wide (hidden layer sizes too large) If you keep making the network wider accuracy will gradually decline, and computation time will increase quadratically in the layer size – you’re likely to give up due to excessive slowness long before the accuracy falls too much. The full autograder for all parts of the assignment takes a few minutes to run with staff solutions; if your code is taking much longer you should check it for efficiency.
• If your model is returning Infinity or NaN, your learning rate is probably too high for your current architecture.

Provided Code (Part II)

Here is a full list of nodes available in nn.py. You will make use of these in the remaining parts of the assignment:

• nn.Constant represents a matrix (2D array) of floating point numbers. It is typically used to represent input features or target outputs/labels. Instances of this type will be provided to you by other functions in the API; you will not need to construct them directly.
• nn.Parameter represents a trainable parameter of a perceptron or neural network. All parameters must be 2-dimensional.
  • Usage: nn.Parameter(n, m) constructs a parameter with shape n by m.
• nn.Add adds matrices element-wise.
  • Usage: nn.Add(x, y) accepts two nodes of shape batch_size by num_features and constructs a node that also has shape batch_size by num_features.
• nn.AddBias adds a bias vector to each feature vector. Note: it automatically broadcasts the bias to add the same vector to every row of features.
  • Usage: nn.AddBias(features, bias) accepts features of shape batch_size by num_features and bias of shape 1 by num_features, and constructs a node that has shape batch_size by num_features.
• nn.Linear applies a linear transformation (matrix multiplication) to the input.
  • Usage: nn.Linear(features, weights) accepts features of shape batch_size by num_input_features and weights of shape num_input_features by num_output_features, and constructs a node that has shape batch_size by num_output_features.
• nn.ReLU applies the element-wise Rectified Linear Unit nonlinearity $\text{relu}(x)=\max(x,0)$. This nonlinearity replaces all negative entries in its input with zeros.
  • Usage: nn.ReLU(features), which returns a node with the same shape as the input.
• nn.SquareLoss computes a batched square loss, used for regression problems.
  • Usage: nn.SquareLoss(a, b), where a and b both have shape batch_size by num_outputs.
• nn.SoftmaxLoss computes a batched softmax loss, used for classification problems. softmax is a way of producing smooth, differentiable approximation to max.
  • Usage: nn.SoftmaxLoss(logits, labels), where logits and labels both have shape batch_size by num_classes. The term “logits” refers to scores produced by a model, where each entry can be an arbitrary real number. The labels, however, must be non-negative and have each row sum to 1. Be sure not to swap the order of the arguments!
• Do not use nn.DotProduct for any model other than the perceptron.

The following methods are available in nn.py:

• nn.gradients computes gradients of a loss with respect to provided parameters.
  • Usage: nn.gradients(loss, [parameter_1, parameter_2, ..., parameter_n]) will return a list [gradient_1, gradient_2, ..., gradient_n], where each element is an nn.Constant containing the gradient of the loss with respect to a parameter.
• nn.as_scalar can extract a Python floating-point number from a loss node. This can be useful to determine when to stop training.
  • Usage: nn.as_scalar(node), where node is either a loss node or has shape (1,1).

The datasets provided also have two additional methods:

• dataset.iterate_forever(batch_size) yields an infinite sequences of batches of examples.
• dataset.get_validation_accuracy() returns the accuracy of your model on the validation set. This can be useful to determine when to stop training.

Example: Linear Regression

As an example of how the neural network framework works, let’s fit a line to a set of data points. We’ll start four points of training data constructed using the function $y=7x_0+8x_1+3$. In batched form, our data is:

Suppose the data is provided to us in the form of nn.Constant nodes:

>>> x
<Constant shape=4x2 at 0x10a30fe80>
>>> y
<Constant shape=4x1 at 0x10a30fef0>

Let’s construct and train a model of the form $f(\mathbf x)=x_0\cdot m_0+x_1 \cdot m_1+b$. If done correctly, we should be able to learn that $m_0=7$, $m_1=8$, and $b=3$.

First, we create our trainable parameters. In matrix form, these are:

Which corresponds to the following code:

m = nn.Parameter(2, 1)
b = nn.Parameter(1, 1)

Printing them gives:

>>> m
<Parameter shape=2x1 at 0x112b8b208>
>>> b
<Parameter shape=1x1 at 0x112b8beb8>

Next, we compute our model’s predictions for $y$:

xm = nn.Linear(x, m)
predicted_y = nn.AddBias(xm, b)

Our goal is to have the predicted $y$-values match the provided data. In linear regression we do this by minimizing the square loss:

We construct a loss node:

loss = nn.SquareLoss(predicted_y, y)

In our framework, we provide a method that will return the gradients of the loss with respect to the parameters:

grad_wrt_m, grad_wrt_b = nn.gradients(loss, [m, b])

Printing the nodes used gives:

>>> xm
<Linear shape=4x1 at 0x11a869588>
>>> predicted_y
<AddBias shape=4x1 at 0x11c23aa90>
>>> loss
<SquareLoss shape=() at 0x11c23a240>
>>> grad_wrt_m
<Constant shape=2x1 at 0x11a8cb160>
>>> grad_wrt_b
<Constant shape=1x1 at 0x11a8cb588>

We can then use the update method to update our parameters. Here is an update for m, assuming we have already initialized a multiplier variable based on a suitable learning rate of our choosing:

m.update(grad_wrt_m, multiplier)

If we also include an update for b and add a loop to repeatedly perform gradient updates, we will have the full training procedure for linear regression.

Question 5 (6 points): Non-linear Regression

For this question, you will train a neural network to approximate $\sin(x)$ over $[-2\pi, 2\pi]$.

You will need to complete the implementation of the RegressionModel class in models.py. For this problem, a relatively simple architecture should suffice (see Neural Network Tips for architecture tips). Use nn.SquareLoss as your loss.

Your tasks are to:

• Implement RegressionModel.__init__ with any needed initialization.
• Implement RegressionModel.run to return a batch_size by 1 node that represents your model’s prediction.
• Implement RegressionModel.get_loss to return a loss for given inputs and target outputs.
• Implement RegressionModel.train, which should train your model using gradient-based updates.

There is only a single dataset split for this task (i.e., there is only training data and no validation data or test set). Your implementation will receive full points if it gets a loss of 0.02 or better, averaged across all examples in the dataset. You may use the training loss to determine when to stop training (use nn.as_scalar to convert a loss node to a Python number). Note that it should take the model a few minutes to train.

Suggested network architecture: Normally, you would need to use trial-and-error to find working hyperparameters. Below is a set of hyperparameters that worked for us, but feel free to experiment and use your own.

• Hidden layer size 512
• Batch size 200
• Learning rate 0.05
• One hidden layer (2 linear layers in total)

python autograder2.py -q q5 

Here's how to understand the visualization provided by the autograder: The blue curve shows the true function that you are trying to learn. The red line shows what your neural network has learned.

Question 6 (6 points): Digit Classification

For this question, you will train a network to classify handwritten digits from the MNIST dataset.

Each digit is of size 28 by 28 pixels, the values of which are stored in a 784-dimensional vector of floating point numbers. Each output we provide is a 10-dimensional vector which has zeros in all positions, except for a one in the position corresponding to the correct class of the digit. This means that the last layer of your network should be of type nn.parameter(1,10).

Complete the implementation of the DigitClassificationModel class in models.py. The return value from DigitClassificationModel.run() should be a batch_size by 10 node containing scores, where higher scores indicate a higher probability of a digit belonging to a particular class (0-9). You should use nn.SoftmaxLoss as your loss. Do not put a ReLU activation in the last linear layer of the network.

For both this question and Q4, in addition to training data, there is also validation data and a test set. You can use dataset.get_validation_accuracy() to compute validation accuracy for your model, which can be useful when deciding whether to stop training. The test set will be used by the autograder.

To receive points for this question, your model should achieve an accuracy of at least 97% on the test set. For reference, our staff implementation consistently achieves an accuracy of 98% on the validation data after training for around 5 epochs. Note that the test grades you on test accuracy, while you only have access to validation accuracy – so if your validation accuracy meets the 97% threshold, you may still fail the test if your test accuracy does not meet the threshold. Therefore, it may help to set a slightly higher stopping threshold on validation accuracy, such as 97.5% or 98%.

Suggested network architecture: Normally, you would need to use trial-and-error to find working hyperparameters. Below is a set of hyperparameters that worked for us, but feel free to experiment and use your own.

• Hidden layer size 200
• Batch size 100
• Learning rate 0.5
• One hidden layer (2 linear layers in total)

To test your implementation, run the autograder2:

python autograder2.py -q q6
  

Here's how to understand the visualization provided by the autograder: Each row corresponds to one digit. The digits are placed horizontally on the row according to the probability assigned by the softmax function. If a digit is classified correctly, it is shown in green. If it is classified incorrectly, it is shown in red and the label assigned to it is shown underneath. Note that it's possible for a correctly classified digit to be assigned the correct label with probability less than 0.5 since the remaining 9 digits could still be assigned lower probabilty by softmax.

Submission

Submit inference.py, bustersAgents.py and models.py to Homework 4 Coding on Gradescope.

python submission_autograder.py