Clustering is a fundamental problem in unsupervised machine learning, and fair variants of it have recently received significant attention due to its societal implications. In this work we introduce a novel definition of individual fairness for clustering problems. Specifically, in our model, each point $j$ has a set of other points $\mathcal{S}_j$ that it perceives as similar to itself, and it feels that it is fairly treated if the quality of service it receives in the solution is $\alpha$-close (in a multiplicative sense, for a given $\alpha \geq 1$) to that of the points in $\mathcal{S}_j$. We begin our study by answering questions regarding the structure of the problem, namely for what values of $\alpha$ the problem is well-defined, and what the behavior of the \emph{Price of Fairness (PoF)} for it is. For the well-defined region of $\alpha$, we provide efficient and easily-implementable approximation algorithms for the $k$-center objective, which in certain cases enjoy bounded-PoF guarantees. We finally complement our analysis by an extensive suite of experiments that validates the effectiveness of our theoretical results.


翻译:集成是不受监督的机器学习中的一个根本问题, 其公平的变种最近因其社会影响而受到极大关注。 在这项工作中, 我们引入了个人对集群问题公平性的新定义。 具体地说, 在我们的模型中, 每点美元都有一系列其他的点数 $mathcal{S ⁇ j$, 它自认为与自己相似, 并且它觉得如果它在解决方案中获得的服务质量质量为$alpha$- close( 从多种意义上讲, 给的$\alpha\ ge $1美元) 与$\ mathcal{S ⁇ j$的点的点数相比, 它得到了公平对待。 我们从研究开始, 我们从回答关于问题结构的问题开始, 即 $\ alpha$ 的值是多少, 问题本身认为与自己相似, 以及 它的行为是什么样的。 如果它在解决方案中得到的服务质量是 $alpha- closeal, 我们为$- center目标提供了高效和易于执行的近似的近算算算算算算算算算法, 我们最终享受了理论上的验证结果。

0
下载
关闭预览

相关内容

【AAAI2021】对比聚类,Contrastive Clustering
专知会员服务
76+阅读 · 2021年1月30日
专知会员服务
123+阅读 · 2020年9月8日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
2019年机器学习框架回顾
专知会员服务
35+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
已删除
将门创投
4+阅读 · 2017年12月5日
Arxiv
0+阅读 · 2021年11月25日
Meta-Learning to Cluster
Arxiv
17+阅读 · 2019年10月30日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
已删除
将门创投
4+阅读 · 2017年12月5日
Top
微信扫码咨询专知VIP会员