<jupyter_start><jupyter_text>Credits: Prof <NAME>Course Homework for the course [11-785](https://deeplearning.cs.cmu.edu/) Introduction to Deep Learning, Spring 2020  You will write your own implementation of the backpropagation algorithm for training your own neural network, aswell as a few other features such as activation and loss functions. **Note**:It is difficult to verify whether or not your implementation of backprop works. As we have mentioned in the assignment, we have borrowed it from CMU's deep learning course.You can download this homework archive from their website: http://deeplearning.cs.cmu.edu/document/homework/hw1p1_handout.tarInside the archive, you will find python files where you had to write the code. Paste your code implementation in the respective places, install the dependencies:```pip install numpypip install pytest```And run this command from the top-level directory:```python3 autograder/hw1_autograder/runner.py```You should get a score corresponding to each module.  Task 1: ActivationsImplement the `forward` and `derivative` class methods for each activation function.* The identity function has been implemented for you as an example.* The output of the activation should be stored in the `self.state` variable of the class. The `self.state`variable should be used for calculating the derivative during the backward pass.<jupyter_code>import numpy as np
import math
class Activation(object):

    """
    Interface for activation functions (non-linearities).

    In all implementations, the state attribute must contain the result,
    i.e. the output of forward.
    """

    # No additional work is needed for this class, as it acts like an
    # abstract base class for the others

    # ABC (Abstract base class)
    # 1. A class is called an Abstract class if it contains one or more abstract methods
    # 2. An abstract method is a method that is declared, but contains no implementation.
    # 3. Abstract classes may not be instantiated
    # 4. Abstract method of the base class ,will be implemented with help of child class
    # 5. child class (also known as subclass of superclass ) will inherite base class. 

    # Note that these activation functions are scalar operations. I.e, they
    # shouldn't change the shape of the input.

    def __init__(self):
        self.state = None

    def __call__(self, x):
        return self.forward(x)

    def forward(self, x):
        raise NotImplemented

    def derivative(self):
        raise NotImplemented
class Identity(Activation):

    """
    Identity function (already implemented).
    """

    # This class is a gimme as it is already implemented for you as an example
    # The usage of the super keyword allows  , the child class to access the parent class’s init() property
    
    def __init__(self):
        super(Identity, self).__init__()

    # Activation function and thier derivative are shown in pdf's
    def forward(self, x):
        self.state = x
        return x

    def derivative(self):
        return 1.0
class Sigmoid(Activation):

    """
    Sigmoid non-linearity
    """

    # Remember do not change the function signatures as those are needed
    # to stay the same for AutoLab.

    def __init__(self):
        super(Sigmoid, self).__init__()

    def forward(self, x):
        # Might we need to store something before returning?
        self.state = 1.0 / 1.0 + np.exp(-x)
        return self.state

    def derivative(self):
        # After getting output from the forward pass , we go and find the derivative of sigmoid
        # which comes as f(x)*(1-f(x))
        return self.state*(1-self.state)
class Tanh(Activation):

    """
    Tanh non-linearity
    """

    def __init__(self):
        super(Tanh, self).__init__()

    def forward(self, x):
      e_plus_x = np.exp(x)
      e_minus_x = np.exp(x)

      numerator = e_plus_x - e_minus_x
      denominator = e_plus_x + e_minus_x

      self.state = numerator / denominator
      return self.state

    def derivative(self):
      return (1 - self.state**2)
class ReLU(Activation):

    """
    ReLU non-linearity
    """

    def __init__(self):
        super(ReLU, self).__init__()

    def forward(self, x):
      self.state = np.where(x>0 , x , 0.0)
      return self.state

    def derivative(self):
      relu_prime = np.where( self.state>0 , 1.0 , 0.0)
      return relu_prime<jupyter_output><empty_output><jupyter_text>Task 2: LossImplement the forward and derivative methods for `SoftmaxCrossEntropy`.* This class inherits the base `Criterion` class.* We will be using the softmax cross entropy loss detailed in the appendix of this writeup; use theLogSumExp trick to ensure numerical stability.The LogSumExp trick is used to prevent numerical underflow and overflow which can occur when the exponent is very large or very small. For example, try looking at the results of trying to exponentiate in python shown below:```pythonimport mathprint(math.e**1000)   throws an errorprint(math.e**(-1000)```As you will see, for exponents that are too large, python throws an overflow error, and for exponents that are too small, it rounds down to zero.We can avoid these errors by using the LogSumExp trick:![alt text](https://imgur.com/download/L0P17iv)You can read more about the derivation of the equivalence [here](https://www.xarg.org/2016/06/the-log-sum-exp-trick-in-machine-learning/) and [here](https://blog.feedly.com/tricks-of-the-trade-logsumexp/)<jupyter_code># The following Criterion class will be used again as the basis for a number
# of loss functions (which are in the form of classes so that they can be
# exchanged easily (it's how PyTorch and other ML libraries do it))

class Criterion(object):
    """
    Interface for loss functions.
    """

    # Nothing needs done to this class, it's used by the following Criterion classes

    def __init__(self):
        self.logits = None
        self.labels = None
        self.loss = None

    def __call__(self, x, y):
        return self.forward(x, y)

    def forward(self, x, y):
        raise NotImplemented

    def derivative(self):
        raise NotImplemented<jupyter_output><empty_output><jupyter_text>* Implement the softmax cross entropy operation on a batch of output vectors.  *  Hint: Add a class attribute to keep track of intermediate values necessary for the backward computation* Calculate the ‘derivative’ of softmax cross entropy using intermediate values saved in the forward pass.<jupyter_code>class SoftmaxCrossEntropy(Criterion):

    """
    Softmax loss
    """

    def __init__(self):
        super(SoftmaxCrossEntropy, self).__init__()

    def forward(self, x, y):
        """
        Argument:
            x (np.array): (batch size, 10)
            y (np.array): (batch size, 10)
        Return:
            out (np.array): (batch size, )
        """
        self.logits = x
        self.labels = y

        mx = np.max(self.logits,axis=1).reshape(-1,1)   #row wise maximum 
        substracted = self.logits - mx
        self.exp_logits = np.exp(substracted)
        exp_sum = self.exp_logits.sum(axis=1).reshape(-1,1)         

        self.sm = self.exp_logits / self.exp_sum

        # cross entropy

        first_term = -(self.logits*self.labels).sum(axis=1)
        second_term = mx + np.log(exp_sum)
        return first_term + second_term.reshape(-1)

    def derivative(self):
        """
        Return:
            out (np.array): (batch size, 10)
        """
        return self.sm - self.labels<jupyter_output><empty_output><jupyter_text>Task 3: Linear LayerImplement the forward and backward methods for the `Linear` class.* Hint: Add a class attribute to keep track of intermediate values necessary for the backward computation.Write the code for the backward method of Linear. * The input delta is the derivative of the loss with respect to the output of the linear layer. It has the same shape as the linear layer output. * Calculate `self.dW` and `self.db` for the backward method. `self.dW` and `self.db` represent the gradients of the loss (averaged across the batch) w.r.t `self.W` and `self.b`. Their shapes are the same as the weight `self.W` and the bias `self.b`.* Calculate the return value for the backward method. `dx` is the derivative of the loss with respect to the input of the linear layer and has the same shape as the input.<jupyter_code>class Linear():
    def __init__(self, in_feature, out_feature, weight_init_fn, bias_init_fn):

        """
        Argument:
            W (np.array): (in feature, out feature)
            dW (np.array): (in feature, out feature)
            momentum_W (np.array): (in feature, out feature)

            b (np.array): (1, out feature)
            db (np.array): (1, out feature)
            momentum_B (np.array): (1, out feature)
        """

        self.W = weight_init_fn(in_feature, out_feature)
        self.b = bias_init_fn(out_feature)

        # TODO: Complete these but do not change the names.
        self.dW = np.zeros(None)
        self.db = np.zeros(None)

        self.momentum_W = np.zeros(None)
        self.momentum_b = np.zeros(None)

    def __call__(self, x):
        return self.forward(x)

    def forward(self, x):
        """
        Argument:
            x (np.array): (batch size, in feature)
        Return:
            out (np.array): (batch size, out feature)
        """
        self.x = x
        
        # NOTE TO SELF : Batch processing 
        # When we are dealing with perceptron then x and w is vector
        # When we are dealing with layer i.e. w then it would be matrix

        # Here in these case x would be matrix not a vector
        # Bcoz we are taking batch of vector i.e. batch size
        # it makes computation faster 

        out = np.matmul(self.x , self.w) + self.b  
        return out

    def backward(self, delta):

        """
        Argument:
            delta (np.array): (batch size, out feature)
        Return:
            out (np.array): (batch size, in feature)
        """
        ## Delta : Is a gradient that will be receive from later layer i.e derivative of loss w.r.t output of linear function (y = x*w)
        ## Delta  = dL/dy
        
        """
        3 thing we need
            1.Derivative of loss w.r.t weights
            2.Derivative of loss w.r.t bias
            3.Derivative of loss w.r.t to input that this layer receive
                dL/dx = dL/dy * dy/dx (chain rule)        
                y = x*W (x is matrix and w is matrix then y is also matrix)
            4.Loss will be scalar then we compute the derivate of loss with each element of y
        """
        
        ## When we simplify -> Derivative of loss w.r.t weights 
        ## Average across the batch that's why we divide the term delta.shape[0]

        self.dW = np.dot(self.x.T , delta) / delta.shape[0]
        
        ## When we simplify -> Derivative of loss w.r.t bias 
        self.db = np.sum(delta , axis=0 , keepdims=True) / delta.shape[0]
        
        ## When we simplify -> Derivative of loss w.r.t input 
        dx = np.dot(delta , self.w.T)

        return dx
## Dot product with 1-D array

a = np.array([[1],
              [2],
              [3]])
b = np.array([[1,2,3]])
c = np.dot(a,b)
print(c)
d = c + [[1,1,1]]
print(d)
## Dot product with 2-D array

a = np.array([
                [1,2],
                [3, 4],
             ])

b = np.array([
                [2,1],
                [4,3]
             ])

c = np.dot(a,b)
print(c)
# d = c + [[1,1]]
# print(d)
## Just see how zip works

a = ("John", "Charles", "Mike")
b = ("Jenny", "Christy", "Monica", "Vicky")

x = list(zip(a, b))

#use the tuple() function to display a readable version of the result:

print(x)
print(x[0])
print(x[0][0])

print("=============================")

for i,j in zip(a,b):
  print(i)
  print(j)<jupyter_output>[('John', 'Jenny'), ('Charles', 'Christy'), ('Mike', 'Monica')]
('John', 'Jenny')
John
=============================
John
Jenny
Charles
Christy
Mike
Monica<jupyter_text>Task 4: Simple MLPIn this section of the homework, you will be implementing a Multi-Layer  Perceptron with an API similar to popular Automatic Differentiation Libraries like PyTorch.Go through the functions of the given `MLP` class thoroughly and make sure you understand what each function in the class does so that you can create a generic implementation that supports an arbitrary number of layers, types of activations and network sizes.The parameters for the MLP class are:* `input size`: The size of each individual data example.* `output size`: The number of outputs.* `hiddens`: A list with the number of units in each hidden layer.* `activations`: A list of Activation objects for each layer.* `weight init fn`: A function applied to each weight matrix before training.* `bias init fn`: A function applied to each bias vector before training.* `criterion`: A Criterion object to compute the loss and its derivative.* `lr`: The learning rate.The attributes of the MLP class are:* `@linear layers`: A list of Linear objects.* `@bn layers`: A list of BatchNorm objects. (Should be None until completing 3.3).The methods of the MLP class are:* `forward`: Forward pass. Accepts a mini-batch of data and return a batch of output activations.* `backward`: Backward pass. Accepts ground truth labels and computes gradients for all parameters.Hint: Use state stored in activations during forward pass to simplify your code.* `zero grads`: Set all gradient terms to 0.* `step`: Apply gradients computed in backward to the parameters.* `train` (Already implemented): Set the mode of the network to train.* `eval` (Already implemented): Set the mode of the network to evaluation.Note: Pay attention to the data structures being passed into the constructor and the class attributes specified initially.Sample constructor call:```pythonMLP(784, 10, [64, 64, 32], [Sigmoid(), Sigmoid(), Sigmoid(), Identity()],weight_init_fn, bias_init_fn, SoftmaxCrossEntropy(), 0.008)```<jupyter_code>class MLP(object):

    """
    A simple multilayer perceptron
    """

    def __init__(self, input_size, output_size, hiddens, activations, weight_init_fn,
                 bias_init_fn, criterion, lr):

        # Don't change this -->
        self.train_mode = True
        self.nlayers = len(hiddens) + 1
        self.input_size = input_size
        self.output_size = output_size
        self.activations = activations
        self.criterion = criterion
        self.lr = lr
        # <---------------------

        # Don't change the name of the following class attributes,
        # the autograder will check against these attributes. But you will need to change
        # the values in order to initialize them correctly

        # Initialize and add all your linear layers into the list 'self.linear_layers'
        # (HINT: self.foo = [ bar(???) for ?? in ? ])
        # (HINT: Can you use zip here?)
        self.linear_layers = [Linear(inf, outf,weight_init_fn,bias_init_fn) for inf,outf in zip([self.input_size]+hiddens , hiddens+[self.output_size])]


x = layer(x)

    def forward(self, x):
        """
        Argument:
            x (np.array): (batch size, input_size)
        Return:
            out (np.array): (batch size, output_size)
        """
        # Complete the forward pass through your entire MLP.
        for i,layer in enumerate(self.linear_layers):
          x = layer(x)
          x = self.activation[i](x)
        return x

    def zero_grads(self):
        # Use numpyArray.fill(0.0) to zero out your backpropped derivatives in each
        # of your linear and batchnorm layers.
        for layer in self.linear_layers:
          layer.dW.fill(0.0)
          layer.db.fill(0.0)
    
    def step(self):
        # Apply a step to the weights and biases of the linear layers.
        # (You will add momentum later in the assignment to the linear layers)

        ## without momentum
        for i in range(len(self.linear_layers)):
            # Update weights and biases here
            layer = self.linear_layers[i]
            layer.W = layer.W - self.lr * layer.dW
            layer.b = layer.b - self.lr * layer.db


    def backward(self, labels):
        # Backpropagate through the activation functions, batch norm and
        # linear layers.
        # Be aware of which return derivatives and which are pure backward passes
        # i.e. take in a loss w.r.t it's output.
        
        final_layer = self.activation[-1]                   # final layer activation
        final_outputs = final_layer.state                   # output of final layer
        loss = self.criterion(final_outputs,labels)         # find the loss as we have predicted and label (True value)
        delta = self.criterion.derivative()                 # get the delta which is derivate loss w.r.t

        # Now we propagate error backwords and update the weights
        for i in range(self.layer-1,-1,-1):
          """ 
          while propagative backwards we get 2 function 
              1. when activation comes we take derivative 
              2. when linear layer comes again we update our delta
         """
          ## In backward function we will compute a gradients and pass the gradient from last layer to previous layer and this goes on
          ## gradient will be calculated during backward pass i.e. dL/dx , dx -> represent input receive by the last layer from it previous layer

          delta = delta * self.activations[i].derivative()              
          delta = self.linear_layers[i].backward(delta) 

    def error(self, labels):
        return (np.argmax(self.output, axis = 1) != np.argmax(labels, axis = 1)).sum()

    def total_loss(self, labels):
        return self.criterion(self.output, labels).sum()

    def __call__(self, x):
        return self.forward(x)

    def train(self):
        self.train_mode = True

    def eval(self):
        self.train_mode = False<jupyter_output><empty_output><jupyter_text>Task 5: MomentumModify the `step` function present in the MLP class to include momentum in your gradient descent. We will be using the following momentum update equation:![alt text](https://imgur.com/download/ZVA66FC)    beta : momentum     delta w^(k-1) : Previous gradient    Loss(W^k-1) : Gradient w.r.t loss    eta : learning rate    The momentum value will be passed as a parameter to the `MLP`.Copy the rest of your code from above.<jupyter_code>class MLP(object):

    """
    A simple multilayer perceptron
    """

    def __init__(self, input_size, output_size, hiddens, activations, weight_init_fn,
                 bias_init_fn, criterion, lr, momentum=0.0):

        # Don't change this -->
        self.train_mode = True
        self.nlayers = len(hiddens) + 1
        self.input_size = input_size
        self.output_size = output_size
        self.activations = activations
        self.criterion = criterion
        self.lr = lr
        self.momentum = momentum
        # <---------------------

        # Initialize and add all your linear layers into the list 'self.linear_layers'
        # (HINT: self.foo = [ bar(???) for ?? in ? ])
        # (HINT: Can you use zip here?)
        self.linear_layers = [Linear(inf, outf,weight_init_fn,bias_init_fn) for inf,outf in zip([self.input_size]+hiddens , hiddens+[self.output_size])]

    def forward(self, x):
        """
        Argument:
            x (np.array): (batch size, input_size)
        Return:
            out (np.array): (batch size, output_size)
        """
        # Complete the forward pass through your entire MLP.
        for i,layer in enumerate(self.linear_layers):
          x = layer(x)
          x = self.activation[i](x)
        return x


    def zero_grads(self):
        # Use numpyArray.fill(0.0) to zero out your backpropped derivatives in each
        # of your linear and batchnorm layers.
        for layer in self.linear_layers:
          layer.dW.fill(0.0)
          layer.db.fill(0.0)
    
    def step(self):
        # Apply a step to the weights and biases of the linear layers.
        # (You will add momentum later in the assignment to the linear layers)

        ## without momentum
        for i in range(len(self.linear_layers)):
            # Update weights and biases here
            layer = self.linear_layers[i]

            ## see above formula
            layer.momentum_W = self.momentum * layer.momentum_W - self.lr * layer.dW
            layer.W = layer.W + layer.momentum_W
            layer.momentum_b = self.momentum * layer.momentum_b - self.lr * layer.db
            layer.b = layer.b + layer.momentum_b

    def backward(self, labels):
        # Backpropagate through the activation functions, batch norm and
        # linear layers.
        # Be aware of which return derivatives and which are pure backward passes
        # i.e. take in a loss w.r.t it's output.
        
        final_layer = self.activation[-1]                   # final layer activation
        final_outputs = final_layer.state                   # output of final layer
        loss = self.criterion(final_outputs,labels)         # find the loss as we have predicted and label (True value)
        delta = self.criterion.derivative()                 # get the delta which is derivate loss w.r.t

        # Now we propagate error backwords and update the weights
        for i in range(self.layer-1,-1,-1):
          """ 
          while propagative backwards we get 2 function 
              1. when activation comes we take derivative 
              2. when linear layer comes again we update our delta
         """
          ## In backward function we will compute a gradients and pass the gradient from last layer to previous layer and this goes on
          ## gradient will be calculated during backward pass i.e. dL/dx , dx -> represent input receive by the last layer from it previous layer

          delta = delta * self.activations[i].derivative()              
          delta = self.linear_layers[i].backward(delta) 

    def error(self, labels):
        return (np.argmax(self.output, axis = 1) != np.argmax(labels, axis = 1)).sum()

    def total_loss(self, labels):
        return self.criterion(self.output, labels).sum()

    def __call__(self, x):
        return self.forward(x)

    def train(self):
        self.train_mode = True

    def eval(self):
        self.train_mode = False<jupyter_output><empty_output><jupyter_text>**`Reference`**:* [Advanced Training of Neural Networks - Shala2020](https://www.youtube.com/watch?v=KdjBONblhHw&t=2928s)<jupyter_code><jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup