From 6.034 Wiki

Revision as of 18:12, 5 November 2015 (view source) Ocsenave (Talk | contribs) m (→Helper functions) ← Previous diff		Revision as of 18:23, 5 November 2015 (view source) Ocsenave (Talk | contribs) (→Forward propagation) Next diff →
Line 71:		Line 71:
	=== Forward propagation ===		=== Forward propagation ===
-	Forward propagation is the act of running a set of input values through the wired connections in a neural net.	+	First, we will code forward propagation, which takes in a set of inputs and computes the output of every neuron in a neural net. To do so, you should understand how a single neuron computes its output as a function of its input: each input into the neuron is multiplied by the weight of the wire; the weighted inputs are summed together, and the sum is passed through a pre-determined threshold function to produce the output.
-	For each neuron in the net, the inputs get multiplied by the weight of the edges they travel along. The weighted inputs are then summed and go through a threshold function. The output of the neuron then continues moving through the net until the final output is computed.	+	To compute the output of each neuron in a neural net, iterate over each neuron in the network in order, starting from the input neurons and working toward the output neuron. (The function <b><tt>net</tt></b><tt>.topological_sort()</tt> can be useful here; see the API for details). Compute the output of each neuron; the outputs you calculate for earlier neurons in the network will be used to calculate outputs for later neurons in the network.
-	Implement this process in <tt>forward_prop</tt>, given a neural net, a dictionary mapping input variables to input values, and the provided threshold function in order to compute the binary output of the neural net.	+	Implement the <tt>forward_prop(net, inputs, threshold_fn)</tt> subroutine. Here, <tt>net</tt> is a neural network, <tt>inputs</tt> is a dictionary which maps inputs of the network to their values, and <tt>threshold_fn</tt> is a function which each neuron will use to decide what value to output. This subroutine should return a tuple containing
		+	# The output value of the network, i.e. the output value associated with the output neuron of the network.
		+	# A dictionary mapping neurons to their immediate outputs.
		+	The dictionary of outputs is permitted to contain extra keys (for example, the input values). The subroutine should <em>not</em> modify the neural net in any way.
-	This function should not modify the input net and should return a tuple containing:
-	# the final binary output (0 or 1)	+	<!-- todo: i made up the args from memory; should check later. !-->
-	# a dictionary mapping neurons to their immediate outputs (the dictionary is allowed to contain additional keys, such as inputs)	+
		+	<!-- , given a neural net, a dictionary mapping input variables to input values, and the provided threshold function in order to compute the binary output of the neural net.
	=== Backward propagation ===		=== Backward propagation ===

---

Revision as of 18:23, 5 November 2015

Contents 1 Problems 1.1 Neural Nets 1.1.1 Wiring a neural net 1.1.2 Neural net equations (reference only) 1.1.3 Helper functions 1.1.4 Forward propagation 1.2 Support Vector Machines 1.2.1 Vector Math 1.2.2 Equations 1.2.3 SVM Functions 1.2.4 Classification Accuracy 1.3 Survey 2 API 2.1 Neural Nets 2.1.1 NeuralNet 2.2 Support Vector Machines 2.2.1 Point 2.2.2 DecisionBoundary 2.2.3 SupportVectorMachine 2.2.4 Helper functions for vector math

This lab is due by TODO at 10:00pm.

To work on this lab, you will need to get the code, much like you did for the first two labs.

• You can view the files at: http://web.mit.edu/6.034/www/labs/lab6/
• Download it as a ZIP file: http://web.mit.edu/6.034/www/labs/lab6/lab6.zip
• Or, on Athena, add 6.034 and copy it from /mit/6.034/www/labs/lab6/.

Your answers for this lab belong in the main file lab6.py.

Problems

This lab is divided into two independent parts. In the first part, you'll code subroutines necessary for training and using neural networks. In the second part, you'll code subroutines for using and validating support vector machines.

Neural Nets

Wiring a neural net

A neural net is composed of individual neurons, which generally take this form:

We form the net by combining the neurons into a structure, such as the example shown below.

In a neural net with two inputs x and y, each input-layer neuron draws a line and shades one side of it. The remaining neurons in the neural net perform logic functions on the shadings. For each of the following pictures, fill in the list with the numbers of nodes per layer resulting in the minimum total number of neurons.

As an example, the neural net shown above would be represented by the list [3, 2, 3, 1].

nn_half = [] #todo pictures/formatting

nn_angle = []

nn_cross = []

nn_stripe = []

nn_hexagon = []

Optional problem; change TEST_NN_GRID to True to run the local test TEST_NN_GRID = False nn_grid = []

Neural net equations (reference only)

For reference, here are the fundamental equations that define a neural net:

Helper functions

First, you'll code helper functions for the neural nets. The stairstep and sigmoid functions are threshold functions; each neuron in a neural net uses a threshold function to determine whether its input stimulation is large enough for it to emit an output.

stairstep: Computes the output of the stairstep function using the given threshold

sigmoid: Computes the output of the sigmoid function using the given steepness and midpoint

The accuracy function is used during training with back-propagation. It measures the performance of the neural net as a function of its desired output and its actual output (given some set of inputs). Note that the accuracy function is symmetric -- that is, it doesn't care which argument is desired and which is actual.

accuracy: Computes accuracy using desired_output and actual_output. If the neurons in the network are using the stairstep threshold function, the accuracy will range from -0.5 to 0

Forward propagation

First, we will code forward propagation, which takes in a set of inputs and computes the output of every neuron in a neural net. To do so, you should understand how a single neuron computes its output as a function of its input: each input into the neuron is multiplied by the weight of the wire; the weighted inputs are summed together, and the sum is passed through a pre-determined threshold function to produce the output.

To compute the output of each neuron in a neural net, iterate over each neuron in the network in order, starting from the input neurons and working toward the output neuron. (The function net.topological_sort() can be useful here; see the API for details). Compute the output of each neuron; the outputs you calculate for earlier neurons in the network will be used to calculate outputs for later neurons in the network.

Implement the forward_prop(net, inputs, threshold_fn) subroutine. Here, net is a neural network, inputs is a dictionary which maps inputs of the network to their values, and threshold_fn is a function which each neuron will use to decide what value to output. This subroutine should return a tuple containing

1. The output value of the network, i.e. the output value associated with the output neuron of the network.
2. A dictionary mapping neurons to their immediate outputs.

The dictionary of outputs is permitted to contain extra keys (for example, the input values). The subroutine should not modify the neural net in any way.

1. Compute the update coefficient <math>\delta_B</math> for each neuron in the network, starting from the output neuron and working backward toward the input neurons.
2. Use the update coefficients <math>\delta_B</math> to compute new weights for the network.
3. Update all of the weights in the network.

You have already coded the forward_propagation routine. To complete the definition of back propagation, you'll define a helper function calculate_deltas for computing the update coefficients <math>\delta_B</math> of each neuron in the network, and a function update_weights which retrieves the list of update coefficients using calculate_deltas, then modifies the weights of the network accordingly.

def calculate_deltas(net, input_values, desired_output):

   """Computes delta_B values for entire neural net, using sigmoid function to
   compute output.  Returns a dictionary mapping neurons to delta_B values."""

update_weights: Performs a single step of back propagation. Computes delta_B values and weight updates for entire neural net, then updates all weights. Uses the sigmoid function to compute output.

Returns a tuple containing:

1) the modified neural net, with updated weights

2) a dictionary mapping neurons to delta_B values

back_prop: Updates the weights until the accuracy surpasses minimum_accuracy. Uses the sigmoid function to compute output.

Returns a tuple containing:

1) The modified neural net, with trained weights

2) The number of iterations (that is, the number of weight updates)

Support Vector Machines

Vector Math

norm(v): Returns the length of the vector v. Note that v can either be a Point instance or a tuple/list of coordinates.

dot_product(u,v): Computes the dot product of two vectors u, v. Again, each vector can either be a Point instance or tuple/list of coordinates.

Equations

The following five equations may be helpful. Recall that Equations 1-3 will define the decision boundary and the margin width. Equations 4 & 5 will allow you to calculate the alpha values for the training points.

SVM Functions

positiveness: Evaluates Equation 1 for the given point

classify: Uses the given SVM to classify a Point. We assume that point's classification is unknown. Returns +1 or -1, or 0 if point is on boundary.

margin_width: Calculates the margin width based on current decision boundary.

todo formatting below

1. Equation 3

def check_gutter_constraint(svm):

   """Returns the set of training points that violate one or both conditions:
       * gutter constraint (positiveness == classification for support vectors)
       * training points must not be between the gutters
   Assumes that the SVM has support vectors assigned."""
   raise NotImplementedError

1. Equations 4, 5

def check_alpha_signs(svm):

   """Returns the set of training points that violate either condition:
       * all non-support-vector training points have alpha = 0
       * all support vectors have alpha > 0
   Assumes that the SVM has support vectors assigned, and that all training
   points have alpha values assigned."""
   raise NotImplementedError

def check_alpha_equations(svm):

   """Returns True if both Lagrange-multiplier equations are satisfied,
   otherwise False.  Assumes that the SVM has support vectors assigned, and
   that all training points have alpha values assigned."""

Classification Accuracy

def misclassified_training_points(svm):

   """Returns the set of training points that are classified incorrectly
   using the current decision boundary."""

todo formatting

Survey

Please answer these questions at the bottom of your lab6.py file:

• NAME: What is your name? (string)

• COLLABORATORS: Other than 6.034 staff, whom did you work with on this lab? (string, or empty string if you worked alone)

• HOW_MANY_HOURS_THIS_LAB_TOOK: Approximately how many hours did you spend on this lab? (number or string)

• WHAT_I_FOUND_INTERESTING: Which parts of this lab, if any, did you find interesting? (string)

• WHAT_I_FOUND_BORING: Which parts of this lab, if any, did you find boring or tedious? (string)

• (optional) SUGGESTIONS: What specific changes would you recommend, if any, to improve this lab for future years? (string)

(We'd ask which parts you find confusing, but if you're confused you should really ask a TA.)

When you're done, run the online tester to submit your code.

API

Neural Nets

The file neural_net_api.py defines the Wire and NeuralNet classes, described below.

NeuralNet

A NeuralNet is represented as a directed graph. Its fields are:

• net.inputs, a list of named inputs. Inputs are represented as strings denoting their names.
• net.neurons, a list of neurons. Neurons are represented as strings denoting their names.
• net.wires, a list of the wires (edges) which connect the nodes in the network. Each wire is a Wire object (see below.)

In this lab, inputs are supplied to neural nets in the form of a dictionary that associates each named input with an input value.

You can retrieve the nodes (neurons, inputs) in a network:

• net.get_incoming_neighbors(node). Return a list of the nodes which are connected as inputs to node
• net.get_outgoing_neighbors(node). Return a list of the nodes to which node sends its output.
• net.get_output_neuron(). Return the final, output neuron of the network. (In this lab, each neural net has exactly one output neuron.)
• net.topological_sort(). Return a sorted list of all the neurons in the network. The list is "topologically" sorted, which means that each neuron appears in the list after all the neurons that provide its inputs. Thus, the input layer neurons are first, and the output neuron is last, etc.

You can also retrieve the wires:

• net.get_wires(startNode=None, endNode=None). Return a list of all the wires in the network. If startNode or endNode are provided, returns only wires that start/end at particular nodes.
• net.get_incoming_wires(node). Return a list of wires that feed in to the given node.
• net.get_outgoing_wires(node). Return a list of wires that the node feeds into.

Finally, you can query the parts of the network:

• net.is_input_neuron(node). Return True if the node is connected directly to an input, otherwise False.
• net.is_output_neuron(node). Return True if the node is the final, output neuron in the network, otherwise False.
• net.is_connected(startNode, endNode). Return True if there is a wire from startNode to endNode in the network, otherwise False.

todo: add note about the fake wire to NeuralNet.OUT

A neural net is represented as a directed graph whose edges are Wires and nodes can be neurons, inputs, or OUT.

Note that:

- Each variable input is represented by its name (a string).

- Each constant input is represented by an int or float (eg -1).

- Each neuron is represented by its name (a string).

- The final output is represented by the constant string NeuralNet.OUT.

The following methods are available for you to use:

get_wires(startNode=None, endNode=None): Returns a list of all the wires in the graph. If the start or end are provided, it restricts to wires that start/end at particular nodes. (A node can be an input, a neuron, or the output OUT.)

get_incoming_neighbors(node): Returns an alphabetical list of neighboring nodes (neurons or inputs) that appear earlier in the neural net. That is, nodes that have wires leading into the provided node. Each node appears at most once.

get_outgoing_neighbors(node): Returns an alphabetical list of neighboring nodes (either be neurons or OUT) that appear later in the neural net (that is, nodes that receive the provided node's output). Each node appears at most once.

get_incoming_wires(endNode): Returns a list of wires leading into the provided neuron or OUT.

get_outgoing_wires(startNode): Returns a list of wires exiting out of the provided neuron or input.

get_wire(startNode, endNode): Returns the wire that directly connects startNode to endNode or None if no such wire exists.

is_connected(startNode, endNode): Returns True if there is a wire that connects startNode to endNode or False if no such wire exists.

is_input_neuron(neuron): Returns True if neuron is an input-layer neuron, else False.

is_output_neuron(neuron): Returns True if neuron is an output-layer neuron, else False.

Support Vector Machines

The file svm_api.py defines the Point, DecisionBoundary, and SupportVectorMachine classes, as well as some helper functions for vector math, all described below.

Point

A Point has a name (a string), a list or tuple of coordinates, and optionally a classification or an alpha value.

Note that the classification (if any) is a number, typically +1 or -1.

We have also provided a copy method to create a new instance of a Point with the same parameters.

Additionally, you can see if two Point objects have equivalent coordinates, classifications, and alpha values using the == equivalence method.

DecisionBoundary

A DecisionBoundary is defined by two parameters: a normal vector w, and an offset b. w is represented as a list or tuple of coordinates.

We have also provided a copy method to create a new instance of a DecisionBoundary with the same parameters.

Additionally, you can see if two DecisionBoundary objects have equivalent w and b values using the == equivalence method.

SupportVectorMachine

A SupportVectorMachine is a classifier that uses a DecisionBoundary to classify points. It has a list of training points and optionally a list of support vectors.

The class has three attributes - the boundary, a list of training_points, and a list of support_vectors.

We have also provided a copy method to create a new instance of a SupportVectorMachine with the same parameters.

You can see if two SupportVectorMachine objects have the same boundary,training points, and support vectors by using the == equivalence method.

Helper functions for vector math

convert_point_to_coords: Given either a Point object or a tuple of coordinates, returns a tuple of coordinates.

vector_add: Given two vectors represented as lists or tuples of coordinates, returns their sum as a list of coordinates.

scalar_mult: Given a constant scalar and a vector (as a tuple or list of coordinates), returns a scaled list of coordinates.