Lehrstuhl Mathematik & InformatikStructural Results about Exact Learning with Unspecified Attribute Values
Abstract. This paper deals with the UAV learning model of
Goldman, Kwek and Scott [7], where "UAV" is the acronym for "Unspecified
Attribute Values". As in [7], 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 Chervonenkis dimension
of the concept class. We show furthermore that a natural extension of Angluin's
Sunflower Lemma [1] is still applicable in the exact UAV learning model.
Our UAV Sunflower Lemma allows to establish exponentially large
lower bounds on the necessary number 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 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-EQr+\omega
(log n) is strictly stronger than UAV-MQr .
We also determine the relation between query types chosen from different
hierarchies.
References:
[1] D. Angluin, Queries and concept learning,
in "Machine Learning", 2(4):319-342, 1988.
[7] S. A. Goldman, S. Kwek, S. D. Scott, Learning
from examples with unspecified attribute values,
in "Proceedings of
the 10th Annual Conference on Computational Learning Theory", pages 231-242,
ACM Press, New York,
1997.