LambdaNet:利用图神经网络的概率类型推断

今天这篇博客主要讲下一篇清华大学唐杰老师推荐的一篇论文：LambdaNet:利用图神经网络的概率类型推断

本文的主要观点为：
随着渐进类型在Python和TypeScript，越来越需要自动推断类型注释。当类型注释有助于完成代码完成和静态错误捕获等任务，这些注释不能由编译器完全确定，而且对于一个用手记。本文提出了一种概率型推理方案基于图形神经网络的打字脚本。我们的方法首先使用轻量级源代码分析以生成称为类型依赖项的程序抽象图，它将类型变量与逻辑约束以及名称和使用信息。给出这个程序的抽象，然后我们使用一个图神经在相关类型变量之间传播信息并最终
进行类型预测。我们的神经结构可以预测两种标准类型，像数字或字符串，以及用户定义的类型在训练中识别。我们的实验结果表明我们的方法在此空间中对库类型执行14%（绝对）的先前工作，同时做出超出现有技术范围的类型预测的能力。

注： Gradual Typing 是 Jeremy Siek 和 Walid Taha 在2006年开发的一套类型系统，它允许程序的一部分使用动态类型（Dynamically typed）而另一部分使用静态类型（Statically typed）。

该论文首先解释了如果以传统的Rule-Based (基于规则的)类型推理算法很难推导真正的类型注释

在这篇文章中，作者提出一个新的针对typescript的概率型别推断演算法来解决这些问题
图神经网络结构（GNN）的缺点（Velickoviˇc等人，2018年；Li等人c类2016年；Mou等人，2016年）。我们的方法使用轻量级的源代码分析来转换程序进入一个称为类型依赖关系图的新表示，其中的节点表示类型变量和
标记的超边编码它们之间的关系。除了表达逻辑约束之外 例如，子类型关系）与传统类型推理一样，类型依赖关系图也包含涉及命名和变量用法的上下文提示。给定这样一个类型依赖图，我们的方法使用GNN来计算向量嵌入
对于每个类型变量，然后使用指针网络（如architec）执行类型预测真的（Vinyals等人，2015年）。图形神经网络本身需要处理各种超边类型有些具有可变数量的参数，我们为其定义适当的图传播算子。我们的预测层将类型变量的向量嵌入与候选类型的向量表示，允许我们灵活地处理具有训练期间未观察到。此外，我们的模型通过
构造，因为它进行可变级别而不是标记级别的预测。我们将我们的新体系结构作为一个叫做LAMBDANET的工具来实现，并评估了它的性能在Github的实际TypeScript项目中。当只预测库类型时，LAMBDANET
top1精度为75.6%，比DeepTyper（61.5%）有显著提高。在总精度（包括用户定义的类型）方面，LAMBDANET达到了大约64.2%，比TypeScript编译器高55.2%（绝对值）。

贡献
本文的主要贡献如下：

• （1）提出了一种概率类型利用深度学习对TypeScript推理算法程序的依赖图表示。
• （2） 我们描述一种计算矢量的技术基于GNNs的类型变量嵌入及指针网络预测方法用户定义的类型。
• （3） 我们在数百个真实世界类型上对我们的方法进行了实验评估编写项目脚本，并表明我们的方法在以前的工作基础上有了显著的改进。

2动机的示例和问题设置
图1显示了一个（类型注释）TypeScript程序。我们在这项工作中的目标是推断如图所示，给出了此代码的未注释版本。我们现在证明我们使用这个例子的解决方案。
输入约束。图1中某些函数/运算符的使用对可分配给程序变量的类型。

