Generalized Collective Inference with Symmetric Clique Potentials

Details Generalized Collective Inference with Symmetric Clique Potentials Generalized Collective Inference with Symmetric Clique Potentials

2009-07-03

arxiv.org/abs/0907.0589v2

Computer Science

Artificial Intelligence

30 pages

Scientific paper

Collective graphical models exploit inter-instance associative dependence to output more accurate labelings. However existing models support very limited kind of associativity which restricts accuracy gains. This paper makes two major contributions. First, we propose a general collective inference framework that biases data instances to agree on a set of {\em properties} of their labelings. Agreement is encouraged through symmetric clique potentials. We show that rich properties leads to bigger gains, and present a systematic inference procedure for a large class of such properties. The procedure performs message passing on the cluster graph, where property-aware messages are computed with cluster specific algorithms. This provides an inference-only solution for domain adaptation. Our experiments on bibliographic information extraction illustrate significant test error reduction over unseen domains. Our second major contribution consists of algorithms for computing outgoing messages from clique clusters with symmetric clique potentials. Our algorithms are exact for arbitrary symmetric potentials on binary labels and for max-like and majority-like potentials on multiple labels. For majority potentials, we also provide an efficient Lagrangian Relaxation based algorithm that compares favorably with the exact algorithm. We present a 13/15-approximation algorithm for the NP-hard Potts potential, with runtime sub-quadratic in the clique size. In contrast, the best known previous guarantee for graphs with Potts potentials is only 1/2. We empirically show that our method for Potts potentials is an order of magnitude faster than the best alternatives, and our Lagrangian Relaxation based algorithm for majority potentials beats the best applicable heuristic -- ICM.

Affiliated with

Also associated with

No associations

Rating

Generalized Collective Inference with Symmetric Clique Potentials does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Generalized Collective Inference with Symmetric Clique Potentials, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Generalized Collective Inference with Symmetric Clique Potentials will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-705865