Learning Latent Permutations with Gumbel-Sinkhorn Networks

• 概
• SinkHorn operator

Mean G. E., Belanger D., Linderman C. and Snoek J. Learning latent permutations with gumbel-sinkhorn networks. ICLR, 2018.

概

本文提出了一种自动学习 permutations 的方法.

SinkHorn operator

• SinkHorn operator 的操作流程如下:

  \[S^{0} (X) = \exp(X), \\ S^l(X) = \mathcal{T}_c \bigg(\mathcal{T}_r(S^{l-1}(X)) \bigg), \\ S(X) = \lim_{l \rightarrow \infty} S^l(X). \]

  其中 \(\mathcal{T}_c, \mathcal{T}_r\) 分别表示列和行归一化.

• 给定 \(X\), 一般的 permutation matrix 可以通过如下的方式得到:

  \[M(X) = \text{argmax}_{P \in \mathcal{P}_N} \langle P, X \rangle_F, \]

  需要注意 \(\mathcal{P}_N\) 是 permutaton matrix 的集合 (每行每列有且仅有一个 1).

• 作者证明:

  \[S(X / \tau) = \arg \max_{P \in \mathcal{B}_N} \langle P, X \rangle_F + \tau h(P), \]

  其中 \(h(P) = -\sum_{i,j} P_{i,j} \log (P_{ij})\), \(\mathcal{B}_N\) 表示 doubly-stochastic matrix.

• 所以当 \(\tau\) 足够小的时候, 我们可以用 \(S\) 取逼近 \(M\).

• 用 \(P\) 代替 \(M\) 的一个显然的好处是, 梯度可以传播了, 所以可以训练一个 SinkHorn networks \(P_{\theta}(X)\), 给定 \(X\) 返回一个合适的 permutation matrix 的近似.