import numpy as np
import matplotlib.pyplot as plt

%matplotlib inline

"""
Explanation: Objetivos: 

entender os conceitos de derivada e gradiente
entender a diferença entre gradiente analítico e numérico
aprender a calcular a backpropagação de qualquer rede neural.

Sumário
0. Imports and Configurações
1. Introdução
- O Objetivo
- Estratégia 1: Busca Aleatória
- Estratégia 2: Busca Aleatória Local
- Estratégia 3: Gradiente Numérico
- Estratégia 4: Gradiente Analítico
- Caso Recursivo: Múltiplas Portas
- Checagem do gradiente numérico
- Neurônio Sigmóide
2. Backpropagation
- Se tornando um Ninja em Backpropagation!
- Resumo dos Padrões na Backpropagation
- Exemplo 1
- Exemplo 2
0. Imports and Configurações
End of explanation
"""


x, y = -2, 3
melhor_saida = forwardMultiplyGate(x,y)
melhor_x, melhor_y = 0, 0

for k in range(0,100):
    x_try = 5*np.random.random() - 5
    y_try = 5*np.random.random() - 5
    out = forwardMultiplyGate(x_try, y_try)
    
    if out > melhor_saida:
        melhor_saida = out
        melhor_x, melhor_y = x_try, y_try

print(melhor_x, melhor_y, forwardMultiplyGate(melhor_x, melhor_y))

"""
Explanation: 1. Introdução
A melhor maneira de pensar em redes neurais é como circuitos de valores reais. Mas, ao invés de valores booleanos, valores reais e, ao invés de portas lógicas como and ou or, portas binárias (dois operandos) como $$ (multiplicação), + (adição), max, exp, etc. Além disso, também teremos gradientes* fluindo pelo circuito, mas na direção oposta.
<img src='images/porta_multiplicacao.png' width="250">
De forma matemática, a gente pode considerar que essa porta implementa a seguinte função:
$$f(x,y)=x*y$$
O Objetivo
Vamos imaginar que temos o seguinte problema:
1. Nós vamos providenciar a um circuito valores específicos como entrada (x=-2, y=3)
2. O circuito vai calcular o valor de saída (-6)
3. A questão é: Quanto mudar a entrada para levemente aumentar a saída?
No nosso caso, em que direção devemos mudar x,y para conseguir um número maior que -6? Note que, pro nosso exemplo, se x = -1.99 e y = 2.99, x$$y = -5.95 que é maior que -6. -5.95 é melhor (maior) que 6*, e obtivemos uma melhora de 0.05.
Estratégia 1: Busca Aleatória
Ok. Isso não é trivial? A gente pode simplesmente gerar valores aleatórios, calcular a saída e guardar o melhor resultado.
End of explanation
"""


x, y = -2, 3
passo = 0.01
melhor_saida = forwardMultiplyGate(x,y)
melhor_x, melhor_y = 0, 0

for k in range(0,100):
    x_try = x + passo * (2*np.random.random() - 1)
    y_try = y + passo * (2*np.random.random() - 1)  
    out = forwardMultiplyGate(x_try, y_try)
    
    if out > melhor_saida:
        melhor_saida = out
        melhor_x, melhor_y = x_try, y_try

print(melhor_x, melhor_y, forwardMultiplyGate(melhor_x, melhor_y))

"""
Explanation: Ok, foi bem melhor. Mas, e se tivermos milhões de entradas? É claro que essa estratégia não funcionará. Vamos tentar algo mais aprimorado.
Estratégia 2: Busca Aleatória Local
End of explanation
"""


x, y = -2, 3
out = forwardMultiplyGate(x,y)
h = 0.0001

# derivada em relação a x


# derivada em relação a y


