Andreas Birkendorf, Norbert Klasner, Christian Kuhlmann, Hans Ulrich Simon:

Structural Results about Exact Learning with Unspecified Attribute Values

This paper deals with the UAV learning model of Goldman, Kwek and Scott [GKS97]. (``UAV'' is the acronym for ``Unspecified Attribute Values''.) As in [GKS97], we consider exact learning within the UAV framework, where the learner has to exactly identify an unknown target concept by means of UAV membership (UAV-MQs) and/or UAV equivalence queries (UAV-EQs or UAV-ARB-EQs, respectively). A smooth transition between exact learning in the UAV setting and standard exact learning is obtained by putting a fixed bound $r$ on the number of unspecified attribute values per instance. For $r=0$, we obtain the standard model. For $r=n$ (the total number of attributes), we obtain the (unrestricted) UAV model. Between these extremes, we find the hierarchies $(UAV-MQ_r)_{0 \leq r \leq n}$, $(UAV-EQ_r)_{0 \leq r \leq n}$, and $(UAV-ARB-EQ_r)_{0\leq r \leq n}$.

Our main results are as follows. We present lower bounds on the number of UAV-ARB-EQs and UAV-MQs in terms of the Vapnik Chervonenkis dimension of the concept class. We show furthermore that a natural extension of Angluin's Sunflower Lemma [Ang88] is still applicable in the exact UAV learning model. Our UAV Sunflower Lemma allows to establish exponentially large lower bounds on the number of UAV-MQs needed to achieve exact identification of Boolean concepts from the following classes: monotone DNF, read-twice DNF, $O(n)$-term DNF and 2-decision lists. This is contrasted by our positive learning results, where efficient UAV-MQ learning algorithms for read-once DNF, constant-term DNF and $1$-decision lists are presented (in addition to some other positive learning results). Finally, we determine the inherent structure of the aforementioned three hierarchies and the relations between them. It turns out that query type $UAV-EQ_{r-1}$ is strictly stronger than $UAV-EQ_r$ (for each constant $r$). The analogous result for UAV-ARB-EQ is valid. Furthermore, $UAV-MQ_{r+\omega(\log n)}$ is strictly stronger than $UAV-MQ_r$. As for the relations between two query types from different hierarchies, we can always tell whether they are equivalent, or independent, or whether one is strictly stronger than the other. (For instance, each query type from the UAV-MQ hierarchy is incomparable to each query type from the UAV-EQ hierarchy.) We also compare two collections of query types (though in a less systematic fashion).


Last update: 11/17/98. Norbert Klasner, klasner@lmi.ruhr-uni-bochum.de.

Return to list of my publications.