Action-centered reasoning for probabilistic dynamic domains

Hajishirzi, Hannaneh

Permalink

https://hdl.handle.net/2142/29669 Copy

Description

Title

Action-centered reasoning for probabilistic dynamic domains

Author(s)

Hajishirzi, Hannaneh

Issue Date

2012-02-06T20:10:00Z

Director of Research (if dissertation) or Advisor (if thesis)

Amir, Eyal

Committee Member(s)

• Roth, Dan
• Hockenmaier, Julia C.
• Mueller, Erik T.

Department of Study

Computer Science

Discipline

Computer Science

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Probabilistic reasoning
• Action theories
• Statistical Relational Models
• Narrative Understanding
• Web Monitoring

Abstract

This dissertation focuses on modeling stochastic dynamic domains, using representations and algorithms that combine logical AI ideas and probabilistic methods. We introduce new tractable and highly accurate algorithms for reasoning in those complex domains. Furthermore, we apply these algorithms to tasks of narrative understanding and web page monitoring. We model stochastic dynamic domains with a factored logical representation that uses a graphical model to represent a prior distribution over initial states. Our representation uses sequences of actions (represented in logical form) to represent transitions. We introduce an algorithm for reasoning in stochastic dynamic domains (in propositional and relational fashions) based on subroutines for reasoning in deterministic substructure of the domain. Our algorithm takes advantage of the factored logical representation and efficient subroutines for logical progression and regression. The tractability of the algorithm results from the tractability of these underlying subroutines. Our theoretical and empirical results show significant improvement of our algorithm over previous approaches for reasoning. Our novel algorithm for reasoning in probabilistic dynamic domains samples sequences of deterministic actions corresponding to an observed sequence of probabilistic actions. This algorithm is built upon a novel exact and tractable algorithm to reason about deterministic dynamic domains with a probabilistic prior. We apply the dynamic domain representation and our algorithms to the understanding of narratives. For that, we introduce a label-free iterative learning approach which outperforms the state- of-the-art that uses labeled data. We also apply dynamic domains and reasoning about them in the problem of monitoring change in webpages to direct crawlers. For that, we introduce a greedy algorithm that outperforms the state-of-the-art algorithms.

Graduation Semester

2011-12

Permalink

http://hdl.handle.net/2142/29669

Copyright and License Information

Copyright 2011 Hannaneh Hajishirzi

Owning Collections