Automatisk differensiering

Automatisk differensiering ( AD ), også kjent som algoritmisk differensiering eller beregningsdifferensiering , [ 1] er et sett med teknikker for automatisk beregning av deriverte av en matematisk funksjon implementert av et dataprogram . Automatisk differensiering utnytter det faktum at implementeringen av en funksjon , uansett hvor kompleks den er, reduseres til utførelse av en rekke aritmetiske operasjoner (addisjon, subtraksjon, multiplikasjon, divisjon, etc.) ogelementære funksjoner ( eksponentielle , trigonometriske funksjoner , etc.). Ved å bruke kjederegelen gjentatte ganger på slike operasjoner, kan den deriverte av en vilkårlig kompleks funksjon beregnes automatisk, med beregningspresisjonen i bruk, og raskt, ved å bruke et antall operasjoner som maksimalt tilsvarer en liten og konstant faktor med hensyn til antall operasjoner brukt i den opprinnelige funksjonen.

Automatisk differensiering skal ikke forveksles med symbolsk differensiering , som utføres ved å manipulere uttrykkene representert i symbolsk form, og heller ikke med numerisk differensiering , som tilnærmer den deriverte med en endelig forskjell . Den første metoden er vanligvis mye tregere og begrenset av vanskeligheten med å konvertere vilkårlige funksjoner til symbolsk form, mens den andre metoden introduserer numeriske diskretiseringsfeil som har en tendens til å forplante seg og begrense numerisk stabilitet . Videre er begge metodene trege til å beregne partielle deriverte av funksjoner med et stort antall variabler, et problem som ofte oppstår i gradientnedstigningsbaserte optimaliseringsmetoder . Slike metoder underbygger implementeringen av mange maskinlæringsteknikker , spesielt dyp læring , og de fleste rammeverk for dyp læring implementerer automatisk differensiering for automatisk gradientberegning . [2] [3] [4]

Kjederegel og akkumulering fremover og bakover

Kjederegelen lar deg dekomponere et derivat til en rekke enklere derivater. For en sammensetning gir kjederegelen som et resultat

Den automatiske differensieringen kan betjenes på to forskjellige måter, foroverakkumulering ( foroverakkumulering eller forovermodus ) og inversakkumulering ( reversakkumulering eller reversmodus ). Den fremadgående akkumuleringen går gjennom operasjonskjeden fra innsiden og ut (i eksemplet beregner først , deretter og til slutt ), mens den inverse akkumuleringen innebærer å krysse kjeden fra utsiden til innsiden (beregner først , deretter og til slutt og til slutt ). Oppsummert har vi at foroverakkumuleringen beregner den rekursive relasjonen

med , mens invers akkumulering beregner

med . Generelt sett er begge metodene spesielle tilfeller av bruken av programsammensetningsoperatøren , og setter på riktig måte ett av de to argumentene .

Videresend akkumulering

Ved foroverakkumulering er de uavhengige variablene der differensieringen beregnes faste, deretter utføres beregningen av de deriverte av underuttrykkene rekursivt. Dette kan gjøres ved å gjentatte ganger erstatte de deriverte av de interne funksjonene i kjederegelen:

Prosedyren er generalisert til tilfellet i flere variabler, som et produkt av jakobianske matriser .

I motsetning til invers akkumulering, er foroverakkumulering mer naturlig og lettere å implementere, ettersom flyten av informasjon i beregningen av den deriverte faller sammen med evalueringsrekkefølgen, og øker hver variabel med den numeriske verdien av dens deriverte,

Derivatene blir deretter beregnet synkronisert med uttrykksevalueringstrinnene, og kombinert med andre derivater via kjederegelen.

La for eksempel funksjonen gis

hvor, for klarhetens skyld, hvert enkelt underuttrykk er merket med en variabel . Valget av uavhengige variabler bestemmer startverdiene og (kalt frø ). For eksempel, hvis du ønsker å beregne den deriverte av funksjonen med hensyn til , settes startverdiene til

Med disse frøene forplantes derivatene gjennom kjederegelen, som vist i følgende tabell og i beregningsgrafen i figuren til siden.

For å beregne gradienten til funksjonen, er det nødvendig med ytterligere kryssinger av beregningsgrafen, ved å bruke passende frø, for eksempel for å beregne den deriverte med hensyn til .

Beregningskompleksiteten til hver kryssing av grafen er proporsjonal med kompleksiteten til den opprinnelige funksjonen. Foroverakkumulering er mer effektiv enn invers for funksjoner i form med , da det kun kreves kryssinger, sammenlignet med de som kreves ved invers akkumulering.

Invers akkumulering

Ved invers akkumulering er de avhengige variablene som differensieringen beregnes med, faste, deretter beregnes den deriverte rekursivt med hensyn til hvert underuttrykk. Tilsvarende erstattes den deriverte av den ytterste funksjonen i kjederegelen

Mengden som brukes i beregningen ved invers akkumulering kalles en adjoint , betegnet med en skråstrek ( ), og er den deriverte av en avhengig variabel med hensyn til underuttrykket :

Den inverse akkumuleringen krysser kjeden fra utsiden mot innsiden, det vil si at den krysser beregningsgrafen (figur på siden) fra topp til bunn. Én grafovergang er nødvendig for hver komponent av funksjonen , så bare én for skalarfunksjoner . Dette genererer en avveining mellom kostnad i rom og i tid med hensyn til foroverakkumulering: mens invers akkumulering kan kreve færre grafkryssinger, er det imidlertid nødvendig å lagre de mellomliggende variablene (vanligvis ved å bruke en Wengert-liste ), [5] [6 ] som kan representere en uholdbar kostnad når det gjelder minne hvis beregningsgrafen er veldig stor. Dette problemet reduseres delvis ved å lagre bare en del av de mellomliggende verdiene, og rekonstruere resten gjennom ytterligere beregninger (en metode kjent som sjekkpunkt ).

Operasjonene som kreves for å beregne den deriverte ved invers akkumulering i dette eksemplet er:

Beregningsgrafen kan manipuleres for å beregne gradienten til den opprinnelige operasjonen, ved å forsterke hver node med en ekstra node, og med toppunktene mellom de adderte nodene orientert i motsatt retning av toppunktene mellom de opprinnelige nodene. Disse adderte nodene representerer multiplikasjonen med den deriverte av uttrykket beregnet i den opprinnelige noden. For eksempel vil en node som inneholder funksjonen ha uttrykket i den tilsvarende noden lagt til.

Invers akkumulering er mer effektiv enn foroverakkumulering for funksjoner i form med , da det krever traverser av beregningsgrafen, sammenlignet med traverser som kreves av foroverakkumulering.

Den omvendte akkumuleringen ble først publisert i 1970 av Seppo Linnainmaa i sin M.Sc. , [7] [8] [9] og brukes ofte til å implementere feilutbredelse bakover i kunstige nevrale nettverk .

Andre metoder

Forover- og bakoverakkumuleringer er bare to ekstreme metoder for å krysse kjeden av derivater. Problemet med å beregne den jakobiske matrisen med et minimum antall operasjoner er kjent som det optimale jakobiske akkumuleringsproblemet (OJA), og det er et NP-komplett problem . [10]

Automatisk differensiering med to tall

Foroverakkumulering kan implementeres ved å utvide algebraen til reelle tall , der hvert tall er assosiert med en ekstra nilpotent komponent som representerer den deriverte av funksjonen som er evaluert i det tallet. Aritmetiske operasjoner kan utvides til denne nye algebraen, kjent som dobbelttallsalgebra . Denne formuleringen kan generaliseres ytterligere, i det som er kjent som teorien om operasjonell kalkulus .

Utvidet aritmetikk kan konstrueres ved å erstatte et hvilket som helst reelt tall med kvantitet , der det er et reelt tall og er et uendelig , et nilpotent abstrakt tall slik at . Fra denne definisjonen får vi det

og andre operasjoner kan defineres på lignende måte.

Det er mulig å definere polynomer i denne utvidede aritmetikken. Hvis , da

hvor er den deriverte av med hensyn til det første argumentet, og , kalt seed , kan tildeles vilkårlig.

Denne nye aritmetikken består av ordnede par , med vanlig aritmetikk i den første komponenten og førstederiverte aritmetikk i den andre komponenten. Ved å utvide de tidligere resultatene fra polynomer til analytiske funksjoner får vi en ny elementær aritmetikk:

og generelt, for en funksjon vi har

hvor og er derivatene av respekt for henholdsvis det første og andre argumentet.

En elementær binær operasjon kan utvides til konstanter, og applikasjonen til et dobbelttall og en konstant (reelt tall) utføres ved å promotere konstanten til dobbelttallet . Det er mulig å beregne den deriverte av en funksjon i , ved å beregne i denne aritmetikken, hvis resultat er .

Vektor- og multivariabelfunksjoner

Multivariable vektorfunksjoner kan behandles med lignende effektivitet ved å bruke den samme mekanismen for envariabelfunksjoner, ved å definere en retningsderivert operatør som beregner , retningsderiverten av at i retning , som kan beregnes som å bruke den samme aritmetikken definert i forrang . Evalueringer er nødvendig for å beregne gradienten .

Høyere ordens derivater

Aritmetikken definert for den første deriverte kan utvides til å beregne høyere ordens deriverte. Men når rekkefølgen øker, blir uttrykkene mye mer komplekse, og kostnaden er kvadratisk i rekkefølgen til den høyeste deriverte. Du kan definere en lignende algebra på avkortede Taylor-polynomer , slik at du kan utføre beregninger raskere. En generell og streng formulering er definert i sammenheng med den operasjonelle beregningen .

Driftsberegning

Operasjonell kalkulus i programrom [11] generaliserer begrepet automatisk differensiering, generaliserer algebraen av doble tall med en tensoralgebra , og gir et strengt grunnlag for matematikken som brukes i dyp læring .

Implementering

Fremoverakkumulering kan implementeres gjennom en ikke-standard tolkning av programmet, der hvert reelt tall erstattes med et dobbelttall, konstanter erstattes med dobbelttall med uendelig del null, og operasjoner på reelle er erstattet med operasjoner på dualer. Ikke-standard tolkning kan generelt implementeres med to tilnærminger: kildekodetransformasjon og operatøroverbelastning .

Kildekodetransformasjon

Kildekoden til en funksjon erstattes med den automatisk genererte koden til en funksjon som sammenfletter de originale instruksjonene med tilleggsinstruksjonene for beregning av deriverte. Denne tilnærmingen kan implementeres på alle språk, og muliggjør et større antall automatiske optimaliseringer av kompilatoren, men implementeringen av det automatiske generasjonsverktøyet er ganske komplekst.

Operatør overbelastning

Denne metoden kan brukes på språk som støtter operatøroverbelastning . Det krever vanligvis ikke å endre rekkefølgen av operasjoner i programmet, men krever definisjon av flere numeriske datatyper . Det er enklere å implementere, og kan også brukes til omvendt akkumulering, men det gjør automatisk kodeoptimalisering mer kompleks. Eksempler på biblioteker med automatisk differensiering gjennom operatøroverbelastning er Adept og Stan .

Merknader

  1. ^ Richard D. Neidinger, Introduction to Automatic Differentiation and MATLAB Object-Oriented Programming ( PDF ), i SIAM Review , vol. 52, n. 3, 2010, s. 545–563, DOI : 10.1137 / 080743627 .
  2. ^ Ivrig henrettelse , på tensorflow.org .
  3. ^ Automatisk differensieringspakke - torch.autograd , på pytorch.org .
  4. ^ Derivater i Theano-Theano 1.0.0 dokumentasjon , på deeplearning.net .
  5. ^ RE Wengert, Et enkelt automatisk derivatevalueringsprogram , i Comm. ACM , vol. 7, 1964, s. 463–464, DOI : 10.1145 / 355586.364791 .
  6. ^ Michael Bartholomew-Biggs, Steven Brown, Bruce Christianson og Laurence Dixon, Automatisk differensiering av algoritmer , i Journal of Computational and Applied Mathematics , vol. 124, n. 1-2, 2000, s. 171-190, DOI : 10.1016 / S0377-0427 (00) 00422-2 .
  7. ^ Linnainmaa, Seppo (1970). Representasjonen av den kumulative avrundingsfeilen til en algoritme som en Taylor-utvidelse av de lokale avrundingsfeilene. Masteroppgave (på finsk), Univ. Helsinki, 6-7.
  8. ^ Linnainmaa, Seppo (1976). Taylor utvidelse av den akkumulerte avrundingsfeilen. BIT Numerisk matematikk, 16 (2), 146-160.
  9. ^ Griewank, Andreas (2012). Hvem oppfant den omvendte differensieringsmodusen? Optimaliseringshistorier, Documenta Matematica, Extra Volume ISMP (2012), 389-400.
  10. ^ Uwe Naumann, Optimal Jacobian-akkumulering er NP-fullstendig , i Mathematical Programming , vol. 112, n. 2, april 2008, s. 427–441, DOI : 10.1007 / s10107-006-0042-z .
  11. ^ Žiga Sajovic og Martin Vuk, Operational calculus on programmering spaces , 24. oktober 2016.

Bibliografi

Eksterne lenker