Библиотека автоматического дифференцирования в Scheme / Common Lisp / Clojure

Я слышал, что одной из первоначальных мотиваций Маккарти для изобретения Лиспа было создание системы для автоматического распознавания. Несмотря на это, мой поиск в Google не дал никаких библиотек / макросов для этого. Существуют ли какие-либо библиотеки (макросы) Scheme / Common Lisp / Clojure для взятия функции F и возврата функции dF / dx, которая вычисляет производную от F?

Я бы хотел, чтобы он поддерживал F несколькими аргументами. Пользователь мог бы выбрать, по какому из них нужно различать x. В идеале дифференциатор работал бы даже для векторных F и x.

РЕДАКТИРОВАТЬ: несколько человек упомянули о символической дифференциации. Разница между символическим дифференцированием и автоматическим различием невелика, но она хорошо резюмирована в Википедии, и особенно в этом изображении. Это различие не так сильно в lisp, где символические выражения могут быть превращены в рабочие программы как есть, но остается потенциальная трудность:

Символическое дифференцирование требует, чтобы дифференцируемое выражение состояло из операций с известными производными. Например, кто-то упомянул пример макроса SICP, который перебирает простые выражения, такие как (+ y (* (x y))), и использует правило цепочки, наряду со знанием того, как различать + и *, чтобы вернуть sexp, представляющий производную. Мне это понадобится для работы с выражениями типа (* (foo x y) (bar x)), где foo и bar могут, в свою очередь, вызывать другие функции, производные которых не известны во время дифференцирования.

Это было бы хорошо, если бы есть способ взять выражение типа (foo x y) и заменить его телом функции, заменив любое упоминание аргументов на x и y гигиеничным способом. Есть?

Кроме того, ни одно из вышеперечисленных действий не решает проблем, возникающих при дифференцировании векторных функций по отношению к векторным аргументам ... для чего и ориентировано большинство реализаций автодифференцирования.


clojure numerical-methods automatic-differentiation lisp scheme
person SuperElectric    schedule 03.02.2011    source источник
comment
Тег числовых методов не подходит для вашего вопроса, потому что вы запрашиваете символическое дифференцирование. Нахождение производной функции f в точке x путем численного дифференцирования было бы просто вычислением (f (x + dx) -f (x)) / dx для некоторого небольшого значения dx.   -  person Curd    schedule 04.02.2011
comment
@curd: Добавляя тег числовых методов, я не имел в виду, что искал способ выполнить численное дифференцирование, чего я, конечно же, не искал. Я просто имел в виду, что вопрос касается функций, относящихся к числовым вычислениям (например, оценка символьных выражений, реализующих численные методы).   -  person SuperElectric    schedule 04.02.2011
comment
Я с тобой. Это расстраивает то, что каждый раз, когда я упоминаю автоматическую дифференциацию, люди путают ее с символической дифференциацией и часто отказываются слышать, что есть разница. Это, безусловно, численный метод, и это уж точно не численное дифференцирование.   -  person sigfpe    schedule 29.04.2011

Ответы (7)


arrow_upward
4
arrow_downward

Есть два других пакета, оба для автоматического различения в Scheme. Второй основан на первом, но переработан как куриное яйцо. Они поддерживают как прямой, так и обратный режим.

person Barak A. Pearlmutter    schedule 10.04.2013

arrow_upward
8
arrow_downward

Алексей Радул пишет:

Ну, в Scmutils есть автоматическая система дифференциации

http://groups.csail.mit.edu/mac/users/gjs/6946/linux-install.htm

(который по совпадению также выполняет символическое дифференцирование). Я не знаю других выпущенных реализаций, но вы можете проверить http://autodiff.org/.

Также есть хорошее объяснение того, как реализовать это самостоятельно, в приложении Структура и интерпретация классической механики.

http://mitpress.mit.edu/sicm/

а также в академической литературе. В частности, прямой режим не так уж и сложен, хотя вы должны быть осторожны, чтобы избежать путаницы. Вы можете проконсультироваться с публикациями Барака Перлмуттера и Джеффри Марка Сискинда, которые работают над высокопроизводительным вариантом Lisp, который включает AD, и публикуют публикации по сопутствующим вопросам.

http://scholar.google.com/scholar?q=Barak+Pearlmutter+and+Jeffrey+Mark+Siskind

person Gregory Marton    schedule 04.02.2011
comment
Спасибо! И последнее: не могли бы вы дать определение или дать ссылку на термин «путаница»? Я не знаком с этим термином. - person SuperElectric; 05.02.2011
comment
Хорошо, я сам нашел ответ из этой статьи: eprints.nuim.ie/archive/ 00000566/01 / Perturbation.pdf эти реализации (...) могут вычислять крайне неверные результаты, когда оператор дифференцирования применяется к функции, которая сама использует этот оператор. Основная причина этой проблемы - путаница возмущений, неспособность различить различные возмущения, вызванные различными вызовами оператора дифференцирования. Затем мы обсудим, как можно избежать путаницы, связанной с возмущением. - person SuperElectric; 06.02.2011

arrow_upward
3
arrow_downward

Если вам нужна символьная система, вы можете попробовать maxima (или здесь). Он работает на нескольких комбинациях платформ Common-Lisp / OS, но является скорее законченной системой, чем библиотекой.

Консольный вывод - это нормально, но он может давать довольно красивый вывод в сочетании с texmacs.

Maxima 5.23.2 http://maxima.sourceforge.net
using Lisp GNU Common Lisp (GCL) GCL 2.6.8 (a.k.a. GCL)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) diff(sin(1/x),x);
                                        1
                                     cos(-)
                                         x
(%o1)                              - ------
                                        2
                                       x

ИЗМЕНИТЬ

Хорошо, похоже, я неправильно понял вопрос. Немного погуглив, можно предположить, что в SCMUTILS есть несколько инструментов, здесь, загрузите здесь, руководство пользователя здесь (см. стр. 24 и далее).

person clstrfsck    schedule 03.02.2011
comment
Спасибо, но внешние инструменты для символической дифференциации - не то, что я ищу. Я отредактировал вопрос, чтобы прояснить это. - person SuperElectric; 04.02.2011
comment
Должна быть возможность использовать Maxima как библиотеку из любой распространенной программы lisp (и, следовательно, ее можно использовать изнутри макроса), так что в конце концов, это не так уж и важно. - person SK-logic; 04.02.2011
comment
Проблема в символичности. Я ищу макрос, который принимает функцию F и возвращает функцию F '. Я имею в виду вычисляемую функцию, которая принимает числовые аргументы, а не символьное выражение. - person SuperElectric; 29.12.2011

arrow_upward
2
arrow_downward

Может быть интересно, что scmutlis теперь перенесен на Clojure. Предстоит еще много работы, но код в первых главах книги SICM, похоже, работает нормально.

Процедуры и операторы дифференциации также кажутся нормальными для того небольшого тестирования, которое я провел, и даже в нем нет некоторых ошибок, которые, кажется, закрались в более поздние версии scmutils.

Я думаю, что scmutils покрывает требования OP к дифференциации, поскольку он будет правильно обрабатывать производные как известных, так и неизвестных (буквальных) функций. На этой странице приведены сведения, необходимые для проверки соответствия требованиям: SICM - Derivatives - Notation

Одним из преимуществ работы на JVM является то, что при необходимости она будет работать как автономная, даже не нужно устанавливать Clojure!

Он очень близок к исходной схеме, с минимальными уступками синтаксису Clojure.

Вы можете увидеть это здесь: https://github.com/littleredcomputer/sicmutils#sicmutils

===

Приложение: вот пример автоматического различения в пакете SicmUtils Clojure. Это типичный пример, распространяющийся на различных Интернет-сайтах. Код, который следует различать, выглядит следующим образом:

    function f(x)
      y = x;
      for i=1...100
        y = sin(x+y);
      return y

Немного изменив его с помощью Clojurification, мы получим

   > (defn inner [y] (fn[x] (sin (+ x y))))
   > (defn f100 [x] (nth (iterate (inner x) x) 100))
   ;; value of derivative at 6
   > ((D f100) 6)
    => 0.51603111348625
   ;; value of the 4th derivative at 1
   > (((expt D 4) f100) 1)
    => -1.7853200839806143
person Alex Gian    schedule 24.01.2016

arrow_upward
1
arrow_downward

Вот реализация AD в общем лиспе.

person sigfpe    schedule 28.04.2011

arrow_upward
1
arrow_downward

Стоит попробовать Deriva, которая выполняет автоматическое распознавание как для Clojure, так и для Java:

Вы также можете быть заинтересованы в expresso, который больше связан с манипуляциями с числовыми выражениями, но все же имеет некоторые функции дифференциации и, вероятно, может быть адаптирован для большинства случаев использования AD:

person mikera    schedule 04.11.2013

arrow_upward
-1
arrow_downward

Поищите в Google "символическое различие лиспа", и вы найдете множество примеров, например

http://mitpress.mit.edu/sicp/full-text/sicp/book/node39.html

person Curd    schedule 03.02.2011
comment
Я отредактировал вопрос, чтобы прояснить, почему эти примеры не совсем предоставляют все, что я ищу. - person SuperElectric; 04.02.2011