Abstract
Matching between two sets of objects is tpically ap-proached by finding the object pairs that collectively mari-mize the joint matching score.In this paper, we argue thar this single solution does not necessarily lead to the opti-mal matching accuracy and that general one-to-one assign-ment problems can be improved by considering multiple hy-potheses before compuring the final similarity measure.To that end,we propose to utilize the marginal distributions for each entity.Previously;,this idea has been neglecred mainly because exact marginalization is intractable due to a com-binatorial number of all possible matching permutations.Here,we propose a generic approach to efficiently appro.x-imate the marginal distributions by exploiting the m-best solurions of the original problem.This approach nor only improves the matching solution,but also provides more ac-curate ranking of the results,because of the extra informa-tion included in the marginal distribution.We validate our claim on two distinct objectives:(i)person re-idenrificarion and temporal marching modeled as an integer linear pro-gram,and(ii)feature point matching using a quadratic cost fimction.Our experiments confirm that marginalization in-deed leads to superior performance compared to the single (nearly)opfimal solution,yielding state-of-the-art results in both applications on standard benchmarks