MAP inference in Large Factor Graphs with Reinforcement Learning

Khashayar Rohanimanesh, Michael Wick, Sameer Singh, Andrew McCallumScholarWorks@UMassAmherst 2008

Abstract

Large, relational factor graphs with structure defined by first-order logic or other languages give rise to notoriously difficult inference problems. Because unrolling the structure necessary to represent distributions over all hypotheses has exponential blow-up, solutions are often derived from MCMC. However, because of limitations in the design and parameterization of the jump function, these sampling-based methods suffer from local minima--the system must transition through lower-scoring configurations before arriving at a better MAP solution. This paper presents a new method of explicitly selecting fruitful downward jumps by leveraging reinforcement learning (RL) to model delayed reward with a log-linear function approximation of residual future score improvement. Our method provides dramatic empirical success, producing new state-of-the-art results on a complex joint model of ontology alignment, with a 48% reduction in error over state-of-the-art in that domain.
BibTeX
@inproceedings{rohanimanesh2008map,
  author = {Khashayar Rohanimanesh and Michael Wick and Sameer Singh and Andrew McCallum},
  title = {{MAP inference in Large Factor Graphs with Reinforcement Learning}},
  booktitle = {ScholarWorks@UMassAmherst},
  year = {2008},
}

Loading related content...

Figure