Timezone: »
Poster
Fairness constraints can help exact inference in structured prediction
Kevin Bello · Jean Honorio
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 $\bar{y}$, it has been previously shown that when G has good expansion properties, such as complete graphs or dregular expanders, one can exactly recover $\bar{y}$ (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 tradeoffs 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 of achieving exact recovery. Finally, as a byproduct of our analysis, we provide a tighter minimumeigenvalue bound than that which can be derived from Weyl's inequality.
Author Information
Kevin Bello (Purdue University)
Jean Honorio (Purdue University)
More from the Same Authors

2021 Spotlight: Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem »
Adarsh Barik · Jean Honorio 
2022 Poster: Support Recovery in Sparse PCA with Incomplete Data »
Hanbyul Lee · Qifan Song · Jean Honorio 
2021 Poster: Inverse Reinforcement Learning in a Continuous State Space with Formal Guarantees »
Gregory Dexter · Kevin Bello · Jean Honorio 
2021 Poster: Fair Sparse Regression with Clustering: An Invex Relaxation for a Combinatorial Problem »
Adarsh Barik · Jean Honorio 
2019 Poster: Learning Bayesian Networks with Low Rank Conditional Probability Tables »
Adarsh Barik · Jean Honorio 
2019 Poster: On the Correctness and Sample Complexity of Inverse Reinforcement Learning »
Abi Komanduru · Jean Honorio 
2019 Poster: Exact inference in structured prediction »
Kevin Bello · Jean Honorio 
2018 Poster: Learning latent variable structured prediction models with Gaussian perturbations »
Kevin Bello · Jean Honorio 
2018 Poster: Informationtheoretic Limits for Community Detection in Network Models »
Chuyang Ke · Jean Honorio 
2018 Poster: Computationally and statistically efficient learning of causal Bayes nets using path queries »
Kevin Bello · Jean Honorio 
2017 Poster: Learning Identifiable Gaussian Bayesian Networks in Polynomial Time and Sample Complexity »
Asish Ghoshal · Jean Honorio