计算图与图计算

研究已经开始揭示许多算法可以表示为矩阵乘法，这表明线性代数和计算机科学之间存在一种未实现的联系。我推测图表是拼图中缺失的一块。图不仅是认知辅助工具，而且是适合各种任务的数据结构，特别是在现代并行处理硬件上。

在这篇文章中，我探讨了图形、代数、类型的优点，并展示了这些概念如何帮助我们对程序进行推理。我提出了一种基于图信号处理的计算原语，将软件工程、图和线性代数联系起来。最后，我分享我对未来道路的预测，我认为这是计算历史上令人兴奋的新篇章的开始。

注：这些想法都不是我一个人的。巨人的肩膀。遵循链接并使用横向模式以获得最佳阅读体验。

在过去的十年里，我押注于一些奇怪的想法。当时我尊敬的很多人都嘲笑我。我打赌他们不再笑了。总有一天我应该感谢他们，因为他们的笑声给了我很大的动力。当然，我说了一些愚蠢的话，但我也做了一些可笑的预测，这些预测是正确的。学到的教训是：瞄准更直。

2012年，我在奥斯汀坐在一位名叫阿米尔的前扑克玩家旁边，他当时在歌颂辛顿。被他的彩色幻灯片迷住了，我匆忙辞去了工作，开始了一个使用语音识别和受限玻尔兹曼机器的教育项目。它从未奏效，但我学到了很多关于ASR和Android音频的知识。我还是很喜欢这个主意。

2017年，我开始写一本关于自动化伦理的书，并预测了大规模失业和社会动荡。尽管我把原因弄错了(大流行，去想一想)，但信息经济和确认偏差都是完全正确的。可悲的是，这现在正把世界逼得完全疯了。别说我警告过你，出去修理我们坏掉的系统。这个世界需要更多关心这件事的工程师。

2017年，我见证了可差编程的诞生，我从克里斯·奥拉那里偷来的，并把它变成了一篇硕士论文。要说服人们相信经典程序可以变得可微有很大的困难，但是看看今天任何一个机器学习会议的会议记录，你会发现几十篇关于可微排序、渲染和模拟的论文。别谢我，谢谢克里斯和西亚诺的伙计们。

2018年，我正确地预测了微软将收购GitHub来挖掘代码。为什么是微软而不是谷歌？我打赌他们试过了，但谷歌领导层对AGI抱有幻想，除了JetBrains，微软是唯一关心开发者的人。现在ML4SE是一个蓬勃发展的研究领域，并出现在真正的产品中，这让那些认为ML是一种时尚的人非常懊恼。我怀疑他们的炒作过滤器蒙蔽了他们对这些工具提供的价值的认识。

预测：微软将在五年内收购GH。如果#ML4Code的东西为MS提供服务，那么收购的可能性很高。虽然几年前会便宜些。Https://t.co/5ZMtiRtifD https://t.co/TaxkArm5ps。

--布雷丹(@BreDani)2018年5月7日。

而是去他妈的我说的每一句话！如果我只有一个想法要与这些ML人分享，那就是类型。尽可能大声地敲打那个鼓。类型是我们所知的合成推理的最佳工具。如果您想要构建在实际应用程序上可伸缩的可证明正确的系统，请使用类型。还不是每个人都信服，但记住我的话，各种类型的人都来了。无论谁弄清楚如何将类型和学习联系起来，谁就是下一个芭芭拉·利斯科夫或弗朗西斯·艾伦。

今年，我在封锁前几周预测到了大流行，退出了市场，拒绝了谷歌的一份工作。有人说我疯了。现在我要全力以赴研究一些新想法(这些想法都不是我的)。我下了一些大赌注，有些会错的，但我在他们身上看到了同样的天才火花。

当我还是个孩子的时候，我得到了一本关于数学史的书。我记得它有一些有趣的谜题，包括一个有几座桥的拼图，位于一个被河流分割的小镇上，曾经居住着一个叫欧拉的人。每座桥都正好有一次过桥的旅游团吗？有没有可能在不检查每条路的情况下就能辨别出来？我记得我花了几天时间试图找出答案。

90年代末，我和妈妈去了爱尔兰。我记得参观三一学院，了解到一位名叫汉密尔顿的数学家发现了一个连接代数和几何的著名公式，并将其雕刻在一座桥上。后来我们参观了那座桥，导游指了指那块石头，我们摸了摸以求好运。爱尔兰人喜欢石头。