"""
Explanation: Estratégia 3: Gradiente Numérico
Imagine agora que a gente pega as entradas de um circuito e puxa-as para uma direção positiva. Essa força puxando $x$ e $y$ vai nos dizer como $x$ e $y$ devem mudar para aumentar a saída. Não entendeu? Vamos explicar:
Se olharmos para as entradas, a gente pode intuitivamente ver que a força em $x$ deveria sempre ser positiva, porque tornando $x$ um pouquinho maior de $x=-2$ para $x=-1$ aumenta a saída do circuito para $-3$, o que é bem maior que $-6$. Por outro lado, se a força em $y$ for negativa, tornando-o menor, como de $y=3$ para $y=2$, também aumenta a saída: $-2\times2 = -4$, de novo maior que $-6$.
E como calcular essa força? Usando derivadas.

A derivada pode ser pensada como a força que a gente aplica em cada entrada para aumentar a saída

<img src='images/derivada.gif'>
E como exatamente a gente vai fazer isso? Em vez de olhar para o valor de saída, como fizemos anteriormente, nós vamos iterar sobre as cada entrada individualmente, aumentando-as bem devagar e vendo o que acontece com a saída. A quantidade que a saída muda é a resposta da derivada.
Vamos para definição matemática. A derivada em relação a $x$ pode ser definida como:
$$\frac{\partial f(x,y)}{\partial x} = \frac{f(x+h,y) - f(x,y)}{h}$$
Onde $h$ é pequeno. Nós vamos, então, calcular a saída inicial $f(x,y)$ e aumentar $x$ por um valor pequeno $h$ e calcular a nova saída $f(x+h,y)$. Então, nós subtraimos esse valores para ver a diferença e dividimos por $f(x+h,y)$ para normalizar essa mudança pelo valor (arbitrário) que nós usamos.
Em termos de código, teremos:
End of explanation
"""


x, y = -2, 3
out = forwardMultiplyGate(x,y)

# insira seu código aqui!

"""
Explanation: Como a gente pode ver, a derivada em relação a $x$ é igual a $+3$. O sinal positivo indica que alterando o valor de $x$ pelo passo $h$, a saída se torna maior. O valor $3$ pode ser considerado como o valor da força que puxa $x$. O inverso acontece com $y$.

A derivada em relação a alguma entrada pode ser calculada ajustando levemente aquela entrada e observando a mudança no valor da saída

A derivada é calculada sobre cada entrada, enquanto o gradiente representa todas as derivadas sobre as entradas concatenadas em um vetor.
Como a gente pode perceber $-5.87 > -6$. Apenas 3 avaliações foram necessárias para aumentar o valor da saída (ao invés de centenas) e conseguimos um melhor resultado.
Passo maior nem sempre é melhor: É importante destacar que qualquer valor de passo maior que 0.01 ia sempre funcionar melhor (por exemplo, passo = 1 gera a saída = 1). No entanto, à medida que os circuitos vão ficando mais complexos (como em redes neurais completas), a função vai ser tornando mais caótica e complexa. O gradiente garante que se você tem um passo muito pequeno (o ideal seria infinitesimal), então você definitivamente aumenta a saída seguindo aquela direção. O passo que estamos utilizando (0.01) ainda é muito grande, mas como nosso circuito é simples, podemos esperar pelo melhor resultado. Lembre-se da analogia do escalador cego.
Estratégia 4: Gradiente Analítico
A estratégia que utilizamos até agora de ajustar levemente a entrada e ver o que acontece com a saída pode não ser muito cômoda na prática quando temos milhares de entradas para ajustar. Então, a gente precisa de algo melhor.
Felizmente, existe uma estratégia mais fácil e muito mais rápida para calcular o gradiente: podemos usar cálculo para derivar diretamente a nossa função. Chamamos isso de gradiente analítico e dessa forma não precisamos ajustar levemente nada. 

O gradiente analítico evita o leve ajustamento das entradas. O circuito pode ser derivado usando cálculo.

É muito fácil calcular derivadas parciais para funções simples como $x*y$. Se você não lembra da definição, aqui está o cálculo da derivada parcial em relação a $x$ da nossa função $f(x,y)$:
$$\frac{\partial f(x,y)}{\partial x} = \frac{f(x+h,y) - f(x,y)}{h}
= \frac{(x+h)y - xy}{h}
= \frac{xy + hy - xy}{h}
= \frac{hy}{h}
= y$$
A derivada parcial em relação em $x$ da nossa $f(x,y)$ é igual $y$. Você reparou na coincidência de $\partial x = 3.0$, que é exatamente o valor de $y$? E que o mesmo aconteceu para $x$? Então, a gente não precisa ajustar nada! E nosso código fica assim:
End of explanation
"""




# Derivada da porta de multiplicação
 

