2
$\begingroup$

I am trying to implement a gradient descent algorithm for a simple linear function:

y(x) = x

Where initial hypothesis function is:

h(x) = 0.5 * x

and learning rate:

alpha = 0.1

enter image description here

Target function graph is blue and hypothesis is green.

Cost function:

J = 1/2m * sum[(h(x) - y(x)) * (h(x) - y(x))]

Gradient descent:

q = q - alpha/m * sum[(h(x) - y(x)) * x] 

My implementation does not converge:

import numpy as np
import matplotlib.pyplot as plt

def y(x):
    return x

def get_h(q):
    """ Create hypothesis function
    
        Args:
            q - coefficient to multiply x with
            
        Returns:
            h(x) - hypothesis function
    """
    return lambda x: q*x 

def j(x, y, h):
    """Calculte a single value of a cost function 
    
        Args:
            x - target function argument values
            y - target function
            h - hypothesis function
            
        Returns:
            Value of a cost function for the given hypothesis function
    """
    m = len(x)
    return (1/(2*m)) * np.sum( np.power( (y(x) -h(x)),2 ) )

def df(h, y, xs):
    """Calculate gradient of a cost function
    
        Args:
            h - hypothesis function
            y - target function
            xs - x values
            
        Returns:
            differential of a cost function for a hypothesis with given q
            
    """
    df = np.sum((h(xs)-y(xs))*xs) / len(xs)
    return df

xs = np.array(range(100))
ys = y(xs)
hs = h(xs)

costs = []
qs = []
q = 0.5
alpha = 0.1
h = get_h(0.5) # initial hypothesis function
iters = 10
for i in range(iters):
    cost = j(xs,y,h)
    costs.append(cost)
    qs.append(q)
    print("q: {} --- cost: {}".format(q,cost))
    df_cost = df(h, y, xs)
    q = q - alpha * df_cost  # update coefficient
    h = get_h(q) # new hypothesis

What am I doing wrong? Should I account for q0 even if my target function intercept is zero?

Update / Solution

Answer from gunes is correct, the problem was with too big learning rate alpha = 0.1. Hypothesis function converges with target function even with alpha = 0.0001 and 30 iterations as opposed to alpha = 1E-5 and 100 iterations as gunes has suggested.

This updated code shows how it all works:

costs = []
df_costs = [] # cost differential values
qs = [] # cost parameters
q = 0.5 # initial coast parameter
h = get_h(0.5) # initial hypothesis function
alpha = 0.0001 # learning rate
iters = 30 # number of gradient descent itterations

_=plt.plot(xs,ys) # plot target function
for i in range(iters):
    _=plt.plot(xs,h(xs)) # plot hypothesis 
    cost = j(xs,y,h) # current cost
    costs.append(cost)
    qs.append(q) # current cost function parameter
    #print("q: {} --- cost: {}".format(q,cost))
    df_cost = df(h, y, xs) # get differential of the cost
    df_costs.append(df_cost)
    #print("df_cost: ",df_cost)
    q = q - alpha * df_cost  # update hypothesis parameter 
    h = get_h(q) # get new hypothesis
    
_=plt.title("Hypothesis converges with target")
_=plt.show()
_=plt.close()

enter image description here

_=plt.title("Costs")
_=plt.xlabel("Iterations")
_=plt.plot(range(iters), costs)
_=plt.show()
_=plt.close()

enter image description here

_=plt.title("Cost differentials")
_=plt.xlabel("Iterations")
_=plt.plot(range(iters), df_costs)
_=plt.show()
_=plt.close()

enter image description here

$\endgroup$
  • $\begingroup$ You can answer your own question by typing your solution in the Answer box. $\endgroup$ – Sycorax Aug 26 '20 at 15:13
2
$\begingroup$

Your gradients and update rules are correct. It's just you're using a large learning rate for your data, because your gradients are large. Try $\alpha=10^{-5}$ and $100$ iterations. You'll see that it'll converge.

$\endgroup$
  • $\begingroup$ Please see update of my question $\endgroup$ – stv Aug 26 '20 at 15:12
  • $\begingroup$ Yeah, my $\alpha$ was just a suggestion for a small value. $\endgroup$ – gunes Aug 26 '20 at 15:14
  • 1
    $\begingroup$ Thanks for your help! $\endgroup$ – stv Aug 26 '20 at 15:14

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.