基于形式语言的通用信息抽取框架

《Information and Computation》：A general information extraction framework based on formal languages

　　

摘要专业翻译 对于终端字母表Σ和属性字母表Γ，一个(Σ, Γ)-抽取器（extractor）是一个函数，它将Σ上的每个字符串w映射到一个表（table），该表的每一列对应一个属性，单元格条目为w的位置集合。这一相当通用的信息抽取框架扩展了著名的文档跨度器（document spanner）框架，后者在过去十年间已在数据库理论领域得到深入研究。此外，本框架以特别简洁明了的方式建立在形式语言理论（formal language theory）基础之上。除这一概念性贡献外，研究人员还研究了抽取器的闭包性质（closure properties）、不同的表示形式体系（representation formalisms）以及自然决策问题（decision problems）的复杂性。

论文解读文章

一、研究背景与研究动机

信息抽取（information extraction）是数据库理论中一个重要的数据查询范式，其核心任务是从文本数据中提取结构化的关系表。在过去十余年间，文档跨度器（document spanner）框架作为信息抽取领域最著名的实例，受到了数据库理论界的广泛关注。文档跨度器基于跨度（span）的概念，即字符串中两个位置所界定的连续子串，从输入字符串中提取以跨度作为单元格条目的关系表。然而，文档跨度器框架存在一定的局限性：其单元格条目被严格限制为恰好两个位置所构成的连续区间，这在一定程度上限制了其表达能力。

研究人员提出了一种更为通用的信息抽取框架，其动机主要来自三个方面。第一，文档跨度器研究中已开发的多种深层算法技术（如参考文献[7]、[21]、[23]、[24]中的成果）在更一般的设定下无需额外工作即可适用，因此有必要正式定义并研究这一更一般的设定。第二，该通用框架能够以更简洁的方式嵌入经典形式语言理论，即抽取器类与形式语言类之间的等价关系更加明确，从而可作为面向形式语言与自动机理论研究者的一种接口。第三，该信息抽取框架在语言描述符（language descriptors）与转换器（transducers）之间占据了一个有趣的位置，值得纯粹从形式语言理论的角度加以研究，而非仅聚焦于数据库理论中的数据处理任务。

二、研究内容与核心结论

研究人员首先正式定义了(Σ, Γ)-抽取器（extractor）的概念：对于终端字母表Σ和属性字母表Γ，一个(Σ, Γ)-抽取器是将Σ*上的每个字符串w映射到一个Γ-表（Γ-table）的全函数，其中Γ-表是Γ-元组（Γ-tuple）的集合，每个Γ-元组是从属性集合Γ到字符串w的位置集合的幂集的函数。这一框架通过将文档跨度器中的跨度（恰好两个位置）替换为任意位置集合，自然地将文档跨度器框架作为特例包含在内。

该框架的核心创新在于其与形式语言理论的紧密联系。研究人员证明了抽取器可以被自然地视为形式语言：每个抽取器E都对应一个标记语言（marker language）L_E，该语言中的每个字符串是对输入字符串w的带注释版本，其中每个位置上的标记（marker）指示该位置属于哪些属性的条目集合。这种对应关系是双射（bijection）的，意味着抽取器的研究可以完全在声明式的形式语言层面进行，无需依赖操作式的机器模型。

在此基础上，研究人员在抽取器上定义了多种运算，包括集合运算（并、交、差、补）、连接变体（乘积、自然连接以及三种广义连接?∪、?∩、?_?）、连接（concatenation）与Kleene星（Kleene star）、投影（projection）、合并（merge）以及属性重命名（attribute renaming）。这些运算在标记语言层面均有对应的自然语言运算，且解释映射?·?是同态（homomorphism），这意味着抽取器的复合可以在标记语言层面直接进行。

研究人员重点研究了由正则语言和上下文无关语言所描述的抽取器类，即正则抽取器（regular extractors）和上下文无关抽取器（context-free extractors），证明了正则抽取器对上述所有抽取器运算均具有闭包性质（closure properties），并考察了不同的表示形式体系以及若干自然决策问题（decision problems）的计算复杂性。

三、关键技术与方法

研究人员采用的核心方法是将信息抽取问题完全转化为形式语言理论中的经典问题来处理。具体而言，研究人员定义了Σ-带符号Γ-标记字母表Δ_Σ,Γ，其中每个符号为X_b形式，X?Γ为标记集合，b∈Σ为符号（sign）。通过编码映射enc_Σ,Γ，每个(w, t)对（其中w为终端字符串，t为Γ-元组）被唯一地编码为一个带符号标记字符串，从而建立了抽取器与标记语言之间的双射关系。基于这一对应关系，抽取器的各类运算被转化为标记语言上的对应运算，抽取器的闭包性质研究被归结为相应语言类的闭包性质研究，决策问题的复杂性分析也被转化为对正则语言和上下文无关语言的经典复杂性分析。此外，研究人员还利用了正则语言类和上下文无关语言类的经典闭包性质（如正则语言对并、交、补、连接、Kleene星等运算的封闭性）来证明正则抽取器的闭包性质。

四、研究结果

4.1 框架的正式定义（第2节）

研究人员正式定义了(Σ, Γ)-抽取器的概念，包括Γ-元组、Γ-表、支撑集（support）、有限支撑、空Γ-抽取器等基本概念，并通过示例说明了抽取器如何从具体字符串中提取关系表。该框架仅需少量基本定义即可完整表述，体现了其简洁性。

4.2 抽取器上的运算（第3节）

研究人员定义了抽取器的集合运算（并、交、差、补）、连接变体（乘积、自然连接、广义连接）、连接与Kleene星以及其他一元运算（投影、合并、属性重命名），并证明了连接的结合性（Proposition 3.1）。这些运算均来源于关系代数中的典型运算，同时连接与Kleene星的引入为后续的形式语言表述奠定了基础。

4.3 抽取器作为形式语言（第4节）

研究人员建立了抽取器与标记语言之间的双射对应关系（Proposition 4.3），定义了Σ-带符号Γ-标记语言的概念，并证明了抽取器运算与标记语言运算之间的同态性（Theorem 4.6、4.7、4.8）。这一部分是该论文的核心概念贡献，使得抽取器的研究可以完全在声明式的形式语言层面进行。

4.4 正则与上下文无关抽取器（第5节）

研究人员定义了正则抽取器和上下文无关抽取器类，即由正则标记语言和上下文无关标记语言所描述的抽取器。这些类继承了正则语言和上下文无关语言的若干优良性质，正则抽取器对所有在第3节中定义的抽取器运算均具有闭包性质，该结论通过将抽取器运算解释为标记语言运算并利用正则语言的闭包性质来证明。

五、讨论与结论

论文的讨论部分指出，该通用信息抽取框架与经典形式语言理论的嵌入比文档跨度器框架更加明确和简洁：抽取器类与形式语言类之间的等价关系是直接的，无需通过操作式的机器模型来刻画。该框架在语言描述符与转换器之间占据了一个有趣的位置，为形式语言和自动机理论研究者提供了一个特别定制的接口。研究人员还考察了正则抽取器和上下文无关抽取器的不同表示形式体系以及若干自然决策问题的计算复杂性，这些结果进一步验证了该框架的理论价值。

研究结论表明，所提出的基于形式语言的通用信息抽取框架是对文档跨度器框架的合理且自然的推广，它不仅统一了已有的大量算法技术，而且为形式语言理论研究者提供了一个更直接、更简洁的接口来研究信息抽取问题。该框架的闭包性质、表示形式体系以及决策问题复杂性的研究结果，为未来在更广泛的语言类上研究信息抽取问题奠定了理论基础。