Implementacja automatycznego różnicowania dla drugiej pochodnej: algorytm do przechodzenia przez wykres obliczeniowy?

Próbuję wdrożyć automatic differentiation dla pakietu statystyk Python (formułowanie problemu jest podobne do formułowania problemów optymalizacji).Implementacja automatycznego różnicowania dla drugiej pochodnej: algorytm do przechodzenia przez wykres obliczeniowy?

Wykres obliczeniowy jest generowany z wykorzystaniem przeciążenia operatora i funkcji fabrycznych dla operacji takich jak sum(), exp() itp. Zaimplementowałem automatyczne różnicowanie gradientu przy użyciu odwrotnej akumulacji. Jednakże, stwierdziłem, że wprowadzenie automatycznego różnicowania dla drugiej pochodnej (heskiego) jest o wiele trudniejsze. Wiem, jak wykonywać poszczególne obliczenia drugiego gradientu częściowego, ale miałem problemy z wymyśleniem inteligentnego sposobu na przechodzenie przez wykres i robienie nagromadzeń. Czy ktoś wie o dobrych artykułach, które dają algorytmy automatycznego różnicowania dla drugiej pochodnej lub bibliotek open source, które implementują to samo, z czego mogę próbować się uczyć?

Źródło

2010-07-04 John Salvatier

"Off-topic" moja stopa (komentując samotnego SOERA, który głosował w ten sposób) - to wszystko o programowaniu, co jeszcze może "przemierzać obliczenia wykres "być około ?! (Chociaż nie rozumiem, dlaczego @John nie może wykonać drugiej pochodnej przez dwukrotne zastosowanie swojej funkcji pierwszej pochodnej, może to być spowodowane tym, że nie wiem, co to jest "Hesjanin" [[z wyjątkiem żołnierza pochodzącego z Niemiec walczyć o Brytyjczyków w 1776 roku! -)]]). –

Aby odpowiedzieć na pytanie, dwukrotne odróżnienie jest nietrywialne z powodu interakcji między zmiennymi. Jeśli twoja funkcja jest skalarem (z n wejściami), pierwsza pochodna jest długością wektora n, druga pochodna jest macierzą n^2 trzecia pochodna to n^3 itd. Dla pierwszej pochodnej musisz podążać w górę 1 ścieżkę od niezależnej zmiennej zależnej w perspektywie, dla drugiej pochodnej musisz podążać dwiema różnymi ścieżkami. Byłem/byłem trochę zaniepokojony tym tematem, ale nie wiem, jakie jest lepsze forum dla tego pytania; to zdecydowanie nie jest rzecz z przelewem matematycznym. –

Czy automatyczne różnicowanie jest absolutnie konieczne?Za każdym razem, gdy to rozważałem, stwierdziłem, że ręczne rozróżnianie algorytmu ręcznie jest prostsze, ale z drugiej strony, moi hessańczycy zwykle byli dość proste (jak przekątna lub obliczalne przez formułę analityczną). –

Najpierw trzeba zdecydować, czy chcesz o obliczyć rzadki Hesjan lub coś bliżej w pełni gęsty Hesjan.

Jeśli nie jest to dokładnie to, czego chcesz, obecnie istnieją dwa konkurencyjne sposoby robienia tego. Tylko przy użyciu obliczeniowej wykres w sprytny sposób, jeden wsteczny omiecenie obliczeniowej wykresu można obliczyć Macierz Hessego za pomocą algorytmu edge_pushing:

http://www.tandfonline.com/doi/full/10.1080/10556788.2011.580098

Albo można spróbować technik kolorowanie grafu do kompaktowania matrycę Hesji w matryca o mniejszej liczbie kolumn, a następnie za pomocą odwrotnej gromadzeniu obliczyć każdą kolumnę

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.2603

Jeśli to, co chcesz jest gęsta Hesji (co jest niezwykłe w praktyce), wówczas prawdopodobnie lepiej obliczania jedną kolumnę w Hesji czas wykorzystujący odwrotną akumulację (szukanie BRUCE CHRISTIANSON i odwrotna akumulacja)

Źródło

2012-11-24 12:09:40

To całkiem interesujące. Czy masz wersję pdf pierwszego artykułu? –

-1

Zazwyczaj sposób zbliżony Hessian w 3 wymiarach jest BFGS

Sposób L-BFGS jest podobny.

Here można znaleźć kod źródłowy dla L-BFGS (który oblicza Hesjan jako wynik pośredni do rozwiązywania ODE) w kilku językach (C#, C++, VBA, itp.), Chociaż nie w python. Myślę, że nie jest to łatwe do przetłumaczenia.

Jeśli masz zamiar przetłumaczyć ALG z innym języku, należy zwrócić szczególną uwagę na błędy liczbowych i zrobić analizę wrażliwości (trzeba obliczyć odwrotność macierzy Hesji)

Źródło

2010-07-06 00:31:39

Implementacja automatycznego różnicowania dla drugiej pochodnej: algorytm do przechodzenia przez wykres obliczeniowy?

Odpowiedz

Powiązane problemy