Fair and Diverse DPP-based Data Summarization

L. Elisa Celis; Vijay Keswani; Damian Straszak; Amit Deshpande; Tarun Kathuria; Nisheeth K. Vishnoi

Source-linked AI summary

Fair and Diverse DPP-based Data Summarization

L. Elisa Celis, Vijay Keswani, Damian Straszak, Amit Deshpande, Tarun Kathuria, Nisheeth K. Vishnoi

arXiv:1802.04023v1Feb 12, 2018cs.LGcs.CYcs.IRstat.ML

TL;DR

Data summarization methods can produce diverse but biased subsets, motivating fair and diverse summaries. The paper adds flexible fairness constraints to DPPs and develops a fast approximate sampler under a natural balance condition. Experiments and theory show that these constraints can improve fairness while causing minimal diversity loss.

Problem
Data summarization methods can under- or over-represent sensitive groups, so the paper studies how to produce summaries that are both diverse and fair.
Method
The paper models fairness through partition DPPs with specified counts for disjoint sensitive classes and provides a fast sampler with guarantees under a natural β-balance condition.
Results
Experiments show fairness constraints produce minimal loss to diversity, even for biased datasets or substantially changed attribute proportions.
Takeaways & Limitations
Fairness constraints can improve representation in DPP-based summaries while preserving much of their geometric diversity.
Takeaways & Limitations
The flexible fairness framework makes sampling from partition DPPs computationally difficult, with the problem shown to be #P-hard [7].

Abstract

from arXiv · show

Sampling methods that choose a subset of the data proportional to its diversity in the feature space are popular for data summarization. However, recent studies have noted the occurrence of bias (under- or over-representation of a certain gender or race) in such data summarization methods. In this paper we initiate a study of the problem of outputting a diverse and fair summary of a given dataset. We work with a well-studied determinantal measure of diversity and corresponding distributions (DPPs) and present a framework that allows us to incorporate a general class of fairness constraints into such distributions. Coming up with efficient algorithms to sample from these constrained determinantal distributions, however, suffers from a complexity barrier and we present a fast sampler that is provably good when the input vectors satisfy a natural property. Our experimental results on a real-world and an image dataset show that the diversity of the samples produced by adding fairness constraints is not too far from the unconstrained case, and we also provide a theoretical explanation of it.

1 Introduction

Data summarization seeks small, diverse subsets, but existing methods can under-represent sensitive groups. This paper develops fairness-constrained DPP sampling and shows fairness can improve with little loss of geometric diversity.

Fairness-constrained DPP sampling addresses biased data summaries while retaining probability proportional to the geometric diversity measure G(·).The framework supports fairness constraints for disjoint sensitive attributes and models the task using partition DPPs.
A linear-time approximate sampler for partition DPPs is provably close to the target distribution under a natural condition on the input data.Partition-DPP sampling is otherwise intractable in a strong sense [7], and random data matrices satisfy the condition used for the guarantee.
Experiments on the Adult and curated image datasets improve fairness without substantially compromising geometric diversity.The paper also gives a theoretical explanation for this low price of fairness.
DPP-based sampling has applications in text, images, videos, documents, recommendation systems, and sensors, while constrained-DPP sampling remains computationally challenging [7].The authors position their method as the first near-linear-time algorithm for constrained DPPs.

2 Our Model

The model combines geometric diversity from DPPs with user-specified fairness constraints over disjoint sensitive classes. It defines P-DPPs as the most diverse distributions supported on fair subsets, while highlighting computational difficulty in sampling them.

Geometric diversity: Geometric diversity is the squared volume of the parallelepiped spanned by selected feature vectors, represented by the determinant of their row submatrix.Larger volume indicates a more diverse subset in feature space.
Determinantal distributions: A DPP assigns subset probability proportional to its determinant, and a k-DPP is the corresponding distribution restricted to subsets of size k.DPPs favor diverse subsets because including one item makes including similar items less likely.
Fairness constraints: P-DPPs restrict summaries to subsets containing exactly k_j points from each sensitive class, allowing fairness notions such as proportional representation.The class quotas satisfy ∑_{j=1}^p k_j = k, the requested summary size.
Fair determinantal distribution: The P-DPP is the distribution proportional to the k-DPP over fair subsets and zero elsewhere, making it the most diverse distribution subject to the specified fairness constraints.This distribution is characterized as minimizing KL divergence to the unconstrained distribution among distributions supported on the fair family.
Computational challenge: Sampling P-DPPs is computationally challenging because sampling from them is #P-hard, creating a complexity barrier for efficient exact algorithms.The framework’s flexibility in specifying fairness constraints comes at this computational cost.

3 Our Algorithm

The paper develops Sample-and-Project, an approximate sampler for partition DPPs that repeatedly samples within eligible partitions and projects remaining vectors orthogonally. Its approximation guarantee depends on β-balance, while unconstrained exact sampling is computationally difficult.

3.2 Our Sample and Project Algorithm: The determinant volume lemma expresses det(WW^⊤) as the product of squared projected-vector norms, motivating the algorithm’s projection steps.Each projection removes components in the span of previously processed vectors.
3.2 Our Sample and Project Algorithm: Algorithm 1 runs in O(mnk) time, whereas the only known exact P-DPP sampler runs in m^O(p) time and is polynomial only when p = O(1) [7].The approximate method performs linear work per sampled point relative to the Θ(mn) input size.
3.2 Our Sample and Project Algorithm: Sample-and-Project samples from eligible partitions, then orthogonalizes every remaining vector against the selected vector before continuing.The procedure maintains partition quotas and updates vectors using orthogonal projection.
3.3 Provable Guarantees for Our Algorithm: β-balance requires every partition’s singular values to remain within a factor β of the corresponding singular values of the full matrix.Geometrically, each partition’s feature ellipsoid must approximate the full-data ellipsoid.
3.3 Provable Guarantees for Our Algorithm: Under β-balance, Algorithm 1 always satisfies the partition constraints and its output distribution can be controlled relative to the corresponding P-DPP.The guarantee applies to sets containing exactly k_j elements from each partition.
3.3 Provable Guarantees for Our Algorithm: Without β-balance, the algorithm can fail: in a duplicated-basis construction, it outputs a set with non-zero determinant with exponentially small probability.The example has one partition spanning 2n dimensions and another spanning only n dimensions.

4 Price of Fairness

The price of fairness is measured by the KL-divergence between unconstrained k-DPP and partition-constrained P-DPP distributions. Under a δ-drop condition, this divergence is bounded, explaining when fairness constraints preserve most unconstrained probability mass.

The price of fairness is D_KL(q⋆||q), comparing partition-constrained P-DPP samples with unconstrained k-DPP samples.The P-DPP support is a subset of the corresponding k-DPP support.
A δ-drop partition requires each partition’s (k_i+1)-st singular value to be at most δ times its k_i-th singular value.When δ is small, each partition matrix is effectively rank-k_i.
If δ satisfies the theorem’s bound, the price of ensuring fairness is D_KL(q⋆||q) ≤ log 1/(1−ε).The same condition implies that most unconstrained k-DPP probability mass lies on subsets satisfying the partition constraints.

5.1 Algorithms and Baselines

The experiments compare unconstrained k-DPP and uniform sampling with fairness-constrained P-DPP and k_i-DPP methods. Fairness is evaluated through KL-divergence from either uniform or proportional representation, alongside geometric diversity.

The benchmarks are unconstrained k-DPP and UNIF, compared against fairness-constrained P-DPP and k_i-DPP.k_i-DPP independently samples k_i points from each partition and combines the samples.
Fairness is measured as D_q(S)=D_KL(q||s), where s records the selected frequency of each partition.D_un uses uniform target frequencies, while D_prop uses the dataset’s population proportions.
The experiments report geometric diversity G(·) together with unfairness under uniform and proportional representation targets.These metrics evaluate the diversity–fairness behavior of each sampling distribution.

5.2 Experiment on Image Dataset

The image experiments vary the proportion of male images in datasets built from scientist and painter searches. P-DPP substantially improves fairness while retaining geometric diversity close to unconstrained k-DPP.

Dataset construction: The image dataset uses four Google Image searches covering male and female scientists and painters, with male-image prevalence varied from 10% to 50%.All female images were included, while male images were subsampled to create biased datasets.
Results: P-DPP significantly outperforms k-DPP and UNIF on uniform unfairness D_un when the image dataset is biased by gender composition.The comparison is statistically significant under paired one-sided t-tests with p < 0.05.
Results: P-DPP has significantly higher geometric diversity G(·) than UNIF and k_i-DPP, while remaining statistically comparable to k-DPP.The mean diversity of k-DPP is higher, but the difference is not significant.
Results: When the underlying image data is biased, fairness differences can be very large while geometric-diversity differences are negligible.The observed tradeoff favors P-DPP for D_un and k-DPP for G(·).

5.3 Experiment on Real-World Dataset

On the Adult dataset, P-DPP achieves the highest diversity among constrained methods across gender and race settings. Its diversity often matches unconstrained k-DPP and remains only minimally lower in the remaining representation settings.

Experimental setup: The Adult experiments use gender and race partitions, with equal representation set to 50% per attribute and proportional representation matching population frequencies.The dataset contains 68.3% male and 31.7% female entries, and 85.7% Caucasian and 14.3% non-Caucasian entries.
Results: P-DPP has the highest diversity among constrained methods across both sensitive attributes and both representation targets.The comparison covers gender and race under equal and proportional representation.
Results: P-DPP matches unconstrained k-DPP in diversity for gender under proportional representation and race under equal representation.In the other two settings, its diversity is minimally lower than k-DPP and exceeds k_i-DPP by several standard deviations.
Results: ki-UNIF has poor overall geometric diversity but performs better under equal than proportional representation, suggesting equal selection may have value beyond fairness.This observation is reported as a suggestion rather than a demonstrated causal effect.
Results: The race experiment changes non-Caucasian representation from 14.3% in the dataset to 50% in the selected sample, yet P-DPP incurs minimal or zero geometric-diversity loss.The result supports substantial representation changes without materially reducing geometric diversity.

5.4 Experiment on Price of Fairness

The experiments evaluate how singular-value scaling affects fairness and geometric diversity, finding that Scale-And-Sample closely matches constrained sampling while preserving diversity.

5.4 Experiment on Price of Fairness: The experiment compares unscaled and tail-singular-value-scaled partition matrices using Dun(·) and log G(·).The tail singular values are scaled by δ = O(1/n).
5.4 Experiment on Price of Fairness: Mean Dun(·) for scaled k-DPP is very low and closely resembles the constrained-sampling case.
5.4 Experiment on Price of Fairness: Mean Dun(·) is almost zero for Scale-And-Sample, indicating near-zero relative unfairness under constrained sampling.The approach uses any k-DPP algorithm after scaling the smallest (n − ki) singular values by 1/n.
5.4 Experiment on Price of Fairness: The scaled approach retains geometric diversity, with log G(·) similar to unscaled P-DPP.

6 Proofs

The proofs establish properties of the KL-optimal constrained distribution, determinant-based matrix identities, rank conditions, and correctness conditions for the sampling algorithm.

6 Proofs: The KL-optimal distribution over constrained sets achieves minimum divergence log α from the reference distribution.The proof uses the nonnegativity of DKL(q||q⋆).
6 Proofs: The determinant lemma is proved by induction using elementary row and column operations that preserve the determinant.The base case relates det(WW ⊤) to the squared norm of the projected row vector.
6 Proofs: The remaining algebraic steps repeatedly eliminate matrix entries while preserving determinants and apply the induction hypothesis.
6 Proofs: The characteristic-polynomial proof connects coefficients of det(xI + VV ⊤) with principal minors and the singular values of V.
6 Proofs: Under β-balance, each partition matrix has rank at least k because it retains the number of non-zero singular values needed for k-sized diversity.This rank property is used to rule out zero-determinant outputs during sampling.
6 Proofs: The algorithm can produce a zero determinant only if an underrepresented partition has all remaining vectors in the span of previously selected vectors, contradicting the rank condition.

7 Conclusion and Future Work

The paper concludes that fair DPP sampling can preserve diversity under biased data, while identifying approximation, structural, and downstream-learning questions for future work.

7 Conclusion and Future Work: Fairness constraints cause minimal loss to diversity even when the dataset is very biased or attribute proportions change significantly.
7 Conclusion and Future Work: The method has provably good guarantees when the data matrix satisfies the natural β-balance property, which the paper shows many datasets satisfy.
7 Conclusion and Future Work: Future theory should improve approximation guarantees, weaken necessary conditions, and extend results from partitions to arbitrary group structures.The extension to arbitrary group structures is described as significantly more challenging.
7 Conclusion and Future Work: The downstream effects of debiasing on machine-learning accuracy and later bias remain unresolved.The paper specifically identifies classification as an example of a downstream task.