Proof of the Gumbel Max Trick

2019-08-01 | Tech

#Statement

Assume that $𝛼 1, 𝛼 2, \dots, 𝛼 𝑛$ satisify $\sum 𝑘 𝛼 𝑘 = 1$ . Define

$𝑍 = a r g m a x 𝑘 {l o g 𝛼 𝑘 + 𝐺 𝑘}$

where $𝐺 1, \dots, 𝐺 𝑛 i . i . d . \sim 𝐺 𝑢 𝑚 𝑏 𝑒 𝑙 (0, 1)$ , whose PDF and CDF are defined as

$𝑓 (𝑥) = 𝑒 - (𝑥 + 𝑒 - 𝑥) 𝐹 (𝑥) = 𝑒 - 𝑒 - 𝑥$

. Then $ℙ (𝑍 = 𝑘) = 𝛼 𝑘$ .

#Proof

Set $𝑢 𝑘 = l o g 𝛼 𝑘 + 𝐺 𝑘$ . We prove by direct calculations.

$ℙ (𝑍 = 𝑘) = ℙ (𝑢 𝑘 \geq 𝑢 𝑗, \forall 𝑗 \neq 𝑘) = \int \infty - \infty ℙ (𝑢 𝑘 \geq 𝑢 𝑗, \forall 𝑗 \neq 𝑘 | 𝑢 𝑘) ℙ (𝑢 𝑘) 𝑑 𝑢 𝑘 = \int \infty - \infty \prod 𝑗 \neq 𝑘 ℙ (𝑢 𝑘 \geq 𝑢 𝑗 | 𝑢 𝑘) ℙ (𝑢 𝑘) 𝑑 𝑢 𝑘 = \int \infty - \infty \prod 𝑗 \neq 𝑘 𝑒 - 𝑒 - 𝑢 𝑘 + l o g 𝛼 𝑗 𝑒 - (𝑢 𝑘 - l o g 𝛼 𝑘 + 𝑒 - (𝑢 𝑘 - l o g 𝛼 𝑘)) 𝑑 𝑢 𝑘 = \int \infty - \infty 𝑒 - \sum 𝑗 \neq 𝑘 𝛼 𝑗 𝑒 - 𝑢 𝑘 𝛼 𝑘 𝑒 - (𝑢 𝑘 + 𝛼 𝑘 𝑒 - 𝑢 𝑘) 𝑑 𝑢 𝑘 = 𝛼 𝑘 \int \infty - \infty 𝑒 - 𝑢 𝑘 - (𝛼 𝑘 + \sum 𝑗 \neq 𝑘 𝛼 𝑗) 𝑒 - 𝑢 𝑘 𝑑 𝑢 𝑘 = 𝛼 𝑘$ .

#Application

The trick is commonly used in DL to make sampling over a discrete distribution differentiable.

#References

Author: hsfzxjy.
Link: https://i.hsfzxjy.site/proof-of-gumbel-max-trick/.
License: CC BY-NC-ND 4.0.
All rights reserved by the author.
Commercial use of this post in any form is NOT permitted.
Non-commercial use of this post should be attributed with this block of text.

Probability Math