Computing the g3-error with Relaxed Equality: Complexity, Algorithms and Visualization

The incorporation of domain knowledge (DK) in AI has been studied for years and turns out to be critical in practice. Functions are also a basic notion for dealing with data science projects and are somehow related to DK. Consider the following scenario. Let D ( y , z 1 , …, z n ) be a dataset, Alice a data scientist, Bob a domain expert and y = f ( z 1 , …, z n ) a function known to Bob from his background knowledge. Alice is interested in the following simple yet crucial questions: How to define the satisfaction of f in D ?How to measure that satisfaction efficiently?How does this satisfaction relate to the supervised learning task of learning f from D ? It turns out that these problems are related to the study of counterexamples through the use of functional dependencies (FDs) and, in particular, FD measures used to quantify their satisfaction in a dataset such as the g 3 indicator where the equality is replaced by more flexible predicates. In this paper, we first examine the complexity of computing g 3 . It is known that g 3 can be computed in polynomial time when using equality, while it becomes NP -hard when using general predicates. Our goal is to refine this dichotomy by studying the impact of the following common properties: reflexivity, transitivity, symmetry, and antisymmetry. We show that symmetry and transitivity together are sufficient to guarantee that the g 3 can be computed in polynomial time. However, removing one of them makes the problem NP -hard. Second, we study the computation of g 3 in the polynomial and NP -hard cases identified previously. We propose different exact and approximate solutions for the computation of g 3 in both cases. We compare these solutions in a detailed experimental study of time performance and approximation accuracy. All the algorithms are also made available via fastg3 , an open-source Python library with an underlying C++ implementation. Finally, we link counterexamples and g 3 to supervised learning with a web application called adesit . adesit is intended to be part of an iterative data refinement process right after data selection and just before the machine learning process itself. It provides a way to evaluate the ability of a dataset to perform well for a given supervised learning problem through statistical and visual exploration. In a last section, we validate our approach by applying it to the industrial problem of air gap monitoring in compact hydro-generators.