在Haskell中表示计算图

Question

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

有什么高效的方式可以在Haskell中表示类型安全（有向）计算图？我知道ad包使用"data-reify"方法，但我不太熟悉它。有人能提供一些见解吗？谢谢！

- thoughtpolice

---

请见http://conal.net/papers/compiling-to-categories/。 - Will Ness

Answer 1

正如Will Ness的评论所指出的，自动微分（AD）的正确抽象是一个范畴，而不是一个图。不幸的是，标准的Category class并不真正起作用，因为它需要在任何 Haskell 类型之间添加箭头，但微分只有在平滑流形之间才有意义。大多数库都不知道流形，并将其进一步限制为欧几里得向量空间（它们表示为“向量”或“张量”，即数组）。实际上，没有令人信服的理由去这么严格 - 任何仿射空间都可以用于正向模式AD；对于反向模式，您还需要了解对偶空间的概念来区分向量。

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

在反向模式中，Diff x -> Diff y函数必须是线性函数（您可以使用专门的箭头类型来表示这种函数，或者只是使用本质上是线性的(->)函数）。唯一不同的是，在反向模式中，此线性映射的伴随被表示，而不是映射本身。（在实值矩阵实现中，线性映射是Jacobian矩阵，其伴随版本是其转置，但不要使用矩阵，因为它们对此非常低效。）
很整洁，对吧？所有那些人们一直谈论的图形/遍历/变异/反向传递的废话实际上并不需要。（有关详细信息，请参见Conal的论文。）

因此，要在Haskell中使用这个实用程序，您需要实现范畴组合器。这就是我编写constrained-categories package的原因。以下是所需内容的概述：

import qualified Prelude as Hask
import Control.Category.Constrained.Prelude
import Control.Arrow.Constrained
import Data.AffineSpace
import Data.AdditiveGroup
import Data.VectorSpace

instance Category FwAD where
  type Object FwAD a
     = (AffineSpace a, VectorSpace (Diff a), Scalar (Diff a) ~ Double)
  id = FwAD $ \x -> (x, id)
  FwAD f . FwAD g = FwAD $ \x -> case g x of
     (gx, dg) -> case f gx of
       (fgx, df) -> (fgx, df . dg)

instance Cartesian FwAD where
  ...
instance Morphism FwAD where
  ...
instance PreArrow FwAD where
  ...
instance WellPointed FwAD where
  ...

这些实例都很简单几乎没有歧义，让编译器消息指引你（类型空白 _ 非常有用）。基本上，每当需要作用域内的类型变量时，请使用它；每当需要不在作用域内的向量空间类型变量时，请使用 zeroV。

到那时，您将真正拥有所有基本的可微函数工具，但要实际定义这样的函数，您需要使用无点风格，大量使用 .、&&& 和 *** 组合器以及硬编码数字原语，看起来不太常规且相当令人困惑。为了避免这种情况，您可以使用 代理值：这些值基本上假装是简单的数字变量，但实际上包含某个固定域类型的整个类别箭头。 （这基本上是练习中“构建图形”的部分。）您可以简单地使用提供的 GenericAgent 包装器。

instance HasAgent FwAD where
  type AgentVal FwAD a v = GenericAgent FwAD a v
  alg = genericAlg
  ($~) = genericAgentMap

instance CartesianAgent FwAD where
  alg1to2 = genericAlg1to2
  alg2to1 = genericAlg2to1
  alg2to2 = genericAlg2to2

instance PointAgent (GenericAgent FwAD) FwAD a x where
  point = genericPoint

instance ( Num v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
         , Scalar a ~ v )
      => Num (GenericAgent FwAD a v) where
  fromInteger = point . fromInteger
  (+) = genericAgentCombine . FwAD $ \(x,y) -> (x+y, \(dx,dy) -> dx+dy)
  (*) = genericAgentCombine . FwAD $ \(x,y) -> (x*y, \(dx,dy) -> y*dx+x*dy)
  abs = genericAgentMap . FwAD $ \x -> (abs x, \dx -> if x<0 then -dx else dx)
  ...
instance ( Fractional v, AffineSpace v, Diff v ~ v, VectorSpace v, Scalar v ~ v
         , Scalar a ~ v )
      => Fractional (GenericAgent FwAD a v) where
  ...
instance (...) => Floating (...) where
  ...

如果您已经完成了所有这些实例，并且可能有一个简单的助手来提取结果。

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

然后你可以编写如下代码

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

在底层，这些代数表达式通过与&&&“拆分”数据流并***并行组成FwAD箭头的组合，即使输入和最终结果是简单的Double，中间结果也将被拉入适当的元组类型。[我想，那可能就是你标题问题的答案：有向图在某种意义上被表示为一个分支组合链，原则上与你在 Arrow的图解释中发现的是一样的。]

- leftaroundabout

---

这个 “Agent” 的想法是你自己的，还是我可以在文献中读到更多相关内容，也许是用不同的名称？ - Josh.F

它受到Conal Elliott早期工作的强烈启发，该工作在编译成类别论文中进行了总结。基本上，这个想法是希望将那些CCC表达式写成lambda形式，但只使用现有的Haskell工具。我认为它也与Yoneda / Coyoneda机制密切相关，但我从来没有完全弄清楚... - leftaroundabout