5
$\begingroup$

I would like to find the optimal correspondences between two systems of objects based on the distances between objects WITHIN the two systems. So, the input to the algorithm would be two square distance matrices which express the distances of every object from one system to every other object within the same system. For example, if one system has objects {Q, R, S} and the other has objects {A, B, C} then the two distance matrices might look like:

        Q       R       S
Q       0       .5      .2
R       .5      0       .7
S       .2      .7      0

        A       B       C
A       0       .8      .4
B       .8      0       .3
C       .4      .3      0

meaning, for example, that the distance of object R to S is 0.7. Every object has a distance of 0 to itself, but the distances need not satisfy the assumptions of a metric space. However, each of the distance matrices can be assumed to be symmetric as in this example. The output of the algorithm would be a set of correspondences between objects in the systems that minimizes the sum of the absolute differences between the distances of corresponding objects under the constraint that no object in one system corresponds to more than one object in the other system. In the example above, the optimal correspondences would be R<->A, Q<->C, and S<->B, which results in a sum of dissimilarities between distances of:

|0.4-0.5| + |0.8-0.7|   for the distance relations that R and A enter into. E.g. dist(R,Q)=.5 and dist(A,C)=.4
          +
|0.2-0.3| + |0.5-0.4|   for the distance relations that Q and C enter into.
          +
|0.3-0.2| + |0.7-0.8|   for the distance relations that S and B enter into.
          =
         0.6

which is lower than any other consistent (no 2-to-1 correspondences allowed) way of placing the objects in correspondence. The output, then, for the algorithm, might look like:

        Q       R       S
A       0       1       0
B       0       0       1
C       1       0       0

where 1 means that the objects are placed into correspondences. I have already developed (http://cognitrn.psych.indiana.edu/rgoldsto/pdfs/relalign.pdf) an iterative neural network constraint satisfaction algorithm for this problem, but it is far too slow and computationally inefficient for systems that contain more than 20 or so objects because it has O(n^4) complexity. It feels like there should be a fast linear algebraic solution to this problem. There are a couple of possibly related solutions that I can’t seem to get to be related enough for my needs. For example, the “assignment problem” has a O(n^3) solution in the form of the “Hungarian algorithm” but this assumes fixed costs for each assignment, whereas in the above problem the cost associated with assigning A to Q, for example, depends on all of the other assignments being made because these other assignments will change which distances between systems are being compared. The problem also seems like something that might be handled with Multidimensional Unfolding or Generalized Procrustes Analysis, but the key difference in the current problem is that we don’t have labels that tell us which objects from one system are the same as which objects in the other system — that’s what we’re trying to figure out in the first place! Thanks for any leads.

$\endgroup$
4
$\begingroup$

One possible approach: use the Hungarian twice.

Here is your two square symmetric proximity matrices (I multiplied everything by 10; also, changed AB value from 8 to 9 - my fancy, with your permission)

        Q       R       S
Q              
R       5       
S       2       7       

        A       B       C
A       
B       9       
C       4       3       

Consider every pair of values between the matrices, their absolute difference, as a cost and construct the cost matrix

      AB     AC     BC
QR  |5-9|  |5-4|  |5-3|
QS  |2-9|  |2-4|  |2-3|
RS  |7-9|  |7-4|  |7-3|
             =
      AB     AC     BC
QR     4      1*     2
QS     7      2      1*
RS     2*     3      4

Perform Hungarian matching. The starred values above being the ones which sum is the minimum, and so the matching is

QR - AC
QS - BC
RS - AB

OK. In each pair, there is two objects from set1 and two objects from set2. Construct set1 X set2 object matrix showing how many times they encounter with each other within pairs.

   A   B   C
Q  1   1   2*
R  2*  1   1
S  1   2*  1

Perform Hungarian match (now treating these frequencies as gain, not cost). The starred values, which sum is maximized, mark the pairs you are after.

Q - C
R - A
S - B

As a variant, you can weight counts of the last (gain) matrix by the values from the previous cost matrix. For example, R and A encounter twice, as we see. Once under RS-AB with cost 2 and once under QR-AC with cost 1. So you can weight the frequency, make it the sum-of-costs. In your example, since costs are opposite to gains, you should somehow invert those weights; or just do the whole analysis based only on gains from the beginning.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.