Choosing how to choose with self-normalising weights

[julian]

This is a development topic.

There have been discussions about having a way of conveniently normalising weights for random choice. Since the first option modifies a common method, it is discussed here.

Here is an updated collection of options.

Normalising them in wchoose is not good, because it will do this normalisation for each new random value, which is a waste of energy (though see 2b below).

Note that I have allowed myself to add/remove as a way to reap the results of the discussion, if you’d like a particular option to appear here, please let me know. I always leave the numbers to keep the reference for the discussion intact.

// 1.
choose(unnormalizedWeights) // uses weights if not nil, then normalises
wchoose(weights) // stays as now, you have to normalise yourself

• pro: no extra method / the common method is extended / simple / other languages do this / low friction from choose
• con: breaks with existing logic / suggests an inefficient method as default / needs explanation

// 1b. 
// both normalise if flag is true, defaults differ
choose(weights, normalize=true) // without weights
wchoose(weights, normalize=false)// normalises if flag is true, off by default (like the TWChoose ugen)

pro: separates concerns / symmetric
con: suggests an inefficient method as default

// 2.
choose // without weights
wchoose(weights) // stays as now, you have to normalise yourself
wchooseN(normalizedWeights) // normalises

pro: separates concerns / logical and idiomatic / most efficient
con: extra method / two modification steps away from choose (front and end, alternative name: wnchoose is better, but less discoverable)

// 2b
choose // without weights
wchoose(normalizedWeights) ) // normalises
wchooseN(weights) you have to normalise yourself

this assumes that normalisation is very efficient and only matters for very large arrays
pro: separates concerns / logical and idiomatic
con: extra method / may make some existing code less efficient or break for ear tuned pieces

// 3. 
choose // without weights
wchoose(weights, normalize=false) // normalises if flag is true, off by default (like the TWChoose ugen)

pro: separates concerns / logical and idiomatic
con: not easy to read in code

[jordan]

Imho…

1 would be fine if you could guarantee it’s a FloatArray.

2 would be more methods and since it’s just a single extra method call, seems unnecessary.

3 and 2 might be considered more from the users perspectiv?. If you’re in an ide and either 3 or 2 popup in suggestions it’s quite obvious what you should do with them… But if the argument for wchoose was named ‘normalisedWeights’ I think you’d get a similar experience, and less noise. You could use the ide/lsp to guide the correct usage, because the problem isn’t that it’s hard to do, it’s just hard to remember to do.

I’m also not a fan of having arguments as options where you only fill the argument you want. I don’t know of any other language that does this and I stumble every time I come across it.

[julian]

@jordan

1 would be fine if you could guarantee it’s a FloatArray.

A normal Array should be also fine, could be e.g. [1, 2, 3]. I think that it is fine to accept anything that responds to normalizeSum with something that responds to windex.

@jordan

2 would be more methods and since it’s just a single extra method call, seems unnecessary.

Over time, I have come to prefer adding new methods instead of more arguments. It is what functional languages do. The main thing is to get the names right – e.g. in this case it could also be wnchoose or whchoosen. Easy to write and clear to understand. version 1 is a little confusing, because you may first wonder why you have a wchoose if you already have weights in choose. Then only through documentation you get the difference. With 3 methods, the logic is relatively clear, and the autocompletion response is also logical (if you know about wchoose already, the new option is almost self-explanatory).

@jordan

I’m also not a fan of having arguments as options where you only fill the argument you want.

It is a very good way to allow incremental specifications (and not unusual, e.g. python and ruby both have default arguments, lisp has optional arguments). But yes - they should not be used to switch between kinds of functionality too much – I think it is nicer and even more concise to just use a different method name then.

In the end, it is about how expressive the code is that is actually written when using it.

[dscheiba]

I think the PR interface could be improved. Currently the PR implements

• If I just want to get a random element, I can use the choose method.
• If I want to use a custom distribution, I can use wchoose, short for weighted(?) choose. If the distribution passed is not a distribution (all elements >=0, sum equal to 1.0), the function will implicitly proceed with non-deterministic behavior.
• If I have an array of values that may not be a probability distribution, but can be transformed into such a distribution, I have to use choose, but now with arguments.

So based on what kind of “distribution” I have, I need to choose between two functions and their arguments properly - seems like something I already have to look up.

Lets take a look at the equivalent Python interface random.choices, which was already mentioned

def random.choices(population, weights=None, *, cum_weights=None, k=1)

You have a unified function where given weights are normalized. Instead of providing different functions with names you need to know, we can use arguments that can be displayed from within the IDE and make you memorize less, which I think is more user friendly, especially for beginners.

So, why not try to be a bit more radical here with the PR?

• make choose accept arguments

  SequencableCollection.choose { |weights: nil, normalize: true|
    if(weights.isNil, { ^this.at(this.size.rand) });
    if(normalizeWeights, { weights = weights.normalizeSum });
    ^this.at(weights.windex);
  }
  

  Normalize is true b/c only in the edge case of large arrays that are already scaled does it make sense to turn off this flag - this is advanced usage for users who know what they are doing in regards of performance.
