logo标签列表

函数式编程中的大数据结构

functional-programming
13

我是函数式编程的新手。

我有一个数千个神经元的大型神经网络，每个神经元之间的连接都有其权重。我需要经常更新这些权重，每次学习会话中要进行数千次更新。

函数式编程在这里仍然适用吗？我的意思是，在函数式编程中，我们不能修改变量，只能返回新变量而不能改变先前的值。这是否意味着我必须在每次权重更新时重新创建整个网络？

4个回答
18

函数式编程在这里是否仍然适用？

你可以使用函数式风格编写具有良好渐进算法效率的代码，但是你不太可能获得10倍于良好命令式解决方案的性能，因为纯粹的函数式编程使得难以有效利用CPU缓存。

我的意思是，在fp中我们不能修改变量，只能返回新变量而不能更改先前的值。 这是否意味着我必须在每次权重更新时重新创建整个网络？

不需要，由于以下两个原因：

  1. 纯函数式数据结构可以高效地进行更新，因为它们将大型结构（例如哈希表）分解为许多小递归定义的结构（例如平衡二叉树）。当您更新不可变树中的单个节点时，您会从根到目标路径上的每个节点复制数据，但通过引用回到所有其他分支安全地知道它们在您下面不能更改，因为它们是不可变的。因此，您只需要做O（log n）的工作而不是O（n）的工作。

  2. 纯函数式数据结构通常提供像map这样的函数，允许以相同的方式更新每个元素并通过复制源树的结构而避免重新平衡。因此，n次更新的时间为O（n），而不是O（n log n ）。

因此，您应该能够实现类似或甚至相等的渐进时间复杂度，但是在绝对意义上，您将使用比命令式解决方案多几倍的空间和时间。我在我的书《Visual F# 2010 技术计算》中详细介绍了这些基础知识，并为OCaml Journal写了一篇名为人工智能：神经网络（2010年5月8日）的文章。

2

了解一下Haskell数组，其中包括在单子中可变的变体。

1

每次权重更新时，您不需要重新创建整个网络。假设您的神经元被建模为单独的对象-这意味着要“更新”一个单独的神经元，实际上是创建一个具有更新权重的新神经元。然后，将该神经元插入到网络中以替换旧神经元，而旧神经元则可以由垃圾回收器进行回收。

我不同意使用可变状态的想法。函数式语言知道它们是函数式的，因此它们对函数式编程进行了优化。如果函数式语言确实是最适合工作的工具，那么应该充分利用其优势。

假设我有一个简单的树： 根 |
节点1 节点2 那么如果我创建节点3并用节点3替换节点1，这不意味着我正在改变整棵树吗？ - Denis Gorodetskiy
你的例子有两个问题。首先，你的帖子问的是每次权重更新是否需要重新创建整个网络，而不是它是否“改变”。我在我的回答中解决了这个问题。其次，你把它变得足够小，以至于每个节点都有一些变化。相反，想象一下你有一个由1000个节点组成的网络，只有一个节点需要被替换。你还会改变整棵树吗？ - danben
你的话“然后这个神经元将被插入到网络中取代旧的那个”并不意味着神经网络实际上发生了变化吗？我的意思是，部分替换整体——这不是一个变量的改变（在这种情况下是神经网络）吗？ - Denis Gorodetskiy
试着将神经网络看作是一组实体（节点），而不是单个实体。 - danben
1

如果您以这样的方式构建数据，即可以使用持久化数据结构来模拟神经网络，则对神经网络进行功能更新将会很便宜（至少与整个复制相比如此）。

如果速度仍然不够快，您的编程语言可能允许其他技术（例如谨慎使用变异）来加速；例如，如果您正在使用Clojure，则可以使用transients来实现一些额外的速度。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接