# Derivada da porta de adição


# Regra da cadeia



"""
Explanation: É importante destacar que a Estratégia #3 reduziu a #2 para uma única vez. Porém, a #3 nos dá somente uma aproximação do gradiente, enquanto a Estratégia #4 nos dá o valor exato. Sem aproximações. O único lado negativo é que temos de saber derivar a nossa funcão.
Recapitulando o que vimos até aqui:
- Estratégia 1: definimos valores aleatórios em todas as iterações. Não funciona para muitas entradas.
- Estratégia 2: pequenos ajustes aleatórios nas entradas e vemos qual funciona melhor. Tão ruim quando a #1.
- Estratégia 3: muito melhor através do cálculo do gradiente. Independentemente de quão complicado é o circuito, o gradiente numérico é muito simples de se calcular (mas um pouco caro).
- Estratégia 4: no final, vimos que a forma melhor, mais inteligente e mais rápida é calcular o gradiente analítico. O resultado é idêntico ao gradiente numérico, porém mais rápido e não precisa de ajustes.
Caso Recursivo: Múltiplas Portas
Calcular o gradiente para o nosso circuito foi trivial. Mas, e em circuitos mais complexos? Como a gente vai ver agora, cada porta pode ser tratada individualmente e a gente pode calcular derivadas locais como a gente fez anteriormente. Vamos considerar nossa função agora como a seguinte:
$$f(x,y,z) = (x+y)*z$$
<img src='images/circuito_2.png' width='300'>
Como vamos calcular agora a nossa derivada? Primeiramente, vamos esquecer da porta de soma e fingir que temos apenas duas entradas no nosso circuito: q e z. Como já vimos, as nossas derivadas parciais podem ser definidas da seguinte maneira:
$$f(q,z) = q z \hspace{0.5in} \implies \hspace{0.5in} \frac{\partial f(q,z)}{\partial q} = z, \hspace{1in} \frac{\partial f(q,z)}{\partial z} = q$$
Ok, mas e em relação a $x$ e $y$? Como $q$ é calculado em função de $x$ e $y$ (pela adição em nosso exemplo), nós também podemos calcular suas derivadas parciais:
$$q(x,y) = x + y \hspace{0.5in} \implies \hspace{0.5in} \frac{\partial q(x,y)}{\partial x} = 1, \hspace{1in} \frac{\partial q(x,y)}{\partial y} = 1$$
Correto! As derivadas parciais são 1, independentemente dos valores de $x$ e $y$. Isso faz sentido se pensarmos que para aumentar A saída de uma porta de adição, a gente espera uma força positiva tanto em $x$ quanto em $y$, independente dos seus valores.
Com as fórmulas acima, nós sabemos calcular o gradiente da saída em relação a $q$ e $z$, e o gradiente de $q$ em relação a $x$ e $y$. Para calcular o gradiente do nosso circuito em relação a $x$, $y$ e $z$, nós vamos utilizar a Regra da Cadeia, que vai nos dizer como combinar esses gradientes. A derivada final em relação a $x$, será dada por:
$$\frac{\partial f(q,z)}{\partial x} = \frac{\partial q(x,y)}{\partial x} \frac{\partial f(q,z)}{\partial q}$$
Pode parecer complicado à primeira vista, mas a verdade é que isso vai ser simplificado a somente duas multiplicações:
End of explanation
"""


x,y,z = -2,5,-4
h = 0.0001

#insira seu código aqui

