Kiedy dostępny jest analityczny jakobian, czy lepiej jest przybliżyć Hessian przez

19

Powiedzmy, że obliczam niektóre parametry modelu, minimalizując resztkowe sumy do kwadratu i zakładam, że moje błędy są gaussowskie. Mój model wytwarza analityczne pochodne, więc optymalizator nie musi używać różnic skończonych. Po zakończeniu dopasowania chcę obliczyć standardowe błędy dopasowanych parametrów.

Zasadniczo w tej sytuacji przyjmuje się, że Hesja funkcji błędu jest powiązana z macierzą kowariancji przez: gdzie jest wariantem reszt.σ 2

σ2H1=C
σ2

Gdy nie są dostępne żadne analityczne pochodne błędu, obliczenie Hesji jest zazwyczaj niepraktyczne, więc jest traktowane jako dobre przybliżenie.JTJ

Jednak w moim przypadku mam analityczną literę J, więc obliczenie H przez różnicowanie skończone J. jest stosunkowo tanie.

Moje pytanie brzmi zatem: czy bardziej dokładne byłoby przybliżenie H przy użyciu mojego dokładnego J i zastosowanie powyższego przybliżenia, czy też przybliżenie H poprzez skończone różnicowanie J?

Colin K.
źródło

Odpowiedzi:

12

Dobre pytanie. Najpierw przypomnij sobie, skąd pochodzi to przybliżenie . Niech będą twoimi punktami danych, będzie twoim modelem, a parametrami twojego modelu. Zatem funkcją celu nieliniowego problemu najmniejszych kwadratów jest gdzie jest wektorem reszt, . Dokładny Hesjan funkcji celu to . Zatem błąd w tym przybliżeniu to( x i , y i ) f ( ) β 1HJTJ(xi,yi)f()βrri=yi-f12rTrrH = J T J + r i 2 r i H - J T J = r i 2 r iri=yif(xi,β)H=JTJ+ri2riHJTJ=ri2ri. To dobre przybliżenie, gdy reszty same w sobie są małe; lub gdy druga pochodna reszt jest mała. Liniowe najmniejsze kwadraty można uznać za szczególny przypadek, w którym 2. pochodna reszty wynosi zero.

Jeśli chodzi o przybliżenie różnic skończonych, jest ono stosunkowo tanie. Aby obliczyć różnicę centralną, musisz ocenić Jacobian dodatkowe razy (różnica w przód będzie cię kosztować n dodatkowych ocen, więc nie zawracałbym sobie głowy). Błąd przybliżenia centralnej różnicy jest proporcjonalny do 4 r i h 2 , gdzie h jest wielkością kroku. Optymalny rozmiar kroku to h ϵ 12nn4rh2h , gdzieϵoznacza precyzję maszyny. Więc jeśli pochodne reszt nie wybuchną, jest całkiem jasne, że przybliżenie różnic skończonych powinno być O wiele lepsze. Powinienem zaznaczyć, że chociaż obliczenia są minimalne, księgowość nie jest łatwa. Każda skończona różnica na Jakubie da ci jeden rząd Hesji na każdą resztę. Będziesz musiał ponownie złożyć Heski, korzystając z powyższej formuły.hϵ13ϵ

Istnieje jednak trzecia opcja. Jeśli Twój solver korzysta z metody Quasi-Newtona (DFP, BFGS, Bryoden itp.), Jest już zbliżony do Hesji przy każdej iteracji. Przybliżenie może być całkiem dobre, ponieważ wykorzystuje funkcję celu i wartości gradientu z każdej iteracji. Większość solverów daje ci dostęp do ostatecznej prognozy Hesji (lub jej odwrotności). Jeśli jest to opcja dla ciebie, użyłbym tego jako szacunku Hesji. Jest już obliczony i prawdopodobnie będzie to całkiem niezły szacunek.

Bill Woessner
źródło
ϵ1/3
5
hhϵ f ( x )h2f(x) hhϵ1ϵf(x)hhhϵ13
3
Dotyczy to tylko różnic centralnych. W przypadku różnic w przód optymalny rozmiar kroku to . Są też inne sztuczki. Na przykład upewnij się, że faktycznie wiesz, co to jest . Wiem, że to brzmi głupio, ale dziwne rzeczy mogą się zdarzyć w arytmetyki zmiennoprzecinkowej. Oto prosty sposób, aby upewnić się, że masz prawidłową wartość : . Matematycznie oczywiście . Ale jeśli użyjesz wartości, których nie można dokładnie przedstawić w postaci zmiennoprzecinkowej (np. ), zobaczysz, że tak nie jest. hhhactual=hdesiredh=0,0001hϵ12hhh_actual = (x + h_desired) - xhactual=hdesiredh=0.0001
Bill Woessner,
Być może ta treść mogłaby zostać dodana do twojej odpowiedzi, a nie do komentarzy. W ten sposób przyszli użytkownicy nie będą musieli przedzierać się przez obszerną sekcję komentarzy, aby znaleźć materiał, który bezpośrednio dotyczy roszczeń zawartych w odpowiedzi.
Sycorax mówi Przywróć Monikę
2
O mój Boże. Przybliżenie quasi-Newtona Hesji może być okropnym oszacowaniem Hesji, a zatem skutkować bardzo słabym oszacowaniem macierzy kowariancji. Może to dobrze służyć do ułatwienia progresji algorytmu do optymalnego, ale może być dość słabe jako oszacowanie Hesji.
Mark L. Stone