2025-11-14T02:49:11.540996

Iterative Data Curation with Theoretical Guarantees

Jonasson, Magnusson
In recent years, more and more large data sets have become available. Data accuracy, the absence of verifiable errors in data, is crucial for these large materials to enable high-quality research, downstream applications, and model training. This results in the problem of how to curate or improve data accuracy in such large and growing data, especially when the data is too large for manual curation to be feasible. This paper presents a unified procedure for iterative and continuous improvement of data sets. We provide theoretical guarantees that data accuracy tests speed up error reduction and, most importantly, that the proposed approach will, asymptotically, eliminate all errors in data with probability one. We corroborate the theoretical results with simulations and a real-world use case.
academic

Iterative Data Curation with Theoretical Guarantees

基本信息

  • 论文ID: 2510.11428
  • 标题: Iterative Data Curation with Theoretical Guarantees
  • 作者: Väinö Yrjänäinen, Johan Jonasson, Måns Magnusson
  • 分类: stat.ME (Statistics - Methodology)
  • 发表时间: 2025年10月13日 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.11428v1

摘要

随着大规模数据集的日益普及，数据准确性（即数据中没有可验证错误）对于高质量研究、下游应用和模型训练变得至关重要。本文针对大规模数据集中数据准确性改进的挑战，提出了一个统一的迭代数据集持续改进程序。研究提供了理论保证，证明数据准确性测试能够加速错误减少，更重要的是，所提出的方法将渐近地以概率1消除数据中的所有错误。理论结果通过仿真实验和真实世界用例得到验证。

研究背景与动机

问题定义

本研究要解决的核心问题是：如何在大规模数据集中系统性地改进数据准确性，特别是当数据规模过大而无法进行人工整理时。

问题重要性

  1. 数据质量的关键性：高质量数据对于机器学习预测、统计推断、决策制定和可靠预测模型训练至关重要
  2. 现实挑战：常用的机器学习数据集如Fashion MNIST、Common Crawl、Wikipedia语料库等都包含大量错误，缺乏准确性保证
  3. 规模限制：传统的人工整理方法在大规模数据集上不可行

现有方法局限性

  1. 基于规则的算法：虽然能同时纠正数千个错误，但没有准确性保证，通常伴随不可忽略的错误率
  2. 众包和外部数据源：同样存在不可忽略的错误率
  3. 缺乏理论保证：现有方法无法提供收敛到无错误数据集的理论保证

研究动机

论文旨在建立一个具有理论保证的可扩展数据整理框架，能够在最小人工开销下实现高质量的迭代更新。

核心贡献

  1. 迭代整理框架：提出了一个针对大规模文本和表格数据集的结构化可扩展数据准确性改进流程
  2. 理论保证：证明了渐近收敛到无错误数据集、错误的指数衰减以及每次数据修订时错误减少率的期望保证
  3. 实验验证：通过仿真实验和瑞典议会语料库的真实案例研究支持理论结果
  4. 噪声容忍性：证明了方法对噪声预言机（noisy oracle）的鲁棒性

方法详解

任务定义

输入：包含错误的初始数据集 S0∈SS_0 \in S输出：经过迭代改进后趋于无错误的数据集序列 {St}\{S_t\}目标：lim⁡t→∞P(Et=0)=1\lim_{t \to \infty} P(E_t = 0) = 1，其中 Et=d(S∗,St)E_t = d(S^*, S_t) 为错误数量

模型架构

迭代整理流程

整个流程包含四个主要步骤，其中后三步循环执行：

步骤1：建立原型

  • 创建最小可行的原型数据集
  • 定义合适的数据格式 SS（人类可读且易扩展）
  • 进行彻底的人工检查和验证

步骤2：创建修订提案

  • 生成修订提案 Rt+1∈SR_{t+1} \in S
  • 包括两种类型：添加（扩展数据）和纠正（修正错误）

步骤3：接受或拒绝提案

  • 3.1 自动数据测试：格式验证、内容合理性检查
  • 3.2 编辑采样：从编辑集合 Δt=Δ(Rt+1,St)\Delta_t = \Delta(R_{t+1}, S_t) 中随机采样 nn 个编辑
  • 预言机验证：人工检查采样编辑的正确性
  • 决策规则：当正确编辑数量 ≥m\geq m 时接受提案

步骤4：发布新版本

  • 使用语义版本控制标记变更类型（MAJOR/MINOR/PATCH）

技术创新点

1. 分支过程建模

将错误数量建模为随机环境中的分支过程（BPRE），其中：

  • p0,t=(1−rt)λtp_{0,t} = (1-r_t)\lambda_t：错误减少概率
  • p1,t=1−λtp_{1,t} = 1-\lambda_t：错误不变概率
  • p2,t=rtλtp_{2,t} = r_t\lambda_t：错误增加概率

2. 理论保证机制

通过控制接受阈值 (n,m)(n,m)，确保： Ert,λt[log⁡E[ζ]∣M≥m]<0E_{r_t,\lambda_t}[\log E[\zeta] | M \geq m] < 0

这保证了分支过程的次临界性，从而实现错误的指数衰减。

3. 数据格式适应性

为两种主要数据格式提供了具体实现：

  • 表格数据：使用汉明距离
  • 序列数据：使用加法-删除编辑距离

实验设置

数据集

  1. 仿真数据：
    • 直接仿真错误数量 EtE_t，错误率 rt∼Beta(α,β)r_t \sim \text{Beta}(\alpha, \beta)
    • 100万词的英文Wikipedia序列，初始包含约1万个错误
  2. 真实数据：瑞典议会记录语料库
    • 17,938个议会记录（1867-2024年）
    • 超过5亿词，ParlaClarin XML格式

