原创 LAMP：通过导数计算的基于图的机器学习算法的数据来源

1 摘要

数据来源跟踪确定与给定输出相关的一组输入。它使数据工程中的质量控制和问题诊断成为可能。大多数现有技术通过跟踪程序依赖性来工作。他们无法从数量上评估相关输入的重要性，这对于机器学习算法至关重要，在机器学习算法中，输出往往取决于大量输入，而其中只有一些输入很重要。在本文中，我们提出了 LAMP，一种用于机器学习算法的出处计算系统。受自动微分（AD）的启发，LAMP 通过计算偏导数来量化输入对于输出的重要性。LAMP 将原始数据处理和更昂贵的导数计算分离到不同的过程中，以实现成本效益。另外，它允许量化与离散行为（例如控制流选择）相关的输入的重要性。对一组现实世界的程序和数据集的评估表明，与基于程序依赖的技术相比，LAMP 产生了更精确，更简洁的出处，而开销却少得多。我们的案例研究证明了 LAMP 在数据工程问题诊断中的潜力。

2 研究简介

与传统软件工程相比，数据工程的复杂性主要在于数据和模型。例如，许多数据处理程序，例如众所周知的机器学习程序，具有较小的尺寸。但是这些程序处理的数据和生成的模型通常很大且很复杂。基于图的机器学习（GML）是一种越来越受欢迎的数据处理方法。提供输入图模型和初始权重值后，GML 算法将生成更新的模型。这些算法大多数都是迭代算法。在每次迭代中，一个顶点与其邻居进行通信并更新其值，直到所有值收敛为止。通过多次迭代，一个顶点会影响到许多边缘不远的其他顶点。这就是所谓的涟漪效应。由于这种计算的性质，要确定所生成模型的正确性极具挑战性，因为故障可能会通过许多步骤传播，而故障状态可能会在传播过程中累积/混淆。即使用户怀疑最终输出的不正确性，他也几乎无法诊断确定根本原因的过程，根本原因可能出现在输入图模型，初始权重值甚至 GML 算法本身中。

数据出处是一种重要的方法解决问题。它标识输入输出依存关系和/或记录操作历史，大多数专注于在运行时选择性地收集中间结果，以努力提供崩溃恢复机制，调试支持等。但是，这些技术几乎无法解释输入输出的依赖性，无法量化单个输入的重要性。由于 GML 算法的涟漪效应，即使大多数输入对输出的影响微不足道，输出也往往取决于大量输入。

在本文中，作者提出了 LAMP，一种量化输入重要性的技术。受到自动差分，LAMP 通过计算关于输入的输出导数来工作。该设计将原始数据处理与出处计算分开，因此在生产运行过程中引入的开销很少。它通过产生过程具体确定输出变化来量化那些可能引起控制流变化的输入重要性。作者团队的主要贡献在于：

• 正式定义了 GML 算法的出处计算问题，这是量化输入重要性的关键挑战。
• 提出了一种将原始数据处理与出处计算分离的新颖设计。
• 提出了一种基于执行的方法来量化与控制相关的输入重要性流程。
• 我们开发了原型 LAMP。我案例研究证明了 LAMP 在数据工程中的潜力，它可以帮助开发过程和发现输入数据，图形模型甚至 GML 算法实现中的错误。

概念定义

如果一个顶点很重要（即，通过具有高的初始权重或通过与许多其他顶点连接），则其初始值的较小扰动将更改所有连接的顶点的值，并最终导致实质性的输出变化。但是，尽管数学功能在很大程度上是连续的，但 GML 程序具有许多离散的行为。结果，Fn 函数通常是不连续的。请注意，在不连续函数中，任意小的输入变化不会导致任意小的输出变化。结果，导数是无限的。在这种情况下，导数不代表输入变化的影响。因此，作者改为报告输出变化，见图 1。

图 1 LAMP 原理本质示意图

3 LAMP 方法描述

基本思路

LAMP 动态计算每个变量的偏导数。给定一个语句

操作数，LAMP 利用导数链规则计算每个初始权重的偏导数。计算函数组成的导数是一条如下规则：

