Esiste un'implementazione funzionante della differenziazione automatica in modalità inversa per Haskell?

L'implementazione più simile a Haskell che ho visto è la modalità di inoltro a http://hackage.haskell.org/packages/archive/fad/1.0/doc/html/Numeric-FAD.html.Esiste un'implementazione funzionante della differenziazione automatica in modalità inversa per Haskell?

La ricerca correlata più simile correlata sembra essere la modalità inversa per un altro linguaggio funzionale correlato a Schema a http://www.bcl.hamilton.ie/~qobi/stalingrad/.

Vedo la modalità inversa in Haskell come una sorta di Sacro Graal per molti compiti, con la speranza che possa usare il parallelismo dei dati nidificato di Haskell per ottenere una buona accelerazione con una pesante ottimizzazione numerica.

fonte

2010-04-30 Ian Fiske

Una possibile alternativa: ho avuto un bel po 'di successo con l'ottimizzazione di sistemi di grandi dimensioni (ad esempio 10000 dimensionale) con forward AD. (Il codice era C++ ma in gran parte scritto in uno stile puramente funzionale.) Il trucco era quello di sfruttare la sparsità che il mio problema aveva in modo da poter usare un tipo sparse per rappresentare le derivate. Era più veloce della versione reverse AD per il mio problema (di nuovo scritto in C++, ma per niente puro). – sigfpe

Davvero? Mi sto chiedendo come realizzare una cosa del genere. Qualche vantaggio? –

In risposta a questa domanda, ho caricato un pacchetto denominato ad in Hackage per la gestione della differenziazione automatica in modalità inversa in Haskell.

Internamente, sfrutta un trucco di Kansas Lava di Andy Gill per osservare la condivisione nel nastro che registra per scopi di propagazione posteriore e utilizza il marchio di livello di tipo per evitare confuse sensibilità.

Ho cercato di mantenere l'API relativamente vicino a quello di Barak Pearlmutter e del pacchetto di moda di Jeffrey Mark Siskind, ma non ho potuto resistere a fare un paio di modifiche minori qua e là per la generalità.

Ho ancora bisogno di passare e finire i restanti combinatori di mode non implementati, trovare un modo carino per costruire una torre AD in modalità inversa, convalidare che non ho rovinato il mio ricordo del calcolo di base e fornire un bella API per l'utilizzo di questo approccio per ottenere checkpoint locali in modalità inversa in un programma AD in modalità di inoltro altrimenti, ma sono abbastanza contento di come le cose sono progredite finora.

fonte

2010-05-16 04:39:53

+15

Implementare un'intera libreria per dare a questa domanda una risposta adeguata - ora * è * dedizione! –

Tanto più che la mia altra risposta era già stata contrassegnata come accettata. ;) –

E lo apprezzo !! Anche se spero che le persone diverse da me troveranno utile il contributo di Edward. –

Non che io sappia. So che some Haskell folks are interested nella differenziazione automatica, ma alcuni scavi veloci hanno trovato poco più che brevi accenno alla modalità inversa; Mi aspetto che tu abbia già trovato lo stesso materiale che ho fatto.

Ho anche notare che il pacchetto fad e progetto Stalingrado avete trovato sono infatti opera dello stesso two people, e che almeno il Prof. Pearlmutter ha pubblicato alla haskell-cafe mailing list. Puoi prendere in considerazione di contattarlo direttamente sul suo lavoro: è possibile che abbia qualcosa in corso o che si imbattesse in seri ostacoli mentre tentava di implementare AD in modalità inversa.

Scusate, non sono riuscito a trovare nulla di più utile; se qualcun altro vuole approfondire, almeno i link sopra sono un punto di partenza.

fonte

2010-04-30 15:16:06

Grazie comunque per la tua risposta. Almeno mi hai aiutato a rassicurarmi che non mi sono perso qualcosa;) –

Abbiamo un sacco di implementazioni di modalità avanti AD (ne ho persino una nella mia libreria di monoidi!), Ma la modalità inversa AD per tutto Haskell sembra essere intrattabile.

