0
$\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

Answer: https://stats.stackexchange.com/questions/484750/linear-function-gradient-descent

$\endgroup$
1
  • $\begingroup$ Cross posting can get one in trouble. Be careful. $\endgroup$ Aug 26, 2020 at 15:32

1 Answer 1

1
$\begingroup$

As you and @gunes pointed out in this post, your formula are correct, but hyperparameters $\alpha$ and $iterations$ were not well adjusted.

$\endgroup$
4
  • $\begingroup$ Can you show a before/after plot or error track showing convergence? $\endgroup$ Aug 26, 2020 at 15:00
  • 1
    $\begingroup$ I have added code, plot and output. Hope it helps. $\endgroup$
    – etiennedm
    Aug 26, 2020 at 15:15
  • 2
    $\begingroup$ Please see question update (answer at stats.stackexchange.com/questions/484750/…) $\endgroup$
    – stv
    Aug 26, 2020 at 15:17
  • $\begingroup$ oh yep, you're right, my mistake $\endgroup$
    – etiennedm
    Aug 26, 2020 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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