PaperlayerView exact revision on arXiv

Source-linked AI summary

HoloClean: Holistic Data Repairs with Probabilistic Inference

Theodoros Rekatsinas, Xu Chu, Ihab F. Ilyas, Christopher Ré

arXiv:1702.00820v1cs.DB

TL;DR

Large-scale data cleaning must repair inconsistent, missing, and duplicate data, while existing repairing methods often rely on only one useful signal. HoloClean unifies integrity constraints, external data, and quantitative statistics in a probabilistic framework with scalable inference optimizations. Across multiple datasets, it achieves about 90% average precision, about 76% average recall, and more than a 2× average F1 improvement over state-of-the-art methods.

  • Problem

    Existing data repairing methods often use only one signal, with average F1 below 0.35 across datasets and frequent failure to make correct repairs.

  • Method

    HoloClean automatically generates a probabilistic model that unifies integrity constraints, external data, and quantitative statistics, using inference optimizations for scalability.

  • Results

    Across multiple datasets, HoloClean achieves average precision of ∼90%, average recall of ∼76%, and more than a 2× average F1-score improvement against state-of-the-art data repairing methods.

  • Takeaways & Limitations

    HoloClean provides a common formal framework for data repairing and obtains significantly more accurate repairs than state-of-the-art data cleaning methods.

  • Takeaways & Limitations

    Multi-attribute integrity constraints can cause combinatorial explosion, while pairwise tuple correlations can produce quadratic-size factor graphs, requiring mechanisms to constrain assignments and interactions.

Abstract

from arXiv · show

We introduce HoloClean, a framework for holistic data repairing driven by probabilistic inference. HoloClean unifies existing qualitative data repairing approaches, which rely on integrity constraints or external data sources, with quantitative data repairing methods, which leverage statistical properties of the input data. Given an inconsistent dataset as input, HoloClean automatically generates a probabilistic program that performs data repairing. Inspired by recent theoretical advances in probabilistic inference, we introduce a series of optimizations which ensure that inference over HoloClean's probabilistic model scales to instances with millions of tuples. We show that HoloClean scales to instances with millions of tuples and find data repairs with an average precision of ~90% and an average recall of above ~76% across a diverse array of datasets exhibiting different types of errors. This yields an average F1 improvement of more than 2x against state-of-the-art methods.

1. INTRODUCTION

Large-scale data cleaning must address diverse inconsistencies while combining integrity constraints, external information, and dataset statistics. HoloClean unifies these signals in a probabilistic framework and introduces optimizations that make inference scale to millions of tuples.

  • Motivation: Data cleaning identifies and repairs incorrect, missing, duplicate, and constraint-violating data in modern analytics datasets.
  • Motivation: Existing repairing methods often rely on one signal, limiting their ability to use information needed for correct repairs.Constraint-based, external-data, and statistical methods each have distinct coverage or information limitations.
  • Our Approach: HoloClean unifies integrity constraints, external data, and quantitative statistics through an automatically generated probabilistic model.Its compiler produces a factor graph and supports error detection methods including constraint-violation and outlier detection.
  • Results: ∼90% average precision and ∼76% average recall were achieved across multiple datasets, with more than 2× average F1 improvement over state-of-the-art repairing methods.
  • Technical Challenges: 7× to 96,000× reductions in factor-graph size enabled HoloClean to scale inference to inputs with millions of tuples.The reductions came from limiting candidate value assignments and partitioning tuples when enumerating constraint correlations.
  • Technical Challenges: Relaxing hard integrity constraints to priors yields independent variables for which Gibbs sampling requires polynomially many samples to mix.The approximation was studied as a runtime–repair-quality trade-off and produced repairs of the same quality as non-approximate models.

2. THE HoloClean FRAMEWORK

HoloClean models uncertain cell values in a structured dataset and repairs detected errors using probabilistic inference. Its recall remains bounded by the upstream error-detection methods, while repair probabilities can support user feedback.

  • 2.1 Problem Statement: HoloClean identifies and repairs erroneous records in a structured dataset by estimating latent true cell values.
  • 2. THE HoloClean FRAMEWORK: HoloClean accepts a dirty database and repairing constraints, including denial constraints and matching dependencies.
  • 2. THE HoloClean FRAMEWORK: Error detection separates potentially inaccurate cells from clean cells, while users may supply any method for detecting errors.
  • 2. THE HoloClean FRAMEWORK: Compilation assigns noisy cells finite-domain random variables and builds a factor graph representing their probability distribution.
  • 2. THE HoloClean FRAMEWORK: Data repairing uses learned probabilities and inference to assign each noisy cell its most probable value.HoloClean applies empirical risk minimization to learn model parameters and computes marginal probabilities for candidate values.
  • 2. THE HoloClean FRAMEWORK: Recall is limited by the error-detection methods used, which are outside this paper’s scope.

3. BACKGROUND

