Overview

• Constructs random mazes using Kruskal’s algorithm and Union Find.
• Displays the maze and animates both depth first and breadth first search for the solution.
• Allow the user to traverse the maze manually
• Shows many different visualizations of the maze

Skills Demonstrated

• Algorithms: Utilized 3 algorithms in the implementation of this project: Kruskal’s Minimum Spanning tree, Depth first search, and Breadth first search.
• Protected Object Oriented Design: All fields in this project were final, which ensured flexible programming and mimimal dependencies when working with interconnected classes.
• Graphs, Hashmaps, Trees, and Arraylists: Maze was constructed and worked with as a Graph, required use of different data structures to best accomplish goals.

Data Structure

In order to implement a mimimum spanning tree algorithm, the maze consisted of two main classes:

• Cells: Represent each square of the maze or nodes in a graph, contains fields for all 4 (or 6) edges.
• Edges: Represent the edges between cells or connections within a graph, contains fields for to and from cells as well as weight for generation.

Both cells and edges are handled by a central maze class, which has the following properties:

• A 2-dimensional ArrayList of Cells representing the maze.
• A Hashmap<Cell, Cell> for defining groups for the union/find data structure.
• An ArrayList of Edges representing all the edges that could be in the maze.
• An ArrayList of Edges representing the edges that make up the maze.
• A Worklist for the current seach algorithm.
• A Hashmap<Cell, Cell> that defines a the solution path cell by cell from start to finish.

Functionality

• To Generate the maze, edges were constructed between every adjacent cell, and given a random weight. From there, the cells and edges were equivalient to nodes and connections on a graph, and kruskals algorithm could be used to find edges that would create one and only one path between every node, creating a maze.
  This process consisted of splitting each cell into groups, and then combining groups with single connections until every cell was in the same group. By connecting edges with the highest weight first, the produced maze was random.
• To solve the maze, the algorithm started with a cell (the top left), and used the edges on that cell to add connected cells to a worklist. From here, cells were pulled from the worklist and processed. The only difference between breadth first and depth first search is whether the cells are pulled from the start or the end of the worklist.

Additional Features

Because the maze generation was based on the weight of the edges, it is possible to create mazes with biases in different directions by changing the randomess of the weights. For example, below are mazes with 75% (left) and 100% (right) vertical bias on edges. (Note that even with 100% bias, there must still be some horizontal connections to make a viable maze.)

Another added feature to this project is the ability for cells to know their distance within the maze to other cells. Below are mazes with each cell colored in a gradient from red to blue with the distance from either the start (left) or the end (right). Note that these are not just reversed maps of each other due to the nature of trees/mazes.

Finally, the most complex addition to this project was hexagonal mazes. Because from a graph perspective hexagonal mazes are no more complex than square mazes, most of the code did not have to be changed, but many of the processes (including cells and edges) had to be abstracted to allow for the new layout.

*This project was done in collaboration with Zach Croft*

*All code for any project is available upon request*

Gameplay

• Board can be any size or shape, as long as it is made of blocks. Every board has one exit on it denoted by the black square.
• There are three types of pieces, a target piece, cars, and trucks.
  • The target piece is 2 blocks long and either horizontal or vertical.
  • Trucks are 3 blocks long and either horizontal or vertical.
  • Cars are 2 blocks long and either horizontal or vertical.
• All pieces can only move forward or backward in the direction they are facing.
• Pieces and walls cannot collide with each other, only the target piece can enter the exit, at which point the game is won.

Skills Demonstrated

• Object Oriented Design: Various different objects that interact with each other and are all controlled in a game class. Allows for customizability while also preventing impossible game states.
• Flexible Programming: Started off with minimum viable game, and worked up in complexity adding features. This forced the design to be flexible and easy to modify/work with.
• Control Over Aliasing and Mutability: Utilized aliasing and mutable states to simplify code. Involved keeping track of objects and understanding of Java mutibility.
• User Interface: Needed easy way to build and play complex levels, ended up using text parser. Also required work with game display and mouse/keyboard controls.

Data Structure

The class structure of this game was designed as follows:

