Cálculo em Gráficos Computacionais: Backpropagation

– http://colah.github.io/posts/2015-08-Backprop/
Postado em 31 de agosto de 2015

Introdução
Backpropagation é o algoritmo chave que torna o treinamento de modelos profundos computacionalmente atraentes. Para as redes neurais modernas, pode fazer treinamento com descida gradiente até dez milhões de vezes mais rápido, em relação a uma implementação ingênua. Essa é a diferença entre um modelo que leva uma semana para treinar e levar 200 mil anos.
Para além do seu uso na aprendizagem profunda, o backpropagation é uma poderosa ferramenta computacional em muitas outras áreas, que vão desde a previsão do tempo até a análise da estabilidade numérica – apenas por nomes diferentes. De fato, o algoritmo foi reinventado pelo menos dezenas de vezes em diferentes campos (ver Griewank (2010)). O nome geral, independente do aplicativo, é “diferenciação de modo reverso”.
Fundamentalmente, é uma técnica para calcular rapidamente os derivados. E é um truque essencial para ter no seu saco, não só em aprendizagem profunda, mas numa grande variedade de situações de computação numérica.

Gráficos computacionais
Os gráficos computacionais são uma ótima maneira de pensar sobre expressões matemáticas. Por exemplo, considere a expressão e = (a + b) * (b + 1). Existem três operações: duas adições e uma multiplicação. Para nos ajudar a falar sobre isso, vamos apresentar duas variáveis intermediárias, c e d para que a saída de cada função tenha uma variável. Agora temos:
c = a + b
d = b + 1
e = c * d
Para criar um gráfico computacional, fazemos cada uma dessas operações, juntamente com as variáveis de entrada, em nós. Quando o valor de um nó é a entrada para outro nó, uma seta vai de um para outro.

Esses tipos de gráficos surgem o tempo todo em ciência da computação, especialmente em falar sobre programas funcionais. Eles estão muito relacionados às noções de gráficos de dependência e gráficos de chamadas. Eles também são a principal abstração por trás do quadro popular de aprendizagem profunda Theano.
Podemos avaliar a expressão configurando as variáveis de entrada para certos valores e nós de computação através do gráfico. Por exemplo, vamos definir a=2 e b=1:

A expressão avalia a 66.

Derivados em Gráficos Computacionais
Se alguém quiser entender derivativos em um gráfico computacional, a chave é entender derivadas nas bordas. Se “a” afetar diretamente “c”, então queremos saber como ele afeta “c”. Se “a” muda um pouco, como muda “c”? Chamamos isso de derivada parcial de “c” em relação a “a”.
Para avaliar as derivadas parciais neste gráfico, precisamos da regra de soma e da regra do produto:
Abaixo, o gráfico tem a derivada em cada borda rotulada.

E se queremos entender como os nós que não estão diretamente conectados se afetam? Consideremos como e é afetado por a. Se mudarmos “a” a uma velocidade de 1, “c” também muda a uma velocidade de 11. Por sua vez, “c” mudando a uma velocidade de 11 faz com que “e” mude a uma velocidade de 22. Então “e” muda a uma taxa de 1*21* 2 em relação a “a”.
A regra geral é somar todos os caminhos possíveis de um nó para o outro, multiplicando as derivadas em cada extremidade do caminho juntos. Por exemplo, para obter a derivada de “e” em relação ao “b”, obtemos:
∂e / ∂b = 1*2+1*3
Isso explica como b afeta e através de c e também como ele afeta isso através de d.
Esta regra geral “soma sobre caminhos” é apenas uma maneira diferente de pensar sobre a regra da cadeia multivariada.

Caminhos de factoring
O problema com apenas “somar os caminhos” é que é muito fácil obter uma explosão combinatória no número de caminhos possíveis.

No diagrama acima, existem três caminhos de X para Y, e outros três caminhos de Y para Z. Se quisermos obter a derivada ∂Z/X∂ ao somar todos os caminhos, precisamos somar mais de 3*3 = 9 caminhos:
∂Z/∂X = αδ + αε + αζ + βδ + βε + βζ + γδ + γε + γζ

O acima tem apenas nove caminhos, mas seria fácil ter o número de caminhos para crescer exponencialmente à medida que o gráfico se torna mais complicado.
Em vez de simplesmente somar ingenuamente sobre os caminhos, seria muito melhor fator-los:
∂Z/∂X = (α + β + γ) (δ + ε + ζ)
É aqui que entram a “diferenciação do modo para frente” e a “diferenciação do modo reverso”. São algoritmos para computar a soma de forma eficiente fazendo face aos caminhos. Em vez de somar todos os caminhos explicitamente, eles calculam a mesma soma de forma mais eficiente juntando caminhos de volta em cada nó. Na verdade, ambos os algoritmos tocam cada extremidade exatamente uma vez!
A diferenciação do modo avançado começa em uma entrada para o gráfico e se move para o final. Em cada nó, isso resume todos os caminhos que se entrem. Cada um desses caminhos representa uma maneira pela qual a entrada afeta esse nó. Ao adicioná-los, obtemos a maneira total pela qual o nó é afetado pela entrada, é derivado.

Embora você provavelmente não pensou nisso em termos de gráficos, a diferenciação de modo direto é muito semelhante ao que você implicitamente aprendeu a fazer se você fez uma introdução à classe de cálculo.
A diferenciação do modo inverso, por outro lado, começa numa saída do gráfico e move-se para o início. Em cada nó, ele combina todos os caminhos que se originaram nesse nó.