"""
Explanation: <img src="images/circuito_2_back.png">
É isso! Vamos agora fazer nossas entradas responderem ao gradiente. Lembrando que queremos um valor maior que -12.
Vamos agora analisar os resultados separadamente. Analisando primeiramente $q$ e $z$, vemos que o circuito quer que $z$ aumente (der_f_rel_z = +3) e o valor de $q$ diminua (der_f_rel_q = -4) com uma força maior (4 contra 3).
Em relação a porta de soma, como vimos, o padrão é que aumentando as entradas a saída também aumenta. Porém, o circuito quer que $q$ diminua (der_f_rel_q = -4). Esse é o ponto crucial: em vez de aplicarmos uma força de +1 as entradas da porta de soma como normalmente faríamos (derivada local), o circuito quer que os gradientes em $x$ e $y$ se tornem 1x-4=-4. Isso faz sentido: o circuito quer $x$ e $y$ pequeno para que $q$ seja pequeno também, o que vai aumentar $f$.

Se isso fez sentido, você entendeu backpropagation.

Recapitulando:
- Vimos que, para uma simples porta (or simples expressão), podemos derivar o gradiente analítico usando cálculo simples. Nós interpretamos o gradiente como uma força que puxa as entradas na direção necessária para fazer a saída aumentar.
- No caso de múltiplas portas, cada porta é tratada individualmente até que o circuito seja tratado como um todo. A única diferença é que agora o circuito diz como a saída de outras portas devem se comportar (como da porta de adição), que é o gradiente final do circuito em relação a saída da porta. É como o circuito pedindo aquela porta maior ou menor valor de saída, e com alguma força. A porta simplesmente pega essa força e multiplica em relação a todas as forças calculadas para suas entradas anteriores (regra da cadeia) - repare como a força de q (-4) é multiplicada as forças de x e y. Isso pode ter dois efeitos desejados:
    - Se a porta tem uma força positiva de saída, essa força também é multiplicada nas suas entradas, escalonada pelo valor da força das entradas.
    - Se a porta tem uma força negativa de saída, isso significa que o circuito quer que a saída decresça, então essa força é multiplicada pelas entradas para diminuir o valor de saída.

Tenha em mente que a força da saída do circuito vai puxando as outras forças na direção desejada por todo o circuito até as entradas.

Checagem do gradiente numérico
Vamos verificar se os gradientes analíticos que calculamos por backpropagation estão corretos. Lembre-se que podemos fazer isso através do gradiente numérico e esperamos que o resultado seja [-4, -4, 4] para $x,y,z$.
End of explanation
"""


w0, w1, w2 = 2, -3, -3
x0, x1 = -1, -2

# forward pass


# backward pass


# Nova saida


"""
Explanation: Neurônio Sigmóide
Qualquer função diferenciável pode atuar como uma porta, como também podemos agrupar múltiplas portas para formar uma simples porta, ou decompor um função em múltiplas portas quando for conveniente. Para exemplificar, vamos utilizar a função de ativação sigmoid com entradas x e pesos w:
$$f(w,x) = \frac{1}{1+e^{-(w_0x_0 + w_1x_1 + w_2)}}$$
Como dito, a função acima nada mais é que a função sigmoid $\sigma(x)$. Sabendo, então, que a derivada da função sigmoid é:
$$\sigma(x)=\frac{1}{1+e^{-x}}=(1-\sigma(x))\sigma(x)$$
Vamos calcular a gradiente em relação as entradas:
End of explanation
"""


w0, w1, w2 = 2, -3, -3
x0, x1 = -1, -2

# forward pass


# backward pass



