Gibt es eine funktionierende Implementierung von Reverse-Modus automatische Differenzierung für Haskell?

Die am nächsten verwandte Implementierung in Haskell, die ich gesehen habe, ist der Vorwärtsmodus bei http://hackage.haskell.org/packages/archive/fad/1.0/doc/html/Numeric-FAD.html.Gibt es eine funktionierende Implementierung von Reverse-Modus automatische Differenzierung für Haskell?

Die am nächsten verwandte verwandte Forschung scheint Umkehrmodus für eine andere funktionale Sprache im Zusammenhang mit Schema bei http://www.bcl.hamilton.ie/~qobi/stalingrad/ zu sein.

Ich sehe den umgekehrten Modus in Haskell als eine Art heiligen Gral für viele Aufgaben, mit der Hoffnung, dass Haskells verschachtelte Datenparallelität eine schöne Beschleunigung in der schweren numerischen Optimierung erreichen könnte.

Quelle

2010-04-30 Ian Fiske

Eine mögliche Alternative: Ich hatte ziemlich viel Erfolg mit der Optimierung großer Systeme (z. B. 10000 dimensional) mit Vorwärts-AD. (Der Code war C++, aber größtenteils in einem rein funktionalen Stil geschrieben.) Der Trick bestand darin, die Seltenheit meines Problems auszunutzen, sodass ich einen Sparse-Typ verwenden konnte, um die Derivate darzustellen. Es war schneller als die umgekehrte AD-Version für mein Problem (wieder in C++ geschrieben, aber überhaupt nicht rein). – sigfpe

Wirklich? Ich frage mich, wie ich so etwas erreichen kann. Irgendwelche Leads? –

Als Antwort auf diese Frage habe ich ein Paket mit dem Namen ad Hackage für den Umgang mit Reverse-Modus automatische Differenzierung in Haskell hochgeladen.

Intern nutzt es einen Trick von Andy Gills Kansas Lava, um zu beobachten, wie das Band für Back-Propagation-Zwecke aufgezeichnet wird, und verwendet Typ-Level-Branding, um verwirrende Empfindlichkeiten zu vermeiden.

Ich habe versucht, die API relativ nah an der von Barak Pearlmutter und Jeffrey Mark Siskind Fad Paket halten, aber ich konnte nicht widerstehen, ein paar kleinere Verbesserungen hier und da für die Allgemeinheit zu machen.

Ich muss noch gehen und beenden die verbleibenden nicht implementierten Modenkombinatoren, herauszufinden, eine gute Möglichkeit, einen Reverse-Modus AD Tower zu bauen, zu validieren, dass ich meine Erinnerung an Grundrechnung nicht vermasselt, und bieten eine nice API für die Verwendung dieses Ansatzes, um lokale Reverse-Modus-Checkpoints in einem ansonsten Forward-Modus AD-Programm zu bekommen, aber ich bin ziemlich glücklich darüber, wie die Dinge bisher Fortschritte gemacht haben.

Quelle

2010-05-16 04:39:53

+15

Eine ganze Bibliothek implementieren, um dieser Frage eine richtige Antwort zu geben - jetzt * das ist Widmung! –

Zumal meine andere Antwort bereits als akzeptiert markiert war. ;) –

Und ich schätze es !! Obwohl ich hoffe, dass andere Leute als ich Edwards Beitrag nützlich finden werden. –

Nicht, dass ich mir dessen bewusst bin. Ich weiß, dass some Haskell folks are interested in der automatischen Differenzierung, aber einige schnelle Grabung gefunden wenig mehr als kurze neben erwähnt die Umkehr-Modus; Ich nehme an, du hast das gleiche Material schon gefunden.

Ich stelle auch fest, dass das fad Paket und Stalingrad-Projekt Sie ist in der Tat die Arbeit der gleichen two people gefunden, und dass zumindest Prof. Pearlmutter hat zur haskell-cafe Mailing-Liste geschrieben. Vielleicht sollten Sie in Betracht ziehen, ihn direkt über seine Arbeit zu informieren - es ist möglich, dass er etwas in Arbeit hat oder bei der Implementierung von Reverse-Modus-AD auf ernsthafte Hindernisse stößt.

Tut mir leid, ich konnte nichts Nützlicheres aufzeigen; wenn jemand anders weiter graben möchte, sind zumindest die obigen Links ein Ausgangspunkt.

Quelle

2010-04-30 15:16:06

Danke für Ihre Antwort jedenfalls. Du hast mir zumindest geholfen, mir zu versichern, dass ich nichts verpasst habe;) –

Wir haben eine Reihe von AD-Implementierungen im Forward-Modus (ich habe sogar einen in meiner Monoids-Bibliothek!), Aber der Reverse-Modus AD für alle Haskell scheint unzugänglich zu sein.

Traurig, während Pearlmutter und Siskind eine Übersetzung für einen Lambda-Kalkül geben, wird es nicht in etwas, was Sie für beliebige Haskell Lambdas tun können, zugeordnet, erhalten Sie nicht die richtigen Introspektionseigenschaften und gegeben die Art der Typen Veränderung in der Übersetzung Sie erhalten nicht etwas, das in eine Monade, einen Pfeil oder eine andere Kontrollstruktur gepackt werden kann.

Ich habe es über eine Reihe von E-Mail-Austausch mit Pearlmutter versucht, aber das Beste, was ich erhalten konnte war eine Reverse-Modus AD-Lösung für eine kleine EDSL in Haskell, und keine Lösung für Haskell selbst.

Quelle

2010-04-30 15:16:17

Was meinst du mit "ganz Haskell"? Sie können nicht erwarten, alle Funktionen zu unterscheiden. Sie möchten nur Funktionen unterscheiden, die auf eine bestimmte Schnittstelle geschrieben sind, wie zum Beispiel 'Num'. Pearlmutter hat auf einige Probleme mit Schachtelableitungen hingewiesen, aber das ist kein Hindernis für die Implementierung von Reverse AD, die zur Lösung von Problemen in der realen Welt verwendet werden können. Die Probleme, die ich mit reverse AD in Haskell gefunden habe, waren anders. Aus Gründen der Effizienz möchten Sie die explizite Freigabe in Bäumen und den Status im Baum speichern, während Sie ihn durchlaufen. Dies alles kann in reiner Haskell-Qualität implementiert werden, ist aber nicht effizient. – sigfpe

Ich stimme zu, dass ich keine möglichen Haskell-Programme unterscheiden müsste - nur mehr typische numerische Zielfunktionen. Teilen Sie Ihre EDSL überall online? Welche Art von Teilproblemen kann es unterscheiden? –

@Ian: Ich werde sehen, es zu polieren und es zu veröffentlichen, wenn ich ein paar Ausfallzeiten bekomme. @ @ user207442: Sie können die Freigabe durch eine Reihe von Mitteln sichtbar machen, die Art, wie ich normalerweise gehe, ist durch StableNames, was mir die Hässlichkeit der Verwendung von explizit monadischen oder expliziten Let_Bindungen mit dem oleg-Stil vermeidet. Ich werde es vielleicht nochmal versuchen, da ich diese Probleme in anderen Einstellungen angehen musste, seit ich das letzte Mal im Reverse-Modus AD geschaut habe. –

Ich denke vorwärts ist der Weg in Haskell zu gehen. Sie sollten nicht in der Lage sein, bei beliebigen Funktionen den umgekehrten Modus auszuführen, wie Edward hervorhob. Aber Sie haben darauf geantwortet, dass Sie dies in bestimmten eingeschränkten Funktionen tun können. Und diese Einschränkungen können leicht zum Vorwärtsmodus führen. Z.B. Wenn Sie eine Funktion haben:

foo :: Num a => a -> a -> a

Dann können Sie a mit einem differenzierbar Typ, instanziiert und damit foo in Vorwärtsmodus unterscheiden.

Sehen Sie die vector-space Bibliothek auf Hackage für sehr elegante Vorwärtsmodus automatische Differenzierung. Es ist vielleicht nicht ganz klar, wie man es zuerst benutzt. Lesen Sie den Artikel darüber, Beautiful Differentiation von Conal Elliott.

Quelle

2010-05-01 00:22:55 luqui

Danke, aber der Hauptvorteil des Reverse-Modus ist ein billiger Gradient. Dies ist sehr wichtig in meinen Anwendungen, die Gradienten von Funktionen von 1000 Variablen erfordern. Ich werde mir den Vorwärtsmodus ansehen und sehen, ob er meinem Bedarf entspricht, aber ich bin nicht optimistisch. –

OK, ich habe die Zeitung überflogen und das Video unter http://www.vimeo.com/6622658 angeschaut, und ich denke, der Vektorraum könnte vielversprechend sein. Aber ich sehe immer noch nicht, wie man es benutzt, um Ableitungen von Funktionen tatsächlich zu berechnen. Dokumentationen scheinen zu fehlen, oder ich bin langsam. Vielleicht werde ich eine andere Frage dafür aufmachen. –

Bei dichten hochdimensionalen Problemen ist der Vorwärtsmodus kein Problem. Wenn Sie eine flüssige Simulation mit 100.000 Variablen optimieren, ist das im Vorwärtsmodus einfach unmöglich. Es multipliziert jedoch nur die Fluid-Sim-Komplexität um einen kleinen konstanten Faktor im Rückwärtsmodus. Sogar für 100.000 Variablen! (Wenn Sie genug Speicher haben, um den Ausführungsbaum zu speichern.) – sigfpe

Gibt es eine funktionierende Implementierung von Reverse-Modus automatische Differenzierung für Haskell?

Antwort

Verwandte Themen