Fairness, Semi-Supervised Learning, and More: A General Framework for Clustering with Stochastic Pairwise Constraints
Metric clustering is fundamental in areas ranging from Combinatorial Optimization and Data Mining, to Machine Learning and Operations Research. However, in a variety of situations we may have additional requirements or knowledge, distinct from the underlying metric, regarding which pairs of points should be clustered together. To capture and analyze such scenarios, we introduce a novel family of \emph{stochastic pairwise constraints}, which we incorporate into several essential clustering objectives (radius/median/means). Moreover, we demonstrate that these constraints can succinctly model an intriguing collection of applications, including among others \emph{Individual Fairness} in clustering and \emph{Must-link} constraints in semi-supervised learning. Our main result consists of a general framework that yields approximation algorithms with provable guarantees for important clustering objectives, while at the same time producing solutions that respect the stochastic pairwise constraints. Furthermore, for certain objectives we devise improved results in the case of Must-link constraints, which are also the best possible from a theoretical perspective. Finally, we present experimental evidence that validates the effectiveness of our algorithms.
Code (1)
Tasks
ClusteringCombinatorial OptimizationFairnessSimilar Papers 제목 키워드 기반
Fairness Constraints in Semi-supervised Learning
Fairness in machine learning has received considerable attention. However, most studies on fair learning focus on either supervised learning or unsupervised learning. Very few consider semi-supervised settings. Yet, in r…
BIG-bench Machine LearningFairnessLeveraging Semi-Supervised Learning for Fairness using Neural Networks
There has been a growing concern about the fairness of decision-making systems based on machine learning. The shortage of labeled data has been always a challenging problem facing machine learning based systems. In such …
BIG-bench Machine LearningDecision MakingFairnessFairness in Semi-supervised Learning: Unlabeled Data Help to Reduce Discrimination
A growing specter in the rise of machine learning is whether the decisions made by machine learning models are fair. While research is already underway to formalize a machine-learning concept of fairness and to design fr…
BIG-bench Machine LearningEnsemble LearningFairnessAdaptation and Generalization for Unknown Sensitive Factors of Variations
Assured AI in unrestricted settings is a critical problem. Our framework addresses AI assurance challenges lying at the intersection of domain adaptation, fairness, and counterfactuals analysis, operating via the discove…
Domain AdaptationDomain GeneralizationFairnessSubgroup Generalization and Fairness of Graph Neural Networks
Despite enormous successful applications of graph neural networks (GNNs), theoretical understanding of their generalization ability, especially for node-level tasks where data are not independent and identically-distribu…
Fairness