"""
Explanation: Vamos supor agora que não sabemos a derivada da função $\sigma(x)$ muito menos de $f(w,x)$. O que podemos fazer?.
Decompor essa função em circuito com múltiplas portas! Dessa forma:
<img src='images/circuito_3.png' width='800'>
Calculando a saída para cada porta, temos:
<img src='images/circuito_3_forward.png' width='800'>
Onde sabemos as seguintes derivadas:
$$f(x) = \frac{1}{x} \rightarrow \frac{df}{dx} = -1/x^2 
\\
f_c(x) = c + x \rightarrow \frac{df}{dx} = 1 
\\
f(x) = e^x \rightarrow \frac{df}{dx} = e^x
\\
f_a(x) = ax \rightarrow \frac{df}{dx} = a$$
Onde as funções $f_c(x)$ e $f_a(x)$ transladam a entrada por uma constante $c$ e escala por uma contante $a$, respectivamente. Na verdade, são apenas casos especias de adição e multiplicação, mas que foram introduzidos como portas unárias.
Como podemos calcular a derivada em relação as entradas agora? Usando Backpropagation!!
2. Backpropagation
Se tornando um Ninja em Backpropagation!
Antes de resolver o circuito acima, vamos praticar um pouco de backpropagation com alguns exemplos. Vamos esquecer funções por enquanto e trabalhar só com 4 variáveis: $a$, $b$, $c$, e $x$. Vamos também nos referir as seus gradientes como $da$, $db$, $dc$, e $dx$. Além disso, vamos assumir que $dx$ é dado (ou é +1 como nos casos acima). Nosso primeiro exemplo é a porta $*$, que já conhecemos:
$$x  = a * b$$
$$da = b * dx$$
$$db = a * dx$$
Se você reparar bem, vai perceber que a porta $$ atua como um switcher* durante a backpropagation, ou seja, o gradiente de cada entrada é o valor da outra multiplicado pelo gradiente da anterior (regra da cadeia). Por outro lado, vamos analisar a porta +:
$$x  = a + b$$
$$da = 1.0 * dx$$
$$db = 1.0 * dx$$
Nesse caso, 1.0 é o gradiente local e a multiplicação é a nossa regra da cadeia. E se fosse a adição de 3 números?:
$$q = a + b$$
$$x = q + c$$
$$dc = 1.0 * dx$$
$$dq = 1.0 * dx$$
$$da = 1.0 * dq$$
$$db = 1.0 * dq$$
Você percebe o que está acontecendo? Se você olhar nos diagramas dos circuitos que já resolvemos, vai perceber que a porta + simplesmente pega o gradiente atual e roteia igualmente para todas as entradas (porque os gradientes locais são sempre 1.0 para todas as entradas, independente dos seus valores atuais). Então, podemos fazer bem mais rápido:
$$x = a + b + c$$
$$da = 1.0 * dx$$
$$db = 1.0 * dx$$
$$dc = 1.0 * dx$$
Okay. Mas, e se combinarmos portas?
$$x = a*b + c$$
$$da = b * dx$$
$$db = a * dx$$
$$dc = 1.0 * dx$$
Se você não percebeu o que aconteceu, introduza uma variável temporária $q = a * b$ e então calcula $x = q + c$ para se convencer. E quanto a este exemplo:
$$x = a * a$$
$$da = 2 * a * dx$$
Outro exemplo:
$$x = aa + bb + c*c$$
$$da = 2 * a * dx$$
$$db = 2 * b * dx$$
$$dc = 2 * c * dx$$
Ok. Agora mais complexo:
$$x = (a * b + c) * d)^2$$
Quando casos mais complexos como esse acontecem, eu gosto de dividir a expressão em partes gerenciáveis que são quase sempre compostas de simples expressões onde eu posso aplicar a regra da cadeia:
$$x1 = a * b + c$$
$$x2 = x1 * d$$
$$x = x2 * x2$$
$$dx2 = 2 * x2 * dx$$
$$dx1 = d * dx2$$
$$dd = x1 * dx2$$
$$da = b * dx1$$
$$db = a * dx1$$
$$dc = 1 * dx1$$
Não foi tão difícil! Essas são as equações para toda a expressão, e nós fizemos dividindo peça por peça e aplicando backpropagation a todas as variáveis. Note que toda variável durante a fase forward tem uma variável equivalente na backpropagação que contém o gradiente em relação a saída do circuito.. Mais um exemplo útil de função e seu gradiente local:
$$x = 1.0/a$$
$$da = 1.0/(a*a) * dx$$
E como ela pode ser aplicada na prática:
$$x = (a+b)/(c+d)$$
$$x1 = a + b$$
$$x2 = c + d$$
$$x3 = 1.0 / x2$$
$$x  = x1 * x3$$
$$dx1 = x3 * dx$$
$$dx3 = x1 * dx$$
$$dx2 = (1.0/(x2 * x2)) * dx3$$
$$dc = 1 * dx2$$
$$dd = 1 * dx2$$
$$da = 1 * dx1$$
$$db = 1 * dx1$$
E mais uma:
$$x = math.max(a, b)$$
$$da = x == a\ ?\ 1.0 * dx\ :\ 0.0$$
$$db = x == b\ ?\ 1.0 * dx\ :\ 0.0$$
No caso acima é mais difícil de entender. A função max passa o valor para a maior entrada e ignora as outras. Na fase de backpropagation, a porta max simplesmente pega o gradiente atual e roteia para a entrada que teve o maior valor durante a fase de forward. A porta age como um simples switch baseado na entrada com o maior valor durante a forward. As outras entradas terão gradiente zero.
Agora, vamos dar uma olhada na porta ReLU (Rectified Linear Unit), muita usada em redes neurais no lugar da função sigmoid. Ela é simplesmente um threshold com zero:
$$x = max(a, 0)$$
$$da = a > 0\ ?\ 1.0 * dx\ :\ 0.0$$
Em outras palavras, essa porta simplesmente passa o valor adiante se ele é maior que zero, ou interrompe o fluxo e seta o valor para zero. Na backpropagação, a porta vai passar o gradiente atual se ele foi ativado durante a forward. Se a entrada original foi menor que zero, ela vai interromper o fluxo de gradiente.
Finalmente, vamos ver como calcular o gradiente em operações vetorizadas que vamos utilizar muito em redes neurais:
$$W = np.random.randn(5,10)$$
$$X = np.random.randn(3,10)$$
$$Y = X.dot(W^T)$$
Supondo que o gradiente de Y é dado como a seguir:
$$dY = np.random.randn(*Y.shape)$$
$$dW = dY^T.dot(X)$$
$$dX = dY.dot(W)$$
Espero que tenha entendido como calcular expressões inteiras (que são feitas de muitas portas) e como calcular a backpropagação para cada uma delas.
Resumo dos Padrões na Backpropagation
Para resumir os padrões no fluxo da backpropagation considere esse circuito:
<img src='images/backpropagation_padroes.png' width='450'>
A porta de soma simplesmente pega o gradiente na saída e distribui igualmente para entrada, independente dos valores durante a etapa de forward. Isso vem do fato que o gradiente local para a operação de adicionar é simplesmente +1.0, então os gradientes em todas as entradas vão ser exatamente iguais ao gradiente da saída porque ele vai ser multiplicado por 1.0 (e continua o mesmo). No circuito acima, repare como a porta + roteou o gradiente 2.0 para ambas as entradas, igualmente e sem alteração.
A porta max roteia o gradiente. Diferente da porta de soma que distribui o gradiente para todas as entradas, distribui o gradiente (sem alteração) para exatamente uma das entradas (a que tinha o maior valor durante a etapa de forward). Isso acontece por que o gradiente local é 1.0 para o maior valor e 0.0 para os outros valores. No circuito acima, a operação max roteou o gradiente de 2.0 para a variável $z$, que tinha um valor maior que $w$, e o gradiente de $w$ continua zero.
A porta de multiplicação é um pouquinho mais difícil de interpretar. Os gradientes locais são os valores das entradas (cambiados) e multiplicados pelo gradiente da saída durante a regra da cadeia. No exemplo acima, o gradiente em $x$ é -8.00, pois é igual a -4.00x2.00.
Efeitos não inutuitivos e suas consequências. Note que se uma das entradas na porta de multiplicação é muito pequena e a outra é muito grande, então a porta de multiplicação vai fazer algo intuitivo: ela vai atribuir um gradiente muito alto para a menor entrada e um muito pequeno para a maior entrada. Perceba que no caso de classificadores lineares, onde os pesos são multiplicados com as entradas $w^Tx_i$, isso implica que a escala dos dados tem um efeito na magnitude do gradiente para os pesos. Por exemplo, se você multiplicar todos os dados de entrada $x_i$ por 1000 durante pré-processamento, então o gradiente dos pesos vão ser 1000x maior, e você terá de usar baixas taxas de aprendizagem para compensar o fator. Por isso que o pré-processamento é tão importante e o conhecimento intuitivo sobre os gradientes podem ajudar a debugar alguns desses casos.
Exemplo 1
Implementando o nosso neurônio
<img src='images/circuito_3_back.png' width='800'>
End of explanation
"""


x, y = 3, -4

# forward pass


# backward pass



"""
Explanation: Exemplo 2
Vamos ver outro exemplo. Suponha que temos a seguinte função:
$$f(x,y) = \frac{x + \sigma(y)}{\sigma(x) + (x+y)^2}$$
Só para deixar claro, essa função é completamente inútil, mas um bom exemplo de backpropagation na prática. Também é importante destacar que ela é bem difícil de derivar em relação a $x$ e $y$. No entanto, como vimos, saber derivar uma função é completamente desnecessário por que não precisamos saber derivar a função inteira para calcular os gradientes. Só precisamos saber como calcular os gradientes locais. Aqui está a resolução:
End of explanation
"""


