Although to train predictive models Machine Learning approaches completely rely on data, the latter can dynamically evolve over time. This could make predictive models outdated due to the presence of possible data shifts, with a consequent decrease in prediction accuracy. Concept drift detection techniques aim to detect such shifts in order to adopt countermeasures and maintain predictive performance over time. To this end, drift detection methods aim to monitor data distribution shifts, trying to identify changes without evaluating model predictions. In this discussion paper, we present a profiling metadata-driven approach for quantifying concept drift. Specifically, we focus on Relaxed Functional Dependencies ( rfds) and formalize the relationship between changes in metadata and performance trends of the predictive models over time. Moreover, we define a suite of rfd-based metrics measuring the distance between two sets of data. To evaluate the proposed approach, we compared it with other distribution-based metrics on datasets with both known and unknown drift. Results proved that the proposed metrics are strongly correlated with the model's performance according to their trends. Moreover, the defined suite of metrics is also able to capture concept drift more efectively than traditional distribution-based approaches.
Machine Learning (ML) models are increasingly relied upon for a multitude of tasks, including
critical ones such as anomaly detection [
Profiling Metadata. Functional Dependencies (fds) describe relationships among two sets of attributes X and Y. Formally, an fd X → Y (X implies Y ) is satisfied if and only if for every pair of tuples (1, 2), whenever (1[] = 2[]), then (1[ ] = 2[ ]). The attribute set = 1, 2, . . . , ℎ represents the Left Hand Side (LHS) of the fd, whereas the set = 1, 2, . . . , is the Right Hand Side (RHS).
The definition of fd has been recently extended to address challenges associated with inaccurate real-world data, leading to Relaxed Functional Dependencies (rfds). The latter admit a limited number of violations (rfds relaxing on the extent, namely rfds) and/or the usage of similarity/distance functions as matching operators (rfds relaxing on the attribute comparison, namely rfds). In this paper, we leverage rfds only. Formally, given an instance of a relation schema , a constraint , over an attribute A ∈ attr(R), is a predicate ([], []) , where is a similarity (or distance) function, a comparison operator, and a threshold. A specific similarity/distance function is applied according to the nature of the attributes. Definition 1. (rfd). Given a relation schema , an rfd is denoted as Φ1 → Φ2 , where: = 1, 2, ..., ℎ and = 1, 2, ..., , with , ⊆ () and ∩ = ∅; and Φ 1 = ⋀︀∈ [](Φ 2 = ⋀︀∈ [ ], .), with ( , .) a conjunction of similarity/distance constraints on ( , .) and = 1, . . . , ℎ ( = 1, . . . , , .). Thus, given an instance r of R, we can state that r satisfies the rfd (i.e., r ⊨ ) if and only if for every pair of tuples (1, 2) ∈ , if Φ 1 is true then also Φ 2 returns true.
For the sake of simplicity and without loss of generality, in what follows, we consider rfds with a single attribute on the RHS, i.e., Φ1 → 2 . Moreover, we will refer to constraints defined through distance functions, with a comparison operator ( ≤ ) and the associated threshold.
For example, consider the tuples ranging from 0 to 6 of the dataset snippet shown in Figure 1a, then an example of holding rfd is: :Model≤ 4, Year≤ 1 → Price≤ 300, denoting that whenever two tuples have similar values on Model and Year, then they have a similar Price. +
Model Kia Picanto Renault Clio Ford Fiesta tdci
Fiat Panda Hyundai i10 1.0
Renault Clio Renault Clio dCi 2019 Year #Owners Price 6.000
Model , #Owners
Model , Year Year
, Price Model , Price Model , #Owners
Price Price Model Year
Year Price Year #Owners #Owners b)
Model , #Owners , Year
Price Year , Price
Model Model , Price , #Owners
Year Price
#Owners Year , #Owners #Model
The minimality property ensures that an rfd no longer holds after either () increasing one or more thresholds on the LHS, () reducing the LHS, or () decreasing the RHS threshold.
To leverage rfds in real-world scenarios, it is necessary to exploit discovery algorithms to
automatically infer the set of minimal rfds holding on a given dataset [
Updating rfds over time. Real-world data evolves over time following inserts, deletions, and updates of data, and rfds evolve accordingly. Specifically, after a tuple deletion, a given rfd
may be generalized by an rfd ′ that either has (i) larger thresholds on the LHS and/or a smaller threshold on the RHS, (ii) fewer attributes on the LHS, or (iii) both. Instead, after a tuple insertion, a given rfd can be specialized by one or more rfds ′′ that either have (i) smaller thresholds on the LHS and/or higher thresholds on the RHS, (ii) additional attributes on the LHS, or (iii) both. Notice that updates can be seen as a deletion followed by an insertion. Consider the tuples ranging from 0 to 6 shown in Figure 1a, and suppose that 1 gets deleted. The rfd :Model≤ 4, Year≤ 1 → Price≤ 300 still holds, but no longer minimal, since ′:Year≤ 1 → Price≤ 300 is also valid. On the other hand, suppose that tuple 7 is inserted, the rfd :Model≤ 4, Year≤ 1 → Price≤ 300 is no longer valid, since (2,7) and (4,7) violate . However, ′′ holds on the updated dataset: ′′:Model≤ 4, Year≤ 1, #Owners≤ 1 → Price≤ 300. In this study, we formalize how to exploit rfd evolution to quantify concept drift.
Relating rfds to Concept Drift. Consider a supervised ML setting, in which each instance
is composed of a feature vector and a target . Concept drift is a change in the joint distribution
(, ) between two time instants and + , i.e., (, ) ̸= +(, ) [
∈ Σ to verify if is somehow related to any rfd ′ ∈ Σ ′. Specifically, ∀
∈ Σ : (i) can also belong to Σ ′; (ii) can be specialized by at least one ′ ∈ Σ ′; or (iii) can neither belong to Σ ′ nor be specialized by any ′ ∈ Σ ′, meaning that has been invalidated.
Training Set
...
... ...
Model training g isnign ss es ce oc ro pr ep re Pr P ...... ...... ......
...
ML Model
RRFFDDDDisicsocoveveryry
RRFFDDFFiltielterr RRFFDDDDisicsocoveveryry
RRFFDDFFiltielterr RRFFDDDDisicsocoveveryry
RRFFDDFFiltielterr n on irsairsoisonsnoonsonnnon pparairairsraisoirsiso
i ommppaprar CDoCoCmompoCmompaompCmpao
CCom FRFRDFDFDRDFDFCRDFC
RRFRDFD
R R g n i r u s a e M s ess rree saeuseuarsau e iMft tM ftrDiDM rif Dr As an example, consider the sets of rfds Σ and Σ ′ provided in Figure 1b. Considering Σ , we can quantify its shift as follows: (i) 2 does not change, since it also belongs to Σ ′; (ii) 5 rfds are specialized in Σ ′ ( 0 and 1 are specialized by ′0, 3 and 4 by ′2, and 5 by ′3); and (iii) 6 is invalidated, since it does not belong to Σ ′ and there is no rfd in Σ ′ specializing it. Definition 3 (Shift from Σ ′ to Σ ). To quantify the divergence between Σ ′ and Σ , it is necessary to evaluate each rfd ′ ∈ Σ ′ to verify if ′ is somehow related to any rfd ∈ Σ . Specifically, ∀ ′ ∈ Σ ′: (i) ′ can also belong to Σ ; (ii) ′ can be generalized by at least one ∈ Σ ; or (iii) ′ can neither belong to Σ nor be generalized by any ∈ Σ , meaning that ′ is a new rfd. As an example, consider the sets of rfds Σ and Σ ′ in Figure 1b. Considering Σ ′, we can quantify its shift as follows: (i) ′1 does not change, since it also belongs to Σ ; (ii) 3 rfds are generalized in Σ ( ′0 is generalized by 0 and 1; ′2 by 3 and 4; and ′3 by 5); and (iii) ′4 is a new rfd, since it does not belong to Σ and there is no rfd in Σ generalizing it.
We introduce an approach to quantify concept drift in supervised ML settings. As shown in Figure 2, it involves two main steps, denoted with black and red arrows. In the Initial step, the ML model that has to be monitored is trained on the available data, while an rfd discovery process extracts the set of holding rfds for each target label. In the Updating step, the deployed ML model makes predictions on incoming data. Our approach entails periodical checks for drifts. This involves a new rfd discovery on an updated dataset combining training data with the predicted instances. For each class, the original rfd set is compared with the updated one using a suite of rfd-based metrics to detect significant shifts that may require model retraining. 3.1. Collecting Meaningful rfds Our approach underlies three main phases for collecting meaningful rfds: i) Preprocessing, ii) rfd Discovery, and iii) rfd Filtering; as highlighted by the yellow box in Figure 2.
The preprocessing prepares the dataset for rfd discovery through three main operations.
First, we leverage mutual information-based feature selection [
After preprocessing, each of the subsets is given as input to an rfd discovery algorithm.
We leverage domino [
The third phase filters discovered rfds, aiming at retaining, for each target label, only its most representative rfds, i.e., those that distinguish it most from the others. Specifically, we remove from each set Σ all rfds that also belong to other sets Σ . Then, we further filter rfds by retaining, for each label, only rfds that are minimal w.r.t. all the rfds discovered on the other labels. This ensures that the rfds of each class are unique and not related to those discovered for the other classes. The output of this phase consists of the updated rfd sets.
For example, consider a scenario with two target labels and , and suppose that after the discovery process, the following resulting rfds are provided: • Σ =Σ ∪ { 7} where Σ is shown in Figure 1b and 7:Year≤ 2, #Owners≤ 1 → Model≤ 3; • Σ ={ 7, 8, 9}where 8:Model≤ 2,Price≤ 300→#Owners≤ 0 and 9:Year≤ 3→ Model≤ 2. Notice that the rfd 7 is shared between the two sets Σ and Σ and that 8 ∈ Σ is not minimal with respect to 5 ∈ Σ . Consequently, the sets Σ and Σ will become Σ = { 0, 1, 2, 3, 4, 5, 6} and Σ = { 9} after the application of the filtering strategy. 3.2. Evaluating Drift through
rfds Starting from the the original rfd sets Σ and the updated ones Σ ′ (with = 1, 2, . . . , ), the drift evaluation can be performed. The latter consists of two main phases: i) rfd Comparison and ii) Measuring; as highlighted by the green box in Figure 2.
rfd Comparison. This phase compares the original rfd set Σ and the updated one Σ ′ . This comparison provides diferent interpretations, i.e., from Σ and Σ ′ and vice versa, yielding diferent types of changes. Independently from the direction, there can be a certain number of rfds that appear in both sets, namely Imm. Instead, if the comparison is from Σ to Σ ′ , then it is possible to quantify the number of rfds in Σ that are: (i) specialized in Σ ′ , namely Spec; (ii) specialized in Σ ′ by adding LHS attributes; (iii) specialized in Σ ′ by varying thresholds only; or (iv) invalidated, i.e., neither present nor specialized in Σ ′ , namely Inv. As an example, consider the two sets Σ and Σ ′ shown in Figure 1b, which can be denoted as Σ and Σ ′ since they are associated to a single label. Thus, it is possible to say that there is just one Imm rfd, i.e., 2 and one Inv rfd, i.e., 6. Among the five Spec rfds: 0, 1, 3 4, and 5; only the latter, compared with ′3, is only driven by a simple variation of the RHS threshold. If the comparison is from Σ ′ to Σ , it is possible to quantify the rfds in Σ ′ that are: (i) generalized in Σ , namely Gen; (ii) generalized in Σ by removing LHS attributes; (iii) generalized in Σ by varying thresholds only; or (iv) New.
As an example, consider the sets of rfds in Figure 1b. Thus, it is possible to say that there is just one Imm rfd, i.e., ′1 and one New rfd, i.e., ′4. Moreover, among the three Gen rfds: ′0, ′2, ′3; only the latter, compared with 5, is driven by a variation of the RHS threshold. Overall, the quantitative information provided by the several comparison criteria can be used to define diferent metrics to measure a possible drift into data.
Measuring. After the comparison phase, the proposed approach can measure the shift in terms of rfds according to a suite of rfd-based metrics. Among them, some evaluate the magnitude of the change of Σ with respect to Σ ′ , while others consider the opposite direction. Specifically, we defined two categories of metrics: 12 metrics to quantify the divergence between two sets of rfds, and 7 metrics inspired by ML, following a confusion matrix-based evaluation1. To accurately estimating the severity of changes, the former metrics use coeficients to weight diferent types of rfd evolution, assigning greater importance to more substantial changes (e.g., invalidations and new rfds) w.r.t. moderate ones (e.g., specializations and generalizations). As an example, consider the sets of rfds Σ and Σ ′ in Figure 1b, which can also be denoted as Σ and Σ ′ since they are associated to a single label. By considering the definition of a divergence metric, namely 5, we can quantify drift from Σ to Σ ′ as follows: 5 = + (( − ) × 0.5) + ( × 0.05) |Σ |
1 + ((5 − 1) × 0.5) + (1 × 0.05) = = 0.44 7 where denotes the number of rfds specialized by others with the same LHS. The second category of metrics is inspired by the confusion matrix commonly employed for ML evaluation. In particular, we adapted the concepts of True∖False Positives and True∖False Negatives to investigate whether this (re-)interpretation aligns with the model’s actual performance trend. For instance, consider one of these metrics (i.e., 1), through which we identify True Positives as the number of rfds that were in Σ and are still in Σ ′ , and False Negatives as the rfds that were in Σ but not in Σ ′ . Instead, False Positives represent rfds that were not in Σ but in Σ ′ (i.e., new rfds). From this interpretation, the F1-Measure can be computed. In general, lower values indicate a larger change between the two sets of rfds.
This section evaluates whether the proposed metrics exhibit trends strongly correlated with the model’s performance w.r.t. baseline methods. A higher correlation would imply that rfd-based metrics more accurately capture drifts, providing reliable insights into the model’s behavior.
Baseline approaches. As compared techniques, we considered the Hellinger distance [
Experimental settings. The evaluation has been performed in two phases: in the first one,
we consider datasets with Known Drift, while the second one considers datasets with Unknown
Drift to simulate real-world scenarios (see Figure 3a). The datasets with Known Drift can be
divided into two groups: IDs 1-9, namely Statistical Drift, which contains 9 configurations
with drift afecting the data distribution; IDs 10-18, namely Attribute-relationship Drift, which
considers 3 datasets and their synthetically generated drifted versions obtained by independently
shufling the values of the number of columns reported in Figure 3a. For the scenario with
1The full set of comparison criteria, metric definitions, and experimental results has been provided in [
Unknown Drift (IDs 19-24), we considered 5 classification datasets. As shown in Figure 3a, for all datasets configurations, we randomly sampled a certain number of rows to vary the data within each configuration. Instead, we used all samples for smaller datasets (IDs 21-24). The experimental sessions required to split datasets into four batches, corresponding to the 25%, 45%, 70%, and 100% of their size, respectively. The first one is used for training a Random Forest model, which is deployed for making predictions over the other ones. To evaluate the proposed metrics and the baselines, we compared, for each class, the correlation of their trend with the actual F1-Measure trend of the model. For rfd-based divergences and the baselines, we expect a negative correlation, while, for the confusion matrix-based metrics, we expect a positive one.
Experimental Results Figure 3b shows the correlations obtained by the baseline approaches and the top-4 rfd-based metrics. The latter include two divergence metrics, i.e., 5 and 7, and two confusion matrix-based metrics, i.e., 2 and 3. For the latter, we consider the inverted correlations to include all metrics in a single plot, as they showed positive values as expected. In general, we can observe that rfd-based metrics achieved stronger correlations than baseline approaches. More specifically, 5 and 7 recorded an average correlation of − 0.94 and − 0.93, respectively, while 3 and 2 have an average correlation of 0.87 and 0.86, respectively. Concerning the baseline approaches, the best metric was , with an average correlation of − 0.75, while achieved a slightly lower correlation (i.e., − 0.73). and performed significantly worse, with average correlations of − 0.62 and − 0.59, respectively. By considering the configurations from ID 1 to 9, we expected the baseline approaches to perform well, as the dataset contains changes of the statistical properties. In fact, the Hellinger distance performed reasonably well: achieved an average correlation of − 0.86 and a correlation of − 0.85. Despite these good results, the rfd-based metrics outperformed them. In fact, 5 was the best metric, with an average correlation of − 0.927, followed by 7 (i.e., − 0.926), 3 (i.e., 0.91), and 2 (i.e., 0.90). Instead, and , recorded the worst results, with correlations of − 0.71 and − 0.64, respectively. For experiments with IDs 10-18, we artificially introduced drift by altering multi-column relationships. This type of drift significantly afected the performance of the baselines: achieved an average correlation of − 0.65, while and recorded a correlation of − 0.61. Finally, obtained the worst result, with an average correlation of − 0.48. Thus, their trend was not aligned to the F1-Measure of the model. Instead, the rfd-based metrics showed the best results: 5 and 7 achieved an average correlation of − 0.95 and − 0.94, respectively; whereas 3 and 2 performed slightly worse (i.e., 0.82 and 0.81, resp.). Thus, we can conclude that although confusion matrix-based metrics are able to obtain significant results, they are less reliable than rfd-based divergences. Among the latter, 5 and 7 proved to be the most efective, consistently maintaining strong correlations in all experiments. For experiments with Unknown Drift (IDs 19-24), the rfd-based divergences 5 and 7 achieved the strongest correlations in almost all experiments, confirming themselves as the best metrics we proposed, achieving an average correlation of − 0.946 and − 0.948, respectively. As for confusion matrix-based metrics, we observed a similar behavior w.r.t. previous scenarios: although often achieving good correlations, they were less consistent, with a lower average outcome (i.e., 0.85 for 3 and 0.70 for 2). As for the baseline approaches, and achieved an average correlation of − 0.79 and − 0.74, respectively, while and recorded a correlation of − 0.70 and − 0.65, respectively. However, also in this case, 5, 7, and 3 were more accurate in quantifying drifts with respect to all baseline approaches.
We investigated the potential of profiling metadata to quantify drifts within data evolving over time. We introduced two categories of rfd-based metrics to measure the shift within data, proposing rfd-based divergences and rfd confusion matrix-based metrics. We evaluated our approach on datasets with both known and unknown drift, by also comparing it with other distribution-based measures. Results shown that the trend of rfd-based metrics is strongly correlated with the F1-Measure of the model, and that they provide more reliable insights than the compared baseline, especially when drift afects attribute relationships. In fact, one of the strengths of this method lies in helping drift profile and understand which data relationships are changing. Moreover, the proposed approach does not require ground-truth labels for incoming data during the monitoring process. In the future, we want to investigate other types of profiling metadata to define a complete drift framework. A limitation of this work is the fact that it leverage static discovery algorithms, which also deal with a problem that is exponential in the number of attributes. Future works could employ incremental discovery strategies [20, 21, 22] to update rfds over time without reconsidering already processed data. This will require new incremental discovery algorithms capable of inferring similarity/distance thresholds.
This work was partially supported by the PNRR MUR project PE0000013-FAIR (Future Artificial Intelligence Research).
The authors have not employed any Generative AI tools. and Data Mining, ACM, Sydney, Australia, 2015, pp. 935–944. [20] L. Caruccio, S. Cirillo, V. Deufemia, G. Polese, et al., Incremental discovery of functional dependencies with a bit-vector algorithm, in: Proceedings of the 27th Italian Symposium on Advanced Database Systems, 2019. [21] L. Caruccio, S. Cirillo, Incremental discovery of imprecise functional dependencies, Journal of Data and Information Quality (JDIQ) 12 (2020) 1–25. [22] B. Breve, L. Caruccio, S. Cirillo, V. Deufemia, G. Polese, Indibits: Incremental discovery of relaxed functional dependencies using bitwise similarity, in: Proceedings of the 2023 IEEE 39th International Conference on Data Engineering (ICDE), IEEE, 2023, pp. 1393–1405.