0
$\begingroup$

I understand the idea behind momentum, and how to implement it with batch gradient descent, but I'm not sure how to implement it with mini-batch gradient descent. As I understand it, implementing momentum in batch gradient descent goes like this:

for example in training_set:
    calculate gradient for this example
    accumulate the gradient
for w, g in weights, gradients:
    w = w - learning_rate * g + momentum * gradients_at[-1]

Where gradients_at records the gradients for each weight at backprop iteration t.

Is this correct? If so, what modifications are necessary to apply this technique in mini-batch gradient descent?

$\endgroup$
1
$\begingroup$

The only difference between a batch and a mini-batch is that you're using part of the data set rather than the entire dataset during each epoch. Thus, you would calculate the gradient for only a subset of the samples in your training set and use these during each update epoch. Repeat for many epochs, where each epoch contains a different subset of the the full dataset.

$\endgroup$
0
$\begingroup$

The difference between Gradient Descent, Stochastic Gradient Descent, and Mini-batch Gradient Descent is the next:

  • Gradient Descent: You take all the data to compute the gradient.
  • Stochastic Gradient Descent: You only take 1 point to compute the gradient (the bath size is 1) It is faster than Gradient Descent but is too noisy and is affected by the data variance.
  • Mini-Batch Gradient Descent: you take n points (n< data_size) to compute the gradient. Normally you take n aleatory points. As a note, if you take in Mini-batch gradient descent n==data_size you will be computing normal gradient descent. The difference between Stochastic Gradient Descent and Mini-batch Gradient descent is the size we take for computing the gradient.

The algorithm to get the gradient is the same.

def stochastic_gradient_descent_step(m,b,data_sample):

    n_points = data_sample.shape[0] #size of data
    m_grad = 0
    b_grad = 0
    stepper = 0.0001 #this is the learning rate

    for i in range(n_points):

        #Get current pair (x,y)
        x = data_sample[i,0]
        y = data_sample[i,1]
        if(math.isnan(x)|math.isnan(y)): #it will prevent for crashing when some data is missing
            #print("is nan")
            continue

        #you will calculate the partical derivative for each value in data
        #Partial derivative respect 'm'
        dm = -((2/n_points) * x * (y - (m*x + b)))

        #Partial derivative respect 'b'
        db = - ((2/n_points) * (y - (m*x + b)))


        #Update gradient
        m_grad = m_grad + dm
        b_grad = b_grad + db

    #Set the new 'better' updated 'm' and 'b'   
    m_updated = m - stepper*m_grad
    b_updated = b - stepper*b_grad
    #print('m ', m)
    ##print('steepr*gradient ',stepper*m_grad)
    #print('m_updated', m_updated)
    '''
    Important note: The value '0.0001' that multiplies the 'm_grad' and 'b_grad' is the 'learning rate', but it's a concept
    out of the scope of this challenge. For now, just leave that there and think about it like a 'smoother' of the learn, 
    to prevent overshooting, that is, an extremly fast and uncontrolled learning.
    '''

    return m_updated,b_updated

We add the next function to get the batch that we are going to use

def getSmallRandomDataSample(data, batch_size, shuffle=True): #this method only covers the solution when suffle is true
    #stolchastic gradient descent

    #it will take tha batch of size 1, Im just putting this here so you can see the difference. You can delete the next 
    #two lines and it will work.
    if(batch_size==1):
        return np.array([random.choice(data)])
    #mini-batch gradient descent
    if(batch_size< data.shape[0]):
        if(shuffle):
            #the first two line are simulating like if we were choosing randomly points from the data
            index = np.random.permutation(data.shape[0]) #first suffle the index of data
            index = index[0:batch_size] #then we take the batch 
            #algorithm for getting the sample_data
            data_sample=[]
            for i in index:
                data_sample.append(data[i])
            return np.array(data_sample)

We execute the code with the next step

max_epochs = 100
print('Starting line: y = %.2fx + %.2f - Error: %.2f' %(m,b,sse))
start = time.time()
for i in range(max_epochs):
    data_sample = getSmallRandomDataSample(data,1)
    m,b = stochastic_gradient_descent_step(m,b,data_sample)
    sse = SSE(m,b,data)
    if(i%10==0):
        end = time.time()
        print('time consumtion = ',end-start)
        print('iteration ', i)
        start = time.time()
    #print('At step %d - Line: y = %.2fx + %.2f - Error: %.2f' %(i+1,m,b,sse))
print('\nBest  line: y = %.2fx + %.2f - Error: %.2f' %(m,b,sse))

You can check a complete example with some extra notes in my github repo

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.