Diferenciação automática - Automatic differentiation

Em matemática e álgebra computacional , a diferenciação automática ( AD ), também chamada de diferenciação algorítmica , diferenciação computacional , auto-diferenciação ou simplesmente autodiff , é um conjunto de técnicas para avaliar a derivada de uma função especificada por um programa de computador. AD explora o fato de que cada programa de computador, não importa o quão complicado seja, executa uma sequência de operações aritméticas elementares (adição, subtração, multiplicação, divisão, etc.) e funções elementares (exp, log, sin, cos, etc.). Aplicando a regra da cadeia repetidamente a essas operações, as derivadas de ordem arbitrária podem ser calculadas automaticamente, com precisão de trabalho e usando no máximo um pequeno fator constante mais operações aritméticas do que o programa original.

A diferenciação automática é diferente da diferenciação simbólica e da diferenciação numérica (o método das diferenças finitas). A diferenciação simbólica pode levar a um código ineficiente e enfrenta a dificuldade de converter um programa de computador em uma única expressão, enquanto a diferenciação numérica pode introduzir erros de arredondamento no processo de discretização e cancelamento. Ambos os métodos clássicos têm problemas com o cálculo de derivadas mais altas, onde a complexidade e os erros aumentam. Finalmente, ambos os métodos clássicos são lentos para calcular derivadas parciais de uma função em relação a muitas entradas, como é necessário para algoritmos de otimização baseados em gradiente . A diferenciação automática resolve todos esses problemas.

A regra da cadeia, acumulação direta e reversa

Fundamental para AD é a decomposição de diferenciais fornecidos pela regra da cadeia . Para a composição simples

a regra da corrente dá

Normalmente, dois modos distintos de AD são apresentados, acumulação direta (ou modo direto ) e acumulação reversa (ou modo reverso ). A acumulação direta especifica que se atravessa a regra da cadeia de dentro para fora (ou seja, primeiro calcule e depois e por último ), enquanto a acumulação reversa faz a travessia de fora para dentro (primeiro calcule e depois e por último ). Mais sucintamente, ${\ displaystyle dw_ {1} / dx}$${\ displaystyle dw_ {2} / dw_ {1}}$${\ displaystyle dy / dw_ {2}}$${\ displaystyle dy / dw_ {2}}$${\ displaystyle dw_ {2} / dw_ {1}}$${\ displaystyle dw_ {1} / dx}$

1. a acumulação direta calcula a relação recursiva: com , e,${\ displaystyle {\ frac {dw_ {i}} {dx}} = {\ frac {dw_ {i}} {dw_ {i-1}}} {\ frac {dw_ {i-1}} {dx}} }$${\ displaystyle w_ {3} = y}$
2. a acumulação reversa calcula a relação recursiva: com .${\ displaystyle {\ frac {dy} {dw_ {i}}} = {\ frac {dy} {dw_ {i + 1}}} {\ frac {dw_ {i + 1}} {dw_ {i}}} }$${\ displaystyle w_ {0} = x}$

Acumulação para frente

Na acumulação direta AD, primeiro fixa-se a variável independente em relação à qual a diferenciação é realizada e calcula-se a derivada de cada subexpressão recursivamente. Em um cálculo de caneta e papel, isso envolve a substituição repetida da derivada das funções internas na regra da cadeia:

Isso pode ser generalizado para várias variáveis ​​como um produto da matriz de Jacobianos .

Comparada à acumulação reversa, a acumulação direta é natural e fácil de implementar, pois o fluxo de informações derivadas coincide com a ordem de avaliação. Cada variável w é aumentada com sua derivada ẇ (armazenada como um valor numérico, não uma expressão simbólica),

conforme indicado pelo ponto. As derivadas são então calculadas em sincronia com as etapas de avaliação e combinadas com outras derivadas por meio da regra da cadeia.

Como exemplo, considere a função:

Para maior clareza, as subexpressões individuais foram rotuladas com as variáveis w _i .

A escolha da variável independente para a qual a diferenciação é realizada afeta os valores de sementes ẇ ₁ e ẇ ₂ . Dado o interesse na derivada desta função em relação a x ₁ , os valores iniciais devem ser definidos para:

