Class Density and Dataset Quality in High-Dimensional, Unstructured Data

arXiv:2202.03856 · cs.LG, cs.CV · Submitted 2022-02-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Class Density and Dataset Quality in High-Dimensional, Unstructured Data".

Jane: The gist The authors provide a definition for class density that can be used to measure the aggregate similarity of the samples within each of the classes in a high-dimensional,…

Tom: First, who's behind it and why it matters.

Title and authors: Tom: So we're looking at this paper titled "Class Density and Dataset Quality in High-Dimensional, Unstructured Data". We’re starting by talking about who wrote it and what the core concept is, moving beyond just the mechanics of how they calculated things.

Jane: Before we get into the math, I want to ask, what is the actual big picture here? How does this paper fit into the bigger conversation about managing huge datasets in AI?

Tom: It’s written by Adam Byerly and Tatiana Kalganova from Brunel University London and Bradley University. They introduce a density measurement to gauge the aggregate similarity within each class, which is key for unstructured data.

Lu: The authors are looking at how we can define data quality when we don't have a universal definition for it in this area. They focus specifically on completeness as their measure of quality.

Meng: So they aren't trying to solve every problem in unstructured data, just focusing on one aspect—completeness—and using density to drive the next step, which is data reduction.

Jane: That makes sense. It sounds like they are building a specific tool for cleaning up messy data before training AI models on it.

Tom: Exactly. They propose several candidate methods for calculating this class density and then analyze how correlated those results are with the actual test accuracies achieved on a trained model.

Lu: They chose the mean candidate, Equation three as their final method because it showed the highest mean correlation across all tested datasets, despite some other candidates having negative correlations <ref:2202.03856#pg1>.

Jane: So why did they go with the mean one over the min and max methods? What’s the reasoning there?

Tom: Because those other methods had negative correlations for specific datasets, like MNIST and Fashion-MNIST, which means they weren't reliable indicators of class similarity in those cases.

The paper's summary: Jane: Now that we know they picked Equation three what’s the actual purpose of this whole measurement process <ref:2202.03856#pg1>? What are they trying to achieve with this density definition?

Tom: The goal is to provide a definition for class density that measures aggregate similarity within each class in a high-dimensional, unstructured dataset. It’s about quantifying how similar those samples are relative to each other.

Lu: They then use this density measure to propose several methods for calculating it, and they analyze the correlation between these calculated values and the corresponding individual class test accuracies achieved on a trained model.

Meng: So the output of that process is a number that tells you how dense or sparse a class is in terms of sample distribution.

Jane: It’s more than just counting samples; it's about the aggregate similarity across all dimensions, which is what makes it useful for unstructured data.

Tom: And then they build on this by proposing a definition for dataset quality based on completeness, showing that datasets meeting a certain quality threshold could be candidates for eliding redundant data using the individual class densities.

Lu: They show that if you hit that threshold, those datasets are candidates for eliding redundant data based on the calculated class densities.

Jane: So it’s a two-step process: measure density, then use that measurement to determine if the dataset is high enough quality to warrant data reduction.

The paper's improvements: Tom: The paper suggests several key improvements for this framework, which are about making the system more practical and robust. These suggestions focus on how we can actually use these tools in a real workflow.

Jane: What kind of practical improvements are they suggesting? Are we supposed to change the way we calculate density or just change how we apply the quality threshold?

Tom: They suggest using Equation five to calculate dataset quality as a single value, where closer to zero means lower quality and room for improvement <ref:2202.03856#pg3>. This is defined as one over the product of the standard deviation of class densities and the range of density values.

Lu: They also suggest that this equation simply captures that greater variance among the class densities means lower data quality.

Meng: So if we have high variance, we know immediately that our dataset is messy, without needing to run a full classification benchmark first. That’s a huge win for scaling up data prep pipelines.

Jane: And they also suggest using the Mean-Derived Density Calculation—Equation three as the primary metric because it had the highest mean correlation with class accuracies <ref:2202.03856#pg1>.

Tom: So we should be prioritizing that over Equation one and Equation two when calculating individual class densities based on UMAP reductions to inform synthetic sample creation or under-sampling strategies <ref:2202.03856#pg3>.

Conclusion: Jane: To wrap up, what’s the final thought they want us to take away from the entire paper? What’s the big implication for people who just listen to this discussion?

Tom: The main implication is that for most datasets studied, if you hit that quality threshold of greater than ten you can reduce your training data down to a target density of at most one point zero without losing accuracy <ref:2202.03856#pg3>.

Jane: That’s the practical takeaway: if your data is good enough according to their metric, you can safely cut it down by nearly half with minimal impact on performance.

Lu: The only caveat they highlight is Imagenette, where the low number of training samples combined with feature complexity creates a lower bound on sample size that means any elision risks underfitting in the training procedure.

Meng: So for production, that means you have to be cautious about those very small or very complex datasets because of this inherent risk they flagged.

Lalam: I’m confident this framework is sound; it directly connects density and quality to actionable data reduction decisions.

Adam Byerly, Tatiana Kalganova

Brunel University London · Bradley University

cs.LG, cs.CV

Submitted: 2022-02-08

Updated: 2022-02-08

Comments: 13 pages, 27 tables

DOI: 10.1007/s42979-022-01549-4

Code: https://github.com/fastai/imagenette

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: The gist The authors provide a definition for class density that can be used to measure the aggregate similarity of the samples within each of the classes in a high-dimensional, unstructured dataset

Key concepts

Class Density: A measure used to quantify how similar samples are within a specific class in high-dimensional data. The paper tested several methods, ultimately selecting the mean-derived calculation as the most appropriate metric for this purpose.
Dataset Quality: A metric calculated using the variance of class densities. A higher quality score indicates lower variance among class densities, suggesting more uniform distribution and suitability for data reduction techniques.
Data Elision: The process of removing redundant or unnecessary data points from a dataset. The paper suggests that datasets meeting a high quality threshold are candidates for this process based on their calculated class densities.

Summary

The gist The authors provide a definition for class density that can be used to measure the aggregate similarity of the samples within each of the classes in a high-dimensional, unstructured dataset and propose a definition for dataset quality based on completeness, showing that datasets meeting a certain quality threshold were candidates for eliding redundant data based on individual class densities.

Defining Class Density

The paper introduces three candidate methods for calculating class density, all based on the distribution of points in each dimension of any m-dimensional reduction<ref:2202.03856#pg2> The first three terms of each calculation are identical and are used for biasing unbalanced datasets<ref:2202.03856#pg2> For unbalanced datasets, these three terms create a value 1.0 for those classes that have more samples than average<ref:2202.03856#pg2> The motivation for this is to incorporate over and underrepresentation of classes into the density definition<ref:2202.03856#pg2> The mean candidate, Equation 3, has been chosen for the calculation of class density<ref:2202.03856#pg2>.

Equation 1 defines the Min-Derived Density Calculation as dmin i = n · ci · (Xn j cj) −1 · min (σi) −1<ref:2202.03856#pg2> Equation 2 defines the Max-Derived Density Calculation as di = n · ci · (Xn j cj) −1 · 1/m Xm k σik!−1<ref:2202.03856#pg2> Equation 3 defines the Mean-Derived Density Calculation as di = n · ci · (Xn j cj) −1 · 1/m Xm k σjk! − 1<ref:2202.03856#pg2>. The study showed that on average, all candidate calculations showed a moderate correlation<ref:2202.03856#pg2> However, the min and max candidates each had a dataset for which the correlation was negative (MNIST and Fashion-MNIST respectively)<ref:2202.03856#pg2>. As such, the mean candidate, Equation 3, has been chosen for the calculation of class density<ref:2202.03856#pg2>.

Defining Dataset Quality

The paper proposes a definition for dataset quality for high-dimensional, unstructured data and shows that those datasets that met a certain quality threshold (experimentally demonstrated to be > 10 for the datasets studied) were candidates for eliding redundant data based on the individual class densities<ref:2202.03856#pg2>. For the high-dimensional, unstructured data we will be evaluating, completeness will be demonstrated by removing data from the dataset, based on a target density threshold, while maintaining classification accuracy<ref:2202.03856#pg2>.

Equation 5 represents an attempt to capture this measure numerically in a single value such that the closer the value is to zero, the lower the “quality” of the dataset, or from another point of view, there exists room for improvement<ref:2202.03856#pg2>. In this equation, d are the densities of the classes as calculated using Equation 4<ref:2202.03856#pg2>. As such, the equation is simply 1 over the product of the standard deviation of the class densities and the range of density values<ref:2202.03856#pg2>. Thus and simply, the greater variance among the class densities, the lower the quality of data<ref:2202.03856#pg2>.

Dynamic Data Reduction Experiments

The experiments detailed thus far have demonstrated that, for the datasets studied, there exists an amount of redundant data in each such dataset and that that data can be located near the centroid of a dimensional reduction of the data<ref:2202.03856#pg2>. This observation inspires the possibility of a measure of the dataset quality that can be used a-priori to determine whether or not the data distributed in the lower-dimensional space is capable of leading to optimal or near-optimal classification accuracy<ref:2202.03856#pg2>.

The experiments showed that for all datasets except Imagenette, datasets with a quality of > 10 could be reduced to a target density of at most 1.0 and achieve accuracy that is statistically insignificantly different from the baseline<ref:2202.03856#pg2>. Unique to Imagenette is the relatively low number of training samples coupled with the complexity of the features that comprise the subject matter<ref:2202.03856#pg2>. That combined with the large image size and the assumptions made by UMAP suggest that there is a lower bound on the number of training samples such that any elision whatsoever risks underfitting in the training procedure<ref:2202.03856#pg2>.

Dataset Quality Results

Table 26 shows this calculation as applied to the training datasets we have studied<ref:2202.03856#pg2>. MNIST, EMNIST-Digits, CIFAR10 and the micro-PCB dataset all had values for quality > 10 and all of these datasets were shown to have had excess data in their training datasets<ref:2202.03856#pg2>. Fashion-MNIST and CIFAR-100 each had values for quality < 10 and both of these datasets were shown not to have had an excess of data in their training datasets<ref:2202.03856#pg2>. Imagenette was inconsistent with this<ref:2202.03856#pg2>. It is hypothesized that in the case of Imagenette, that the lower number of training samples coupled with the complexity of the features that comprise the subject matter, compared to the other datasets, dominates any ability to elide redundant data<ref:2202.03856#pg2>.

Summary

In this work, we have put forth a definition for class density along with several methods for calculating such<ref:2202.03856#pg2>. Analysis of seven datasets showed that Equation 4, derived from the normalized mean standard deviations of the data points in lower dimensional space, was the appropriate choice for the calculation for density<ref:2202.03856#pg2>. Additionally, we put forth a definition for dataset quality in Equation 5, which showed that those datasets that met a certain quality threshold (experimentally demonstrated to be > 10 for the datasets studied) were candidates for eliding redundant data using Equation 4<ref:2202.03856#pg2>. The experiments showed that for all datasets except Imagenette, datasets with a quality of > 10 could be reduced to a target density of at most 1.0 and achieve accuracy that is statistically insignificantly different from the baseline<ref:2202.03856#pg2>. Unique to Imagenette is the relatively low number of training samples coupled with the complexity of the features that comprise the subject matter<ref:2202.03856#pg2>. That combined with the large image size and the assumptions made by UMAP suggest that there is a lower bound on the number of training samples such that any elision whatsoever risks underfitting in the training procedure<ref:2202.03856#pg2>.

References [1] Aisha Abdallah, Mohd Aizaini Maarof, and Anazida Zainal. “Fraud detection system: A survey”. In: Journal of Network and Computer Applications 68 (2016), pp. 90–113. ISSN: 1084-8045. DOI: https://doi.org/10.1016/j.jnca.2016.04.007.; [2] Zhenchuan Li et al., “A hybrid method with dynamic weighted entropy for handling the problem of class imbalance with overlap in credit card fraud detection”. In: Expert Systems with Applications 175 (2021). ISSN: 0957-4174. DOI: https://doi.org/10.1016/j.eswa.2021.114750.; [3] N Chawla et al., “SMOTE: Synthetic minority over-sampling technique”. In: Journal of Artificial Intelligence Research 16 (2002), pp. 321–357. ISSN: 10769757. DOI: 10.1613/jair.953.; [4] Chumphol Bunkhumpornpat and Krung Sinapiromsaran, “DBMUTE: density-based majority under-sampling technique”. In: Knowledge and Information Systems 50 (2017), pp. 827–850. ISSN: 0219-3116. DOI: https://doi.org/10.1007/s10115-016-0957-5.

Improvements for AI systems

To improve data reduction strategies, implement a mechanism that utilizes Dataset Quality Calculation (Equation 5) to determine if a dataset meets a threshold (experimentally demonstrated to be "> 10 for the datasets studied) before applying data elision based on class densities. This allows the system to only attempt data reduction when the dataset exhibits excess data in their training datasets."
To enhance classification performance, use the Mean-Derived Density Calculation (Equation 3) as the primary density metric, as it was shown to have the highest mean correlation with class accuracies across all tested datasets. This method should be used for calculating individual class densities based on UMAP reductions to inform synthetic sample creation or under-sampling strategies.
To optimize data reduction targets, dynamically adjust target densities based on the dataset's characteristics, as seen in Table 6 through Table 12 showing that the accuracy matched or exceeded the accuracy of the baseline for MNIST and CIFAR-10 when using target densities from 1.0 down to 0.7. This suggests a tiered approach where lower density targets might be explored if initial high-density reductions fail to yield statistically significant improvements, as shown by statistical insignificantly different from the baseline.
To identify potentially problematic datasets for data reduction, flag any dataset with a calculated "quality < 10 as candidates for further investigation into feature complexity or sample size limitations, such as Imagenette which was hypothesized to have a lower bound on training samples such that any elision whatsoever risks underfitting in the training procedure."
To refine density calculation robustness, incorporate the normalization term from Equation 4 into Equation 3 to create a Mean-Derived and Normalized Density Calculation, which yielded higher correlation coefficients in several cases compared to the standard mean-derived calculation.