Computer Science – Artificial Intelligence
Scientific paper
2012-04-15
Computer Science
Artificial Intelligence
Scientific paper
One of the big challenges in the development of probabilistic relational (or probabilistic logical) modeling and learning frameworks is the design of inference techniques that operate on the level of the abstract model representation language, rather than on the level of ground, propositional instances of the model. Numerous approaches for such "lifted inference" techniques have been proposed. While it has been demonstrated that these techniques will lead to significantly more efficient inference on some specific models, there are only very recent and still quite restricted results that show the feasibility of lifted inference on certain syntactically defined classes of models. Lower complexity bounds that imply some limitations for the feasibility of lifted inference on more expressive model classes were established early on in (Jaeger 2000). However, it is not immediate that these results also apply to the type of modeling languages that currently receive the most attention, i.e., weighted, quantifier-free formulas. In this paper we extend these earlier results, and show that under the assumption that NETIME =/= ETIME, there is no polynomial lifted inference algorithm for knowledge bases of weighted, quantifier- and function-free formulas. Further strengthening earlier results, this is also shown to hold for approximate inference, and for knowledge bases not containing the equality predicate.
No associations
LandOfFree
Lower Complexity Bounds for Lifted Inference 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 Lower Complexity Bounds for Lifted Inference, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Lower Complexity Bounds for Lifted Inference will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-287457