<jupyter_start><jupyter_text>---layout: pagetitle: Gradiente Descendentenav_order: 17---[](https://colab.research.google.com/github/icd-ufmg/icd-ufmg.github.io/blob/master/_lessons/17-gradiente.ipynb) Gradiente Descendente{: .no_toc .mb-2 }Entendimento de relação entre dados.{: .fs-6 .fw-300 }{: .no_toc .text-delta }Resultados Esperados1. Entender como o computador otimiza funções1. Entender o algoritmo de gradiente descendente e ascendente1. Implementar os dois---**Sumário**1. TOC{:toc}---<jupyter_code># -*- coding: utf8

from scipy import stats as ss

import matplotlib.pyplot as plt
import numpy as np
import pandas as pd
import seaborn as sns
plt.style.use('seaborn-colorblind')
plt.rcParams['figure.figsize']  = (16, 10)
plt.rcParams['axes.labelsize']  = 20
plt.rcParams['axes.titlesize']  = 20
plt.rcParams['legend.fontsize'] = 20
plt.rcParams['xtick.labelsize'] = 20
plt.rcParams['ytick.labelsize'] = 20
plt.rcParams['lines.linewidth'] = 4
plt.ion()
def despine(ax=None):
    if ax is None:
        ax = plt.gca()
    # Hide the right and top spines
    ax.spines['right'].set_visible(False)
    ax.spines['top'].set_visible(False)

    # Only show ticks on the left and bottom spines
    ax.yaxis.set_ticks_position('left')
    ax.xaxis.set_ticks_position('bottom')<jupyter_output><empty_output><jupyter_text>Aula 18 - Gradiente Descendente (*Gradient Descent*)**Material adaptado do Professor <NAME>**Ao fazer ciência de dados é comum se deparar com casos onde buscamos um melhor modelo. Diferente dos testes de hipóteses, onde buscamos a chance dos nossos dados em um modelo. Aqui, estamos tentando encontrar o melhor modelo para uma determinada situação. Geralmente "melhor" significará algo como "minimiza o erro do modelo" ou "maximiza a verossimilhaça dos dados". Para casos simples, como na regressão linear, é possível achar o melhor modelo usando cálculo. Porém, em casos particulares, precisamos achar tal modelo na marra. Nossa abordagem será uma técnica chamada gradiente descendente, que funciona muito bem para diferentes cenário. Gradiente descendente é a base da maioria dos __frameworks__ de aprendizado de máquina. Você pode não achar isso super excitante por si só, mas ao combinar gradiente descendente com modelos complexos temos a fórmula do sucesso de aprendizando hoje em dia. A ideia por trás do gradiente descendenteVamos focar no caso de regressão linear com dados z-normalizados. Aqui, temos um modelo muito simples:$$y_i = \beta x_i + \epsilon_i$$Sabemos tratar com o mesmo de um ponto de vista de minimos quadrados como também de máxima verossimilhança. Vamos explorar uma base onde queremos prever o comprimento dos narizes de Kangaroos. Para isto vamos usar uma feature fantástica, a largura do nariz do Kangaroo.<jupyter_code>df = pd.read_csv('https://media.githubusercontent.com/media/icd-ufmg/material/master/aulas/18-GradienteDescendente/gray-kangaroos.csv', names=['comprimento', 'largura'], header=0)
df.head()<jupyter_output><empty_output><jupyter_text>Abaixo temos o modelo.<jupyter_code>sns.regplot(x='largura', y='comprimento', data=df, n_boot=10000,
            line_kws={'color':'magenta', 'lw':4},
            scatter_kws={'edgecolor':'k', 's':80, 'alpha':0.8})
despine()<jupyter_output><empty_output><jupyter_text>z-normalizando<jupyter_code>df -= df.mean()
df /= df.std(ddof=1)
sns.regplot(x='largura', y='comprimento', data=df, n_boot=10000,
            line_kws={'color':'magenta', 'lw':4},
            scatter_kws={'edgecolor':'k', 's':80, 'alpha':0.8})
despine()<jupyter_output><empty_output><jupyter_text>A regressão. Note o intercepto = 0.<jupyter_code>y = df['comprimento']
x = df['largura']
ss.linregress(x, y)<jupyter_output><empty_output><jupyter_text>Abaixo temos um plot com a soma dos erros ao quadrado que é utilizado para chegar na reta. Lembre-se das aulas anteriores. Chegamos no resultado acima usando cálculo, isto é, setamos as derivadas para zero. Uma outra abordagem para minimizar o erro é escolher um ponto de partida aleatório. Deste, calculamos o gradiente (derivadas). Depois, damos um pequeno passo na oposta do gradiente.Inicialmente, observe como o erro é para um ponto. Lembrando que estamos trabalhando com uma função de erros quadrado. Diferente das aulas anteriores, ao invés de somar a mesma vamos tirar a média. Como o número de pontos, $n$, é uma constante, não afeta nossos algoritmos. Ao setar a derivada para zero o n some. De qualquer forma, pode ajudar os nossos algoritmos (evitar overflow).$L(\beta) = n^{-1} \sum_i (y_i - \beta x_i)^2$<jupyter_code>betas = np.linspace(0.1, 16, 100)
errs = np.zeros_like(betas)
for j in range(len(betas)):
    err = ((y[0] - betas[j] * x[0]) ** 2).mean()
    errs[j] = err
plt.plot(betas, errs, label='L(beta)')
plt.xlabel(r'$\beta$')
plt.title(r'Erro para um ponto: x = {:.2f}, y = {:.2f}'.format(x[2], y[2]))
plt.ylabel(r'$(y_i - \beta x_i)^2$')
plt.grid()
despine()<jupyter_output><empty_output><jupyter_text>A soma de duas funções convexas é convexa. Então, a soma do erro quadrado nos pontos tamém é convexa. (prova nos slides)<jupyter_code>betas = np.linspace(0.1, 1.7, 100)
errs = np.zeros_like(betas)
grads = np.zeros_like(betas)
for j in range(len(betas)):
    err = ((y - betas[j] * x) ** 2).mean()
    grads[j] = (-2 * (y - betas[j] * x) * x).mean()
    errs[j] = err
plt.plot(betas, errs, label='L(beta)')
#plt.plot(betas, grads, label='L\'(beta)')
plt.xlabel(r'$\beta$')
plt.title(r'Erro na soma para todos os pontos')
plt.ylabel(r'$\sum_i(y_i - \beta x_i)^2$')
plt.legend()
plt.grid()
despine()<jupyter_output><empty_output><jupyter_text>Observe que essa função possui um ponto de mínimo nas quando $\beta \approx 0.9$.  Observe que o gradiente, ou a derivada, é negativa quando estamos do lado esquero do mínimo. É positiva do lado direto e zero no valor ótimo. Então, a partir de um local inicial o sinal da derivada, na verdade o oposto do sinal como estamos minimizando, indica a direção que devemos ir.<jupyter_code>plt.plot(betas, errs, label='L(beta)')
plt.plot(betas, grads, label='L\'(beta)')
plt.xlabel(r'$\beta$')
plt.title(r'Erro na soma para todos os pontos')
plt.ylabel(r'$\sum_i(y_i - \beta x_i)^2$')
plt.legend()
plt.grid()
despine()<jupyter_output><empty_output><jupyter_text>Caso você tenha problemas com derivadas, use o módulo sympy. Abaixo temos a derivadas para um ponto apenas.<jupyter_code>import sympy as sy

x_i , y_i, beta = sy.symbols('x_i y_i beta')
fun = (y_i - beta * x_i)**2
sy.diff(fun, beta)<jupyter_output><empty_output><jupyter_text>Gradiente DescendenteCom o conhecimento acima temos a base do Gradiente Descendente. Iniciando de um local qualquer, $\beta=2$. Vamos:1. Computar a derivada $\frac{dL(\beta)}{d\beta}$1. Setar $\beta = \beta - \lambda \frac{dL(\beta)}{d\beta}$1. RepetirO valor de $\lambda$ define nossa taxa de aprendizado.<jupyter_code>def ssq_znormed(x, y, beta):
    return ((y - beta * x) ** 2).mean()
def grad_znormed(x, y, beta):
    return (-2 * x * (y - beta * x)).mean()
beta = 2
beta_passo = [beta]
erros = []
for _ in range(500):
    err_sq = ssq_znormed(x, y, beta)
    grad = grad_znormed(x, y, beta)
    beta = beta - 0.01 * grad
    beta_passo.append(beta)
    erros.append(err_sq)
plt.plot(beta_passo)
plt.xlabel('Passo')
plt.ylabel('Valor de Beta')
despine()<jupyter_output><empty_output><jupyter_text>Observe os erros<jupyter_code>plt.plot(erros)
plt.xlabel('Passo')
plt.ylabel('Erro Sq')
despine()<jupyter_output><empty_output><jupyter_text>Gradiente Descendente EstocásticoMuitas vezes usaremos o gradiente descendente para escolher os parâmetros de um modelo de maneira a minimizar alguma noção de erro. Usando a abordagem em lote anterior, cada etapa do método exige que façamos uma previsão e calculemos o gradiente para todo o conjunto de dados, o que faz com que cada etapa demore muito.Geralmente, essas funções de erro são *aditivas*, o que significa que o erro preditivo em todo o conjunto de dados é simplesmente a soma dos erros preditivos para cada ponto de dados.Quando este é o caso, podemos, em vez disso, aplicar uma técnica chamada gradiente descendente estocástico (ou *stochastic gradient descent*), que calcula o gradiente (e dá um passo) para apenas um ponto por vez. Ele passa sobre os dados repetidamente até atingir um ponto de parada.Durante cada ciclo, queremos iterar nossos dados em uma ordem aleatória:<jupyter_code>beta = 2
beta_passo = [beta]
erros = []
for _ in range(1000):
    i = np.random.randint(0, len(x))
    x_i, y_i = x[i], y[i]
    err_sq = ssq_znormed(x, y, beta) # esta linha ainda precisa ser em todos os pontos
    grad = grad_znormed(x_i, y_i, beta)
    beta = beta - 0.01 * grad
    beta_passo.append(beta)
    erros.append(err_sq)
plt.plot(beta_passo)
plt.xlabel('Passo')
plt.ylabel('Valor de Beta')
despine()
plt.plot(erros)
plt.xlabel('Passo')
plt.ylabel('Erro Sq')
despine()<jupyter_output><empty_output><jupyter_text>Escolhendo o tamanho certo do passoEmbora o raciocínio para se mover na direção oposta ao gradiente seja claro, até que ponto mover-se não é. De fato, escolher o tamanho certo do passo que devemos nos mover é mais uma arte do que uma ciência. Opções populares incluem:* Usar um tamanho de passo fixo;* Diminuir gradualmente o tamanho do passo ao longo do tempo;* Em cada etapa, escolha o tamanho do passo que minimiza o valor da função objetivo.O último parece ótimo, mas é, na prática, um cálculo caro. Podemos aproximá-lo tentando uma variedade de tamanhos de passo e escolhendo aquele que resulta no menor valor da função objetivo:  Caso MultivariadoAté agora estamos roubando um pouco ao normalizar os dados. Isto é, estamos forçando $\alpha=0$ na equação abaixo:$$y_i = \beta x_i + \alpha$$Vamos voltar para os dados originais. Note que o resultado da regressão é outro. Em particular, o intercepto é 22. Queremos estimar o mesmo também.<jupyter_code>x = np.random.normal(size=1000)
y = 2 * x + np.random.normal(loc=3, size=1000)
ss.linregress(x, y)
plt.scatter(x, y, alpha=0.8, s=80, edgecolors='k')
despine()<jupyter_output><empty_output><jupyter_text>Abaixo tenho as derivadas:$$\frac{dL}{d\alpha} = n^{-1}\sum_i 2 (-y_i + \beta x_i + \alpha)$$$$\frac{d L}{d\beta} =n^{-1} \sum_i 2 (-y_i + \beta x_i + \alpha) x_i$$<jupyter_code>def derivadas_regressao(parametros, x, y):
    alpha, beta = parametros
    da = (-2 * y) + (2 * beta * x) + (2 * alpha)
    db = (-2 * y * x) + (2 * beta * (x ** 2)) + (2 * alpha * x)
    return np.array([da.mean(), db.mean()])<jupyter_output><empty_output><jupyter_text>Um gradient descent simples. O mesmo vai parar de executar quando os parâmetros convergem. Aqui temos uma função mais organizada. A mesma recebe uma outra função de derivada.<jupyter_code>def gd(parametros, d_fun, x, y, lambda_=0.01):
    parametros = parametros.copy()
    for i in range(1000):
        grad = d_fun(parametros, x, y)
        parametros_novos = parametros - lambda_ * grad
        if np.abs(parametros - parametros_novos).mean() <= 0.00001:
            break
        parametros = parametros_novos
        print('Iter {}; alpha, beta = '.format(i), parametros)
    return parametros<jupyter_output><empty_output><jupyter_text>Resposta!<jupyter_code>parametros_iniciais = np.array([1, 1])
gd(parametros_iniciais, derivadas_regressao, x, y)<jupyter_output>Iter 0; alpha, beta =  [1.03959014 1.02053009]
Iter 1; alpha, beta =  [1.07840492 1.04064866]
Iter 2; alpha, beta =  [1.11645951 1.06036398]
Iter 3; alpha, beta =  [1.15376879 1.07968415]
Iter 4; alpha, beta =  [1.19034736 1.09861709]
Iter 5; alpha, beta =  [1.22620951 1.11717059]
Iter 6; alpha, beta =  [1.26136928 1.13535226]
Iter 7; alpha, beta =  [1.2958404  1.15316957]
Iter 8; alpha, beta =  [1.32963637 1.17062984]
Iter 9; alpha, beta =  [1.3627704  1.18774022]
Iter 10; alpha, beta =  [1.39525545 1.20450774]
Iter 11; alpha, beta =  [1.42710423 1.22093929]
Iter 12; alpha, beta =  [1.45832918 1.2370416 ]
Iter 13; alpha, beta =  [1.48894253 1.2528213 ]
Iter 14; alpha, beta =  [1.51895625 1.26828484]
Iter 15; alpha, beta =  [1.54838207 1.28343859]
Iter 16; alpha, beta =  [1.57723151 1.29828874]
Iter 17; alpha, beta =  [1.60551584 1.31284141]
Iter 18; alpha, beta =  [1.63324615 1.32710255]
Iter 19; alpha, beta =  [1.66043327 1.34107801]
Iter 20; alpha, beta =  [1.68708783 1.35477354]
It[...]<jupyter_text>Observe como alpha é o intercept e beta o slope da regressão com scipy<jupyter_code>ss.linregress(x, y)<jupyter_output><empty_output><jupyter_text>Gradiente AscendenteVamos agora chegar no mesmo resultado usando Gradiente Ascendente. Em particular, ainda vamos nos manter em uma regressão linear. Porém, queremos maximizar a log-verossimilhança. Da aula anterior, nosso modelo é:$$y_i = \beta x_i + \alpha + \epsilon_i $$$$\epsilon_i = y_i - \beta x_i - \alpha $$$$\epsilon_i \sim Normal(0, \sigma) $$Partindo do mesmo chegamos em:$$p(\epsilon_i\mid \sigma^2, \alpha, \beta) = \frac{1}{\sqrt {\sigma ^22\pi } }e^{- ({y_i - \beta x_i - \alpha })^2 / 2\sigma^2} $$Assumindo que cada erro é independente, a verossimilhança de todos os erros é:$$p_{\Theta}(E) = \prod_{i} p_{\Theta}(\epsilon_i) \\\log(p_{\Theta}(E)) = \mathcal{l}_{\Theta}(E) =  \sum_{i} \log(p_{\Theta}(\epsilon_i))$$O log da mesma é:$$\mathcal{l}_{\Theta}(E) =  -n \log(\sqrt{2\pi}) - n{\log(\sigma) } - { \sum^n_{i=1} ({y_i - \beta x_i - \alpha })^2 \over 2\sigma^2} $$A derivada em $\sigma$ é:$${d \mathcal{l}_{\Theta} \over d\sigma} =  -{n\over \sigma} + { 2 \sum^n_{i=1} ({y_i - \beta x_i - \alpha })^2 \over 2\sigma^3}$$A derivada em $\alpha$ e $\beta$ é a mesma de antes, apenas invertemos o sinal:$$\frac{d\mathcal{l}_{\Theta}}{d\alpha} = -n^{-1} \sum_i 2 (-y_i + \beta x_i + \alpha)$$$$\frac{d\mathcal{l}_{\Theta}}{d\beta} = -n^{-1} \sum_i 2 (-y_i + \beta x_i + \alpha) x_i$$Em outras palavras, vamos chegar no mesmo resultado.<jupyter_code>def derivadas_vero(parametros, x, y):
    alpha, beta = parametros
    da = -1 * ((-2 * y) + (2 * beta * x) + (2 * alpha))
    db = -1 * ((-2 * y * x) + (2 * beta * (x ** 2)) + (2 * alpha * x))
    return np.array([da.mean(), db.mean()])
def ga(parametros, d_fun, x, y, lambda_=0.01):
    parametros = parametros.copy()
    print('Iter {}; alpha, beta = '.format(-1), parametros)
    for i in range(1000):
        grad = d_fun(parametros, x, y)
        parametros_novos = parametros + lambda_ * grad
        if np.abs(parametros - parametros_novos).mean() <= 0.00001:
            break
        parametros = parametros_novos
        print('Iter {}; alpha, beta = '.format(i), parametros)
    return parametros
parametros_iniciais = np.array([0.1, 0.1])
parametros = ga(parametros_iniciais, derivadas_vero, x, y)
ss.linregress(x, y)<jupyter_output><empty_output><jupyter_text>MLEAbaixo tenho os plots para MLE. O material está nos slides.<jupyter_code>x = np.array([1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0])
x
thetas = np.linspace(0.01, 0.99, 1000)
l = []
for theta in thetas:
    model = (theta ** x) * ((1 - theta) ** (1-x))
    l.append(model.prod())
plt.plot(thetas, l)
plt.xlabel(r'$\theta$')
plt.ylabel('Verossimilhança')
despine()
ll = []
for theta in thetas:
    model = np.log((theta ** x) * ((1 - theta) ** (1-x)))
    ll.append(model.sum())
plt.plot(thetas, ll)
plt.xlabel(r'$\theta$')
plt.ylabel('Log-Verossimilhança')
despine()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.1362237212653088, 'fraction_numerical': 0.04145654594275984, 'mean_word_length': 4.463327370304114, 'pattern_counts': {'":': 0, '<': 79, '<?xml version=': 0, '>': 77, 'https://': 2, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '19', 'dir': 'jupyter-structured-clean-dedup', 'id': '462351', 'license': 'MIT', 'n_tokens_mistral': 6378, 'n_tokens_neox': 5887, 'n_words': 1693, 'path': '_lessons/.ipynb_checkpoints/17-gradiente-checkpoint.ipynb', 'repo_name': 'icd-ufmg/icd-ufmg.github.io', 'size': '15273'}