LEARNING CONCEPTS IN PARALLEL BASED UPON THE STRATEGY OF VERSION SPACE

Abstract

In this paper, we have attempted to apply the technique of parallel processing to concept learning. A parallel version-space learning algorithm based upon the principle of divide-and-conquer is proposed. Its time complexity is analyzed to be O(k log(2) n) with n processors, where n is the number of given training instances and k is a coefficient depending on application domains. For a bounded number of processors in the real situations, a modified parallel learning algorithm is then proposed. Experimental results are then performed on a real learning problem, showing our parallel learning algorithm works and being quite consistent with results of theoretic analysis. We have finally concluded that when the number of training instances is large, it is worth learning in parallel because of its faster execution.