Реализация автоматического дифференцирования для 2-й производной: алгоритм обхода вычислительного графа?

Question

Я пытаюсь внедрить автоматическое дифференцирование для пакета статистики Python (формулировка задачи аналогична формулировке задачи оптимизации).

Вычислительный граф генерируется с использованием перегрузки операторов и фабричных функций для таких операций, как sum (), exp () и т. Д. Я реализовал автоматическое дифференцирование градиента с использованием обратного накопления. Тем не менее, я обнаружил, что внедрение автоматического дифференцирования для второй производной (гессиана) гораздо сложнее. Я знаю, как выполнять отдельные вычисления 2-го частичного градиента, но у меня возникли проблемы с поиском интеллектуального способа обхода графика и накопления. Кто-нибудь знает хорошие статьи, которые дают алгоритмы для автоматического дифференцирования для второй производной или библиотеки с открытым исходным кодом, которые реализуют то же самое, из чего я могу попытаться поучиться?

Answer 1

Сначала вы должны решить, хотите ли вы рассчитать разреженный гессиан или что-то ближе к полностью плотному гессиану.

Если вам нужен разреженный тип, в настоящее время есть два способа сделать это. Только используя вычислительный граф умным способом, за один оборот развертки вычислительного графа вы можете вычислить матрицу Гессиана, используя алгоритм edge_pushing:

http://www.tandfonline.com/doi/full/10.1080/10556788.2011.580098

Или вы можете попробовать методы раскраски графов, чтобы скомпоновать матрицу Гессе в матрицу из меньшего числа столбцов, а затем использовать обратное накопление для вычисления каждого столбца

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.66.2603

Если вам нужен плотный гессиан (необычно на практике), то вам, вероятно, лучше рассчитывать один столбец гессиана за раз, используя обратное накопление (поиск BRUCE CHRISTIANSON и обратное накопление)

Answer 2

Обычный метод аппроксимации гессиана в трех измерениях: BFGS

Метод L-BFGS аналогичен.

Здесь вы можете найти исходный код для L-BFGS (который вычисляет гессиан как промежуточный результат для решения ODE) на нескольких языках (C #, C ++, VBA и т. Д.), Хотя и не на питон. Я думаю, что это не легко перевести.

Если вы собираетесь перевести alg с другого языка, обратите особое внимание на числовые ошибки и проведите анализ чувствительности (вам нужно будет вычислить обратное значение матрицы Гессе)