Exact inference in structured prediction. Bello, K. & Honorio, J. *<span style="color: #0088cc; font-style: normal">NeurIPS-19.</span> Advances in Neural Information Processing Systems*, 2019. Proceedings Preprint abstract bibtex 1 download Structured prediction can be thought of as a simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise and unary potentials. The above is naturally modeled with a graph, where edges and vertices are related to pairwise and unary potentials, respectively. We consider the generative process proposed by Globerson et al. (2015) and apply it to general connected graphs. We analyze the structural conditions of the graph that allow for the exact recovery of the labels. Our results show that exact recovery is possible and achievable in polynomial time for a large class of graphs. In particular, we show that graphs that are bad expanders can be exactly recovered by adding small edge perturbations coming from the Erdos-Renyi model. Finally, as a byproduct of our analysis, we provide an extension of Cheeger's inequality.

@article{bello2019exact,
title={Exact inference in structured prediction},
author={Bello, Kevin and Honorio, Jean},
journal={<span style="color: #0088cc; font-style: normal">NeurIPS-19.</span> Advances in Neural Information Processing Systems},
abstract={Structured prediction can be thought of as a simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise and unary potentials. The above is naturally modeled with a graph, where edges and vertices are related to pairwise and unary potentials, respectively. We consider the generative process proposed by Globerson et al. (2015) and apply it to general connected graphs. We analyze the structural conditions of the graph that allow for the exact recovery of the labels. Our results show that exact recovery is possible and achievable in polynomial time for a large class of graphs. In particular, we show that graphs that are bad expanders can be exactly recovered by adding small edge perturbations coming from the Erdos-Renyi model. Finally, as a byproduct of our analysis, we provide an extension of Cheeger's inequality.},
volume={32},
year={2019},
url_proceedings={https://papers.nips.cc/paper_files/paper/2019/hash/312351bff07989769097660a56395065-Abstract.html},
url_preprint={https://arxiv.org/pdf/1906.00451.pdf},
keyword={Statistical Machine Learning,Optimization,Causality and Graphical Models},
}

Downloads: 1

{"_id":"wgiWw6nPPkfmq9QAW","bibbaseid":"bello-honorio-exactinferenceinstructuredprediction-2019","author_short":["Bello, K.","Honorio, J."],"bibdata":{"bibtype":"article","type":"article","title":"Exact inference in structured prediction","author":[{"propositions":[],"lastnames":["Bello"],"firstnames":["Kevin"],"suffixes":[]},{"propositions":[],"lastnames":["Honorio"],"firstnames":["Jean"],"suffixes":[]}],"journal":"<span style=\"color: #0088cc; font-style: normal\">NeurIPS-19.</span> Advances in Neural Information Processing Systems","abstract":"Structured prediction can be thought of as a simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise and unary potentials. The above is naturally modeled with a graph, where edges and vertices are related to pairwise and unary potentials, respectively. We consider the generative process proposed by Globerson et al. (2015) and apply it to general connected graphs. We analyze the structural conditions of the graph that allow for the exact recovery of the labels. Our results show that exact recovery is possible and achievable in polynomial time for a large class of graphs. In particular, we show that graphs that are bad expanders can be exactly recovered by adding small edge perturbations coming from the Erdos-Renyi model. Finally, as a byproduct of our analysis, we provide an extension of Cheeger's inequality.","volume":"32","year":"2019","url_proceedings":"https://papers.nips.cc/paper_files/paper/2019/hash/312351bff07989769097660a56395065-Abstract.html","url_preprint":"https://arxiv.org/pdf/1906.00451.pdf","keyword":["Statistical Machine Learning","Optimization","Causality and Graphical Models"],"bibtex":"@article{bello2019exact,\n title={Exact inference in structured prediction},\n author={Bello, Kevin and Honorio, Jean},\n journal={<span style=\"color: #0088cc; font-style: normal\">NeurIPS-19.</span> Advances in Neural Information Processing Systems},\n abstract={Structured prediction can be thought of as a simultaneous prediction of multiple labels. This is often done by maximizing a score function on the space of labels, which decomposes as a sum of pairwise and unary potentials. The above is naturally modeled with a graph, where edges and vertices are related to pairwise and unary potentials, respectively. We consider the generative process proposed by Globerson et al. (2015) and apply it to general connected graphs. We analyze the structural conditions of the graph that allow for the exact recovery of the labels. Our results show that exact recovery is possible and achievable in polynomial time for a large class of graphs. In particular, we show that graphs that are bad expanders can be exactly recovered by adding small edge perturbations coming from the Erdos-Renyi model. Finally, as a byproduct of our analysis, we provide an extension of Cheeger's inequality.},\n volume={32},\n year={2019},\n url_proceedings={https://papers.nips.cc/paper_files/paper/2019/hash/312351bff07989769097660a56395065-Abstract.html},\n url_preprint={https://arxiv.org/pdf/1906.00451.pdf},\n keyword={Statistical Machine Learning,Optimization,Causality and Graphical Models},\n}\n\n","author_short":["Bello, K.","Honorio, J."],"key":"bello2019exact","id":"bello2019exact","bibbaseid":"bello-honorio-exactinferenceinstructuredprediction-2019","role":"author","urls":{" proceedings":"https://papers.nips.cc/paper_files/paper/2019/hash/312351bff07989769097660a56395065-Abstract.html"," preprint":"https://arxiv.org/pdf/1906.00451.pdf"},"metadata":{"authorlinks":{}},"downloads":1},"bibtype":"article","biburl":"junzhez.com/junzhez.bib","dataSources":["F26AnfY8gE9wMaNyy","CavkB2Lkd3jh4oMwt","HrmPSc7G6y6hJHcfF","nuxfbQ2S44wcaktWS","prcvE6Y2PvawRuuAq","hzL8QYDRKjBmF7mYQ","tvHnp37BztDCaTaD4","qdkS3Ci7YjmkLPrb2"],"keywords":["statistical machine learning","optimization","causality and graphical models"],"search_terms":["exact","inference","structured","prediction","bello","honorio"],"title":"Exact inference in structured prediction","year":2019,"downloads":1}