I’ve been trying to code a program that uses the softmax activation function in the middle.

Right now, I have a list of probabilities like this:


The sum of all the variables in P is always 1.

I wanted a way to pick the index of the list given the probability attached to it.
Or, in other words, a function that returned

0 - 10% of the time
1 - 25% of the time
2 - 60% of the time
3 - 5% of the time

I’ve absolutely no idea where to start on this. Any help would be appreciated. 🙂

You can easily achieve this with numpy. It has a choice function which accepts the parameter of probabilities.

  ['pooh', 'rabbit', 'piglet', 'Christopher'], 
  p=[0.5, 0.1, 0.1, 0.3]

Basically, make a cumulative probability distribution (CDF) array. Basically, the value of the CDF for a given index is equal to the sum of all values in P equal to or less than that index. Then you generate a random number between 0 and 1 and do a binary search (or linear search if you want). Here’s some simple code for it.

from bisect import bisect
from random import random

P = [0.10,0.25,0.60,0.05]

cdf = [P[0]]
for i in xrange(1, len(P)):
    cdf.append(cdf[-1] + P[i])

random_ind = bisect(cdf,random())

of course you can generate a bunch of random indices with something like

rs = [bisect(cdf, random()) for i in xrange(20)]


[2, 2, 3, 2, 2, 1, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2]

(results will, and should vary). Of course, binary search is rather unnecessary for so few of possible indices, but definitely recommended for distributions with more possible indices.

Hmm interesting, how about…

  1. Generate a number between 0 and 1.

  2. Walk the list substracting the probability of each item from your number.

  3. Pick the item that, after substraction, took your number down to 0 or below.

That’s simple, O(n) and should work 🙂

This problem is equivalent to sampling from a categorical distribution. This distribution is commonly conflated with the multinomial distribution which models the result of multiple samples from a categorical distribution.

In numpy, it is easy to sample from the multinomial distribution using numpy.random.multinomial, but a specific categorical version of this does not exist. However, it can be accomplished by sampling from the multinomial distribution with a single trial and then returning the non-zero element in the output.

import numpy as np
pvals = [0.10,0.25,0.60,0.05]
ind = np.where(np.random.multinomial(1,pvals))[0][0]

import random

probs = [0.1, 0.25, 0.6, 0.05]
r = random.random()
index = 0
while(r >= 0 and index < len(probs)):
  r -= probs[index]
  index += 1
print index - 1