Heckerman, JMLR 2000

Citation

Dependency Networks for Inference, Collaborative Filtering, and Data Visualization. David Heckerman, David Maxwell Chickering, Christopher Meek, Robert Rounthwaite, Carl Kadie; in JMLR, 1(Oct):49-75, 2000

Online version

[1]

Summary

In this paper, author describe a graphical model for probabilistic relationship, an alternative to the bayesian network, called dependency network. The dependency network, unlike bayesian network is potentially cyclic. The dependency network are well suited to task of predicting preferences like in collaborative filtering. The dependency network is not good for encoding causal relationship.

Brief description of the method

• Consistent Dependency Network

Given a domain of interest having set of finite variables $X=(X_{1},...,X_{n})$ with a positive joint distribution $p(x)$, a consistent dependency network for $X$ is a pair $(G,P)$ where $G$ is a cyclic directed graph and $P$ is a set of conditional probability distributions. The parents of node $X_{i}$, denoted $Pa_{i}$, correspond to those variable $Pa_{i}\subseteq (X_{1},..,X_{i-1},X_{i+1},...,X_{n})$ that satisfy: $p(x_{i}|pa_{i})=p(x_{i}|x_{1},....,x_{i-1},x_{i+1},...,x_{n})=p(x_{i}|x\setminus x_{i})$

The dependency network is consistent in the sense that each local distribution can be obtained via inference from the joint distribution $p(x)$.

The inference can be perform by converting to a markov network, triangulating that network and then applying one of the standard algorithms for the inference.

• General Dependency Network

Given a domain of interest having set of finite variables $X=(X_{1},...,X_{n})$, let $P=(p_{1}(x_{1}|x\setminus x_{1}),...,p_{n}(x_{n}|x\setminus x_{m}))$ be a set of conditional distribution, one for each variable in $X$. A dependency network for $X$ and $P$ is a pair $(G,P')$ where $G$ is a (usually cyclic) directed graph and $P'$ is a set of conditional probability distribution satisfying $p_{i}(x_{i}|Pa_{i})=p_{i}(x_{i}|x\setminus x_{i})$

Experimental Result

They experimented it on the problem of collaborative filtering on three datasets - Nielsen, MS.COM and MSNBC. Overall Bayesian network are slightly more accurate but dependency network are significantly faster at prediction.