PA081: Programování numerických výpočtů 7. Automatické vyhodnocení derivací Motivace Ruční postup Automatické derivování Zpětné vyhodnocení jaro 2016 Motivace PA081: Programování numerických výpočtů kromě funkce dokážeme vyhodnotit i její derivace ► první, druhé, ... ► parciální mnohé numerické problémy jsou lépe řešitelné metodami s dostupnou derivací metody s derivací zpravidla rychleji konvergují ► Newton vs. metoda sečen Motivace Ruční postup Automatické derivování Zpětné vyhodnocení PA081: Motivace Programování numerických výpočtů ► kromě funkce dokážeme vyhodnotit i její derivace ► první, druhé, ... ► parciální Motivace Ruční postup Automatické derivování ► mnone numerické proDiemy jsou lepe resiteme metoaami vyhodnocení s dostupnou derivací ► metody s derivací zpravidla rychleji konvergují ► Newton vs. metoda sečen ► aproximace konečnou diferencí nestačí ► zpracovávaná funkce nebývá triviální ► analytické vyjádření derivace je náročné ► zdroj nebezpečných chyb ► komplikace při změnách Ruční postup ► funkce je implementována jako program ► hledáme program, který vedle funkční hodnoty spočte i derivace ► http://www.autodiff.org PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení 3/17 Ruční postup ► funkce je implementována jako program ► hledáme program, který vedle funkční hodnoty spočte i derivace ► http://www.autodiff.org příklad s majákem PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení bod dopadu paprsku na nábřeží y\ = v tancot y - tancot y2 = yyi Ruční postup ► vyjádřeno jako jednoduchý program a := tanout; y1 := va/(y - a); y2'=yyú ► chceme spočítat i rychlost pohybu, tj. derivaci v čase ► výpočet současně s původní funkcí PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení ai : a := yi J2 = COt ■- tanai = y -a = va/d2 = yyi t := ä\ : ä := ýi J2 1 = coi -- ái/(cosai)2 = -á = v(äaz - aäi)ICÍ2 = yýi pouze mechanická aplikace základních pravidel Automatické derivování ► transformace zdrojového kódu (např. ADIC) ► přetížení operátorů a funkcí (ADOL-C) ► zjednodušený příklad class adouble { double x; double dx; ... } adouble operátor * (adouble a, adouble b) { adouble r; r.x = a.x * b.x; r.dx = a.x * b.dx + a.dx * b.x; return r; } adouble vl, v2, v3; ■ ■ ■ vl = v 2 * v3; Automatické derivování ► ► ► ► PA081: Programování numerických výpočtů ► aktivní proměnná nezávislé proměnné, podle kterých chceme derivovat všechny další proměnné na nich během výpočtu závisející ► vyhrazený typ adouble ► přiřazení adouble — double je chybné ztrácíme informaci o derivacích tam, kde je potřebná explicitní přístup metodou val ue() ► více nezávislých proměnných ► s každou aktivní proměnnou udržujeme vektor parciálních derivací Motivace Ruční postup Automatické derivování Zpětné vyhodnocení Typický program PA081: Programování numerických výpočtů #define NUMBER_DIRECTIONS 3 #define ADOLC_TAPELESS #include func(adouble[], const adouble[]); adouble x[3]; adouble y[4]; ■ ■ ■ for (i=0; i<3; i++) for (j=0; i<3; x[i].setADValue(j,i= Motivace Ruční postup Automatické derivování Zpětné vyhodnocení =j ? 1.0 : 0.0); func(y,x); for (i=0; i<4; i++) { cout « y. getVal ue() « " : 11; for (j=0; j<3; j++) cout « y.getADValue(j) « ", cout « endl; 7/17 Není to tak jednoduché ► nediferencovatelné funkce (fmod) ► nelze použít ► absolutní hodnota (f abs) ► v 0 pravá nebo levá derivace ± 1 ► případně položíme uměle rovnu 0 ► minimum a maximum (f mi n, f max) ► lze nahradit (a + b ± \a - b\)/2 ► nedefinované na celém R (sqrt, pow, tan, . ► derivaci položíme uměle NaN, resp. Inf ..) PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení Zpětné vyhodnocení ► množství potřebných operací O(mfe) pro /: Km ► m počet nezávislých proměnných ► n počet závislých proměnných ► fc počet kroků výpočtu ► nepříjemné s rostoucím m ► velká třída problémů velkým m ale malým n ► optimalizace funkce více proměnných (n = 1) n PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení Zpětné vyhodnocení ► množství potřebných operací O(mfe) pro /: Km — R ► m počet nezávislých proměnných ► n počet závislých proměnných ► fc počet kroků výpočtu ► nepříjemné s rostoucím m ► velká třída problémů velkým m ale malým n ► optimalizace funkce více proměnných (n = 1) n PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení ► počítali jsme citlivost pomocných proměnných na změny vstupu ► obrácený postup, citlivost výstupu (závislých proměnných) na změny pomocných ► výpočet od konce Zpětné vyhodnocení ► triviální příklad y = sinx2 ► tedy po krocích a\ = x2, y = sinai ► formálním derivováním dy/dai = cosai dai/dx = 2x ► dostáváme dy/dx = 2xcosai PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení 10/17 Zpětné vyhodnocení ► triviální příklad y = sin x2 ► tedy po krocích a\ = x2, y = sinai ► formálním derivováním dy/dai = cosai dai/dx = 2x ► dostáváme dy/dx = 2.x cos ai ► označujeme ä = dy Ida ► obecně v konkrétním kroku a\ = /(a/, a*,...) derivujeme dai/daj = g(aj,au, ■ ■ ■) ► spolu se známým ät = dy/dat dostaneme PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení äj = dy/dcij = g(dj,ak, ...)äi 10/17 Zpětné vyhodnocení ► triviální příklad y = sin x2 ► tedy po krocích a\ = x2, y = sinai ► formálním derivováním dy/dai = cosai dai/dx = 2x ► dostáváme dy/dx = 2xcosai ► označujeme ä = dy Ida ► obecně v konkrétním kroku at = f(aj,ak, ■ ■ ■) derivujeme dai/daj = g(aj,ak, ■■■) ► spolu se známým at = dy/dai dostaneme äj = dy/ddj = g(aj,ak, ■ ■ ■ )ät ► tyto konstrukce jsou pouze ilustrativní, zjednodušené a v principu nekorektní PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení Zpětné vyhodnocení ► např. funkce y = sin(xi/X2)^Xs a\ := X1/X2 a 2 := sinai U3 := eX3 y := a2a3 y := 1 ^2 := a?>y ä3 := a2y x 3 := eX3ä3 ä\ := ä 2 cosai X2 '■= ~ä\/X2 X\ := ČÍ2IX2 ► v O(nk) operacích máme všechny dy/dxi PA08i: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení PA081: Stopa výpočtu Programování numerických výpočtů Motivace ► derivace se vyhodnocují od konce ► tj. až poté, co proběhl výpočet funkce ► proto „zpětné" (reverse) vyhodnocení Ruční postup Automatické derivování Zpětné vyhodnocení ► výpočet funkce je nutné nějak zaznamenat ► ADOL-C: datová struktura (i soubor) páska (tape) ► záznam posloupnosti operací, nikoli konkrétních hodnot ► lze recyklovat pro jiný vstup ► případné rozdílnosti vyhodnocení (a>b ? c : d) jsou detekovány ► použije se pro vyhodnocení funkce, gradientu/Jakobiánu, Hessiánu, ... Instrumentace pro zpětné vyhodnocení PA081: Programování numerických výpočtů /* vstup */ /* vystup */ #include void func( double px[4], double py[4], ) { adouble x[4],y[4],aux; trace_on(0); f or (i=0; i<4; x [i] «= px[i]; aux = x[l] * x[4] + exp(x[2]); /* paska 0 */ /* vlastni vypočet */ Motivace Ruční postup Automatické derivování Zpětné vyhodnocení y [4] = si n (aux) ; f or (i=0; i<4; i++) y [i] »= py[i]; trace_off(); 13/17 Drivery ► ADOL-C poskytuje celou řadu „driver" funkcí ► vstupem je vždy páska a konkrétní vstupní hodnoty ► driver provede výpočet na základě záznamu na pásce ► funkční hodnota funkce Rn — Rm ► function(short tag, int m, int n, double x[n],double y[m]) ► gradient funkce Rn — R ► gradient(short tag, int n, double x[n],double g[n]) ► Jakobián funkce Rn - Rm ► jacobian(short tag, int m, int n, double x[n],double J[m][n]) ► Hessián (matice druhých derivací) funkce Rn — R ► hessian(short tag, int m, int n, double x[n],double H[n][n]) Drivery ► optimalizované varianty pro Newtonovu metodu ► řešení různých typů diferenciálních rovnic ► speciální varianty pro řídké Jakobiány a Hessiány ► tenzory vyšších derivací implicitně definované funkce G(x,y) =0 PA081: Programování numerických výpočtů Motivace Ruční postup Automatické derivování Zpětné vyhodnocení obecné - plná kontrola nad zpracováním pásky Rekapitulace zpětného vyhodnocení PA081: Programování numerických výpočtů ► aktivní proměnné deklarovat jako adoubl e ► výpočet označit trace_on() ... trace_off () ► zavolat instrumentovanou funkci jednou ► s typickými hodnotami vstupů ► vyprodukuje záznam výpočtu - pásku ► opakovaně volat potřebné drivery ► případně na různé vstupy ► pro jinou posloupnost výpočtu zavolat instrumentovanou funkci s jinou páskou Motivace Ruční postup Automatické derivování Zpětné vyhodnocení Další materiál ► rozsáhlá problematika, řada implementací ► včetně obsáhlé teorie ► http://www.autodiff.org ► přehled nástrojů, FAQ, ... ► https://projects.coi n-or.org/ADOL-C ► implementac a dokumentace ADOL-C ► včetně řady příkladů ► Griewank, Walter. Evaluating Derivatives. 2008