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

Question

我正在研究我的下一个项目.这是一个预先规划阶段,所以这个问题只是为了对现有技术进行概述.

建立

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

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

现在我处于幸运的位置,我有一个事件流,每个事件都在一个输入节点中呈现变化.我的想法是,如果我可以静态地知道给定的更改只会影响其中的一部分,我可能不需要步进网络中的每个节点.

例

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

目标

以尽可能小的延迟处理这种网络.图形的大小可能达到100k节点,每个节点进行适量的计算.

计划

我希望有人会站出来宣传图书馆X,只是完成工作.

否则,我当前的计划是从图形描述中导出每个输入节点的计算.可能我会使用Parmonad,这样我就不必自己处理数据依赖,仍然可以从多核机器中受益.

问题

• 是否有任何图书馆可以满足我的需求？
• 我的Par计划可行吗？这取决于每个节点所需的处理量？

Answer 1

像这样的问题通常是针对一个Applicative或Arrow抽象编码的.我只会讨论Applicative.Applicative找到的类型类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

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

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

可以通过遍历图形从图形的表示以编程方式创建相同的编码,使得在其所有依赖性之后将访问每个节点.

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

可观察的分享

在前面的示例中,中间节点eleven仅定义一次,但在三个不同的位置使用.一个实现Applicative将无法透过引用透明度来看到这三个eleven是完全相同的.您可以假设实现使用一些IO魔术来查看引用透明度或定义网络,以便实现可以看到正在重用计算.

以下是Applicative Functors 的类,其中计算的结果可以被划分并在多次计算中重用.在我所知道的任何地方都没有在库中定义此类.

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

infixl 2 </>

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

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加法和减法可以在任意分组中执行,并且仍然可以达到相同的结果.当我们减去旧值并将新值添加到总值时,即使在添加的中间某处添加了旧值,这也可以使我们达到相同的结果.

任何具有这些属性以及闭包和身份的结构都是阿贝尔群.以下字典包含底层库的足够信息以执行相同的优化

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