Exact inference in structured prediction
Authors: Kevin Bello, Jean Honorio
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | 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 Erd os Rényi model. Finally, as a byproduct of our analysis, we provide an extension of Cheeger s inequality. The paper primarily presents mathematical theorems, proofs, and theoretical analyses related to graph properties and conditions for exact recovery, without reporting on empirical experiments or dataset evaluations. |
| Researcher Affiliation | Academia | Kevin Bello Department of Computer Science Purdue Univeristy West Lafayette, IN 47906, USA kbellome@purdue.edu Jean Honorio Department of Computer Science Purdue Univeristy West Lafayette, IN 47906, USA jhonorio@purdue.edu |
| Pseudocode | No | The paper does not contain any pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper is theoretical and does not describe experiments involving specific datasets or their training splits. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments involving specific datasets or their validation splits. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require hardware specifications. |
| Software Dependencies | No | The paper is theoretical and does not describe any experiments that would require software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experimental setup details or hyperparameters. |