<jupyter_start><jupyter_text>Tutorial Computational GraphsIn this exercise you will implement a computational graph in python.<jupyter_code>import numpy as np
import graphviz as gz
from matplotlib import pyplot as plt
from IPython.display import display
class Gate:
    
    """
        Every gate has a set of inputs (input_nodes) and consumers.
        Additionally a gate has to implement the methods forward and backward.
        The forward method computes the result with respect to the given input nodes 
        (use the out field) of the input gates and stores the value in the field out.
        The backward function computes and propagates the gradient for the given gate.
        On call of the backward function, the gate uses the incoming gradient dz and adds 
        to all input nodes the corresponding gradient.
    """
    
    name = "???"

    def __init__(self, input_nodes=[], name=None):
        self.out = None
        self.dz = 0
        self.dzs = {}
        
        if name is not None:
            self.name = name
        
        self.input_nodes = input_nodes

        self.consumers = []

        for input_node in input_nodes:
            input_node.consumers.append(self)

    def forward(self):
        """Computes the output of this operation.
        "" Must be implemented by the particular operation.
        """
        pass

    def backward(self):
        """
        "" Must be implemented by the particular operation.
        """
        pass
    
    def put_gradient(self, gate, dz):
        if gate in self.consumers:
            self.dz += dz * gate.dz
            self.dzs[gate] = dz
class ComputationalGraph:
    
    """
        This class implements the backward and forward function for the whole graph.
        Both methods return a graphviz object visualizing the respective steps.
        To draw the computational graphs in jupyter notebook you can for instance use the imported display function.
    """
    
    def __init__(self, target):
        def get_nodes(target, nodes=[]):
            if target in nodes:
                nodes.remove(target)
            nodes.append(target)
            for inp in target.input_nodes:
                get_nodes(inp, nodes)
            return nodes
        self.nodes = list(reversed(get_nodes(target)))
    
    def forward(self, inputs):
        g = gz.Digraph('G', strict=True)
        g.graph_attr['rankdir'] = 'LR'
        for gate in self.nodes:
            if gate in inputs:
                gate.value = inputs[gate]
            gate.forward()
            g.node(str(id(gate)), label="<%s<br/><FONT POINT-SIZE='10'>%.3f</FONT>>" % (gate.name, gate.out))
            for node in gate.consumers:
                g.edge(str(id(gate)), str(id(node)))
        return g
    
    def backward(self):
        g = gz.Digraph('G', strict=True)
        g.graph_attr['rankdir'] = 'RL'
        for gate in self.nodes: gate.dz = 0
        self.nodes[-1].dz = 1
        for gate in reversed(self.nodes):
            gate.backward()
            g.node(str(id(gate)), label="<%s<br/><FONT POINT-SIZE='10'>%.3f</FONT>>" % (gate.name, gate.dz))
            for node in gate.input_nodes:
                g.edge(str(id(gate)), str(id(node)), label="%.3f" % node.dzs[gate])
        return g<jupyter_output><empty_output><jupyter_text>* Example: Add Gate<jupyter_code>class AddGate(Gate):
    
    name = "+"
    _
    def __init__(self, inputs, name=None):
        super().__init__(inputs, name)
    
    def forward(self):
        self.input_values = [n.out for n in self.input_nodes] #x y
        self.out = np.sum(self.input_values) # x+y
    
    def backward(self):
        for i, node in enumerate(self.input_nodes):
            node.put_gradient(self, 1)<jupyter_output><empty_output><jupyter_text>* Example: Input Gate<jupyter_code>class InputGate(Gate):
    
    name = "inp"
    
    def __init__(self, name=None):
        super().__init__(name=name)
        self.value = 0
 
    def forward(self):
        self.out = self.value
    
    def backward(self):
        pass # There are no input nodes => nothing to do<jupyter_output><empty_output><jupyter_text>* Implement a gate that represents a weight. The constructor shall take the parameter $\alpha$ that represents the learning rate of this weight.<jupyter_code>class WeightGate(Gate):
    
    name = "w"
    
    def __init__(self, alpha=0.1, name=None, weight=None):
        super().__init__(name=name)
        self.weight = 2*np.random.random()-1 if weight is None else weight
        self.alpha = alpha
    
    def forward(self):
        self.out = self.weight
    
    def backward(self):
        self.weight -= self.alpha * self.dz<jupyter_output><empty_output><jupyter_text>* Implement a gate that multiplies the outputs of a set of input gates.<jupyter_code>class MultiplyGate(Gate):
    
    name = "*"
    _
    def __init__(self, inputs, name=None):
        super().__init__(inputs, name)
    
    def forward(self):
        self.input_values = [n.out for n in self.input_nodes]
        self.out = np.prod(self.input_values)
    
    def backward(self):
        for node in self.input_nodes:
            vals = [n.out for n in self.input_nodes if n != node]
            node.put_gradient(self, np.prod(vals))<jupyter_output><empty_output><jupyter_text>* Implement a sigmoid gate that computes the sigmoid of one input.<jupyter_code>class SigmoidGate(Gate):
    
    name = "sig"
    _
    def __init__(self, inp1, name=None):
        super().__init__([inp1], name)
    
    def forward(self):
        self.out = 1. / ( 1. + np.exp(-self.input_nodes[0].out) )
    
    def backward(self):
        self.input_nodes[0].put_gradient(self, self.out * (1 - self.out))<jupyter_output><empty_output><jupyter_text>* Implement a gate with the following loss function $L(y, \hat{y}) = (\hat{y} - y)^2$.<jupyter_code>class SquaredLossGate(Gate):
    
    name = "MSE"
    
    def __init__(self, y, y_pred, name=None):
        super().__init__([y, y_pred], name=name)
    
    def forward(self):
        y, y_pred = [n.out for n in self.input_nodes]
        self.out = (y - y_pred)**2
    
    def backward(self):
        dy = 2 * (self.input_nodes[0].out - self.input_nodes[1].out)
        dy_pred = 2 * (self.input_nodes[1].out - self.input_nodes[0].out)
        self.input_nodes[0].put_gradient(self, dy)
        self.input_nodes[1].put_gradient(self, dy_pred)<jupyter_output><empty_output><jupyter_text>* Build the computational graph from exercise 3-1 in python and compute display the computational graph after forward and backward.<jupyter_code>x1 = InputGate('x1')