• Level: Controls all gameplay, pieces, and functionality
• Piece (Abstract): represents any piece or wall in the game.
  • Vehicle (extends Piece): represents cars or trucks that move horizontally or vertically.
  • Exit (extends Piece): represents the exit of the game.
  • Wall (extends Piece): represents wall on the edge that cannot move.
• Interval: represents the space that any piece occupies and handles collisions and drawing.
• Move: represents a move by the player that is stored to allow for undoing moves.

Because there can be any number of pieces in a given game, and it is useful to be able to access all the pieces at once for collision purposes, the Level object has an arrayList<Piece> of all the pieces. However, because it is also useful to be able to access the selected, target, and exit pieces individually, they are also fields of the Level object. For all three of these, one piece is aliased as both a piece in the pieces array list, and an individual field. This aliasing is best understood in the diagram below:

                     +-------------------+
                     |       Level       |
                     | selectedPiece  ---|--------+
                     | targetPiece  -----|---+    |
                     | exitPiece  -------|-+ |    |
                 +---|--- pieces         | | |    |
                 |   +-------------------+ | |    |
       	         |           +-------------+ |	  |
       	         |           |	             |    |
       	         |           |	       +-----+	  |
       	         |           |	       |          |
       	         |           |	       |          |
    ArrayList of Pieces:     |         |          |
    +------------------------+---------+----------+-----------------------+
    |         |         |    |    |    |    |     |   |         |         |
    |         |         |    |    |    |    |     |   |         |         |
    | Apiece1 | Apiece2 | Apiece3 | Apiece4 | Apiece5 | Apiece6 | Apiece7 |
    |         |         |         |         |         |         |         |
    |         |         |         |         |         |         |         |
    +---------------------------------------------------------------------+

Other Relvant Design Decisions

• Every Piece has an Interval field, which allows all of the collision and drawing code to be universal for every piece.
• In order to easily create new levels, a text parser takes in a string and constructs levels using it. A sample string would look like:

String testlvl = "|||----+\n"
                 + "|||t  T|\n"
                 + "|| C   |\n"
                 + "|g     X\n"
                 + "|t     |\n"
                 + "|    C  |\n"
                 + "|     c  |\n"
                 + "+--------+";

Where t or c correspond to trucks or cars, g is the target car, the capitalization determines the orientation, and X is the exit.

• In order to support undos, a Previous Move object stores a given piece, and a copt of the interval that it started at for a given move. Then, to undo moves, the level stores an array list of all the previous moves, moving pieces back to their original internvals. This saves space as only one interval must be stored for every move.
• There are many checks in the level class that ensure that impossible states of the game are not reached. These were useful in the development process particularly with the aliasing of the pieces.

Additional Functionality

• As a variation on this game, a version was made that allows for any size pieces that can move horizontally or vertically.
  
• This second version was also made only using additional classes that extend a Piece, so a game with a combination of rules could aso be made.
• The game has a move counter in the top left that keeps track of the number of moves the player has made. Undoing does not decrease this move counter

*This project was done in collaboration with Zach Croft*

*All code for any project is available upon request*

Functionality

• Use the color differences between neighboring pixels to compute an “energy” for each pixel, determining how important it is to the image.
• Find the path from top to bottom (or left to right) on the image that removes the least amount of total energy worth of pixels.
• Remove that “seam” of pixels while maintaing the shape of the data, storing it so that the seam can be added back into the image in the future.

Constraints

• Speed:
  • Required a solution that did not involve the recalculation of every pixels energy every time, as only a subset of pixels would need to be updated.
  • Pixels needed easy way to access neighbors.
  • Because seams could be diagonal, could not compare every posssible seams energy loss. Required dynamic programming approach.
• Data Structure:
  • Representation of image needed ability to change size while still being able to access every pixel.
  • Abstracting the removal vertical/horizontal seams required a specific class structure with the ability to iterate through rows or columns
  • In order to accomodate for the needs of the project, utilized a 2-dimensional Deque with custom sentinels and buffers

Skills Demonstrated

• Object Oriented Design: utilized interfaces, abstract classes, and inheiritance within a complex object design that allowed for an elegant solution.
• Linked Lists: Using a 2-dimensional Deque to represent data meant no direct acces to individual pixels, and every pixel could only be accessed through neighboring pixels or helper pieces (sendinels on the top and left, buffers on the right and bottom).
• Dynamic programming: Used a heavily accumulator based algorithm to compute the seams of the image from the top down as opposed to bottom up.

