Hi Forum!
@jeffc has found a bug in torch.multinomial() – see his thread
Duplicate results due to lack of entropy using multinomial without replacement?
(@ptrblck, if this looks like a bug to you, could you pass it on to the
powers that be? I haven’t filed this as a github issue because I still
haven’t set up a new github account.)
The concept is that you can use multinomial() without replacement
to generate random permutations and that these permutations should
be uniformly generated. (That is, any specific permutation of n
“letters” should be generated with probability 1 / n!.)
In @jeffc’s example. he generates permutations of 26 letters. Were
the permutations generated uniformly, it turns out that you would
have to generate about 10**13 permutations in order to have a 50%
chance of generating a duplicate, but duplicates show up in sets of
only tens of thousands of samples.
(I don’t have any intuition about what kind of flaw in multinomial()'s
distribution would lead to this effect. I also don’t see any coarse flaw
in multinomial()'s distribution, but somehow generating permutations
is picking up on some sort of minor fishiness.)
Here is a script that reproduces the bug @jeffc found. It also uses
randperm() to generate permutations and shows that these are
much more uniform.
import torch
print (torch.__version__)
high_bits_for_seed = 16000000000000000000 # to use "good quality" seed
_ = torch.manual_seed (high_bits_for_seed + 2024)
n = 26 # permutations of 26 "letters"
k = 1000000 # number of permutations to generate
print ('n:', n)
print ('k:', k)
# generate random permutations using multinomial() -- not quite uniform
prob = torch.ones (n)
dups_mult = 0
perm_counts_mult = {}
for _ in range (k):
p = tuple (torch.multinomial (prob, n, replacement=False).tolist())
if p in perm_counts_mult:
dups_mult += 1
perm_counts_mult[p] += 1
else:
perm_counts_mult[p] = 1
print ('duplicate multinomial perms: ', dups_mult)
print ('multiple multinomial perms: ', (torch.tensor (list (perm_counts_mult.values())) > 1).sum().item())
print ('max of perm_counts_mult: ', torch.tensor (list (perm_counts_mult.values())).max().item())
print ('len (perm_counts_mult): ', len (perm_counts_mult))
_ = torch.manual_seed (high_bits_for_seed + 2024) # just to be consistent
# generate random permutations using randperm() -- much more uniform
dups_rand = 0
perm_counts_rand = {}
for _ in range (k):
p = tuple (torch.randperm (n).tolist())
if p in perm_counts_rand:
dups_rand += 1
perm_counts_rand[p] += 1
else:
perm_counts_rand[p] = 1
print ('duplicate randperm perms: ', dups_rand)
print ('multiple randperm perms: ', (torch.tensor (list (perm_counts_rand.values())) > 1).sum().item())
print ('max of perm_counts_rand: ', torch.tensor (list (perm_counts_rand.values())).max().item())
print ('len (perm_counts_rand): ', len (perm_counts_rand))
And here is its output:
2.4.0
n: 26
k: 1000000
duplicate multinomial perms: 207
multiple multinomial perms: 207
max of perm_counts_mult: 2
len (perm_counts_mult): 999793
duplicate randperm perms: 0
multiple randperm perms: 0
max of perm_counts_rand: 1
len (perm_counts_rand): 1000000
I don’t really think that it’s the cause, but this multinomial() github issue
might be related. Note, passing the input probabilities as float64
(which would presumably cause multinomial() to process its
probability “buckets” in double precision) does not seem to help the
situation.
Best.
K. Frank