7 replies to this topic

[sooner123]

If I have a bunch of non-negative integers, and I want to select one to display with probability in inverse proportion to its value, what is the logical way to do this that doesn't run into a division-by-zero problem?

Example:
var1 = 3
var2 = 6
var3 = 1
var4 = 4

var1 would have a 1/3 in (1/3 + 1/6 + 1 + 1/4) chance of being displayed
var2 would have a 1/6 in (1/3 + 1/6 + 1 + 1/4) chance of being displayed
var3 would have a 1 in (1/3 + 1/6 + 1 + 1/4) chance of being displayed
var4 would have a 1/4 in (1/3 + 1/6 + 1 + 1/4) chance of being displayed

This seems logical and not arbitrary, but runs into an issue when a variable is zero:

var5 = 0
would then have a 1/0 in (1/3 + 1/6 + 1 + 1/4 + 1/0) chance of being displayed

So what's the best way to pick something with inverse probability to its value and deal with the case of zero (without arbitrarily treating 0 as .1 or something like that)

My first guess is to just isolate all values that are 0 then pick one of them with even probability. (essentially all the variables with value 0 have infinite probability as a group)

[clb]

You say you don't want to arbitrarily treat 0, but that means you have to give some definition to the case of 0. What does it mean to you? What does zero mean compared to one? What should be picked in the case "var1 = 1, var2 = 0", and with which probability?

- You could add 1 to all numbers before computing the inverse probability, so zero won't occur. That skews all the results though.
- You could treat zeroes as ones.
- You could treat zeroes equal to the smallest non-zero number.
- You could treat zeroes as impossible events, i.e. zero = "1/inf" = zero probability.

All of these choices are quite arbitrary. To arrive to a satisfyin solution, you have to think in your problem domain what it means for an input to be zero.

[sooner123]

Sorry I thought I was clearer. I'm basically asking what I should consider 0 as. (what you suggested I ask myself is what I am asking in the first place)

Is there something I could choose that isn't arbitrary.. or what is the common choice? Is there even a common choice?

I guess some context would help.

I'm writing an app that produces flashcards that the user responds to. If they are correct, it increases that value. The goal is to display the flashcards in inverse proportion to the number of correct responses. So you're constantly drilled on things you have reviewed the least times.

[clb]

If I understand correctly, in that flashcard context, a value 0 means "the player has not answered this card correctly even once, or, the player has not seen this card even once." I would give them a value of one, i.e. the first option in my original list of choices.

Perhaps those two cases might be even further differentiated - a card that the user hasn't seen even once should appear with a higher probability than a card the user has seen, but hasn't answered correctly even once?

[Álvaro]

If I were to follow this type of inverse-proportionality rule, I would also give questions a value of 1 initially.

Another interesting option is to consider that your objective is to extract as many incorrect answers from the user as possible, because those are the situations where your user will learn the most. If the probability of the user failing a question were constant over time, your problem would then be like a multi-armed bandit. Even though your user is [hopefully] learning something, so the probabilities of failing would naturally go down, I believe that using one of the algorithms from multi-armed bandit theory would work well.

Anyway, maybe it's just a crazy idea, but I thought I would share it.

[sooner123]

re: clb

I agree, between two equally numCorrectAnswers options, the unseen one should be higher priority. Looks like I'll have to go more in depth with this. I oversimplified the problem.

re: alvaro

Thanks as always. I love that idea. And thanks for the link. An interesting read.

[MrRowl]

Probably you also want to bias your choice towards cards that haven't been seen recently, in which case you could store the time (or number of tests) since each card was shown, and add on Constant/TimeSinceLastShown(card) to each value. Initialise all the TimeSinceLastSeen values to a value you think is reasonable (i.e. that differentiates between short and longer-term memory), and also use that to help you choose an appropriate Constant. Since TimeSinceLastSeen is always greater or equal to 1, this will also solve your original problem, and result in preferring unseen cards in a general way.

Yes, there are constant numbers here - but they have meaningful values, so aren't completely arbitrary.

[Lauris Kaplinski]

Probably you also want to bias your choice towards cards that haven't been seen recently, in which case you could store the time (or number of tests) since each card was shown, and add on Constant/TimeSinceLastShown(card) to each value. Initialise all the TimeSinceLastSeen values to a value you think is reasonable (i.e. that differentiates between short and longer-term memory), and also use that to help you choose an appropriate Constant. Since TimeSinceLastSeen is always greater or equal to 1, this will also solve your original problem, and result in preferring unseen cards in a general way.

I once did flashcard program and we used the following algorithm:

• Each card in deck has weight in range 1...256
• The probability of given card drawn is proportional to its weight
• Initially the weight of all cards was set to 256
• If player answered correctly weight was divided by 2 (if < 1, then set to 1)
• If player answered wrongly weight was multiplied by 16 (if > 256 then set to 256)
• If the weight of all cards reached 1, the program called it a day
• The next day (the next time program was started) the weights of all cards were multiplied by 2

It worked very well with a deck of about 50 cards.
The important point is, that even single incorrect answer raises weight a lot. You cannot "complete" deck, unless your last 4 answers have been correct for each card.
The "completion" criterion was implemented because in that case player is successfully memorized cards in short-term memory and it is pointless to look at them more the same day.