Dr. Mark Humphrys School of Computing. Dublin City University. My big idea: Ancient Brain Search:

# 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 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

```
```
```
```
ancientbrain.com      w2mind.org      humphrysfamilytree.com

On the Internet since 1987.

Wikipedia: Sometimes I link to Wikipedia. I have written something In defence of Wikipedia. It is often a useful starting point but you cannot trust it. Linking to it is like linking to a Google search. A starting point, not a destination. I automatically highlight in red all links to Wikipedia and Google search and other possibly-unreliable user-generated content.