x2 = InputGate('x2')
y = InputGate('y')

w1 = WeightGate(name='w1', weight=4./5.)
w2 = WeightGate(name='w2', weight=-7./5.)
p0 = WeightGate(name='p0', weight=3./5.)

p1 = MultiplyGate([x1, w1], 'p1')
p2 = MultiplyGate([x2, w2], 'p2')

z = AddGate([p0, p1, p2], 'z')

y_pred = SigmoidGate(z, 'ŷ')

loss = SquaredLossGate(y, y_pred, 'L')
graph = ComputationalGraph(loss)
print("Forward:\n")
g = graph.forward({x1: 1, x2: 1, y: 1})
display(g)

print('Backward:\n')
g = graph.backward()
display(g)<jupyter_output>Forward:<jupyter_text>* Construct and train a computational graph / network that can classify the XOR dataset with stochastic gradient descent and the already implemented squared loss function.<jupyter_code>## XOR
X = [[0,0],[0,1],[1,0],[1,1]]
Y = [0, 1, 1, 0]
def train(graph, epochs):
    losses = []
    for epoch in range(epochs):
        epoch_loss = 0
        for x_in, y_in in zip(X, Y):
            g = graph.forward({x1: x_in[0], x2: x_in[1], y: y_in})
            epoch_loss += loss.out
            if epoch == epochs-1:
                display(g)
            g = graph.backward()
            if epoch == epochs-1:
                display(g)
        losses.append(epoch_loss/len(Y))
    plt.plot(losses)<jupyter_output><empty_output><jupyter_text>Kernel Trick:<jupyter_code>x1 = InputGate('x1')
x2 = InputGate('x2')
y = InputGate('y')

w1 = WeightGate(name='w1', weight=4./5.)
w2 = WeightGate(name='w2', weight=-7./5.)
p0 = WeightGate(name='p0', weight=3./5.)

p1 = MultiplyGate([x1, WeightGate(name='w1')])
p2 = MultiplyGate([x2, WeightGate(name='w2')])
p3 = MultiplyGate([x1, x2, WeightGate(name='w3')])

y_pred = SigmoidGate(AddGate([p1, p2, p3, WeightGate(name='b')]), name='ŷ')
loss = SquaredLossGate(y, y_pred, 'L')

train(ComputationalGraph(loss), 500)<jupyter_output><empty_output><jupyter_text>Multi-Layer-Perceptron:<jupyter_code>def perceptron(inputs):
    p = [MultiplyGate([inp, WeightGate()]) for inp in inputs]
    p.append(WeightGate(name='b'))
    return AddGate(p)

x1 = InputGate('x1')
x2 = InputGate('x2')
y = InputGate('y')

hidden = [SigmoidGate(perceptron([x1, x2])) for _ in range(2)]
y_pred = SigmoidGate(perceptron(hidden), 'ŷ')

loss = SquaredLossGate(y, y_pred, 'L')

graph = ComputationalGraph(loss)

epochs = 5000

train(graph, epochs)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.12897091722595078, 'fraction_numerical': 0.0145413870246085, 'mean_word_length': 2.7966029723991506, 'pattern_counts': {'":': 0, '<': 52, '<?xml version=': 0, '>': 53, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '11', 'dir': 'jupyter-structured-clean-dedup', 'id': '212689', 'license': 'MIT', 'n_tokens_mistral': 3047, 'n_tokens_neox': 2952, 'n_words': 759, 'path': 'week3/comp_graph.ipynb', 'repo_name': 'changkun/ws-18-19-deep-learning-tutorial', 'size': '8940'}