Efficient and Consistent Adversarial Bipartite Matching

Rizal Fathony, Sima Behpour, Xinhua Zhang, Brian Ziebart
Proceedings of the 35th International Conference on Machine Learning, PMLR 80:1457-1466, 2018.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v80-fathony18a, title = {Efficient and Consistent Adversarial Bipartite Matching}, author = {Fathony, Rizal and Behpour, Sima and Zhang, Xinhua and Ziebart, Brian}, booktitle = {Proceedings of the 35th International Conference on Machine Learning}, pages = {1457--1466}, year = {2018}, editor = {Dy, Jennifer and Krause, Andreas}, volume = {80}, series = {Proceedings of Machine Learning Research}, month = {10--15 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v80/fathony18a/fathony18a.pdf}, url = {https://proceedings.mlr.press/v80/fathony18a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Efficient and Consistent Adversarial Bipartite Matching %A Rizal Fathony %A Sima Behpour %A Xinhua Zhang %A Brian Ziebart %B Proceedings of the 35th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2018 %E Jennifer Dy %E Andreas Krause %F pmlr-v80-fathony18a %I PMLR %P 1457--1466 %U https://proceedings.mlr.press/v80/fathony18a.html %V 80 %X 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.
APA
Fathony, R., Behpour, S., Zhang, X. & Ziebart, B.. (2018). Efficient and Consistent Adversarial Bipartite Matching. Proceedings of the 35th International Conference on Machine Learning, in Proceedings of Machine Learning Research 80:1457-1466 Available from https://proceedings.mlr.press/v80/fathony18a.html.

Related Material