Acquiring Knowledge by Efficient Query Learning
Proceedings of the Twelfth International Joint Conference on Artificial Intelligence. Learning Be Knowledge Acquisition. Pages 783-788.
© 1991 International Joint Conferences on Artificial Intelligence
Abstract
Membership queries extended with the meta query concept is proposed as a method to acquire complex classification rules. Furthermore, relevent concept classes, where a small number of queries is sufficient, are characterized. In this paper we advocate and present the benefits of the use of queries in order to learn a target concept efficiently. Thus providing the foundations for automating the knowledge acquisition process. Based on these results, we developed a knowledge acquisition tool KAC-Z which uses queries about specific domain objects. The systems usefulness has been demonstrated by its application in the domain of manufacturing (cutting) industry.
- D. Angluin. Queries and concept learning. Machine Learning, 2:319-342, 1988.
- A. Blumer, A. Ehrenfeucht, D. Haussler, and M. Warmuth. Classifying learnable geometric con- cepts with the Vapnik-Chervonenkis dimension . In Proc. 18th STOC, pp. 273-282, 1986.
- E. Feigenbaum. The art of artificial intelligence I. themes and case studies of knowledge engineering. In Proc. 5th IJCAI, pp. 1014-1029, 1977.
- B. R. Gaines. Knowledge acquisition: The conti- nuum linking machine learning and expertise trans- fer. In Proc. Eurpoean Knowledge Acquisition Workshop, 1989.
- A. G. Hoffmann. Unifying several learning situati- ons. In Proc. Workshop on Computational Learning Theory, pp. 415-416, 1988.
- A. G. Hoffmann . Types of efficient query learning. In Proc. 14th German Workshop on Artificial Intel- ligence, pp . 257-266, 1990.
- C. Sammut and R. Banerji. Learning concepts by asking questions. In R. S. Michalski, J. G. Carbo- nell, and Mitchell, T. M., ed., Machine Learning: An Artificial Intelligence Approach, vol. 2, pp. 167-191.
- V. N. Vapnik and A. Y. Chervonenkis. On the uni- form convergence of relative frequencies of events to their probabilities. Theory of Probability and its Ap- plications, 16(2):264-280, 1971.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
In building expert systems the knowledge acquisition is considered to be a bottleneck [3]. This is due to the fact that acquiring knowledge from an expert is generally time-consuming and error-prone. Thus, one is motiva ted to overcome this bottleneck by automating the kno wledge acquisition, i.e. through building learning com ponents for expert systems [4]. A successful learning component in an expert system will probably have to use queries directed towards the experts. For example, Sammut and Banerji's system [7] uses membership que ries about specific examples as part of its strategy for efficiently learning a target concept. Let us consider the problem of using queries in order to learn an unknown concept. For this purpose Angluin [1] suggested different types of queries. Among these query types are mem bership queries which ask for the correct classification of a particular object. Furthermore, she proved that for many concept classes an exhaustive or nearly exhaustive search is necessary when using membership queries. Ho wever, in [6] concept classes have been introduced where efficient learning via various queries is possible. In the present paper these concept classes are significantly ex tended by introducing the notion of meta queries. Meta Sunil Thakar Research Institute Berlin Daimler-Benz AG Alt-Moabit 91b D-1000 Berlin 21, Germany queries ask for hints how to construct complex classifi cation rules. By the use of meta queries combined with membership queries our system is in a position to learn concept classes for which otherwise an exhaustive search would be necessary. Based on this work we developed a knowledge acquisition system KAC-Z which exploits the theoretical results presented in this paper. To prove the applicability of our system in the real world we describe the application of KAC-Z in the domain of manufactu ring industry. KAC-Z will be used to acquire the know ledge of an expert which selects an appropriate cutting metal for a specific cutting process. This paper is or ganized as follows. In section 2 our theoretical results concerning efficient query learning are presented. Sec tion 3 describes the design of KAC-Z. The final section contains the conclusion.
2 Theoretical Foundations
We consider a set of objects X . The task of the learning system is to determine the class of each object in X, i.e. to determine for each object whether or not it belongs to the target concept. For this purpose, we assume a class of concepts C ~ 2x which underlies the learning system in the following sense. The learning system will classify the objects only according to one particular con cept c E C. The learning system L is allowed to ad dress membership queries to an oracle. A membership query means that L provides an arbitrary object 0 E X to the oracle. The answer of the oracle will be 'yes' or 'no' depending on whether 0 belongs to the target con cept or not. One simple but inefficient way of determi ning the correct class of all objects in X via membership queries is to present the description of each object in X to the oracle. Therefore, a trivial upper-bound for the required number of membership queries is lXI. Depen ding on the actual structure of the concept class C there may be clever query strategies which allow the learning system to determine the target concept with much less than lXI membership queries. This may be possible be cause the classification of most objects will be logically implied by the classification of some crucial objects in X . In this paper we investigate the structure of con cept classes which allow the learning system to use such clever query strategies in order to learn the target con cept efficiently, i.e. with a small number of queries. The following results are also applicable in the case of lear ning multiple classes instead of learning just one class as pointed out in [5] . In section 2.1 we define the property of a concept class being independently monotonic. This property allows to learn a concept from C with a small number of queries. As shown in Theorem 1 in section 2.2 by using the preceding Lemma which states an impor tant consequence of a concept class being independently monotonic. In section 2.3 we extend the definition of being independently monotonic to the property of being k-independently monotonic. Concept classes of this kind allow to avoid an exhaustive search if initially k positive examples of the target concept are given to the learning system. A corresponding upper bound is given in Theo rem 2 in section 2.3. In 2.4 the notion of meta queries is formalized .
2.1 Preliminaries
Let X be a finite set of objects, C ~ 2x be a set of concepts or a concept class. That means, C is a set of subsets of X with ICI > 1. Let c E C be an arbitrary concept of C. An object x E X is called a positive example of c iff x E c and a negative example of c iff x rf. c respectively. A concept c' is consistent with a positive (negative) example x of a concept c iff X E c' (X rf_ c').
The Vapnik-Chervonenkis dimension (8] was intro duced in the context of learning theory in (2]. A set s ~ X is said to be shattered by C iff { s n clc E C} = 2'. The Vapnik-Chervonenkis dimension of C, in short VC-Dim( C), is the cardinality of the greatest set s ~ X shattered by C. That means, the Vapnik-Chervonenkis dimension is given by
In the following, a class of concept classes is specified for which the Vapnik-Chervonenkis dimension can be used to give an upper-bound for the required number of mem bership queries.
Definition 1 Let C ~ 2x be a concept class and c an arbitrary concept in C . sEC is a minimal supercon cept of c iff c C s and there is no concept c' E C between c and s . I.e ., there is no c' E C such that c C c' C s holds.
Definition 2 A set of concepts I = {c1, ... , cm} is in dependent in C iff for all concepts c; E I there exists a fixed object x; E c; as follows: For the union U of each s·ubset I, ~ I of concepts in I there is a concept c E C such that U ~ c and for all concepts Cj E (I\ I,) c does not contain the corresponding object Xj. More formally: A set I = { c1, ... , cm} of concepts is independent in C ifJV(c; E I)3(x; E c;)V(I, ~ I)3(c, E C)((Uc.Ef. cr) ~ c, 1\ V(cj E (I\ I,)) (xi rf. c,)

Let C be the set of linear decision functions. A particular linear deci sion function can be viewed as a hy perplane in the n-dimensional euc- 5 lidean space En. In E 2 it is a line 4·. that partitions the plane into two parts. In the diagram, the positive 2 examples lie in the lower part. The 1 dotted lines indicate the only two minimal superconcepts of the con cept represented by the heavy line. smallest superconcepts of c.
Figure 1: Linear threshold functions are independently monotonic
Note: This also means if I is independent inC then there exists a set s ~ X of III objects shattered by C. The set s contains one appropriate object from each concept in I respectively. In particular, s = {x1, ... , xm}·
Example:
Let C { {},{1}, {2}, {3},{ 4},{1, 2}, {1, 3}, {2, 3} , {1,3},{2,3,4},{1,2,3,4}}. Let Io = {{1},{2},{3}}. Then 10 is independent in C since for any union of sets in 10 there exists a concept c E C that is disjoint with the remaining sets in Ia. In contrast to that, the set I1 = { {2}, {3}, {4}} is not independent in C. That is due to the fact that any concept c E C covering both sets {4} and {2} also contains the element '3'. Thus, there is no concept c E C such that ( {2} U { 4}) ~ c and the remaining set {3} E (h \ ({2} U {4})) contains an element not contained in c.
Definition 3 A concept class C is independently monotonic iff for all concepts c E C the set M(c) of minimal superconcepts of c in C is independent in C and the empty set is a concept in C as well.
Examples for relevant concept classes that are indepen dently monotonic follow:
Let the set of objects X be the set of all attribute-value Yectors (vl,v2, ... ,Vn-l,vn} where v; E {1, ... j} ViE {1, ... , n}.
- Onesided conjuntive threshold functions: Let C be the set of all functions f of the following kind:
For C representing the set of onesided-conjuntive threshold functions holds VC-Dim(C)=n.

Let C be the set of ortho- a2 gonal rectangles. Then, by C being 1-independent/y monotonic is meant that for an arbitrary rectangle, given a point p within that rectangle we can expand or not expand it in all four di rections independently.
Figure 2: A geometrical example for a concept class being 1-independently monotonic
- Linear decision functions: Let C be the set of all functions f of the following kind:
For C representing the set of linear decision func tions holds VC-Dim(C)=n.
See Figure 1.
As the examples indicate, concept classes that do notre quire exhaustive searches have to be rather simple struc tured. That kind of being rather simple structured is reflected by the property of being independently mono tonic.
For the proof of the following Lemma the next definition is still required.
Definition 4 An object 0 E X dominates an object o E X in C iff o is contained in all concepts of C in which 0 is contained. That is, iff the membership of 0 in the unknown target concept Ct E C implies the membership ofoinct.
Example: Let X = { d, e,!} and C = { c1 {d,e,f},c2 = {d,e},ca = {f},c4 = {e},cs = {}}. In this example the object 'd' dominates the object 'e' in C. The reason for this is that all concepts in C which contain 'd' contain the object 'e' as well. On the other hand, the object'!' does not dominate the object 'e' be cause there is a concept c3 E C which does not contain 'e' while it is containing 'f'.
2.2 The upper-bound
For the following Theorems the Lemma below is used, which exhibits an important property of independently monotonic concept classes.
Lemma Any independently monotonic concept class C ~ 2x has the following property: There are VC Dim( C) = d disjoint subsets s1 , ... , sd such that each of these subsets is linearly ordered by the dominance rela tion in the concept class C. Furthermore, determining the objects in s1, ... , sd being positive or negative exam ples of an unknown target concept Ct E C leaves only a single concept c' E C consistent with the classified objects in s1 , ... , sd. That means, c' = Ct.
Proof: We prove the Lemma by contradiction.
Assumption: There is a set s = { x 1 , ... , x d+ 1} of more than VC-Dim(C) objects in X such that none of these objects is dominating another object of s in C. An ob ject x not dominating another object y means that x and y belong to different concepts Cx and cy. I.e. x and y belong to different superconcepts of the empty set such that neither Cx is a superconcept of cy nor vice versa. Let be c1, ... , cd+1 the corresponding concepts to which the objects in s belong respectively, such that none of these concepts is a superconcept of another one. For c, being a nonminimal superconcept of a concept c me ans, there are concepts between c and c, in the manner c C c·' C c·" C ... C c'* C c,, i.e. there is a minimal su perconcept c·' of c between c and c,. Since the set M (c) of minimal superconcepts of a concept c E C is indepen dent by definition, the minimal superconcept c·' of c has in turn minimal superconcepts coverin? exactly one of the minimal superconcepts of M(c) \ c· . This property holds for all concepts between c and c, such that it also holds for the concept c·· of which c, is a minimal su perconcept. If the concepts c1, ... , cd+1 do not dominate each other in C and there is a concept Cm E C such that c1, ... , Cd+l are all minimal superconcepts of Cm. That is due to the fact that c1, ... , cd+1 all are superconcepts of the empty set contained in C. However, Cm can be constructed by executing the following procedure using a variable 'current concept' cc:
endfor;
After executing this procedure all superconcepts c1, ... , cd+1 must be minimal superconcepts of Cc since c1, ... , cd+1 are not dominating each other in C. But this is a contradiction to the definition of C being indepen dently monotonic.
0
That situation can be illustrated in the geometrical ex ample given in Figure 1 above. In Figure 1 for each dimension there exists a set 0 of objects along the axes a1 and a2 which are linearly ordered according to the dominance relation in C. That means, all points on the axes in the dashed area are positive examples of c while all remaining points in 0 are negative examples of c. The upper-bound Theorem follows:
| ,-2 | i • | J 10 | J 100 | J 1000 | J 65535 | |
|---|---|---|---|---|---|---|
| n 1 | 3 ."2 | 4 .0. | .64 | 10 .97 | 16.99 | |
| n 2 | 4 | 9.~9 | 13 . ~9 | 26 . .58 | 39.86 | 63 .99 |
| n • | 18 .39 | .51 .44 | 76 .44 | 15 9 .49 | 24~ . .53 | 393.39 |
| n-1 | 6. 8 | 208 . | 8 . | 641.1 | 9'-".:36 | 1.5 6 . 8 |
| n 30 | 7 8 2.8 | 1972 .53 | 2872 . .53 | .5862 .26 | 88.51.99 | 14282 .77 |
| n-100 | 9 4 3.5. 6 | 22654 .9 | 32654.9 | 658 4 .18 | 990>3 .46 | 159335 .4 |
Theorem 1 Let X be a set of objects, C ~ 2x, ICI > 1 be an independently monotonic concept class and d = VC-Dim(C) . Then there is a learning algorithm which learns from membership queries only that requires at most
membership queries in order to determine the correct tar get concept c E C .
Proof: In the Lemma it has been shown that for any in dependently monotonic concept class C there are at most d subsets s1 , . . . , sd of X where each of those subsets can be linearly ordered by the dominance relation in C. That means, for an arbitrary concept c E C the first k;(c) EN elements of a subset s; are positive while the remaining objects in s; are negative examples of c. Furthermore, determining the objects of these subsets to be positive or negative examples of the unknown target concept Ct means, determining exactly one concept c E C. In other words, there is only one concept in C consistent with the determined positive and negative examples. These subsets are linearly ordered by the dominance relation in C. Therefore, a binary search procedure is executa ble on each of these subsets s1 , . . . , Sd to find out which objects are positive examples and which ones are nega tive examples of c, . Hence, in each of the d linearly ordered subsets s1 , . . . , sd of X a binary search for the most objects in s; dominating positive example p can be executed. For this binary search procedure there are at most (log2 isd) + 1 queries necessary. Thus, the greatest number of queries will be required if all d subsets have the same cardinality. Therefore, an upper bound for the number of required queries is d(1 + log2 J.¥ ).
0
For illustration, Theorem 1 can be applied to both of the given examples for independently monotonic concept classes: As already noted, the VC-Dim(C) for C repre senting either the set of linear decision functions or the set of onesided conjuntive threshold functions, is given by the length n of the attribute-value vector of the set of objects X . Moreover, the size of the set X is given by jn . Thus Theorem 1 states the following upper bounds for the number of required membership queries.
2.3 Providing hints
Suppose X= {1, .. . , m} and the concept class C con tains all singletons of X, i.e. all sets which cover only a single object in X. In this case, there is a worst case lower bound on the required number of membership que ries of m- 1. I.e., a (nearly) exhaustive search is neces sary. (See [1] for proofs oflower bounds for various types of queries.) Nevertheless, in certain cases the number of required membership queries can be reduced dramati cally if initially the learning system is provided with one positive example of the target concept Ct. Think of X being the set of coordinates in a grid based plane. That is, X= {(0, 0), (0, 1), ... , (m-1, m-1)} and C being the set of all orthogonal rectangles in this grid based plane. In that case, C includes among other sets all singleton sets of X. Thus, a lower bound for required membership queries is m 2 - 1. For illustration, see Figure 2.
Assume, one gets an arbitrary positive example p of the target concept Ct and the concept class C is purged from all concepts not consistent with p. Then, the remaining concept class C' is independently monotonic. Thus, only d(1 + ~) with d = VC-Dim(C) membership queries are necessary in order to determine the target concept Ct . This observation can be generalized by characterizing the appropriate concept classes through the following de finition:
Definition 5 A concept class C over a set of objects X is k-independently monotonic iff for all objects x E X there is a concept c E C covering x and lei :S k and the set M(c) of minimal superconcepts of c in C is independent in C.
Now, the next Theorem can be formulated:
Theorem 2 Let X be a set of objects, C ~ 2x, ICI > 1 be a k-independently monotonic set of concepts and d = VC-Dim(C) . Then, after initially providing the lear ning system with k different positive examples of the tar get concept Ct there is a learning algorithm which needs at most d(1 + log 2 ~) membership queries in order to determine the correct target concept Ct E C.
Proof: Let s = {x!t ... , Xk} be the set of objects given as positive examples of the concept Ct. By definition of C being k-independently monotonic there is a concept c E C such that c ~ s. Let C' be the remaining concept class after removing all concepts in C not covering c. Thus, there is a reduced concept class C' over a reduced set of objects X' = (X \ c). Especially, C' contains an empty set , i.e. the original concept c after removing the objects of c from X . And by definition of C being k-independently monotonic C' over X' is independently monotonic and Theorem 1 can be applied to the reduced concept class C'.
0
Example: We follow Figure 2, where C is the set of all orthogonal rectangles in a grid based finite plane. In the generalized case of an n-dimensional euclidean space, Theorem 2 can be used to upper bound the number of membership queries required for this generalized concept class C: There is VC-Dim(C)=2n and lXI = jn where j is the number of gridpoints along each dimension. Then Theorem 2 says that at most 2n(l + n log 2 j - log2 2n) membership queries are necessary in order to determine the target concept c E C after initially getting one positive example of the target concept.
2.4 Meta queries
We give just a formal and general description of our no tion of meta queries. The idea is illustrated in section 3.
Definition 6 Let C ~ 2x be a concept class on X . Then, a meta query is a specified subset Xs ~ X. The answer to the meta query is 'no' if the corrsepon ding reduced concept class Cs = {c n Xslc E C} on Xs is !-independently monotonic. Otherwise, the answer is a set XM = {X1, ... ,Xn} of mutually disjoint subsets of Xs. Each subset in XM is required to contain at least one positive example of the target concept.
I.e. each supplied subset in XM either has to be ! independently monotonic or it has to have the potential to become splitted into multiple subsets- such that each subset is !-independently monotonic. Here, the user or expert is asked to provide sets of subsets in a way that the number of subsequent meta queries by the system is minimized.
3 Knowledge Acquisition System KAC-Z
In this section we describe .our Knowledge Acquisition System (KAC-Z) which incorporates the theoretical re sults described in the previous section. An application of KAC-Z in a real world (manufacturing industry) pro blem situation is being described as well.
3.1 System Design
The goal of this system is to acquire knowledge in or der to perform a classification task. For this purpose KAC-Z makes use of goal-directed queries. In particu lar, membership queries are used. As pointed out in section 2.3 learning disjunctive concepts usually require a vast number of membership queries. This poses a dif ficult problem, because no expert is ready to answer a vast number of queries. In order to overcome this pro blem we use in KAC-Z a new query type called meta queries. Meta queries were used to tackle the problem of learning intervals within disjunctive classification. The problem is illustrated in Figure 3.
In the geometrical example (Figure 3) the task is to learn two rectangles r1, r2. Assume, our positive example is point P2· Then the left boundary could easily be misjud ged by the binary search. Reason being that the binary search may produce a membership query for p1 .

| A B c | 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 |
| D | |
| f(A,B,C,D) | 1 1 0 0 0 0 0 0 1 1 0 0 0 1 1 1 |
The answer to that would indicate that p1 is a positive example, which would mean that the left boundary of rectangle r2 containing P2 lies at the left of p1. In fact the binary search procedure would yield to the dashed rectangle r3 as learning result. One generally cannot avoid this by using membership queries only, except one uses an exhaustive search. This leads us to the idea of using yet another type of query which we call meta query. Answers to these queries determine whether there are disjunctive terms in the classification rule and whether a binary search can be applied or not. The idea of meta queries is to provide the system KAC-Z with the bran ching structure of the classification rule tree (Figure 4). Consider an example with learning a disjunctive boolean function f as given in Table 2.
The boolean fu~ctions 11 and h reflect two different tree structures even though both functions are logically equivalent. A branch in the tree represents a disjunction in the corresponding boolean functions . The terminal nodes correspond to a conjunction (eventually intervals) of the remaining attributes. For each of the intermediate nodes the expert is requested to point out the disjunc tions (branching) via a corresponding meta query. As can be seen in Figure 4, the tree structure depends upon the order of disjunctions given by the expert. The sy stem starts with a meta query for the root node. The expert's answer has to indicate whether disjunctive ex pressions are involved in the function to learn. If yes, the expert has to provide an attribute along with at least two disjoint attribute value sets. The given sets are assumed to constitute a relevant and meaningful dicho tomy (polychotomy). In Figure 4 the attribute for the root node would be A respectively B. The attribute va lue sets would be '0' and '1' respectively. In going on, for each emerging node the system uses a further meta query. If the answer indicates that there is no disjunctive structure within the remaining attribute-values, then the node is a terminal node.

We use a frame like description for the objects whose classification should be learnt as shown in section 2. I.e. slot value intervals are efficiently learnt via membership queries . In order to do that, for each interval an upper and a lower bound with the help of a binary search has to be found. For each attribute an initial value which lies within the interval is required. Thus, all required initial values are supplied by an arbitrary single positive example.
Note: The case of irrelevant attributes is included simply if the whole of its value range is recognized as valid.
3.2 Application
KAC-Z is intended to be used in the manufacturing industry. Its goal is to acquire the knowledge for de termining appropriate cutting metals for specific cutting operations. Currently this job is performed by a long time experienced expert from the fixture design depart ment. An example of a classification rule tree for our application, where the expert defines a hierarchy of the materials being used in the specific cutting process is shown in Figure 5. In the example above there are non boolean attributes. In this case similar to boolean attri butes multiple-value sets as well as single-value sets can be assigned to a particular branch.
4 Conclusion
The introduced notion of meta queries turned out to be very valuable for acquiring complex knowledge structu res. Our meta queries appear to have overcome the pro blem of exhaustive search for learning complex concept classes via membership queries. Based on our theoretical results KAC-Z acquires knowledge in the manufacturing domain. However, in future further types of queries will be considered in order to examine their usefulness for supporting the knowledge acquisition.

@inproceedings{ijcai1991p115,
title = {Acquiring Knowledge by Efficient Query Learning},
author = {Hoffmann, Achim G. and Thakar, Sunil},
booktitle = {Proceedings of the Twelfth International Joint Conference on
Artificial Intelligence, {IJCAI-91}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {John Mylopoulos and Ray Reiter},
pages = {783--788},
year = {1991},
month = {8},
note = {Learning Be Knowledge Acquisition},
url = {https://ijcai.org/proceedings/1991/115},
}
TY - CPAPER TI - Acquiring Knowledge by Efficient Query Learning AU - Hoffmann, Achim G. AU - Thakar, Sunil T2 - Proceedings of the Twelfth International Joint Conference on Artificial Intelligence, IJCAI-91 PB - International Joint Conferences on Artificial Intelligence PY - 1991 SP - 783 EP - 788 UR - https://ijcai.org/proceedings/1991/115 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: