P(xneighbors(x)).ppt

Inference Overview The MC-SAT algorithm Knowledge-based model construction Lazy inference Lifted inference MCMC: Gibbs Sampling But … Insufficient for Logic Problem:Deterministic dependencies break MCMCNear-deterministic ones make it very slow Solution:Combine MCMC and WalkSAT→ MC-SAT algorithm Combinatorial Explosion Problem: If there are n constantsand the highest clause arity is c,the ground network requires O(n ) memory(and inference time grows in proportion) Solutions: Knowledge-based model construction Lazy inference Lifted inference Knowledge-BasedModel Construction Basic idea: Most of ground network may be unnecessary,because evidence renders query independent of it Assumption: Evidence is conjunction of ground atoms Knowledge-based model construction (KBMC): First construct minimum subset of network neededto answer query (generalization of KBMC) Then apply MC-SAT (or other) Ground Network Construction Example Grounding Example Grounding Example Grounding Example Grounding Example Grounding Example Grounding Example Grounding Example Grounding Example Grounding Lazy Inference Most domains are extremely sparse Most ground atoms are false Therefore most clauses are trivially satisfied We can exploit this by Having a default state for atoms and clauses Grounding only those atoms and clauses with non-default states Typically reduces memory (and time) by many orders of magnitude Example: Scientific Research Lazy Inference Here: LazySAT (lazy version of WalkSAT) Method is applicable to many other algorithms (including MC-SAT) Na?ve Approach Create the groundings and keep in memory True atoms Unsatisfied clauses Memory cost is O(# unsatisfied clauses) Problem Need to go to the KB for each flip Too slow! Solution Idea : Keep more things in memory A list of active atoms Potentially unsatisfied clauses (active clauses) LazySAT: Definitions An atom is an Active Atom if It is in the initial set of active atoms It was flipped at some point during the sea