Descida gradiente de função linear

Question

Estou tentando implementar um algoritmo de descida gradiente para uma função linear simples:

y(x) = x

Onde a função de hipótese inicial é:

h(x) = 0.5 * x

e taxa de aprendizagem:

alpha = 0.1

O gráfico da função alvo é azul e a hipótese é verde.

Função de custo:

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

Gradiente descendente:

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

Minha implementação não 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

O que estou fazendo errado? Devo contabilizar q0 mesmo se minha interceptação da função de destino for zero?

Atualização / Solução

A resposta de gunesestá correta, o problema era com uma taxa de aprendizado muito grande alpha = 0.1. A função de hipótese converge com a função de destino mesmo com alpha = 0.0001e 30 iterações em oposição a alpha = 1E-5e 100 iterações como gunessugerido.

Este código atualizado mostra como tudo funciona:

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

Seus gradientes e regras de atualização estão corretos. Você está usando uma grande taxa de aprendizado para seus dados, porque seus gradientes são grandes. Experimentar$\alpha=10^{-5}$ e $100$iterações. Você verá que ele convergirá.