IDEALS Home University of Illinois at Urbana-Champaign logo The Alma Mater The Main Quad

Action-centered reasoning for probabilistic dynamic domains

Show full item record

Bookmark or cite this item: http://hdl.handle.net/2142/29669

Files in this item

File Description Format
PDF hajishirzi_hannaneh.pdf (4MB) (no description provided) PDF
Title: Action-centered reasoning for probabilistic dynamic domains
Author(s): Hajishirzi, Hannaneh
Advisor(s): Amir, Eyal
Contributor(s): Roth, Dan; Hockenmaier, Julia; Mueller, Erik T.
Department / Program: Computer Science
Discipline: Computer Science
Degree Granting Institution: University of Illinois at Urbana-Champaign
Degree: Ph.D.
Genre: Doctoral
Subject(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.
Issue Date: 2012-02-06
Genre: thesis
URI: http://hdl.handle.net/2142/29669
Rights Information: Copyright 2011 Hannaneh Hajishirzi
Date Available in IDEALS: 2012-02-06
Date Deposited: 2011-12
 

This item appears in the following Collection(s)

Show full item record

Item Statistics

  • Total Downloads: 132
  • Downloads this Month: 4
  • Downloads Today: 0

Browse

My Account

Information

Access Key