评价指标

  • 错误数量 Et=d(S∗,St)E_t = d(S^*, S_t)：与真实数据的距离
  • 收敛率：错误指数衰减的速度
  • 特定准确性指标：议员映射错误、段落分类错误

对比方法

  • 有决策规则 vs 无决策规则
  • 不同阈值 m/nm/n 的比较（0.4, 0.5, 0.6等）
  • 真实预言机 vs 噪声预言机

实现细节

  • 采样大小：n=10,50n = 10, 50
  • 接受阈值：通常 m/n≈0.5m/n \approx 0.5
  • 噪声预言机：噪声率 ε=0.2\varepsilon = 0.2

实验结果

主要结果

1. 收敛性验证

  • 指数衰减：在对数尺度上观察到错误数量的线性减少
  • 阈值效应：m/n=0.6m/n = 0.6 在 n=10n=10 时优于 m/n=0.5m/n = 0.5；n=50n=50 时相反
  • 决策规则效益：即使在高度乐观的 rt∼Beta(1,4)r_t \sim \text{Beta}(1,4)（94%提案改进数据）情况下，决策规则仍能加速收敛

2. 文本数据仿真

  • 有决策规则：EtE_t 指数减少（均值和分位数）
  • 无决策规则：
    • rt∼Beta(1,1)r_t \sim \text{Beta}(1,1) 时均值保持静态，方差增加
    • rt∼Beta(5,3)r_t \sim \text{Beta}(5,3) 时 EtE_t 指数增加

3. 真实案例结果

瑞典议会数据的两个关键指标均显示持续改进：

  • 议员映射错误：从 10310^3 量级减少到更低水平
  • 段落分类错误：保持在较低水平或继续减少

消融实验

自动测试的效果（定理3.8）

证明了自动数据测试能够加速收敛： P(Et=0∣E0=E)<P(Et′=0∣E0′=E)P(E_t = 0 | E_0 = E) < P(E'_t = 0 | E'_0 = E)

噪声预言机的鲁棒性（定理3.4）

通过调整阈值 mnoisy=m/(1−ε)m_{noisy} = m/(1-\varepsilon)，噪声预言机达到与真实预言机相似的收敛性能。

实验发现

  1. 阈值优化：最优 mm 值趋向于 n/2n/2（当 n→∞n \to \infty）
  2. 规模效应：更大更准确的修订加速错误衰减
  3. 实用性：方法在真实大规模数据集上表现良好

相关工作

数据质量研究

  • 传统方法：基于规则的算法、正则表达式、机器学习方法
  • 众包方法：非专家标注者、外部数据源
  • 局限性：缺乏准确性保证，通常引入新错误

理论贡献

  • 分支过程理论：Smith and Wilkinson (1969) 的随机环境分支过程
  • 本文创新：首次将BPRE应用于数据整理问题并提供收敛保证

软件工程借鉴

  • 版本控制：类似git的提交和版本管理
  • 语义版本控制：Preston-Werner (2013) 的版本标记方法

结论与讨论

主要结论

  1. 理论保证：在适当条件下，迭代整理过程以概率1收敛到无错误数据集
  2. 指数收敛：错误数量呈指数衰减，收敛速度取决于修订质量和规模
  3. 实用性：方法适用于大规模文本和表格数据，已在真实项目中验证

局限性

  1. 假设条件：
    • 需要存在真实数据 S∗S^* 的概念
    • 要求编辑的可加性（对某些数据格式可能不成立）
    • 序列数据需要满足无重复元素等额外假设
  2. 预言机依赖：虽然证明了对噪声的鲁棒性，但仍需要人工验证
  3. 计算复杂性：未详细分析大规模数据集上的计算开销

未来方向

  1. 扩展数据格式：研究更复杂数据结构（如图数据、多模态数据）的适用性
  2. 主动学习：结合主动学习策略优化编辑采样
  3. 自动化程度：减少对人工预言机的依赖

深度评价

优点

  1. 理论严谨性：提供了完整的理论分析和证明，填补了数据整理领域理论保证的空白
  2. 实用价值：方法已在大规模真实项目中应用并取得良好效果
  3. 通用性：框架适用于多种数据格式（表格、文本）
  4. 工程化思维：借鉴软件工程最佳实践，具有良好的可操作性

不足

  1. 假设限制：某些假设（如序列无重复元素）在实际应用中可能过于严格
  2. 人工成本：尽管提高了效率，仍需要大量人工验证工作
  3. 收敛速度：虽然理论上保证收敛，但实际收敛速度可能较慢
  4. 错误类型：主要关注可验证的客观错误，对主观标注问题适用性有限

影响力

  1. 学术贡献：首次为数据整理提供理论保证，可能开创新的研究方向
  2. 实践价值：为大规模数据项目提供了系统性的质量改进方法
  3. 可复现性：提供了完整的实现细节和补充材料

适用场景

  1. 大规模文本语料库：如议会记录、法律文档、历史档案
  2. 表格数据库：需要持续维护和改进的结构化数据
  3. 机器学习数据集：需要高质量标注的训练数据
  4. 长期数据项目：需要版本控制和质量跟踪的数据集

参考文献

论文引用了丰富的相关文献，主要包括：

  1. 数据质量研究：Olson (2003), Jain et al. (2020), Budach et al. (2022)
  2. 分支过程理论：Smith and Wilkinson (1969), Guivarc'h and Liu (2001)
  3. 实际数据集：Common Crawl (2024), Wikipedia contributors (2023)
  4. 软件工程：Preston-Werner (2013), Torvalds et al. (2005)

总体评价：这是一篇理论与实践并重的高质量论文，为数据整理这一重要但缺乏理论基础的领域提供了严谨的数学框架。虽然存在一些假设限制，但其理论贡献和实用价值都很显著，对相关领域具有重要的推动作用。