2007年，我申请大学，从波士顿乘火车到印第安纳州的南本德，那里是好战的爱尔兰人的故乡。在四处闲逛时，我拿起了一篇杂志文章，作者是一位名叫巴拉巴西的匈牙利数学家，当时他在巴黎圣母院，他有一些关于复杂网络的有趣的事情要说。2009年晚些时候，当我在罗切斯特学习时，我和一位不错的教授拼车，了解到复杂的网络存在于大脑、语言和许多神奇的地方。

快进到2017年。我被算法微分的诱惑所吸引。奥利维尔·布利劳克斯介绍了米娅和布切。马特·约翰逊做了一个关于Autograd的演讲。我在长滩遇到了克里斯·奥拉(Chris Olah)，他给了我学习可微编程的想法。我偷了他的点子，把它装扮成科特林，然后用它换了一篇POPL研讨会论文，后来又换成了一篇硕士论文。我们的贡献是使用代数、形状推理和将AD表示为术语重写。

2019年，我和麦吉尔大学一位不错的教授一起加入了一个实验室，将知识图谱应用于软件工程。与逻辑推理一样，知识图是20世纪60年代和70年代第一波人工智能浪潮中的一个想法，随着该领域最近的进展而复兴和研究。我相信这是一个很有潜力的重要研究领域。知识和可追溯性在软件工程中扮演着重要的角色，它是一个好的IDE的基础。如果我们想要理清我们所处的这个烂摊子，这个世界需要更好的环境。

今年春天，我参加了一个关于图形表示学习的有趣的研讨会。在过去的十年里，已经提出了许多令人愉快的图论。PageRank变成了强大的迭代。人们已经发现了线性代数的许多有趣的联系，包括Weisfeiler-Lehman图核、图Laplacian、Krylov方法和谱图理论。这些思想加深了我们对图形信号处理及其在学习和程序分析中的应用的理解。稍后会详细介绍这一点。

图形是用于表示各种数据类型和过程现象的通用数据结构。与大多数顺序语言不同，图能够表达更丰富的实体之间的关系家族，并且非常适合于计算机科学、物理、生物和数学中的许多问题。请考虑以下数据结构层次结构，所有这些数据结构都是表现力不断增强的图形：

正如我们在kotlin∇中实现的那样，有向图可以用来建模数学表达式，也可以用来建模其他形式语言，包括源代码、中间表示和二进制工件。图形不仅可以用来描述人类现有的知识，最近的许多例子表明，机器可以为各种应用“生长”树和图形，如程序综合、数学推导和物理模拟。最近的神经符号应用已经在图形合成方面显示出有希望的早期结果：

自然语言处理领域还开发了一组丰富的基于图形的表示，例如成分、依存、链接和其他类型的属性语法，它们可以用来推理自然语言实体之间的句法和语义关系。研究已经开始显示出这种语法在提取和组织存储在大型文本语料库中的人类知识方面的许多实际应用。这些图形可以进一步处理成用于逻辑推理的本体。

使用共指消解和实体对齐技术，我们可以重建实体之间的内部一致关系，从而捕获自然语言数据集中的跨语料库共识。当存储在知识图中时，这些关系可用于例如在维基和其他内容管理系统上的信息检索和问题回答。最近的技术已经显示出在自动知识库构建方面的前景(参见：Reddy等人，2016)。

瞧，知识图背后的关键思想是我们的老朋友，类型。知识图是多关系图，其节点和边具有一种类型。两个实体可以通过多个类型关联，每个类型可以关联多对实体。我们可以根据实体的类型为其建立索引以进行知识检索，并使用类型对复合查询进行推理，例如。“哪家公司有从港口城市直飞首都的航班？”，如果没有类型系统，就很难回答。

在这一部分中，我们将回顾乔姆斯基语言学中的一些重要概念，包括有限自动机、抽象重写系统和λ演算。已经熟悉这些概念的读者将对每个概念如何共享公共线程以及如何使用相同的底层抽象进行建模有了新的认识。

有一件事总是让我着迷，那就是归纳定义的语言，也被称为递归或结构归纳。考虑一种非常简单的语言，它接受形式为0、1、100、101、1001、1010等的字符串，但拒绝接受01111011或任何包含11的字符串。→符号表示“产品”。|符号，我们将其读作“or”，只是在一行上定义多个产品的简写形式：

True→1Term→0|10|εExpr→Term|Expr Term。

我们有两套产品，一套是可以扩展的，称为“非终端”，另一套是不能再扩展的，称为“终端”。请注意，每个非终端在任何单个产品中最多出现一次。此属性确保语言可由一种称为有限状态机的特殊图形识别。顾名思义，FSM包含一组有限的状态，它们之间带有标记的转换：

想象一下图书馆的服务台：你可以静静地等待，最终你会得到服务。或者，您可以按一次铃，然后静静地等待服务。如果过了一会儿没有人来，您可以再按一次铃，然后继续等待。但千万不要按两次钟，以免打扰顾客而被扔出去。

常规语言还可以对嵌套重复进行建模。考虑一种稍微复杂一些的语言，由正则表达式(0(01)*)*(10)*给出。*，或Kleene星，意思是“接受零个或多个以前的令牌”。

T→ε|0 a→10|a 10 b→0|b 01|b 0‎。

这里请注意，单个符号可能具有来自同一状态的多个转换。这台机器被称为不确定有限自动机(NFA)，可以同时占据多个状态。虽然NFA并不比它们的决定论表亲更强大，但它们通常需要更少的州来承认同一种语言。实现NFA的一种方法是模拟所有状态的叠加，只要发生这样的转换就克隆机器。稍后会详细介绍这一点。

现在假设我们有一种稍微更具表现力的语言，它接受格式良好的算术表达式，最多可以有两个变量，可以是中缀形式，也可以是一元前缀形式。在这种语言中，非终结符在单个产品中可能出现两次-expr可以由两个子表达式组成：

Term→1|0|x|y op→+|-|·expr→Term|op expr|expr op expr。

这是上下文无关语言(CFL)的一个示例。我们可以使用一种特殊的图形(称为语法树)来表示这种语言中的字符串。每次我们用产生式规则扩展expr时，都会在op上生成一个根子树，它的分支是exprs。通常，语法树是反向的，分支向下延伸，如下所示：

虽然语法树可以通过计算来解释，但除非评估，否则它们不会实际执行计算。为了[部分]评估语法树，我们现在将引入一些模式匹配规则。不只是允许终端出现在产品的右侧，假设我们还允许终端出现在左侧，并且应用规则可以缩小我们语言中的字符串。这里，我们在同一行上使用大写字母表示完全匹配，例如，规则U+V→V+U将x+y替换为y+x：

E+E→+E E·E→·E E+1|1+E|+1|-0|·1→1 E+0|0+E|E-0→E E-E|E·0|0·E|0-E|+0|-1|·0→0。

如果我们必须添加两个相同的表达式，为什么要对它们求值两次呢？如果我们需要将一个表达式乘以0，为什么还要计算它呢？相反，每当我们遇到这些模式时，我们都会尝试简化它们。这被称为重写系统，我们可以认为这是嫁接或修剪树枝。有人说，“所有的树都是DAG，但不是所有的DAG都是树”。我更喜欢把DAG想象成一棵有宝石的树：

现在让我们介绍一个新的运算符Dₓ和一些相应的规则。实际上，这些规则将把Dₓ推向尽可能远的方向，同时在此过程中重写术语。我们还将介绍一些终端重写：

[R0]Term→Dₓ(Term)[R1]Dₓ(X)→1[R2]Dₓ(Y)→0[R3]Dₓ(U+V)→Dₓ(U)+Dₓ(V)[R4]Dₓ(U·V)→U·Dₓ(V)+Dₓ(U)·V[R5]Dₓ(+U)→+Dₓ(U)[R6]Dₓ(-U)→-Dₓ(U)[R7]D。·U)→+U·Dₓ(U)[R8]Dₓ(1)→0[R9]Dₓ(0)→0。

尽管为了符号方便，我们指定了排序R0-R9，但是初始字符串一旦被赋予此系统，无论我们以哪种顺序执行替换(需要证明)，都将始终收敛到相同的结果：

这个叫做合流的特性是一些重写系统的一个重要特性：不管替换顺序如何，我们最终都会得到相同的结果。如果一种语言中的所有字符串都简化为不能进一步简化的形式，我们称这种系统为强规范化或终止。如果一个重写系统既是汇合的又是终止的，则称其为收敛的。

到目前为止，我们看到的语言能够生成和简化算术表达式，但它们本身不能执行算术，因为它们不能计算任意算术表达式。现在我们将考虑一种可以对任何算术表达式进行编码和求值的语言：

要用这种语言计算expr的值，我们需要一个替换规则。符号EXPR[var→val]，我们读作“在EXPR内，var变成val”：

例如，将上面的规则应用于表达式(λY.Yz)a会产生一个z。通过这个看似微不足道的添加，我们的语言现在足够强大，可以编码任何可计算的函数！这个系统被称为纯无类型λ演算，相当于一台拥有无限内存的理想化计算机。

