On the Complexity of Rule Discovery from Distributed Data Martin Scholz   View Paper (PDF)   Return to Session 19: Tools and Algorithms Abstract This paper analyses the tractability of rule selection for supervised learning in distributed scenarios. The selection of rules is usually guided by a utility measure such as predictive accuracy or weighted relative accuracy. A common strategy to tackle rule selection from distributed data is to evaluate rules locally on each dataset. While this works well for homogeneously distributed data, this work proves limitations of this strategy if distributions are allowed to deviate. The identification of those subsets for which local and global distributions deviate, poses a learning task of its own, which is shown to be at least as complex as discovering the globally best rules from local data. ©2006 Association for Computing Machinery