其中f(u)是最终输出，u是中间结果，x是输入变量。从直觉上讲，它可以根据函数对输入的导数和中间结果对输入的导数来计算函数对输入的导数。利用链规则，可以基于在定义操作数时计算出的操作数值及其偏导数，在本地对语句进行微分计算。在谓词上，LAMP 检查任何初始权重值的微小变化是否会导致谓词采取不同的分支结果。这可以通过使用谓词表达式的计算偏导数通过线性近似来完成。如果是这样，则 LAMP 产生一个新的进程来接管另一个分支。最后，通过比较所有过程的输出得出输出变化。根据§3 中的问题陈述，由不连续性引起的偏导数和输出变化是衡量输入对输出的影响的结果数据来源。

详细设计：运行时数据采集

在生产运行期间，LAMP 进行非常轻量级的跟踪，以收集分支结果和某些操作（例如乘法）的结果。跟踪语义在图 2 中说明。表达规则是标准的。根据评估上下文 E，在应用语句规则之前，首先将表达式评估为值。语句评估具有 σ，ω 和 C 的配置：σ 是存储;ω 是由跟踪项的顺序组成的跟踪日志，每个跟踪项包含一个语句标签，该语句的执行计数器值和一组值; C 记录当前计数器每个陈述的价值。大多数陈述的评估规则是标准的，因此这种模式是合理的。

图 2 语义规则说明 详细介绍了多种运行时数据语义规则构建形式

规则[MUL-LOG]和[MUL-LOG-Y]指出 LAMP 可能会记录乘法的操作数值，因为在以后的源计算阶段的导数计算中需要使用这些值。如果编译器静态确定两个操作数变量都与带注释的输入变量相关，则通过将条目附加到 ω 来记录其值，同时计数器也增加了。同样，如果只有一个操作数与输入相关，则记录另一个操作数的值。当两个操作数都不与输入变量相关时，LAMP 无需计算导数，因此不记录操作数值（规则[MUL-NoLOG]）。根据条件语句，LAMP 确定谓词是否与输入变量相关。如果是这样，它将通过方法 unstable（）进一步检测出分支结果是否可能不稳定。如果小的输入扰动 Δ 翻转分支结果，则分支结果不稳定。

图 3 代码转化规则 描述不同条件下各类代码的转化规则

详细设计：代码转换

LAMP 将原始程序转换为新程序，该程序将获取原始输入图和在跟踪阶段生成的日志，并执行出处计算。图 3 描述了一组转换规则。

当谓词中的变量与输入不相关时，则将语句转换为从日志中加载分支结果（规则[T-IF-NOINPUT]）。根据规则[T-IF-INPUT]，当变量输入相关时，以下语句将添加到转换后的程序中。第 1 行测试记录的分支结果是否为真。如果是这样，则第 2 行进一步测试日志条目是否包含其他信息（即|ω[ℓ，cnt（ℓ）] |> 1），这表明谓词潜在地不稳定，并且较小的输入变化量 Δ 会导致值变化较大。比（记录的）值大，并利用偏导数。如果是这样，则分支结果可以翻转。因此，LAMP 生成一个进程以继续沿原始程序中的另一个分支执行（第 3 行）。在执行分支之前，LAMP 将恢复临界状态。父进程继续在 true 分支（第 5 行）中进行导数计算。第 4 行用于记录带注释的输入变量，这些变量的变化可能会翻转分支结果和子进程 id。在计算结束时，对于每个导致谓词不稳定的输入，LAMP 会在所有关联过程中以 zmax 和 zmin，最大值和最小值 z 收集输出变量 za 的值，这表示输入对 z 的影响。图 1 显示了转换后的 PageRank。

详细设计：讨论

LAMP 使用导数作为来源，并输出加权偏倚图，其中偏导数作为权重。它可以检测影响此类依赖关系和相应权重的错误。它的能力也会影响具体的数值。对重量不可见或影响不大的 Bug，被 LAMP 检测的概率较小。此外，由于 LAMP 的目标是机器学习计算过程，因此如果工作流中发生错误（例如，选择错误的数据集，不合适的机器学习算法），它将无法提供帮助。

4 验证

作者从来源计算开销，内存开销，日志空间，稳定性等方面评估的 LAMP 的效率，并简单介绍了 LAMP 的实效性。结果表明，该工具具有极高的使用效率，在各项性能和功能的可用性上均有出色表现。相关验证结果图片如下（图 4,表 1）:

图 4 内存计算开销

表 1 来源计算开销