Timezone: »

Training Factor Graphs with Reinforcement Learning for Efficient MAP Inference
Michael Wick · Khashayar Rohanimanesh · Sameer Singh · Andrew McCallum

Tue Dec 08 07:00 PM -- 11:59 PM (PST) @

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). Rather than setting parameters to maximize the likelihood of the training data, parameters of the factor graph are treated as a log-linear function approximator and learned with temporal difference (TD); MAP inference is performed by executing the resulting policy on held out test data. Our method allows efficient gradient updates since only factors in the neighborhood of variables affected by an action need to be computed|we bypass the need to compute marginals entirely. 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.

Author Information

Michael Wick (Oracle Labs)
Khashayar Rohanimanesh (University of Massachusetts)
Sameer Singh (University of California, Irvine)
Andrew McCallum (UMass Amherst)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors