Structural Results about Exact Learning with Unspecified Attribute Values
This paper deals with the UAV learning model of Goldman, Kwek and Scott [GKS], where
"UAV" is the acronym for "Unspecified Attribute Values". As in [GKS], we consider exact
learning within the UAV framework. 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-MQr)0<=r<=n, (UAV-EQr)0<=r<=n and
(UAV-ARB-EQr)0<=r<=n.
Our main results are as follows. We present various lower bounds on the number of ARB-EQs and
UAV-MQs in terms of the Vapnik Chevonenkis dimension of the concept class. We show
furthermore that a natural extension of Angluin's Sunflower Lemma is still applicable in the exact
UAV learning model. Our UAV Sunflower Lemma allows the establishment of
exponentially large lower bounds on the necesary numbert of UAV-MQs for several popular
concept classes. On the other hand, we can show that slight simplifications of these classes are
efficiently learnable using only a few UAV-MQs. Finally, we investigate the inherent
structure of the aforementioned three hierarchies and the relations between them, it turns out that
query type UAV-EQr-1
is strictly stronger than UAV-EQr
(for each constant r). The analogous result for UAV-ARB-EQ is valid. Furthermore,
UAV-MQr+w(log n) is strictly stronger than
UAV-MQr. We also determine the relation between query types chosen
from different hierarchies.