Implement weighted sampling API #518

sicking · 2018-06-20T09:16:51Z

Having experimented with various ways of doing weighted sampling, I think this API is the best I've thought of so far.

This PR adds the following APIs:

IntoIteratorRandom::choose_index_weighted. This is the most low-level way of going a single sampling. It consumes an iterable of weights and returns an index. This index can then be used to index into a slice, another iterator, etc. This is to weighted sampling what gen_range is to uniform sampling.
IntoIteratorRandom::into_weighted_index_distribution. If you're sampling multiple times using the same set of weights, it is more optimal to build up an array of cumulative weights and then do a binary search to find the index corresponding to the randomly generated value. So this is the most low-level API for repeated sampling. This is to weighted sampling what Uniform::new is to uniform sampling.
SliceRandom::choose_weighted. This is a convenience function on top of IntoIteratorRandom::choose_index_weighted which allows using a slice and a mapping function to get a weighted sample from the slice. This function is to weighted sampling what SliceRandom::choose is to uniform sampling.
SliceRandom::choose_weighted_mut. Same as SliceRandom::choose_weighted, but returns a mutable reference. This function is to weighted sampling what SliceRandom::choose_mut is to uniform sampling.

There's still lots of other ways we could approach this. But this set of functions felt pretty good.

The last two felt like very nice pleasant to use APIs which should cover most common use cases. Especially on modern versions of rustc where closures automatically implement Clone when they can. And they nicely match with SliceRandom::choose and SliceRandom::choose_mut.

The first two functions seem like pretty good low-level APIs for doing anything that choose_weighted and choose_weighted_mut. However I'm less sure that these functions live where they should and have the correct names. In particular, maybe IntoIteratorRandom::into_weighted_index_distribution should be a separate struct with a constructor which takes an iterator, more similar to Uniform::new.

And for IntoIteratorRandom::choose_index_weighted, SliceRandom::choose_weighted and SliceRandom::choose_weighted_mut there's the questions of if they should live on SliceRandom or IntoIteratorRandom.

The advantage of things living on IntoIteratorRandom is that they appear on both slices and on iterators, which is a good thing. The downside is that it means that my_vec.choose_index_weighted(...) will actually silently clone the Vec and its contents, which is unlikely expected. However it will also consume the Vec, which will likely lead to compilation errors, allowing the developer to catch this. The fix is to write (&my_vec).choose_index_weighted(...) which will not clone the Vec or its contents, and will not consume the Vec. This problem is unique to Vec objects and do not happen when calling on a slice or an array.

dhardy

I'm less convinced about adding the IntoIteratorRandom trait because (1) the only advantage over IteratorRandom is implicit conversions (e.g. direct usage on a Vec) which aren't always a good idea (as you note) and (2) it's an extra trait. Also (3) this would let us add SliceRandom methods by the same name later without name conflicts.

dhardy · 2018-06-20T09:52:14Z

src/seq.rs

+    /// use rand::prelude::*;
+    ///
+    /// let choices = [('a', 2), ('b', 1), ('c', 1)];
+    /// // In rustc version XXX and newer, you can use a closure instead


Any idea what XXX is? 1.26 is the only version since 1.22 mentioning closures in the release announcement, and doesn't mention cloning. We don't support older than 1.22 anyway.

dhardy · 2018-06-20T10:09:20Z

src/seq.rs

@@ -91,6 +94,52 @@ pub trait SliceRandom {
    fn choose_multiple<R>(&self, rng: &mut R, amount: usize) -> SliceChooseIter<Self, Self::Item>
        where R: Rng + ?Sized;

+    /// Similar to [`choose`], but each item in the slice don't have the same
+    /// likelyhood of getting returned. The likelyhood of a given item getting
+    /// returned is proportional to the value returned by the mapping function


I think it's spelled likelihood. Also, "don't have" is bad grammar and the sentence is indirectly describing the purpose. Try:

A variant of choose where the likelihood of each outcome may be specified. The specified function func maps items x to a relative likelihood func(x). The probability of each item being selected is therefore func(x) / S, where S is the sum of all func(x).

Perhaps also rename func → weight or w or f?

dhardy · 2018-06-20T10:11:38Z

src/seq.rs

+/// Extension trait on IntoIterator, providing random sampling methods.
+pub trait IntoIteratorRandom: IntoIterator + Sized {
+
+    /// Return a the index of a random element from this iterator where the


dhardy · 2018-06-20T10:18:34Z

src/seq.rs

+              Self::Item: SampleBorrow<X> {
+        let mut iter = self.into_iter();
+        let mut total_weight: X = iter.next()
+                                      .expect("Can't create Distribution for empty set of weights")


I don't think we should panic in this case. Maybe return some type of error instead.

vks · 2018-06-20T10:58:04Z

However I'm less sure that these functions live where they should and have the correct names. In particular, maybe IntoIteratorRandom::into_weighted_index_distribution should be a separate struct with a constructor which takes an iterator, more similar to Uniform::new.

I feel like this should be a distributions::Discrete struct, because it is more general: What you implemented can not just be used to generate indices into containers, it can be used to sample from arbitrary discrete distributions. I'm not convinced we need something like gen_range for case, and Discrete::new is a lot cleaner and more consistent with the other distributions than IntoIteratorRandom::into_weighted_index_distribution.

dhardy · 2018-06-20T11:03:23Z

Why not put the weight function func into choose_index_weighted and instead call it just choose_weighted? That way it could do the same thing if called like weights.zip(0..N).choose_weighted(rng, |(w, i)| w).1 but also be more flexible. Of course it's worth testing whether the extra flexibility would impair the performance. The motivation is that it would make the existing choose_weighted redundant (more accurately: the slice version would be redundant and the iterator equivalent would not need a third iteration over the input). The _mut variant could be dropped: it's likely less useful and can be constructed as above anyway.

One thing on my mind here is avoiding adding too much code/API for relatively obscure functionality. We may be able to reduce the API to just IteratorRandom::choose_weighted and IteratorRandom::weighted_distribution (or Weighted::from_iter).

Can you add some benchmarks?

sicking · 2018-06-27T08:09:55Z

I pushed an updated API. It contains

WeightedIndex::new creates a new Distribution which generates weighted indexes.
SliceRandom::choose_weighted, wraps WeightedIndex::new using a passed in mapping function to do a weighted selection from the slice.
SliceRandom::choose_weighted_mut, same but returns a mutable reference.

In this version SliceRandom::choose_weighted/SliceRandom::choose_weighted_mut is slightly slower than in the initial version. However I think that's ok since for performance critical scenarios you likely want to create a WeightedIndex and sample from that multiple times.

SliceRandom::choose_weighted/SliceRandom::choose_weighted_mut now also require #[cfg(feature = "alloc")] since WeightedIndex::new does, but I think that's ok too.

I don't think we can make this a lot smaller. The bulk of the code is in WeightedIndex::new, which I think is the minimal API for weighted sampling. The two new functions on SliceRandom could technically be dropped, but they feel very nice to use, and require very little code.

sicking · 2018-06-27T08:30:25Z

Oh, but on the flip side, SliceRandom::choose_weighted/SliceRandom::choose_weighted_mut now work with closures in all versions of rustc since the function no longer needs to be clonable. (Clonable closures were added in 1.26 FWIW. It's only mentioned in the detailed release notes).

dhardy

Some typos I noticed.

I'm still not sure about the approach though.

dhardy · 2018-06-27T09:36:39Z

src/distributions/weighted.rs

@@ -0,0 +1,182 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT


dhardy · 2018-06-27T09:37:22Z

src/distributions/weighted.rs

+// Note that this whole module is only imported if feature="alloc" is enabled.
+#[cfg(not(feature="std"))] use alloc::Vec;
+
+/// A distribution using weighted sampling to pick an discretely selected item.


a discretely

dhardy · 2018-06-27T09:38:19Z

src/distributions/weighted.rs

+/// of a random element from the iterator used when the `WeightedIndex` was
+/// created. The chance of a given element being picked is proportional to the
+/// value of the element. The weights can use any type `X` for which an
+/// implementaiton of [`Uniform<X>`] exists.


implementation

dhardy · 2018-06-27T09:38:54Z

src/distributions/weighted.rs

+
+/// A distribution using weighted sampling to pick an discretely selected item.
+///
+/// When a `WeightedIndex` is sampled from, it returns the index


Sampling a WeightedIndex distribution returns ...

dhardy · 2018-06-27T09:40:44Z

src/distributions/weighted.rs

+impl<X: SampleUniform + PartialOrd> WeightedIndex<X> {
+    /// Creates a new a `WeightedIndex` [`Distribution`] using the values
+    /// in `weights`. The weights can use any type `X` for which an
+    /// implementaiton of [`Uniform<X>`] exists.


sicking · 2018-06-27T18:37:41Z

I pushed those comment fixes as well as a couple of more tests.

One thing that I wasn't sure which way to go on is what to do with negative weights. Definitely feels like if that happens that it's a pretty severe bug in the calling code, so panicking seems warranted. But also seems somewhat strange to have some errors return a Result::Err, and others panic.

TheIronBorn · 2018-06-27T18:57:47Z

I'm curious: why are we re-implementing binary search?

sicking · 2018-06-27T19:51:35Z

I'm curious: why are we re-implementing binary search?

Good point! Using binary_search_by now.

TheIronBorn · 2018-06-27T19:57:02Z

src/distributions/weighted.rs

+        let chosen_weight = self.weight_distribution.sample(rng);
+        // Find the first item which has a weight *higher* than the chosen weight.
+        self.cumulative_weights.binary_search_by(
+            |w| if *w <= chosen_weight { Ordering::Less } else { Ordering::Greater }).unwrap_err()


~~Doesn't this panic if Ok? Will that just not happen?~~ (Won't happen)

sicking · 2018-06-27T20:10:31Z

Since the closure never returns Ordering::Equal, binary_search_by will never return Ok.

In general binary_search_* is a little wonky in that it tries to both support searching ranges (which is what we're doing here), and searching for items (i.e. an item with a particular value). It works for both but is better at the latter IMO.

dhardy

A couple of little things (sorry I didn't catch this before)!

I also opened #535 but that can be a separate PR.

dhardy · 2018-06-29T08:53:12Z

src/distributions/mod.rs

@@ -192,6 +197,8 @@ use Rng;
 #[doc(inline)] pub use self::dirichlet::Dirichlet;

 pub mod uniform;
+#[cfg(feature="alloc")]
+#[doc(hidden)] pub mod weighted;


We have no reason to make this module public so better make it private I think. The doc(hidden) stuff is supposedly there for backwards compatibility, though probably it's been used erroneously in a couple of cases.

dhardy · 2018-06-29T08:56:25Z

src/distributions/weighted.rs

+    ///
+    /// # Panics
+    ///
+    /// If a value in the iterator is `< 0`.


I don't think it makes sense to panic on some errors while handling others via Result.

dhardy · 2018-06-29T08:56:44Z

src/distributions/weighted.rs

+
+        let zero = <X as Default>::default();
+        let weights = iter.map(|w| {
+            assert!(*w.borrow() >= zero, "Negative weight in WeightedIndex::new");


i.e. this can just return an error

…::choose_weighted_mut

sicking · 2018-06-30T08:09:37Z

Pushed an updated PR that fixes those comments. I'll do a separate PR to address #535.

mrLSD · 2018-08-28T08:00:27Z

It will possible use that as:
https://docs.scipy.org/doc/numpy/reference/generated/numpy.random.choice.html

most important things is size, and replace options.

It most useful in practical life.

P.S. AFAIK numpy.random.choice used CDF algorithm.

dhardy · 2018-08-28T08:59:00Z

@mrLSD we have very different requirements from Python/numpy, so I don't think there is much to take from their approach. Besides which this has already been merged.

This samples with replacement, with given weights. We also have code for sampling without replacement, but without user-defined weights: see choose_multiple in the SliceRandom doc. We do not have code for sampling without replacement using custom weights, though I'm not sure this is widely used?

I don't know why you would want to a size parameter here; wrapper functions can be used to fill an array/matrix/etc. with values. If you really want a function to return a variadic multi-dimensional array, that doesn't belong in the Rand lib; you probably want to use ndarray.

mrLSD · 2018-08-29T09:38:43Z

It's very different functions choose_multiple and choose_weighted.

About size. Very simple example: I have 1kk users with their weights. And I should select only 100 unique users.

Do you really think that it's rare case?

dhardy · 2018-08-29T13:56:07Z

Fair point. Sounds like you have a simple feature request then, rather than wanting a different API or multi-dimensional matrices? Numpy embeds many things in one place, not always for the better.

I opened #596 (which you could have done to start with). I have no plans to work on this now, but at least now there is a visible ticket open.

mrLSD · 2018-08-29T22:15:17Z

@dhardy Thanks!

dhardy reviewed Jun 20, 2018

View reviewed changes

sicking force-pushed the weighted branch from 284e9e4 to fb8c3be Compare June 27, 2018 07:57

sicking force-pushed the weighted branch from fb8c3be to b1169d4 Compare June 27, 2018 08:18

dhardy added the D-review Do: needs review label Jun 27, 2018

sicking force-pushed the weighted branch 6 times, most recently from 261d7b0 to 8538619 Compare June 27, 2018 09:32

dhardy reviewed Jun 27, 2018

View reviewed changes

dhardy mentioned this pull request Jun 27, 2018

Weighted choice algorithms #532

Closed

dhardy removed the D-review Do: needs review label Jun 27, 2018

sicking force-pushed the weighted branch from 8538619 to c988835 Compare June 27, 2018 17:19

sicking force-pushed the weighted branch from c988835 to 8c416f9 Compare June 27, 2018 18:41

sicking force-pushed the weighted branch from 8c416f9 to 38ddf6c Compare June 27, 2018 19:49

TheIronBorn reviewed Jun 27, 2018

View reviewed changes

dhardy mentioned this pull request Jun 29, 2018

ErrorKind::Input #535

Closed

dhardy reviewed Jun 29, 2018

View reviewed changes

Implement WeightedIndex, SliceRandom::choose_weighted and SliceRandom…

bbb037a

…::choose_weighted_mut

sicking force-pushed the weighted branch from 38ddf6c to bbb037a Compare June 29, 2018 20:46

dhardy merged commit 0faff20 into rust-random:master Jul 1, 2018

sicking deleted the weighted branch July 12, 2018 13:03

dhardy mentioned this pull request Jul 13, 2018

Tracker: 0.6 release #520

Closed

28 tasks

This was referenced Jul 22, 2018

WeightedChoice is hard to use with borrow checker #142

Closed

Consider adding an owned version of WeightedChoice #90

Closed

dhardy added this to the 0.6 release milestone Aug 23, 2018

dhardy mentioned this pull request Aug 29, 2018

Implement weighted sampling without replacement #596

Closed

ToferC mentioned this pull request Dec 25, 2019

WeightedChoice depreciated - Uses old rand::distributions module tomassedovic/tcod-rs#305

Closed

sync-by-unito bot mentioned this pull request Dec 15, 2020

Bump rand_core from 0.5.1 to 0.6.0 AleoHQ/leo#503

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implement weighted sampling API #518

Implement weighted sampling API #518

sicking commented Jun 20, 2018

dhardy left a comment

dhardy Jun 20, 2018

dhardy Jun 20, 2018

dhardy Jun 20, 2018

dhardy Jun 20, 2018

vks commented Jun 20, 2018

dhardy commented Jun 20, 2018

sicking commented Jun 27, 2018

sicking commented Jun 27, 2018

dhardy left a comment

dhardy Jun 27, 2018

dhardy Jun 27, 2018

dhardy Jun 27, 2018

dhardy Jun 27, 2018

dhardy Jun 27, 2018

sicking commented Jun 27, 2018

TheIronBorn commented Jun 27, 2018

sicking commented Jun 27, 2018

TheIronBorn Jun 27, 2018 •

edited

sicking commented Jun 27, 2018

dhardy left a comment

dhardy Jun 29, 2018

dhardy Jun 29, 2018

dhardy Jun 29, 2018

sicking commented Jun 30, 2018

mrLSD commented Aug 28, 2018

dhardy commented Aug 28, 2018

mrLSD commented Aug 29, 2018

dhardy commented Aug 29, 2018 •

edited

mrLSD commented Aug 29, 2018

		@@ -0,0 +1,182 @@
		// Copyright 2017 The Rust Project Developers. See the COPYRIGHT

Implement weighted sampling API #518

Implement weighted sampling API #518

Conversation

sicking commented Jun 20, 2018

dhardy left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

vks commented Jun 20, 2018

dhardy commented Jun 20, 2018

sicking commented Jun 27, 2018

sicking commented Jun 27, 2018

dhardy left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

sicking commented Jun 27, 2018

TheIronBorn commented Jun 27, 2018

sicking commented Jun 27, 2018

TheIronBorn Jun 27, 2018 • edited

Choose a reason for hiding this comment

sicking commented Jun 27, 2018

dhardy left a comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

sicking commented Jun 30, 2018

mrLSD commented Aug 28, 2018

dhardy commented Aug 28, 2018

mrLSD commented Aug 29, 2018

dhardy commented Aug 29, 2018 • edited

mrLSD commented Aug 29, 2018

TheIronBorn Jun 27, 2018 •

edited

dhardy commented Aug 29, 2018 •

edited