Dr. Mark Humphrys

School of Computing. Dublin City University.

Home      Blog      Teaching      Research      Contact

Search:

CA216      CA249      CA318

CA400      CA651      CA668


Boltzmann "soft max" distribution

Let us have n items. The "fitness" score of item i is f(i). Let the probability of picking item i, p(i), be defined as:

Then by varying the parameter T, we can vary the selection from picking a random item (T infinite) to: having higher probabilities for items with higher fitness (T small finite) to: strictly picking the item with the best fitness (T goes to 0).

T is called "temperature" - analogy to cooling. See Simulated Annealing.



Bounds

T exactly = 0 will cause divide by 0 error.
Also, in software:

Have to figure out safe T ranges and f ranges for your software system.


We will be keeping T > 0 and looking at T -> 0
If T > 0, and all f(i) are finite (positive or negative),
then f(i)/T is finite (positive or negative).
all e(f(i)/T) > 0
all probabilities are in range:
0 < p(i) < 1
i.e. This is a probability distribution.

As T -> 0 a probability can -> 0
but as long as T > 0 all probabilities are > 0



Exercise

Prove:

  1. Each p(i) is a number between 0 and 1, no matter what the fitness is (positive or negative). This scheme does not require that fitness has to be positive.

  2. The sum of all the p(i)'s is 1.
    i.e. This is a prob. distribution.

  3. No matter what T is:
    1. If 2 items have same fitness, they have same probability of being picked.

    2. If all fitnesses are the same, we pick random item.
      Q. "Pick random item" means each p(i) = what?

  4. No matter what the fitnesses are:
    1. As T → ∞ we tend to pick random item.
      Q. For any item what is p(i)?

    2. As   T -> 0   we tend to pick only the no.1 best item. That is, its probability is 1, all others probability 0.

      If there are m joint best items, we pick them with probability 1/m, all others with probability 0.




As   T -> 0   (example)

To see what happens as T -> 0 consider 2 items:

i     1    2
f(i)  1    2
If T=1, probabilities are:
e / (e + e2)
and:
e2 / (e + e2)
i.e. 0.27 and 0.73

If T=1/20, probabilities are:
e20 / (e20 + e40)
and:
e40 / (e20 + e40)
i.e. pretty much 0 and 1.




As   T -> 0   (in general)

In general:
Let us have any two items where one has a higher fitness value:

i     1    2
f(i)  c    d
where   d > c  
Let   T = 1/N  
Then:

p(1) = ecN / ( ecN + edN )

= 1 / ( 1 + e(d-c)N )

0
as N → ∞
since   (d-c) > 0

So   p(1) -> 0   as   T -> 0  



Q. Show   p(2) -> 1   as   T -> 0  



Q. Show it for any number of items (not just 2)

Clue: p(1) is even smaller than above p(1), which goes to zero.



Q. Show it for joint winners



Feeds      w2mind.org

On Internet since 1987.