On approximately identifying concept classes in the limit

In this paper, we introduce various kinds of approximations of a concept and propose a framework of approximate learning in case that a target concept could be outside the hypothesis space. We present some char­acterization theorems for approximately identifiability. In particular, we show a remarkable result that the upper-best approximate identifiability from com­plete data is collapsed into the upper-best approximate identifiability from positive data. Further, some other characterizations for approximate identifi­ability from positive data are presented, where we establish a relationship be­tween approximate identifiability and some important notions in quasi-order theory and topology theory. The results obtained in this paper are essentially related to the closure property of concept classes under infinite intersections (or infinite unions). We also show that there exist some interesting example concept classes with such properties (including specialized EFS’s) by which an upper-best approximation of any concept can be identifiable in the limit from positive data.