Reparameterizing the Birkhoff polytope for variational permutation inference
Many matching, tracking, sorting, and ranking problems require probabilistic reasoning about possible permutations, a set that grows factorially with dimension. Combinatorial optimization algorithms may enable efficient point estimation, but fully Bayesian inference poses a severe challenge in this...
| Main Authors: | , , , , |
|---|---|
| Format: | Conference item |
| Language: | English |
| Published: |
Proceedings of Machine Learning Research
2018
|
| _version_ | 1797082905035407360 |
|---|---|
| author | Linderman, S Mena, G Cooper, H Paninski, L Cunningham, J |
| author_facet | Linderman, S Mena, G Cooper, H Paninski, L Cunningham, J |
| author_sort | Linderman, S |
| collection | OXFORD |
| description | Many matching, tracking, sorting, and ranking problems require probabilistic reasoning about possible permutations, a set that grows factorially with dimension. Combinatorial optimization algorithms may enable efficient point estimation, but fully Bayesian inference poses a severe challenge in this high-dimensional, discrete space. To surmount this challenge, we start by relaxing the discrete set of permutation matrices to its convex hull the Birkhoff polytope, the set of doubly-stochastic matrices. We then introduce two novel transformations: an invertible and differentiable stick-breaking procedure that maps unconstrained space to the Birkhoff polytope, and a map that rounds points toward the vertices of the polytope. Both transformations include a temperature parameter that, in the limit, concentrates the densities on permutation matrices. We exploit these transformations and reparameterization gradients to introduce variational inference over permutation matrices, and we demonstrate its utility in a series of experiments. |
| first_indexed | 2024-03-07T01:34:31Z |
| format | Conference item |
| id | oxford-uuid:94b0d278-f177-456e-aa8b-fdffdf60bb6a |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-03-07T01:34:31Z |
| publishDate | 2018 |
| publisher | Proceedings of Machine Learning Research |
| record_format | dspace |
| spelling | oxford-uuid:94b0d278-f177-456e-aa8b-fdffdf60bb6a2022-03-26T23:41:13ZReparameterizing the Birkhoff polytope for variational permutation inferenceConference itemhttp://purl.org/coar/resource_type/c_5794uuid:94b0d278-f177-456e-aa8b-fdffdf60bb6aEnglishSymplectic ElementsProceedings of Machine Learning Research2018Linderman, SMena, GCooper, HPaninski, LCunningham, JMany matching, tracking, sorting, and ranking problems require probabilistic reasoning about possible permutations, a set that grows factorially with dimension. Combinatorial optimization algorithms may enable efficient point estimation, but fully Bayesian inference poses a severe challenge in this high-dimensional, discrete space. To surmount this challenge, we start by relaxing the discrete set of permutation matrices to its convex hull the Birkhoff polytope, the set of doubly-stochastic matrices. We then introduce two novel transformations: an invertible and differentiable stick-breaking procedure that maps unconstrained space to the Birkhoff polytope, and a map that rounds points toward the vertices of the polytope. Both transformations include a temperature parameter that, in the limit, concentrates the densities on permutation matrices. We exploit these transformations and reparameterization gradients to introduce variational inference over permutation matrices, and we demonstrate its utility in a series of experiments. |
| spellingShingle | Linderman, S Mena, G Cooper, H Paninski, L Cunningham, J Reparameterizing the Birkhoff polytope for variational permutation inference |
| title | Reparameterizing the Birkhoff polytope for variational permutation inference |
| title_full | Reparameterizing the Birkhoff polytope for variational permutation inference |
| title_fullStr | Reparameterizing the Birkhoff polytope for variational permutation inference |
| title_full_unstemmed | Reparameterizing the Birkhoff polytope for variational permutation inference |
| title_short | Reparameterizing the Birkhoff polytope for variational permutation inference |
| title_sort | reparameterizing the birkhoff polytope for variational permutation inference |
| work_keys_str_mv | AT lindermans reparameterizingthebirkhoffpolytopeforvariationalpermutationinference AT menag reparameterizingthebirkhoffpolytopeforvariationalpermutationinference AT cooperh reparameterizingthebirkhoffpolytopeforvariationalpermutationinference AT paninskil reparameterizingthebirkhoffpolytopeforvariationalpermutationinference AT cunninghamj reparameterizingthebirkhoffpolytopeforvariationalpermutationinference |