• deprecate wchoose which will simply forward the call to .choose(weights, normalize: false) - normalize false in order to mimic the old behavior.

IMO this makes the code much more readable and one does not need to know the differences between choose/wchoose/wchooseN

(0..10).choose;

// looks "wrong", but IDE displays normalize: true as default argument
(0..10).choose(weights: (0..10));

// this looks strange in written code - could be a bug?
(0..10).choose(weights: (0..10), normalize: false);

// "advanced" usage - we are sure that the weights are a distribution
(0..10).choose(weights: (0..10)/(0..10).sum, normalize: false);

[julian]

All in all a good suggestion, even if I prefer to have more methods than more arguments. This is a little bit a cultural difference between python and haskell.

@dscheiba

deprecate wchoose which will simply forward the call to .choose(weights, normalize: false) - normalize false in order to mimic the old behavior.

Please let’s not do this, but in any case keep wchoose as it was. As I said in many use cases, it is a waste of energy to add and divide each time you need a random value. Deprecation is just not worth it.

[semiquaver]

Is there a problem with deprecating wchoose if the behavior is still available?

now:
[1, 2, 3].wchoose([2, 2, 6].normalizeSum)
using @dscheiba’s suggestion becomes
[1, 2, 3].choose([2, 2, 6]) //16 character benefit
and
[1, 2, 3].wchoose([0.4, 0.4, 0.6])
becomes
[1, 2, 3].choose([0.4, 0.4, 0.6], false) //5 character cost

I do think it would be nice to have a single method for choosing rather than 2 (as now) or 3!

FWIW the PR author had another solution: choose(weights: nil, normalizedWeights: nil)

[jordan]

My preferred solution would be changing the argument name of the existing methods tonormalisedWeights. It should show up in the ide and be enough of a reminder to call normalise.

@julian

In the end, it is about how expressive the code is that is actually written when using it.

You know what… I have no idea what expressivity is in this context?!

[semiquaver]

quick Q:

prArrayWindex is already summing the weights if I’m reading it right? (I’m not exactly literate in C++ but…)

couldn’t prArrayWindex normalize the weights if their sum != 1 - so no performance hit with normalized weights, in which case we would just have:

choose( weights = nil ) and be done?

[julian]

@jordan

You know what… I have no idea what expressivity is in this context?!

well, I would say it is a matter of

• how well it is readable
• how much you have to change something to become something different
• how interesting it is when you learn it
• how beautiful code looks like

All of these criteria are idiomatic, so we are talking about aesthetics, with some objective and some subjective criteria.

@semiquaver

Is there a problem with deprecating wchoose if the behavior is still available?

deprecating means eventually removing. So yes, it generates a lot of work for many people. It also disintegrates the code base between old and new.

@semiquaver

prArrayWindex is already summing the weights if I’m reading it right? (I’m not exactly literate in C++ but…)

Yes, it is, but if you do normalizeSum first each time, you have to do it twice and divide once, for each random value. That is, you have at best a performance halving.

[semiquaver]

@julian

Yes, it is, but if you do normalizeSum first each time, you have to do it twice and divide once, for each random value. That is, you have at best a performance halving.

yes but if we change prArrayWindex to normalize when the sum !=1 then there is no performance hit when normalized weights are provided!

