Learning relational probability trees

ABSTRACT

Classification trees are widely used in the machine learning and data mining communities for modeling propositional data. Recent work has extended this basic paradigm to probability estimation trees. Traditional tree learning algorithms assume that instances in the training data are homogenous and independently distributed. Relational probability trees (RPTs) extend standard probability estimation trees to a relational setting in which data instances are heterogeneous and interdependent. Our algorithm for learning the structure and parameters of an RPT searches over a space of relational features that use aggregation functions (e.g. AVERAGE, MODE, COUNT) to dynamically propositionalize relational data and create binary splits within the RPT. Previous work has identified a number of statistical biases due to characteristics of relational data such as autocorrelation and degree disparity. The RPT algorithm uses a novel form of randomization test to adjust for these biases. On a variety of relational learning tasks, RPTs built using randomization tests are significantly smaller than other models and achieve equivalent, or better, performance.

REFERENCES

• 1: Hendrik Blockeel , Luc De Raedt, Top-down induction of first-order logical decision trees, Artificial Intelligence, v.101 n.1-2, p.285-297, May 1998 [doi>10.1016/S0004-3702(98)00034-4]
• 2: Mark Craven , Dan DiPasquo , Dayne Freitag , Andrew McCallum , Tom Mitchell , Kamal Nigam , Seán Slattery, Learning to extract symbolic knowledge from the World Wide Web, Proceedings of the fifteenth national/tenth conference on Artificial intelligence/Innovative applications of artificial intelligence, p.509-516, July 1998, Madison, Wisconsin, United States
• 3: Eugene S Edgington, Randomization tests, Marcel Dekker, Inc., New York, NY, 1986
• 4: Saso (Ed.) Dzeroski , Nada Lavrac , Saso Dzeroski, Relational Data Mining, Springer-Verlag New York, Inc., Secaucus, NJ, 2001
• 5: Nir Friedman , Lise Getoor , Daphne Koller , Avi Pfeffer, Learning Probabilistic Relational Models, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1300-1309, July 31-August 06, 1999
• 6: David D. Jensen , Paul R. Cohen, Multiple Comparisons in Induction Algorithms, Machine Learning, v.38 n.3, p.309-338, March 2000 [doi>10.1023/A:1007631014630]
• 7: David Jensen , Jennifer Neville, Linkage and Autocorrelation Cause Feature Selection Bias in Relational Learning, Proceedings of the Nineteenth International Conference on Machine Learning, p.259-266, July 08-12, 2002
• 8: D. Jensen, J. Neville and M. Hay. Avoiding bias when aggregating relational data with degree disparity. Proc. of the 20th Intl Joint Conf. on Machine Learning, to appear.
• 9: Arno J. Knobbe , Arno Siebes , Danïel van der Wallen, Multi-relational Decision Tree Induction, Proceedings of the Third European Conference on Principles of Data Mining and Knowledge Discovery, p.378-383, September 15-18, 1999
• 10: S. Kramer. Structural regression trees. Proc. of the 13th National Conference on Artificial Intelligence, 812--819, 1996.
• 11: Stefan Kramer , Bernhard Pfahringer , Christopher Helma, Stochastic Propositionalization of Non-determinate Background Knowledge, Proceedings of the 8th International Workshop on Inductive Logic Programming, p.80-94, July 22-24, 1998
• 12: Andrew McCallum , Kamal Nigam , Jason Rennie , Kristie Seymore, A Machine Learning Approach to Building Domain-Specific Search Engines, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.662-667, July 31-August 06, 1999
• 13: J. Neville, D. Jensen, B. Gallagher and R. Fairgrieve. Simple estimators for relational Bayesian classifiers. University of Massachusetts Amherst, Tech Report 03--04, 2003.
• 14: F. Provost and P. Domingos. Well-trained PETs: Improving probability estimation trees. CDER Working Paper #00-04-IS, Stern School of Business, NYU, 2000.
• 15: J. Ross Quinlan, C4.5: programs for machine learning, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1993