Backpropagation Algorithm

backprop.py

from math import exp

class Edge:
    def __init__(self, edgetup, weight):
        self.vertex_out = edgetup[0]
        self.vertex_in = edgetup[1]
        self.weight = weight

class Unit:
    def __init__(self, number, input_edges, output_edges):
        self.number = number
        self.input_edges = input_edges
        self.output_edges = output_edges
        self.weights = []
        self.inputs = []
        self.output = 1
        self.delta = 0

        for edge in input_edges:
            self.weights.append(edge.weight)

    def adjust_inputs(self, inputs):
        self.inputs = inputs

    def calc_output(self):
        self.output = sigmoid(self.weights, self.inputs)

    def copy_outputs(self, outputs):
        for output in outputs:
            self.inputs.append(output)

    def update_weights(self):
        self.weights = []
        for edge in self.input_edges:
            self.weights.append(edge.weight)

def dot_product(a1, a2):
    dp = sum([a1[i] * a2[i] for i in range(len(a1))])
    return dp

def sigmoid(weight, inputs):
    return 1./(1. + exp(-1 * dot_product(weight, inputs)))

def output_correction(unit, expected):
    unit.delta = unit.output * (1 - unit.output) * (expected - unit.output)
    print "Output vertex #" + str(unit.number) + " delta: " + str(unit.delta)

def hidden_correction(unit, outputs):
    for output in outputs:
        delta = output.delta
        weight = 0
        for edge in output.input_edges:
            if edge.vertex_out == unit.number:
                weight = edge.weight
        unit.delta += unit.output * (1 - unit.output) * weight * delta
    print "Hidden vertex #" + str(unit.number) + " delta: " + str(unit.delta)
    
def update_inputs(edge, learning, units):
    delta = units[edge.vertex_in].delta
    x = units[edge.vertex_out].output
    edge.weight = edge.weight + learning * delta * x
    print "Edge " + str((edge.vertex_in, edge.vertex_out)) + " weight: " \
          + str(edge.weight)

def output_hidden(unit_layer, units):
    for unit_index in unit_layer:
        current = units[unit_index]
        current.copy_outputs([1, 0, 1])
        current.calc_output()
        print "Unit #" + str(unit_index) + " output: " + str(current.output)

def output_final(unit_layer, units):
    for unit_index in unit_layer:
        inputs = []
        current = units[unit_index]
        for edge in current.input_edges:
            inputs.append(units[edge.vertex_out].output)
        current.copy_outputs(inputs)
        current.calc_output()
        print "Unit #" + str(unit_index) + " output: " + str(current.output)


def main():

    # solution: 03: 0.597, O4 :0.597, O5: 0.623, 06: 0.584, 07: 0.584
    # w50: 0.237, w53: 0.222, w54: 0.222, w60: 0.142, w63: 0.165, 
    # w64: 0.165, w70: 0.142, w73: 0.165, w74: 0.165

    # define network and initialize
    units = []
    edges = []
    outputs = []

    unit_layers = [(1, 2), (3, 4), (5, 6, 7)]
    edge_tups = [(0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 3), (1, 4), \
                 (2, 3),(2, 4), (3, 5), (3, 6), (3, 7), (4, 5), (4, 6), (4, 7)]
    test_inputs = [1, 0, 1]
    test_outputs = {5: 1, 6: 0, 7: 0}

    for edge in edge_tups:
        new_edge = Edge(edge, 0.2)
        edges.append(new_edge)

    bias_unit = Unit(0, [], edges[:5])
    units.append(bias_unit)

    for i in range(1, 8):
        input_edges = [edge for edge in edges if edge.vertex_in == i]
        output_edges = [edge for edge in edges if edge.vertex_out == i]
        new_unit = Unit(i, input_edges, output_edges)
        units.append(new_unit)

    # forward pass

    output_hidden(unit_layers[1], units)
    output_final(unit_layers[2], units)

    # backward pass

    for unit_index in unit_layers[2]:
        current = units[unit_index]
        outputs.append(current)
        output_correction(current, test_outputs[unit_index])

    for unit_index in unit_layers[1]:
        current = units[unit_index]
        hidden_correction(current, outputs)

    # weight updating

    for edge in edges:
        update_inputs(edge, 0.4, units)

    # re-calculate

    for unit in units:
        unit.update_weights()

    output_hidden(unit_layers[1], units)
    output_final(unit_layers[2], units)

if __name__ == '__main__':
    main()