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.[1]

Markov blanket

edit

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

edit

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.[2] Nonetheless, a dependency network may be more difficult to construct using a knowledge-based approach driven by expert-knowledge.

Dependency networks versus Markov networks

edit

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

edit

A consistent dependency network for a set of random variables   with joint distribution   is a pair   where   is a cyclic directed graph, where each of its nodes corresponds to a variable in  , and   is a set of conditional probability distributions. The parents of node  , denoted  , correspond to those variables   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  . 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  . In that case, there is no joint probability distribution that satisfies the independence relationships subsumed by that pair.

Structure and parameters learning

edit

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   in a dependency network is the conditional distribution  , 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   in domain  , 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   in  , a probabilistic decision tree is learned where   is the target variable and   are the input variables. To learn a decision tree structure for  , 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   in  , until no more replacements increase the score of the tree.

Probabilistic Inference

edit

A probabilistic inference is the task in which we wish to answer probabilistic queries of the form  , given a graphical model for  , where   (the 'target' variables)   (the 'input' variables) are disjoint subsets of  . 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   or   is small, then many iterations are required for an accurate probability estimate. Another approach for estimating   when   is small is to use modified ordered Gibbs sampler, where   is fixed during Gibbs sampling.

It may also happen that   is rare, e.g. when   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   for a particular instance of   and  , where   and   are disjoint subsets.

  • Algorithm 1:
  1.   (* the unprocessed variables *)
  2.   (* the processed and conditioning variables *)
  3.   (* the values for   *)
  4. While  :
    1. Choose   such that   has no more parents in   than any variable in  
    2. If all the parents of   are in  
      1.  
    3. Else
      1. Use a modified ordered Gibbs sampler to determine  
    4.  
    5.  
    6.  
  5. Returns the product of the conditionals  

Applications

edit

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   to produce recommendations. In particular, these estimates may be obtained by a direct lookup in a dependency network.

  • Predicting what movies a person will like based on his or her ratings of movies seen;
  • Predicting what web pages a person will access based on his or her history on the site;
  • Predicting what news stories a person is interested in based on other stories he or she read;
  • Predicting what product a person will buy based on products he or she has already purchased and/or dropped into his or her shopping basket.

Another class of useful applications for dependency networks is related to data visualization, that is, visualization of predictive relationships.

See also

edit

References

edit
  1. ^ HECKERMAN, David; MAXWELL C., David; MEEK, Christopher; ROUNTHWAITE, Robert; KADIE, Carl (October 2000). "Dependency Networks for Inference, Collaborative Filtering, and Data Visualization" (PDF). Journal of Machine Learning Research.
  2. ^ HECKERMAN, David (2012). "Large-Sample Learning of Bayesian Networks is NP-Hard" (PDF). arXiv:1212.2468. {{cite journal}}: Cite journal requires |journal= (help)