虽然语法紧凑，但λ演算中的计算并不特别简洁。为了执行任何计算，我们需要一种对值进行编码的方法。例如，我们可以这样编码布尔代数：

[D1]λx.λy.x=T"；TRUE"；[D2]λx.λY.Y=F"；FALSE"；[D3]λp.λq.p q=&；"；and"；[D4]λp.λq.p q=|"；or"；[D5]λp.λa.λb.p a=！"；NOT"；

要计算布尔表达式！t，我们首先需要将其编码为λ表达式。然后，我们可以使用λ演算计算它，如下所示：

(！)。T→(λp.λa.λb.p b a)T[D5]→(λa.λb.T b a)[p→T]→(λa.λb.(λx.λy.x)b a)[D1]→(λa.λb.(λY.b)a)[x→b]→(λa.λb.(λY.B))[y→a]→(λa.λB.b)[y→]→(F)[D2]

我们已经到了终点站，不能再往回走了。这个特别的计划是可以决定的。其他人呢？让我们考虑一个无法决定的例子：

(λg.(λx.g(X X))(λx.g(X X)f(λx.f(X X))(λx.f(X X))[g→f]f(λx.f(X X))(λx.f(X X))[f→λx.f(X X)]f(λx.f(X))(λx.f(X))[f→λx.f(X)]f(λx.f(X))。X x))(λx.f(X X))[f→λx.f(X X)]...(λx.f(X X))(λx.f(X X))[f→λx.f(X X)]。

这种模式是Curry(1930年)著名的定点组合器，也是递归的基石，称为Y。与它的类型化表亲不同，非类型化的λ演算不是强规范化的，因此不能保证收敛。如果它收敛，它就不是图灵完全的。这种在可判断性和普适性之间的艰难抉择是任何计算语言都无法避免的。

λ演算也可以用图形来解释。我向好奇的读者推荐一些有希望的建议，它们试图将这一观点正式化：

基本元胞自动机是另一种字符串重写系统，由一维二进制数组和三单元语法组成。注意：重写磁带可能有一些规则。事实证明，即使在这个狭小的空间里，也存在着了不起的自动机。请考虑以下重写系统：

我们可以认为这台机器在磁带上滑动，并用第二个值替换每个匹配子字符串中最中心的单元格。根据初始状态和重写模式的不同，细胞自动机可以产生许多视觉上有趣的模式。有些人花了大量的精力来记录CA的家庭和他们的行为。在Robinson(1987)之后，我们还可以使用递归关系来归纳地定义ECA：

这种特性可能会让我们想起数字信号处理中的某种操作，称为离散卷积。我们读作“卷积”：

这就是我们的状态，被称为“内核”。与λ演算类似，这种语言也是众所周知的通用语言。忽略效率，我们可以将任何可计算函数编码为初始状态，并机械地应用规则110来模拟TM、λ演算或任何其他TC系统。

元胞自动机也可以解释为图形重写系统，尽管这种观点的好处还不是很清楚。与字符串重写不同，图替换更难有效实现，因为模式匹配等同于子图同构，这是NP完全的。虽然有一些优化可以缓解这个问题，但是图文法似乎并没有带来任何额外的计算优势。尽管如此，它在概念上还是很有趣的。

就像文法一样，我们可以归纳地定义图本身。由于许多图形算法都是递归的，因此这种选择极大地简化了它们的实现。以Erwig(2001)提出的无标记有向图的一个定义为例。这里，符号List→[Item]是List→Item List的缩写，其中Item是某个终端，List只是项目列表：

顶点→intadj→[顶点]上下文→(adj，vertex，adj)→空|上下文&；图。

Erwig将图形定义为四个部分。首先，我们有一个顶点，它只是一个整数。接下来，我们有一个顶点列表adj，称为邻接表。上下文是一个3元组，分别包含对其入站和出站邻居的顶点和对称引用。最后，我们有一个归纳的情况：一个图或者是(1)空的，或者(2)是上下文和图。

([3]，4，[1，3])&；([1，2，4]，3，[4])&；([1]，2，[1，3])&；([2，4]，1，[2，3])。

让我们考虑一个用Kotlin实现的有向图。我们不存储入站邻居，并尝试将顶点定义为封闭邻居：

开放类图(VAL顶点：集合<；顶点>；){.。。}数据类顶点(邻居：设置<；顶点>；)：GRAPH(此+邻居)//↳编译错误！

请注意协归纳的定义，它马上就会产生问题。因为这在构造对象内部是不可访问的

.