Online Set Selection with Fairness and Diversity Constraints
Online Set Selection with Fairness and Diversity Constraints
复制标题
DOI：
10.5441/002/edbt.2018.22
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Julia Stoyanovich;Ke Yang;H. V. Jagadish
中科院分区：
文献类型：
--
作者：
Julia Stoyanovich;Ke Yang;H. V. Jagadish
选择算法通常孤立地为单个项目评分，然后选择最高的评分项目。但是，通常还有一个额外的多样性目标。由于多样性是一个集体属性，因此它不容易与单个项目评分相提并论。在本文中，我们研究了受多样性和群体公平限制的选择设置查询。我们为通过流数据开发了几种问题设置的算法，在此过程中必须对每个项目做出在线决策。通过使用真实和合成数据的实验，我们可以表明可以实现公平和多样性，通常在质量方面成本适中。我们的实验评估会导致在线选择中的几个重要见解。我们证明，解决方案质量的理论保证在实际数据集中是保守的，并且调整得分估计阶段的长度会导致有趣的准确性效率折衷。此外，我们表明，如果组之间的分数差异差异，则必须在处理过程中分别处理这些组。否则，可以得出符合多样性限制的解决方案，但选择弱势群体的得分较低成员。
Selection algorithms usually score individual items in isolation, and then select the top scoring items. However, often there is an additional diversity objective. Since diversity is a group property, it does not easily jibe with individual item scoring. In this paper, we study set selection queries subject to diversity and group fairness constraints. We develop algorithms for several problem settings with streaming data, where an online decision must be made on each item as it is presented. We show through experiments with real and synthetic data that fairness and diversity can be achieved, usually with modest costs in terms of quality. Our experimental evaluation leads to several important insights in online set selection. We demonstrate that theoretical guarantees on solution quality are conservative in real datasets, and that tuning the length of the score estimation phase leads to an interesting accuracy-efficiency trade-off. Further, we show that if a difference in scores is expected between groups, then these groups must be treated separately during processing. Otherwise, a solution may be derived that meets diversity constraints, but that selects lower-scoring members of disadvantaged groups.