classification
Title: unexpected behaviour of random.choices with zero weights
Type: behavior Stage: resolved
Components: Documentation Versions: Python 3.9
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: rhettinger Nosy List: IRomanowska, mark.dickinson, rhettinger, tim.peters, xtreak
Priority: normal Keywords: patch

Created on 2019-11-21 17:35 by IRomanowska, last changed 2019-11-25 10:40 by IRomanowska. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 17362 merged rhettinger, 2019-11-23 04:06
Messages (12)
msg357185 - (view) Author: Iza Romanowska (IRomanowska) Date: 2019-11-21 17:35
Hi, 
When zero weights are given, the last element of a sequence is always chosen. Example: 

hits= []
for i in range(100):
    hits.append(random.choices(["A","B","C","D"], [0, 0, 0, 0])[0])
print (set(hits))

>> {'D'}

I guess that most users would expect that in case of zero weights it will default into a random.choice behaviour and select one option at random since this is what happens in cases when all weights are equal. Alternatively, it should return an empty array if the assumption was that all choices have a zero probability of being selected. Either way, if it is consistently choosing one option, this may be potentially difficult to spot in situations when a sequence of weights all equal to zero only happen sporadically.
msg357242 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-11-22 04:25
> When zero weights are given, the last element of a sequence 
> is always chosen.

Given non-sensical input, that behavior is as reasonable as any other (fwiw, the same is also observed with all negative weights, even if the negative weights are unequal).

The documentation currently says, "weights are assumed to be non-negative."  Perhaps it should say, "weights are assumed to be non-negative and have at least one positive weight."
msg357243 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-11-22 04:37
Alternatively, we could raise an exception if the weight total isn't positive.  Am not sure that has any real worth, but it could be done with only a small additional cost to the critical path.
msg357257 - (view) Author: Iza Romanowska (IRomanowska) Date: 2019-11-22 09:15
Dear Raymond, 

I understand that passing all zero weights may look nonsensical but random.choices is an implementation of the roulette wheel which is widely used across different scientific disciplines and the situation of passing all zeros is completely plausible. 

In genetics:
A genome may consist of a set of genes none of which increases fitness thus their relative probability of being copied over other genes is all zero. 

In political sciences or cultural evolution:
A voter may hate all parties (ie. their individual preference for any one party is zero). An agent may happen to have no preference for either of the options. 

In engineering: 
All solutions may carry zero increase in performance. 

