Abstract

In this paper we develop an algorithm for structured predic- tion that optimizes against complex performance measures, those which are a function of false positive and false negative counts. The approach can be directly applied to performance measures such as F? score (natu- ral language processing), intersection over union (image segmentation), Precision/Recall at k (search engines) and ROC area (binary classifiers). We attack this optimization problem by approximating the loss function with a piecewise linear function and relaxing the obtained QP problem to a LP which we solve with an off-the-shelf LP solver. We present ex- periments on ob ject class-specific segmentation and show significant im- provement over baseline approaches that either use simple loss functions or simple compatibility functions on VOC 2009.