автомат c дифференцирование вектор-якобиевых произведений в линейное время?

Question

Я новичок во внутренней работе автоматического дифференцирования c и наткнулся на некоторые статьи и слайды, в которых утверждается, что векторные якобианские произведения могут быть вычислены за линейное время с использованием автоматического дифференцирования c. Специально написано:

$e^\top ( \frac{\partial f}{\partial x} )$ 

может быть вычислено для любого e в O(N). Якобиан N-by-N. Я бы подумал, что это N^2, но я не до конца понимаю, как автоматическое дифференцирование c может уменьшить сложность времени.

Answer 1

Если у вас есть базовое предположение, что скрытое пространство фиксировано, то оно линейно. Предположим, что ваша функция f представляет собой композицию матричных преобразований, где фиксированная матрица f1 является H-by-N, f2 является H-by-H, а f3 является N-by-H. Тогда для N-мерного вектора e мы можем вычислить вычисление как f1 * e, затем применить f2, затем применить f3. Это линейно масштабируется с N, но не со скрытым пространством H.