论文标题
公平限制可以帮助精确推断结构化预测
Fairness constraints can help exact inference in structured prediction
论文作者
论文摘要
结构化预测中的许多推理问题可以建模为在标签空间上最大化得分函数，在该空间中，图是将总分分解为一单位（节点）和成对（边缘）分数之和的自然表示。给定具有无方向连接的图形$ g $和二进制标签的真实向量的生成模型，先前已经显示，当$ g $具有良好的扩展属性时，例如完整的图形或$ d $的规范扩展器，就可以从每个边缘和node的单个噪声中恢复真实的标签（具有很高的概率和多项式时间）。我们分析了Globerson等人先前研究的生成模型。 （2015）统计平等概念。也就是说，给定一个公平的二进制节点标记，我们问一个问题，是否有可能从单个边缘和节点观测值中以很高的概率和多项式时间恢复公平分配。我们发现，与公平性和模型性能之间的已知权衡取舍相反，公平限制的增加可提高精确恢复的可能性。我们有效地解释了这一现象，并从经验上展示了膨胀特性（例如网格）的图形如何以高概率实现精确恢复。最后，作为我们分析的副产品，我们提供了比Weyl不平等的更低的最小元素价值结合。
Many inference problems in structured prediction can be modeled as maximizing a score function on a space of labels, where graphs are a natural representation to decompose the total score into a sum of unary (nodes) and pairwise (edges) scores. Given a generative model with an undirected connected graph $G$ and true vector of binary labels, it has been previously shown that when $G$ has good expansion properties, such as complete graphs or $d$-regular expanders, one can exactly recover the true labels (with high probability and in polynomial time) from a single noisy observation of each edge and node. We analyze the previously studied generative model by Globerson et al. (2015) under a notion of statistical parity. That is, given a fair binary node labeling, we ask the question whether it is possible to recover the fair assignment, with high probability and in polynomial time, from single edge and node observations. We find that, in contrast to the known trade-offs between fairness and model performance, the addition of the fairness constraint improves the probability of exact recovery. We effectively explain this phenomenon and empirically show how graphs with poor expansion properties, such as grids, are now capable to achieve exact recovery with high probability. Finally, as a byproduct of our analysis, we provide a tighter minimum-eigenvalue bound than that of Weyl's inequality.