Com os valores iniciais definidos, os valores se propagam usando a regra da cadeia, conforme mostrado. A Figura 2 mostra uma representação pictórica desse processo como um gráfico computacional.

Operações para calcular o valor	Operações para calcular a derivada
${\ displaystyle w_ {1} = x_ {1}}$	${\ displaystyle {\ dot {w}} _ {1} = 1}$ (semente)
${\ displaystyle w_ {2} = x_ {2}}$	${\ displaystyle {\ dot {w}} _ {2} = 0}$ (semente)
${\ displaystyle w_ {3} = w_ {1} \ cdot w_ {2}}$	${\ displaystyle {\ dot {w}} _ {3} = w_ {2} \ cdot {\ dot {w}} _ {1} + w_ {1} \ cdot {\ dot {w}} _ {2} }$
${\ displaystyle w_ {4} = \ sin w_ {1}}$	${\ displaystyle {\ dot {w}} _ {4} = \ cos w_ {1} \ cdot {\ dot {w}} _ {1}}$
${\ displaystyle w_ {5} = w_ {3} + w_ {4}}$	${\ displaystyle {\ dot {w}} _ {5} = {\ dot {w}} _ {3} + {\ dot {w}} _ {4}}$

Para calcular o gradiente desta função de exemplo, que requer as derivadas de f em relação a não apenas x _1, mas também x ₂ , uma varredura adicional é realizada no gráfico computacional usando os valores iniciais . ${\ displaystyle {\ dot {w}} _ {1} = 0; {\ dot {w}} _ {2} = 1}$

A complexidade computacional de uma varredura de acumulação direta é proporcional à complexidade do código original.

A acumulação direta é mais eficiente do que a acumulação reversa para as funções f  : R ⁿ → R ^m com m ≫ n visto que apenas n varreduras são necessárias, em comparação com m varreduras para acumulação reversa.

Acumulação reversa

Na acumulação reversa AD, a variável dependente a ser diferenciada é fixa e a derivada é calculada em relação a cada subexpressão recursivamente. Em um cálculo de caneta e papel, a derivada das funções externas é substituída repetidamente na regra da cadeia:

Na acumulação reversa, a quantidade de juros é o adjunto , denotado por uma barra ( w̄ ); é uma derivada de uma variável dependente escolhida em relação a uma subexpressão w :

A acumulação reversa atravessa a regra da cadeia de fora para dentro ou, no caso do gráfico computacional da Figura 3, de cima para baixo. A função de exemplo tem valor escalar e, portanto, há apenas uma semente para o cálculo da derivada e apenas uma varredura do gráfico computacional é necessária para calcular o gradiente (de dois componentes). Esta é apenas metade do trabalho quando comparada à acumulação direta, mas a acumulação reversa requer o armazenamento das variáveis ​​intermediárias w _i , bem como as instruções que as produziram em uma estrutura de dados conhecida como lista de Wengert (ou "fita"), que pode consumir memória significativa se o gráfico computacional for grande. Isso pode ser mitigado até certo ponto, armazenando apenas um subconjunto das variáveis ​​intermediárias e, em seguida, reconstruindo as variáveis ​​de trabalho necessárias, repetindo as avaliações, uma técnica conhecida como rematerialização . O ponto de verificação também é usado para salvar estados intermediários.

As operações para calcular a derivada usando acumulação reversa são mostradas na tabela abaixo (observe a ordem reversa):

O gráfico de fluxo de dados de um cálculo pode ser manipulado para calcular o gradiente de seu cálculo original. Isso é feito adicionando-se um nó adjacente para cada nó primário, conectado por arestas adjacentes que são paralelas às arestas primárias, mas fluem na direção oposta. Os nós no gráfico adjunto representam a multiplicação pelas derivadas das funções calculadas pelos nós no primário. Por exemplo, adição nas causas primárias fanout no adjunto; fanout no primário causa adição no adjunto; uma função unária y = f  ( x ) no primário causa x̄ = ȳ f  ′ ( x ) no adjunto; etc.

