ARC: Adversarial Robust Cuts for Semi-Supervised and Multi-Label Classification

Authors

  • Sima Behpour University of Illinois at Chicago
  • Wei Xing University of Illinois at Chicago
  • Brian Ziebart University of Illinois at Chicago

DOI:

https://doi.org/10.1609/aaai.v32i1.11817

Keywords:

Adversarial structured prediction, Graph cut, multi-label prediction, semi-supervised classification

Abstract

Many structured prediction tasks arising in computer vision and natural language processing tractably reduce to making minimum cost cuts in graphs with edge weights learned using maximum margin methods. Unfortunately, the hinge loss used to construct these methods often provides a particularly loose bound on the loss function of interest (e.g., the Hamming loss). We develop Adversarial Robust Cuts (ARC), an approach that poses the learning task as a minimax game between predictor and "label approximator" based on minimum cost graph cuts. Unlike maximum margin methods, this game-theoretic perspective always provides meaningful bounds on the Hamming loss. We conduct multi-label and semi-supervised binary prediction experiments that demonstrate the benefits of our approach.

Downloads

Published

2018-04-29

How to Cite

Behpour, S., Xing, W., & Ziebart, B. (2018). ARC: Adversarial Robust Cuts for Semi-Supervised and Multi-Label Classification. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). https://doi.org/10.1609/aaai.v32i1.11817