05.12.2008

A learning machine (see [9]) consists of a learning protocol together with a deduction procedure. Learning protocol specifies the manner in which information about the concepts is obtained from the outside. Deduction procedure is the mechanism by which a correct recognition algorithm for all concepts to be learned is deduced. There are m concepts to be learned. They are represented as terms in a probabilistic DNF form. The goal of this paper is to propose an efficient parallel algorithm on a PRAM (see [2]) for learning these concepts with a minimal error. Information about them comes from three types of queries: equivalence, membership and probabilistic queries. There is a threshold k describing the maximal number of conjuncts allowed in the final descriptions of concepts produced by a learning machine. It can happen that the descriptions known by the teacher contain more conjuncts per concept than k. The goal of the first step of our deduction procedure is to learn descriptions of concepts in the form known by the teacher. We apply here a generalization of a strategy proposed by Angluin (see [1]). In the second step, we apply the strategy which is similar to the one proposed by Ras and Zemankova (see [7]). This way we minimize the number of conjuncts in the descriptions of concepts by taking the advantage of a growing language. The error learning after these two steps is equal to zero. The last step is based on merging two closest conjuncts in one of the terms (in DNF) representing the current outcome of the deduction procedure. This step is repeated until there is no term in DNF (describing one of the concepts to be learned) which contains more conjuncts than the threshold k. The final output of the learning machine is a collection of optimized concepts descriptions in terms of a growing language.