<jupyter_start><jupyter_text>Optimization of Neural Networks - Part 1  Main Contents For today1. GD vs. SGD vs. Mini-Batch GD2. Newton's Method, RMSProp, Momentum, Nesterov's Accelerated Gradient, Adam3. Initialization (Xavier, Kaiming)  Current State1. Data1. We have finalized our initial neural network architecture to train1. How will my neural network learn?  1. Minimize the loss function with respect to the network parameters  1. Calculus to rescue -> Iterative approach -> Gradient Descent  Batch Gradient Descent vs. Stochastic Gradient Descent vs. Mini-batch Gradient DescentBatch Gradient Descent1. Mathematically provable and guranteed to converge to global minimum for convex surfaces with a sufficiently small learning rate (lr <= 1/L for L-smooth surface)2. Tends to be slow since we only make a step after looking through all the data3. Not onlineStochastic Gradient Descent1. Faster. Frequent updates but high variance. Large swings in parameter values2. Online3. Convergence can become an issue but with appropriate learning rate scheduling, convergence behaviour is close to that of Batch Gradient Descent4. Opportunity to jump to a better local minimas. Think exploration vs. exploitationMini-batch Gradient Descent1. More stable convergence as parameters update variance reduces2. Can be as fast as SGD due to parallelization3. Searches through a larger part of the parameter space ( based on empirical data )<jupyter_code>from IPython.display import HTML

HTML('''<script>
code_show=true; 
function code_toggle() {
 if (code_show){
 $('div.input').hide();
 } else {
 $('div.input').show();
 }
 code_show = !code_show
} 
$( document ).ready(code_toggle);
</script>
<form action="javascript:code_toggle()"><input type="submit" value="Click here to toggle on/off the raw code."></form>''')
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatches
import torch

init = torch.tensor([-5.0,7.5])

class QuadFunc:
    '''
    Quadratic function
    '''
    
    def __init__(self,a,b,c,d,e):
        self.a = a
        self.b = b
        self.c = c
        self.d = d
        self.e = e
    
    def getParams(self,x,y):
        if y is None:
            y = x[1]
            x = x[0]
        
        return x, y
    
    def __call__(self,x,y=None):
        x,y = self.getParams(x,y)
        return 0.5*(self.a*x**2 + self.b*y**2 + 2*self.c*x*y) + self.d*x + self.e*y
    
    def grad(self,x,y=None):
        x,y = self.getParams(x,y)
        return torch.tensor([self.a*x+self.c*y+self.d,self.b*y+self.c*x+self.e])
    
    def hess(self,x,y=None):
        x,y = self.getParams(x,y)
        return torch.tensor([[self.a,self.c],[self.c,self.b]])

class GradientDescent:
    '''
    1st order optimizer with support for RMSProps and Momentum.
    '''
    
    def __init__(self,lr=1,b1=0.9,b2=0.999):
        self.lr = lr # learning rate
        self.b1 = b1 # grad aggregation param
        self.b2 = b2 # grad^2 aggregation param
        
        self.v = 0 # grad aggregation
        self.w = 0 # grad^2 aggregation
        self.t = 0
            
        self.eps = 1.0e-9
        
    def __call__(self,grad,hess):
        
        self.t += 1
        
        # aggregation
        self.v = self.b1*(self.v) + (1-self.b1)*grad
        self.w = self.b2*(self.w) + (1-self.b2)*grad**2
        
        # bias correction
        vcorr = self.v/(1-self.b1**self.t)
        wcorr = self.w/(1-self.b2**self.t) if self.b2 != 0 else 1
        
        return -self.lr*vcorr/( wcorr**0.5 + self.eps )
        
    
class Newtons:
    '''
    2nd order optimization
    '''
    
    def __init__(self,lr=1):
        self.lr = lr
    
    def __call__(self,grad,hess):
        return -self.lr*torch.matmul(torch.inverse(hess),grad)
        

class NAG:
    
    def __init__(self,lr=1,gamma=0.9):
        self.lr = lr
        self.gamma = gamma
        self.m = 0
        
    def __call__(self,grad,hess):
        # Grad and Hess passed here are based on future location based on prior momentum
        
        self.m = self.gamma * self.m + grad
        return -self.lr*self.m

class NAG2:
    
    def __init__(self,lr=1,gamma=0.9):
        self.lr = lr
        self.gamma = gamma
        self.m = 0
        
    def __call__(self,grad,hess):
        # Dozat's implementation
        
        self.m = self.gamma * self.m + grad
        return -self.lr*(grad+self.gamma*self.m)
    
