Автоматическое дифференцирование по Гессе

В прикладной математике автоматическое дифференцирование по Гессе — это методы, основанные на автоматическом дифференцировании (AD).которые вычисляют вторую производную $n$-мерная функция, известная как матрица Гессе .

При исследовании функции в окрестности точки можно отбросить многие сложные глобальные аспекты функции и точно аппроксимировать ее более простыми функциями. Квадратичная аппроксимация является наиболее подходящим квадратичным приближением в окрестности точки и часто используется в технике и науке. Для расчета квадратичного приближения необходимо сначала вычислить его градиент и матрицу Гессе.

Позволять $f:\mathbb {R} ^{n}\rightarrow \mathbb {R}$, для каждого $x\in \mathbb {R} ^{n}$ матрица Гессе $H(x)\in \mathbb {R} ^{n\times n}$ является производной второго порядка и является симметричной матрицей.

Обратные векторные произведения Гессе

Для данного $u\in \mathbb {R} ^{n}$, этот метод эффективно вычисляет произведение вектора Гессе $H(x)u$. Таким образом, его можно использовать для расчета всего гессиана путем расчета $H(x)e_{i}$, для $i=1,\ldots ,n$.

Этот метод работает, сначала используя прямой AD для выполнения $f(x)\rightarrow u^{T}\nabla f(x)$, впоследствии метод вычисляет градиент $u^{T}\nabla f(x)$ использование Reverse AD для получения $\nabla \left(u\cdot \nabla f(x)\right)=u^{T}H(x)=(H(x)u)^{T}$. Оба этих двух шага требуют временных затрат, пропорциональных оценке функции, поэтому весь гессиан может быть оценен по затратам, пропорциональным n оценок функции.

Обратный гессиан: Edge_Pushing

Алгоритм, который вычисляет весь гессиан с помощью одного прямого и одного обратного прохода вычислительного графа, называется Edge_Pushing. Edge_Pushing — это результат применения обратного градиента к вычислительному графу градиента. Естественно, этот граф имеет n выходных узлов, поэтому в некотором смысле необходимо применить метод обратного градиента к каждому исходящему узлу. Edge_Pushing делает это, принимая во внимание перекрывающиеся вычисления.

Пример выполнения Edge_Pushing

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

Методы раскраски графов для гессенцев

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

1. Получите глобальную картину разреженности $H$
2. Примените алгоритм раскраски графа, который позволяет нам сжать структуру разреженности.
3. Для каждой желаемой точки $x\in \mathbb {R} ^{n}$ вычислить числовые элементы компактной матрицы.
4. Восстановите матрицу Гессе из компактной матрицы.

Первый и второй шаги необходимо выполнить только один раз, и они, как правило, являются дорогостоящими. Если нужно вычислить гессиан в нескольких точках (например, в программе оптимизации), шаги 3 и 4 повторяются.

Цветная разреженность матрицы Гессе

Компактная матрица Гессе

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

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