Ensuring fairness in machine learning algorithms is a challenging and important task. We consider the problem of clustering a set of points while ensuring fairness constraints. While there have been several attempts to capture group fairness in the k-clustering problem, fairness at an individual level is not well-studied. We introduce a new notion of individual fairness in k-clustering based on features that are not necessarily used for clustering. We show that this problem is NP-hard and does not admit a constant factor approximation. We then design a randomized algorithm that guarantees approximation both in terms of minimizing the clustering distance objective as well as individual fairness under natural restrictions on the distance metric and fairness constraints. Finally, our experimental results validate that our algorithm produces lower clustering costs compared to existing algorithms while being competitive in individual fairness.


翻译:确保机器学习算法的公平性是一项具有挑战性和重要的任务。 我们认为,在确保公平性限制的同时,将一组点分组的问题是一个具有挑战性的重要任务。 虽然在k类集问题中曾几次试图抓住群体公平性,但对个人层面的公平性没有很好地研究。 我们根据不一定用于集群的特征,在k类集中引入了个人公平的新概念。 我们表明,这个问题是NP硬的,并不接受一个恒定的系数近似值。 然后我们设计一种随机化算法,保证在限制距离度和公平性限制的自然限制下,尽可能减少集群的距离目标和个人公平性。 最后,我们的实验结果证实,我们的算法比现有的算法产生较低的集群成本,同时在个人公平性方面具有竞争力。

0
下载
关闭预览

相关内容

专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
27+阅读 · 2021年5月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
LibRec 精选:CCF TPCI 的推荐系统专刊征稿
LibRec智能推荐
4+阅读 · 2019年1月12日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
Arxiv
0+阅读 · 2021年11月1日
Arxiv
0+阅读 · 2021年11月1日
Arxiv
0+阅读 · 2021年10月31日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月28日
VIP会员
相关VIP内容
专知会员服务
14+阅读 · 2021年5月21日
专知会员服务
27+阅读 · 2021年5月2日
因果图,Causal Graphs,52页ppt
专知会员服务
246+阅读 · 2020年4月19日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
LibRec 精选:近期15篇推荐系统论文
LibRec智能推荐
5+阅读 · 2019年3月5日
LibRec 精选:CCF TPCI 的推荐系统专刊征稿
LibRec智能推荐
4+阅读 · 2019年1月12日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
gan生成图像at 1024² 的 代码 论文
CreateAMind
4+阅读 · 2017年10月31日
【计算机类】期刊专刊/国际会议截稿信息6条
Call4Papers
3+阅读 · 2017年10月13日
相关论文
Arxiv
0+阅读 · 2021年11月1日
Arxiv
0+阅读 · 2021年11月1日
Arxiv
0+阅读 · 2021年10月31日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月29日
Arxiv
0+阅读 · 2021年10月28日
Top
微信扫码咨询专知VIP会员