def runOptim(init,optim,func,steps,nag=False):
    
    curpos = init
    path = [curpos]
    val = [func(curpos)]
    
    for _ in range(steps):
        
        if nag:
            grad = func.grad(curpos-optim.lr*optim.gamma*optim.m)
            hess = func.hess(curpos-optim.lr*optim.gamma*optim.m)            
        else:
            grad = func.grad(curpos)
            hess = func.hess(curpos)
            
        dx = optim(grad,hess)
        curpos = curpos + dx
        path.append(curpos)
        val.append(func(curpos))
    
    return path, val

def showPath(func,init,paths,labels,colors,title):

    x = torch.arange(-10,10,0.05)
    y = torch.arange(-10,10,0.05)
    
    # create meshgrid
    xx, yy = torch.meshgrid(x,y)
    zz = func(xx,yy)
    
    # create contour
    fig, ax = plt.subplots(1,1,figsize=(16,10))
    cp = ax.contourf(xx,yy,zz)
    fig.colorbar(cp)
    
    # mark initial point
    ax.plot(init[0],init[1],'ro')
    ax.text(init[0]+0.5,init[1]+0.5,'Intial Point',color='white')
    
    # Plot paths
    for pnum in range(len(paths)):
        for i in range(len(paths[pnum])-1):
            curpos = paths[pnum][i]
            d = paths[pnum][i+1] - curpos
            ax.arrow(curpos[0],curpos[1],d[0],d[1],color=colors[pnum],head_width=0.2)
            ax.text(curpos[0]+d[0],curpos[1]+d[1],str(i),color='white')
    
    # Add legend
    legends = []
    for col in colors:
        legends.append(mpatches.Patch(color=col))
    ax.legend(legends,labels)
    
    # Add title
    ax.set_title(title)
# How regular gradient descent works

init = torch.tensor([-5.0,7.5])
simple = QuadFunc(1,1,0,0,0)
steps = 10
regGD = GradientDescent(0.5,0,0)
path, _ = runOptim(init,regGD,simple,steps)
showPath(simple,init,[path],['Regular Gradient Descent'],['r'],'Regular Gradient Descent for Simple Quadratic Function')<jupyter_output><empty_output><jupyter_text>Issues wih Gradient Descent<jupyter_code># Saddle Points
# Highly non-convex loss surfaces in DL are peppered with saddle points which make progress hard

saddle = QuadFunc(1,-1,0,0,0)
init = torch.tensor([-7.5,0.0])
steps = 20
regGD = GradientDescent(0.5,0,0)
func = saddle

path, _ = runOptim(init,regGD,func,steps)
showPath(func,init,[path],['Regular Gradient Descent'],['r'],'Regular Gradient Descent for Saddle Quadratic Function')
# Pathological Curvature or Valleys
# Severly limits the learning rate that can be used to make faster progress and also explore larger area
# Also creates issues in terms of speed of convergence

a = 1/torch.sqrt(torch.tensor(2.0))
init = torch.matmul(torch.tensor([[a,a],[-a,a]]),torch.tensor([-5.0,7.5]))
patho = QuadFunc(a,a,-a,a,a)

#init = torch.tensor([-5.0,7.5])
#patho = QuadFunc(1,0,0,0,1)
steps = 10
regGD = GradientDescent(1.3,0,0)
func = patho

path, _ = runOptim(init,regGD,func,steps)
showPath(func,init,[path],['Regular Gradient Descent'],['r'],'Regular Gradient Descent for Valley Quadratic Function')<jupyter_output><empty_output><jupyter_text>Fixing Gradient Descent  Newton's Method$\theta_{t+1} = \theta_{t} - \eta*H_{t}^{-1}*g_{t}$$\theta_{t}$ is the parameter at time-step $t$$\eta$ is the learning rate$H_{t}^{-1}$ is the inverse Hessian at time-step $t$$g_{t}$ is the gradient at time-step $t$<jupyter_code># Newton's Method
# Appropriately scaled the gradient information with the Hessian to rescale steps in different directions and obtain faster convergence
# Takes longer steps in the direction of lower gradient. Think Taylor series

a = 1/torch.sqrt(torch.tensor(2.0))
init = torch.matmul(torch.tensor([[a,a],[-a,a]]),torch.tensor([-5.0,7.5]))
patho = QuadFunc(a,a,-0.8*a,a,a)

