算法与理论计算机2016arxiv.org
编程空间上的算子演算与广义张量网络
Operational calculus on programming spaces and generalized tensor networks
专业 · 约 90 分钟读完前置知识：自动微分、抽象代数、程序语义
导读
这篇论文提出在“程序空间”上建立运算微积分：把程序视为向量空间上的映射，为程序定义微分，并试图用良定义的代数统一自动微分、高阶导数与程序复合。论文进一步引入“神经张量级数”等构造，将程序与广义张量网络关联，用于程序分析和张量网络的初始化/训练。整体偏形式化，HN 讨论中不少读者认为难以落地、缺少具体例子。
HN 关注点：能否把自动微分从算法技巧提升为程序代数/微积分，并用于程序分析与张量网络训练；但论文艰深、缺少可操作示例，讨论集中在实际应用和语义难点。
HN 评论精选
这几条评论里：支持 2 质疑 1 补充 1
支持发帖人概括论文：为程序建立可微代数，扩展 AD 并免费获得高阶导与复合，潜在可推广神经网络中的手工结构。
我是发帖人。这篇论文很密，涉及抽象代数、张量、自动机等很多概念，我远没有完全理解。主要点似乎是：实现程序与向量空间上映射的对偶（简化到实数域）；为这些程序定义微分；用良定义的代数扩展当前自动微分方法，而不是只把链式法则做成前向/反向传播算法；微分算子良定义后，高阶导数和可微程序的复合可“免费”得到。我认为这种形式化很有潜力，可推广目前神经网络中需要手工打造的控制结构、递归和复合。
hcarvalhoalves查看英文原文
OP here. This is a dense paper since it involves many concepts (abstract algebras, tensors, automata) and I don't fully grok it (not even close). The main points seem to be: - Realization of the duality between programs and maps over vector space (simplification: assumes the real field). - Define differentiation for those programs. - Expand over current automatic differentiation approaches by having a well defined algebra, as opposed to a pure algorithmic translation of the chain rule by forward/backward propagation. - Since the differentiation operator is well defined, get higher-order derivatives "for free" . - Also, get composition of differentiable programs "for free". This formalization seem to have a lot of potential IMO by allowing generalization of techniques researchers have to currently "hand craft" in neural networks (control structures, recursion, composition).
支持细读者认为核心是用微积分做程序分析，并以“神经张量级数”把程序与张量网络关联、初始化和训练。
我花了几小时读这篇论文。按我的理解，它不只是讲自动微分（AD 只是“高效计算导数的手段”），而是用微积分做程序分析。论文展示如何用程序建立方程并像普通数学那样运算，这也是构造代数的原因；还推导出某种类似傅里叶的变换（我还没完全懂，论文也用这套代数推广 Deep Dream 之类方法）。他们展示如何用该代数从某个次优程序初始化“张量网络”，再训练得到比原程序更好的结果；这个变换叫“神经张量级数”，像是程序的增强版泰勒级数。我能理解的是，它通过该变换把程序与张量网络关联起来，从而互相分析和研究。这个代数让我觉得有趣且重要；他们提到与物理学研究的类比：物理中常把系统表达为方程组的解，因为事先不知道系统，而这里程序也像一个系统。
m_hack查看英文原文
I spent the last few hours reading this paper. From what I understand, the paper is not about AD, but something more. AD is "efficient means to calculating derivatives", as they put it. This paper seems to be about program analysis through calculus (AD comes into play, as derivatives are needed). They show how to form equations with programs and calculate with them, kind of like with "normal" math. This seems to be the reason for constructing the algebra. They derive some transformation of programs similar to Fouriers I do not fully understand yet (they also use this algebra and calculus to generalize methods like Deep Dream). They show how to use this algebra to initialize "tensor networks" from some other sub-optimal program and than train it to obtain better results than the original program. The transformation is called "Neural tensor series", it seems to be like an enhanced Taylor series for programs, but again, I do not fully understand it yet. What I do understand from it, is that through this transformation you can somehow relate a program to a tensor network, and use this to study and analyze programs and vice versa. This algebra strikes me as interesting and important. They mention parallels to how physics is being studied. In physics, you often express a system as a solution to a system of equations, because you do not know the system in advance. In this frame, a program is like a system. Perhaps this theory allows a similar approach to programming. There is another paper listed on github https://arxiv.org/abs/1612.02731 . It seems as though the code on github and this paper are additional material to the paper in the OP, not a full implementation of the theory, but a bridge for those familiar with AD to better understand the theory in the paper. I could be wrong though, it is getting late :)
质疑要求给出阶乘求导/伽马函数这样的具体例子，并质疑递归和非数值数据如何处理。
以常见方式（递归或迭代）定义阶乘函数，用这篇论文怎么对它求导？也会神奇地得到伽马函数吗？我只是略读，远没找到答案——已经理解的人能否用这个具体例子解释一下？我今年早些时候用朴素方式想过：常见的 if-then-else 表达式至少在处理数字时是线性插值的特例（在 a、b 之间按 t 做 lerp 可推广 if t then b else a，取 false=0、true=1）。但递归和非数值数据怎么处理不太明显；我猜通常程序理论有 Scott 连续性，而可微函数在实数上连续，不过我数学底子不够。
abecedarius查看英文原文
Take the factorial function defined in one of the usual ways (recursive or iterative). How do you take the derivative of it, using this paper? Do you magically get the gamma function this way, too? I just skimmed the paper without getting close to answering these questions -- anyone who does already understand, maybe explaining this concrete example could help the rest of us? Thinking about the problem in my naive way earlier this year, I noticed that the usual if-then-else expression is a special case of linear interpolation, at least when you're dealing with numbers. ("lerp by t between a and b" generalizes "if t then b else a", taking false=0 and true=1.) But it's not so obvious how to handle recursion and nonnumeric data: I guess there's a hint in that the usual theory of programs has Scott continuity (https://en.wikipedia.org/wiki/Continuous_function) while differentiable functions are continuous in the reals, but I'm mathematically undereducated.
补充补充相关实现 dCpp，并设想用可演化的并行程序替代 NN，需要任意程序结构的反向传播/AD。
巧了，我昨晚刚在看这个。他们实现了：https://github.com/ZigaSajovic/dCpp。我是从这样一个设想找到它的：我总觉得深度学习的主要优势可能不是神经网络本身，而是其高度并行且非常通用的计算技术。所以如果不必是 NN，也许可以用更像演化出来的并行程序来更高效达到同样结果，也许还需要通用的虚拟传感器 grounding；若找到有用/通用的过程或数据集，就能分发出去立即提升许多不同 agent 的知识/技能。但要演化这些据称通用函数逼近、比深度 NN 更高效可交换的并行程序，你需要类似反向传播的东西，只是用于任意程序结构；维基百科讲反向传播时提到其泛化是自动微分。总之我不完全懂细节，但我的理解是：深度 NN 的反向传播确实通用，结合 grounding 并在广泛多样任务上训练，可能产生通用人类/动物式智能，问题只是算力需求巨大……
ilaksh查看英文原文
Weird I was just looking at this last night. They implemented it: https://github.com/ZigaSajovic/dCpp I got onto that based on this fantasy I was having. Basically I keep thinking that the main advantage deep learning has is probably not actually the neural nets, but the fact that they are highly parallel and very general computation techniques. So if it doesn't really have to be a NN, maybe there could be a way to more efficiently achieve the same level of results by using something more like evolved parallel programs. Maybe have a universal virtual sensor grounding. Then if you find a useful/general procedure/dataset you could distribute it to improve lots of diverse agent's knowledge/skills immediately. But to evolve these supposed universal function-approximating parallel programs that are more efficient and exchangable than deep NNs, you would need something like backpropagation, except for some arbitrary program structures. So when reading about backpropagation on wikipedia they mention the generalization is https://en.m.wikipedia.org/wiki/Automatic_differentiation Anyway I don't grock all the details fully but my interpretation of all of this is that I think things like backpropagation with deep NNs are truly general purpose and when combined with grounding such as streams of virtual/real senses and training across widely varied tasks can actually produce general human and animal/like intelligence. I think the problem is it just takes a ton of computing power, iterations and time. If we wait 2-10 years that probably won't matter. But if we don't want to wait we can probably do something similar and more efficient/readily distributable if we can use algorithms that aren't NNs but are general and highly parallel and can be adjusted via AD to learn. Based on this I personally believe we will see human/animal like general intelligence systems before 2020.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 代码
- github.com/ZigaSajovic/dCpp被提到 3 次
- 评论区提到的论文
历次讨论
- 2016Hacker News 讨论帖166 分 · 50 评
- 2018Hacker News 讨论帖64 分 · 9 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选