How does the affinity propagation software that is posted decide when to stop iterating?
It monitors the exemplar decisions that would be made after each iteration and if these don’t change over convits iterations, the procedure terminates. In any case, if maxits iterations are reached, the procedure terminates. I’ve run affinity propagation many times on several data sets and my intuition is that it always converges when there exists a “stable” or “good” solution (in some sense) but may oscillate when a good solution doesn’t exist. Can you prove anything about this scenario? Yes. It turns out that under certain conditions, if a stable solution exists (ie, a solution that is robust to perturbations in the similarities and preferences), affinity propagation will find it. Let us know if you’re interested in the details.