A acumulação reversa é mais eficiente do que a acumulação direta para as funções f  : R ⁿ → R ^m com m ≪ n visto que apenas m varreduras são necessárias, em comparação com n varreduras para acumulação direta.

O modo reverso AD foi publicado pela primeira vez em 1976 por Seppo Linnainmaa .

A retropropagação de erros em perceptrons multicamadas, uma técnica usada no aprendizado de máquina , é um caso especial do modo reverso AD.

Além da acumulação direta e reversa

A acumulação direta e reversa são apenas duas formas (extremas) de ultrapassar a regra da cadeia. O problema de calcular um Jacobiano completo de f  : R ⁿ → R ^m com um número mínimo de operações aritméticas é conhecido como o problema de acumulação Jacobiana ótima (OJA), que é NP-completo . Central para esta prova é a ideia de que dependências algébricas podem existir entre as parciais locais que rotulam as arestas do gráfico. Em particular, duas ou mais etiquetas de borda podem ser reconhecidas como iguais. A complexidade do problema ainda está aberta se for assumido que todos os rótulos de aresta são únicos e algebricamente independentes.

Diferenciação automática usando números duais

A diferenciação automática do modo progressivo é realizada aumentando a álgebra de números reais e obtendo uma nova aritmética . Um componente adicional é adicionado a cada número para representar a derivada de uma função no número, e todos os operadores aritméticos são estendidos para a álgebra aumentada. A álgebra aumentada é a álgebra de números duais .

Substitua cada número pelo número , onde é um número real, mas é um número abstrato com a propriedade (um infinitesimal ; consulte Análise infinitesimal suave ). Usando apenas isso, a aritmética regular dá ${\ displaystyle \, x}$${\ displaystyle x + x '\ varepsilon}$${\ displaystyle x '}$${\ displaystyle \ varepsilon}$${\ displaystyle \ varepsilon ^ {2} = 0}$

e da mesma forma para subtração e divisão.

Agora, os polinômios podem ser calculados nesta aritmética aumentada. Se então ${\ displaystyle P (x) = p_ {0} + p_ {1} x + p_ {2} x ^ {2} + \ cdots + p_ {n} x ^ {n}}$

