<SYSTEM_TASK:>
Given the following text description, write Python code to implement the functionality described below step by step
<END_TASK>
<USER_TASK:>
Description:
Step12:  Module is an abstract class which defines fundamental methods necessary for a training a neural network. You do not need to change anything here, just read the comments.
Step19:  Sequential container
Define a forward and backward pass procedures.
Step21:  Layers
input
Step22:  This one is probably the hardest but as others only takes 5 lines of code in total. 
- input
Step23:  Implement dropout. The idea and implementation is really simple
Step24:  Activation functions
Here's the complete example for the Rectified Linear Unit non-linearity (aka ReLU)
Step25:  Implement Leaky Rectified Linear Unit. Expriment with slope.
Step31:  Criterions
Criterions are used to score the models answers.
Step32:  The MSECriterion, which is basic L2 norm usually used for regression, is implemented here for you.
Step33:  You task is to implement the ClassNLLCriterion. It should implement multiclass log loss. Nevertheless there is a sum over y (target) in that formula, 
remember that targets are one-hot encoded. This fact simplifies the computations a lot. Note, that criterions are the only places, where you divide by batch size.
<ASSISTANT_TASK:>
Python Code:
class Module(object):
    def __init__ (self):
        self.output = None
        self.gradInput = None
        self.training = True
    
    Basically, you can think of a module as of a something (black box) 
    which can process `input` data and produce `ouput` data.
    This is like applying a function which is called `forward`: 
        
        output = module.forward(input)
    
    The module should be able to perform a backward pass: to differentiate the `forward` function. 
    More, it should be able to differentiate it if is a part of chain (chain rule).
    The latter implies there is a gradient from previous step of a chain rule. 
    
        gradInput = module.backward(input, gradOutput)
    
    
    def forward(self, input):
        
        Takes an input object, and computes the corresponding output of the module.
        
        return self.updateOutput(input)
    def backward(self,input, gradOutput):
        
        Performs a backpropagation step through the module, with respect to the given input.
        
        This includes 
         - computing a gradient w.r.t. `input` (is needed for further backprop),
         - computing a gradient w.r.t. parameters (to update parameters while optimizing).
        
        self.updateGradInput(input, gradOutput)
        self.accGradParameters(input, gradOutput)
        return self.gradInput
    
    def updateOutput(self, input):
        
        Computes the output using the current parameter set of the class and input.
        This function returns the result which is stored in the `output` field.
        
        Make sure to both store the data in `output` field and return it. 
        
        
        # The easiest case:
            
        # self.output = input 
        # return self.output
        
        pass
    def updateGradInput(self, input, gradOutput):
        
        Computing the gradient of the module with respect to its own input. 
        This is returned in `gradInput`. Also, the `gradInput` state variable is updated accordingly.
        
        The shape of `gradInput` is always the same as the shape of `input`.
        
        Make sure to both store the gradients in `gradInput` field and return it.
        
        
        # The easiest case:
        
        # self.gradInput = gradOutput 
        # return self.gradInput
        
        pass   
    
    def accGradParameters(self, input, gradOutput):
        
        Computing the gradient of the module with respect to its own parameters.
        No need to override if module has no parameters (e.g. ReLU).
        
        pass
    
    def zeroGradParameters(self): 
        
        Zeroes `gradParams` variable if the module has params.
        
        pass
        
    def getParameters(self):
        
        Returns a list with its parameters. 
        If the module does not have parameters return empty list. 
        
        return []
        
    def getGradParameters(self):
        
        Returns a list with gradients with respect to its parameters. 
        If the module does not have parameters return empty list. 
        
        return []
    
    def training(self):
        
        Sets training mode for the module.
        Training and testing behaviour differs for Dropout, BatchNorm.
        
        self.training = True
    
    def evaluate(self):
        
        Sets evaluation mode for the module.
        Training and testing behaviour differs for Dropout, BatchNorm.
        
        self.training = False
    
    def __repr__(self):
        
        Pretty printing. Should be overrided in every module if you want 
        to have readable description. 
        
        return "Module"
Explanation: Module is an abstract class which defines fundamental methods necessary for a training a neural network. You do not need to change anything here, just read the comments.
End of explanation
class Sequential(Module):
    
         This class implements a container, which processes `input` data sequentially. 
         
         `input` is processed by each module (layer) in self.modules consecutively.
         The resulting array is called `output`. 
    
    
    def __init__ (self):
        super(Sequential, self).__init__()
        self.modules = []
   
    def add(self, module):
        
        Adds a module to the container.
        
        self.modules.append(module)
    def updateOutput(self, input):
        
        Basic workflow of FORWARD PASS:
        
            y_0    = module[0].forward(input)
            y_1    = module[1].forward(y_0)
            ...
            output = module[n-1].forward(y_{n-2})   
            
            
        Just write a little loop. 
        
        # Your code goes here. ################################################
        
#         module = self.modules[0]
#         y_curr = module.forward(input)
#         for i in range(1, len(self.modules)):
#             y_curr = self.modules[i].forward(y_curr)
#         self.output = y_curr
#         return self.output
#         
#         self.modules[0].output = self.modules[0].forward(input)
#         for i in range(1, len(self.modules)):
#             self.modules[i].output = self.modules[i].forward(self.modules[i-1].output)
#         self.output = self.modules[-1].output
        
        self.y = []
        self.y.append(self.modules[0].forward(input))
        for i in range(1, len(self.modules)):
            self.y.append(self.modules[i].forward(self.y[-1]))
        self.output = self.y[-1]
        return self.output
        
    
    def backward(self, input, gradOutput):
        
        Workflow of BACKWARD PASS:
            
            g_{n-1} = module[n-1].backward(y_{n-2}, gradOutput)
            g_{n-2} = module[n-2].backward(y_{n-3}, g_{n-1})
            ...
            g_1 = module[1].backward(y_0, g_2)   
            gradInput = module[0].backward(input, g_1)   
             
             
        !!!
                
        To ech module you need to provide the input, module saw while forward pass, 
        it is used while computing gradients. 
        Make sure that the input for `i-th` layer the output of `module[i]` (just the same input as in forward pass) 
        and NOT `input` to this Sequential module. 
        
        !!!
        
        
        # Your code goes here. ################################################
        
#         self.modules[-1].gradInput = self.modules[-1].backward(self.modules[-2].output, gradOutput)
#         for i in range(len(self.modules) - 2, 0, -1):
#             self.modules[i].gradInput = self.modules[i].backward(self.modules[i-1].output, self.modules[i+1].gradInput)
#         i = 0
#         self.modules[0].gradInput = self.modules[0].backward(input, self.modules[i+1].gradInput)
#         self.gradInput = self.modules[0].gradInput
        
        self.gradInput = self.modules[-1].backward(self.y[-2], gradOutput)
        for i in range(len(self.modules) - 2, 0, -1):
            self.gradInput = self.modules[i].backward(self.y[i-1], self.gradInput)
        self.gradInput = self.modules[0].backward(input, self.gradInput)
        return self.gradInput
      
    def zeroGradParameters(self): 
        for module in self.modules:
            module.zeroGradParameters()
    
    def getParameters(self):
        
        Should gather all parameters in a list.
        
        return [x.getParameters() for x in self.modules]
    
    def getGradParameters(self):
        
        Should gather all gradients w.r.t parameters in a list.
        
        return [x.getGradParameters() for x in self.modules]
    
    def __repr__(self):
        string = "".join([str(x) + '\n' for x in self.modules])
        return string
    
    def __getitem__(self,x):
        return self.modules.__getitem__(x)
Explanation: Sequential container
Define a forward and backward pass procedures.
End of explanation
class Linear(Module):
    
    A module which applies a linear transformation 
    A common name is fully-connected layer, InnerProductLayer in caffe. 
    
    The module should work with 2D input of shape (n_samples, n_feature).
    
    def __init__(self, n_in, n_out):
        super(Linear, self).__init__()
       
        # This is a nice initialization
        stdv = 1./np.sqrt(n_in)
        self.W = np.random.uniform(-stdv, stdv, size = (n_out, n_in))
        self.b = np.random.uniform(-stdv, stdv, size = n_out)
        
        self.gradW = np.zeros_like(self.W)
        self.gradb = np.zeros_like(self.b)
        
    def updateOutput(self, input):
        # Your code goes here. ################################################
        
#         N = input.shape[0]
#         newx = input.reshape((N,-1))
        self.output = input.dot(self.W.T) + self.b
        return self.output
    
    def updateGradInput(self, input, gradOutput):
        # Your code goes here. ################################################
        
#         x, dout = input, gradOutput
        
#         N = x.shape[0]
#         D = np.prod(x.shape[1:])
#         x2 = np.reshape(x, (N, D))
#         dx2 = np.dot(dout, w.T) # N x D
#         dw = np.dot(x2.T, dout) # D x M
#         db = np.dot(dout.T, np.ones(N)) # M x 1
#         dx = np.reshape(dx2, x.shape)
#         self.gradInput = dx, dw, db #FIXME ?
        
