Why collective inference improves relational classification

ABSTRACT

Procedures for collective inference make simultaneous statistical judgments about the same variables for a set of related data instances. For example, collective inference could be used to simultaneously classify a set of hyperlinked documents or infer the legitimacy of a set of related financial transactions. Several recent studies indicate that collective inference can significantly reduce classification error when compared with traditional inference techniques. We investigate the underlying mechanisms for this error reduction by reviewing past work on collective inference and characterizing different types of statistical models used for making inference in relational data. We show important differences among these models, and we characterize the necessary and sufficient conditions for reduced classification error based on experiments with real and simulated data.

REFERENCES

• 1: Soumen Chakrabarti , Byron Dom , Piotr Indyk, Enhanced hypertext categorization using hyperlinks, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.307-318, June 01-04, 1998, Seattle, Washington, United States
• 2: Pedro Domingos, A Unified Bias-Variance Decomposition for Zero-One and Squared Loss, Proceedings of the Seventeenth National Conference on Artificial Intelligence and Twelfth Conference on Innovative Applications of Artificial Intelligence, p.564-569, July 30-August 03, 2000
• 3: Pedro Domingos , Matt Richardson, Mining the network value of customers, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.57-66, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502525]
• 4: Lise Getoor, Learning Probabilistic Relational Models, Proceedings of the 4th International Symposium on Abstraction, Reformulation, and Approximation, p.322-323, July 26-29, 2000
• 5: Getoor, L., E. Segal, B. Taskar, & D. Koller. Probabilistic Models of Text and Link Structure for Hypertext Classification. In Proc. IJCAI01 Workshop on Text Learning: Beyond Supervision, 2001.
• 6: Getoor, L., J. Rhee, D. Koller, & P. Small. Understanding Tuberculosis Epidemiology using Probabilistic Relational Models. Journal of Artificial Intelligence in Medicine, vol. 30, pp. 233--256, 2004.
• 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: Kersting, K. & L. De Raedt. Basic principles of learning Bayesian logic programs. Technical Report No. 174, Institute for Computer Science, University of Freiburg, Germany, June 2002.
• 9: Macskassy, S. & F. Provost. A Simple Relational Classifier. In Proc. KDD-2003 Workshop on Multi-Relational Data Mining (MRDM-2003), pp. 64--76, 2003.
• 10: Neville, J. & D. Jensen. Iterative Classification in Relational Data. In Proc. AAAI-2000 Workshop on Learning Statistical Models from Relational Data, pp. 13--20, 2000.
• 11: Neville, J. & D. Jensen. Supporting Relational Knowledge Discovery: Lessons in Architecture and Algorithm Design. In Proc. ICML2002 Data Mining Lessons Learned Workshop, pp. 57--64, 2002.
• 12: Neville, J., & Jensen, D. Collective Classification with Relational Dependency Networks. In Proc. KDD-2003 Workshop on Multi-Relational Data Mining (MRDM-2003), pp. 77--91, 2003.
• 13: Jennifer Neville , David Jensen , Brian Gallagher, Simple Estimators for Relational Bayesian Classifiers, Proceedings of the Third IEEE International Conference on Data Mining, p.609, November 19-22, 2003
• 14: Seán Slattery , Tom M. Mitchell, Discovering Test Set Regularities in Relational Domains, Proceedings of the Seventeenth International Conference on Machine Learning, p.895-902, June 29-July 02, 2000
• 15: Taskar, B., P. Abbeel & D. Koller. Discriminative Probabilistic Models for Relational Data. In Proc. 18th Conference on Uncertainty in Artificial Intelligence, pp. 485--492, 2002.
• 16: Taskar, B., E. Segal & D. Koller. Probabilistic Classification and Clustering in Relational Data. In Proc. 17th International Joint Conference on Artificial Intelligence, pp. 870--878, 2001.
• 17: Yiming Yang , Seán Slattery , Rayid Ghani, A Study of Approaches to Hypertext Categorization, Journal of Intelligent Information Systems, v.18 n.2-3, p.219-241, March-May 2002 [doi>10.1023/A:1013685612819]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
collective inference, probabilistic relational models, relational learning