Plan recognition is a fundamental challenge in Artificial Intelligence, involving the observation of an agent's actions to "abduce" or infer the underlying goals or plans that best explain those actions. This paper, presented at AAAI 2011, introduces a novel framework for abductive reasoning using Markov Logic Networks (MLNs). By introducing "Hidden Cause" models and a targeted "Abductive Model Construction" process, the authors enable MLNs to scale to complex plan-recognition tasks that were previously computationally intractable.
The Challenge of Abduction in MLNs
Abduction is often described as "inference to the best explanation." Historically, researchers have approached this through purely logical systems, which handle structured data well but struggle with noise, or purely probabilistic systems, which handle uncertainty but struggle with complex relational data.
Markov Logic Networks were designed to bridge this gap by attaching weights to first-order logic formulas. However, standard MLNs are not naturally suited for abduction. Previous attempts to adapt them often resulted in massive, dense networks that were computationally prohibitive for real-world problems.
The Hidden Cause (HC) Model
To address the complexity of previous models, such as the Pairwise Constraint (PC) model, the authors developed the Hidden Cause (HC) Model. Traditional models often created "cliques" in the underlying graph that grew exponentially in complexity. The HC Model simplifies this by introducing a "hidden cause" node ($C_i$) for every possible explanation.
Instead of one giant, complex rule, the HC model uses simpler biconditionals ($P_i \iff C_i$) and links these hidden causes to the observation ($C_i \implies Q$). By placing a negative weight on these hidden causes, the model naturally prefers the simplest explanation—effectively implementing a probabilistic version of Occam’s Razor. This structural change significantly reduces the maximum clique size, leading to a massive leap in inference speed.
Abductive Model Construction (HCAM)
Standard MLN tools typically attempt to "ground" the entire world, creating nodes for every possible object and relationship. This is impossible for large databases. The authors propose HCAM, which uses traditional logical backchaining to identify only the atoms and rules relevant to the current observation. This results in a much smaller, sparser, and more efficient Markov network. This approach demonstrates that logic can serve as an excellent "pre-filter" for probabilistic engines.
Evaluation and Results
The authors evaluated their approach on three distinct benchmarks: Story Understanding (narrative inference), Monroe (emergency response planning), and Linux (predicting user goals from terminal commands).
Key results include:
- Scalability: HCAM was the only MLN-based approach capable of handling the Monroe and Linux datasets; previous models ran out of memory.
- Speed: On the Monroe dataset, HCAM performed inference in 2.27 seconds, a 100x speedup compared to the 252.13 seconds required by previous state-of-the-art MLN approaches.
- Accuracy: HCAM outperformed the well-known "Blaylock" system on both Monroe (97.3% vs 94.2%) and Linux (38.9% vs 36.1%) datasets, while remaining competitive with Bayesian Abductive Logic Programs (BALPs).
Conclusion and Future Work
The HCAM framework proves that combining logical filtering with probabilistic inference allows for scalable, accurate plan recognition. While the system excels at inference, future work remains in streamlining weight learning from partially observed data and moving toward "online" recognition for real-time AI assistants. Additionally, learning abductive rules directly from raw data remains a promising frontier for the field.
Summary updated