Kiedy automatyczne różnicowanie jest tanie?

12

Automatyczne różnicowanie pozwala nam na liczbową ocenę pochodnej programu na określonym wejściu. Istnieje twierdzenie, że obliczenia te można wykonać kosztem mniejszym niż pięciokrotność kosztu uruchomienia oryginalnego programu. Ten współczynnik pięciu jest górną granicą.

W jakich sytuacjach można dodatkowo obniżyć ten koszt? Wiele kodów pochodnych w terenie działa z prędkością zbliżoną do prędkości oryginalnego programu. Co zrobiono, aby uzyskać to przyspieszenie?

Jakie cechy oryginalnego programu można wykorzystać do przyspieszenia obliczeń?

Jakie sztuczki inżynierii oprogramowania można zastosować, aby przyspieszyć obliczenia?

automatic-differentiation efficiency

— MRocklin
źródło

1

Z pewnością chciałoby się wykorzystać specjalne właściwości pochodnych funkcji, takich jak funkcja wykładnicza i funkcje trygonometryczne. Wiele potencjalnych wspólnych podwyrażeń.

— JM

Czy pytasz o tryb wsteczny lub tryb do przodu?

— Jed Brown,

Moje (ograniczone) zrozumienie jest takie, że zarówno tryb do przodu, jak i do tyłu mają w przybliżeniu podobne koszty.

— MRocklin,

6

Moje ograniczone rozumienie AD przypomina to, co powiedział Matt. Aby przyspieszyć obliczanie pochodnych, struktura grafu ekspresyjnego musi wykorzystywać rzadkość i niedobór w zbiorze macierzy jakobskich. (Zobacz ten artykuł Griewank, aby uzyskać więcej informacji.) Sztuczki inżynierii oprogramowania prawdopodobnie byłyby w samym kodzie AD w celu zrestrukturyzowania wykresu wyrażeń, aby wykorzystać te właściwości w zestawie macierzy jakobskich. Wiedza, w jaki sposób kod AD generuje wykres wyrażeń na podstawie pisanego kodu, pomoże z kolei lepiej zrozumieć, jak pisać kod wymagający mniejszej liczby obliczeń. Każdy dobry kod AD powinien już korzystać z elementów wewnętrznych z typowymi podwyrażeniami, ale dobre kody AD są trudne do napisania.

Standardowym odniesieniem w tej dziedzinie jest ocena pochodnych: zasady i techniki różnicowania algorytmicznego, wydanie drugie autorstwa Andreasa Griewank i Andrei Walther, i powinna dostarczyć bardziej szczegółowych informacji o tym, jak zmniejszyć liczbę obliczeń potrzebnych do oceny pochodnej programu.

— Geoff Oxberry
źródło

3

Każde AD nadal potrzebuje tych wewnętrznych elementów, więc nie widzę, co to ma wspólnego z ogólną złożonością wyrażenia. Zgaduję, że można sklasyfikować złożoność według liczby ścieżek na wykresie wyrażeń, ponieważ w ten sposób frazujesz AD. Andrew Lyons ma tutaj dobrą pracę na wykresach szeregowo-równoległych.

— Matt Knepley
źródło