Wenn ein analytischer Jacobian verfügbar ist, ist es besser, den Hessischen durch oder durch endliche Differenzen des Jacobian anzunähern?

19

Angenommen, ich berechne einige Modellparameter, um die Summe der quadratischen Residuen zu minimieren, und gehe davon aus, dass meine Fehler Gaußsch sind. Mein Modell erzeugt analytische Ableitungen, sodass der Optimierer keine endlichen Differenzen verwenden muss. Sobald die Anpassung abgeschlossen ist, möchte ich Standardfehler der angepassten Parameter berechnen.

Im Allgemeinen wird in dieser Situation angenommen, dass das Hessische der Fehlerfunktion mit der Kovarianzmatrix in Beziehung steht durch: wobei die Varianz der Residuen ist.σ 2

σ2H1=C
σ2

Wenn keine analytischen Ableitungen des Fehlers verfügbar sind, ist es normalerweise unpraktisch, das Hessische zu berechnen, weshalb als gute Näherung genommen wird.JTJ

In meinem Fall habe ich jedoch ein analytisches J, so dass es für mich relativ billig ist, H durch endliche Differenzierung J zu berechnen.

Meine Frage lautet also: Wäre es genauer, H mit meinem exakten J und der obigen Näherung zu approximieren oder H durch endliche Differenzierung von J zu approximieren?

Colin K
quelle

Antworten:

12

Gute Frage. Zunächst erinnern , wo diese Näherung herkommt. Sei Ihr Datenpunkt, Ihr Modell und die Parameter Ihres Modells. Dann ist die Zielfunktion des nichtlinearen Problems der kleinsten Quadrate wobei der Vektor der Residuen ist, . Der genaue Hessische der Zielfunktion ist . Der Fehler in dieser Näherung ist also( x i , y i ) f ( ) β 1HJTJ(xi,yi)f()βrri=yi-f(xi,β)H=JTJ+Σri2RiH-JTJ=Σri2Ri12rTrrri=yif(xi,β)H=JTJ+ri2riHJTJ=ri2ri. Es ist eine gute Annäherung, wenn die Residuen selbst klein sind; oder wenn die 2. Ableitung der Residuen klein ist. Lineare kleinste Quadrate können als Sonderfall betrachtet werden, bei dem die 2. Ableitung der Residuen Null ist.

Die Näherung der endlichen Differenzen ist relativ billig. Um einen zentralen Unterschied zu berechnen, müssen Sie den Jacobianer zusätzlich mal auswerten (ein Vorwärtsunterschied kostet Sie zusätzliche Auswertungen, also würde ich mich nicht darum kümmern). Der Fehler der zentralen Differenzapproximation ist proportional zu und , wobei die Schrittweite ist. Die optimale Schrittweite ist , wobein 4 r h 2 h h ϵ 12nn4rh2h ϵhϵ13ϵist Maschinengenauigkeit. Wenn also die Ableitungen der Residuen nicht explodieren, ist es ziemlich klar, dass die Näherung der endlichen Differenzen VIEL besser sein sollte. Ich sollte darauf hinweisen, dass die Buchhaltung nicht trivial ist, obwohl der Rechenaufwand minimal ist. Jeder endliche Unterschied auf dem Jacobi gibt Ihnen eine Reihe des Hessischen für jedes Residuum. Dann müssen Sie den Hessischen nach der obigen Formel wieder zusammenbauen.

Es gibt jedoch eine dritte Option. Wenn Ihr Löser eine Quasi-Newton-Methode (DFP, BFGS, Bryoden usw.) verwendet, nähert er sich bei jeder Iteration bereits dem Hessischen an. Die Approximation kann recht gut sein, da sie die Zielfunktion und die Gradientenwerte aus jeder Iteration verwendet. Die meisten Löser geben Ihnen Zugriff auf die endgültige hessische Schätzung (oder deren Umkehrung). Wenn das eine Option für Sie ist, würde ich das als hessische Schätzung verwenden. Es ist bereits berechnet und es wird wahrscheinlich eine ziemlich gute Schätzung sein.

Bill Woessner
quelle
Hervorragende Resonanz, danke. Es ist sehr aufschlussreich, dies mit einem Vergleich des jeweiligen Schätzfehlers zu rechtfertigen. Kann ich fragen, woher Sie wissen, dass der optimale Schritt für endliche Differenzen ist? Das habe ich noch nie gesehen. ϵ1/3
Colin K
5
Das ist ein alter Trick, um den Kürzungsfehler gegen den Abrundungsfehler abzugleichen. Um den Kürzungsfehler zu minimieren, möchten Sie natürlich so klein wie möglich machen. Aber sobald zu klein wird, kommt es zu erheblichen Rundungsfehlern. Die Ableitung ist relativ einfach. Unter der Annahme eines zentralen Unterschieds ist der Kürzungsfehler proportional zu . Der Rundungsfehler ist immer proportional zu . Addiere die beiden und minimiere über . Sie erhalten . h h 2 f x ( x ) ϵ f ( x )hhh2f(x) hhϵ1ϵf(x)hhhϵ13
Bill Woessner
3
Dies gilt nur für zentrale Unterschiede. Für Vorwärtsdifferenzen ist die optimale Schrittgröße . Es gibt auch andere Tricks. Stellen Sie beispielsweise sicher, dass Sie tatsächlich wissen, was ist. Ich weiß, das klingt albern, aber seltsame Dinge können in Gleitkomma-Arithmetik passieren. Hier ist eine einfache Möglichkeit , um sicherzustellen , dass Sie den richtigen Wert haben : . Mathematisch gesehen ist natürlich . Wenn Sie jedoch Werte verwenden, die im Gleitkomma nicht genau dargestellt werden können (z. B. ), sehen Sie, dass dies nicht der Fall ist. hhhactual=hdesiredh=0,0001hϵ12hhh_actual = (x + h_desired) - xhactual=hdesiredh=0.0001
Bill Woessner
Vielleicht könnte dieser Inhalt Ihrer Antwort hinzugefügt werden, anstatt den Kommentaren. Auf diese Weise müssen zukünftige Benutzer nicht in einem erweiterten Kommentarbereich nach Material suchen, das sich direkt auf die in der Antwort gemachten Angaben bezieht.
Sycorax sagt Reinstate Monica
2
Du meine Güte. Eine Quasi-Newton-Näherung des Hessischen kann eine schreckliche Schätzung des Hessischen sein und daher zu einer sehr schlechten Schätzung der Kovarianzmatrix führen. Es kann gut dazu dienen, das Fortschreiten des Algorithmus zum Optimum zu erleichtern, kann aber als Schätzung des Hessischen ziemlich schlecht sein.
Mark L. Stone