Distributional Individual Fairness in Clustering
- URL: http://arxiv.org/abs/2006.12589v1
- Date: Mon, 22 Jun 2020 20:02:09 GMT
- Title: Distributional Individual Fairness in Clustering
- Authors: Nihesh Anderson, Suman K. Bera, Syamantak Das, Yang Liu
- Abstract summary: We introduce a framework for assigning individuals, embedded in a metric space, to probability distributions over a bounded number of cluster centers.
We provide an algorithm for clustering with $p$-norm objective and individual fairness constraints with provable approximation guarantee.
- Score: 7.303841123034983
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we initiate the study of fair clustering that ensures
distributional similarity among similar individuals. In response to improving
fairness in machine learning, recent papers have investigated fairness in
clustering algorithms and have focused on the paradigm of statistical
parity/group fairness. These efforts attempt to minimize bias against some
protected groups in the population. However, to the best of our knowledge, the
alternative viewpoint of individual fairness, introduced by Dwork et al. (ITCS
2012) in the context of classification, has not been considered for clustering
so far. Similar to Dwork et al., we adopt the individual fairness notion which
mandates that similar individuals should be treated similarly for clustering
problems. We use the notion of $f$-divergence as a measure of statistical
similarity that significantly generalizes the ones used by Dwork et al. We
introduce a framework for assigning individuals, embedded in a metric space, to
probability distributions over a bounded number of cluster centers. The
objective is to ensure (a) low cost of clustering in expectation and (b)
individuals that are close to each other in a given fairness space are mapped
to statistically similar distributions.
We provide an algorithm for clustering with $p$-norm objective ($k$-center,
$k$-means are special cases) and individual fairness constraints with provable
approximation guarantee. We extend this framework to include both group
fairness and individual fairness inside the protected groups. Finally, we
observe conditions under which individual fairness implies group fairness. We
present extensive experimental evidence that justifies the effectiveness of our
approach.
Related papers
- A Universal Unbiased Method for Classification from Aggregate
Observations [115.20235020903992]
This paper presents a novel universal method of CFAO, which holds an unbiased estimator of the classification risk for arbitrary losses.
Our proposed method not only guarantees the risk consistency due to the unbiased risk estimator but also can be compatible with arbitrary losses.
arXiv Detail & Related papers (2023-06-20T07:22:01Z) - How Robust is Your Fairness? Evaluating and Sustaining Fairness under
Unseen Distribution Shifts [107.72786199113183]
We propose a novel fairness learning method termed CUrvature MAtching (CUMA)
CUMA achieves robust fairness generalizable to unseen domains with unknown distributional shifts.
We evaluate our method on three popular fairness datasets.
arXiv Detail & Related papers (2022-07-04T02:37:50Z) - Improved Approximation for Fair Correlation Clustering [4.629694186457133]
Correlation clustering is a ubiquitous paradigm in unsupervised machine learning where addressing unfairness is a major challenge.
Motivated by this, we study Fair Correlation Clustering where the data points may belong to different protected groups.
Our paper significantly generalizes and improves on the quality guarantees of previous work of Ahmadi et al. and Ahmadian et al.
arXiv Detail & Related papers (2022-06-09T03:07:57Z) - Measuring Fairness of Text Classifiers via Prediction Sensitivity [63.56554964580627]
ACCUMULATED PREDICTION SENSITIVITY measures fairness in machine learning models based on the model's prediction sensitivity to perturbations in input features.
We show that the metric can be theoretically linked with a specific notion of group fairness (statistical parity) and individual fairness.
arXiv Detail & Related papers (2022-03-16T15:00:33Z) - Fair Group-Shared Representations with Normalizing Flows [68.29997072804537]
We develop a fair representation learning algorithm which is able to map individuals belonging to different groups in a single group.
We show experimentally that our methodology is competitive with other fair representation learning algorithms.
arXiv Detail & Related papers (2022-01-17T10:49:49Z) - Fair Clustering Under a Bounded Cost [33.50262066253557]
Clustering is a fundamental unsupervised learning problem where a dataset is partitioned into clusters that consist of nearby points in a metric space.
A recent variant, fair clustering, associates a color with each point representing its group membership and requires that each color has (approximately) equal representation in each cluster to satisfy group fairness.
We consider two fairness objectives: the group utilitarian objective and the group egalitarian objective, as well as the group leximin objective which generalizes the group egalitarian objective.
arXiv Detail & Related papers (2021-06-14T08:47:36Z) - You Never Cluster Alone [150.94921340034688]
We extend the mainstream contrastive learning paradigm to a cluster-level scheme, where all the data subjected to the same cluster contribute to a unified representation.
We define a set of categorical variables as clustering assignment confidence, which links the instance-level learning track with the cluster-level one.
By reparametrizing the assignment variables, TCC is trained end-to-end, requiring no alternating steps.
arXiv Detail & Related papers (2021-06-03T14:59:59Z) - MultiFair: Multi-Group Fairness in Machine Learning [52.24956510371455]
We study multi-group fairness in machine learning (MultiFair)
We propose a generic end-to-end algorithmic framework to solve it.
Our proposed framework is generalizable to many different settings.
arXiv Detail & Related papers (2021-05-24T02:30:22Z) - Metric-Free Individual Fairness with Cooperative Contextual Bandits [17.985752744098267]
Group fairness requires that different groups should be treated similarly which might be unfair to some individuals within a group.
Individual fairness remains understudied due to its reliance on problem-specific similarity metrics.
We propose a metric-free individual fairness and a cooperative contextual bandits algorithm.
arXiv Detail & Related papers (2020-11-13T03:10:35Z) - A Pairwise Fair and Community-preserving Approach to k-Center Clustering [34.386585230600716]
Clustering is a foundational problem in machine learning with numerous applications.
We define two new types of fairness in the clustering setting, pairwise fairness and community preservation.
arXiv Detail & Related papers (2020-07-14T22:32:27Z) - A Notion of Individual Fairness for Clustering [22.288902523866867]
A common distinction in fair machine learning, in particular in fair classification, is between group fairness and individual fairness.
In this paper, we propose a natural notion of individual fairness for clustering. Our notion asks that every data point, on average, is closer to the points in its own cluster than to the points in any other cluster.
arXiv Detail & Related papers (2020-06-08T21:41:39Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.