A diferenciação de modo direto rastreia como uma entrada afeta cada nó. A diferenciação do modo inverso rastreia como cada nó afeta uma saída. Ou seja, a diferenciação de modo direto aplica o operador ∂/∂X a cada nó, enquanto a diferenciação do modo reverso aplica o operador ∂Z/∂ a cada nó.1

Vitórias computacionais
Neste ponto, você pode se perguntar por que alguém se importaria com a diferenciação do modo reverso. Parece uma maneira estranha de fazer o mesmo que o modo avançado. Existe alguma vantagem?
Consideremos nosso exemplo original novamente:

Podemos usar a diferenciação de modo direto de b. Isso nos dá a derivação de cada nó em relação a b.

Nós computamos ∂e/∂b, a derivada da nossa produção em relação a uma de nossas entradas.
E se fizermos a diferenciação de e do modo de reverter para baixo? Isso nos dá a derivada de e em relação a cada nó:

Quando digo que a diferenciação do modo reverso nos dá a derivada de e em relação a cada nó, eu realmente quero dizer todos os nós. Obtemos ∂e/∂a e ∂e/∂b, as derivadas de e em relação a ambas as entradas. A diferenciação do modo direto nos deu a derivada da nossa saída em relação a uma única entrada, mas a diferenciação do modo reverso nos dá todos eles.
Para este gráfico, isso é apenas um fator de duas velocidades, mas imagine uma função com um milhão de entradas e uma saída. A diferenciação em modo para a frente exigiria que passemos pelo gráfico um milhão de vezes para obter os derivativos. A diferenciação de modo inverso pode levá-los de uma só vez! Uma aceleração de um fator de um milhão é bastante agradável!
Ao treinar redes neurais, pensamos no custo (um valor que descreve o quão ruim é uma rede neural) como uma função dos parâmetros (números que descrevem como a rede se comporta). Queremos calcular os derivados do custo em relação a todos os parâmetros, para uso em descida gradiente. Agora, muitas vezes, milhões, ou mesmo dezenas de milhões de parâmetros em uma rede neural. Assim, a diferenciação do modo reverso, chamada de “backpropagation” no contexto das redes neurais, nos dá uma grande aceleração!
(Existe algum caso em que a diferenciação de modo direto faz mais sentido? Sim, existe! Onde o modo reverso dá as derivadas de uma saída em relação a todas as entradas, o modo de frente nos dá as derivadas de todas as saídas em relação a Uma entrada. Se alguém tiver uma função com muitas saídas, a diferenciação do modo direto pode ser muito, muito, muito mais rápida.)
Não é isto Trivial?
Quando eu entendi pela primeira vez o que era a pirataria, minha reação era: “Oh, essa é apenas a regra da cadeia! Como demoramos tanto em descobrir?” Eu não sou o único que teve essa reação. É verdade que, se você perguntar “existe uma maneira inteligente de calcular derivativos em redes neurais feedforward?”, a resposta não é tão difícil.
Mas acho que foi muito mais difícil do que parece. Você vê, no momento em que a pirataria foi inventada, as pessoas não estavam muito concentradas nas redes neurais feedforward que estudamos. Também não era óbvio que os derivados eram o caminho certo para treiná-los. Isso é óbvio quando você percebe que você pode calcular rapidamente os derivados. Havia uma dependência circular.
Pior ainda, seria muito fácil escrever qualquer parte da dependência circular como impossível no pensamento casual. Treinando redes neurais com derivativos? Certamente você ficaria preso em mínimos locais. E, obviamente, seria caro calcular todos esses derivados. É só porque sabemos que esta abordagem funciona que não começamos imediatamente a listar os motivos que não é provável.
Esse é o benefício da retrospectiva. Depois de abordar a questão, o trabalho mais difícil já foi feito.

Conclusão
Os derivados são mais baratos do que você pensa. Essa é a principal lição a tirar desta publicação. Na verdade, eles são inintuosamente baratos, e nós humanos tolos tivemos que redescobrir repetidamente esse fato. Isso é uma coisa importante para entender na aprendizagem profunda. Também é uma coisa realmente útil para saber em outros campos, e apenas mais, se não é um conhecimento comum.
Existem outras lições? Eu acho que existem.
Backpropagation também é uma lente útil para entender como os derivativos fluem através de um modelo. Isso pode ser extremamente útil ao raciocinar sobre por que alguns modelos são difíceis de otimizar. O exemplo clássico disso é o problema dos gradientes de desaparecimento em redes neurais recorrentes.
Finalmente, eu afirmo que há uma ampla lição algorítmica para remover essas técnicas. Backpropagation e diferenciação de modo direto usam um poderoso par de truques (linearização e programação dinâmica) para calcular derivados de forma mais eficiente do que se poderia pensar. Se você realmente entender essas técnicas, você pode usá-las para calcular com eficiência várias outras expressões interessantes que envolvem derivativos. Nós exploraremos isso em uma postagem de blog posterior.
Esta publicação oferece um tratamento muito abstrato de backpropagation. Eu recomendo encarecidamente ler o capítulo de Michael Nielsen sobre isso para uma excelente discussão, mais concretamente focada em redes neurais.

Reconhecimentos
Obrigado a Greg Corrado, Jon Shlens, Samy Bengio e Anelia Angelova por se terem dedicado a revisar esta publicação.
Obrigado também a Dario Amodei, Michael Nielsen e Yoshua Bengio pela discussão de abordagens para explicar a “backpropagation”. Também graças a todos aqueles que me toleraram praticando a explicação de backpropagation em séries de palestras e seminários!

* Isso pode parecer um pouco como programação dinâmica. Isso é porque é! ↩

Sobre o autor

Sara Filipa

Comentar

Posts recentes

Comentários

Arquivos

Categorias

Meta