Abstract:

Graphical models, including constraint networks, Bayes networks,
Markov random fields and influence diagrams, are knowledge
representation  schemes that capture independencies in the knowledge
base and support efficient, graph-based algorithms for a variety of
reasoning tasks, including scheduling,  planning, diagnosis and
situation assessment, design, and hardware and software verification.
Algorithms for processing graphical models are of two primary  types:
inference-based and search-based. Inference-based algorithms (e.g.,
variable-elimination, join-tree clustering)    are time and space
exponentially bounded by the tree-width of the problem's graph.
Search-based algorithms can be executed in linear space and often
outperform their worst-case predictions. The thrust of advanced
schemes is in combining inference and search yielding a spectrum of
memory-sensitive algorithms universally applicable across graphical
models.

Following  a brief overview of  principles of reasoning with
graphical models (e.g.,  constraints and probabilistic reasoning), I
will introduce a new AND/OR search  perspective  for graphical models
and the parameters that govern their space-time tradeoffs. In
particular,  I will prove  exponential saving for linear-memory
search as compared to the traditional  (OR) search-space and show
that in the presence of full caching, the AND/OR space is exponential
in  the tree-width while the OR space is exponential in the
path-width. The  computational power of this concept across all
graphical models will be demonstrated empirically focusing on  "mixed
networks", a recently proposed graphical model that permits
expressing  both probabilistic information and constraints,
explicitly.