Computation Tequinique

The process of removing a seam essentially breaks down into three steps:

• Compute the “energy” of each pixels, which represents how different that pixels brightness is compared to its 8 neighbors. - For each pixel, let the brightness of the 8 neighbors on a scale from 0 to 1 be denoted by TL, TM, TR, ML, MR, BL, BM, BR. The horizontal, vertical, and total energy of any pixel can be defined as: \(\begin{equation} Horizontal Energy = (TL+2ML+BL)-(TR+2MR+BR) \end{equation}\) \(\begin{equation} Vertical Energy = (TL+2TM+TR)-(BL+2BM+BR) \end{equation}\) \(\begin{equation} Energy = \sqrt{Horizontal Energy^2 + Vertical Energy^2} \end{equation}\)
• Find a path of pixels from top to bottom (or left to right) with the least possible combined energy of all pixels in the path. This is called a seam in this project.
  • Start with the top row (or left column), every pixels seam of least energy down to it from the top is only its own energy. Store this value in each of the pixels as the total seam weight.
  • Go to the next row below (or column to the right), for each pixel, find the pixel above it (either TL, TM, or TR) with the lowest total seam weight. Add that weight and its energy to produce its total seam weight. Store the pixel above it with the least seam weight as a field in the pixel.
  • repreat this process until the last row is calculated, at which point every pixel in the bottom row (or right column), will have the total weight of the least expensive seam that ends with that pixel. Find the pixel with the least total weight, and use the stored pixels above it to have a linked list of the seam with the least total energy of the entire image.
  • For a grid of pixels with the energies on the left, this calculation would look like:
    
• remove the seam, fixing the data structure and making necessary re-calculations along the way.
  • Go through the linkedlist of the least costly seam, and have each pixel remove itself.
  • Pixels will fix their left/right connections, and connections below them. Cannot fix connections above as there are pixels above that have not been removed yet.
  • recalculate the energies of only the pixels 2 to the left or right of every removed pixel as these are the only pixels in the image whose energies can be changed.

Adding the seams back is then just a matter of saving the lead sentinel for each seam, along with its position in the sentinel arraylist (described below). Then, the sentinel can be inserted back into the arraylist, and tell each of the pixels in the seam to re-connect themselves. This works because removed seams still point at pixels in the image, but those pixels do not point at it after its removal.

Data Structure

The Core class structure of this project is designed as follows:

• Grid Piece (interface): represents any piece that a pixel can be pointed to by a pixel
  • Edge Pieces (abstract, implements Grid Piece): represents any grid pieces that boarders the grid of pixels
    • Row Sentinel (extends Edge Piece): represents a sentinel at the Left of each row that points right to the first pixel of that specific row.
    • Column Sentinel (extends Edge Piece): represents a sentinel at the top of each column that points down to the top pixel of that specific column.
    • Buffer (extends Edge Piece): represents a piece that pixels on the right/bottom edge point to for their right/down fields
  • Pixel (implements Grid Piece): points to its four neighboring grid pieces in each cardinal direction
• Image Graph: represents an image, contains two ArrayLists, rows and columns, which each contain the row and column sentinelsthat point into the image.
• Seam Info: associated with each Pixel, keeps track of the path of the seam that pixel is in, as well as the total weight of the seam to that point.

With this design, everything can be accessed via a given image graph object, which can use its row or column sentinels to interate through the image either row by row or column by column. This idea is best understood with the diagram below:

In general, most of the process described above are then done by iterating through either the row or column arraylist, and retrieving an iterable from each sentinel that contains every pixel in that row/column. This means a method can easily be called on every pixel. It is also important to note that the first and last row/column are also very easily accessable, making seam calculation/removal much simpler.

Bells and Whistles

In addition to displaying the normal image, there is also an option to display either the energies of each pixel, or the total weight of the minimum seam up to any given pixel in the image. Note that for the total weight, the image will get progressively lighter as the weight inevitably increases, but the darkest path from top to bottom represents the path of least resistance, highlighted by the red line.

*This project was done in collaboration with Zach Croft*

*All code for any project is available upon request*

Model Properties

This model aimed to predict store sales for various different products given a variety of data. In practice, a model like this could help optomize inventory and logistics, decrease food waste, and lower consumer prices. The main topics explored in this project include:

• Exploratory Data Analysis (EDA) to determine best approach
• Encoding: the process of turning categorical data points into numerical ones that can be processed by a model.
• Testing and exploring a variety of different models to produce optimal results
• Adding features to work with trends over time

Skills Demonstrated

• Data Analysis: Required work with large amounts of data. Cleaning, refactoring, and modifying this data properly was necessary for success.
• Machine Learning Techniques: Learned about and implemented many different machine learning techniques which lead to a deep understanding of how time series models function.
• Trial and Error Approach: This project involved testing with many different tecchniques and seeing what worked, which meant developing quick solutions for testing and thorough solutions for the final product.

Data Cleaning

This project began with a lot of data, much of which had to be processed. The data supplied for this project was incredibly detailed, ranging from the price of oil at any given time to clusters of stores around the countrie to local and regional holidays. All of this had to at a minimum be converted into numerical data, and in many cases also processed with other tools. Below is a snap shot of what some of this data looked like.

The most essential part of data cleaning is converting all of the data into numerical data, as a model cannot take in the name of a city as an input for example. To do this, non-numerical data must be encoded into numbers. There are many ways to do this, but some approaches are much better than others depending on your data. We tried the following three methods, and settled on a mix of one-hot encoding and target mean encoding depending on the type of data we were dealing with.

• Method 1: Ordinal Encoding
  • For every value, assign a unique integer based on its “importance”
  • Pros: uses least memory, easy to implement
  • Cons: Only works for values that can be ranked easily
• Method 2: One-Hot Encoding
  • For every value, there is a field for each data point representing either “has this value”: 1 or “doesn’t have this value”: 0
  • Pros: works well for values with equal importance
  • Cons: impractical for large set of values, increases memory and training time
• Method 3: Target Mean Encoding
  • For every value, encode it as the mean of another numerical value related to it (for example families of products could be encoded as the average number of sales in that famil as seen below)
  • Pros: low memory cost and fast training times
  • Cons: reduces data to one dimentional relationship

Below are visualizations of these three methods, Ordinal (left), One-Hot (right), and Target Mean (bottom).

Choosing a Model

For this problem, we settled on utilizing xgbost to build our model. There are many things that make this model an excellent candidate for any project, but one of the main things that likely set it appart from other methods that we tried was its ability to utilize regression trees and random forests.

As seen in the image above to the left, a regression tree is a tree of decisions that can be ran through to reach a conclusion. In the example above, it is used to determine the effectiveness of a drug, which might be an example of how human made decision trees work. However, ML models can also create regression trees, which are particularly powerful when combined with random forests, shown on the right. Random forsts are a method by which models randomly generate regression trees and modify them to become better and better using gradient decent. There is a lot of advanced math hidden within the model, but the image below provides some surface level insights into this process.

The last step of using this model is hypertuning. Because the model takes in a number of different parameters to determine how it learns, hypertuning allows us to try out a range of these parameters and hone in on the ones that produce the best result.

Trend and Seasonality

So far, the model could be used for any kind of data. But there are many properties of temporal data that can be taken advantage of. For example, we would expect people to shop more on the weekend, or during holidays. To take these factors into consideration, we need to look at trends over time within the data.

• On the left, a periodogram provides valuable data about what time periods the data with. It does this by fitting sin waves with different periods to the data, and graphing how well the sin wave matches the data. As expected, there is a large spike in the weekly period, but there are also other spikes that can be used to increase the accuracy of the model.
• On the right, some plots of total sales allow us to directly see the trends followed across the whole year or each week. If we were unsure whether or not there would be temporal trends in the data, this would be one way to look and see.

To actually improve the model with this information, we use fourier features. These are combinations of sin and cosine curves that allow the model to fit to the data, as seen below. The number sin and cos functions determine the accuracy of the curve, but more functions comes at the cost of computation and overfitting. We ended up using 3 sin/cos pairs.

Implementing time series attributes in our model more than doubled its effectiveness, which shows how important these ideas are when it comes to machine learning. In the end, our model placed in the top 20 of 603 participants in the kaggle competition we entered, performing only 9% worse than the best model.

*This project was done in collaboration with Artur Savchii and David Simane*

*All code for any project is available upon request*

Network Properties

• This neural network uses stochastic gradient descent to optomize a cost function and learn how to recognize handwritten digets.
• The network has two mprimary layers, dense layers which are good at detecting patterns between independent variables, and convolution layers which are good at detecting patterns in images.
• The network also has additional layers such as activation layers, reshaping layers, and pooling layers.
• All of these layers are module, so the network will work with any combination, shape, and number of these layers.
• The best performing network was able to classify the handwritten digits in a test set with an accuracy of 97.98%.

Skills Demonstrated

• Understanding of Neural Network Functionality: This project required a deep understanding of the inner workings of convolutional neural networks, including cost functions, backpropogation, and matrix computations.
• Math Intensive Coding and Debugging: With heavily math based operations and lots of room for small errors, there was significant work put into accurately testing and ensuring that the network functioned properly.
• Modular Design and Adjustability: Different problems require different layers, sizes, and parameters. All of the code for this project was designed to be as modular and adjustable as possible.

How Stochastic Gradient Descent Models Work

• Stochastic Gradient Descent (SDG) passes inputs through a series of computations (layers) to produce an output.
• Inputs, layers, and outputs consist of neurons, which are “activated” on a scale from 0 to 1.
• These layers consist of variables which effect the computation on the outputs, which are adjusted to let the network “learn”.
• Because all the computations are continuous, they can be adjusted using their derivatives to slowly decrease a cost function which determines how good the network is, a process known as gradient descent.

Error BackPropogation

• Because layers are often stacked on top of each other, many parameters effect the cost through many other layers. To find the partial derivative of these parameters, the chain rule is used.
• If you have a parameter P, a neuron activation N, and a cost C: \(\begin{equation} {∂C \over ∂N}{∂N \over ∂P} = {∂C \over ∂P} \end{equation}\)
• The derivative with respect to the output of the previous layer is known as the error. The process then repeats for as many layers as the network has; backpropagating the error.
• With the error, each parameter can be moved a small amount to reduce the error. The ammount each is moved is known as the learning rate.
• This idea of propogating the error backwards from the end of the network is core to how SDGs work, and fundamentally boils down to one line of code:

for layer in reversed(self.network):
    vector = layer.backpropogateError(vector, learningRate/batchSizes, pushUpdate)

Cost Function

A critical part of gradient descent is having a function to optimize. This function determines how good a given network is at a given task, and is known as the cost function. In the case of identifying numbers, the network has 10 output nodes, of which the node with the highest activation determines the networks “choice”. The cost function would take these 10 values and compare them to the ideal 10 values for that image (if the image was 2, the ideal 10 values would be [0, 0, 1, 0, . . . , 0]). Two types of cost functions were made that can be used for this network, quadratic and cross-entropy, which compare actual and expected results. The functions (and their derivatives for the backpropogation) are as follows:

def costFunc(self, expected, actual, costType='crossEntropy'):
    if costType == 'quadratic':
        result = 0.0
        for _ in expected:
            result+=(actual-expected)
        result/=len(expected)
        return -.5*(result**2)

    elif costType=='crossEntropy':
        return np.sum(np.nan_to_num(-actual*np.log(expected)-(1-actual)*np.log(1-expected)))

def costPrime(self, expected, actual, Zs, costType='crossEntropy'):
    if costType == 'quadratic':
        return ((actual-expected)*self.sigmoidPrime(Zs))
    elif costType == 'crossEntropy':
        return (actual-expected)

Dense Layers

• Dense layers connect any number of inputs to any number of outputs by multiplying by a weight matrix and adding a bias to each result.
• For example, a dense layer than had 10 inputs and 2 outputs would multiply the [1x10] input matrix by a [10x2] weight matrix, and add a [1x2] bias matrix to produce a [1x2] result. In practice, the relevant code for a dense layer looks like:

//forward passing through network
return np.dot(self.weights, self.inputs) + self.biases

//computing the partial derivative with respect to the weights
weightVector = np.dot(error, np.transpose(self.inputs))

