Map estimation in mrfs via rank aggregation

Abstract

Efficient estimation of the maximum a priori (MAP) assignment in large statistical rela-tional networks still remains an open issue in spite of the extensive research in this area. We propose a novel method of exploiting top-K MAP estimates from simpler subgraphs to find an assignment that is either MAP opti-mal, or has an associated bound on how far it is from the optimal. Our method extends the well-known tree reweighted max-product al-gorithm (TRW) and is guaranteed to always provide tighter upper bounds. Experiments on synthetic and real data show that we are able to the find the optimal in many more cases than TRW, at significantly fewer itera-tions and our bounds are much tighter than those provided by TRW