steps = 3
lr = 1.0

newGD = Newtons(lr)
regGD = GradientDescent(lr,0,0)

func = patho

path1, _ = runOptim(init,regGD,func,steps)
path2, _ = runOptim(init,newGD,func,steps)

showPath(func,init,[path1,path2],['Regular Gradient Descent','Newton Method'],['r','y'],'Regular Gradient Descent for Saddle Quadratic Function')
# Newton's method
# Unfortunately Newton's method is attrached to saddle points.
# Also there are practical issues with Hessian calculations.
# Moreover in DL, the loss surfaces are non-convex and this may result in extremely bad outcomes when using Newton's method.

saddle = QuadFunc(1.0,-1.0,0.0,0.0,0.0)
init = torch.tensor([-7.5,0.5])
steps = 5

regGD = GradientDescent(0.5,0,0)
newGD = Newtons(0.5)

func = saddle

path1, _ = runOptim(init,regGD,func,steps)
path2, _ = runOptim(init,newGD,func,steps)

showPath(func,init,[path1,path2],['Regular Gradient Descent','Newton Method'],['r','y'],'Saddle Quadratic Function')<jupyter_output><empty_output><jupyter_text>RMSProp$v_{t+1} = \gamma v_{t} + (1-\gamma) g_{t}^{2}$$\Delta\theta_{t+1} = \frac{-\eta}{\sqrt{v_{t+1}}+\epsilon}g_{t}$$\theta_{t+1} = \theta_{t} + \Delta\theta_{t+1}$$\theta_{t}$ is the parameter at time-step $t$$\eta$ is the learning rate$g_{t}$ is the gradient at time-step $t$$v_{t}$ is the exponentially decaying average of squared gradients at time-step $t$$\epsilon$ is used to avoid division by zero<jupyter_code># RMSProp: Why can't we have different learning rate for each parameter? But which lr for which param?
# Dampens the osciallations and thereby avoid divergences and can therefore handle larger learning rates.
# Ability to provide larger updates to parameters associated with infrequently occuring features i.e features
# with mostly small gradients compared to other parameters.
# Check AdaDelta for another version and AdaGrad for a more primitive version

a = 1/torch.sqrt(torch.tensor(2.0))
init = torch.matmul(torch.tensor([[a,a],[-a,a]]),torch.tensor([-5.0,7.5]))
patho = QuadFunc(a,a,-0.8*a,a,a)

steps = 20
lr = 1.6

RMSPropGD = GradientDescent(lr,0,0.9)
regGD = GradientDescent(lr,0,0)

func = patho

path1, _ = runOptim(init,regGD,func,steps)
path2, _ = runOptim(init,RMSPropGD,func,steps)

showPath(func,init,[path1,path2],['Regular Gradient Descent','RMSProp'],['r','y'],'Regular Gradient Descent for Saddle Quadratic Function')
# RMSProp
# Can become very slow. Therefore when the parameter space is large i.e step size is smaller compared to the area
# to be explored, RMSProp can slow down greatly!

init = torch.tensor([-5.0,7.5])
simple = QuadFunc(1,1,0,0,0)
steps = 10

lr = 0.5

RMSPropGD = GradientDescent(lr,0,0.9)
regGD = GradientDescent(lr,0,0)

func = simple

path1, _ = runOptim(init,regGD,func,steps)
path2, _ = runOptim(init,RMSPropGD,func,steps)

showPath(func,init,[path1,path2],['Regular Gradient Descent','RMSProp'],['r','y'],'Regular Gradient Descent for Saddle Quadratic Function')<jupyter_output><empty_output><jupyter_text>Momentum$m_{t+1} = \gamma m_{t} + \eta g_{t}$$\theta_{t+1} = \theta_{t} - m_{t+1}$$\theta_{t}$ is the parameter at time-step $t$$\eta$ is the learning rate$g_{t}$ is the gradient at time-step $t$$m_{t}$ is the exponentially decaying average of gradients at time-step $t$<jupyter_code># Momentum = Awesome
# Momentum speeds things up in direction where gradient direction remains the same and slows things down in
# directions where oscillations occur. As a result it is also prone to oscillations when it speeds up way too much!

a = 1/torch.sqrt(torch.tensor(2.0))
init = torch.matmul(torch.tensor([[a,a],[-a,a]]),torch.tensor([-5.0,7.5]))
patho = QuadFunc(a,a,-0.8*a,a,a)

steps = 20
lr = 0.5

momGD = GradientDescent(lr,0.9,0)
regGD = GradientDescent(lr,0,0)

func = patho

path1, _ = runOptim(init,regGD,func,steps)
path2, _ = runOptim(init,momGD,func,steps)

showPath(func,init,[path1,path2],['Regular Gradient Descent','Momentum'],['r','y'],'Saddle Quadratic Function')<jupyter_output><empty_output><jupyter_text>Nesterov's Accelerated Gradient$g_{t} = \nabla f(\theta_{t}-\eta \gamma m_{t})$$m_{t+1} = \gamma m_{t} + g_{t}$$\theta_{t+1} = \theta_{t} - \eta m_{t+1}$$\theta_{t}$ is the parameter at time-step $t$$\eta$ is the learning rate$g_{t}$ is the gradient at time-step $t$$m_{t}$ is the exponentially decaying average of gradients at time-step $t$<jupyter_code># NAG
# Smarter version of momentum
# Has an equivalent version which is a lot easier to implement

a = 1/torch.sqrt(torch.tensor(2.0))
init = torch.matmul(torch.tensor([[a,a],[-a,a]]),torch.tensor([-5.0,7.5]))
patho = QuadFunc(a,a,-0.8*a,a,a)

steps = 10
lr = 0.5
gamma = 0.9

momGD = GradientDescent(lr,gamma,0)
nagGD = NAG(lr,gamma)
nag2GD = NAG2(lr,gamma)

func = patho

path1, _ = runOptim(init,nagGD,func,steps,True)
path2, _ = runOptim(init,nag2GD,func,steps)
path3, _ = runOptim(init,momGD,func,steps)

showPath(func,init,[path1,path2,path3],['NAG','NAG2','Momentum'],['r','y','white'],'Saddle Quadratic Function')<jupyter_output><empty_output><jupyter_text>Adam$v_{t+1} = \gamma_{1} v_{t} + (1-\gamma_{1}) g_{t}^{2}$$m_{t+1} = \gamma_{2} m_{t} + (1-\gamma_{2}) g_{t}$$\hat{v}_{t+1} = \frac{v_{t+1}}{1-\gamma_{1}^{t+1}}$$\hat{m}_{t+1} = \frac{m_{t+1}}{1-\gamma_{2}^{t+1}}$$\Delta\theta_{t+1} = \frac{-\eta}{\sqrt{\hat{v}_{t+1}}+\epsilon}\hat{m}_{t+1}$$\theta_{t+1} = \theta_{t} + \Delta\theta_{t+1}$$\theta_{t}$ is the parameter at time-step $t$$\eta$ is the learning rate$g_{t}$ is the gradient at time-step $t$$v_{t}$ is the exponentially decaying average of squared gradients at time-step $t$$m_{t}$ is the exponentially decaying average of gradients at time-step $t$$\epsilon$ is used to avoid division by zero<jupyter_code># Adam: Best of all worlds?

a = 1/torch.sqrt(torch.tensor(2.0))
init = torch.matmul(torch.tensor([[a,a],[-a,a]]),torch.tensor([-5.0,7.5]))
patho = QuadFunc(a,a,-0.8*a,a,a)

steps = 20
lr = 1.6

adamGD = GradientDescent(lr,0.9,0.999)
regGD = GradientDescent(lr,0,0)
momGD = GradientDescent(lr,0.9,0)
rmsGD = GradientDescent(lr,0,0.999)

func = patho

path1, _ = runOptim(init,regGD,func,steps)
path2, _ = runOptim(init,adamGD,func,steps)
path3, _ = runOptim(init,momGD,func,steps)
path4, _ = runOptim(init,rmsGD,func,steps)

showPath(func,init,[path1,path2,path3,path4],['GD','Adam','Momentum','RMSProp'],['r','y','w','g'],'Saddle Quadratic Function')<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.15133037694013304, 'fraction_numerical': 0.026676829268292682, 'mean_word_length': 3.8760135135135134, 'pattern_counts': {'":': 0, '<': 35, '<?xml version=': 0, '>': 36, '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': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '548787', 'license': 'MIT', 'n_tokens_mistral': 5420, 'n_tokens_neox': 5215, 'n_words': 1249, 'path': 'Notes-Courses/Deep-Learning-CMU/Optimizing the Network - 1.ipynb', 'repo_name': 'SuperBruceJia/paper-reading', 'size': '14432'}