从数据中学习树结构差异的规则，解释两棵树为何不同。
Learning Tree Pattern Transformations
- 用模式匹配语言描述树之间的变换规则。
- 证明了部分规则学习问题为NP难，揭示计算复杂性。
- 结合SAT求解器解决教育研究中的实际树差异分析。
在计算机科学中，解释一棵树 $t$ 与另一棵树 $t^ ext{⋆}$ 的结构差异是一个常见问题，尤其在处理如XML或JSON等树形数据时。本文探讨如何从样本数据中学习解释这类结构差异的规则：给定一组带标签、有序的树对 $igrace{(t_1, t_1^ ext{⋆}), igdots, (t_n, t_n^ ext{⋆})}$，是否存在一组小型规则能解释所有树对之间的结构差异？这引出两个核心问题：(i) 在此背景下，“规则”的合理定义是什么？(ii) 如何算法化地学习一组能解释数据集的规则？本文从数据库理论视角出发，(1) 提出一种基于模式的树变换规范语言；(2) 分析该算法问题多种变体的计算复杂性，例如证明某些极简情形下问题为NP-hard；(3) 探讨如何利用SAT求解器解决来自计算机科学教育研究的数据中的树差异问题。
原文摘要 · Abstract (English)
Explaining why and how a tree $t$ structurally differs from another tree $t^\star$ is a question that is encountered throughout computer science, including in understanding tree-structured data such as XML or JSON data. In this article, we explore how to learn explanations for structural differences between pairs of trees from sample data: suppose we are given a set $\{(t_1, t_1^\star),\dots, (t_n, t_n^\star)\}$ of pairs of labelled, ordered trees; is there a small set of rules that explains the structural differences between all pairs $(t_i, t_i^\star)$? This raises two research questions: (i) what is a good notion of "rule" in this context?; and (ii) how can sets of rules explaining a data set be learned algorithmically? We explore these questions from the perspective of database theory by (1) introducing a pattern-based specification language for tree transformations; (2) exploring the computational complexity of variants of the above algorithmic problem, e.g. showing NP-hardness for very restricted variants; and (3) discussing how to solve the problem for data from CS education research using SAT solvers.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。