Tensorflow's .shuffle(BUFFER_SIZE)

Question

I came across the following function in Tensorflow's tutorial on Machine Translation:

BUFFER_SIZE = 32000
BATCH_SIZE = 64
data_size = 30000
train_dataset = train_dataset.shuffle(BUFFER_SIZE).batch(BATCH_SIZE, drop_remainder=True)

I went through several blogs to understand .shuffle(BUFFER_SIZE), but what puzzles me is the fact that a BUFFER_SIZE > DATA_SIZE results in a perfectly uniform shuffling. Neither do I understand what they mean by 'uniform shuffling', nor do I understand how a BUFFER_SIZE> DATA_SIZE is even possible.

From what I understand, tensorflow keeps a BUFFER_SIZE of elements, selects a random element and adds the next input element into the buffer. This makes sense if the BUFFER_SIZE is <= DATA_SIZE. But, what happens to the buffer in case we have more number of elements than the size of the dataset? Do we not have some NULL elements? How does it result in uniform shuffling?

Could anyone please explain to me with an example of how BUFFER_SIZE > DATA_SIZE results in a uniform shuffling? And, what exactly do we mean by uniform shuffling?

Answer 1

Shuffling begins by making a buffer of size BUFFER_SIZE (which starts empty but has enough room to store that many elements). The buffer is then filled until it has no more capacity with elements from the dataset, then an element is chosen uniformly at random. This means that each example in the buffer is equally likely to be chosen, with probability 1/BUFFER_SIZE. Then, a new example is loaded to fill the slot in the buffer that was emptied. This continues until there is nothing left to load.

A uniform shuffle would be what you would think of as truly random: any sequence of examples is equally likely. If the buffer is smaller than the size of the dataset, this is not possible. Here is an example of why: imagine I have ten examples, labelled 1 to 10, and a buffer of size 2. First I load examples 1 and 2 into the buffer, then I have no more space so I must randomly select something from the buffer. Therefore, my random shuffle always begins with example 1 or 2: not uniformly random!

If you have a buffer as big as the dataset, you can obtain a uniform shuffle (think the same process through as above). For a buffer larger than the dataset, as you observe there will be spare capacity in the buffer, but you will still obtain a uniform shuffle.