Tristemente mentre Pearlmutter e Siskind danno una traduzione per un lambda calcolo, non mappa in qualcosa che puoi fare per arbitrario Haskell lambdas, non hai le giuste proprietà di introspezione e dato il modo in cui la forma dei tipi cambiare nella traduzione non si ottiene qualcosa che è suscettibile di essere impacchettato in una monade, una freccia o altra struttura di controllo.

Ho avuto un tentativo tramite una serie di scambi di e-mail con Pearlmutter, ma alla fine il meglio che sono riuscito a ottenere era una soluzione AD in modalità inversa per una piccola EDSL in Haskell, e non una soluzione per Haskell stessa.

fonte

2010-04-30 15:16:17

Cosa intendi con "tutto Haskell"? Non puoi aspettarti di differenziare tutte le funzioni. Si desidera solo differenziare le funzioni scritte su una particolare interfaccia come 'Num'. Pearlmutter ha evidenziato alcuni problemi con i derivati del nesting, ma non è un ostacolo per implementare il reverse AD che può essere utilizzato per risolvere problemi del mondo reale. I problemi che ho riscontrato con reverse AD in Haskell sono stati diversi. Per efficienza vuoi una condivisione esplicita sugli alberi e per memorizzare lo stato nell'albero mentre lo attraversi. Tutto questo può essere implementato in pura Haskell, ma non è efficiente. – sigfpe

Sono d'accordo sul fatto che non avrei bisogno di differenziare eventuali programmi Haskell - solo funzioni obiettivo tipiche numeriche. Stai condividendo la tua EDSL online ovunque? Che tipo di sottoproblemi possono differenziarsi? –

@Ian: vedrò di lucidarlo e pubblicarlo quando avrò dei tempi di inattività. @ user207442: Puoi rendere la condivisione visibile con un numero di mezzi, il modo in cui di solito vado attraverso StableNames, che mi permette di evitare un sacco di bruttezza nell'usare qualcosa esplicitamente monadico o usando legamenti espliciti let in stile oleg. Potrei provarci di nuovo perché ho dovuto affrontare questi problemi in altre impostazioni dall'ultima volta che ho visto la modalità reverse AD. –

Penso che in avanti sia la strada da percorrere per Haskell. Non dovresti essere in grado di fare la modalità inversa su funzioni arbitrarie, come ha fatto notare Edward. Ma hai risposto che dovresti essere in grado di farlo su determinate funzioni vincolate. E detti vincoli possono portare facilmente alla modalità di inoltro. Per esempio. se si dispone di una funzione:

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

Quindi è possibile creare un'istanza con un tipo a differenziabile, e quindi differenziare foo in modalità avanti.

Vedere la libreria vector-space su Hackage per la differenziazione automatica in modalità avanzata molto elegante. Potrebbe non essere del tutto chiaro come usarlo all'inizio. Leggi il documento a riguardo, Beautiful Differentiation di Conal Elliott.

fonte

2010-05-01 00:22:55 luqui

Grazie, ma il vantaggio chiave della modalità inversa è un gradiente economico. Questo è molto importante nelle mie applicazioni, che richiedono gradienti di funzioni di migliaia di variabili. Guardo la modalità avanti e vedo se soddisfa le mie esigenze, ma non sono ottimista. –

OK, ho scremato il foglio e guardato il video all'indirizzo http://www.vimeo.com/6622658, e penso che lo spazio vettoriale potrebbe essere promettente. Ma continuo a non vedere come usarlo per calcolare effettivamente i derivati delle funzioni. Le documentazioni sembrano mancare, o sono lento. Forse aprirò un'altra domanda per questo. –

Per problemi densi di alta dimensione, la modalità di inoltro non è di avviamento. Se stai ottimizzando una simulazione fluida con 100.000 variabili, è semplicemente impossibile in modalità avanti. Ma moltiplica solo la complessità della simulazione di un piccolo fattore costante in modalità inversa. Anche per 100.000 variabili! (Se hai abbastanza memoria per memorizzare l'albero di esecuzione.) – sigfpe

Esiste un'implementazione funzionante della differenziazione automatica in modalità inversa per Haskell?

risposta

Problemi correlati