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

Question

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

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

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

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

Используя мой пакет 'ad' для 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

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