用 Haskell 表示计算图

Question

我正在尝试用 Haskell 编写一个简单的自动微分包。

在 Haskell 中表示类型安全（有向）计算图的有效方法是什么？我知道广告包使用“data-reify”方法，但我不太熟悉它。谁能为我提供一些见解？谢谢！

Answer 1

正如 Will Ness 的评论所指出的，AD 的正确抽象是类别，而不是图表。不幸的是，标准Category类并没有真正做到这一点，因为它需要任何Haskell 类型之间的箭头，但微分仅在平滑流形之间才有意义。大多数库不了解流形，并将其进一步限制为欧几里得向量空间（它们表示为 \xe2\x80\x9cvectors\xe2\x80\x9d 或 \xe2\x80\x9ctensors\xe2\x80\x9d ，它们只是数组）。确实没有令人信服的理由来限制\xe2\x80\x93 任何仿射空间都适用于前向模式 AD；对于反向模式，您还需要差分向量的对偶空间的概念。

\n

data FwAD x y = FwAD (x -> (y, Diff x -> Diff y))\ndata RvAD x y = RvAD (x -> (y, DualVector (Diff y) -> DualVector (Diff x)))\n

\n

其中Diff x -> Diff y函数必须是线性函数。（您可以为此类函数使用专用的箭头类型，或者您可以只使用(->)恰好是线性的函数。）反向模式中唯一不同的是，表示了该线性映射的伴随，而不是地图本身。（在实值矩阵实现中，线性映射是雅可比矩阵及其转置的伴随版本，但不要使用矩阵，它们对此效率非常低。）\n 很
整洁，对吧？人们一直在谈论的所有图形/遍历/变异/向后传递的废话并不是真正需要的。（详细说明请参阅Conal 的论文。）

\n

因此，要使其在 Haskell 中有用，您需要实现类别组合器。这几乎正​​是我编写constrained-categories 包的目的。这是您需要的概要实例：

\n

import qualified Prelude as Hask\nimport Control.Category.Constrained.Prelude\nimport Control.Arrow.Constrained\nimport Data.AffineSpace\nimport Data.AdditiveGroup\nimport Data.VectorSpace\n\ninstance Category FwAD where\n  type Object FwAD a\n     = (AffineSpace a, VectorSpace (Diff a), Scalar (Diff a) ~ Double)\n  id = FwAD $ \\x -> (x, id)\n  FwAD f . FwAD g = FwAD $ \\x -> case g x of\n     (gx, dg) -> case f gx of\n       (fgx, df) -> (fgx, df . dg)\n\ninstance Cartesian FwAD where\n  ...\ninstance Morphism FwAD where\n  ...\ninstance PreArrow FwAD where\n  ...\ninstance WellPointed FwAD where\n  ...\n

\n

这些实例都很简单，几乎不含糊，让编译器消息指导您（类型化的漏洞 _非常有用）。基本上，只要需要范围内类型的变量，就使用它；当需要不在范围内的向量空间类型的变量时，请使用zeroV.

\n

那时，您将真正拥有所有基本的可微函数工具，但要实际定义此类函数，您需要使用带有大量.、&&&和***组合器以及硬编码数值基元的无点样式，这看起来非常规且相当混乱。为了避免这种情况，您可以使用代理值：基本上伪装成简单数字变量的值，但实际上包含来自某些固定域类型的整个类别箭头。（这基本上是练习的 \xe2\x80\x9c 构建图形 \xe2\x80\x9d 部分。）您可以简单地使用提供的GenericAgent包装器。

\n

instance HasAgent FwAD where\n  type AgentVal FwAD a v = GenericAgent FwAD a v\n  alg = genericAlg\n  ($~) = genericAgentMap\n\ninstance CartesianAgent FwAD where\n  alg1to2 = genericAlg1to2\n  alg2to1 = genericAlg2to1\n  alg2to2 = genericAlg2to2\n\ninstance PointAgent (GenericAgent FwAD) FwAD a x where\n  point = genericPoint\n\ninstance ( Num v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v\n         , Scalar a ~ v )\n      => Num (GenericAgent FwAD a v) where\n  fromInteger = point . fromInteger\n  (+) = genericAgentCombine . FwAD $ \\(x,y) -> (x+y, \\(dx,dy) -> dx+dy)\n  (*) = genericAgentCombine . FwAD $ \\(x,y) -> (x*y, \\(dx,dy) -> y*dx+x*dy)\n  abs = genericAgentMap . FwAD $ \\x -> (abs x, \\dx -> if x<0 then -dx else dx)\n  ...\ninstance ( Fractional v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v\n         , Scalar a ~ v )\n      => Fractional (GenericAgent FwAD a v) where\n  ...\ninstance (...) => Floating (...) where\n  ...\n

\n

如果您已完成所有这些实例，也许还有一个简单的帮助程序来提取结果

\n

evalWithGrad :: FwAD Double Double -> Double -> (Double, Double)\nevalWithGrad (FwAD f) x = case f x of\n   (fx, df) -> (fx, df 1)\n

\n

然后你可以编写如下代码

\n

> evalWithGrad (alg (\\x -> x^2 + x) 3)\n(12.0, 7.0)\n> evalWithGrad (alg sin 0)\n(0.0, 1.0)\n

\n

FwAD在底层，这些代数表达式用&&&\xe2\x80\x9csplitting\xe2\x80\x9d构建了箭头的组合，数据流并***并行组合，即即使输入和最终结果很简单，Double中间结果也将是通过合适的元组类型拉取。[我想，这就是您标题问题的答案：有向图在某种意义上表示为分支组合链，原则上与您在s的图表解释中找到的内容相同Arrow中找到的内容相同。]

\n