Approximate Inference in Structured Instances with Noisy Categorical Observations
This addresses structured prediction with categorical labels, generalizing prior binary-label work, but appears incremental as it extends existing methods to categorical cases.
The paper tackles the problem of recovering latent categorical labels in structured instances with noisy observations, presenting an approximate algorithm that achieves low Hamming error with a logarithmic dependency on the number of categories.
We study the problem of recovering the latent ground truth labeling of a structured instance with categorical random variables in the presence of noisy observations. We present a new approximate algorithm for graphs with categorical variables that achieves low Hamming error in the presence of noisy vertex and edge observations. Our main result shows a logarithmic dependency of the Hamming error to the number of categories of the random variables. Our approach draws connections to correlation clustering with a fixed number of clusters. Our results generalize the works of Globerson et al. (2015) and Foster et al. (2018), who study the hardness of structured prediction under binary labels, to the case of categorical labels.