Descenso de gradiente de función lineal

Question

Estoy tratando de implementar un algoritmo de descenso de gradiente para una función lineal simple:

y(x) = x

Donde la función de hipótesis inicial es:

h(x) = 0.5 * x

y tasa de aprendizaje:

alpha = 0.1

El gráfico de la función objetivo es azul y la hipótesis es verde.

Función de costo:

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

Descenso de gradiente:

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

Mi implementación no 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

¿Qué estoy haciendo mal? ¿Debo tener en cuenta q0 incluso si la intersección de mi función de destino es cero?

Actualización / Solución

La respuesta de guneses correcta, el problema fue con una tasa de aprendizaje demasiado alta alpha = 0.1. La función de hipótesis converge con la función de destino incluso con alpha = 0.0001y 30 iteraciones en lugar de alpha = 1E-5y 100 iteraciones como se gunesha sugerido.

Este código actualizado muestra cómo funciona todo:

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()

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

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

Answer 1

Tus gradientes y reglas de actualización son correctas. Es solo que está utilizando una gran tasa de aprendizaje para sus datos, porque sus gradientes son grandes. Tratar$\alpha=10^{-5}$ y $100$iteraciones. Verás que convergerá.