¿Hay alguna implementación en funcionamiento de diferenciación automática en modo inverso para Haskell?

La implementación relacionada más cercana en Haskell que he visto es el modo de avance en http://hackage.haskell.org/packages/archive/fad/1.0/doc/html/Numeric-FAD.html.¿Hay alguna implementación en funcionamiento de diferenciación automática en modo inverso para Haskell?

La investigación relacionada relacionada más cercana parece ser el modo inverso para otro lenguaje funcional relacionado con Scheme en http://www.bcl.hamilton.ie/~qobi/stalingrad/.

Veo el modo inverso en Haskell como una especie de santo grial para muchas tareas, con la esperanza de que pueda usar el paralelismo de datos anidados de Haskell para obtener una aceleración agradable con una gran optimización numérica.

Fuente

2010-04-30 Ian Fiske

Una posible alternativa: he tenido bastante éxito con la optimización de sistemas grandes (por ejemplo, 10000 dimensiones) con AD avanzado. (El código era C++ pero escrito en gran parte en un estilo funcional puro.) El truco era explotar la escasez que tenía mi problema, así que podía usar un tipo disperso para representar las derivadas. Fue más rápido que la versión AD inversa para mi problema (otra vez escrito en C++, pero no del todo puro). – sigfpe

¿De verdad? Me pregunto cómo lograr tal cosa. ¿Alguna pista? –

En respuesta a esta pregunta, he cargado un paquete llamado ad en Hackage para manejar la diferenciación automática en modo inverso en Haskell.

Internamente, aprovecha un truco de Andy Gill's Kansas Lava para observar el uso compartido en la cinta que registra para fines de propagación hacia atrás, y utiliza la marca de nivel de tipo para evitar sensibilidades confusas.

He intentado mantener la API relativamente cerca de Barak Pearlmutter y el paquete de moda de Jeffrey Mark Siskind, pero no pude resistirme a hacer algunos ajustes menores aquí y allá para generalizar.

Todavía tengo que pasar y terminar los restantes combinadores de moda no implementados, descubrir una buena forma de construir una torre AD en modo inverso, validar que no arruiné mi recolección de cálculo básico, y proporcionar un buena API para usar este enfoque para obtener puntos de control del modo reverso local en un programa AD en el modo de adelanto, pero estoy bastante contento con la forma en que las cosas han progresado hasta ahora.

Fuente

2010-05-16 04:39:53

+15

Implementar una biblioteca completa para dar a esta pregunta la respuesta correcta: ¡ahora * eso es * dedicación! –

Especialmente porque mi otra respuesta ya fue marcada como aceptada. ;) –

¡Y lo aprecio! Aunque espero que personas que no sean yo encuentren útil la contribución de Edward. –

No es que yo sepa. Sé que some Haskell folks are interested en diferenciación automática, pero algunas búsquedas rápidas encontraron poco más que comentarios cortos que mencionan el modo inverso; Espero que ya hayas encontrado el mismo material que yo.

También observo que el paquete fad y Stalingrado proyecto que has encontrado son, de hecho, el trabajo de la misma two people, y que al menos el Prof. Pearlmutter ha publicado a la lista de correo haskell-cafe. Es posible que desee considerar contactarlo directamente sobre su trabajo: es posible que tenga algo en progreso o que encuentre obstáculos serios al intentar implementar AD en modo inverso.

Lo siento, no pude encontrar algo más útil; si alguien más quiere profundizar, al menos los enlaces de arriba son un punto de partida.

Fuente

2010-04-30 15:16:06

Gracias por su respuesta de todos modos. Al menos me ayudaste a asegurarme que no me perdí de nada;) –

Tenemos un montón de implementaciones de AD en modo directo (¡incluso tengo una en mi biblioteca de monoides!), Pero el AD en modo inverso para todo Haskell parece ser insoluble.

Tristemente, mientras que Pearlmutter y Siskind dan una traducción para un cálculo lambda, no se traduce en algo que se pueda hacer para arbitrarias Haskell lambdas, no se obtienen las propiedades de introspección correctas y la forma de los tipos cambio en la traducción no obtienes algo que pueda empaquetarse en una mónada, flecha u otra estructura de control.

Tuve una oportunidad a través de una serie de intercambios de correo electrónico con Pearlmutter, pero finalmente lo mejor que pude obtener fue una solución AD en modo inverso para una pequeña EDSL en Haskell, y no una solución para Haskell.

Fuente

2010-04-30 15:16:17

¿Qué quieres decir con "todo Haskell"? No puede esperar diferenciar todas las funciones. Solo quiere diferenciar funciones escritas en una interfaz particular como 'Num'. Pearlmutter ha señalado algunos problemas con los derivados de anidación, pero eso no es un obstáculo para la implementación de AD inverso que se puede utilizar para resolver problemas del mundo real. Los problemas que he encontrado con AD inverso en Haskell han sido diferentes. Para mayor eficiencia, quiere compartir explícitamente en árboles, y almacenar estado en el árbol a medida que lo barre. Todo esto puede implementarse en puro Haskell fino, pero no es eficiente. – sigfpe

Acepto que no necesitaría diferenciar ningún posible programa Haskell, solo más funciones típicas de objetivos numéricos. ¿Estás compartiendo tu EDSL en línea en cualquier lugar? ¿Qué tipo de subproblemas puede diferenciar? –

@Ian: veré cómo pulirlo y publicarlo cuando tenga un tiempo de inactividad. @ user207442: Puedes hacer que el intercambio sea visible por varios medios, la manera en que normalmente uso es a través de StableNames, lo que me permite evitar la fealdad de usar algo explícitamente monádico o usar enlaces let_ explícitos al estilo oleg. Quizás vuelva a intentarlo, ya que tuve que enfrentar esos problemas en otros entornos desde la última vez que revisé el modo inverso AD. –

Creo que avanzar es el camino a seguir en Haskell. No deberías poder hacer el modo inverso en funciones arbitrarias, como señaló Edward. Pero respondiste que deberías poder hacerlo en ciertas funciones restringidas. Y dichas restricciones pueden conducir fácilmente al modo de avance. P.ej. si tiene una función:

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

A continuación, puede crear una instancia a con un tipo diferenciable, y por lo tanto diferenciar foo en modo de avance.

Consulte la biblioteca vector-space en Hackage para obtener una diferenciación automática en el modo de avance muy elegante. Puede que no esté del todo claro cómo usarlo al principio. Lea el artículo al respecto, Beautiful Differentiation por Conal Elliott.

Fuente

2010-05-01 00:22:55 luqui

Gracias, pero la ventaja clave del modo inverso es un gradiente económico. Esto es muy importante en mis aplicaciones, que requieren gradientes de funciones de 1000 de variables. Echaré un vistazo al modo de avance y veré si satisface mis necesidades, pero no soy optimista. –

OK, hojeé el papel y vi el video en http://www.vimeo.com/6622658, y creo que el espacio vectorial podría ser prometedor. Pero todavía no veo cómo usarlo para calcular derivados de funciones. La documentación parece faltar, o soy lento. Quizás abra otra pregunta para esto. –

Para problemas densos de alta dimensión, el modo de avance no es inicial. Si está optimizando un simulador de fluido con 100.000 variables, es simplemente imposible en el modo de avance. Pero solo multiplica la complejidad de la sim fluida por un pequeño factor constante en modo inverso. ¡Incluso para 100,000 variables! (Si tiene suficiente memoria para almacenar el árbol de ejecución) – sigfpe

¿Hay alguna implementación en funcionamiento de diferenciación automática en modo inverso para Haskell?

Respuesta

Cuestiones relacionadas