Learning Latent Permutations with Gumbel-Sinkhorn Networks
Permutations and matchings are core building blocks in a variety of latent variable models, as they allow us to align, canonicalize, and sort data. Learning in such models is difficult, however, because exact marginalization over these combinatorial objects is intractable. In response, this paper introduces a collection of new methods for end-to-end learning in such models that approximate discrete maximum-weight matching using the continuous Sinkhorn operator. Sinkhorn iteration is attractive because it functions as a simple, easy-to-implement analog of the softmax operator. With this, we can define the Gumbel-Sinkhorn method, an extension of the Gumbel-Softmax method (Jang et al. 2016, Maddison2016 et al. 2016) to distributions over latent matchings. We demonstrate the effectiveness of our method by outperforming competitive baselines on a range of qualitatively different tasks: sorting numbers, solving jigsaw puzzles, and identifying neural signals in worms.
 The idea on which the paper is based - that the limit of the entropic regularisation over Birkhoff polytope is on the vertices = permutation matrices -, and the link with optimal transport, is very interesting. The core of the paper, Section 3, is interesting and represents a valuable contribution. I am wondering whether the paper*s approach and its Theorem 1 can be extended to other regularised versions of the optimal transport cost, such as this family (Tsallis) that generalises the entropic one: https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14584/14420 Also, it would be good to keep in mind the actual proportion of errors that would make a random choice of a permutation matrix for your Jigsaws. When you look at your numbers, the expected proportion of parts wrong for a random assignment could be competitive with your results on the smallest puzzles (typically, 2x2). Perhaps you can put the *difference* between your result and the expected result of a random permutation; this will give a better understanding of what you gain from the non-informative baseline. (also, it would be good to define "Prop. wrong" and "Prop. any wrong". I think I got it but it is better to be written down) There should also be better metrics for bigger jigsaws -- for example, I would accept bigger errors if pieces that are close in the solution tend also to be put close in the err*ed solution. Typos: * Rewrite definition 2 in appendix. Some notations do not really make sense.
You are a member of the scientific community tasked with peer review. Review the following paper title and abstract.
### Title + Abstract
Learning Latent Permutations with Gumbel-Sinkhorn Networks
Permutations and matchings are core building blocks in a variety of latent variable models, as they allow us to align, canonicalize, and sort data. Learning in such models is difficult, however, because exact marginalization over these combinatorial objects is intractable. In response, this paper introduces a collection of new methods for end-to-end learning in such models that approximate discrete maximum-weight matching using the continuous Sinkhorn operator. Sinkhorn iteration is attractive because it functions as a simple, easy-to-implement analog of the softmax operator. With this, we can define the Gumbel-Sinkhorn method, an extension of the Gumbel-Softmax method (Jang et al. 2016, Maddison2016 et al. 2016) to distributions over latent matchings. We demonstrate the effectiveness of our method by outperforming competitive baselines on a range of qualitatively different tasks: sorting numbers, solving jigsaw puzzles, and identifying neural signals in worms.
user
<think>Okay, to do a decent peer review, I should start with summarizing what the work is about. This includes novelty, contributions, clarity, and impact. I might include suggestions to issues that I find critical to the usefulness of the work. Starting with novelty, there are different types of novelty. The first aspect of novelty is scope and scale. Is the work covering a broader perspective than previous works? The second aspect is methodology. Is the proposed methodology novel compared to previous methods? Do they provide any significant advantage over previous methodologies? The third aspect is results. Are the results different compared previous work? Does this lead to any novel theories or an extension of current theories? Next is clarity, I will be reading the work in depth and analyze if any sentences can be potentially ambiguous or misleading. If any sentences are ambiguous, I will state them and give a suggestion on how to rephrase such sentence or how to make more clear to the audience. Lastly, impact is important. I will attempt to predict how such work will impact the scientific community. This might include the applications of such work and how the work might transform the way we study a certain topic. Finally, I will might only mention issues that are critical. This is to keep the review as concise and helpful as possible.</think>



 The idea on which the paper is based - that the limit of the entropic regularisation over Birkhoff polytope is on the vertices = permutation matrices -, and the link with optimal transport, is very interesting. The core of the paper, Section 3, is interesting and represents a valuable contribution. I am wondering whether the paper*s approach and its Theorem 1 can be extended to other regularised versions of the optimal transport cost, such as this family (Tsallis) that generalises the entropic one: https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14584/14420 Also, it would be good to keep in mind the actual proportion of errors that would make a random choice of a permutation matrix for your Jigsaws. When you look at your numbers, the expected proportion of parts wrong for a random assignment could be competitive with your results on the smallest puzzles (typically, 2x2). Perhaps you can put the *difference* between your result and the expected result of a random permutation; this will give a better understanding of what you gain from the non-informative baseline. (also, it would be good to define "Prop. wrong" and "Prop. any wrong". I think I got it but it is better to be written down) There should also be better metrics for bigger jigsaws -- for example, I would accept bigger errors if pieces that are close in the solution tend also to be put close in the err*ed solution. Typos: * Rewrite definition 2 in appendix. Some notations do not really make sense.
assistant
 The idea on which the paper is based - that the limit of the entropic regularisation over Birkhoff polytope is on the vertices = permutation matrices -, and the link with optimal transport, is very interesting. The core of the paper, Section 3, is interesting and represents a valuable contribution. I am wondering whether the paper*s approach and its Theorem 1 can be extended to other regularised versions of the optimal transport cost, such as this family (Tsallis) that generalises the entropic one: https://aaai.org/ocs/index.php/AAAI/AAAI17/paper/view/14584/14420 Also, it would be good to keep in mind the actual proportion of errors that would make a random choice of a permutation matrix for your Jigsaws. When you look at your numbers, the expected proportion of parts wrong for a random assignment could be competitive with your results on the smallest puzzles (typically, 2x2). Perhaps you can put the *difference* between your result and the expected result of a random permutation; this will give a better understanding of what you gain from the non-informative baseline. (also, it would be good to define "Prop. wrong" and "Prop. any wrong". I think I got it but it is better to be written down) There should also be better metrics for bigger jigsaws -- for example, I would accept bigger errors if pieces that are close in the solution tend also to be put close in the err*ed solution. Typos: * Rewrite definition 2 in appendix. Some notations do not really make sense.