Tabular：基于电子表格的概率推理语言

# Tabular：基于电子表格的概率推理语言 ## 1. 概述 概率编程语言旨在让机器学习更易上手，允许用户将生成模型写成计算机程序，并提供通用推理引擎，对用该语言编写的有效程序进行推理。然而，现有的大多数概率编程语言本质上是传统编程语言的概率扩展，对于非专业程序员来说使用难度较大。而且，这些语言通常要求将所有必要数据加载并放置在正确的数据结构中，这往往需要大量的数据预处理工作，即使是经验丰富的程序员和统计学家也会觉得麻烦。 Tabular语言采用了不同的方法。它不是在普通编程语言中添加采样和条件化原语，而是在关系数据库模式中添加概率模型表达式和注释。其核心思想在于，在基于模型的贝叶斯机器学习中，起点并非模型本身，而是要拟合模型的数据集，这些数据通常存储在数据库（如电子表格）中。在Tabular里，概率模型构建于数据之上，输入数据库在输入程序前无需进行操作。 Tabular的主要优势在于它比标准编程语言更易于使用，用户无需从头编写实际程序，只需用概率表达式注释数据库模式，解释数据的生成方式，并为感兴趣的未知量添加潜在列。此外，Tabular的设计使其能够与电子表格应用等用户熟悉的环境集成。实际上，Tabular已实现为Excel插件，模型和输入数据库都以Excel电子表格的形式指定，推理结果也保存到电子表格中，便于后续处理和可视化。Tabular的命令行版本是开源的，源代码可在https://github.com/TabularLang/CoreTabular获取。 ## 2. 介绍与示例 ### 2.1 Tabular中的概率编程 Tabular程序通过扩展数据库模式来构建，具体包括： - 潜在列：表示数据库中不存在的未知参数，需要从数据中推断得出。 - 注释：定义各列在概率模型中的角色（输入变量、建模输出变量、局部变量）。 - 模型表达式：表达对数据库中给定列的值是如何生成的看法。 在最简单的情况下，模型表达式是用带有随机抽样的一阶函数式语言编写的普通表达式。我们将仅包含此类简单表达式的模式和表称为核心模式和表。其他类型的模型包括函数应用和索引模型，后续会详细讨论。 以在线视频游戏玩家排名的TrueSkill模型为例，假设我们有一个包含玩家过去比赛结果的数据库，其模式如下： ```plaintext table Players Name string table Matches Player1 link(Players) Player2 link(Players) Win1 bool ``` 其中，`Win1` 为 `true` 表示玩家1赢得比赛，为 `false` 表示玩家2赢得比赛（假设没有平局）。我们希望根据这些过去的结果推断玩家的相对技能。 根据TrueSkill模型，我们用一个数值来量化玩家在某场比赛中的表现，该数值是玩家技能的有噪副本。我们假设每场比赛由表现值较高的玩家获胜。在Tabular中，我们可以通过扩展上述模式来实现这个模型： ```plaintext table Players Name string!det input Skill real!rnd output Gaussian(100.0, 100.0) table Matches Player1 link(Players)!det input Player2 link(Players)!det input Perf1 real!rnd output Gaussian(Player1.Skill, 100.0) Perf2 real!rnd output Gaussian(Player2.Skill, 100.0) Win1 bool!rnd output Perf1 > Perf2 ``` 我们在 `Players` 表中添加了一个新列 `Skill`，在 `Matches` 表中添加了两列 `Perf1` 和 `Perf2`。`Skill` 列的分布需要从观察数据中推断，我们为其分配表达式 `Gaussian(100.0, 100.0)`，定义了玩家技能的先验分布为均值为100、方差为100的高斯分布。`Perf1` 和 `Perf2` 列的值在模型的生成解释中，从以相应玩家技能为中心的高斯分布中抽取。最后，观察列 `Win1` 被分配表达式 `Perf1 > Perf2`，表示在 `Matches` 表的每一行中，如果 `Win1` 为 `true`，则 `Perf1` 必须大于 `Perf2`；如果 `Win1` 为 `false`，则 `Perf1` 不得大于 `Perf2`，否则参数值将与观察结果不一致。 这些类型中的 `det` 和 `rnd` 注释指定了给定列中的数据是确定性的（预先已知）还是随机的（由推理算法推断）。这些注释（我们称为空间）用于类型系统，以捕获信息流错误，例如假定为确定性的数据依赖于随机变量。Tabular列也可以处于 `qry` 空间，后续会进行讨论。 为了在上述模型中进行推理，我们需要在特定数据集上对其进行参数化。在Tabular中，输入数据与程序分离，由编译器从单独的数据源加载。这种方法使得在不修改模型的情况下，对同一模型使用多个数据集进行推理成为可能。上述实现的TrueSkill模型旨在应用于包含数千场比赛和玩家的数据库，但以下是该模式的一个有效的小型输入数据库： | Players | ID | Name | | --- | --- | --- | | | 0 | "Alice" | | | 1 | "Bob" | | | 2 | "Cynthia" | | Matches | Win1 | Player2 | ID | Player1 | | --- | --- | --- | --- | --- | | | false | 1 | 0 | 0 | | | false | 2 | 1 | 1 | 在这个例子中，我们有三个玩家：Alice、Bob和Cynthia。假设Bob在第一场比赛中击败了Alice，在第二场比赛中被Cynthia击败。 Tabular的默认推理算法是期望传播（Expectation Propagation），它将未观察到的随机列的近似分布添加到输入数据库中。上述小型示例的输出数据库如下： | Players | Skill | ID | Name | | --- | --- | --- | --- | | | Gaussian(95.25, 82.28) | 0 | "Alice" | | | Gaussian(100.0, 70.66) | 1 | "Bob" | | | Gaussian(104.8, 82.28) | 2 | "Cynthia" | | Matches | Win1 | Perf2 | ID | P1 | P2 | Perf1 | | --- | --- | --- | --- | --- | --- | --- | | | false | Gaussian(104.8, 123.6) | 0 | 0 | 1 | Gaussian(90.49, 129.1) | | | false | Gaussian(109.5, 129.1) | 1 | 1 | 2 | Gaussian(95.25, 123.6) | 这与我们的直觉相符，即Cynthia击败了第一场比赛的获胜者，很可能是三个玩家中最优秀的，而Alice可能是最弱的。 除了上述按潜在列查询的推理方式，Tabular还支持按缺失值查询，即数据库中一个或多个输出列存在缺失条目，目标是计算这些缺失值的分布。例如，如果我们想预测Alice和Cynthia即将进行的比赛的结果，可以将比赛表扩展如下： | Matches | ID | Player1 | Player2 | Win1 | | --- | --- | --- | --- | --- | | | 1 | 0 | 0 | false | | | 1 | 1 | 2 | false | | | 2 | 0 | 2 |? | Tabular推理引擎将计算第三列中 `Win1` 的分布： | Matches | Win1 | Perf2 | ID | P1 | P2 | Perf1 | | --- | --- | --- | --- | --- | --- | --- | | | false | Gaussian(104.8, 123.6) | 1 | 0 | 0 | Gaussian(90.49, 129.1) | | | false | Gaussian(109.5, 129.1) | 1 | 1 | 2 | Gaussian(95.25, 123.6) | | | Bernoulli(0.3092) | Gaussian(104.8, 182.3) | 2 | 0 | 2 | Gaussian(95.25, 182.3) | ### 2.2 用户定义的依赖类型函数 Tabular支持函数，这些函数的定义方式与普通表相同，可用于抽象出仅在模型表达式中使用的某些值不同的任意重复代码块。函数有助于用户使模式更简洁。Tabular自带一个预定义函数库，例如表示常用共轭模型的函数，用户也可以定义新函数。 为了说明函数在Tabular中的使用方法，我们考虑从抛硬币结果推断硬币偏差的问题。假设每个偏差（介于0和1之间）的可能性相等，这个模型在Tabular中可以表示为： ```plaintext table Coins V real!rnd[2] static output Dirichlet[2]([1.0, 1.0]) Flip mod(2)!rnd output Discrete[2](V) ``` 其中，`Dirichlet[2]([1.0, 1.0])` 是两个概率之和为1的均匀分布，`Discrete[2](V)` 根据 `V` 的相应分量的比例抽取0或1（分别表示反面和正面）。 这个模型是共轭离散模型的一个实例，共轭离散模型是许多更复杂模型的构建块，在标准函数库中定义如下： ```plaintext fun CDiscrete N int!det static input R real!det static input V real!rnd[N] static output Dirichlet[N]([for i < N →R]) ret mod(N)!rnd output Discrete[N](V) ``` 该函数的参数 `N` 和 `R` 分别表示参数向量的长度和传递给先验的超参数向量的每个分量的值（`R` 的值越高，参数向量的分量预期越接近）。这个函数还展示了依赖类型的使用：`real!rnd[N]` 表示给定的随机列是一个大小由变量 `N` 确定的实数数组，`mod(N)!rnd` 表示一个小于 `N` 的非负随机整数。需要注意的是，在 `CDiscrete` 的定义中，我们也可以将传递给 `Dirichlet[N]` 的整个伪计数向量作为类型为 `real!det[N]` 的参数。 有了这个函数，我们可以将抛硬币模型重写为： ```plaintext table Coins Flip mod(2)!rnd output CDiscrete(N=2, R=1.0) ``` 将 `R` 设置为1.0可确保正面和反面概率 `V` 的先验分布是均匀的。 Tabular还支持索引函数应用，这会将模型的静态参数转换为数组，由分类变量（即具有有限域的离散随机变量）进行索引。例如，假设在上述问题中有两枚具有不同偏差的硬币，我们总是随机选择一枚进行抛掷。为了推断硬币的偏差，我们可以将上述Tabular程序修改如下： ```plaintext table Coins CoinUsed mod(2)!rnd output Discrete[2]([0.5, 0.5]) Flip int!rnd output CDiscrete(N=2, R=1.0)[CoinUsed < 2] ``` 现在，我们有两个偏差向量 `V` 的副本，每个硬币一个，在每一行中，使用由随机变量 `CoinUsed` 指示的向量。 ### 2.3 查询变量 Tabular的另一个新特性是 `infer` 运算符，它可用于提取推断分布的属性，例如高斯分布的均值或伯努利分布的偏差。这些属性可用于计算依赖于推理结果的一些伪确定性数据。 例如，在上述有偏差的硬币示例中，我们可能希望提取硬币的实际偏差，以数值而非分布的形式表示。由于偏差的后验分布是狄利克雷分布，由正面和反面的“伪计数”参数化，偏差本身就是正面的计数除以总计数。使用 `infer` 运算符，我们可以如下计算： ```plaintext table Coins V real!rnd[2] static output Dirichlet[2]([1.0, 1.0]) Flip mod(2)!rnd output Discrete[2](V) counts real!qry[2] static local infer.Dirichlet[2].pseudocount(V) Bias real!qry static output counts[1]/(counts[1]+counts[0]) ``` 例如，如果我们将这个模型应用于一个由三次抛硬币结果组成的小型数据库，其中两次为正面，一次为反面，推理算法将返回以下静态量： | Coins | Bias | counts | V | | --- | --- | --- | --- | | | 0.6 | [2,3] | Dirichlet(2, 3) | 在表达式 `infer.Dirichlet[2].pseudocount(V)` 中，`Dirichlet[2]` 表示要提取属性的分布类型，`pseudocount` 是要提取的参数的名称（在Tabular中，所有分布都有命名参数），`V` 是定义分布的列。 所有包含依赖于查询结果的计算的列都处于 `qry` 空间。该空间中的列只能通过 `infer` 运算符引用随机变量。 添加 `infer` 运算符后，Tabular中现在有三种不同类型的列： - 确定性列：其值在推理前已知。 - 随机列：其分布需要推断，可能依赖于确定性列。 - 查询列：依赖于推断分布。 这些列的值或分布（在所有行中）必须按正确的顺序计算，例如，随机列不能依赖于查询结果。为了确保程序中没有错误的依赖关系，列被分为三个空间：`det`、`rnd` 和 `qry`；空间注释确保了列之间依赖关系的约束得以保留。 ### 2.4 相关工作 概率编程正成为一种越来越流行的贝叶斯推理方法，最近出现了许多遵循不同范式的新语言。这些语言包括函数式语言（如Fun、Church、Anglican、Venture、WebPPL和monad - bayes）、过程式语言（如R2、Infer.NET和Stan）、逻辑语言（如ProbLog），甚至还有概率过程代数ProPPA的实现。最近，一类将贝叶斯建模与深度神经网络相结合的新概率语言也应运而生，例如Pyro和ProbTorch。 设计语言需要在表达能力和性能之间进行权衡。在这方面，概率语言大致可分为两类： - 通用的图灵完备语言：如R2和Church及其派生语言，允许创建任意概率模型（包括具有无限数量随机变量的非参数模型），但只能使用有限范围的基于采样的推理算法。 - 更受限的语言：如Infer.NET和BUGS，其中的模型对应于因子图，因此可以使用更广泛的推理算法，包括因子图算法。Tabular属于第二类，使用期望传播作为其默认推理算法。 在范式和用户界面方面，与Tabular最相关的两个概率编程包是BayesDB和Scenarios。BayesDB是一个基于关系数据库模式的概率包，其建模语言是SQL的概率扩展，与Tabular直接注释数据库模式的方法有很大不同。Scenarios是一个商业Excel插件，允许在电子表格环境中定义概率模型。Scenarios与Tabular的区别在于，前者浅嵌入Excel中，通过特殊的Excel函数定义概率模型，而Tabular是一个独立的概率语言，仅将Excel用作方便的开发环境。由于Scenarios浅嵌入在动态类型的公式语言中，它没有静态类型系统。 ### 2.5 回顾与相关项目 Tabular最初是一种基于数据库模式的语言，以GUI程序的形式独立实现，可直接与关系数据库交互。该语言的初始版本不支持函数，模型要么是简单表达式，要么是来自小型固定库的预定义共轭模型。Tabular有一个无空间的非依赖类型系统，其中模式的类型是嵌套记录类型的五元组，其组件指定了由表定义的模型的超参数、参数、输入以及潜在和观察变量的类型。Tabular的语义通过转换为一阶函数式概率编程语言Fun来定义，推理结果的后处理必须在Tabular之外完成。 Gordon等人（2015）描述的语言修订版增加了对用户定义函数和查询的支持。原始类型系统被一个更简单的类型系统所取代，其中类型本身与核心Tabular表具有相似的形式。新的类型系统支持基本的依赖类型，并提供空间注释，将列分为确定性、随机和查询列。新版本Tabular的语义包括一个将带有函数和索引的模式简化为核心形式的归约系统，以及核心Tabular模型的语义（本章省略，详见上述论文的长版本），该语义直接根据测度理论定义。归约为核心形式被证明是类型安全的。 Szymczak（2018）的博士论文对Tabular进行了进一步改进，引入了双列名以解决α - 转换问题，并给出了模式归约类型安全性的更严格证明。该论文还描述了一种新的、更严格和优雅的核心Tabular模型语义。 Borgström等人（2016）提出的Fabular在Tabular的基础上扩展了分层线性回归公式，类似于R包（如lmer）中使用的公式表示法。这些公式允许简洁地表示广泛的模型，并且可以像其他模型表达式一样在Tabular中使用。 此外，Hutchison（2016）在其硕士论文中提出了一种生成式语法，允许动态创建Tabular程序，这可以作为Tabular自动模型建议工具的基础。因此，Tabular被用于研究濒危植物标本的互联网贸易。 ## 3. Tabular的语法 ### 3.1 数据库的语法 Tabular数据库是一个元组 `DB = (δin, ρsz)`，由两个映射组成，其定义域是数据库中表的名称集合。 - 第一个映射 `δin = [ti ↦ τi i∈1..n]`：将每个表映射到另一个映射 `τi = [cj ↦ aj j∈1..mi]`，该映射将每个列 `ci` 映射到一个属性 `ai`。属性 `aj = ℓj(Vj)` 由一个级别 `ℓj` 和一个值 `Vj` 组成，`Vj` 可以是标量（即整数、实数或布尔值）或值的数组。属性的级别可以是 `static`（表示给定列在所有行中只有一个值）或 `inst`（表示该列每行有一个值）。在后一种情况下，`Vj` 实际上是一个值的数组，每行一个值。列名 `cj` 的形式与模式中的外部列名相同（如下所述），但不允许为空。 - 第二个映射 `ρsz = [ti ↦ szi i∈1..n]`：简单地存储表的大小。表 `ti` 的每个 `inst` 级属性的值必须是大小为 `szi` 的数组。 数据库中的任何值 `Vj` 都可以为空，即任何静态属性都可以有一个空值（用 `?` 表示），并且在任何 `inst` 属性中，任何数量的组件值都可以为空。输出列某一行中的空值意味着该行和该列的分布需要由推理算法从其他数据中推断得出。 数据库、表、属性和值的语法定义如下： ```plaintext δin ::= [ti ↦ τi i∈1..n] table map c,o ::= b1.(...).bn column name ρsz ::= [ti ↦ szi i∈1..n] table size map a ::= ℓ(V) attribute value: V with level ℓ V ::= ? | s | [V0,...,Vn−1] nullable value ℓ, pc ::= static | inst level (static < inst) τ ::= [cj ↦ aj j∈1..m] table in database ``` 例如，第2.1节中TrueSkill示例的输入数据库使用数据库的形式语法可以写成如下形式： ```plaintext [Players ↦ [ID ↦ inst([0,1,2])], Matches ↦ [ID ↦ inst([0,1,2]),Player1 ↦ inst([0,1,0]), Player2 ↦ inst([1,2,2]),Win1 ↦ inst([0,0,?])] ``` 其中，玩家姓名被省略（因为它们对模型不重要，并且Tabular的形式语法不允许字符串），真和假分别用1和0表示。 ### 3.2 核心模式的语法 我们首先给出核心模式的语法，这些模式可以直接解释为因子图。我们先定义Tabular列的基本构建块。 #### 索引表达式、空间和依赖类型 ```plaintext e ::= index expression x variable s scalar constant sizeof(t) size of a table S ::= bool | int | real scalar type spc ::= det | rnd | qry space T,U ::= (S ! spc) | (mod(e) ! spc) | T[e] (attribute) type c,o ::= _ | b1.(...).bn external column name space(S ! spc) ≜ spc space(mod(e) ! spc) ≜ spc space(T[e]) ≜ space(T) ``` 索引表达式可以是常量、变量（引用前一列或数组索引）或 `sizeof` 表达式，返回给定表的大小（即如果 `ρsz` 是表大小的映射，`sizeof(t)` 返回 `ρsz(t)`）。标量类型是 `bool`、`int` 或 `real` 之一，对应于传统语言中的标量类型。列的空间作为其类型的一部分，可以是 `det`、`rnd` 或 `qry`，分别表示该列是确定性的、随机的或查询级别的。属性类型可以是带有空间的标量类型 `S`、由索引表达式 `e` 定义边界的依赖有界整数类型 `mod(e)` 并带有空间，或者是递归定义的数组类型 `T[e]`，其中 `T` 是任意类型，`e` 是定义数组大小的索引表达式。我们使用 `link(t)` 作为 `mod(sizeof(t))` 的简写。外部列名用于引用另一个表中的列或访问简化函数体的字段，它可以为空（用 `_` 表示），也可以由一个或多个用点分隔的原子名称 `bi` 组成。 `space` 运算符用于返回给定类型中嵌套的唯一空间注释。 例如，第2.2节中 `Coins` 表的 `Flip` 列的类型 `mod(2)!rnd` 表示一个有界的随机非负整数值表达式，界限为2（即只允许值0和1）。根据 `space` 的定义，`space(mod(2)!rnd) = rnd`。此外，第2.2节中 `CDiscrete` 的 `V` 列的类型 `real!rnd[N]` 表示一个大小由变量 `N` 确定的实数数组，其元素的类型都是 `real!rnd`（即随机实数值表达式）。该类型的空间为 `space(real!rnd[N]) = space(real!rnd) = rnd`。 #### 表达式 ```plaintext E, F ::= expression e index expression g(E1,..., En) deterministic primitive g D[e1,...,em](F1,..., Fn) random draw from distribution D if E then F1 else F2 if-then-else [E1,..., En] | E[F] array literal, lookup [for x < e →F] for loop (scope of index x is F) infer.D[e1,...,em].c(E) parameter c of inferred marginal of E E : t.c dereference link E to instance of c t.c dereference static attribute c of t ``` 这个表达式语法主要是标准的一阶概率函数式语言，用于定义表中特定列的模型。表达式 `D[e1,...,em](F1,..., Fn)` 表示从具有由索引表达式 `e1,...,em` 确定的超参数和由表达式 `F1,..., Fn` 定义的参数的原始分布 `D` 中抽取一个样本。运算符 `infer.D[e1,...,em].c(E)` 返回表达式 `E` 的后验分布的参数 `c` 的近似值，预期 `E` 的形式为 `D[e1,...,em]`。通过运算符 `t.c` 和 `E : t.c` 可以访问前面表中定义的列，分别引用表 `t` 中全局名称为 `c` 的静态属性和表 `t` 中全局名称为 `c` 的 `inst` 级属性的第 `E` 行。我们假设存在一个固定（但可扩展）的分布和确定性原语集合，如加法、乘法和比较。 分布签名由 `spc` 参数化，以区分相应分布在随机模型和查询中的使用。分布的签名包括： ```plaintext Distributions: Dspc : [x1 : T1,..., xm : Tm](c1 : U1,...,cn : Un) →T Bernoullispc : (bias : real!spc) →bool!rnd Betaspc :: (a : real!spc,b : real!spc) →real!rnd Discretespc : [N : int!det](probs : real!spc[N]) →mod(N)!rnd Dirichletspc : [N : int!det](pseudocount : (real!spc)[N]) →(real!rnd)[N] Gammaspc : (shape : real!spc,scale : real!spc) →real!rnd Gaussianspc : (mean : real!spc,variance : real!spc) →real!rnd VectorGaussianspc : [N : int!det](mean : (real!spc)[N],covariance : real!spc[N][N]) → (real!rnd[N]) ``` 分布的参数名称是固定的，不可进行α - 转换，因为它们可以被 `infer` 运算符按名称引用。 随机抽样和 `infer` 运算符在第2.2节和第2.3节