onde denota a derivada de em relação ao seu primeiro argumento, e , chamado de semente , pode ser escolhido arbitrariamente. ${\ displaystyle P ^ {(1)}}$${\ displaystyle P}$${\ displaystyle x '}$

A nova aritmética consiste em pares ordenados , elementos escritos , com aritmética ordinária no primeiro componente e aritmética de diferenciação de primeira ordem no segundo componente, conforme descrito acima. Estender os resultados acima em polinômios para

funções analíticas fornece uma lista da aritmética básica e algumas funções padrão para a nova aritmética: ${\ displaystyle \ langle x, x '\ rangle}$

$${\ displaystyle {\ begin {alinhado} \ left \ langle u, u '\ right \ rangle + \ left \ langle v, v' \ right \ rangle & = \ left \ langle u + v, u '+ v' \ direita \ rangle \\\ esquerda \ langle u, u '\ right \ rangle - \ left \ langle v, v' \ right \ rangle & = \ left \ langle uv, u'-v '\ right \ rangle \\\ esq \ langle u, u '\ right \ rangle * \ left \ langle v, v' \ right \ rangle & = \ left \ langle uv, u'v + uv '\ right \ rangle \\\ left \ langle u, u '\ right \ rangle / \ left \ langle v, v' \ right \ rangle & = \ left \ langle {\ frac {u} {v}}, {\ frac {u'v-uv '} {v ^ {2}}} \ right \ rangle \ quad (v \ neq 0) \\\ sin \ left \ langle u, u '\ right \ rangle & = \ left \ langle \ sin (u), u' \ cos ( u) \ right \ rangle \\\ cos \ left \ langle u, u '\ right \ rangle & = \ left \ langle \ cos (u), - u' \ sin (u) \ right \ rangle \\\ exp \ left \ langle u, u '\ right \ rangle & = \ left \ langle \ exp u, u' \ exp u \ right \ rangle \\\ log \ left \ langle u, u '\ right \ rangle & = \ left \ langle \ log (u), u '/ u \ right \ rangle \ quad (u> 0) \\\ left \ langle u, u' \ right \ rangle ^ {k} & = \ left \ langle u ^ {k}, ku ^ {k-1} u '\ right \ rangle \ quad (u \ neq 0) \\\ left | \ left \ langle u, u' \ right \ rangle \ right | & = \ left \ langle \ left | u \ right |, u '{\ mbox {sinal}} u \ right \ rangle \ quad (u \ neq 0) \ end {alinhado}}}$$

e em geral para a função primitiva , ${\ displaystyle g}$

$${\ displaystyle g (\ langle u, u '\ rangle, \ langle v, v' \ rangle) = \ langle g (u, v), g_ {u} (u, v) u '+ g_ {v} ( u, v) v '\ rangle}$$

onde e são os derivados de em relação ao seu primeiro e segundo argumentos, respectivamente. ${\ displaystyle g_ {u}}$${\ displaystyle g_ {v}}$${\ displaystyle g}$

Quando uma operação aritmética básica binária é aplicada a argumentos mistos - o par e o número real - o número real é primeiro elevado a . A derivada de uma função no ponto agora é encontrada calculando usando a aritmética acima, que fornece o resultado. ${\ displaystyle \ langle u, u '\ rangle}$${\ displaystyle c}$${\ displaystyle \ langle c, 0 \ rangle}$${\ displaystyle f: \ mathbb {R} \ to \ mathbb {R}}$${\ displaystyle x_ {0}}$${\ displaystyle f (\ langle x_ {0}, 1 \ rangle)}$${\ displaystyle \ langle f (x_ {0}), f '(x_ {0}) \ rangle}$

Argumentos e funções de vetor

As funções multivariadas podem ser tratadas com a mesma eficiência e mecanismos que as funções univariadas, adotando-se um operador derivado direcional. Ou seja, se for suficiente calcular a derivada direcional de at na direção , isso pode ser calculado usando a mesma aritmética acima. Se todos os elementos de forem desejados, as avaliações da função serão necessárias. Observe que em muitas aplicações de otimização, a derivada direcional é de fato suficiente. ${\ displaystyle y '= \ nabla f (x) \ cdot x'}$${\ displaystyle y '\ in \ mathbb {R} ^ {m}}$${\ displaystyle f: \ mathbb {R} ^ {n} \ to \ mathbb {R} ^ {m}}$${\ displaystyle x \ in \ mathbb {R} ^ {n}}$${\ displaystyle x '\ in \ mathbb {R} ^ {n}}$${\ displaystyle (\ langle y_ {1}, y '_ {1} \ rangle, \ ldots, \ langle y_ {m}, y' _ {m} \ rangle) = f (\ langle x_ {1}, x '_ {1} \ rangle, \ ldots, \ langle x_ {n}, x' _ {n} \ rangle)}$${\ displaystyle \ nabla f}$${\ displaystyle n}$

Alta ordem e muitas variáveis

A aritmética acima pode ser generalizada para calcular derivadas de segunda ordem e superiores de funções multivariadas. No entanto, as regras aritméticas tornam-se rapidamente complicadas: a complexidade é quadrática no grau de derivação mais alto. Em vez disso, pode ser usada a álgebra polinomial de Taylor truncada . A aritmética resultante, definida em números duais generalizados, permite um cálculo eficiente usando funções como se fossem um tipo de dados. Uma vez que o polinômio de Taylor de uma função é conhecido, as derivadas são facilmente extraídas.

Implementação

O modo avançado AD é implementado por uma interpretação não padronizada do programa em que os números reais são substituídos por números duais, as constantes são elevadas para números duais com um coeficiente épsilon zero e os primitivos numéricos são elevados para operar em números duais. Essa interpretação não padronizada é geralmente implementada usando uma de duas estratégias: transformação do código-fonte ou sobrecarga do operador .

Transformação do código fonte (SCT)

Figura 4: Exemplo de como a transformação do código-fonte poderia funcionar

O código-fonte de uma função é substituído por um código-fonte gerado automaticamente que inclui instruções para calcular os derivados intercalados com as instruções originais.

A transformação do código-fonte pode ser implementada para todas as linguagens de programação e também é mais fácil para o compilador fazer otimizações de tempo de compilação. No entanto, a implementação da ferramenta AD em si é mais difícil.

Sobrecarga do operador (OO)

Figura 5: Exemplo de como a sobrecarga do operador poderia funcionar

A sobrecarga do operador é uma possibilidade para o código-fonte escrito em uma linguagem que o suporte. Objetos para números reais e operações matemáticas elementares devem ser sobrecarregados para atender à aritmética aumentada descrita acima. Isso não requer nenhuma mudança na forma ou sequência de operações no código-fonte original para que a função seja diferenciada, mas geralmente requer mudanças nos tipos de dados básicos para números e vetores para suportar sobrecarga e frequentemente também envolve a inserção de operações de sinalização especiais.

A sobrecarga do operador para acumulação direta é fácil de implementar e também possível para acumulação reversa. No entanto, os compiladores atuais ficam para trás na otimização do código quando comparados à acumulação direta.

A sobrecarga do operador, para acumulação direta e reversa, pode ser adequada para aplicações em que os objetos são vetores de números reais em vez de escalares. Isso ocorre porque a fita compreende operações vetoriais; isso pode facilitar implementações computacionalmente eficientes, onde cada operação vetorial realiza muitas operações escalares. Técnicas de diferenciação algorítmica adjunta de vetor (vetor AAD) podem ser usadas, por exemplo, para diferenciar valores calculados por simulação de Monte-Carlo.

Exemplos de implementações que sobrecarregam o operador de diferenciação automática em C ++ são as bibliotecas Adept e Stan .

Veja também

• Programação diferenciável

Notas

Referências

Leitura adicional

• Rall, Louis B. (1981). Diferenciação automática: técnicas e aplicações . Notas de aula em Ciência da Computação. 120 . Springer . ISBN 978-3-540-10861-0.
• Griewank, Andreas; Walther, Andrea (2008). Avaliando Derivados: Princípios e Técnicas de Diferenciação Algorítmica . Outros Títulos em Matemática Aplicada. 105 (2ª ed.). SIAM . ISBN 978-0-89871-659-7. Arquivado do original em 23/03/2010 . Página visitada em 2009-10-21 .
• Neidinger, Richard (2010). "Introdução à Diferenciação Automática e Programação Orientada a Objetos MATLAB" (PDF) . Revisão do SIAM . 52 (3): 545–563. CiteSeerX  10.1.1.362.6580 . doi : 10.1137 / 080743627 . Página visitada em 2013-03-15 .
• Naumann, Uwe (2012). A Arte de Diferenciar Programas de Computador . Ferramentas de ambientes de software. SIAM . ISBN 978-1-611972-06-1.
• Henrard, Marc (2017). Diferenciação Algorítmica em Finanças Explicada . Engenharia Financeira Explicada. Palgrave Macmillan . ISBN 978-3-319-53978-2.

links externos

• www.autodiff.org , um "site de entrada para tudo o que você deseja saber sobre diferenciação automática"
• Diferenciação automática de programas OpenMP paralelos
• Diferenciação automática, modelos C ++ e fotogrametria
• Diferenciação automática, abordagem de sobrecarga do operador
• Calcule derivados analíticos de qualquer programa Fortran77, Fortran95 ou C por meio de uma interface baseada na web Diferenciação automática de programas Fortran
• Descrição e exemplo de código para diferenciação automática direta em Scala
• extensões de diferenciação automática finmath-lib , diferenciação automática para variáveis ​​aleatórias (implementação Java da diferenciação automática estocástica).
• Diferenciação Algorítmica Adjunta: Calibração e Teorema da Função Implícita
• Artigo e

implementação de diferenciação automática baseada em modelo C ++

Derivativos tangentes de origem a origem depuráveis

[1] , Gregos exatos de primeira e segunda ordem por diferenciação algorítmica

[2] , Diferenciação Algorítmica Adjunta de um Aplicativo Acelerado por GPU

[3] , Métodos Adjuntos em Ferramentas de Software de Finanças Computacionais para Diferenciação Algorítmicaop