detan.detan – deterministic annealing library

class detan.detan.AssignmentAnnealing(function, initial_assignments, temperature_ratio)

The deterministic annealing algorithm starts with randomised assignment expectations (the 〈M[i,λ]〉). Fixed point iteration (usually involving an intermediate potential calculation) at a particular “temperature” should cause the assignment expectations to converge. Lowering the temperature will eventually cause them to converge closer to {0, 1}.

Instances of this class hold the state of convergence and perform the iterations. It can be used as an iterator, like so:

# Random initial assignments
M = 1 - np.random.random((n ,k))

# Normalise the assignments so each row sum is 1
M = M/np.tile(M.sum(1), (k, 1)).T

# Create deterministic annealing state
annealer = AssignmentAnnealing(iterator_function, M, 0.73)

# Tolerance for convergence
tolerance = 1e-6

for temperature_steps in range(20):
    for new_assignments in annealer:
        if (new_assignments - old_assignments).abs().max() < tolerance:
            break
    annealer.cool()

print(np.round(annealer.assignments).astype(int))

This is a very simple example; there are modes of failure you might need to account for depending on your inputs. Since the iterator returned by the annealer is just itself, you can use the built-in function next() instead:

for temperature_steps in range(20):
    for iterations in range(20):
        next(annealer)
    annealer.cool()

The cool() method will lower the temperature by the ratio given in the constructor.

The annealing object also keeps track of the last set of assignment potentials and temperature when cool() was called.

Due to the maths involved combined with floating point imprecision, it is possible that the fixed point iteration sometimes results in NaN entries in the assignment matrix. The reheat() method will restore the remembered temperature and assignments, and the caller can then eg. change the ratio, or take some other action to continue annealing.

The ratio member is a part of the API and can be changed at any time. It must always be strictly between 0 and 1. It has the same meaning as the ratio parameter in the constructor.

The assignments member is part of the API, but should not be assigned to, only read from.

cool()

Reduces the temperature used for further function calls by the user-supplied ratio.

reheat()

Restores the result and temperature from before the cool() method was called.

detan.detan.assignment_expectations(potentials, T)

Calculates assignment expectations (the 〈M[i,λ]〉) from assignment potentials for deterministic annealing.

Parameters:

• potentials – the assignment potentials (any real numbers)
• T – the Lagrangian parameter (temperature) for deterministic annealing (strictly greater than zero)

detan.detan.assignment_iteration(distances)

Composition of assignment_potential() and assignment_expectations() suitable for fixed point iteration. This will raise an exception if the assignment matrix contains any NaN entries.

detan.detan.assignment_potential(assignments, distances)

This calculates the potentials (the ‘ε*[i,λ]’) from the assignment expectations matrix for deterministic annealing.

The assignment matrix must contain entries in (0, 1) (note open endpoints), and the distance matrix must be symmetric and contain only zeros on the diagonal.

Parameters:

• assignments – assignment expectations
• distances – pairwise distance matrix

Returns:

assignment potentials