Subsetting as an approach to distributed learning.

  • 格式:pdf
  • 大小:41.67 KB
  • 文档页数:11

Subsetting as an approach to distributed learning.Simon Thompson and Max Bramer.Artificial Intelligence Research Group,Department of Information Science,University of Portsmouth.

This paper discusses one approach to the scaling problem of machine learning (Chan and Stolfo1995) namely the decomposition of large datasets into smaller subsets so that the learning task oneach subset is greatly reduced in comparison to the learning task for the whole dataset. A previousstudy (Catlett 1992) has examined this approach and concluded that classifiers learned on a subsetof available data were significantly less accurate that classifiers learned on training sets entire. Weexamine a different set of properties from those looked at by Catlett, focusing on the agreementbetween classifiers learned on subsets of a data set. Our intention is to use the information from thelearning process and about the data set to iteratively construct improved subsets which improve theclassification performance of classifiers learned on them with a view to distributing the learningprocess over a number of processors and thus reduce overall learning time. We propose methodswhich can be used to this and discuss the prospect of their development into a distributed knowledgediscovery scheme.

Introduction

In the information age a sea of data surrounds the institutions of our society. The military, civil service,companies both commercial and industrial, even the individual himself: all are overwhelmed by the waveof trivial that they both generate and gather. Yet the proliferation of high speed communications and highperformance computing does not promise to stem this flow, instead the flood gates are to be flung wide.Machine learning and knowledge discovery algorithms offer tools that can be used to sieve the data floodfor useful knowledge. However these technologies may have only limited usefulness when dealing withvery large physically distributed data - such as the data generated by the high speed networks of the future.Dealing with large distributed data sets has become known as the scaling problem of machine learning(Chan and Stolfo 1995).

Traditionally parallel and distributed machine learning tasks have been seen as the province of eitherNeural Networks, or evolutionary algorithms. The drawbacks of Neural Network approaches incomparison to symbolic approaches, and their strengths, are well documented. Clearly in domains whereit is important that the classifiers produced are transparent to the user or expert, Neural Network areinadequate. Evolutionary algorithms are another method of machine learning which use the metaphor ofevolution as a search strategy. Evolutionary algorithms are seen as inherently parallel and can be used toproduce symbolic classifiers. These systems are often called Classifier Systems and may be eitherMichigan or Pittsburgh classifier systems depending on whether the ruleset or individual rules are beingevolved. The main drawback of evolutionary approaches to learning is the relatively high computationalcost of these algorithms (Quinlan 1988).

Scaling has been an issue in machine learning research since its inception: ID3 uses windowing in anattempt to deal with data sets that were intractable for computers in the late 1970’s (Quinlan 1992).Methods such as sampling the dataset to produce a statistically similar subset to train a classifier on havebeen shown to be inappropriate. This problem was studied by Catlett, (Catlett 1991a). He examined threemethods of sampling from datasets - removing duplicates by compaction; stratification to produce an evendistribution in the dataset and iterative random sampling to find a superior random sample. The results ofthis study show that “the techniques [stratification and compaction] are not safe as a means of reducinglearning time” and that “windowing usually adds to the learning time” in noisy datasets.

Work on scaling since Catletts study has tended to focus on his recommendation that methods be soughtto improve the effectiveness and efficiency of processing large training sets. One approach has been toparallelise one or more task in the learning process, or to develop an more efficient and less time complexalgorithm for performing a learning step. Catlett (1991b) describes a technique that allows faster attributeevaluation and Freitas and Lavington (1995) introduce a method of using parallel DB servers to speed upthe retrieval of instances from datasets for knowledge discovery. Alternatively researchers have focused onglobally decomposing the learning problem. A simple method of doing this is to produce groups of votingclassifiers, which can be combined using voting, weighted voting or some baysian or probabilty relatedstrategy. Alternatively more sophisticated methods of combining and integrating knowledge fromindividual classifiers can be used. Examples of this approach are the meta-learning systems proposed byChan and Stolfo (1996) and the agent based approach advocated by Davies and Edwards (1995) .