Approximate Inference in Structured Instances with Noisy Categorical Observations

Alireza Heidari, Ihab F. Ilyas, Theodoros Rekatsinas
Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, PMLR 115:412-421, 2020.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v115-heidari20a, title = {Approximate Inference in Structured Instances with Noisy Categorical Observations}, author = {Heidari, Alireza and Ilyas, Ihab F. and Rekatsinas, Theodoros}, booktitle = {Proceedings of The 35th Uncertainty in Artificial Intelligence Conference}, pages = {412--421}, year = {2020}, editor = {Adams, Ryan P. and Gogate, Vibhav}, volume = {115}, series = {Proceedings of Machine Learning Research}, month = {22--25 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v115/heidari20a/heidari20a.pdf}, url = {https://proceedings.mlr.press/v115/heidari20a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Approximate Inference in Structured Instances with Noisy Categorical Observations %A Alireza Heidari %A Ihab F. Ilyas %A Theodoros Rekatsinas %B Proceedings of The 35th Uncertainty in Artificial Intelligence Conference %C Proceedings of Machine Learning Research %D 2020 %E Ryan P. Adams %E Vibhav Gogate %F pmlr-v115-heidari20a %I PMLR %P 412--421 %U https://proceedings.mlr.press/v115/heidari20a.html %V 115 %X 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.
APA
Heidari, A., Ilyas, I.F. & Rekatsinas, T.. (2020). Approximate Inference in Structured Instances with Noisy Categorical Observations. Proceedings of The 35th Uncertainty in Artificial Intelligence Conference, in Proceedings of Machine Learning Research 115:412-421 Available from https://proceedings.mlr.press/v115/heidari20a.html.

Related Material