Proceedings of a Workshop on Statistics on Networks (CD-ROM) (2007) / Chapter Skim
Currently Skimming:
Dependency Networks for Relational Data--David Jensen, University of Massachusetts
Dependency Networks for Relational Data--David Jensen, University of Massachusetts
Pages 425-449
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 425... ...
She is also in the job market this year, so if you happen to be in computer science and looking for a good faculty candidate, she should definitely be on your list. The main point of what I'm going to talk about is a new joint model for relational data: Relational Dependency Networks (RDNs)
|
From page 426... ...
We have the entire database, but you can access records on your particular stockbroker if you are interested in finding out if they have engaged in questionable conduct prior to you working with them. The website is http://www.nasdbrokercheck.com.
|
From page 427... ...
There is one aspect in which there is missing data, which is that brokers file disclosures indicating that they may have done something wrong. This can be a minor customer complaint; it can be a felony, and there is a large range of possible behaviors.
|
From page 428... ...
You assume the instances are independent, and you are looking for relationships between the variables in a given instance. In contrast, we assume there are multiple tables, many different types of objects, and importantly, the statistical dependencies may run between instances in the 428
|
From page 429... ...
Some of the details aren't here because NASD, for obvious reasons, has said "Would you please not provide too many details of the exact model that you have built," although they are surprisingly willing to work with us on publication. In fact, three of the co-authors of a paper that we just presented at the Knowledge Discovery and Data Mining Conference were all from NASD, and that paper goes into some detail.
|
From page 430... ...
You can look at these and get a sense of the overall types of statistical dependencies that exist in your data, and then the high-level summary of a model that actually has more detail sitting under each of the nodes in much the same way that Bayesian networks do. Also, there are these black dots in the upper left-hand corners of the four boxes, which indicate dependence on the mere count of those object types.
|
From page 431... ...
That includes work by Daphne Koller's group at Stanford on what they originally called PRMs, and now often called relational Bayesian networks, relational Markov networks, also out of Daphne's group, and Ben Taskar, one of her students, our own relational dependency networks, and most recently some work at the University of Washington by Pedro Domingos and his student Matt Richardson in Markov logic networks. Figure 5 lists some of this work.
|
From page 432... ...
This sounds like a really bad idea, because what you would like to do is learn your entire model, all of the elements of your model jointly, but if you have a sufficiently large data set, what you end up with is the data set performing a coordination function that allows you to have the individual conditional models be consistent enough with each other, that you end up forming something that looks a lot like a coherent joint distribution of the data. What you want to do, for instance, is learn these individual conditional models.
|
From page 433... ...
FIGURE 6 The types of conditional models that we learned are these relational probability trees. These are trees where you take, for instance, a broker and the surrounding neighborhood of objects, which we specify ahead of time, drop that into the tree, and it rattles down to one of several leaf nodes.
|
From page 434... ...
That's addressed in detail in the paper. Finally, you can construct yourself one of these relational probability trees.
|
From page 435... ...
If we do the wrong kind of learning of conditional models, we can end up with a relational dependency network that looks like this, that is essentially impossible to interpret, which makes inference much more complex. The reasons for that are there are at least two special problems you run into.
|
From page 436... ...
Firms tend to have either lots of these brokers or very few of them, so autocorrelation is a fact of life in many of these data sets.
|
From page 437... ...
Figure 12 shows just notionally a citation network where you have papers and authors, and they are connected in the way that you would expect in terms of people authoring papers and papers citing each other. We have this network, and we also have attributes on these individual things: attributes on these papers and attributes on these authors.
|
From page 438... ...
We also need to have the entire data set available to us to make these inferences simultaneously, because some of these nodes that are parents of the node we are trying to predict are, in turn, other things whose values we are inferring, other variables whose value we are inferring. FIGURE 12 We used Gibbs sampling to do this inference process, and we have had very good experience with its convergence and other properties.
|
From page 439... ...
The influence of highly confident inferences can travel substantial distances in the graph. Collective inference exploits a clever factoring of the space of dependencies to reduce variance, thus improving performance over considering all relational attributes, as shown in (Jensen, Neville, and Gallagher, 2004)
|
From page 440... ...
, which was very useful. QGRAPH allows us to submit queries, written with a simple visual syntax, that return entire subgraphs with heterogeneous structure.
|
From page 441... ...
So, these get you structures that can be highly variable in size, but which have the same basic properties in terms of the kinds of objects that they contain. We use these queries both as an ad hoc tool for looking at big graphs, and for pulling out small pieces of them that are easy to actually display visually.
|
From page 442... ...
We have open source software (PROXIMITY) available to build these relational dependency networks, and that implements the query language and other things.
|
From page 443... ...
One example I want to note is that of Pedro Domingos and Matt Richardson who put out a paper in 2001 that won the best paper award at the Knowledge Discovery and Data Mining Conference. Two years later Jon Kleinberg and co-authors picked up on that line of work, which had to do with viral marketing and some really interesting technical issues.
|
From page 444... ...
DR. JENSEN: Structural learning in RDNs is merely learning conditional models, and looking at the variables that are in those conditional models.
|
From page 445... ...
DR. JENSEN: When we are learning the relational probability trees we are looking at individual variables as possible predictors of our dependent variable.
|
From page 446... ...
You wouldn't learn much from our implementation unless you were using this particularly bizarre database that we use for efficiency reasons. However, the algebra should provide you a really good starting point for an implementation that should be fairly straightforward, and many of the query optimizations that work for SQL will 446
|
From page 447... ...
Proceedings of the 2nd Multi- Relational Data Mining Workshop, 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Neville, J., and D
|
From page 448... ...
2004. Markov Logic: A Unifying Framework for Statistical Relational Learning.
|
From page 449... ...
Appendixes 449
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.