HoloClean builds on factor graphs and DDlog to represent data-cleaning signals as a probabilistic model. Its variables encode possible facts or cell assignments, while weighted rules generate factors for inference.

  • Factor Graphs: Factor graphs represent random variables as nodes and factors as hyperedges with real-valued weights and factor functions.The resulting factorization defines the probability distribution over variable assignments, with a partition function ensuring a valid distribution.
  • DDlog: DDlog extends Datalog-like rules with probability-oriented annotations for specifying factor graphs in DeepDive.Rules derive relations through joins and scoped conditions, then extend them with question-mark relations and weights for probabilistic inference.
  • Random Variables: Grounding a question-mark relation creates one random variable for each relevant value, corresponding to nodes in the factor graph.For HoloClean, analogous variables represent assignments of values to dataset cells.
  • Inference Rules: Inference rules associate features with random variables by defining factor functions whose weights can vary across features.The example factor returns 1.0 for True and −1.0 otherwise, while feature-specific weights encode differing confidence levels.
  • Inference: Evidence variables are fixed, whereas query variables are inferred; learning estimates weights that maximize the probability of the evidence.During inference, the weights are treated as known and the query-variable values are the target of inference.

4. COMPILATION IN HOLOCLEAN

HoloClean compiles dataset transformations and heterogeneous repair signals into DDlog rules whose groundings construct the probabilistic model. The compilation supports quantitative features, external dictionaries, integrity constraints, and minimality priors.

  • Compilation Overview: HoloClean compiles quantitative statistics, external data, integrity constraints, and minimality into one DDlog program for repairing dataset D.Grounding the generated rules constructs the factors used in the probabilistic model.
  • Compilation Overview: Compilation first generates relations from D and then uses them to generate inference DDlog rules defining HoloClean’s probabilistic model.This two-step process separates input-derived relation construction from factor-rule generation.
  • Input Relations: The compiler creates Tuple, InitValue, Domain, and HasFeature relations to represent tuple identifiers, initial cell values, possible values, and cell features.These relations are automatically populated from D, its attribute domains, and distributional features such as values in the same tuple.
  • External Data: ExtDict stores values from multiple external dictionaries, identified by k, and matching rules populate Matched lookup results.A zip-code match can produce a candidate city value for a dataset tuple, with dictionary-specific reliability weights w(k).
  • Integrity Constraints: Denial constraints become DDlog factors over cell-value variables, while assigning w = ∞ makes them hard constraints and finite w makes them soft constraints.Larger finite weights place more emphasis on satisfying the constraints, whereas hard-constraint inference is generally computationally difficult.
  • Minimality Priors: The minimality prior favors fewer updated cells, with its strength controlled by a positive weight w.A stronger prior corresponds to the assumption that the input contains fewer erroneous than clean records.
  • Extensibility: The compilation architecture is extensible because additional external signals can be mapped to DDlog rules, after which factor-graph complexity is managed for efficient inference.The paper explicitly connects adding signals with subsequent optimizations for scaling inference.

5. SCALINGINFERENCEINHOLOCLEAN

HoloClean addresses inference scalability by pruning candidate domains and tuple interactions during grounding, then relaxing constraints to obtain rapidly mixing Gibbs sampling. These optimizations target combinatorial grounding growth and slow mixing while preserving repair quality within reported bounds.

  • Scalability challenges: HoloClean’s factor graph can grow combinatorially when complex rules correlate random variables with large domains.For the example constraints, grounding requires O(|T|^2 · |Z| · |S|^2) groundings.
  • Scalability challenges: Domain size and all-pairs tuple correlations are the two main sources of HoloClean’s grounding scalability problems.HoloClean addresses them with domain pruning based on co-occurrence statistics and tuple-pair pruning for denial constraints.
  • Domain pruning: Candidate repairs are restricted to attribute values whose conditional co-occurrence probability with another cell value exceeds threshold τ.The strategy uses Pr[v|v_c′] ≥ τ to determine whether candidate values co-occur.
  • Domain pruning: Varying τ trades off HoloClean’s scalability against repair precision and recall, and pruning was necessary for the largest evaluated dataset with 2.7 million tuples.The threshold controls the size of random-variable domains and affects both runtime and repair quality.
  • Tuple partitioning: Tuple partitioning restricts denial-constraint grounding to connected components of a conflict hypergraph instead of all tuple pairs.The resulting factor count is O(Σ_g∈G |g|^2) rather than O(|Σ||D|^2), with speed-ups up to 2× and average F1 loss below 0.5%.
  • Rapid mixing of Gibbs sampling: Relaxing denial-constraint rules yields independent random variables, for which Gibbs sampling mixes in O(n log n) steps and parameter learning is convex.The relaxed model does not penalize arbitrary simultaneous constraint violations, yet achieves the same repair quality as the non-relaxed model in the reported experiment.

6. EXPERIMENTS

The experiments evaluate HoloClean against state-of-the-art cleaning methods on synthetic and real-world datasets. They focus on repair accuracy, the contribution of different signals, and pruning effects on scalability and accuracy.

  • Experimental design: HoloClean is compared with state-of-the-art data cleaning methods across a variety of synthetic and real-world datasets.The evaluation includes four real datasets spanning hospital, flight scheduling, Chicago food inspection, and Medicare professional data.
  • Experimental design: The experiments test repair accuracy, the impact of different signals, and the effects of pruning methods on scalability and accuracy.Table 2 reports parameters for the evaluation data; noisy cells do not necessarily correspond to erroneous cells.

