Dependency network (graphical model)

Dependency networks (DNs) are graphical models, similar to Markov networks, wherein each vertex (node) corresponds to a random variable and each edge captures dependencies among variables. 
Unlike Bayesian networks, DNs may contain cycles. 
Each node is associated to a conditional probability table, which determines the realization of the random variable given its parents.
Markov blanket.
In a Bayesian network, the Markov blanket of a node is the set of parents and children of that node, together with the children's parents. The values of the parents and children of a node evidently give information about that node. However, its children's parents also have to be included in the Markov blanket, because they can be used to explain away the node in question. In a Markov random field, the Markov blanket for a node is simply its adjacent (or neighboring) nodes. In a dependency network, the Markov blanket for a node is simply the set of its parents.
Dependency network versus Bayesian networks.
Dependency networks have advantages and disadvantages with respect to Bayesian networks. In particular, they are easier to parameterize from data, as there are efficient algorithms for learning both the structure and probabilities of a dependency network from data. Such algorithms are not available for Bayesian networks, for which the problem of determining the optimal structure is NP-hard. Nonetheless, a dependency network may be more difficult to construct using a knowledge-based approach driven by expert-knowledge.
Dependency networks versus Markov networks.
Consistent dependency networks and Markov networks have the same representational power. Nonetheless, it is possible to construct non-consistent dependency networks, i.e., dependency networks for which there is no compatible valid joint probability distribution. Markov networks, in contrast, are always consistent.
Definition.
A consistent dependency network for a set of random variables formula_1 with joint distribution formula_2 is a pair formula_3 where formula_4 is a cyclic directed graph, where each of its nodes corresponds to a variable in formula_5, and formula_6 is a set of conditional probability distributions. The parents of node formula_7, denoted formula_8, correspond to those variables formula_9 that satisfy the following independence relationships
The dependency network is consistent in the sense that each local distribution can be obtained from the joint distribution formula_2. Dependency networks learned using large data sets with large sample sizes will almost always be consistent. A non-consistent network is a network for which there is no joint probability distribution compatible with the pair formula_3. In that case, there is no joint probability distribution that satisfies the independence relationships subsumed by that pair.
Structure and parameters learning.
Two important tasks in a dependency network are to learn its structure and probabilities from data. Essentially, the learning algorithm consists of independently performing a probabilistic regression or classification for each variable in the domain. It comes from observation that the local distribution for variable formula_7 in a dependency network is the conditional distribution formula_14, which can be estimated by any number of classification or regression techniques, such as methods using a probabilistic decision tree, a neural network or a probabilistic support-vector machine. Hence, for each variable formula_7 in domain formula_16, we independently estimate its local distribution from data using a classification algorithm, even though it is a distinct method for each variable.
Here, we will briefly show how probabilistic decision trees are used to estimate the local distributions. For each variable formula_7 in formula_5, a probabilistic decision tree is learned where formula_7 is the target variable and formula_20 are the input variables. To learn a decision tree structure for formula_7, the search algorithm begins with a singleton root node without children. Then, each leaf node in the tree is replaced with a binary split on some variable formula_22 in formula_20, until no more replacements increase the score of the tree.
Probabilistic Inference.
A probabilistic inference is the task in which we wish to answer probabilistic queries of the form formula_24, given a graphical model for formula_5, where formula_26 (the 'target' variables) formula_27 (the 'input' variables) are disjoint subsets of formula_5. One of the alternatives for performing probabilistic inference is using Gibbs sampling. A naive approach for this uses an ordered Gibbs sampler, an important difficulty of which is that if either formula_24 or formula_30 is small, then many iterations are required for an accurate probability estimate. Another approach for estimating formula_24 when formula_30 is small is to use modified ordered Gibbs sampler, where formula_33 is fixed during Gibbs sampling.
It may also happen that formula_34 is rare, e.g. when formula_26 has many variables. So, the law of total probability along with the independencies encoded in a dependency network can be used to decompose the inference task into a set of inference tasks on single variables. This approach comes with the advantage that some terms may be obtained by direct lookup, thereby avoiding some Gibbs sampling.
You can see below an algorithm that can be used for obtain formula_36 for a particular instance of formula_37 and formula_38, where formula_26 and formula_27 are disjoint subsets.
Applications.
In addition to the applications to probabilistic inference, the following applications are in the category of Collaborative Filtering (CF), which is the task of predicting preferences. Dependency networks are a natural model class on which to base CF predictions, once an algorithm for this task only needs estimation of formula_58 to produce recommendations. In particular, these estimates may be obtained by a direct lookup in a dependency network.
Another class of useful applications for dependency networks is related to data visualization, that is, visualization of predictive relationships.