//computing the error to pass to the next layer
return np.dot(np.transpose(self.weights), error)

Convolutional Layers

• Dense layers treat variables as independent, but pixels are not independent, which is where convolution layers come in.
• In a convolutional layer, filters are put over different parts of the image to assess how well that part of the image matches up with the filter.
• For example, a [2x2] filter could be passed over a [4x4] array of pixels, and multiplying and adding corresponding numbers for every position of the filter would give [3x3] result. The code for this convolution process looks like:

//layer is the input image, and filter is the filter
for i in range(xoffset, len(layer)-offset):
    for j in range(yoffset, len(layer[i])-yoffset):
        value = 0
        for x in range(len(filter)):
            for y in range(len(filter[x])):
                value += layer[i+x-offset][j+y-offset]*filter[x][y]
        if total:
            output[i-xoffset][j-yoffset] = value

• Backpropogation through this network is much more complicated, and involves some confusing back to understand. A good explanation can be found here. In the end, the backpropogation code looks like:

for i in range(self.depth):
    for j in range(self.inputDepth):
        filterVector[i, j] = self.convolute(self.input[j], error[i])
        intputVector[j] = self.fullFlippedConv(error[i], self.filters[i, j])

self.filterVectores -= learningRate * filterVector
self.biaseVectors -= learningRate * error

Additional Layers

• Activation Functions: An activation function introduces non-linearity into the network to allow the network to to learn more complicated patterns. This project included both sigmoid and relu activation fucntions.
• Pooling Layers: Because convolutional layers often have many filters passing over the same image, the amount of data being processed can become very large, slowing the network down. To help this, pooling layers reduce the information in the filtered images, usually by averaging groups of 4 pixels and combining them into one data point.
• Reshaping Layers: This is a simple quality of life layer that helps to format between layers. For example, a convolu- tional layer might output a 10x7x7 array of neurons (10 filters on a 5x5 image) which can then be flattened into a 490 element array to be put in a dense network.

Modular Approach

Because each of the layers explained here function independently of each other, there were all coded as independent classes. This makes it easy to change not just the size and user parameters of the network, but also the order and number of layers in any given network. For example, building a model might look like:

convolutional_Network = [
    Reshape((784, 1), ((1, 28, 28))),
    Convolitional((1, 28, 28), 5, 32),
    Activation('relu'),
    AvPool([32, 24, 24], filterSize=[2, 2]),
    Reshape((32, 12, 12), (32*12*12, 1)),
    Dense(32*12*12, 10),
    Activation('sigmoid')
]

This sample model encorperates many different layers. Notice how the output of each layer corresponds to the input of the next layer, and overall the network takes in 784 input pixels (28x28 image) and has 10 outputs for numbers 0 through 9.

While all the settings in this project are well researched and have known strengths and weaknesses, it is still fascinating to see those same results from self conducted testing. For example, using a standard convolutional network with 5x5 filters, a depth of 10, and a pooling layer, many different learning rates were tested:

There is a clear sweet spot for the learning rate at about 0.15. This curve happens because too low of a learning rate causes the network to get stuck in small local minimums, while too high learning rates skip back and forth across minimums never reaching the bottom.

Dense networks sizes were also compared. Using a dense network with 784 starting neurons, a hidden layer of x neurons, and a final layer of 10 neurons, this chart displays how adding more neurons changes the networks performance:

The chart shows that there is initially a clear relationship between adding neurons and performance, but at some point this is no longer the case. This is a clear example of why bigger networks are not always better.

Using similar methods to the two examples above, it was also found that RELU activations narrowly out preformed sigmoid activations in larger networks, cross entropy was significantly better than quadratic cost, the ideal filter size is between 3 and 5, and a batch size of 10-15 was best for optimizing time and performance. Finally, using the model shown in the code above, the best network was able to classify images with an accuracy of 97.98%.

Overall this project was successful in its goal of creating a convolutional neural network from scratch. The resulting network was able to classify digits from the mnist data set with an accuracy of 97.98%, and compare many different types of CNN’s and learning settings. It has led to a deeper understanding of how neural networks function at their core and how one type of machine learning solves problems.

*All code for any project is available upon request*