arXiv:2607.04735cs.DBcs.LG2026-07

揭示多视图预训练中查询可识别性的本质限制与修复方法

Identifiability of Relational Queries in Multi-View Pretraining

  • 通过属性闭包构建可识别性判定算法CheckCert
  • 不可识别查询存在1/2的最小误差下界
  • 提出最小增补算法,可快速修复接口设计缺陷

当数据源通过共享接口整合时,下游查询的答案可能无法由接口暴露的信息唯一确定:两个全局一致的世界可能在所有共享属性上一致,却对查询结果有分歧。这种歧义是接口设计的结构性问题,而非数据量或模型大小所致,无法通过增加样本或扩大模型解决。本文形式化了在接口规则(跨所有合法世界一致成立的功能依赖)下的查询可识别性,并证明三个结论:(i) 一个多项式时间证书(CheckCert)通过属性闭包判定可识别性,在暴露残余歧义的实例上完全精确;(ii) 不可识别查询对任何仅使用接口证据的估计器均存在不可约的1/2最小极大误差下界,为多视图预训练系统设定了理论下限;(iii) 一种最小增补算法(Greedy-MinAug)可找到使查询可识别的最小接口添加集,归约为集合覆盖问题(对数近似)。在合成基准、涵盖学术、产品、餐厅三领域的真实集成数据集以及最大达10^3个属性的模式上,实验验证了CheckCert的精确性,两算法运行时间均在单位毫秒级,机器学习分类器表现出预测的误差下界和突变的能力提升。

原文摘要 · Abstract (English)

When data sources are integrated through a shared interface, a downstream query may or may not be determined by what the interface exposes: two globally consistent worlds can agree on every shared attribute yet disagree on the query answer. This ambiguity is structural -- a property of the interface design, not the data volume -- and cannot be resolved by collecting more records or training a larger model. We formalize query identifiability for data integration under interface laws (functional dependencies that hold uniformly across all legal worlds rather than within a single instance) and prove three results. (i) A polynomial-time certificate (CheckCert) decides identifiability via attribute closure, and is exact on instances that expose any residual ambiguity (closure-separable). (ii) Non-identifiable queries face an irreducible 1/2 minimax error floor for any estimator using only interface evidence, bounding multi-view pretraining systems from below. (iii) A minimum-augmentation algorithm (Greedy-MinAug) finds the smallest set of interface additions to certify a query, reducing to Set Cover (logarithmic approximation). Experiments on synthetic benchmarks, real integration datasets spanning three domains (scholarly, product, restaurant), and schemas up to 10^3 attributes confirm CheckCert is exact, both algorithms run in single-digit milliseconds, and ML classifiers exhibit the predicted error floor and abrupt capability gains.

多视图预训练查询可识别性数据集成理论分析

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。