Optimizing nondecomposable loss functions in structured prediction

Abstract

We develop an algorithm for structured prediction with nondecomposable performance measures. The algorithm learns parameters of Markov Random Fields (MRFs) and can be applied to multivariate performance measures. Examples include performance measures such as Fβ score (natural language processing), intersection over union (object category 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. The loss augmented inference forms a Quadratic Program (QP), which we solve using LP relaxation. We apply this approach to two tasks: object class-specific segmentation and human action retrieval from videos. We show significant improvement over baseline approaches that either use simple loss functions or simple scoring functions on the PASCAL VOC and H3D Segmentation datasets, and a nursing home action recognition dataset.

Fig. 1

Intersection over union loss surface in F P and F N space. a) Exact surface, b) a piecewise linear approximation with 40 subregions, c) a piecewise linear approximation with 15 subregions.

Fig. 2

Visualization of the average root and part shapes in person category. Each row corresponds to shape models obtained from root and part appearance models of one object pose.

Fig. 3

The process of computing top-down features for the head part. Instead of showing the center of the detected parts we depict the bounding box for visualization purposes in the second stage.

Fig. 4

Intersection over union performance (%) comparison on VOC 2009 and 2010 datasets

Fig. 5

Segmentation for person category. Optimizing adjusted Hamming loss (“Hamming”) against our proposed method. a) input image, b) segmentation considering adjusted Hamming loss (“Hamming”), c) our proposed method employing intersection over union. Intersection over union provides more true positives by possibly creating some false positives. Adjusted Hamming loss decreases false positive by sacrificing some true positives.

Fig. 6

Intersection over union performance (%) comparison on H3D dataset

Fig. 7

Illustration of our model. A Markov random field with unary (red), intra-frame (green) and inter-frame (yellow) connections is used.

Fig. 8

Visualization for some of the learned intra-frame (left) and inter-frame (right) interactions. Vertical labels are the query actions (walk (W), Stand(St), Sit(Si), Bend(B) and Fall(F)). The inter-frame interactions are asymmetric, which is shown as two weights one from query action to the other actions (left half) and from the other actions to the query action (right half).

Fig. 9

Some segmentation results on Pascal VOC 2009 dataset. Each row corresponds to one object category.

Fig. 10

Some segmentation results on H3D dataset.