You are absolutely right that negative weights make no sense (how can you choose option A with a -10% chance. But a 0% chance is entirely possible. 

I consulted with colleagues working in other languages and it looks that the default for roulette wheel with zero weights is choosing at random. 
This should probably be consulted with a mathematician who knows the definition of the algorithm.
msg357259 - (view) Author: Karthikeyan Singaravelan (xtreak) * (Python committer) Date: 2019-11-22 09:28
IIUC, there was a similar discussion on negative weights and all weights being zero to raise ValueError at https://bugs.python.org/issue18844#msg196252
msg357265 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-11-22 10:35
xtreak, the other discussion isn't similar at all.  The OP is proposing that weights all equal to zero be a well-defined way to specify an equiprobable selection.  That is a completely new proposal which is easy to implement, but doesn't make much sense to me.  

The current concept is that the weights express an odds ratio where a zero weight means that an event has no chance of being selected.  This view implies that if all weights are zero, the result is undefined (or an error).

Iza, it seems to me that the provided examples are conflating a zero incremental preference with a zero chance of occurrence.
msg357267 - (view) Author: Iza Romanowska (IRomanowska) Date: 2019-11-22 11:18
Hi, 

Many thanks for engaging with this. 
I agree that we should very clearly separate negative weights from zero weights. A negative number is illegal and that's the end of it. However, a zero weight is not illegal, e.g., [0, 0, 0, 0.1] is a legal sequence to pass as weight. 

Raymond, I agree with you that this is conflating incremental preference with zero chance of occurring. From a standard user perspective, if the [0, 0, 0, 0.1] sequence is passed as weights the first three options have a zero probability of selection thus that interpretation (even if in your opinion erroneous) is very likely to happen for most of the users. 

I think we all agree that an output that always chooses the last element of the sequence is not ok. We differ in opinion as to what should happen instead: raising an error or returning a value at random. My arguments for the latter are: 
 - this seems to be the standard for other programming languages (I've checked for R and NetLogo but this should be confirmed by others);
 - a weight sequence [1, 1, 1, 1] is equivalent to [10, 10, 10, 10] so if we don't want to make [0, 0, 0, 0] 'a special case' it should give the same behaviour (equal probability);
 - when a weight sequence is not provided (i.e., there are no odds given) a random selection is made. One can argue that the odds [,,,,] are similar to [0, 0, 0, 0 ]. Perhaps the zero weights option could be pushed into the if-loop of no weights? 

I see the logic of the second solution, i.e., raising an error. It may make it more difficult to catch the issue for those doing simulations but at least it's not giving a wrong result. 
 
As mentioned this is a key algorithm for many scientific applications with predominantly non-computer science users like myself. So please do take into consideration that it will be often used naively. 

Many thanks.
msg357358 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2019-11-23 02:54
There are a number of "obvious" properties that should obtain, given the intended meaning of weights:

- An input with weight 0 should never be returned.

- The distribution shouldn't be affected by adding a new input with weight 0.

- The distribution shouldn't be affected by removing an input with weight 0.

Especially because of the 3rd, the only sensible thing to do is to treat an input with weights all 0 much like an empty population - although, in context, ValueError would make more immediate sense for "all weights are 0" than the IndexError raised for an empty population.

Anything other than that is "too clever" by half, and I just don't believe would be of real use often enough to be worth violating the "obvious" properties above.
msg357370 - (view) Author: Mark Dickinson (mark.dickinson) * (Python committer) Date: 2019-11-23 09:56
Either raising, or treating a zero-weight-sum as undefined behaviour and documenting that the sum of the weights should be positive sounds fine to me.

-1 on the suggestion to (deliberately, by documented design) choose at random in this case. Mathematically, this situation doesn't make sense: as Tim said, it's analogous to choosing from an empty population.

Ex: you have `nred` red balls and `nblue` blue balls in a bag. If you want to simulate drawing a single ball from the bag, then

   random.choices(["red", "blue"], [nred, nblue])

does the job. But in the case where `nred = nblue = 0`, the bag is empty and it's not possible to draw anything; in that case I'd expect an error. I definitely wouldn't expect to get either a red ball or a blue ball (with equal probability).
msg357372 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-11-23 10:22
New changeset 041d8b48a2e59fa642b2c5124d78086baf74e339 by Raymond Hettinger in branch 'master':
bpo-38881: choices() raises ValueError when all weights are zero (GH-17362)
https://github.com/python/cpython/commit/041d8b48a2e59fa642b2c5124d78086baf74e339
msg357373 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2019-11-23 10:23
Thanks for the suggestions.
msg357436 - (view) Author: Iza Romanowska (IRomanowska) Date: 2019-11-25 10:40
Many thanks for patching it! 
Much appreciated.
History
Date User Action Args
2019-11-25 10:40:56IRomanowskasetmessages: + msg357436
2019-11-23 10:23:11rhettingersetstatus: open -> closed
versions: - Python 3.7, Python 3.8
messages: + msg357373

resolution: fixed
stage: patch review -> resolved
2019-11-23 10:22:23rhettingersetmessages: + msg357372
2019-11-23 09:56:18mark.dickinsonsetmessages: + msg357370
2019-11-23 04:06:54rhettingersetkeywords: + patch
stage: patch review
pull_requests: + pull_request16847
2019-11-23 02:54:54tim.peterssetmessages: + msg357358
2019-11-22 11:18:30IRomanowskasetmessages: + msg357267
2019-11-22 10:35:37rhettingersetmessages: + msg357265
2019-11-22 09:28:37xtreaksetnosy: + xtreak
messages: + msg357259
2019-11-22 09:15:04IRomanowskasetmessages: + msg357257
2019-11-22 07:47:18mark.dickinsonsetnosy: + mark.dickinson
2019-11-22 04:37:23rhettingersetmessages: + msg357243
2019-11-22 04:25:49rhettingersetnosy: + tim.peters
2019-11-22 04:25:29rhettingersetassignee: rhettinger
messages: + msg357242
components: + Documentation, - Library (Lib)
versions: + Python 3.8, Python 3.9
2019-11-21 19:41:12xtreaksetnosy: + rhettinger
2019-11-21 17:35:22IRomanowskacreate