Toward Formal Data Set Verification for Building Effective Machine Learning Models

Jorge López, Maxime Labonne, Claude Poletti

TL;DR

This paper introduces a formal framework for verifying that machine learning datasets meet specific requirements—such as being balanced, normalized, or representative—before training begins. By encoding datasets and desired properties into First-Order Logic and using an SMT solver (Z3), the authors provide a way to mathematically prove whether a dataset is "fit for purpose," moving beyond ad-hoc manual checks.

What Problem Does This Paper Address?

The "Garbage In, Garbage Out" principle is the Achilles' heel of Machine Learning. If a training dataset is biased, underrepresents certain classes, or fails to cover the entire input space, the resulting model will likely fail to generalize to real-world scenarios.

While the industry has developed robust tools for verifying models, verifying the data itself remains a largely manual and overlooked task. Researchers often rely on simple heuristics or "collecting more data" in hopes of fixing biases, which is inefficient and often ineffective. This paper addresses the lack of a rigorous, automated, and formal method to ensure a dataset satisfies a set of arbitrary, user-defined properties before it is used for training.

Methods

The authors propose a formal verification pipeline consisting of three main steps:

  1. Dataset Encoding: Using a custom algorithm, a structured dataset (represented as a matrix of features and a vector of labels) is transformed into a Many-Sorted First Order Logic (MSFOL) formula. This treats the data not just as a file, but as a set of mathematical constraints.
  2. Property Specification: Desired characteristics of the data (e.g., "the dataset must have at least 100 samples" or "the data must be min-max normalized") are also written as MSFOL formulas.
  3. Formal Verification via SMT: The encoded dataset and the properties are fed into an SMT (Satisfiability Modulo Theories) solver, specifically the widely-used Z3 solver. The solver checks for "satisfiability":
  4. If the conjunction of the data and the property is Satisfiable, the property holds.
  5. If it is Unsatisfiable, the property is violated, helping developers diagnose missing or incorrect information.

The authors implemented this approach in a prototype tool called Dsverif, developed in Julia.

Datasets

The paper focuses on the formalism and feasibility of the method rather than benchmarking against massive public datasets.

  • Synthetic Example: The authors demonstrate the logic using a small, structured dataset (10 training examples, 2 features, and 3 distinct labels).
  • Incremental Testing: They evaluated the performance of their tool by incrementally increasing the number of training examples (up to 120) to observe how the solver's processing time scales.

Key Insights and Ideas

  • Data as Logic: The core "aha" moment is treating a static CSV file as a logical formula. This allows researchers to use decades of research in formal methods to "prove" things about their data.
  • Declarative Verification: Instead of writing custom Python scripts to check for every possible bias, a user can declare properties in a formal language (SMT-LIB). This is more flexible and less prone to "bugs in the checker."
  • Handling Loops via Recursion: Since First-Order Logic doesn't have a native concept of "loops," the authors suggest using recursive functions (like a counting function S(A, v, s)) to verify properties like class balance.
  • The "Unknown" Verdict: The paper highlights that SMT solvers aren't magic. For highly complex properties (like those involving quantifiers over large arrays), the solver may return "Unknown," indicating a limit in current computational logic for very large datasets.

Key Results

  • Feasibility: The prototype successfully verified properties like sample count ($\pi_{\#}$), min-max normalization ($\pi_{\pm}$), and class balance ($\pi_{\equiv}$).
  • Performance: For the tested scales, verification was extremely fast, often taking less than 0.15 seconds for hundreds of training examples.
  • Scalability Trends: Simple properties (like sample counts) scale linearly, while complex properties involving Euclidean distance or class balance show more significant (though still manageable at small scales) increases in computation time.

Limitations and Future Work

  • The Scalability Wall: SMT solving is computationally expensive (often exponential in the worst case). The authors acknowledge that verifying massive, million-row datasets will require more optimized strategies or Domain Specific Languages (DSLs) to reduce formula complexity.
  • Fictitious Repairs: While the solver can find a "satisfiable" model if a property fails, that model might contain "fictitious" data points that don't exist in reality, making automatic data repair tricky.
  • Unstructured Data: The current framework only handles structured (tabular) data. Extending this to images, audio, or text remains a significant challenge.
  • Future Direction: The authors plan to investigate DSLs to make it easier for non-logicians to write properties and to explore "automatic data repair" by identifying which specific samples cause a property to fail.

Summary updated

Abstract

In order to properly train a machine learning model, data must be properly collected. To guarantee a proper data collection, verifying that the collected data set holds certain properties is a possible solution. For example, guaranteeing that the data set contains samples across the whole input space, or that the data set is balanced w.r.t. different classes. We present a formal approach for verifying a set of arbitrarily stated properties over a data set. The proposed approach relies on the transformation of the data set into a first order logic formula, which can be later verified w.r.t. the different properties also stated in the same logic. A prototype tool, which uses the z3 solver, has been developed; the prototype can take as an input a set of properties stated in a formal language and formally verify a given data set w.r.t. to the given set of properties. Preliminary experimental results show the feasibility and performance of the proposed approach, and furthermore the flexibility for expressing properties of interest.
BibTeX
@inproceedings{lopez2021toward,
  author = {Jorge López and Maxime Labonne and Claude Poletti},
  title = {{Toward Formal Data Set Verification for Building Effective Machine Learning Models}},
  booktitle = {KDIR},
  year = {2021},
  url = {https://openreview.net/forum?id=sPqQ4g540IQ},
}

Loading related content...

Figure