#         self.gradb = np.sum(gradOutput,axis = 0)
        self.gradInput = gradOutput.dot(self.W)#.reshape(*input.shape)
#         self.gradW = input.reshape((input.shape[0],-1)).T.dot(gradOutput)
        return self.gradInput
    
    def accGradParameters(self, input, gradOutput):
        # Your code goes here. ################################################
        self.gradb = np.sum(gradOutput,axis = 0)
        self.gradW = gradOutput.T.dot(input)
#         self.gradW = input.reshape((input.shape[0],-1)).T.dot(gradOutput)
#         pass
    
    def zeroGradParameters(self):
        self.gradW.fill(0)
        self.gradb.fill(0)
        
    def getParameters(self):
        return [self.W, self.b]
    
    def getGradParameters(self):
        return [self.gradW, self.gradb]
    
    def __repr__(self):
        s = self.W.shape
        q = 'Linear %d -> %d' %(s[1],s[0])
        return q
input_dim = 3
output_dim = 2
x = np.random.randn(5, input_dim)
w = np.random.randn(output_dim, input_dim)
b = np.random.randn(output_dim)
dout = np.random.randn(5, output_dim)
linear = Linear(input_dim, output_dim)
def update_W_matrix(new_W):
    linear.W = new_W
    return linear.forward(x)
def update_bias(new_b):
    linear.b = new_b
    return linear.forward(x)
dx = linear.backward(x, dout)
dx_num = eval_numerical_gradient_array(lambda x: linear.forward(x), x, dout)
dw_num = eval_numerical_gradient_array(update_W_matrix, w, dout)
db_num = eval_numerical_gradient_array(update_bias, b, dout)
print 'Testing Linear_backward function:'
print 'dx error: ', rel_error(dx_num, dx)
print 'dw error: ', rel_error(dw_num, linear.gradW)
print 'db error: ', rel_error(db_num, linear.gradb)
Explanation: Layers
input:   batch_size x n_feats1
output: batch_size x n_feats2
End of explanation
class SoftMax(Module):
    def __init__(self):
         super(SoftMax, self).__init__()
    
    def updateOutput(self, input):
        # start with normalization for numerical stability
        self.output = np.subtract(input, input.max(axis=1, keepdims=True))
        
        # Your code goes here. ################################################
        self.output = np.exp(self.output)
#         out_sum = self.output.sum(axis=1, keepdims=True)
        self.output = np.divide(self.output, self.output.sum(axis=1, keepdims=True))
        return self.output
    
    def updateGradInput(self, input, gradOutput):
        # Your code goes here. ################################################
#         N = self.output.shape[0]
#         self.gradInput = self.output.copy()
#         self.gradInput[np.arange(N).astype(np.int), gradOutput.astype(np.int)] -= 1
#         self.gradInput /= N
        batch_size, n_feats = self.output.shape
        a = self.output.reshape(batch_size, n_feats, -1)
        b = self.output.reshape(batch_size, -1, n_feats)
        self.gradInput = np.multiply(gradOutput.reshape(batch_size, -1, n_feats), 
                                    np.subtract(np.multiply(np.eye(n_feats), a),
                                                np.multiply(a, b))).sum(axis=2)
        return self.gradInput
    
    def __repr__(self):
        return "SoftMax"
soft_max = SoftMax()
x = np.random.randn(5, 3)
dout = np.random.randn(5, 3)
dx_numeric = eval_numerical_gradient_array(lambda x: soft_max.forward(x), x, dout)
dx = soft_max.backward(x, dout)
# The error should be around 1e-10
print 'Testing SoftMax grad:'
print 'dx error: ', rel_error(dx_numeric, dx)
Explanation: This one is probably the hardest but as others only takes 5 lines of code in total. 
- input:   batch_size x n_feats
- output: batch_size x n_feats
End of explanation
class Dropout(Module):
    def __init__(self, p=0.5):
        super(Dropout, self).__init__()
        
        self.p = p
        self.mask = None
        
    def updateOutput(self, input):
        # Your code goes here. ################################################
        self.mask = np.random.binomial(1, self.p, input.shape) if self.training else np.ones(input.shape)
        self.output = input*self.mask
        return  self.output
    
    def updateGradInput(self, input, gradOutput):
        # Your code goes here. ################################################
        self.gradInput = gradOutput*self.mask
        return self.gradInput
        
    def __repr__(self):
        return "Dropout"
Explanation: Implement dropout. The idea and implementation is really simple: just multimply the input by $Bernoulli(p)$ mask. 
This is a very cool regularizer. In fact, when you see your net is overfitting try to add more dropout.
While training (self.training == True) it should sample a mask on each iteration (for every batch). When testing this module should implement identity transform i.e. self.output = input.
input:   batch_size x n_feats
output: batch_size x n_feats
End of explanation
class ReLU(Module):
    def __init__(self):
         super(ReLU, self).__init__()
    
    def updateOutput(self, input):
        self.output = np.maximum(input, 0)
        return self.output
    
    def updateGradInput(self, input, gradOutput):
        self.gradInput = np.multiply(gradOutput , input > 0)
        return self.gradInput
    
    def __repr__(self):
        return "ReLU"
Explanation: Activation functions
Here's the complete example for the Rectified Linear Unit non-linearity (aka ReLU):
End of explanation
class LeakyReLU(Module):
    def __init__(self, slope = 0.03):
        super(LeakyReLU, self).__init__()
            
        self.slope = slope
        
    def updateOutput(self, input):
        # Your code goes here. ################################################
#         self.output = np.maximum(input, input*self.slope)
        self.output = input.copy()
        self.output[self.output < 0] *= self.slope
        return  self.output
    
    def updateGradInput(self, input, gradOutput):
        # Your code goes here. ################################################
#         self.gradInput = np.multiply(gradOutput, input > 0) #FIXME
        self.gradInput = gradOutput.copy()
        self.gradInput[input < 0] *= self.slope
        return self.gradInput
    
    def __repr__(self):
        return "LeakyReLU"
Explanation: Implement Leaky Rectified Linear Unit. Expriment with slope.
End of explanation
class Criterion(object):
    def __init__ (self):
        self.output = None
        self.gradInput = None
        
    def forward(self, input, target):
        
            Given an input and a target, compute the loss function 
            associated to the criterion and return the result.
            
            For consistency this function should not be overrided,
            all the code goes in `updateOutput`.
        
        return self.updateOutput(input, target)
    def backward(self, input, target):
        
            Given an input and a target, compute the gradients of the loss function
            associated to the criterion and return the result. 
            For consistency this function should not be overrided,
            all the code goes in `updateGradInput`.
        
        return self.updateGradInput(input, target)
    
    def updateOutput(self, input, target):
        
        Function to override.
        
        return self.output
    def updateGradInput(self, input, target):
        
        Function to override.
        
        return self.gradInput   
    def __repr__(self):
        
        Pretty printing. Should be overrided in every module if you want 
        to have readable description. 
        
        return "Criterion"
Explanation: Criterions
Criterions are used to score the models answers.
End of explanation
class MSECriterion(Criterion):
    def __init__(self):
        super(MSECriterion, self).__init__()
        
    def updateOutput(self, input, target):   
        self.output = np.sum(np.power(input - target,2)) / input.shape[0]
        return self.output 
 
    def updateGradInput(self, input, target):
        self.gradInput  = (input - target) * 2 / input.shape[0]
        return self.gradInput
    def __repr__(self):
        return "MSECriterion"
Explanation: The MSECriterion, which is basic L2 norm usually used for regression, is implemented here for you.
End of explanation
class ClassNLLCriterion(Criterion):
    def __init__(self):
        a = super(ClassNLLCriterion, self)
        super(ClassNLLCriterion, self).__init__()
        
    def updateOutput(self, input, target): 
        
        # Use this trick to avoid numerical errors
        eps = 1e-15 
        input_clamp = np.clip(input, eps, 1 - eps)
        
        # Your code goes here. ################################################
#         N = input_clamp.shape[0]
#         self.output = -np.sum(np.log(input_clamp[np.arange(N).astype(np.int), target.astype(np.int)]+1e-8)) / N
        self.output = -np.sum(np.multiply(target, np.log(input_clamp))) / len(input)
        return self.output
    def updateGradInput(self, input, target):
        
        # Use this trick to avoid numerical errors
        input_clamp = np.maximum(1e-15, np.minimum(input, 1 - 1e-15) )
                
        # Your code goes here. ################################################
        self.gradInput = np.subtract(input_clamp, target) / len(input)
        return self.gradInput
    
    def __repr__(self):
        return "ClassNLLCriterion"
Explanation: You task is to implement the ClassNLLCriterion. It should implement multiclass log loss. Nevertheless there is a sum over y (target) in that formula, 
remember that targets are one-hot encoded. This fact simplifies the computations a lot. Note, that criterions are the only places, where you divide by batch size.
End of explanation
<END_TASK>