• 例如，在forward函数中，vari 必须为表x，y分配一个支持concat操作的类型；因此，x，y可以有类型类似于字符串、数组或张量，但不包括布尔值。这个观察激发了我们将输入约束合并到我们的模型中。
• 上下文提示。类型约束并不总是足以确定预期的类型
• 一个变量。例如，对于函数还原中的变量网络，输入约束
• 要求network的类型是一个带有名为time的字段的类，但是可以有许多类
• 具有这样的属性（例如，日期）。然后，变量名网络之间的相似性类名MyNetwork提示network可能有MyNetwork类型。基于此相信，我们可以进一步传播库函数readNumber的返回类型（假设知道它是数字）来推断MyNetwork中时间字段的类型很可能是数字。
• 需要类型依赖关系图。有很多方法可以查看程序，例如，作为标记se序列、抽象语法树、控制流图等。但是，这些表示都不是特别有助于推断最可能的类型注释。因此，我们的方法使用静态分析用于推断与类型推断问题相关的一组谓词，并表示这些谓词使用称为类型依赖关系图的程序抽象的谓词。
• 处理用户定义的类型。如第1节所述，先前的技术只能预测类型在训练中看到。但是，图1中的代码定义了自己的类MyNetwork和稍后在restore方法中使用MyNetwork类型的变量。一个成功的模型 因此，任务必须根据用户定义的类型的定义动态地对其进行推断。

2.1问题设置
我们的目标是训练一个类型推理模型，它可以将完全（或部分）未注释的TypeScript project g并为每个缺少的注释输出类型的概率分布。预测空间是Y（g）=Ylib∪Y user（g），其中Yuser（g）是所有用户定义类型的集合
（类/接口）在g中声明，而Ylib是一组固定的常用库类型。在此领域的前期工作之后（Hellendorn等人，2018；Raychev等人，2015；Xu等人。，2016年），我们将预测范围限制在非多态和非功能类型。那个我们不区分List、List、List等等，并认为它们都是列表类型。类似地，我们还折叠函数类型，如
将number→string和string→string转换为一个称为Function的类型。我们留下作为未来工作的预测结构化类型的扩展。

3类型依赖关系图
类型依赖图G=（N，E）是一个超图，其中节点N表示类型变量和标记的超边对它们之间的关系进行编码。我们提取了一个给定的TypeScript程序，通过对其中间表示形式执行静态分析源代码，它允许我们将一个唯一的变量与每个程序子表达式相关联。作为图2展示了图1中代码的中间表示。直观地说，类型依赖关系图编码类型变量的属性和关系
他们之间。每个超边对应于表1中所示的一个谓词。我们将我们的谓词（即超边）分为两类，即逻辑和上下文，其中for mer类别可以被视为对类型变量和后一个类别施加硬约束编码从变量、函数和类的名称中提取的有用提示。
图3显示了从in提取的类型依赖图G中的一些超边 如图2所示。如图3（A）所示，我们的分析提取了一个谓词
此代码中的子类型（τ13，τ5），因为与返回表达式关联的类型变量v4必须是封闭函数的返回类型的子类型。同样，如图3（B）所示，我们的分析提取谓词Objectname，time，forward（τ8，τ1，τ2，τ9），因为τ8是
名称、时间和前向构件分别与类型变量τ1、τ2、τ9相关。与对类型变量施加硬约束的子类型和对象谓词不同，
图3所示的下两个超边编码从变量名获得的上下文线索。图3（C）表明类型变量τ14与名为restore的表达式相关联。
而这种命名信息对于TypeScript的结构类型系统是不可见的（？），它作为第4节中描述的GNN体系结构的有用输入特性。

除了存储与每个类型变量相关联的唯一变量名之外，类型dependency图还对变量名和类名之间的相似性进行编码。许多程序的名称变量模拟它们的类型：例如，名为MyNetwork的类的实例通常是
称为网络或网络1。为了捕获这种对应关系，我们的类型依赖图也包含一个名为NameSimilar的超边，如果类型变量α和β对应标记化名称有一个非空的交集。1如表1所示，有一个名为Usage的超边的最终类型，它有助于类型推断
对象类型的。特别是，如果有一个对象访问变量y=x.l，我们提取谓词Usagel（τx，τy），（α1，β1）。，（αk，βk））将x和y型变量与所有类αi连接起来那个包含名为l的属性/方法βi。图3显示了从图2中的代码。正如我们将在下一节中看到的，我们的GNN架构使用了一个特殊的注意机制沿着这些使用边缘传递信息。

4神经结构
我们用于进行类型预测的神经结构由两个主要部分组成。首先，一个图神经网络沿着类型依赖图传递信息以生成向量值嵌入基于每个类型变量的邻居。其次，指针网络比较每个变量的类型嵌入到候选类型的嵌入向量（都是从上一个
阶段）在可能的类型分配上放置分布。给定一个类型依赖图G=（N，E），我们首先计算每个类型的向量嵌入vn
使这些向量隐式地编码类型信息。因为我们的程序抽象是一个图，自然选择是使用一个图神经网络架构。从高层来看
架构接受初始向量对于每个节点n，执行K轮消息传入图形神经网络，并返回每个类型变量的最终表示形式。更详细地说，让由消息传递和聚合步骤组成。消息传递步骤计算向量值更新发送到每个超连接节点 e ∈ E 连接的每个节点p1, . . . , pa.
然后，在计算完所有消息之后，聚合步骤将计算一个新的嵌入对于每个n，通过组合发送到n的所有消息：

这里，N是邻域函数，Msge表示一个特定的神经操作，它依赖于在边的类型上（固定的、不固定的或不连续的），我们将在后面描述。
初始化。在我们的GNN中，节点对应于类型变量，每个类型变量都与程序变量或常量相关联。我们将表示常量（resp.variables）的节点称为常量（resp.variables）。变量）节点，我们的初始化过程的工作方式不同
取决于n是否为常量节点。由于每个常数的类型都是已知的，我们将类型τ（例如，字符串）的每个常数节点的初始嵌入设置为可训练向量cτ，并且在GNN迭代期间不更新它（即，t，=cτ）。另一方面，如果n是
变量节点，则在初始化过程中我们没有关于其类型的信息；因此，我们使用通用的可训练初始向量初始化所有变量节点（即，它们初始化为相同的向量，但在GNN迭代过程中更新为不同的值）。信息传递。我们的Msg运算符取决于它对应的边的类别（请参见表1）；但是，权重在同一超边类型的所有实例之间共享。接下来，我们描述用于计算每种类型超边缘的消息的神经层：

• Fixed：由于这些边对应于固定的算术谓词（并且每个参数的位置都很重要），我们首先将所有参数的嵌入向量串联起来，然后将结果向量馈送给2层MLP作为jth参数，从而计算出jth参数的消息。此外，

由于类型Access的超边有一个标识符，我们还将标识符作为向量嵌入，并将其作为额外的参数处理。（我们将在本节后面描述标识符嵌入的详细信息。）

• NARY：由于NARY边缘连接的节点数量可变，因此我们需要一个能够应对这一挑战的架构。在我们当前的LAMBDANET实现中，我们使用了一个简单的架构，该架构易于批处理。具体地说，给定一个n边El1，…，lk（α，β1，…）。，βk）（对于函数和调用，标签lj是参数位置），计算α的消息集 当{MLPα（vlj-kvβj）| j=1时。k} ，每个βj的消息计算为MLPβ（vlj-kvα）。观察到我们为α计算k个不同的信息，每个βj的信息仅取决于α的向量嵌入及其位置j，而不取决于其他βj的向量嵌入。
• NPAIRS:这是与Usagel（（α，β），（α1，β1）。（αk，βk））。Re 调用这种边是由形式b=a.l的表达式产生的，用于连接a和 b的类型变量，所有类αi都包含标签为l的属性/方法βi。直观地说，如果a的类型嵌入与C的类型非常相似，那么b的类型可能与C.l的类型相同。根据这个推理，我们使用基于点积的注意来计算αt的消息 和βo。具体来说，我们使用αw αj’s作为注意键，βj’s作为注意值计算 β的消息（并切换关键值角色以计算α的消息）：

聚合。回想一下，聚合步骤将发送到节点n的所有消息组合起来进行计算新的嵌入. 为了实现这个目标，我们使用了基于注意力的聚合的变体图来实现注意网络中提出的算子（Velickoviˇcc等人，2018）。

其中，我们是来自边缘e的消息的注意权重。具体来说，权重被计算为softmax（a）， 其中可训练矩阵。与最初的GAT架构类似，我们将LeakyReLu的斜率设置为0.2，但我们使用点积来计算注意权重，而不是线性模型。
标识符嵌入。就像在Allamanis等人。（2017），我们根据驼峰大小写和下划线规则将变量名分解为单词标记，并为在训练集中出现多次的所有单词标记分配一个可训练向量。与Allamanis等人不同的是，所有其他代币。（2017年），将它们全部映射到一个标记中，我们将它们随机映射到标记中的一个，在我们当前的实现中，i的范围从0到50。每次我们运行GNN时，这个映射都是随机构造的，因此有助于我们的神经网络区分
不同的token，即使它们是稀有的token。我们端到端地训练这些标识符嵌入以及我们的架构的其他部分。
预测层。对于每个类型变量n和每个候选类型c∈Y（g），我们使用MLP计算相容性得分sn，c=MLP（vn，uc），其中uc是c的嵌入向量。如果c∈Ylib，vc是每个库类型c的可训练向量；如果c∈Yuser（g），则它对应于
g的类型依赖图中的一个节点nc，所以我们只对nc使用嵌入向量，并设置uc=vnc. 形式上，这种方法看起来像一个指针网络（Vinyals等人，2015），在这里我们使用前向传递期间计算的嵌入来预测这些类型的“指针”。
考虑到这些兼容性得分，我们应用softmax层将其转换为概率分布。
在测试期间，我们最大化了(或者TopN)计算最可能的类型分配.

5评估
在这一部分中，我们描述了实验评估的结果，旨在回答以下问题：（1）我们的方法与以前的工作相比如何？（2） 我们的模型可以预测用户定义的类型吗？（3） 我们模型的每个组件有多有用？
数据集。类似于Hellendorn等人。（2018），我们在来自Github的流行开源TypeScript项目上培训和评估我们的模型。具体来说，我们从Github收集了300个流行的TypeScript项目，这些项目包含500到10000行代码，其中至少10%的类型注释是用户定义的类型。注意，每个项目通常包含数百到 要预测的类型变量数以千计，这些项目总共包含大约120万行类型脚本代码。在这300个项目中，我们使用60个用于测试，40个用于验证，其余用于训练。
代码复制。我们对整个数据集运行了jscpd3，发现只有2.7%的代码是重复的。此外，这些副本大多是项目内部的。因此，我们认为代码复制在我们的数据集中不是一个严重的问题。
预处理。因为我们的基准测试套件中的一些项目只有少量的an 表示类型，所以我们使用TypeScript编译器提供的前向类型推断功能来扩充我们标记的训练数据。4编译器无法推断每个变量的类型，并且在失败的推断过程中留下许多标记为any；因此，我们排除了任何标记在我们的数据集中。

此外，在测试时，我们只在由开发人员手动添加的注释上评估我们的技术。这与Hellendorn等人使用的方法相同。（2018），而且，由于开发人员经常在代码最不清楚的地方添加注释，这对类型预测构成了一个挑战性的设置。
预测空间。如2.1节所述，我们的方法以整个TypeScript项目g作为输入，相应的类型预测空间是Y（g）=Ylib∪Yuser（g）。在我们的实验中，我们将Yuser（g）设置为g中定义的所有类/接口（除了与DeepTyper比较时，我们将Yuser（g）设置为空），对于Ylib，我们选择了训练集中最常见的100种类型。注意，这涵盖了98%（分别为。97.5%的非任何培训说明（分别。测试）设置。
在开发模型时，我们通过调整验证集来选择超参数。我们使用32维类型的嵌入向量，模型中的所有MLP变换使用一个32个单位的隐藏层，除了MLP用于计算预测层中的分数，
它使用大小为32、16和8的三个隐藏层（输出为大小1）。来自不同时间步的GNN消息传递层具有独立的权重。
我们使用默认参数（α=0.9，β=0.999）的Adam（Kingma&Ba，2014）训练模型，并将学习率设置为10-3
最初但线性地减少到10-4，直到第30个Epoch(数据集的整体重复训练)。
我们使用10-4的权重衰减进行正则化，并在验证集的损失开始增加（通常发生在30个阶段左右）时停止训练。我们将单个项目的类型注释用作小批量，并将最大批量大小（通过下采样）限制为训练集的中值，以防止任何单个项目产生太大的影响。

实施细节。我们在Scala中实现了LAMBDANET，构建在Java高性能张量库Nd4j（nd4）之上，并使用自定义的自动差分库实现了GNN。我们的GNN实现不使用邻接矩阵来表示GNN
层；相反，我们直接从类型依赖关系图构建超边缘连接，并在计算同一类型的所有超边缘的消息时执行批处理。
代码库。我们已经在Github上公开了我们的代码
5.1与DeepTyper的比较
在这个实验中，我们将LAMBDANET的性能与DeepTyper（hellendorn et al.，2018）进行了比较，后者将程序视为令牌序列，并使用双向RNN进行类型预测。因为DeepTyper只能从一个固定的词汇表预测类型，所以我们修复了两个LAMBDANET 以及DeepTyper对Ylib的预测空间，并测量其相应的top-1精度。原始的DeepTyper模型对每个变量的出现进行预测，而不是对decla  ration进行预测。为了在DeepTyper和LAMBDANET之间进行有意义的比较，我们实现了DeepTyper的一个变体，它对每个变量进行一次预测（在进行预测之前，通过对同一变量的所有出现的RNN内部状态进行平均）。此外，为了公平比较，我们确保DeepTyper和LAMBDANET都使用相同的改进命名功能，将单词拆分为标记。

我们的主要结果总结如下，其中声明（分别。出现）列显示每个变量声明的准确度（分别。令牌级事件）。注意，我们通过用每个变量的出现次数加权每个变量，从而从声明级别的准确性中获得出现级别的准确性。

从表中可以看出，LAMBDANET与DeepTyper。特别是，LAMBDANET在声明方面比DeepTyper强14.1%（绝对值）水平精度，发生水平精度为9.6%。
请注意，我们为DeepTyper（67.4%）报告的准确性与原始数据不可直接比较Hellendorn等人报告的准确性。（2018年）（56.9%）原因如下。当我们展示静态分析的时候，并严格区分库类型和用户定义类型，只对两者进行评估
关于库类型注释的工具在这个实验中，它们的实现将类型视为标记和没有这种区别。因此，他们的模型还考虑了更大的预测空间由许多用户定义的类型组成，其中大多数从未在项目之外使用它们是定义的，并且在一组不同于我们的注释上进行计算。
5.2预测用户定义的类型
如前所述，我们的方法不同于以往的工作，因为它能够预测用户定义的类型；因此，在第二个实验中，我们将LAMBDANET的预测空间扩展到包括用户定义的类型。然而，由于这类类型不在先验的预测空间中
工作（Hellendorn等人，2018），我们实现了两个更简单的基线，可用于校准我们模型的演示。我们的第一个基线是由TypeScript执行的类型推断编译器，它是健全的，但不完整（即，如果它推断出一个类型，则保证它是正确的，但是我们的第二个基线，称为SIMILARNAME，灵感来自变量名及其对应类型之间的相似性；它预测每个变量名的类型变量v是其名称与v共享最多公共字标记的类型。
实验结果如表2所示，显示了前1名和前5名的准确度分别用于用户定义的类型和库类型以及整体精度。总的来说
预测准确率，前1名的LAMBDANET达到64.2%，前5名的LAMBDANET达到84.5%，显著高于前2名执行两个基线。我们的结果表明我们的逻辑和上下文信息的融合预测类型远比孤立地基于规则合并这些类型更有效。

5.3消融研究
表3显示了消融研究的结果，其中（a）我们改变了消息传递迭代的次数（左）和（b）禁用了我们架构设计的各种特性（右）。从左表可以看出，随着消息传递次数的增加，准确性不断提高迭代次数高达6次；这一增益表明我们的网络学会了远距离执行推理。右表显示了我们的几个设计选择对总体结果的影响。

例如，如果我们不使用上下文边缘（resp。逻辑边缘），总体准确度下降了14.5%（分别为。25.8%。这些下降表明，这两种谓词对于获得良好的准确性至关重要。我们还发现NPAIR的注意层对
库类型和用户定义类型。最后，简单聚合是LAMBDANET的一个变体，它使用更简单的聚合操作，用简单平均值替换等式1中基于注意力的加权和。如表3最后一行（右）所示，基于注意力的聚合
对于用户定义的类型有很大的不同。
5.4与JSNICE的比较
由于JSNice（Raychev et al.，2015）无法正确处理类定义和用户定义类型，为了进行有意义的比较，我们比较了两个工具在从测试集中随机抽样的顶级函数上的性能。我们筛选出参数不是库类型和man的函数
确保所有依赖项定义也都包含在内。这样，我们构建了一个由41个函数组成的小型基准测试套件。在107个函数参数中
类型注释中，LAMBDANET正确预测了77个，而JSNice只正确预测了48个。这些结果表明LAMBDANET优于JSNice，即使仅在JSNice适用的地方进行评估。

6相关工作
使用统计方法的类型推断。在预测动态类型语言的可能类型注释方面，以前有一些工作：Raychev等人。（2015）和Xu等人。（2016）对Javascript和Python使用结构化推理模型，但它们的方法没有利用
深度学习的，并且局限于一个非常有限的预测空间。Hellendorn等人。（2018）和Jangda&Anand（2019）将程序建模为序列和AST树，并将深度学习模型（RRN和树RNN）应用于TypeScript和Python程序。Malik等人。（2019）利用 一个不同的信息源，并将文档字符串作为其输入的一部分。然而，以往的研究都局限于从固定词汇中预测类型。程序的图嵌入。Allamanis等人。（2017）是第一个使用GNNs来获得程序深度嵌入的，但它们侧重于预测变量名和C]的误用，并依赖静态类型信息来构造程序图。Wang等人。（2017）使用GNN编码
定理自动证明中前提选择的数学公式。我们对类型的编码方式与它们对量化公式的编码方式有一些相似之处，但是当它们的重点放在更高阶的公式上时，我们的问题需要对对象类型进行编码。Velickovicc等人。（2018）是第一个
在GNNs中使用注意机制。当他们使用注意从消息计算节点嵌入时，我们使用注意从节点嵌入计算某些消息。
从一个开放的词汇预测。在测试时预测看不见的标签对传统的机器学习方法提出了挑战。对于计算机视觉应用，解决方案可能包括查看对象属性（Farhadi等人，2017）或标签相似性Wang等人。（2018）；对于自然语言，类似的技术被应用于概括话语的语义属性（Dauphin等人，2013年）、实体（Eshel等人，2017年）或标签（Ren等人，2016年）。从形式上讲，这些方法大多将输入的嵌入与标签的某些嵌入进行比较；什么使我们的方法a指针网络（Vinyals等人，2015年）是，我们的类型编码是在输入的前向传递过程中导出的，类似于机器翻译的未知单词（Gulcehre等人，2016年）

7结论
我们提出了LAMBDANET，一种将显式程序分析和图形神经网络相结合的类型推理神经结构。LAMBDANET不仅在预测库类型时优于其他最先进的工具，而且还可以有效地预测用户定义的类型
在训练中没有遇到过的。我们的消融研究证明了我们提出的逻辑和上下文超边缘的有用性。对于未来的工作，我们现有的系统有几个潜在的改进和扩展。当前体系结构的一个限制是对函数类型和泛型类型的简化处理 （即，将它们折叠成非通用的对应项）。将预测空间扩展到还包括结构化类型将允许我们充分利用许多现代语言（如TypeScript）提供的丰富类型系统。另一个重要方向是实施硬约束在推理过程中，确保得到的类型分配是一致的。

项目github地址： https://github.com/MrVPlusOne/LambdaNet