Timezone: »

Efficient and Consistent Adversarial Bipartite Matching
Rizal Fathony · Sima Behpour · Xinhua Zhang · Brian Ziebart

Wed Jul 11 09:15 AM -- 12:00 PM (PDT) @ Hall B #65

Many important structured prediction problems, including learning to rank items, correspondence-based natural language processing, and multi-object tracking, can be formulated as weighted bipartite matching optimizations. Existing structured prediction approaches have significant drawbacks when applied under the constraints of perfect bipartite matchings. Exponential family probabilistic models, such as the conditional random field (CRF), provide statistical consistency guarantees, but suffer computationally from the need to compute the normalization term of its distribution over matchings, which is a #P-hard matrix permanent computation. In contrast, the structured support vector machine (SSVM) provides computational efficiency, but lacks Fisher consistency, meaning that there are distributions of data for which it cannot learn the optimal matching even under ideal learning conditions (i.e., given the true distribution and selecting from all measurable potential functions). We propose adversarial bipartite matching to avoid both of these limitations. We develop this approach algorithmically, establish its computational efficiency and Fisher consistency properties, and apply it to matching problems that demonstrate its empirical benefits.

Author Information

Rizal Fathony (University of Illinois at Chicago)
Sima Behpour (University of Illinois at Chicago)
Xinhua Zhang (University of Illinois at Chicago)
Brian Ziebart (University of Illinois at Chicago)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors