Source-linked AI summary
Assessing and Remedying Coverage for a Given Dataset
Abolfazl Asudeh, Zhongjun Jin, H. V. Jagadish
TL;DR
Datasets assembled without control may not adequately cover less common combinations of categorical attributes, with implications for model performance and adversarial vulnerabilities. The paper proposes methods to identify maximal uncovered patterns and to minimize additional data collection for remedying coverage gaps. It establishes hardness results for the problems and presents algorithmic approaches to address them.
Problem
Datasets may inadequately cover less common categories across multiple attributes, making it important to assess coverage and identify poorly covered regions.
Source: §I · pp. 1–2Method
The paper formalizes maximal uncovered patterns, develops pattern-graph algorithms to find them, and models additional data collection as a hitting-set problem with a greedy approximation.
Source: §I · p. 2Results
MUP identification has no polynomial-time algorithm that can guarantee enumeration, and coverage enhancement is NP-hard.
Source: §I · p. 2, §II · p. 4Takeaways & Limitations
The proposed framework assesses dataset coverage and identifies the minimum additional tuples needed to meet a target coverage level.
Source: §I · p. 2
Abstract
from arXiv · showhide
Data analysis impacts virtually every aspect of our society today. Often, this analysis is performed on an existing dataset, possibly collected through a process that the data scientists had limited control over. The existing data analyzed may not include the complete universe, but it is expected to cover the diversity of items in the universe. Lack of adequate coverage in the dataset can result in undesirable outcomes such as biased decisions and algorithmic racism, as well as creating vulnerabilities such as opening up room for adversarial attacks. In this paper, we assess the coverage of a given dataset over multiple categorical attributes. We first provide efficient techniques for traversing the combinatorial explosion of value combinations to identify any regions of attribute space not adequately covered by the data. Then, we determine the least amount of additional data that must be obtained to resolve this lack of adequate coverage. We confirm the value of our proposal through both theoretical analyses and comprehensive experiments on real data.
I. INTRODUCTION
Datasets collected without control may lack coverage of less common attribute combinations, risking poor performance across underrepresented groups and vulnerabilities to adversarial examples. The paper formalizes maximal uncovered patterns, proposes methods to find them and minimize additional data collection, and establishes hardness results for both problems.
I. INTRODUCTION
- Found datasets can miss underrepresented attribute groups, a problem linked to poor recognition outcomes and adversarial opportunities.The paper motivates coverage partly through examples involving image recognition, criminal risk assessment, and adversarial attacks.Source: §I · pp. 1–2
II. PRELIMINARIES
- Coverage enhancement seeks the minimum additional tuples needed to reach a target maximum covered level or satisfy a minimum value-count criterion.The paper notes that data collection has costs and that one tuple can contribute to multiple patterns.Source: §I · p. 2, §II · p. 4
I. INTRODUCTION
- The paper defines maximal uncovered patterns (MUPs) to identify insufficiently covered regions across multiple attributes, and shows MUP identification cannot be guaranteed in polynomial time.Coverage enhancement is NP-hard; the hardness proof reduces vertex cover to the problem.Source: §I · p. 2, §II · pp. 3–4
- The proposed algorithms use a pattern graph and PATTERN-BREAKER, PATTERN-COMBINER, and DEEPDIVER to discover MUPs.The paper also connects additional data collection to hitting set and proposes a greedy approximation.Source: §I · p. 2
II. PRELIMINARIES
- A pattern specifies values for some attributes and leaves others unspecified; its coverage is the number of dataset items matching those specified values.A pattern is uncovered when its coverage is below the chosen threshold.Source: §II · p. 3
- A MUP is uncovered while each parent pattern is covered, so it marks a maximal uncovered region without listing its more specific, dominated patterns.The paper distinguishes material MUPs from combinations that domain experts identify as infeasible or safe to ignore.Source: §II · pp. 3–4
- Maximum covered level sets the largest pattern level for which no material MUP exists at that level or below.The paper describes this as a way to prioritize larger uncovered regions.Source: §II · p. 4
- The coverage-enhancement problem is NP-hard, as shown by a polynomial-time reduction from vertex cover.The reduction constructs MUPs corresponding to graph edges, so covering those patterns corresponds to selecting vertices incident to every edge.Source: §II · pp. 4–5
III. MUP IDENTIFICATION
The paper studies MUP identification and proposes efficient search and pruning strategies.
III. MUP IDENTIFICATION
- The paper proposes efficient search and pruning strategies for identifying maximal uncovered patterns.This section studies the MUP identification problem.Source: §III · p. 5
A. Na¨ıve
The naïve approach enumerates patterns and filters uncovered ones to find the maximal uncovered patterns, but its cost grows with the pattern space and the number of uncovered patterns.
A. Na¨ıve
- A naïve approach counts coverage for every pattern, then compares uncovered patterns pairwise and removes those dominated by another uncovered pattern.This requires O(n × c+) time to find uncovered patterns and an additional O(u^2) time to filter them, where u is the number of uncovered patterns.Source: A. Na¨ıve · p. 5
- The approach requires one counter per possible pattern, with c_i + 1 choices for each attribute, so its space grows with the full pattern space.The passage gives the total pattern count as the product of the per-attribute choices.Source: A. Na¨ıve · p. 5
- In the example, one MUP, 1XX, dominates eight other uncovered patterns, illustrating that the uncovered-pattern list can be much larger than the MUP set.The example uses three binary attributes and a coverage threshold of 1.Source: A. Na¨ıve · p. 5
B. Pattern Graph
The pattern graph represents possible value patterns as nodes linked by parent-child relationships, organizing them from general to specific. Its size grows across attribute levels.
B. Pattern Graph
- Each node is a possible pattern, and edges connect patterns with a parent-child relationship across adjacent levels.The root is the most general pattern; lower levels are more specific.Source: B. Pattern Graph · p. 5
- For three binary attributes, the pattern graph has 27 nodes and 54 edges.The node count is (2 + 1)^3 = 27; the passage confirms the 54-edge total.Source: B. Pattern Graph · p. 5, Figure 2 · p. 5
- At level ℓ, each node has c^(d−ℓ) children when all d attributes have cardinality c.The children are formed by assigning a value to one of the remaining non-deterministic attributes.Source: B. Pattern Graph · p. 5
C. PATTERN-BREAKER: The top-down algorithm
PATTERN-BREAKER searches the pattern graph top-down, using coverage monotonicity and Rule 1 to prune descendants and generate candidates once. Its traversal can still spend effort in covered regions.
C. PATTERN-BREAKER: The top-down algorithm
- PATTERN-BREAKER starts at the general patterns and searches downward, pruning descendants of uncovered patterns because they cannot be MUPs.Coverage monotonicity means an uncovered pattern's children and descendants are also uncovered.Source: C. PATTERN-BREAKER: The top-down… · p. 6
- Rule 1 generates each MUP candidate exactly once, transforming the pattern graph into a tree.A covered node generates selected children by replacing non-deterministic elements to the right of its right-most deterministic element.Source: C. PATTERN-BREAKER: The top-down… · p. 6, Figure 3 · p. 6
- The algorithm checks whether a candidate has an uncovered parent before computing coverage, then adds it as a MUP when coverage is below threshold.Children are generated for the next level when a candidate meets the coverage threshold.Source: C. PATTERN-BREAKER: The top-down… · p. 6
- PATTERN-BREAKER may traverse covered regions and generate many candidates from pruned regions, making runtime depend on the size of the covered graph.The example shows an uncovered child that is not a MUP because it is dominated by an uncovered pattern.Source: C. PATTERN-BREAKER: The top-down… · p. 6
D. PATTERN-COMBINER: The bottom-up algorithm
PATTERN-COMBINER searches bottom-up, deriving a pattern's coverage from disjoint child partitions and using Rule 2 to generate candidates once. This approach prunes branches at covered nodes.
D. PATTERN-COMBINER: The bottom-up algorithm
- A pattern's coverage can be computed by summing the coverages of children that partition its matches across one attribute's values.The children are disjoint, and their number equals the cardinality of that attribute.Source: D. PATTERN-COMBINER: The bottom-up… · p. 7
- PATTERN-COMBINER starts at the most specific patterns, computes their coverage in one data pass, then combines uncovered nodes level by level.Uncovered nodes whose parents are all covered are MUPs.Source: D. PATTERN-COMBINER: The bottom-up… · p. 7
- Rule 2 transforms the pattern graph into a forest and guarantees each MUP candidate is generated exactly once.For a node below threshold, Rule 2 generates candidates at the preceding level by replacing selected deterministic elements with X.Source: D. PATTERN-COMBINER: The bottom-up… · p. 7
- The algorithm prunes a branch when it finds a covered node, and its monotonicity-based pruning ensures it does not discard an uncovered node.The paper states that this property, together with Theorem 4, guarantees discovery of all MUPs.Source: D. PATTERN-COMBINER: The bottom-up… · p. 7
E. DEEPDIVER: Fast search space pruner
DEEPDIVER seeks MUPs quickly by descending to uncovered regions, then searching upward to find maximal patterns. It uses discovered MUPs to prune both ancestors and descendants.
E. DEEPDIVER: Fast search space pruner
- The method targets cases where PATTERN-BREAKER or PATTERN-COMBINER performs poorly: mostly covered, mostly uncovered, or MUPs in the middle of the graph.The first two algorithms traverse the covered and uncovered regions, respectively; both may traverse about half the graph when MUPs lie in the middle.Source: E. DEEPDIVER: Fast search space pruner · pp. 7–8
- DEEPDIVER finds MUPs and prunes patterns that dominate or are dominated by them, limiting the remaining search space.The algorithm follows a path downward to an uncovered node, then moves upward until it finds a MUP.Source: E. DEEPDIVER: Fast search space pruner · p. 8
- An uncovered node is not necessarily a MUP, so DEEPDIVER checks its parents and moves upward while any parent remains uncovered.It prunes ancestors and descendants after discovering a MUP, then searches the unpruned regions.Source: E. DEEPDIVER: Fast search space pruner · p. 8
- A pattern is dominated by a MUP when that MUP dominates the pattern; dominated patterns and patterns that dominate MUPs lie outside the search space.The algorithm uses inverted indices to check MUP dominance efficiently.Source: E. DEEPDIVER: Fast search space pruner · p. 8
IV. COVERAGE ENHANCEMENT
Coverage enhancement seeks the fewest additional tuples needed to cover selected uncovered patterns, rather than trying to resolve every uncovered region. The approach balances coverage goals with acquisition costs and relies on expert input to keep targets and collected combinations meaningful.
IV. COVERAGE ENHANCEMENT
- MUPs represent under-covered regions; more general MUPs cover larger regions, while the AirBnB example has thousands of MUPs but few at low levels.At n = 1000, d = 13, and τ = 50, most MUPs are at levels 5 and 6, with one at level 1 and fewer than 40 at level 2.Source: §IV · pp. 8–9
- Because collecting, cleaning, storing, and indexing data costs resources, the objective is to acquire as few additional tuples as possible.Experts also review discovered MUPs and define validation rules so the enhancement targets problematic, semantically valid combinations.Source: §IV · p. 9
- For target level λ, the goal is to collect the minimum number of tuples so the dataset’s maximum covered level reaches at least λ.This requires covering all uncovered patterns at level λ, not just maximal uncovered patterns at or below that level.Source: §IV · p. 9
- Choosing tuples that match multiple uncovered patterns turns coverage enhancement into a hitting-set problem, avoiding separate collections for each pattern.A tuple can contribute to several patterns, so collecting enough data for each one independently may exceed the minimum.Source: §IV · p. 9
A. Transformation to hitting set
The paper transforms coverage enhancement into a hitting-set problem over value combinations and uncovered patterns. A greedy approximation is then motivated, but searching all combinations directly is inefficient.
A. Transformation to hitting set
- The universe U comprises possible value combinations, and each uncovered pattern represents the set of combinations that match it.The hitting-set objective is to select the fewest combinations that hit every target pattern.Source: A. Transformation to hitting set · p. 9
- The transformation forms a bipartite graph with value combinations on one side and uncovered patterns on the other, linked when a combination matches a pattern.The solution selects the minimum number of combination nodes that hit every pattern node.Source: A. Transformation to hitting set · p. 10
- Although hitting set is NP-complete, greedy selection has a logarithmic approximation ratio; directly finding each best combination is inefficient at scale.At each iteration, greedy selects the combination that hits the largest number of un-hit patterns.Source: A. Transformation to hitting set · p. 10
B. Efficient implementation of the greedy algorithm
The GREEDY implementation uses inverted indices and a tree search to efficiently find value combinations that hit uncovered patterns. The experiments evaluate the algorithms on real datasets, with coverage-performance questions and scalability questions assigned different datasets.
B. Efficient implementation of the greedy algorithm
- GREEDY traverses a value-combination tree, intersects bit-vector filters with inverted indices, and prunes branches that cannot beat the best-known hit count.A path represents a value combination; the number of remaining set bits gives its hit count, and a validation oracle filters semantically invalid combinations.Source: B. Efficient implementation of the… · p. 10
- The example’s greedy collection is 02011, 02111, and 10201; intersecting the patterns each tuple hits yields more general collection targets.The more general patterns give users greater freedom in data collection.Source: B. Efficient implementation of the… · p. 11
V. EXPERIMENTAL EVALUATION
- Experiments study real-data coverage, prediction effects, MUP identification, and coverage enhancement across three datasets.The study emphasizes COMPAS for potential consequences and AirBnB for performance, adding BlueNile to examine higher attribute cardinalities.Source: §V · p. 11, A. Experimental Setup · p. 11
A. Experimental Setup
- The setup includes COMPAS demographics and recidivism data, AirBnB property records, and BlueNile diamond records with categorical attributes.The BlueNile dataset has seven attributes with cardinalities from 3 to 10; the AirBnB collection includes approximately 2 million properties and 36 boolean attributes.Source: A. Experimental Setup · p. 11
B. Validation
The COMPAS experiments identify under-covered demographic combinations, examine subgroup prediction performance as coverage changes, and test oracle-constrained coverage enhancement. The performance evaluation compares proposed algorithms with baselines, though the supplied passages do not report its benchmark outcomes.
1) Issues with Coverage in Real Data:
- At threshold 10, COMPAS contained 65 MUPs, including 19 at level 2; the widowed Hispanic pattern XX23 matched only two records.Both matching records involved individuals who had offended multiple times, so the authors flag the subgroup for expert assessment rather than declaring the MUP problematic.Source: 1) Issues with Coverage in Real Data · pp. 11–12
2) Lack of coverage’s effect:
- Accuracy remained 76% overall as Hispanic Female coverage increased, while subgroup accuracy and F1 improved with additional training examples.With no Hispanic Female examples in training, subgroup accuracy was below 50%; the accuracy curve’s slope reduced around 40 examples.Source: 2) Lack of coverage’s effect · p. 12, Figure 11 · p. 13
3) Coverage Enhancement Quality:
- For coverage level 2, oracle-constrained GREEDY recommends five combinations, excluding unknown marital status and under-20 non-single cases.The oracle rules are intended to ensure the output combinations are semantically valid.Source: 3) Coverage Enhancement Quality · p. 12
C. Performance Evaluation
- Naïve MUP identification did not finish within the time limit; evaluation compares three proposed identifiers and GREEDY against direct hitting-set approximation.The experiments vary coverage threshold and dataset size or attribute count, and also compare MUP identification with an APRIORI adaptation.Source: C. Performance Evaluation · p. 12
1) MUP identification - varying threshold:
MUP identification runtime depends on coverage threshold, data size, and attribute count, with the algorithms responding differently to pattern-graph structure. Across these experiments, DEEPDIVER is fast across coverage settings, and limiting search to low-level MUPs extends identification to many attributes.
1) MUP identification - varying threshold:
- DEEPDIVER was as fast or faster than the alternatives across AirBnB thresholds and was best across BlueNile thresholds; PATTERN-COMBINER lagged most on high-cardinality BlueNile data.PATTERN-BREAKER sped up as thresholds rose, while PATTERN-COMBINER slowed; their relative runtimes shifted with MUP levels in the pattern graph.Source: 1) MUP identification - varying… · pp. 13–14
2) MUP identification - varying data size:
- Across all tested dataset-size settings, all three algorithms ran in less than 100 seconds, with runtime only slightly impacted by dataset size; effort depended more on pattern count, independent of dataset size.PATTERN-COMBINER checks the actual dataset only for the bottom layer of the pattern graph; inverted indices limit data-size impact for PATTERN-BREAKER and DEEPDIVER.Source: 2) MUP identification - varying data… · p. 14
3) MUP identification - varying data dimensions:
- Runtime and MUP counts grew exponentially with attribute count, yet all algorithms finished within two minutes through 17 attributes.Limiting DEEPDIVER to MUPs of up to level 2 found such patterns among 35 attributes in around 10 seconds.Source: 3) MUP identification - varying data… · p. 14
- As attribute count grows, MUPs become more numerous but combine more attributes, making higher-level patterns less central to the stated risk focus.The paper motivates limiting exploration level to retain scale while finding lower-level risky MUPs.Source: 3) MUP identification - varying data… · p. 14
4) Coverage enhancement - varying threshold:
Coverage enhancement seeks the fewest additional items needed to cover uncovered patterns up to a chosen maximum level. GREEDY completed the tested threshold settings quickly, while greater levels and attribute counts increased computational and collection demands.
4) Coverage enhancement - varying threshold:
- GREEDY finished in a few seconds for every tested threshold setting, while the naïve algorithm finished within the time limit in only one.GREEDY runtime rose with the maximum coverage level and threshold, as both meant more uncovered patterns or additional points to collect.Source: 4) Coverage enhancement - varying… · p. 14
5) Coverage enhancement - varying data dimensions:
- GREEDY's runtime and output size increased with maximum coverage level and attribute count, but its output required significantly fewer points than the uncovered patterns it hit.Each added value combination can hit multiple uncovered patterns; resolving smaller maximum levels remained reasonably performant.Source: 5) Coverage enhancement - varying data… · pp. 14–15
VI. RELATED WORK
- The approach differs from database sampling: it assesses an existing dataset, often acquired independently, rather than drawing a sample from a larger database.Its pattern-graph traversal also differs from powerset-lattice methods, which the authors say cannot be directly applied.Source: §VI · p. 15
VII. FINAL REMARKS
- The paper frames inadequate coverage as a dataset risk and reports real-data experiments supporting techniques to identify gaps and guide additional collection.The authors note that lack of coverage may cause errors, including algorithmic racism.Source: §VII · p. 15
- MUP identification uses one fixed coverage threshold across value combinations; selecting thresholds and minor subgroups is left for future work.Source: §VII · p. 15
APPENDIX
The appendix describes implementation choices for computing pattern coverage and checking MUP dominance, then clarifies which uncovered patterns must be hit to assure a maximum coverage level. The assurance procedure targets uncovered patterns at that level, not merely the MUPs themselves.
A. Coverage Computation
- Coverage computation uses inverted-index bit vectors for attribute values, combines vectors for a pattern's deterministic elements, then weights matching combinations by their item counts.The vectors represent unique value combinations; their dot product with the count vector gives pattern coverage.Source: A. Coverage Computation · p. 16
B. Efficient Dominance Checking
- Dominance checks use bit-vector operations over discovered MUPs, with early stopping once an AND result contains a 1.The index encodes deterministic values and non-deterministic positions to test whether a pattern dominates or is dominated by current MUPs.Source: B. Efficient Dominance Checking · p. 16
C. Uncovered patterns to hit for maximum coverage level assurance
- Hitting MUPs at or below level λ alone may leave uncovered patterns at level λ; covering all uncovered patterns at λ also covers more-general patterns at lower levels.The procedure generates level-λ descendants of qualifying MUPs and applies the greedy hitting set to the uncovered patterns at that level.Source: C. Uncovered patterns to hit for… · pp. 16–17