代码之家 › 专栏 › 技术社区 › fho

如何从有向非循环图导出FRP?

frp directed-acyclic-graphs haskell

13

fho · 技术社区 · 10 年前

我目前正在研究我的下一个项目。这是一个预先规划阶段,所以这个问题只是为了了解现有技术的概况。

安装程序

我有一个具有多个输入和输出的有向无环图(DAG),现在想想人工神经网络:

Directed acyclic graph

处理这种结构的常见方法是在每个(时间)步骤上处理整个网络。我相信这是frp库使用的方法,例如 netwire .

现在,我处于一个幸运的位置,我有一系列的事件,每一件都呈现了一输入节点的。这个想法是,如果我可以静态地知道给定的更改只会影响网络的一部分,那么我可能不必对网络中的每个节点进行分级。

实例

在上面的图像中,5、7和3是输入,11和8是“隐藏”的,2、9和10是输出节点。节点5处的改变将仅影响节点11,并且实际上影响节点2、9和10。我不需要处理节点7、3和8。

目标

以尽可能少的延迟处理此类网络。图形的大小可能会达到100k个节点,每个节点的计算量适中。

计划

我希望有人会站出来,为X库做广告,让它完成这项工作。

否则,我当前的计划是从图形描述中导出每个输入节点的计算。也许我会用 Par monad,这样我就不必自己处理数据依赖性,而且还能从多核机器中获益。

问题

有没有图书馆能满足我的需要?
是我的 标准杆数 计划是否可行?这在多大程度上取决于每个节点所需的处理量?

1 回复 | 直到 10 年前

1

9

Community CDub 7 年前

此类问题通常针对 Applicative 或 Arrow 抽象。我只讨论 适用的 这个 适用的 类型类,在中找到 Control.Applicative ,允许通过 pure 和应用于值的函数 <*> .

class Functor f => Applicative f where
    -- | Lift a value.
    pure :: a -> f a

    -- | Sequential application.
    (<*>) :: f (a -> b) -> f a -> f b

您的示例图可以非常简单地编码为 适用的 (用加法替换每个节点)为

example1 :: (Applicative f, Num a) => f a -> f a -> f a -> f (a, a, a)
example1 five seven three = 
    let
        eleven = pure (+) <*> five   <*> seven
        eight  = pure (+) <*> seven  <*> three
        two    = pure id  <*> eleven
        nine   = pure (+) <*> eleven <*> eight
        ten    = pure (+) <*> eleven <*> three
    in
        pure (,,) <*> two <*> nine <*> ten

通过遍历图,可以从图的表示中以编程方式创建相同的编码,以便在所有依赖项之后访问每个节点。

对于仅使用编码的网络,可能需要三种无法实现的优化 适用的 。一般策略是根据 适用的 以及优化或额外功能所需的一些附加类。然后提供一个或多个实现必要类的解释器。这使您可以将问题与实现分开,允许您编写自己的解释器或使用现有的库,如 reactive , reactive-banana 或 mvc-updates 。我不打算讨论如何编写这些口译员或将此处给出的表述改编为特定的口译员。我只讨论程序的通用表示,这是底层解释器能够利用这些优化所需的。我链接的所有三个库都可以避免重新计算值,并且可以适应以下优化。

可观的共享

在前面的示例中,中间节点 eleven 仅定义一次,但在三个不同的地方使用。实现 适用的 将无法透过参考透明度看到这三个 十一 s都是一样的。您可以假设实现使用一些 IO magic to peek through referential transparency 或者定义网络,以便实现可以看到正在重用计算。

以下是 适用的 Functor 其中计算结果可以被分割并在多个计算中重复使用。我所知道的任何地方都没有在库中定义这个类。

class Applicative f => Divisible f where
    (</>) :: f a -> (f a -> f b) -> f b

infixl 2 </>

然后,您的示例可以非常简单地编码为 Divisible 函数 像

example2 :: (Divisible f, Num a) => f a -> f a -> f a -> f (a, a, a)
example2 five seven three = 
    pure (+) <*> five   <*> seven </> \eleven ->
    pure (+) <*> seven  <*> three </> \eight  ->
    pure id  <*> eleven           </> \two    ->
    pure (+) <*> eleven <*> eight </> \nine   ->
    pure (+) <*> eleven <*> three </> \ten    ->
    pure (,,) <*> two <*> nine <*> ten

和与阿贝尔群

典型的神经元计算其输入的加权和,并将响应函数应用于该和。对于一个度数较大的神经元来说,将其所有输入相加是非常耗时的。更新和的一个简单优化是减去旧值并添加新值。这利用了加法的三个财产:

相反的 - a * b * bâ»Â¹ = a 减法是加法的逆运算,这个逆运算允许我们从总数中删除之前相加的数字

交换性 - a * b = b * a 无论执行加法和减法的顺序如何,它们都会达到相同的结果。这样,即使旧值不是最近添加的值,当我们减去旧值并将新值添加到总值时,也会达到相同结果。

关联性 - a * (b * c) = (a * b) * c 可以在任意分组中执行加法和减法,并且仍然可以获得相同的结果。这使我们在减去旧值并将新值添加到总值时可以获得相同的结果,即使旧值是在添加的中间添加的。

任何具有这些财产、闭包和标识的结构都是 Abelian group 。下面的字典为基础库保存了足够的信息以执行相同的优化

data Abelian a = Abelian {
    id  :: a,
    inv :: a -> a,
    op  :: a -> a -> a
}

这是一类可以对阿贝尔群求和的结构

class Total f where 
    total :: Abelian a -> [f a] -> f a

类似的优化对于地图的构建也是可能的。

阈值和相等

神经网络中的另一个典型操作是将值与阈值进行比较,并完全基于该值是否超过阈值来确定响应。如果对输入的更新没有改变值落在阈值的哪一侧,则响应不会改变。如果响应没有改变,就没有理由重新计算所有下游节点。检测阈值没有变化的能力 Bool 或者响应是相等的。以下是一类可以利用平等的结构。 stabilize 提供 Eq 实例映射到基础结构。

class Stabilizes f where
    stabilize :: Eq a => f a -> f a