Toward Formal Data Set Verification for Building Effective Machine Learning Models

Jorge López, Maxime Labonne, Claude Poletti

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.

Introduction: The "Garbage In, Garbage Out" Problem

The "Garbage In, Garbage Out" principle remains the primary challenge in Machine Learning. If a training dataset is biased, underrepresents certain classes, or fails to cover the entire input space, the resulting model will inevitably 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 training begins.

Methods: Encoding Data as Logic

The authors propose a formal verification pipeline that moves beyond ad-hoc manual checks by treating datasets as mathematical constraints. The process consists 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 logical assertions.
  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 Z3 solver. The solver checks for "satisfiability": if the conjunction of the data and the property is Satisfiable, the property holds; if it is Unsatisfiable, the property is violated.
Algorithm 1: The process for encoding a dataset into a Many-Sorted First Order Logic (MSFOL) formula.

The authors implemented this approach in a prototype tool called Dsverif, developed in Julia. The encoding process, detailed in Algorithm 1, iterates through training examples and features to build a comprehensive logical representation of the input space.

Key Insights and Ideas

  • Data as Logic: The core innovation 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 to verify properties like class balance.
  • The "Unknown" Verdict: SMT solvers have limits. For highly complex properties involving quantifiers over large arrays, the solver may return "Unknown," indicating a computational boundary for very large datasets.

Key Results and Performance

The prototype successfully verified several critical properties, including sample count ($\pi_{\#}$), min-max normalization ($\pi_{\pm}$), and class balance ($\pi_{\equiv}$).

Performance scaling of the verification tool across different properties as the number of training examples (m) increases.

As shown in Figure 1, verification for the tested scales was extremely fast, often taking less than 0.15 seconds for hundreds of training examples. While simple properties like sample counts scale linearly, more complex properties involving class balance show more significant increases in computation time, though they remain manageable at these scales.

Limitations and Future Work

Despite the promise of formal verification, several challenges remain:

  • The Scalability Wall: SMT solving is computationally expensive (often exponential in the worst case). 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 complex.
  • Unstructured Data: The current framework only handles structured (tabular) data. Extending this to images, audio, or text remains a significant challenge for future research.

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