5

这是在自动微分的背景下——这样的系统将如何处理类似的功能map,或者filter——甚至是SKI 组合器之一?

示例:我有以下功能:

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

它的衍生物是什么?AD 系统会产生什么结果?(此函数在实数输入上定义明确)。

4

3 回答 3

4

我不同意公认的答案,即您无法有效地区分更高等级的函数,或者您需要通过在实践中演示它来将自己限制在其中的一个特别小的子集。

使用我的 Haskell 'ad' 包,我们得到:

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

一般来说,自动微分对高阶函数没有问题。但是,根据特定工具的限制,源到源的翻译可能会遇到一些问题。

于 2012-06-26T02:35:42.350 回答
3

一个好的广告系统将毫无困难地轻松完成。如果 AD 代码执行源到源的翻译,那么sum. 但是,如果它是一个通过重载算术运算符来工作的 AD 系统,那么 AD 代码实际上不会“看到”sum函数,而只是函数调用的+操作。sum

于 2010-04-30T19:14:16.997 回答
1

高阶函数是离散的。它们不具有笛卡尔的质量,即具有对某些 n 维空间中的点具有明确定义的映射的参数。

但是,随着您对答案的澄清,可以说几件事。符号区分一些高阶函数是可能的,但仅适用于解析为众所周知的函数的某些调用模式。

可能数值微分会更有成效,因为它可以通过重复评估给定函数来估计导数。

此外,完全通用的函数——你的例子正朝着这个方向发展,使用相对任意的函数——最终你会达到图灵完备性,这意味着符号微分器的任何聪明之处都无法自动区分功能。

于 2008-11-26T15:28:29.883 回答