Robust Inference for Multiclass Classification

Uriel Feige, Yishay Mansour, Robert E. Schapire
Proceedings of Algorithmic Learning Theory, PMLR 83:368-386, 2018.

Abstract

We consider the problem of robust inference in which inputs may be maliciously corrupted by a powerful adversary, and the learner’s goal is to accurately predict the original, uncorrupted input’s true label given only the adversarially corrupted version of the input. We specifically focus on the multiclass version of this problem in which more than two labels are possible. We substantially extend and generalize previous work which had only considered the binary case, thus uncovering stark differences between the two cases. We show how robust inference can be modeled as a zero-sum game between a learner who maximizes the expected accuracy, and an adversary. The value of this game is the best-attainable accuracy rate of any algorithm. We then show how the optimal policy for both the learner and adversary can be exactly characterized in terms of a particular hypergraph, specifically, as the hypergraph’s maximum fractional independent set and minimum fractional set cover, respectively. This characterization yields efficient algorithms in the size of the domain (number of possible inputs). For the typical setting that the domain is huge, we also design efficient local computation algorithms for approximating maximum fractional independent set in hypergraphs. This leads to a near optimal algorithm for the learner whose complexity is independent of the domain size, instead depending only on the rank and maximum degree of the underlying hypergraph, and on the desired approximation ratio.

Cite this Paper

BibTeX
@InProceedings{pmlr-v83-feige18a, title = {Robust Inference for Multiclass Classification}, author = {Feige, Uriel and Mansour, Yishay and Schapire, Robert E.}, booktitle = {Proceedings of Algorithmic Learning Theory}, pages = {368--386}, year = {2018}, editor = {Janoos, Firdaus and Mohri, Mehryar and Sridharan, Karthik}, volume = {83}, series = {Proceedings of Machine Learning Research}, month = {07--09 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v83/feige18a/feige18a.pdf}, url = {https://proceedings.mlr.press/v83/feige18a.html}, abstract = {We consider the problem of robust inference in which inputs may be maliciously corrupted by a powerful adversary, and the learner’s goal is to accurately predict the original, uncorrupted input’s true label given only the adversarially corrupted version of the input. We specifically focus on the multiclass version of this problem in which more than two labels are possible. We substantially extend and generalize previous work which had only considered the binary case, thus uncovering stark differences between the two cases. We show how robust inference can be modeled as a zero-sum game between a learner who maximizes the expected accuracy, and an adversary. The value of this game is the best-attainable accuracy rate of any algorithm. We then show how the optimal policy for both the learner and adversary can be exactly characterized in terms of a particular hypergraph, specifically, as the hypergraph’s maximum fractional independent set and minimum fractional set cover, respectively. This characterization yields efficient algorithms in the size of the domain (number of possible inputs). For the typical setting that the domain is huge, we also design efficient local computation algorithms for approximating maximum fractional independent set in hypergraphs. This leads to a near optimal algorithm for the learner whose complexity is independent of the domain size, instead depending only on the rank and maximum degree of the underlying hypergraph, and on the desired approximation ratio.} }
Endnote
%0 Conference Paper %T Robust Inference for Multiclass Classification %A Uriel Feige %A Yishay Mansour %A Robert E. Schapire %B Proceedings of Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2018 %E Firdaus Janoos %E Mehryar Mohri %E Karthik Sridharan %F pmlr-v83-feige18a %I PMLR %P 368--386 %U https://proceedings.mlr.press/v83/feige18a.html %V 83 %X We consider the problem of robust inference in which inputs may be maliciously corrupted by a powerful adversary, and the learner’s goal is to accurately predict the original, uncorrupted input’s true label given only the adversarially corrupted version of the input. We specifically focus on the multiclass version of this problem in which more than two labels are possible. We substantially extend and generalize previous work which had only considered the binary case, thus uncovering stark differences between the two cases. We show how robust inference can be modeled as a zero-sum game between a learner who maximizes the expected accuracy, and an adversary. The value of this game is the best-attainable accuracy rate of any algorithm. We then show how the optimal policy for both the learner and adversary can be exactly characterized in terms of a particular hypergraph, specifically, as the hypergraph’s maximum fractional independent set and minimum fractional set cover, respectively. This characterization yields efficient algorithms in the size of the domain (number of possible inputs). For the typical setting that the domain is huge, we also design efficient local computation algorithms for approximating maximum fractional independent set in hypergraphs. This leads to a near optimal algorithm for the learner whose complexity is independent of the domain size, instead depending only on the rank and maximum degree of the underlying hypergraph, and on the desired approximation ratio.
APA
Feige, U., Mansour, Y. & Schapire, R.E.. (2018). Robust Inference for Multiclass Classification. Proceedings of Algorithmic Learning Theory, in Proceedings of Machine Learning Research 83:368-386 Available from https://proceedings.mlr.press/v83/feige18a.html.

Related Material