Reasoning with models of probabilistic knowledge over probabilistic knowledge

Shirazi, Afsaneh H.

Permalink

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

Description

Title

Reasoning with models of probabilistic knowledge over probabilistic knowledge

Author(s)

Shirazi, Afsaneh H.

Issue Date

2011-05-25T14:58:10Z

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

Amir, Eyal

Doctoral Committee Chair(s)

Amir, Eyal

Committee Member(s)

• Roth, Dan
• Forsyth, David A.
• Chekuri, Chandra S.

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 Knowledge
• Bayesian Networks
• Modal Logic

Abstract

In multi-agent systems, the knowledge of agents about other agents’ knowledge often plays a pivotal role in their decisions. In many applications, this knowledge involves uncertainty. This uncertainty may be about the state of the world or about the other agents’ knowledge. In this thesis, we answer the question of how to model this probabilistic knowledge and reason about it efficiently. Modal logics enable representation of knowledge and belief by explicit reference to classical logical formulas in addition to references to those formulas’ truth values. Traditional modal logics (see e.g. [Fitting, 1993; Blackburn et al., 2007]) cannot easily represent scenarios involving degrees of belief. Works that combine modal logics and probabilities apply the representation power of modal operators for representing beliefs over beliefs, and the representation power of probability for modeling graded beliefs. Most tractable approaches apply a single model that is either engineered or learned, and reasoning is done within that model. Present model-based approaches of this kind are limited in that either their semantics is restricted to have all agents with a common prior on world states, or are resolving to reasoning algorithms that do not scale to large models. In this thesis we provide the first sampling-based algorithms for model-based reasoning in such combinations of modal logics and probability. We examine a different point than examined before in the expressivity-tractability tradeoff for that combination, and examine both general models and also models which use Bayesian Networks to represent subjective probabilistic beliefs of agents. We provide exact inference algorithms for the two representations, together with correctness results, and show that they are faster than comparable previous ones when some structural conditions hold. We also present sampling-based algorithms, show that those converge under relaxed conditions and that they may not converge otherwise, demonstrate the methods on some examples, and examine the performance of our algorithms experimentally.

Graduation Semester

2011-05

Permalink

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

Copyright and License Information

Copyright 2011 Afsaneh H Shirazi

Owning Collections