Many problems related to learning and reasoning can make use of graphical models where a knowledge structure is compactly encoded into a graph. When dependencies (or independencies) among the variables of concern are effectively captured in graphical form, it becomes possible to develop efficient methods for answering queries over that information.

Though representation of a given problem into its graphical form requires expertise related to that particular domain, methods of reasoning from graph-based structures are universal and applicable across problem domains. With this in mind, here the author is presenting exact algorithms for propositional graphical models over discrete variables.

Reasoning algorithms can be based on inference or search. The book describes bucket elimination as an example of an inference-based scheme; it involves the generation of an equivalent representation of the input problem through a sequence of deductive steps. Search-based algorithms repeatedly perform a conditioning step that fixes the value of a variable and are described through AND/OR search spaces. Toward the end, the book also covers methods that combine search and inference.

Inference is introduced with the adaptive consistency algorithm for constraint networks. It works by “processing and eliminating variables one by one, while deducing the effect of the eliminated variable.” The procedure involves a join operation over all the relations defined on the current variable. Constraints are partitioned into buckets based on a given variable ordering, and after all buckets are processed without discovering any inconsistency, the method can generate a solution in a backtrack-free manner.

“The complexity of adaptive-consistency is linear in the number of buckets,” but the time to process each bucket depends on generating the join of all relations that is “exponential in the number of variables mentioned in a bucket” [1]. Thus, the efficiency of this approach depends on finding a variable ordering that yields the smallest induced width of the graph, and the book suggests some greedy heuristics for this task.

Bucket elimination can be applied to probabilistic networks by replacing the join and project operators of adaptive consistency with product and summation. Here the task is referred to as belief updating and involves determining posterior probability of singleton variables based on new evidence. An algorithm called BE-bel is considered in much depth. To seek belief for a variable, it needs to be the initial variable of the ordering. The complexity of BE-bel is exponential in the number of variables of the largest bucket.

Cluster-tree elimination algorithms take inference further and avoid the need to call BE-bel multiple times to answer belief query on multiple variables. Considering bucket elimination as a message-passing algorithm along a rooted bucket tree, these algorithms augment it with a second set of messages from bottom to top.

Search-based reasoning algorithms can be executed in a linear space and are the only choice for models with large tree width, large domains, and implicit representation. The book considers AND/OR search spaces in much detail, as their models can be exponentially smaller when compared to linear search.

A general class of spanning trees, called pseudo-trees, are considered to guide the AND/OR search. Such a tree has the property that any arc of the graph that is not part of the tree connects a node to one of its ancestors in the pseudo-tree. The size of the AND/OR search tree depends on the height of its pseudo-tree. To generate compact AND/OR graphs from AND/OR trees, the book presents a merge operation that makes use of the notion of equivalence based on a universal graphical model.

Toward the end, methods to combine inference and search are discussed. Such a scheme can be applied to graphs that contain cycles. Consistent values for variables of the cycle-cutset are found through search, whereas the remaining problem can be solved through inference.

The chapters are organized with content building on earlier material, such that the reader who follows the text from beginning to end derives maximum benefit. An adequate introduction is given to make the book self-contained, while also offering an elaborate bibliography for reference. Part of the current work is based on an earlier book by the same author on constraint processing [1].

The presentation is pleasant and explanations are lucid. All the needed basics are described, and adequate examples are provided.