Tzung-Pei Hong and Shian-Shyong Tseng+
Department of Information Management
Kaohsiung County, 840, Taiwan, R.O.C.
+ Institute of Computer and Information Science
National Chiao Tung University
Hsinchu, 300, Taiwan, R.O.C.
Among incremental learning strategies, the "version space" learning strategy is one of the most well known. This learning strategy is, however, applicable only to learning conjunctive concepts. When the concepts to be learned are in disjunctive form, the version space learning strategy returns a null version space that cannot correctly represent the desired concepts. In this paper, we present a modification of the original version space strategy that enables learning of disjunctive concepts. The new proposed version-space-based learning strategy, called the "primal-dual version-spaces" learning strategy, learns disjunctive concepts incrementally and without saving past training instances. The correctness of its underlying algorithm is analyzed and proven.
Keywords: version space, incremental learning, multiple version spaces, disjunctive concepts, primal version space, dual version space
Received May 15, 1996; revised September 26, 1997.
Communicated by Jieh Hsiang.
This is an expanded version of the paper entittled "Primal-dual version spaces" presented at the 1996 IEEE international conference on systems, man, and cybernetics, pp. 2145-2148.