  Existing machine learning models have proven to fail when it comes to their
performance for minority groups, mainly due to biases in data. In particular,
datasets, especially social data, are often not representative of minorities.
In this paper, we consider the problem of representation bias identification on
image datasets without explicit attribute values. Using the notion of data
coverage for detecting a lack of representation, we develop multiple
crowdsourcing approaches. Our core approach, at a high level, is a divide and
conquer algorithm that applies a search space pruning strategy to efficiently
identify if a dataset misses proper coverage for a given group. We provide a
different theoretical analysis of our algorithm, including a tight upper bound
on its performance which guarantees its near-optimality. Using this algorithm
as the core, we propose multiple heuristics to reduce the coverage detection
cost across different cases with multiple intersectional/non-intersectional
groups. We demonstrate how the pre-trained predictors are not reliable and
hence not sufficient for detecting representation bias in the data. Finally, we
adjust our core algorithm to utilize existing models for predicting image
group(s) to minimize the coverage identification cost. We conduct extensive
experiments, including live experiments on Amazon Mechanical Turk to validate
our problem and evaluate our algorithms' performance.
