Efficient Sampling for Bipartite Matching Problems
Bipartite matching problems characterize many situations, ranging from ranking in information retrieval to correspondence in vision. Exact inference in real-world applications of these problems is intractable, making efficient approximation methods essential for learning and inference. In this paper we propose a novel {\it sequential matching} sampler based on the generalization of the Plackett-Luce model, which can effectively make large moves in the space of matchings. This allows the sampler to match the difficult target distributions common in these problems: highly multimodal distributions with well separated modes. We present experimental results with bipartite matching problems - ranking and image correspondence - which show that the sequential matching sampler efficiently approximates the target distribution, significantly outperforming other sampling approaches.
Code (0)
등록된 구현이 없습니다.
Tasks
Information RetrievalRetrievalSimilar Papers 제목 키워드 기반
Efficient and Consistent Adversarial Bipartite Matching
Many important structured prediction problems, including learning to rank items, correspondence-based natural language processing, and multi-object tracking, can be formulated as weighted bipartite matching optimiza…
Computational EfficiencyLearning-To-RankMulti-Object TrackingObject Tracking+1WeaveNet for Approximating Two-sided Matching Problems
Matching, a task to optimally assign limited resources under constraints, is a fundamental technology for society. The task potentially has various objectives, conditions, and constraints; however, the efficient neural n…
Efficient Neural NetworkGraph Neural NetworkDeep Policies for Online Bipartite Matching: A Reinforcement Learning Approach
The challenge in the widely applicable online matching problem lies in making irrevocable assignments while there is uncertainty about future inputs. Most theoretically-grounded policies are myopic or greedy in nature. I…
Decision Makingreinforcement-learningReinforcement LearningReinforcement Learning (RL)$k$-Variance: A Clustered Notion of Variance
We introduce $k$-variance, a generalization of variance built on the machinery of random bipartite matchings. $K$-variance measures the expected cost of matching two sets of $k$ samples from a distribution to each other,…
Restricted Boltzmann Machine Assignment Algorithm: Application to solve many-to-one matching problems on weighted bipartite graph
In this work an iterative algorithm based on unsupervised learning is presented, specifically on a Restricted Boltzmann Machine (RBM) to solve a perfect matching problem on a bipartite weighted graph. Iteratively is calc…