Производная функции высшего порядка

Question

Это в контексте Автоматическое дифференцирование - что будет делать такая система с такой функцией, как map или filter - или даже с одним из SKI Combinators

Пример: у меня есть следующая функция:

def func(x):
    return sum(map(lambda a: a**x, range(20)))

Каким будет его производное? Что в результате даст система AD? (Эта функция четко определена на входах действительных чисел).

Answer 1

Хорошая система AD пройдет без проблем. Если код AD выполняет преобразование исходного кода в исходное, то могут возникнуть проблемы с sum. Но если это система AD, которая работает с перегрузкой арифметических операторов, тогда код AD на самом деле не «видит» функцию sum, а только операции +, которые вызывает функция sum.

Answer 2

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

Используя мой пакет объявлений 'Haskell', мы получаем:

ghci> :m + Numeric.AD
ghci> diff (\x -> sum (map (**x) [1..20])) 10
7.073726805128313e13

Мы можем извлечь то, что было сделано, злоупотребив отслеживаемым числовым типом, чтобы ответить на ваш вопрос о производной:

ghci> :m + Debug.Traced
ghci> putStrLn $ showAsExp $ diff (\x -> sum (map (**x) [1..20])) (unknown "x" :: Traced Double) 
1.0 * (1.0 ** x * log 1.0) + 
1.0 * (2.0 ** x * log 2.0) +
1.0 * (3.0 ** x * log 3.0) +
1.0 * (4.0 ** x * log 4.0) +
1.0 * (5.0 ** x * log 5.0) +
1.0 * (6.0 ** x * log 6.0) +
1.0 * (7.0 ** x * log 7.0) +
1.0 * (8.0 ** x * log 8.0) +
1.0 * (9.0 ** x * log 9.0) +
1.0 * (10.0 ** x * log 10.0) +
1.0 * (11.0 ** x * log 11.0) +
1.0 * (12.0 ** x * log 12.0) +
1.0 * (13.0 ** x * log 13.0) +
1.0 * (14.0 ** x * log 14.0) +
1.0 * (15.0 ** x * log 15.0) +
1.0 * (16.0 ** x * log 16.0) +
1.0 * (17.0 ** x * log 17.0) +
1.0 * (18.0 ** x * log 18.0) +
1.0 * (19.0 ** x * log 19.0) +
1.0 * (20.0 ** x * log 20.0)

При полном совместном использовании вы получаете довольно ужасные результаты, которые иногда асимптотически более эффективны.

ghci> putStrLn $ showAsExp $ reShare $ diff (\x -> sum (map (**x) [1..20])) 
      (unknown "x" :: Traced Double)
let _21 = 1.0 ** x;
    _23 = log 1.0;
    _20 = _21 * _23;
    _19 = 1.0 * _20;
    _26 = 2.0 ** x;
    _27 = log 2.0;
    _25 = _26 * _27;
    _24 = 1.0 * _25;
    _18 = _19 + _24;
    _30 = 3.0 ** x;
    _31 = log 3.0;
    _29 = _30 * _31;
    _28 = 1.0 * _29;
    _17 = _18 + _28;
    _34 = 4.0 ** x;
    _35 = log 4.0;
    _33 = _34 * _35;
    _32 = 1.0 * _33;
    _16 = _17 + _32;
    _38 = 5.0 ** x;
    _39 = log 5.0;
    _37 = _38 * _39;
    _36 = 1.0 * _37;
    _15 = _16 + _36;
    _42 = 6.0 ** x;
    _43 = log 6.0;
    _41 = _42 * _43;
    _40 = 1.0 * _41;
    _14 = _15 + _40;
    _46 = 7.0 ** x;
    _47 = log 7.0;
    _45 = _46 * _47;
    _44 = 1.0 * _45;
    _13 = _14 + _44;
    _50 = 8.0 ** x;
    _51 = log 8.0;
    _49 = _50 * _51;
    _48 = 1.0 * _49;
    _12 = _13 + _48;
    _54 = 9.0 ** x;
    _55 = log 9.0;
    _53 = _54 * _55;
    _52 = 1.0 * _53;
    _11 = _12 + _52;
    _58 = 10.0 ** x;
    _59 = log 10.0;
    _57 = _58 * _59;
    _56 = 1.0 * _57;
    _10 = _11 + _56;
    _62 = 11.0 ** x;
    _63 = log 11.0;
    _61 = _62 * _63;
    _60 = 1.0 * _61;
    _9 = _10 + _60;
    _66 = 12.0 ** x;
    _67 = log 12.0;
    _65 = _66 * _67;
    _64 = 1.0 * _65;
    _8 = _9 + _64;
    _70 = 13.0 ** x;
    _71 = log 13.0;
    _69 = _70 * _71;
    _68 = 1.0 * _69;
    _7 = _8 + _68;
    _74 = 14.0 ** x;
    _75 = log 14.0;
    _73 = _74 * _75;
    _72 = 1.0 * _73;
    _6 = _7 + _72;
    _78 = 15.0 ** x;
    _79 = log 15.0;
    _77 = _78 * _79;
    _76 = 1.0 * _77;
    _5 = _6 + _76;
    _82 = 16.0 ** x;
    _83 = log 16.0;
    _81 = _82 * _83;
    _80 = 1.0 * _81;
    _4 = _5 + _80;
    _86 = 17.0 ** x;
    _87 = log 17.0;
    _85 = _86 * _87;
    _84 = 1.0 * _85;
    _3 = _4 + _84;
    _90 = 18.0 ** x;
    _91 = log 18.0;
    _89 = _90 * _91;
    _88 = 1.0 * _89;
    _2 = _3 + _88;
    _94 = 19.0 ** x;
    _95 = log 19.0;
    _93 = _94 * _95;
    _92 = 1.0 * _93;
    _1 = _2 + _92;
    _98 = 20.0 ** x;
    _99 = log 20.0;
    _97 = _98 * _99;
    _96 = 1.0 * _97;
    _0 = _1 + _96;
in  _0

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

Answer 3

Функции высшего порядка являются дискретными. Они не обладают декартовым качеством наличия аргументов, которые имеют четко определенные отображения на точки в некотором n-мерном пространстве.

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

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

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