wchoose([0.5, 0.5]) would still perform as choose([0.5, 0.5]) - only `choose([1, 1]) would introduce the division. (no need to do the sum twice as we already have the value). or have I misunderstood?

[julian]

@semiquaver

yes but if we change prArrayWindex to normalize when the sum !=1 then there is no performance hit when normalized weights are provided!

Yes, right, we can save the division. But how do we find out if the sum ≠ 1 ? We have to add up a second time anyway. Or did you have another idea?

And: is there a threshold? With floating point numbers, it may be a decision to say if 0.9999 is ok.

[semiquaver]

ahh looking further at prArrayWIndex I see that I hadn’t quite understood.

the “sum” is just partial sums as part of the weighted selection algorithm…

so we are doing an average of n/2 additions and comparisons per call. if we sum first - check != 1 we are adding n additions and one comparison so yes this would be a little slower!

to normalize we would multiply the random number before finding the index as that’s faster than division. There might be a faster algorithm out there - build the integral of the weights, scale the rand, then do a binary search perhaps.

[mike]

I’m in favor of #3

@julian

choose // without weights
wchoose(weights, flag) // normalises if flag is true, off by default (like the TWChoose ugen)

Pros

• separates concerns / logical and idiomatic (already mentioned)
• no new method
• the flag is a natural extension to current functionality (bonus in the new SC release!)

con: not easy to read in code

I don’t see this as a con, if flag is instead called normalize. Then it actually just becomes expressive (if you choose to simply tab-complete in the IDE to include the key)

The question is then how to handle the normalize arg.

I’d prefer this to be true—arguably the current behavior “feels broken” (hence the PR). So a default of true says “call normalizeSum for me, I’ll take the performance hit”. For someone concerned with performance, they’ll go out of their way to set false.

But, that’s not backwards compatible, so it “has to be” false (breaking change, anyone?).

This leaves the “broken” behavior by default . But, the flag is there to make the user consider why one might want to normalize, and either use the flag, or supply a pre-normalized distribution.

This sounds more complicated than it is, it’s easily clarified in the docs. (BTW, why isn’t there already an example showing the use of .normalizeSum??)

My runner up choice is #2

wchooseN(normalizedWeights) // normalises

for the pros already mentioned, and it will show up in auto-complete if you know about wchoose, and docs will clarify the differences if it’s not obvious.
Note though the arg would be just weights, (normalizedWeights implies they’re pre-normalized).

Please not #4!

wchoose(weights, normalizedWeights)

[mike]

A couple more thoughts:

I didn’t do a dive into prArrayWIndex, but I’m rooting for @semiquaver to find an efficient solution That would be cool.

And… here’s an unconventional idea: what about a “soft” deprecation? i.e. extend choose as @dscheiba suggested:

SequencableCollection.choose { |weights: nil, normalize: true|

essentially superseding wchoose without deprecating it, and let’s us default to normalize: true without breaking backward compatibility

@semiquaver

Is there a problem with deprecating wchoose if the behavior is still available?

because actually deprecating that method will surely eventually annoy users / break old code.

(Not convinced of this myself, just throwing it out there…)

[Asmatzaile]

Hi! The PR author here.
As @semiquaver indicated here, I actually suggested extending .choose in the issue preceding the PR, inspired by the interface of random.choices in Python. That would make the code more readable; a view that @dscheiba expressed here. It would look something like this:

	choose { arg weights, norm_weights;
  	^case
		{not(norm_weights.isNil)} {this.wchoose(norm_weights)}
		{not(weights.isNil)} {this.wchoose(weights.normalizeSum)}
		{this.at(this.size.rand)}
	}

I also think that a normalize flag with a default of false is not a good idea. Not normalizing is the advanced need of an user seeking better performance; normalizing is the arguably expected behavior of a weighted choosing function, and it is what the Python, Haskell, and Max/MSP bach library implementations do.

[julian]

Hi, thanks for one more suggestion. I’ve integrated it to the list in the beginning of the page.
To me it is not clear that it is the best solution. It combines both advantages and disadvantages of other variants.

In particular, it needs to be explained and documented that it is wrong to write:

[1, 2, 3].choose([10, 2, 1], [0.1, 0.5, 0.4])

It is at least unusual that arguments can’t be combined, and more idiomatic to use separate methods for separate behaviours.

Just so I can understand better: can you explain a bit what is the disadvantage of just simply having a separate method?

[semiquaver]

One of the joys of SC is rapid iteration. I might think “lets choose between two synths”:

[\harp, \dogBark].choose

after listening I think: "I’d like to hear \harp twice as often!. Now I must do three things: change the method name to wchoose (which I have to remember) then add the argument [2, 1] and remember to call normalizeSum (or what I usually write is [2, 1] / 3 – and I am usually annoyed by this moment of friction)

if choose was capable, I’d much rather just insert an argument [2, 1] and be done! - having a flag that defaults to true for normalize would be best and quickest. Later, if I were seeking to improve performance I could always change [2, 1] to [0.66, 0.34] and the flag from true to false.

Reserving wchoose for the case where arguments have been normalized is suboptimal since the name wchoose does not suggest this distinction.

I’d mention that there are very very many methods for Array and I often forget exactly which is which - the IDE can show us the flag and optional method, but it can’t suggest an alternate method which we might not remember. So I favor @dscheiba’s suggestion with @mike’s soft deprecation. This would leave wchoose available but steer users to the new idiom. I agree that the mutually exclusive arguments in @Asmatzaile’s version is unidiomatic.

[mike]

For those curious about the efficiency aspect:

(
var numIter = 50e3.asInteger;
var arrSize = 5e3.asInteger;
var array = arrSize.collect{ rrand(0, 1.0) };
var weights = arrSize.collect({ rrand(0, 1.0) });

"Non-normalized:\n\t".post;
bench {
	numIter.do{
		array.wchoose(weights)
	}
};

"Normalized:\n\t".post;
bench {
	numIter.do{
		array.wchoose(weights.normalizeSum)
	}
}; ""
)

Once you hit an arrSize of ~1000, the hit is more than an order of magnitude, and really climbs for larger sizes. (perhaps a useful benchmark for future docs)

[mike]

I tend to agree with @semiquaver 's framing here! (Pls. share piece with harp + dog on the forum)

[Asmatzaile]

Well put
If the mutually exclusive arguments version is unidiomatic, I am also comfortable with that solution!