6.1 Experimental Setup

The evaluation uses four real-world datasets with varied sizes and error patterns, compares HoloClean with three repairing systems, and measures repair quality, runtime, and labeled ground truth.

  • Datasets: Four datasets cover hospital, flight, food-inspection, and physician information, spanning different sizes and error patterns.Hospital and Flights have ground truth for all cells; Food and Physicians require manual labeling.
  • Datasets: Hospital contains approximately 5% errors and substantial duplication, enabling evaluation of repairs that leverage duplicate information.The dataset has ground truth for all cells and is characterized as an easy benchmark.
  • Datasets: Flights contains conflicts across web data sources, with most cells noisy and source provenance available for evaluating robustness.Four denial constraints enforce unique scheduled and actual departure and arrival times for each flight.
  • Datasets: Food and Physicians contain respectively conflicting inspection records and systematic errors across medical-professional entries.Food errors are captured by seven denial constraints, while Physicians uses nine denial constraints to identify errors.
  • Evaluation: HoloClean is compared with Holistic, KATARA, and SCARE using precision, recall, F1-score, and wall-clock runtime.Food and Physicians use manually labeled samples of 2,000 and 2,500 cells, respectively, for evaluation.

6.2 Experimental Results

Across datasets, HoloClean outperforms competing repair methods, achieving large F1 gains while operating at runtimes that vary by dataset and method.

  • Overall results: More than 2× average F1-score improvement separates HoloClean from existing state-of-the-art repairing methods.The comparison covers all datasets and evaluates repair quality against competing approaches.
  • Overall results: More than 40% relative F1-score improvement occurs for HoloClean over other methods in every dataset.Table 3 reports precision, recall, F1-score, and the pruning threshold used for each dataset.
  • HoloClean performance: HoloClean reaches 100% precision and 71.3% recall on Hospital, 88.8% precision and 66.9% recall on Flights, and F1-scores of 0.783 and 0.897 on Food and Physicians.The reported performance reflects how duplicate information, source provenance, and dataset-specific error patterns affect repairs.
  • Competing methods: Logical-constraint repair performs poorly on noisy or randomly patterned datasets, with precision 0.0 for Flights and 0.14 for Food.Holistic performs around 50% F1 on datasets with substantial duplication or systematic errors.
  • Competing methods: KATARA produces very high precision but limited recall, while SCARE benefits from duplicate records and performs less effectively when duplicates are limited.KATARA’s limited recall is attributed to external knowledge-base coverage.
  • Runtime: HoloClean’s runtime is within one order of magnitude of Holistic on Hospital and Flights, but Food requires substantially more time and Physicians is in the same magnitude.KATARA is faster because it performs only matching operations; Table 4 uses a three-day nontermination threshold.

6.3 Micro-benchmark Results

Micro-benchmarks examine pruning, partitioning, constraint relaxation, external dictionaries, and marginal probabilities as tradeoffs between scalability and repair quality.

  • Domain pruning: Increasing pruning threshold τ raises precision but lowers recall; in Food, recall drops from 0.77 to 0.36 when τ increases from 0.5 to 0.7.Flights is an exception: severe pruning can reduce precision because correct values may be excluded when duplicates are scarce.
  • Domain pruning: Higher τ reduces repair time while leaving compilation runtime similar, supporting accurate repairs on Physicians with 37M cells.Runtime comparisons in Figure 4 use a log scale and focus on compilation and repair phases.
  • Model optimizations: Partitioning and denial-constraint features improve runtime by up to 2× when random-variable domains are large.When domains are heavily pruned, all HoloClean variants have comparable runtimes because grounding benefits from database optimizations.
  • Model optimizations: Relaxing denial constraints into features improves repair quality and can outperform complex constraint-factor models when domains are misspecified.The authors conjecture that limited noise and overly large domains contribute to this behavior, identifying formal analysis as future work.
  • External signals: External dictionaries improve F1-score by less than 1% across all datasets.The experiment uses a dictionary of U.S. ZIP codes, cities, and states with matching dependencies.

7. CONCLUSIONS

HoloClean unifies data-repairing methods under a statistical-learning and inference framework while scaling inference through optimizations. The study also identifies future work on constraint enforcement, theoretical guarantees, and integrating data programming with cleaning.

  • HoloClean unifies a range of data-repairing methods under a common formal framework based on statistical learning and inference.
  • Several optimizations scale inference for data repairing, with quality–runtime tradeoffs studied empirically.
  • HoloClean produces repairs that are significantly more accurate than state-of-the-art data-cleaning methods.
  • Future research includes determining when integrity constraints should be enforced versus encoded as features, alongside developing scalable tools with theoretical guarantees.
  • Another direction is unifying data programming and data cleaning in a probabilistic framework to improve error detection and repairing.
Loading 1702.00820v1…