A Framework for Learning from Distributed Data Using Sufficient Statistics and Its Application to Learning Decision Trees

Article type: Research Article

Authors: Caragea, Doina | Silvescu, Adrian | Honavar, Vasant

Affiliations: Artificial Intelligence Research Laboratory, Computer Science Department, Iowa State University, 226 Atanasoff Hall, Ames, IA 50011-1040, USA. dcaragea@cs.iastate.edu, silvescu@cs.iastate.edu, honavar@cs.iastate.edu

Abstract: This paper motivates and precisely formulates the problem of learning from distributed data; describes a general strategy for transforming traditional machine learning algorithms into algorithms for learning from distributed data; demonstrates the application of this strategy to devise algorithms for decision tree induction from distributed data; and identifies the conditions under which the algorithms in the distributed setting are superior to their centralized counterparts in terms of time and communication complexity. The resulting algorithms are provably exact in that the decision tree constructed from distributed data is identical to that obtained in the centralized setting. Some natural extensions leading to algorithms for learning from heterogeneous distributed data and learning under privacy constraints are outlined.

Keywords: Distributed Learning, Sufficient Statistics, Learning Agents, Decision Trees

DOI: 10.3233/HIS-2004-11-210

Journal: International Journal of Hybrid Intelligent Systems, vol. 1, no. 1-2, pp. 80-89, 2004