This content was uploaded by our users and we assume good faith they have the permission to share this book. If you own the copyright to this book and it is wrongfully on our website, we offer a simple DMCA procedure to remove your content from our site. Start by pressing the button below!
where p and ~ are respectively a referent specialization operator and a coreference partition operator on G, and tp is a substitution for annotation variables in G. The answer is said to be correct iff tp is a solution for C G and every annotation variable-flee instance of p~tpQ G is a logical consequence of P. The following definition of FCG unification is modified from the one in 4 with the introduction o f FCGP annotation terms and constraints on them. As defined in 4, a VAR generic marker is one whose concept occurs in an FCGP query, or in the body of an FCGP rule, or in the head of an FCGP rule and coreferenced with a concept in the body of the rule; a NON-VAR generic marker is one whose concept occurs in an FCGP fact, or in the head of an FCGP rule but are not coreferenced with any concept in the body of the rule.
Definition 4. 7 Let u and v be finite normal FCGs. An FCG unification from u to v is a mapping 0: u --->v such that: 1. V c e V C : type(c) is matchable to type(Oc) and referent-unified(c, Oc), and 2. V r e V R : type(r) is matchable to type(Or), and 'Vie { 1, 2 ..... arity(r) } : neighbor(Or, i) = Oneighbor(r, i), and 3. No VAR generic maker is unified with different individual markers or noncoreferenced NON-VARgeneric markers. The constraint produced by 0 is denoted by C O and defined by the set {aval(c)
aval(Oc) I c e V c , and c is a fuzzy attribute concept}u{type(c) <~ type(Oc) I ceVc,}~{type(r)
are respec-
Note that, in Definition 4.7, if aval(c) is of the form lub{cs 1, ~2 ..... Gin}, where t~i's are simple FCGP annotation terms, then the constraint lub{t~l, t~ ..... ~m} -
280
Definition 4.8 Let G be an FCGP goal QG I1 CG and C be an FCGP reductant if u then v (G and C have no variables in common). Suppose that there exists an FCG unification 0 from a normalized sub-graph g of QG to v. Then, the corresponding resolvent of G and C is a new FCGP goal denoted by Ro(G,C) and defined to be P0~0~50QG u II C0 & CG, where 80 deletes g from QG-
Property 4.3 Let G and C be respectively an FCGP goal and an FCGP reductant. If G is a normal FCGP goal, then any resolvent of G and C is also a normal FCGP goal.
Proof The proof is similar to the proofs for the alike properties of annotated logic programs (Lemma 2 in 20) and AFLPs (Property 4.3 in 7). Note that the order of the inequalities in C o is not significant, but the order of C o and C G in Definition 4.8 is.
Definition 4.9 Let P be an FCGP and G be an FCGP goal. A refutation of G and P is a finite sequence G
Example 4.3 Let P be the program in Example 4.1 and G be the following FCGP goal querying "Which product has a moderate price and what is its quality like?": PRODUCT: *x --->(ATTR2)=~PRICE: @moderate ---->(ATTR3)~ QUALITY: @X Assuming the relations between the linguistic labels in P and G as in Example 4.2, a refutation of G and P can be constructed as follows: go = PRODUCT:*x--->(ATTR2)~PRICE:@m~ (a sub-graph of QG) C 1 = if PRODUCT:*y--->(ATTR1)=~DEMAND: @tub{not high+~, not low+ql} (u) then PRODUCT: *y--~(ATTR2):=*,PRICE: @ lub {not expensive+ G, not cheap+ql } (v ) 01: go --->v, p01 = { }, ~ol = { {PRODUCT:*x, PRODUCT:*y } } G 1 = PRODUCT: *y---)(ATTR 1)==~DEMAND: @lub{not high+~, not low+ql} -->(AT'rR3)~ QUALITY: @X II (moderate
II (lub{not high+ G, not low+q1} <-tnormal) & (moderate -
281
c3--c: 03: QG 2 ---) C3, P03 = { }, 1~03= { } G3 = II (X
(moderate
II (X st quite good) & (not high+~ ~ normal) & (not low+W -
As in Example 4.2, one has X = quite good and ~ = W = 0 as a solution for the constraint above, whence the corresponding answer for G w.r.t. P is <{(PRODUCT:*X, #2) }, { }, {X/quite good}>. Note that, if a clause rather than a reductant of P were used to resolve go, there would not be a refutation of G and P because, generally, neither moderate -
is applied when gl is deleted from QG 1.
The following theorems state the soundness and the completeness of this FCGP proof procedure. Due to space limitation we omit the proofs for these theorems, which were presented in the submitted version of this paper.
Theorem 4.4 (Soundness) Let P be an FCGP and G be an FCGP goal. If G
Theorem 4.5 (Completeness) Let P be an FCGP and G be a normal FCGP goal. If there exists a correct answer for G w.r.t. P, then there exists a refutation of G and P. 4.4. Remarks A crisp attribute-value is a special fuzzy one defined by a fuzzy set whose membership function only has values 0 or 1. A basic type is a special fuzzy one whose fuzzy truth-value is absolutely true. So, a CG can be considered as a special FCG and a CGP as a special FCGP with all nodes in each of its rules being firm nodes. We now give remarks on proof procedures for both FCGPs and CGPs from the viewpoint of lattice-based reasoning. For discussion, let us consider the following CGP as a special FCGP: if PERSON: *X--)(WORK_FOR)--)PERSON: * then EMPLOYEE: *x if PERSON: *y--~(ATTEND)--~UNIVERSITY: * then STUDENT: *y PERSON: John----Y(WORK FOR)---)PERSON: * --)(ATrEND)--->UNIVERSITY: Queensland PERSON: John---)(BROTHER OF)---)GIRL: Mary where the first rule says "A person is an employee if working for another", the second rule says "A person is a student if attending a university", the first fact says "John works for some person and attends university Queensland", and the second fact says "John is a brother of Mary". Note the rules in this CGP, where two coreferenced concepts occur in the body
282
and the head of a rule with two different concept types. These rules realize a close coupling between the concept type hierarchy and the axiomatic part of a knowledge base (3, 4). A backward chaining proof procedure based on clause selection like the ones in 15, 28, 4 is not complete when such rules are present or facts are not in CG normal form. For example, it cannot satisfy the goal EMPLOYEE-STUDENT" John where EMPLOYEE-STUDENT= lub{EMPLOYEE,STUDENT}, because it does not combine rule-defined concept types of an individual, which are EMPLOYEE and STUDENTin this case. Meanwhile, CG normal form is required to combine fact-defined concept types of an individual. Such combinations are inherent in a forward chaining method (cf. 28, 19). Actually, the significance of FCGP reductants is to combine concept types as well as other lattice-based data for backward chaining. In this example, a reductant of the CGP is: if PERSON: *X-->(WORK_FOR)-->PERSON: * then EMPLOYEE-STUDENT: *x ---9(ATTEND)-->UNIVERSITY: * which together with the first fact resolve the goal EMPLOYEE-STUDENT: John. Moreover, in the light of annotated logic programming (20, 7), types have been viewed as annotations which can also be queried about. This then reveals an advantage of CG notation that makes this view possible, which has not been addressed in the previous works on CGPs/FCGPs (15, 28, 4, 19). With classical first-order logic notation, this view is hindered due to types being encoded in predicate symbols, whence queries about sorts of objects or relations among objects have not been thought about (cf. 1, 3). For example, the following CG query asks "What is John and what is John's relation with Mary?": X: John--->(Y)---->PERSON: Mary where X is a concept type variable and Y is a relation type variable. Applying the presented FCGP proof procedure, one obtains X = EMPLOYEE-STUDENT and Y = BROTHER_OF, which say "John is an employee and a student, and John is a brother of Mary", as the most informative answer w.r.t, the given CGP.
5. Conclusions The syntax of FCGPs with the introduction of fuzzy types has been presented, providing unified structure and treatment for both FCGPs and CGPs. The general declarative semantics of FCGPs based on the notion of ideal FCGs has been defined, ensuring finite proofs of logical consequences of programs. The fixpoint semantics of FCGPs has been studied as the bridge between their declarative and procedural semantics. Then, a new SLD-style proof procedure for FCGPs has been developed and proved to be sound and complete w.r.t, their declarative semantics. The two main new points in the presented FCGP proof procedure are that, it selects reductants rather than clauses of an FCGP in resolution steps and involves solving constraints on fuzzy value terms. As it has been analysed, a CGP/FCGP SLD-style proof procedure based on clause selection is not generally complete. The constraint solving supports more expressive queries which are possibly about not only fuzzy attribute-values but also fuzzy types. Since a CGP can be considered as a special FCGP, the results obtained here for
283
F C G P s could be applied to C G P systems. They could also be useful for any extension that adds to CGs lattice-based annotations to enhance their knowledge representation and reasoning power. The presented F C G P system, on one hand, extends C G P s to deal with vague and imprecise information pervading the real world as reflected in natural languages. On the other hand, to our knowledge, it is the first fuzzy order-sorted logic programming system for handling uncertainty about types o f objects. W h e n only fuzzy sets o f special cases are involved, F C G P s could become possibilistic CGPs, where concept and relation nodes in a C G are weighted by only values in 0,1 interpreted as necessity degrees. They are less expressive than general F C G P s but have simpler computation and are still very useful for CG-based systems dealing with uncertainty. Besides, F C G P s could be extended further to represent and reason with other kinds of uncertain knowledge, such as imprecise temporal information or vague generalized quantifiers. These are among the topics that are currently being investigated. A c k n o w l e d g m e n t . We would like to thank Marie-Laure Mugnier and the anonymous referees for the comments that help us to revise the paper for its readability. References 1. Ait-Kaci, H. & Nasr, R. (1986), Login: A Logic Programming Language with Built-In Inheritance. J. of Logic Programming, 3: 185-215. 2. Baldwin, J.E & Martin, T.P. & Pilsworth, B.W. (1995), Fril - Fuzzy and Evidential Reasoning in Artificial Intelligence. John Wiley & Sons, New York. 3. Beierle, C. & Hedtstuck, U. & Pletat, U. & Schmitt, P.H. & Siekrnann, J. (1992), An Order-Sorted Logicfor Knowledge Representation Systems. J. of Artificial Intelligence, 55: 149-191. 4. Cao, T.H. & Creasy, P.N. & Wuwongse, V. (1997), Fuzzy Unification and Resolution Proof Procedure for Fuzzy Conceptual Graph Programs. In Lukose, D. et al. (Eds.): Conceptual Structures - Fulfilling Peirce's Dream, LNAI No. 1257, Springer-Verlag, pp. 386-400. 5. Cao, T.H. & Creasy, P.N. & Wuwongse, V. (1997), Fuzzy Types and Their Lattices. In Proc. of the 6th IEEE International Conference on Fuzzy Systems, pp. 805-812. 6. Cao, T.H. & Creasy, P.N. (1997), Universal Marker and Functional Relation: Semantics and Operations. In Lukose, D. et al. (Eds.): Conceptual Structures - Fulfilling Peirce's Dream, LNAI No. 1257, Springer-Verlag, pp. 416-430. 7. Cao, T.H. (1997), Annotated Fuzzy Logic Programs. Int. J. of Fuzzy Sets and Systems. To appear. 8. Cao, T.H & Creasy, P.N. (1997), Fuzzy Conceptual Graph Programs and Their Fixpoint Semantics. Tech. Report No. 424, Department of CS&EE, University of Queensland. 9. Cao, T.H. (1998), Annotated Fuzzy Logic Programsfor Soft Computing. In Proc. of the 2nd International Conference on Computational Intelligence and Multimedia Applications, World Scientific, pp. 459-464. 10. Carpenter, B. (1992), The Logic of Typed Feature Structures with Applications to Unification Grammars, Logic Programs and Constraint Resolution. Cambridge University Press. 11. Chevallet, J-P. (1992), Un ModUle Logique de Recherche d'Informations Appliqud au Formalisme des Graphes Conceptuels. Le Prototype ELEN et Son Expdrimentation sur un Corpus de Composants Logiciels. PhD Thesis, Universit6 Joseph Fourier. 12. Dubois, D. & Lang, J. & Prade, H., (1994) PossibilisticLogic. In Gabbay, D.M. et al. (Eds.): Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 3, Oxford University Press, pp. 439-514. 13. Genest, D. & Chein, M. (1997), An Experiment in Document Retrieval Using Conceptual Graphs. In Lukose, D. et al. (Eds.): Conceptual Structures - Fulfilling Peirce's Dream, LNAI No. 1257, Springer-Verlag, pp. 489-504. 14. Ghosh, B.C. & Wuwongse, V. (1995), Conceptual Graph Programs and Their Declarative Semantics. IEICE Trans. on Information and Systems, Vol. E78-D, No. 9, pp. 1208-1217.
284
15. Ghosh, B.C. (1996), Conceptual Graph Language - A Language of Logic and Information in Conceptual Structures. PhD Thesis, Asian Institute of Technology. 16. Gr~itzer, G. (1978), GeneralLattice Theory. Academic Press, New York. 17. Ho, K.H.L. (1994), Learning Fuzzy Concepts By Examples with Fuzzy Conceptual Graphs. In Proc. of the 1st. Australian Conceptual Structures Workshop. 18. Hopcroft, J.E. & Ullman, J.D. (1979), Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Massachusetts. 19. Kerdiles, G. & Salvat, E. (1997), A Sound and Complete CG Proof Procedure Combining Projections with Analytic Tableaux. In Lukose, D. et al. (Eds.): Conceptual Structures - Fulfilling Peirce's Dream, LNAI No. 1257, Springer-Verlag, pp. 371-385. 20. Kifer, M. & Subrahmanian, V.S. (1992), Theory of Generalized Annotated Logic Programming and Its Applications. J. of Logic Programming, 12: 335-367. 21. Klawonn, F. (1995), Prolog Extensions to Many-Valued Logics. In H/Shle, U. & Klement, E.P. (Eds.): Non-Classical Logics and Their Applications to Fuzzy Subsets, Kluwer Academic Publishers, Dordrecht, pp. 271-289. 22. Lloyd, J.W. (1987), Foundations of Logic Programming. Springer-Verlag, Berlin. 23. Magrez, P. & Smets, P. (1989), Fuzzy Modus Ponens: A New Model Suitable for Applications in Knowledge-Based Systems. Int. J. of Intelligent Systems, 4: 181-200. 24. Mineau, G.W. (1994), Views, Mappings and Functions: Essential Definitions to the Conceptual Graph Theory. In Tepfenhart, W.M. & Dick, J.P. & Sowa, J.F. (Eds.): Conceptual Structures Current Practices, LNAI No. 835, Springer-Verlag, pp. 160-174. 25. Morton, S. (1987), Conceptual Graphs and Fuzziness in Artificial Intelligence. PhD Thesis, University of Bristol. 26. Mukaidono, M. & Shen, Z. & Ding, L. (1989), Fundamentals of Fuzzy Prolog. Int. J. of Approximate Reasoning, 3: 179-194. 27. Myaeng, S.H. & Khoo, C. (1993), On Uncertainty Handling in Plausible Reasoning with Conceptual Graphs. In Pfeiffer, H.D. & Nagle, T.E. (Eds.): Conceptual Structures - Theory and Implementation, LNAI No. 754, Springer-Verlag, pp. 137-147. 28. Salvat, E. & Mugnier, M.L. (1996), Sound and Complete Forward and Backward Chainings of Graph Rules. In Eklund, P.W. & Ellis, G. & Mann, G. (Eds.): Conceptual Structures - Knowledge Representation as Interlingua, LNAI No. 1115, Springer-Verlag, pp. 248-262. 29. Sowa, J.E (1984), Conceptual Structures: Information Processing in Mind and Machine. AddisonWesley, Massachusetts. 30. Sowa, J.F. (1991), Towards the Expressive Power of Natural Languages. In Sowa, J.F. (Ed.): Principles of Semantic Networks - Explorations in the Representation of Knowledge, Morgan Kaufmann Publishers, San Mateo, CA, pp. 157-189. 31. Sowa, J.E (1997), Matching Logical Structure to Linguistic Structure. In Houser, N. & Roberts, D.D. & Van Evra, J. (Eds.): Studies in the Logic of Charles Sanders Peirce, Indiana University Press, pp. 418-444. 32. Umano, M. (1987), Fuzzy Set Prolog. In Preprints of the 2nd International Fuzzy Systems Association Congress, pp. 750-753. 33. Wuwongse, V. & Manzano, M. (1993), Fuzzy Conceptual Graphs. In Mineau, G.W. & Moulin, B. & Sowa, J.E (Eds.): Conceptual Graphs for Knowledge Representation, LNAI No. 699, SpringerVerlag, pp. 430-449. 34. Wuwongse, V. & Cao, T.H. (1996), Towards Fuzzy Conceptual Graph Programs. In Eklund, P.W. & Ellis, G. & Mann, G. (Eds.): Conceptual Structures - Knowledge Representation as Interlingua, LNAI No. 1115, Springer-Verlag, pp. 263-276. 35. Zadeh, L.A. (1965), Fuzzy Sets. J. of Information and Control, 8: 338-353. 36. Zadeh, L.A. (1978), PRUF - A Meaning Representation Languagefor Natural Languages. Int. J. of Man-Machine Studies, 10: 395-460. 37. Zadeh, L.A. (1990), The Birth and Evolution of Fuzzy Logic. Int. J. of General Systems, 17: 95105. 38. Zadeh, L.A. (1996), Fuzzy Logic = Computing with Words. IEEE Trans. on Fuzzy Systems, 4: 103111.
Knowledge Querying in the Conceptual Graph Model: The RAP Module Olivier Guinaldo 1 and Ollivier Haemmerl~ 2 1 LIMOS - U. d'Auvergne, IUT de Clermont-Ferrand, BP 86, F-63172 Aubi~re Cedex, France guinaldo@volcans-ia, univ-bpclermont, fr
2 INA-PG, D~partement OMIP, 16, rue Claude Bernard F-75231 Paris Cedex 05, France Ollivier. gaemmerle@inapg, inra. fr
A b s t r a c t . The projection operation can be used to query a CG knowledge base by searching all the specializations of a particular CG - the question. But in some cases it may not be enough, particularly when the knowledge allowing an answer is distributed among several graphs belonging to the fact base. We define two operating mechanisms of knowledge querying, that work by means of graph operations. Both these mechanisms are equivalent and logically based. The first one modifies the knowledge base, while the second modifies the question. The RAP module is an implementation of the last algorithm on CoGITo.
1 Introduction The specialization relation, which can be computed by means of the projection operation, is the basis for the reasoning in the CG model. It expresses that one graph contains a more specific knowledge than another. One of the strong points of the CG model is that there exist sound and complete logical semantics, which means that the graphical reasoning is equivalent to the logical deduction upon the logical formulae associated with the graphs 1,
2. In this paper, we consider a knowledge based system in which the fact base and the query are represented in terms of CGs. An important step is to provide methods allowing one to query such a fact base. The projection operation can be used for such a search, but the problem is that the knowledge allowing one to answer a query can be distributed among several graphs of the knowledge base, in which case no projection can be made. We propose two algorithms designed to avoid that inconvenience. These algorithms are based on those of the ROCK system 3, 4. In the R o c k system we used some heuristics in order to limit the combinatory. But after our work upon the management of large knowledge bases, we implemented these algorithms and showed that they were equivalent to logical deduction 5, 6. This paper results from these works that were never published in an international event.
288
We propose a first reasoning algorithm which is sound and complete regarding the logical deduction. This algorithm works on the knowledge base by using a first step t h a t merges the knowledge in order to allow the projection to run. Then we propose a second algorithm t h a t uses a dual mechanism: the knowledge base is not modified, but the question is split and partial answers are searched for. We proved in 6 t h a t this second mechanism is equivalent to the first one, and t h a t it is sound and complete regarding the logical deduction. Then we show t h a t this second algorithm presents several valuable points compared with the first one. The last section of this article is a presentation of the RAP module based on the second algorithm. RAP is implemented on the CoGITo platform 7. 2
Knowledge
querying
In the following, we call the fact base a set of CGs under normal form I representing the facts of our system. Our goal is to provide CG answers to a CG question asked on a fact base. The projection operation is the ground operation used to make deductions.
2.1
T h e reasoning
In this paper, we exclusively focus on reasoning in terms of graph operations. However, in order to clarify the notions of fact base, question and answers, we propose an intuitive definition of these notions. A formal definition in first order logic is proposed in 6.
Definition 1 Let F B = { F 1 , . . . , Fk } be a set of CGs under normal form defined on the support S and ~ ( F 1 ) , . . . ,~(Fk) the set of associated formulae. Let ~ ( S ) be the set of formulae associated with S. Given Q a CG defined on S and ~(Q) its associated formula. We say that there exists an answer A to Q on F B iff ~( S), ~( F1), . . . , ~( Fk ) F9 (Q). The construction of such an answer is presented in the next section. 2.2
COMPOSITION:the first algorithm
Our goal is to propose a sound and complete algorithm computing CG answers according to the previous definition. In other words we want to show t h a t it is possible to give a CG answer A to the CG question Q without using a logical theorem prover. We could define the notion of answer as a "specialization of the CG question belonging to the CG fact base". Thus the algorithm could be "projecting the CG question upon each CG fact". But such a definition cannot solve the following 1 According to 8, a CG is under normal form if it doesn't have two conceptual vertices with the same individual marker; the normal form of a graph is computed by merging the conceptual vertices with the same individual marker.
289
problem: the knowledge relative to an individual marker and allowing one to answer a question m a y be distributed among several CG facts of the base. In t h a t case it is impossible to answer, because of the impossibility of finding a projection. For example, consider the question Q and the fact base F B presented in fig. 1. Q cannot be projected on a graph of FB. But the logical formula associated with Q can be deduced from the part of F B in bold lines. G r a p h F in fig. 1 is obtained by the disjunctive sum of F1 and F 2 (a disjunctive sum is a specialization operation in 8 consisting in the juxtaposition of two CGs), and then by the join made on the individual vertices Mike. This graph admits obviously a projection of Q on its grey subgraph. T h a t sub-graph of F is an answer to Q.
" ~ ~ ~ - - - - ~ C a r
CLT63
2
obj
1
Drive
1
agt
2
Man : Mike
F1
FB
Fig. 1. Example of a CG fact base and a CG question. No graph of FB admits a projection of Q. But graph F, the logical interpretation of which is equivalent to the conjonction of formulae associated with the graphs in FB, admits a projection of Q. There exists an answer to Q in FB.
So the first algorithm consists in considering the fact base F B = {F1,. 9 9 Fk} as a unique graph resulting from the disjunctive sum of F 1 , . . . , Fk, then normalizing t h a t graph by merging all the vertices with the same individual marker, and finally projecting Q on F. The COMPOSITION algorithm is presented thoroughly in 6.
290
2.3
BLUES: the second algorithm
Two drawbacks of the COMPOSITION algorithm can be noted. Firstly, the knowledge base is modified by the use of disjunctive sum and normalization. This is not a problem in terms of the complexity of these operations, but the original form of the knowledge is modified. This can be a problem for instance if such a knowledge represents sentences from a text and you want to know easily which sentences an answer comes from. Secondly, COMPOSITION involves a projection of the CG question into a graph of a size "equivalent to the size of the knowledge base". In terms of implementation, this can be prejudicial, the whole knowledge base having to be loaded into the m e m o r y in order to compute the projection. T h a t ' s why we propose the BLUES2 algorithm, which does not modify the fact base: BLUES splits the question instead of merging the CG base. The main idea of this algorithm was proposed by CarbonneiU and Haemmerl~ 4. It is an equivalent alternative to the COMPOSITION algorithm. Afterwards, we consider t h a t all the CG facts are individually in normal form: the combinatory increases significantly when we work with unspecified graphs, while putting a graph under normal form (which is an equivalent form in terms of logic) has a linear complexity in the size of the graph.
P r e s e n t a t i o n and definitions In the COMPOSITION algorithm, we have seen t h a t the answers to a question Q on a fact base F B are graphs resulting from the projection of Q into the graph produced by the disjunctive sum of CG facts then put under normal form. The BLUES algorithm simulates these operations in two stages: 1. It splits the question instead of merging the facts, then tries to m a t c h each generated sub-question into the base in order to obtain partial answers. 2. It expresses conditions on recombination of these partial answers in order to generate exact answers. More precisely, the s p l i t t i n g of a question Q gives us a set Q = { Q 1 , . . - , Qi, 9. . , Qn} of CGs t h a t we call s u b - q u e s t i o n s , and a set C = {C1,. 99 C j , . . . , Cm} of conceptual vertices sets. Each sub-question Qi is a copy of a connected sub-graph of Q which has at most one relation vertex (and its concept vertices neighbours). Each Cj is composed of all the concept vertices in Q which result from the splitting of the same concept vertex of Q t h a t we call a cut vertex. The c u t v e r t i c e s of Q are the concept vertices t h a t have at least two distinct neighbouring relation vertices. Moreover, we note c / t h e concept vertex of the sub-question Qi generated by the cut vertex c of Q (see fig. 2).
Definition 2 We call partial answer to a CG question Q the graph that results from the projection Hi of the sub-question Q~ into a graph of the base F B . We write it down IIi(Qi). 2 Building alL the solUtions aftEr splitS.
291
C
I
Q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
C31
Cl
I
,. i L~nve
I
Q3
Q1 Q2
Q
2
Fig. 2. Split of a CG question Q. c and c~ are two cut vertices of Q that generate four sub-questions. We have the following sets: Q = {QI,Q2,Q3, Q4} and
{{cl, c2}, (c2, c3, ~,}} Our goal is to know whether a partial answer set 7~ -- { H I ( Q 1 ) , - . . , IIn(Qn)} can be recombined into an exact answer to Q. We note H the sum of projections I I 1 , . . . , 1-In such t h a t Vi, 1 < i < n, if v E Qi then II(v) = Hi(v). D e f i n i t i o n 3 Given Cj = { c i l , ' " , c i z } the set of concept vertices resulting from the splitting of the cut vertex c of Q. Given Vj, 1 < j <_ l, Ilii(ci~) the image by Ilij of the vertex ci~ in the sub-question Qij. The set 11Cj = { Ilz ( % ) , . . . , Ilz ( % ) } is r e c o m b i n a b l e / f each pair ( II~ ( ci. ), Ilv (ci. ) ) satisfies one of the following conditions (the indices u and v are between 1 and l): a) IIu (ci=) and Ilv (ci,) is the same vertex; the splitting was not necessary. b) IIu(ci=) and 11v(ci~) are distinct but they have the same individual marker. D e f i n i t i o n 4 G i v e n / / I ( Q 1 ) , ' " , IIn( Qn) some partial answers which have been
obtained by projecting the sub-questions (of Q) Q1, " " , Qn by I I 1 , . . . , IIn on the CG fact base B F . Given C = {C1,... , C j , . . . ,Cm} the set of concept vertices sets due to the splitting in the CG question Q. Given H the sum of projections H I , . . . ,IIn such that Vi 1 < i < n, if v E Qi then 11(v) = IIi(v). Given Q1,...,n the graph resulting from the disjunctive sum on Q1," " , Qn. IfVj, 1 <_ j <_ m, IICj is recombinable, then we call a n s w e r to Q the normal form of the CG 11(Q1,...,n). Figure 3 shows an example of recombination of a CG answer by the BLUES algorithm. Note t h a t BLUES computes all the CG answers to a CG question Q on a CG fact base. The BLUES algorithm is presented thoroughly in 6. We also proved in t h a t article t h a t BLUES algorithm is a sound and complete reasoning mechanism with regard to our logical definition of the reasoning (definition 1) and t h a t it is equivalent to the C O M P O S I T I O N algorithm. Moreover, it is i m p o r t a n t to say t h a t these two algorithms are both based on the NP-complete problem of the graph projection 9.
292
H, ( 0 ,
"J
..... # ~ ( O4 i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
i
i
. .F1 ............................
-.:.:7:: . . . . . . . . . . .~. . . . . . . . . . . . . . . . . . . . .
Q1, Q2
I
~
Duplication+ "& Normalization
Drive
Fig. 3. Recombination of answers. A is a CG answer to the CG question Q of figure 2 on the CG fact base F B = (F1,F2}. Each IIi(Qi) is the partial answer to subquestion Qi on F B . and V~ symbolize the different cases of recombination on IIC1 = ' / / 3 ( c D', / / 4 ( c 4 ) } . ' (IIz(cl), IIz(c2)} and HC2 = {H2(c2),
3 3.1
The RAP Module Presentation
The RAP module (seaRch for All Projections) is essentially an implementation of the BLUES algorithm, thus it proposes a sound and complete reasoning. The RAP module is implemented on the CoGITo platform 10, 7 and then can take advantage of its graph base management system 5, 11. This management system is based on the hierarchy on the CGs induced by the specialization relation. Added to the usual techniques of classification and indexation 12, 13, the CoGITo platform implements hash-coding and filtering mechanisms that allow a reduction of the search domain without using any projection operation. In addition the projection algorithms that are used are efficient 9,11. As far as we know 14, the RAP module is the only reasoning module working in a general framework (the projection is not reduced to an injective projection... ) and being sound and complete regarding the logical deduction. Among the systems close to ours, we can cite the PEIRCE system 15. PEIRCE ignores the possibility of "split" knowledge, and it uses injective projection. But it proposes "close match" CGs which are pertinent answers. ROCK (Reasoning On
293
Conceptual Knowledge) 3 is another system close to ours. It searches exact and pertinent answers by modifying the question graph. It considers type definitions (RAP doesn't). But its major drawback is that it is not complete. ROCK can fail to find exact answers to a question. This drawback was at the source of the development of the BLUES algorithm by Carbonneill and Haemmerl~ 4, 6. 3.2
O p t i m i z a t i o n o f t h e BLUES
algorithm
Two optimizations of the BLUES algorithm have been done in the RAP module. The first one consists in using the set of specialization graphs of each subquestion graph as the search domain, instead of all the fact base. This is done by means of the specialization search functionnalities of CoGITo, that use hierarchical structuration and indexation. The second optimization consists in recomposing the answers only when it is certain that the sets of concept vertices o f / / C are recombinable, instead of trying an hypothetic recombination for all the combination of partial answers. More precisely this optimization is based on the following property: the choice of a partial answer to a sub-question Qi implies restrictions on the choice of the partial answers to the sub-questions that are localized in the immediate neighbourhood of Qi. If no partial answer is possible for one of these sub-questions, then the partial answer of Qi that was chosen cannot lead to an exact answer
to Q. Two kinds of restriction are used in this optimization. In the example of figures 2 and 3, when the algorithm chooses a partial answer of Q1 in F1, then it must choose a partial answer also belonging to F1 as a partial answer of Q2, in order to make a recombination of a type. Then for Q3 and Qa, the algorithm has to choose partial answers containing the individual vertex Man:Mike in order to make a recombination of b type. The indexed gestion of graphs in the CoGITo platform makes such a restriction of the search domain easy.
4
Conclusion
and perspectives
We have studied two reasoning algorithms only based on graph operations: the COMPOSITION algorithm that modifies the CG fact base in order to "compose" the knowledge eventually split through several distinct CGs, and the BLUES algorithm that works by splitting the question graph, searching for partial answers, then recombining a complete answer. These algorithms are sound and complete regarding the logical deduction. This work was preliminary a "theoretic" work, but we have implemented the BLUES algorithm in order to test it and to observe its behaviour on large CG bases. The first test concerns a base of 10000 graphs (generated by a random algorithm). The CPU times of BLUES are close to those of COMPOSITION. It is a valuable result, because it shows that using an algorithm that respects the original form of a CG fact base is not prejudicial.
294
This first step in the development of a reasoning module of the CoGITo platform has to lead us to a more complete module taking the extension of the CG model into account (nested CGs for instance 8). Another direction of study can be the exploration of techniques allowing one to provide pertinent answers as it was done by the ROCK system. The BLUES algorithm would be easily adaptable to a heuristic reasoning during its recombination phase. This would allow to take advantage of both the completeness of the RAP module and the ability of providing pertinent answers of the ROCK system.
References 1. J.F. Sowa. Conceptual Structures - Information Processing in Mind and Machine. Addison-Wesley, Reading, Massachusetts, 1984. 2. M. Chein and M.L. Mugnier. Conceptual Graphs : fundamental notions. Revue d 'Intelligence A rtificieUe, 6(4):365-406, 1992. 3. B. Carbonneill and O. Haemmerld. ROCK : Un syst~me de question/r~ponse fond~ sur le formalisme des graphes conceptuels. In Acres du 9~me Congr~s Reconnaissance des Formes et Intelligence Artificielle, Paris, pages 159-169, 1994. 4. B. Caxbonneill. Vers un syst~me de reprgsentation de connaissances et de raisonnement fondg sur les graphes conceptuels. Th~se d'informatique, Universit~ Montpellier 2, Janvier 1996. 5. O. Guinaldo. Etude d'un gestionnaire d'ensembles de graphes conceptuels. PhD thesis, Universit~ Montpellier 2, D~cembre 1996. 6. O. Guinaldo and O. Haemmerl~. Algorithmes de raisonnement dans le formalisme des graphes conceptuels. In Acres du XIe congr~s RFIA, volume 3, pages 335-344, Clermont-Ferrand, 1998. 7. O. Guinaldo and O. Haemmerl~. CoGITo : une plate-forme logicielle pour raisonner avec des graphes conceptuels. In Acres du XVe congr~s INFORSID, pages 287-306, Toulouse, juin 1997. 8. M.L. Mugnier and M. Chein. Representer des connaissances et raisonner avec des graphes. Revue d'Intelligence ArtificieUe, 10(1):7-56, 1996. 9. M.L. Mugnier and M. Chein. Polynomial algorithms for projection and matching. In Heather D. Pfeiffer, editor, Proceedings of the 7th Annual Workshop on Conceptual Graphs, pages 49-58, New Mexico State University, 1992. 10. O. Haemmerl~. CoGITo : Une plate-forme de dgveloppement de logiciels sur les graphes conceptuels. Th~se d'informatique, Universit~ Montpellier 2, Janvier 1995. 11. O. Guinaldo. Conceptual graphs isomorphism - algorithm and use. In Proceedings of the 4th Int. Conf. on Conceptual Structures, Lecture Notes in Artificial Intelligence, Springer-Verlag, pages 160-174, Sydney, Australia, August 1996. 12. R. Levinson. Pattern Associativity and the Retrieval of Semantic Network. Computers Math. Applic., 23(6-9):573-600, 1992. 13. G. Ellis. Compiled hierarchical retrieval. In E. Way, editor, Proceedings of the 6th Annual Workshop on Conceptual Graphs, pages 187-207, Binghamton, 1991. 14. D. Lukose, editor. Proceedings of the First CGTOOLS Workshop, University of New South Wales Sydney, N.S.W., AUSTRALIA, August 1996. 15. G. Ellis, R. Levinson, and P. Robinson. Managing complex objects in PEIRCE. International journal on human-Computer Studies, 41:109-148, 1994.
Stepwise Construction of the Dedekind-MacNeille Completion Bernhard Ganter 1 and Sergei O. Kuznetsov 2 1 Technische Universit/it Dresden, Institut f'dr Algebra, D-01062 Dresden 2 Department of Theoretical Foundations of Informatics, All-Russia Institute for Scientific and Technical Information (VINITI), ul. Usievicha 20 a, 125219 Moscow, Russia
A b s t r a c t . Lattices are mathematical structures which are frequently used for the representation of data. Several authors have considered the problem of incremental construction of lattices. We show that with a rather general approach, this problem becomes well-structured. We give simple algorithms with satisfactory complexity bounds.
For a subset A C_ P of an ordered set (P, <) let A t denote the set of all upper bounds. T h a t is, A t := {p C P I a < p for all a E A}. The set A; of lower bound is defined dually. A c u t of (P, <) is a pair (A, B) with A, B C P, A t = B, and A = B $. It is well known that these cuts, ordered by (A1, B1) <~ (A2, B 2 ) : ~ A1 C A2 ( -' ~. B2 C B1) form a complete lattice, the D e d e k i n d - M a c N e i l l e c o m p l e t i o n (or short c o m p l e t i o n ) of (P, <). It is the smallest complete lattice containing a subset orderisomorphic with (P, <). The size of the completion may be exponential in PI. The completion can be computed in steps: first complete a small part of (P, <), then add another element, complete again, et cetera. Each such step increases the size of the completion only moderately and is moreover easy to perform. We shall demonstrate this by describing an elementary algorithm that, given a (finite) ordered set (P, <) and its completion (L, <), constructs the completion of any one-element extension of (P, <) in
O(ILI. IP. w(P)) steps, where w(P) denotes the width of (P, <). The special case that (P, <) is itself a complete lattice and thus isomorphic to its completion, has been considered as the problem of m i n i m a l i n s e r t i o n of an element into a lattice, see e.g. Valtchev 4. We obtain that the complexity of inserting an element into a lattice (L, <) and then forming its completion is bounded by
O(ILI .,,(L)).
296
The elementary considerations on the incidence matrix of (P, <), which we use in the proof, do not utilize any of the order properties. Our result therefore generalizes to arbitrary incidence matrices. In the language of Formal Concept Analysis this may be interpreted as inserting a preconcept into a concept lattice.
1
Computing the completion
Let us define a p r e c u t of an ordered set to be a pair (S, T), where S is an order filter and T is an order ideal such that S C_T ~, T C_ S t. We consider the following construction problem: INSTANCE:
A finite ordered set (P,_~), its completion, and a precut (S,T) of
(P, _).
OUTPUT: The completion of (P U {x}, ~), where x ~ P is some new element with
p~_x ~
pES
x~_p .'. '.. p E T
and
forallpEP. 1
(P, _~) may be given by its incidence matrix (of size O(PI2)). The completion may be represented as a list of cuts, that is, of pairs of subsets of P. With a simple case analysis we show how the cuts of (P U {x}, ~) can be obtained from those of (P, <).
Proposition 1. Each cut of (P U {x}, <), except (S U {x}, T U {x}), is of the form (C,D),
(CU{x},DnT),
or
(CNS, DU{x})
for some cut (C, D) of (P, ~). IS (C, D) is a cut of (P, ~) then 1. ( C U { x } , D N T ) is a cut of ( P U { x } , _ ) iff S c C = ( D n T ) 4, 2. ( C N S , D U { x } ) i s a c u t o f ( P U { x } , ~ ) i f f T C D = ( C N S ) t,
3. (C,D) i s a c u t o f ( P U { x } , ~ _ )
iffC~:S andn~:T.
For a p r o o f of this result and of the following see the next section.
Proposition 2. The number of cuts of (P U {x}, _<) does not exceed twice the number of cuts of (P, ~_), plus two. i natural embedding of the completion of (P, _~) into that of (P U {x}, _~) is given by the next proposition:
Proposition 3. For each cut (C, D) of (P, ~_) exactly one of (C,D),
(CU{x},n),
(c, n u { x } ) ,
(CU{x},nu{x})
is a cut of (P U {x}, <). These cuts can be considered to be the "old" cuts, up to a modification. "New" cuts are obtained only from cuts (C, D) that satisfy 3) and simultaneously 1) or 2). An algorithm can now be given: 1 For elements of P different from x, the order remains as it was.
297
A l g o r i t h m to construct the completion of (P U {x}, <). Let L denote the set of all cuts of (P, <). - Output (SU { x } , T U {x}). - For each (C, D) 9 L do: 1. If C C_ S and D q: T then output (C, D U {x}). 2. If C g S and D C_ T then output (C U {x}, D). 3. I f C g S a n d D ~ T t h e n (a) output (C, D), (b) if C = (D n T)t then output (C U {x}, D n T), (c) if D = (C N S) t then output (C n S, D U {x}). - End. It follows from the above propositions that this algorithm outputs every cut of (P U {x}, <) exactly once. Each step of the algorithm involves operations for subsets of P. The most time consuming one is the computation of (D n T) 4 and" of (C n S) t. Note that ( n N T) ~ = (min(D n T)) "~, where m i n ( n n T) is the set of the minimal elements of n N T and can be computed in O(P I 9w(P)) steps. Since I m i n ( n N T) I _< w (P) and, moreover, (min(D N T)) 4 =
I p 9 min(D n T ) } ,
we conclude that (D n T) * can be obtained with an effort of O(IPI" w(P))- The dual argument for (C n S) t leads to the same result. So if L is the set of cuts of (P, <), then the algorithm can be completed in O(ILl" IPI" ~(P)) steps. Let us mention that computing an incidence matrix of the completion can be done in O(IL 2) steps, once the completion has been computed, see Proposition 6.
2
Inserting a preconcept
A triple (G, M, I) is called a f o r m a l c o n t e x t if G and M are sets and I C G x M is a relation between G and M. For each subset A C G let A I := {m 9 M I (g, m) 9 I for all g 9 A}. Dually, we define for B C_ M B I:={g 9
9149
A formal concept of (G,M,I) is a pair (A,B) with A C C, B C_ M, A I = B , and A = B t. The formal concepts, ordered by (A1,B1) _< (A2, B2): r
A1 C_ A2
(~
B2 C_ B1),
form a complete lattice, the concept lattice of (G, M, I). Most of the arguments given below become rather obvious if one visualizes a formal context as a G x M - cross table, where the crosses indicate the incidence
298 relation I. The concepts (we sometimes omit the word "formal") then correspond to maximal rectangles in such a table. Note that if A = B I for some set B C_ M, then (A, A I) automatically is a concept of (G, M, I). A pair (A,B) with A C_ G, B C_ M, A C_ B I, and B C_ A I is called a p r e e o n c e p t of (G, M, I). In order to change a preconcept into a concept, one may extend each of the sets G and M by one element with the appropriate incidences. So as a straightforward generalization of the above, we consider the following construction problem: A finite context (G,M,I), its concept lattice, and a preconcept (S, T) of (G, M, I). OUTPUT: The concept lattice of (G U {x}, M U {x}, I+), where x ~ G U M is a new element and INSTANCE:
I + := I U ((S U {z}) x ({x} UT)). The special case of section 1 is obtained by letting G=M:=P
and
(g,m) E I : ~
g~m.
P r o p o s i t i o n 4. Each formal concept of (G O {x}, M U {z}, I+), with the exception of (S U {x}, T O {x}), is of the form
(C,D),
(CU{x},DNT),
or
(CNS, DU{x})
for some formal concept (C, D) of (G, M, I). With the obvious modifications, the conditions given in Proposition 1 hold. Proof. Each formal concept (A, B) of (G U {x}, M U {x}, I +) belongs to one of the following cases: 1. x E A , x E B . ThenA=SU{x},B=TU{x}. 2. x E A,x ~ B. Then B C_ T and B I = A \ { x } . Therefore (C,D) := (A \ {x}, (A \ {x}) I) is a formal concept of (G, M, I) satisfying S C C = ( D N T ) I.
(1)
Conversely if (C, D) is a formal concept of (G, M, I) satisfying (1), then
(A,B) := (CO { x } , D n T ) is a formal concept of (G O {x}, M U {x}, I+). 3. x ~ A, x E B, dual to 2. Then (C, D) := ((B \ {x}) I, B \ {x}) is a concept of (GU { x } , U U {x},I +) with T C n = ( C N S ) z. Conversely each formal concept (C, D) with (2) yields a formal concept (A, B) := (C n S, D U {x}) of (G U {x}, M U {x}, I+).
(2)
299
4. x • A, x r B. satisfying
Then (C, D) := (A, B) is a formal concept also of (G, M, I),
C~:S,
D~:T.
(3)
Conversely is each pair with (3) also a concept of (G U {x}, U U {x}, I+). If both (C U {x}, D N T) and (C N S , D U {x}) happen to be concepts, then S C_ C and T C_ D, which implies C U {z} = T I, D U {x} = S z. Thus apart from perhaps one exceptional case these two possibilities exclude each other. From each concept of (G, M , I ) , we therefore obtain at most two concepts of (G U {x}, M U {z}, I+), except in a single exceptional case, which may lead to three solutions. On the other hand, each concept of (G U {x}, U U {x}, I+), except (S U {x}, TU {x}), is obtained in this manner. This proves Proposition 2. To see that Proposition 3 holds in the general case, note that each formal concept (C, D) of (g, M, I) belongs to one of the following cases: 1. C = S, D = T. Then (CU{x}, DU{x}) is a concept of (GU{x}, MU{x}, I+). 2. C C_ S, T C D. Then D = C I and condition (2) (from the proof of Proposition 4) is fulfilled. Thus (C, D U {z}) is a concept of (G U {z}, M U {z}, I+). 3. S C C, D C_ T. Then C = D x and condition (1) is satisfied. Therefore (C U {x}, D) is a concept of (G U {x}, M U {x}, I+). 4. C ~: S, D q~ T. Then (C, D) is a concept of (G U {x}, M U {x}, I+). It is clear that each of the possible outcomes determines (C, D), and that therefore the possibilities are mutually exclusive. It is a routine matter to check that these formal concepts are ordered in the same way than those of (G, M, I). The construction thus yields a canonical order embedding of the small concept lattice into that of the enlarged context. Since all details have carried over to the more general case, we may resume: P r o p o s i t i o n 5. The algorithm given in section 1, when applied to the concept lattice L of (G, M, I), computes the concept lattice of (G U {x}, M U {x}, I+). The abovementioned complexity considerations apply as well, but it is helpful to introduce a parameter for contexts that corresponds to the width. The incidence relation induces a quasiorder relation on G by gl <: g2 : ~
{g2} I C__{g2} I.
Let w(G) be the width of this quasiorder, and let w(M) denote the width of the corresponding quasiorder on M. Let
r(G, M, I) := (w(a) + w(M)) 9 (ICl + IMI). Of course, r(G, M, I) < (IGI + IMI) 2. Provided the induced quasiorders on G and M are given as incidence matrices (these can be obtained in O(IGI 9 IMI 9 (IGI + IM)) steps), we have a better bound on the complexity of the derivation operators: the set A z can be computed from A with complexity O(r(G, M, I)).
300
Computing A I was the most time consuming step in the algorithm on section 1. Thus computing the new concept lattice can be performed with O(ILI 9
M, I))
bit operations. Each concept of (GU{x}, MS{x}, I+), except (SU{x}, TU{x}), is generated by exactly one of the steps 1, 2, 3a, 3b, 3c of the algorithm, and precisely 3b) and 3c) lead to "new" concepts (other than (SU {x}, TU {x}). When performing the algorithm, we may note down how the concepts were obtained. These data can be used later to construct an incidence matrix of the new lattice:
Proposition 6. The order relation of the new lattice can be computed in additional
O(ILI 2)
steps.
Proof. (SU {x}, TU {x}) is the largest concept containing x in its extent and the smallest concepts containing x in its intent. In other words, (S U {x}, T U {x}) is greater than all concepts generated in steps 2) and 3b) and smaller than all concepts generated by steps 1) and 3c). It is incomparable to the other elements. So we may exclude this concept from further considerations. The order relation between the "old" concepts, i.e. between those generated in steps 1), 2), and 3a), is the same as before. For the remaining case, we consider w.l.o.g, a concept (CU {x}, n A T ) , which was generated in step 35) from a concept (C, D) of (G, M, I). Now (CU {x}, O n T) < (E, F) if and only if (E, F) has been generated in steps 2) or 35) from some concept ( E \ {x}, ( E \ {x}) I) > (C, D) of (G, M, I). If x E E, then similarly (E, F) < (C U {x}, D n T) is true if and only if (E, F) has been generated in steps 2) or 3b) from some concept (E \ {x}, (E \ {x}) I) < (C, D) of (G, M, I). Suppose x r E. If (E, F) was obtained in steps 1) or 3a) of the algorithm, than (E, E I) is a concept of (G, M, I) and (E, F) < (CU{x}, O A T ) is equivalent to (E, E x) < (C, D). If (E, F) was obtained in step 3c), then S z C F, which implies O A T C S x C F. So in this case (E, F) < (CU {x}, O A T ) always holds. Summarizing these facts, we obtain all comparabilities of a concept (C U {x}, D n T) of (G U {x}, M U {x}, I +) which was derived from a concept (C, D) of (G, M, I) in step 3b): Concepts greater than (CU{x}, b A T ) are those obtained in steps 2 or 3b) from concepts greater than (C, D), concepts smaller than (C U {x}, D n T) are those obtained in steps 1), 2), 3a) or 3b) from those smaller than (C, D) and all those obtained in step 3c). Thus the comparabilities of (C U {x}, D n T) can be obtained from those of (C, D) using only a bounded number of elementary operations in each case. Filling the corresponding row of the incidence matrix is of complexity O (ILl). The argument for concepts obtained by 3c) is analogous.
The generalized algorithm may be applied to the context (P, P, ;g), obtained from an arbitrary ordered set (P, _<). The concept lattice is the lattice of maximal antichains of (P, <) (see Wille 5). Our result therefore relates to that of Jard, Jourdan and Rampon 2.
301
3
A non-incremental procedure may be more convenient
In practice, a strategy suggests itself that may be more time-consuming, but is nevertheless simpler than the algorithm presented in section 1. Rather than pursuing an incremental algorithm, it may be easier to compute the lattice "from scratch" (i.e. from the formal context, or, in the special case, from the ordered set (P, <)) each time. For this task there is an algorithm that is remarkably simple (it can b e programmed in a few lines) and at the same time is not dramatically slower than the incremental approach: it computes the concept lattice i of a formal context (G, M, I) in O(ILI. IGI 2. IMI) steps. Using the parameter introduced above, we can improve this to O( IL I 9IG I 9r( G, M, I)). This algorithm generates the formal concepts inductively and does not require a list of concepts to be stored. Let us exemplify the advantage of this by a simple calculation: A formal context (G, M, I) with IGI = IMI -- 50 may have as may as 250 formal concepts in the extreme. But even if the lattice is "small" and has only, say, 101~ elements, it would require almost a hundred Gigabytes of storage space. Generating such a lattice with the inductive algorithm appears to be time-consuming, but not out of reach; the storage space required would be less than one Kilobyte. Moreover, this algorithm admits modifications that allow to search specific parts of the lattice. For details and proofs we refer to the literature (see 1), but the algorithm itself is so simple that it can be recalled here. For simplicity assume G := { 1 , . . . , n}, and define for subsets A, B C G A
i E B is minimal in ( A \ B) U (B \ A).
Then the definition A
A
yields a strict linear order on the set of all subsets of G (a lexicographic or, for short, leetle order). If (A, B) is a formal concept of (G, M, I) then A is called its e x t e n t . Since B = A I, the extents uniquely determine the concepts. To generate all concepts, it therefore suffices to generate these. This can be done in lectic order, starting with 0 II. The step that constructs from a given set A the "next" extent is of the form A ~ i := ((A N { 1 , . . . , i - 1}) U {i}) II. The following theorem describes how the element i must be chosen:
Let (G, M, I) be a formal context with G := { 1 , . . . , n}. For given A C G, the smallest extent that is larger than A (with respect to the lectic order) is given by A + := A 9 i, T h e o r e m 1 (see 1).
where i is maximal with respect to A
302
It is easy to see that computing A • i requires at most O(IGI. IMI) steps, using the induced quasiorders only O(v(G, M, I)) steps. The "next" extent therefore is found at an expense of O(IG 2. IMI), or even O(IG I 9 v(G, M, I)). If a lattice diagram is to be generated, the inductive approach may even be faster than the incremental one. For a given extent A 5~ G, the extents of the upper covers are precisely the minimal sets of the form ( A U { i } ) H,
i~A.
Computing these requires O(IGI 2 9 IMI) steps. Localizing such an upper cover in a linear list of extents, using a binary search algorithm, can be done with O(loglLI) comparisons of subsets of G. The complexity thus is O(IG I 9 IMI), since ILl < 2 IMI. Every finite lattice (L, <) is isomorphic to some concept lattice. A natural choice is the formal context (J(L), M ( L ) , _<), where J(L) and M ( L ) denote the sets of join- and meet-irreducible elements of (L, <), respectively. If we denote the cnrdinalities of these sets by j ( L ) := IJ(L)h
re(L) := IM(L)h
we can resume: C o r o l l a r y 1. The covering relation of a finite lattice (L, <) can be computed in O ( j ( Z ) 2 9 r e ( L ) . ILl) steps, provided the sets J(L) and M ( L ) of join- and of meet-irreducible elements are given. This is considerably better e.g. than the bound given by Skorsky3. Again, the bound can be refined using the width of the induced orders on G and on M.
References 1. Bernhard Ganter, Rudolf Wille: Formale Begriffsanalyse - Mathematische Grundlagen. Springer Verlag 1996. 2. C. Jard, G.-V. Jourdan and J.-X. Rampon: Computing On-Line the Lattice of Maximal Antichains of Posets. Order 11 (1994). 3. Martin Skorsky: Endliche Verbiinde - Diagramme and Eigenschaften. Shaker, 1992. 4. Petko Valtchev: An Algorithm for Minimal Insertion in a Type Lattice. Second International KRUSE Symposium, Vancouver, 1997. 5. Rudolf Wille: Finite distributive lattices as concept lattices. Atti Inc. Logica Mathematica, 2 (1985).
PAC Learning Conceptual Graphs Pascal Jappy
Richard Nock
Laboratoire d'Informatique, de Robotique et de Micro61ectronique de Montpellier 161 rue Ada, 34392 Montpellier Cedex 5, France {jappy, nock}@lirmm.fr
Abstract. This paper discusses the practical learnability of simple classes of conceptual graphs. We place ourselves in the well studied PAC learnability framework and describe the proof technique we use. We first prove a negative learning result for general conceptual graphs. We then establish positive results by restricting ourselves to classes in which basic operations are polynomial. More precisely, we first state a sufficient condition for the learnability of graphs having a polynomial projection operation. We then extend this result to disjunctions of graphs of bounded size.
1
Introduction
The last decade has seen an explosive growth in database technology and the amount of data collected. Advances in data collection have flooded us with lots of data. Data mining is the efficient supervised or unsupervised discovery of interesting, useful, and previously unknown patterns from this data. Machine Learning, and in particular, Inductive Learning, is the supervised extraction of an abstract concept which has to correctly explain classified observations. In both Data Mining and Machine Learning, the choice of the language used to represent the data is of uppermost importance. And the study of the efficiency of learning for a given representation language, i.e. its learnability, has become an active field of research. It is common, in Data analysis and Machine Learning, to represent data as attribute-value pair vectors, often real valued. And, in Computational Learning Theory, the complexity of Learning has been studied mainly for Boolean (i.e. two valued) formula classes. However, alternative descriptions have been proposed in the fields of Artificial Intelligence and Knowledge Representation. Structural representations, for instance, provide a means of capturing a special type of information that others do not. Not only are an object's properties described, but also t h e relations between its subcomponents. Furthermore, the readability of such representations is far greater. This makes them much more usable by experts and an abundant literature has been devoted to them, from early semantic networks 18 to the more recent Description Logics 2 or Conceptual Graphs 23, 3. In Machine Learning, the former are now being used in several applications such as DENDRAL 13.
304
To formally analyse the learning hardness associated to a given description language, several theoretical models have been proposed. Identifiability in the limit 8, for instance, focuses on isolating a formula capable of explaining a set of examples in finite time but with no a priori bound on the number examples available to the learner. But the most widely used learnability model is the Probably Approximately Correct (PAC) framework introduced by Valiant 24. It has become a learnability benchmark in which the vast majority of studies of the past ten years have been undertaken. Early work cast a pessimistic shadow on the learnability of such classes. 9, for instance, showed that learning existential conjunctions in structural domains can be intractable. However, more recent studies have shown that compromises can be found between sheer representation power and complexity of learning. In the quest for more expressive representation languages for Machine Learning, two main trends of structural formalisms have emerged. On one side, Inductive Logic Programming (ILP) aims at learning concepts expressed as Horn Clauses from examples and background knowledge 15. Though the general problem is undecidable, many restricted clasSes have led to learnability in the limit 22 or Probably Approximately Correct (PAC) learnability results 6; 12; 4. On the other, a family of structural languages called Description Logics has been developed in the past decade by the Knowledge Representation (KR) community. They provide an efficient means for expressing concept hierarchies and form the basis of KR systems such as KL-ONE 2. Furthermore, they offer syntactic restrictions of First Order Logic (FOL) previously unexplored in ILP. In this paper, we study the possibility of using Conceptual Graphs in learning applications. This formalism has been studied extensively and their algorithmic properties are well known 3 making it a natural candidate for learning applications. Besides, their expressive power is high, equivalent to large subsets of First Order Logic 23, 3. b-hrthermore, document retreival applications which employ search procedures close to Data Mining techniques have been developed using conceptual graphs 7. We place ourselves in the PAC framework and use a constructive proof technique 1 to obtain our results. Our goal is to isolate which subsets of general Conceptual Graphs allows efficient learning. We first give negative result for conceptual graphs, showing that their NP-Complete projection operation makes it impossible to PAC learn them. We then show a sufficient condition for Conceptual Graph classes with polynomial projection to be learnable. Finally, we extend this result to disjunctions and decision lists of graphs of limited size. Both disjunctions and decision lists are widely employed in Machine Learning and the classes we define by extending these to conceptual graphs are likely to prove very efficient. The rest of this paper is organized as follows. In section 2, we present the' formal learnability model we have chosen to place ourselves in. In particular, we describe both the techniques used in practice to prove positive results, and existing theories which limit our search for efficiently learnable classes. In section 3,
305
we prove a first negative result for general conceptual graphs. Section 4 the lists our positive results and their respective proofs. We finally conclude in section 5.
2
Formal
Background
Our goal in this paper is to determine which conceptual graph classes are efficiently learnable. Obviously, this formal analysis requises an explicit model of what it means to be efficiently learnable. In this section, we describe our model of learnability, which is a slight modification of the PAC learnability model introduced by Valiant 24.
2.1
Hypothesis Space
In inductive learning, the goal is to find an unknown target concept, or some good approximation, from a set of labeled examples. Let X be a set called the domain, and let CG the set of conceptual graphs. A concept C over X is a subset of X. A concept class is a set of concepts. This will designate a constrained set of potential "target" concepts which could be labelling the training examples. A hypothesis is also a subset of X which the learning algorithm produces as an approximation of the hidden target concept. A hypothesis class is a set of hypotheses. Associated with each concept or hypothesis class is a language L C C~ used for writing down concepts or hypotheses in these classes. In this paper, both hypotheses and concept classes will be variously restrited Conceptual Graphs classes. We will also assume the existence of an acceptable size measure (by acceptable, we mean somehow polynomially related to the actual number of bits required to write down a concept or hypothesis). Also, as it will always be clear from the context whether we are refering to a concept or its representation i n / : , we will let c denote both. Usually, examples of the concept c are elements of the domain X, with x E X labeled as positive if x E c and negative otherwise. Here, we will depart from this practice and consider examples described as conceptual graphs, since this is closer to real applications of the domain. Therefore, examples will be elements selected from CG and x will be labeled positive if c subsumes x (i.e. c projects onto x) and negative otherwise. Finally, the learning algorithm must be allowed greater resources if the concept class is vast. Thus class complexity parameters are needed to express this richness. In this paper, we will follow the accepted theoretical presentation of conceptual graphs proposed in 3. Hence, the parameters which determine the richness of a given class of conceptual graphs are the number of relations in the support, the number of concept in the type lattice and the number of individual markers allowed. We will let a l , a2 and a3 denote these respectively. And more generally, C~(~) will represent the subset of CG defined using parameters (a~).
306
2.2
PAC
learnability
Informally, to say that a class C of concepts is "learnable from examples" means that there exists a corresponding learning algorithm ,4 which for any function c in C is capable of converging upon c as it is given more and more examples. ,4 will have learnt c from the examples. This accomplishment by itself is not necessarily very interesting as no bound on .A's execution time or on the number of examples required has been stated. For instance, any boolean function class defined over n variables is clearly learnable from examples, since all the algorithm has to do is to wait for an example corresponding to each of the 2 n possible variable assignments to know the complete truth table for e. So the interesting question really is to know whether C is easily learnable from examples, that is if the learning algorithm will require both few examples and a reasonable computing time. Valiant 24 introduced a notion of learnability which explicitely specifies that the hypothesis acquired by the learning algorithm should be a close approximation of the concept being taught via its examples, in the sense that this hypothesis should perform well on new data. We now make these notions more precise. Assume a fixed but unknown probability ditribution D~(o to be defined on CGa(~) and according to which the examples are drawn. When a hypothesis h is returned by the algorithm, its quality is evaluated by the measure of the probability that a new example drawn according to D~(o is incorrectly classified by h. 1. Let C denote a concept class and C(a~) the subset o l d containing all elements built with parameters (~i). C is polynomially learnable by 74 iff 3 A a learning algorithm, such that:
Definition
- VD(a~) probability distribution over C(a~), - Vc~(i) richness parameters, - Vc, target concept in C(a~), - Vc precision parameter, - Vr confidence parameter,
when given a set of size m polynomial in ~i, size(c), 1/~ and 1/~? of examples of c drawn according to D(~), A finds a hypothesis g in C(~) such that : PD(.,)(PD(.,)(f ~ g ) > e) < 77
(1)
in time polynomial in m and he. In other words, this definition requires that .4 be able to produce an answer whose error is less than the prespecified precision parameter e. However, it is theoretically possible to draw a learning sample of examples according to P~(~) that is not '~epresentative" of the target concept c. So, the model also supplies a confidence parameter (f and only demands that the precision be exceeded with probability at most J. Obviously, as e and 5 approach 0, the algorithm is allowed a larger learning sample and more computation time.
307
If a concept class C conforms to definition 1, it is said to be PAC learnable by itself, that is, the hidden concept c belongs to it and the learning algorithm also searches for the hypotheses to approximate c in C. There are a number of variations on this definition. In particular, one which interests us is the relaxation which happens when the algorithm is allowed to look for the hypotheses in another (hypothesis) class 74. In this case, the concept class C is said to be PAC learnable by 74.
2.3
Obtaining positive results
Proving positive PAC results using Valiant's definition can be dificult. Blumer et al. 1 have developed easier techniques for doing so. We now repeat one of their key theorems which allows the proof to be split into two simple ones. D e f i n i t i o n 2. A class C is said to be of polynomial (code) size if V(~i)~(c~,) = log(IC=, I) is polynomial in (ai).
Definition 3. A class C is said to be polynomial time identifiable if, when given parameters (ai) and a set of m examples, an identification algorithm can produce in time polynomial in m and (ai) a function g of C(~) which is consistent with the examples, or detect its non existence. T h e o r e m 1. Let C denote a concept class of polynomial size. If C is polynomial time identifiable then C is polynomially learnable. P r o o f Suppose f is a hypothesis in C(a~) whose error probability is greater than ~. The chance that f be consistent with a sample of m examples drawn according to 7~(a~) in C(a~) is at most (1 - e) m. So the chance that an arbitrary concept in C(~) satisfy both conditions is at most C(~)I(1 - e) m. The PAC learning requirements demand that: IC(o,,)l(1 - e) TM _< 1
-
6.
(2)
So, if we solve, we get: m > l(log(IC(~,)l) + log(~))
(3)
if m satisfies this equation, the probability that a hypothesis consistent with the sample turns out to have an error greater than e is less than & In other words, the algorithm needs only examine m examples and return a consistent hypothesis. The class being polynomial sized, m is bounded by a polynomial in ( ~ ) , 7, 1 ~ and the size of the largest example as required by the PAC framework. The practical consequence of this result is that, in order to prove a positive PAC result for a concept class C it is sufficient to produce an identification algorithm and prove C's polynomial size. Unfortunately, this also highlights one major constraint of this technique: if
308
testing whether an element x is an example of a concept c cannot be done in polynomial time, then no identification algorithm can be polynomial. This limits the use of the above results to classes for which this test is polynomial. In the following section we give a stronger result for conceptual graphs, similar in spirit to T h e o r e m 1 in 5. 3
A Negative
Result
Our first result concerns the general class of conceptual graphs CG for which we prove the necessity of a polynomial projection test for the existence of a PAC learning algorithm. The proof of our theorem relies on a structural complexity hypothesis and requires the presentation of the complexity class P/Poly. D e f i n i t i o n 4. The class P/Poly is the set of all languages accepted by a (pos-
sibly nonuniform) family of polynomial-size deterministic circuits. It is an accepted assumption that N P ~ P/Poly, which in particular implies N P - complete ~=P/Poly. We now state our first result. 2. Let C C CG denote a conceptual graph class. If the projection test between elements in C is either NP-Complete or coNP-Complete, then C is not PA C-learnable unless NP C P/Poly.
Theorem
P r o o f For any conceptual class C and concept c E C, we note inf(c) the concept having the same representation as c, but which denotes the set inf(c) -d E C such t h a t c projects into d. Similarly, we define inf(C) = inf(c),c E C. It is immediate t h a t C is PAC learnable i f f inf(C) is also, and that testing membership for a concept inf(c) E inf(C) is as hard as testing projection between elements in C. In T h e o r e m 7 21, it is shown t h a t if inf(C) is PAC learnable then inf(C) E P/Poly. Thus, if projection in inf(C) is NP-Complete or CoNP-Complete, then we have N P C C_ P/Poly or C o N P C_ P/Poly. This leads to a contradiction in b o t h cases (because P/Poly is closed under complementation). A simple corollary of this theorem yields our first result regarding the learnability of conceptual graphs. C o r o l l a r y 1. Since the projection operation is NP-complete in C~ , general conceptual graphs are not PAC learnable. In the next section, we examine restrictions of this ast class and determine which are learnable in the framework presented above. 4
Three
positive
results
In this section, we investigate restrictions on conceptual graphs which are sufficient to ensure PAC learnability. Our previous negative result imposes t h a t we restrict ourselves to classes whose projection operation operation is polynomial.
309 Our first positive result is a general one. It is based on a transcription of Theorem 1 and highlights a size limitation on classes which is sufficient to ensure classe's PAC learnability. We then specialize this and prove that well known boolean formula classes can be extended by substituting conceptual graphs of limited size for the boolean monomes more commonly used in machine learning. We prove that the classes thus obtained, which are far more expressive than their boolean counterparts, are PAC learnable. 4.1
P A C learning individual g r a p h s
T h e o r e m 3. Let C(a~) C CG denote a conceptual graph class. If C(a~) is of polynomial (code) size and the least upper bound operation is polynomial, then C(~) is PAC learnable. P r o o f We use the technique based on theorem 1. We prove that log(IC(~)l) is polynomial in (~i, and provide an identification algorithm, that is one capable of returning a conceptual graph consistent with an imput sample. We give a large upperbound of the number of elements of C(~) with a total number of n vertices (which we use as a crude but acceptable size measure) as follows. We suppose that we have n relation vertices, and n concept vertices. In this bipartite graph, we suppose that any edge is either present or absent. We suppose that for any n concept vertex, we have 0~2c~3 substitution possibilities, and for any relation vertex, we have ~1 possibilities of substitution. Given this procedure for generating graphs, it follows that we can generate any graph in C(~) having a total number of n vertices. The number of total substitutions of vertices is upperbounded by And the size of C(~) is therefore calculated taking into account the possibility for any edge of being either absent or present, therefore the total number of CG having n vertices is (largely) upperbounded by ((O~1C~20,3)n)n 2
=
?%3
It is obvious that taking the log of this quantity gives a polynomial in ai. The identification algorithm we propose is based on the least upper bound operation lub(., .) which returns for any pair of conceptual graphs the most specific one which projects into both. Let S = S + t2 S - denote the sample. Let %os be the graph defined as the lub of all positive examples and Cneg the lub of all negative examples. One of these two graphs is necessarily consistent with the sample. Indeed, if this were not the case, there would be a positive example which projects into cn~g and a negative one which projects into cpos. Since, by definition of the lub, cpos projects into all positive examples and cn~g into all negative ones, the transitivity of the projection operation would mean there would be a cycle between the positive examples (or the negative ones) and themselves, which is impossible.
310
We have thus produced an algorithm capable of returning a graph consistent with the input sample. And if the lub operation is polynomial, this algorithm also is. This concludes the proof. This result uses the lub(., .) operation to construct hypothesis graphs. The theorem below links the more commonly studied projection operation to PAC learnability. T h e o r e m 4. Let C(a,) E CG denote a conceptual graph class. If the both the
complexity o/ projection test between elements of C(~) and IC(a~)l are polynomial in (ai) then C(~) is PAC learnable. P r o o f Here, the size restriction imposed on C(a~) lets us construct an even simpler identification algorithm. Indeed, a simple enumeration of all the elements in C(~) and a projection test between the current graph and all the examples in the sample are all that is needed to select a consistent graph or detect its non existence. This algorithm is obviously polynomial if the theorem's assumptions are true. T h a t the polynomial (code) size criterion is met is also trivial since the class itself is of polynomial cardinal. This result is weaker than the previous one since it requires the class to be of smaller size. However, in the next section, we extend it by showing that under identical conditions on C(~), more elaborate hypotheses (than individual graphs) can be constructed from elements of C(~) and successfully PAC learnt. 4.2
L e a r n i n g f o r m u l a s b a s e d o n size l i m i t e d g r a p h s
In this section, we examine the possibility of using Conceptual Graphs as the basic buidling blocs of more elaborate formulas. Two classes of boolean formulas have been at the center of numerous studies in Machine Learning. These are DNF (Disjunctive Normal Form) 25 and DL (Decision Lists) 19. An element of DNF (which we will note dnf)is the disjunction of boolean monomes, that is the conjunction of boolean litterals. A d n f classifies an example x as positive if x satisfies at least one of its monomes. The learnability of DNF is an important open problem, but several results have been shown for subsets of this class. In particular, the class k-DNF, in which the monomes in a disjunction are limited in size to a maximum of k, is PAC learnable25. A decision list (dl) is an ordered list of conjunctive rules noted
(tl -~ gI), (t~ -+ g2), ..., (tk -~ gk),gk+l where V1 < i < k, ti is a boolean monome and gi E 0,1), and the class gk+l is called the default class. The class associated to any example x is the goal class corresponding to the first test passed by the example, ie the first monome satisfied by x. If none is passed, the example is assigned the default class. Again, a positive PAC learning result is obtained if the monomes in the list are limited in size to at most k.
311
These two classes are very much used in learning applications, and have good algorithmic properties. Thus, it is very interesting to extend them by replacing the monomes they contain by more expressive terms. This increases their representation power, yet retains the good algorithmic aspects. This approach has already been studied in detailed in 10 for several Description Logics as well as other similar structured knowledge representation formalisms. Here, we propose to do the same with conceptual graphs. Our next result shows under which conidtions on the graph sets this extension leads to learnable formula classes. T h e o r e m 5. Let C(c~) E C~ denote a conceptual graph class. If the both the complexity of projection test between elements of C(~) and C(a~) are polynomial in (ai) then k - C(a~)DNF and k - C(~)DL are P A C learnable. P r o o f Again, our proof is contructive. Let k - C(~) denote the subset of C(al) containing only graphs of size no greater than k. Replacing n by k in the size of C(~) yields:
Ik -C(,,) _<( a l a 2 a 3 ) k3
(4)
We first calculate the number of disjunctions and of desision lists of graphs in k-C(a0 then produce identificationalgorithmsfor k-C(a0DNF and k-C(a~)DL. Any element of k - C(~I)DNF is built in the followingway: all the graphs in k - C(a~) are examinedone by one and each is either added to the formulaor left out. Thus, the number of disjunctions is equal to 21k-C(-oI. And consequently: l o g ( k - C(~)DNFI) =
Ik- C(~,)l __ (ot10~20t3) ka
(5)
Similarly any element of k - C(a~)DL is built as follows: all the graphs in k - C(a~) are examined one by one and each is either added to the formula associated to class 0, or added to the formula associated to class 1, or left out. Also, the order of the elements in the class is important so all graphs selection orders must be examined. So the number of decision lists is equal to: Ik - C(a,)DL I = 31k-c(~,)l(Ik - C(~,)l)!
(6)
And consequently:
log(Ik -
C(,,)DLI) =
O(Ik
-
C(.,)l) = O((0~10/2013) k3)
(7)
The identification algorithms for the two classes we are interested in follow. These two greedy algorithms are based on the simple observation that any concept consistent with a sample set is necessarily consistent with any of its subsets. Therefore, both consist in selecting graphs which are consistent with a subset of the sample, adding the graph to the current formula and removing the examples correctly classified. When all the examples have been removed, a consistent formula has been constructed. If at anytime, this proves impossible, then the non consistency of the formula has been detected.
312
Tables 1 and 2 describe the identification algorithm for disjunctions. Every time a graph consistent with a part of the sample is found, it is ORed to the current disjunction. If all possible graphs have been examined and some examples are left unexplained then no disjunction is consistent with the sample. Indeed, the disjunction being commutative, the order of graph selection is unimportant and the concept class need only be searched once.
BuildDNF DNF := MakeEmptyDNF() ; LS := ExamplesSet ; WHILE NotAllNegative(LS) DO CurrentGraph := SearchPositiveGraph(LS) ; LS := LS -- ExamplesSatisfiedBy(CurrentGraph) DNF := DNF + CurrentGraph; END Return DNF; END
;
Table 1. Pseudocode for building a CG disjunction.
Sear chPositiveGraph (LS) CGraph = Make extensive search of a CG satisfied by positive examples; Return CGraph; END
Table 2. Pseudocode for extensive search of a CG consistent with positive examples.
It is obvious that for both classes, if Ik- C(~,) is polynomial in a i and the projection test is also polynomial in these parameters, then the two above algorithms also are. Two classes to which this result applies are Conceptual Trees 17 and locally injective Conceptual Graphs 14. Although their expressivity is not as good as unconstrained conceptual graphs, their combination in more complex formulas yields very interesting concept classes for learning. Disjunction Normal form formulas are thought to be natural knowledge reprewsentations for the human brain 25. Decision Lists are also very easy to interpret because they axe lists of easily understandable rules. Besides, they axe among the most general known PAC learnable classes. The extensions defined above are likely to prove very efficient and interpretable in learning applications.
313
BuildDL DL := MakeEmptyDL(); LS := ExamplesSet; WHILE NotOnly0neClass(LS) DO CurrentGraph := SearchGraph(LS); LS := LS -- ExamplesSatisfiedBy(CurrentGraph); DL := DL + CurrentGraph; END AddDefaultClass(LS); Return DL;
END T a b l e 3. Pseudocode for building a CG decision list.
SearchGraph(LS) CGraph = Make extensive search of a CG satisfied by examples from only one class; Return CGraph; END
Table 4. Pseudocode for extensive search of a CG.
5
Conclusion
In this paper, we have studied the practical learnability of classes of conceptual graphs. We have first presented a formal leaxnability model derived from the famous PAC learning framework which we have adapted to make it suitable for the analysis of graphs. This is our main contribution because it paves the way to other studies. In particular, we have shown that conceptual graphs, in their general form 3 do not allow PAC learning, under widely accepted complexity assumptions. This negative result being linked to the NP-Completeness of the projection test, we have then studied the possibility of learning classes of graphs for which basic algorithmic operations are polynomial, and shown that results become positive in this case. Finally, we have shown that graphs of limited size allow efficient learning not only as isolated concepts but as basic building blocs of more elaborate formulae which extend well known boolean concept classes. This type of extension of existing boolean formula classes has already been formally studied in 10 where various Description Logics were shown to be adequate extension languages. Here the results are different further since restricted conceptual graphs play this role. It would be ineteresting to compare the expressivity of the resulting classes in both cases. Another interesting extension would be to examine learning graphs rules, such as those presented in 20. This could not be done in this paper because a (polynomial) rule generation mechanism from example graphs would be needed to build
314
an indentification algorithm. However, the structure of these rules being an extension of function free Horn clauses quite similar to the extension of boolean formulae defined above, it is quite likely t h a t positive learnability results could also be obtained (with the same size limitation on graphs) by using some inference techniques of Inductive Logic Programming. Finally, the various PAC results presented in this work are just early learning results and are only meant to p a t h the way to more extensive studies. It should be noted t h a t the PAC framework has become a benchmark model over the years, but is by no means the only interesting one. In fact it makes severe assumptions which may bias learning results 11. Thus, it would be most interesting to study the learnability of conceptual graphs in newer models. In particular, U-learnability 16 comes to mind. Indeed, two of PAC's drawbacks are its distributional assumptions and the worst case analysis which makes a polynomial projection mandatory. This last point is a m a j o r handicap since in practice the NP-Completeness of the projection test is never a handicap and efficient algorithms have been incorporated in most applied systems.
References 1. A. Blumer, A. Ehrenfeucht, D. Hanssler, and M. K. Warmuth. Learnability and the vapnik-chervonenkis dimension. J. ACM, pages 929-965, 1989. 2. R.J. Brachman and J. Schmolze. An overview of the kl-one knowledge representation system. Cognitive Science, 9:171-216, 1985. 3. M. Chein and M.L. Mugnier. Conceptual graphs: Fundamental notions. Revue d'Intelligence Artificielle, pages 365-406, 1992. 4. W. W. Cohen. Pac-learning non-determinate clauses. In Proc. of AAAI-94, pages 676-681, 1994. 5. W. W. Cohen and H. Hirsh. The learnability of Description Logic with equality constrain ts. Machine Learning, pages 169-199, 1994. 6. S. Dzeroski, S. Muggleton, and S. Russel. Pac-learning of determinate logic programs. In Proc. of the 5 th International Conference on Computational Theory, pages 128-137, 1992. 7. D. Genest. Document retrieval: An approach based on conceptual graphs. Rapport de Recherche LIRMM No 97296, 1998. 8. E.M. Gold. Language identification in the limit. Information and Control, 10:447474, 1967. 9. D. Haussler. Learning conjunctive concepts in structural domains. Machine Learning, 4:7-40, 1989. 10. P. Jalopy and O. Gascuel. On the conputational hardness of learning from structured symbolic data. In Proceedings of the 6th Internationl Conference on Ordinal and Symbolic Data Analysis, OSDA95, pages 128-143, 1995. 11. P. Jappy, R. Nock, and O. Gascuel. Negative robust learning results for horn clause programs. In Proc. of the 13 ~h International Conference on Machine Learning, 1996. 12. J.U. Kietz. Some lower bounds for the computational complexity of inductive logic programming. In European Conference on Machine Learning, ECML'93, pages 115-123, 1993.
315
13. R.K. Lindzay, B.G. Buchanan, E.A. Feigenbaum, and J. Lederberg. Dendral: a case study of the first expert system for scientific hypothesis formation. Artificial Intelligence, 61:209-261, 1993. 14. M. Liqui~re. Apprentissage ~ partir d'objets structurds. Conception et Rdalisation. PhD thesis, Universit6 de Montpellier II, 1990. 15. S.H. Muggleton. Inductive Logic Programming. Academic Press. New York, 1992. 16. S.H. Muggleton. Bayesian inductive logic programming. In COLTg$, pages 3-11, 1994. 17. M.L. Mugnier and M. Chein. Polynomial algorithms for projection and matching. In Proc. of the 7th Workshop on Conceptual Structures, pages 68-76, 1992. 18. R.H. Richens. Preprogramming for mechanical translation. Mechanical Translation, 3, 1956. 19. R.L. Rivest. Learning decision lists. Machine Learning, pages 229-246, 1987. 20. E. Salvat and M.L. Mugnier. Sound and complete forward and backward chaining of graph rules. In Proceeding of the International Conference on Conceptual Structures, ICCS96, pages 248-262, 1996. 21. R. Shapire. The strength of weak learning. Machine Learning, 5(2), 1990. 22. E.Y. Shapiro. Algorithmic Program Debugging. Academic Press. New York, 1983. 23. J.F. Sowa. Conceptual Structures - Information Processinf in Mind and Machine. Addison-Wesley, 1984. 24. L. G. Valiant. A theory of the learnable. Communications of the A CM, pages 1134-1142, 1984. 25. L. G. Valiant. Learning disjunctions of conjunctions. In Proe. of the 9 th IJCAL pages 560-566, 1985.
Procedural Renunciation and the Semi-automatic Trap Graham A. Mann Artificial Intelligence Laboratory School of Computer Science & Engineering University of New South Wales Sydney, NSW 2052, Australia. [email protected] Abstract. This paper addresses two contemporary issues which could threaten the usefulness of conceptualgraphs and their widespread acceptance as a knowledge representation. The first concerns the recent debate over the place of actors in the formalism. After briefly summarising arguments on both sides, I take the position that actors should be retained, and marshal four supporting arguments. An example shows that (slightly enhanced) actor nodes can greatly simplify the delivery of external control signals, without excessively comphcating the denotation of the graphs they contain. The second issue concerns an epistemological problem which I have called the semi-automatic trap. This is our tendency to continue constructing systems of logic that depend on human involvement beyond necessity to the point at which such involvement is impractical, unscaleable and theoretically problematic. Two important escape routes from the semi-automatic trap are pointed out, involvmg more emiohasis o n automatic graph construction from primitive data, and emphasis o n automatic interpretation of conceptual graphs. Practical methods for both are suggested as ways forward for the community.
1
Introduction
Recently, the conceptual graphs (CG) community briefly debated the role of, and suitability for inclusion of actors, the angle-bracketed procedural nodes outlined the original theory, within the newly emerging ANSI standard. The exchange took place over a few weeks in the electronic forum of the CG mailing list. On the proelimination side, it was argued that actors are unnecessary in that existing elements of CG theory can effectively be used to do all that is claimed for actors without further complicating the standard; and were formally problematic, syntactically because their linear form symbols already have assignments and semantically because their denotation is at best awkward and at worst impossible to specify. Putative mechanisms for enabling naturally stepwise processes, to be handled by CG systems without actors were discussed. Those arguing for retention held that these alternatives lead to a different set of problems, and that explicit tokens of procedural knowledge are intuitive to use and strategically prudent, since industrial developers want them as connection points to their chosen programming language. Actors were claimed to provide needed ways of capturing concepts with extensions that are unbounded sets, changing the values of referents, and sending and receiving messages from outside the CG system. The outcome of this exchange was a kind of compromise, articulated by Sowa, in which actors are viewed as calls in a functional language, with a distinction drawn between "impure" and "pure" actors, meaning whether or not the function involved left side effects. Pure actors are much like relations and so could be expressed using the round-bracket or circle syntax, but would be defined by the named function, not the relational catalogue. Impure actors could pass control signals back and forth to concepts in the graphs to which they are connected, and may have irreversible effects outside the
320
system. Actors would be included in the forthcoming CGIF draft, but only the pure variety. In order to include impure actors, provision for actor-tokens in the referent field of a concept would need to be made, and a metalanguage statement amounting to a declaration specifying the possible inputs and outputs would need to be provided somehow; these were left as tasks for the future. In the first part of this paper, I will marshal a number of arguments which further substantiate the role of procedural tokens as an indispensable part of any knowledge formalism and make the case for a stronger role for actors in both the theory and practice of CGs. In the second part of this work is both a cautionary note about a risk to our efforts which is so pervasive that it is difficult to see clearly, and a response to what I see as our community's curious ambivalence about tools and implemented systems. On the one hand, we all recognise the need for standardised tools, and admire good applications of CG technology. Yet until only last year, papers about these subjects tended to be excluded from the main proceedings of our conferences, while discussions about such things were practically relegated to separate events. As funding for public sector research in many countries is being reduced, industrial sponsorship becomes more important than ever - yet for the most part our attention seems to be directed elsewhere, on minutiae. This is not a suggestion that pure research on this topic be abandoned, but only that striving toward a mathematical ideal not blind us to what will really make our efforts count in the long run - the widespread adoption of CGs in the knowledge-based societies of tomorrow. I will argue that these conflicts stem primarily from different views we hold about what CGs are to be used for. Some of us are interested in the notation itself and its formal properties. Others are applying the formalism and the algorithms implementing its denotation to make new kinds of databases, retrieval mechanisms and other information technologies. Still others are chiefly interested in knowledge representation and automated reasoning for artificial intelligence. Often the differences between these groups can be ignored. For the purposes of this exposition I will exaggerate the differences between these three professional viewpoints - the logician, the informationsystem builder and the intelligent-system builder - and show how each is affected by what I call the semi-automatic trap. This is our tendency to continue constructing systems of logic that depend on human involvement, beyond necessity into realms where such involvement is impractical, inefficient and theoretically problematic. Partly following from traditional Platonic epistemology (Rationalism) and its modern extensions, and partly a consequence of the seduction of the computer, the semiautomatic trap has ensnared the CG and other symbolic approaches to the study of artificial reasoning. After identifying the main features and implications of the semi-automatic trap, I point out two important escape routes, both involving full, rather than partial, automation. First, the emerging interest in acquisition of conceptual structures from simpler symbolic constituents can be viewed as the beginnings of a reaction to the prevailing inward-orientation of CG work. A sketch is offered of an experiment in which conceptual knowledge is collected from more primitive grades of data. Second, the more difficult issue of interpretation of conceptual structures by automatic means will be briefly considered. It is suggested that the label fields of nodes be made switchable, so that the developer can toggle between mnemonic labels and meaningless but systematic labels. A recommended principle to guide progress toward automatic interpretation - that we begin the transition from truth-preserving algorithms to plausibility-preserving heuristics - is illustrated with a simple example. Except for one instance, the practical demands imposed by the development of commercial systems will be seen to exert a healthy influence on these issues.
321
2
The Role of Actors
Let us begin with the role of actors in CG theory. In the debate mentioned above, writers on both sides commented that actors tended to be left out of many conceptual graphs appearing in published papers (except those used in commercial systems). The idea that actors are somehow unnecessary is a contemporary instance of the current ascendancy of declarative accounts of knowledge over procedural accounts. This orthodoxy holds that declarative formalisms (including programming languages, knowledge bases and models of brain function) are cleaner, more economical and more transparent than procedural versions. While many epistemologies pay lip service to the need for a balance between the two, the models they lead to rarely seem intermix them. Procedures are often portrayed as outdated, of limited portability, and resistant to learning or explanation. They are sometimes associated with bad programming habits in old-fashioned languages, hacking, and scruffy methodology. Some attempts to incorporate procedural elements in knowledge models began to be seen in the 80s in the KL-ONE modifications, KRYPTON 1 and B A C K 12, OMEGA 5 and CycL 8. Original CG theory 14, also a product of the 80s, showed foresight in permitting actors to influence and be influenced by concepts, even if the examples given were simple mathematical functions, which tended to foster the view that they are nothing more than a special kind of relation. At the end of this section, I will show how actors may be transformed into parameterised procedural calls in a way which has less to do with relations. Good reasons why procedures should be "tolerated" in CG epistemology were recently advanced by Rochowiak 13. Beginning from a classical philosophical definition of knowledge as justified true belief, he argues that declarative and procedural forms can be distinguished in each of these three definitional terms. The relationship between the two is complex, at least in the case of human knowledge: they share concepts, interact in complex ways see 6 and Rochowiak speaks of a "natural history" of (scientific) knowledge in which if unarticulated skills are sufficiently important to continued scientific enterprise, they are promoted through the heuristic level to a "context-free" level which is distinct from, yet dependent on, the prior procedural form. As usual, Charles Peirce seems to have beaten us all to the conclusion that knowledge must combine the declarative and procedural. As Rochowiak points out, Peirce was strongly committed to a view of concept meaning which fused the formal and practical. This commitment can be seen in his famous pragmatic maxim, one expression of which was: "Pragmatism is the principle that every theoretical judgement expressible in a sentence in the indicative mood is a confused form of thought whose only meaning, if it has any, lies in it's tendency to enforce a corresponding practical maxim expressible as a conditional having as its apodosis in the imperative mood. " 3: 5.18 Using the vocabulary available to him, Peirce was suggesting that conceptual knowledge be thought of as rule-like pairs, with an imperative apodosis (consequent), or what today would be a procedure in the rule's then-clause. This is the essence of today's expert systems. Of course, rules may have simple assertions or variable assignments in their then-clauses. But Peirce continually used the word "practical" in his definitions of the maxim, which means that he understood the centrality of active outcomes, in the broadest sense of that word. Furthermore, even a cursory examination of Peirce's work reveals the importance he attached to idea of knowledge as a dynamic, evolving entity which emerges from and is critiqued by social processes in a community. His ambition of creating a process by
322
which knowledge can be refined by successive elaborations of a publicly-readable graphical expression by members of a scientific community would, in the modern context, be a call to negotiate knowledge between the contributions of a multiple agents. His pragmatism was an attempt to overcome, or at least make tractable, the problems of logic theory, which in the words of Peircian scholar Ernest Nagel "...derive almost entirely from isolating knowledge from the procedures leading up to it, so that it becomes logically impossible to obtain." 2. These deliberations suggest that the procedural aspects of knowledge should not be factored out. Perhaps this idea has not been realised for historical reasons. In the late 1950s, computer science theory bifurcated into traditional stepwise control methods for a state-machine emerging directly from von Neumann's work on the one hand 17, and mathematical function-based models, on which for example McCarthy based his Lisp 9, on the other. At each turn, as simple data structures and control metaphors gave way to more sophisticated schemes, the declarative was presented as the more refined, explicit, portable and formally backed. As notions of conceptual knowledge as logic developed, this backing became connected to the solidity of truth-conditional logic. Languages based on this idea could have very simple and elegant interpreters, since they essentially only needed to return truth values for expressions they evaluated. (Of course, practical functional languages do concede a need for incremental changes of state to get things done, but only reluctantly, as signified by the disdainful term "side-effects".) This simplicity is appealing enough to help perpetuate the erroneous notion that what is important or interesting about expressions in a knowledge language can always be captured by mapping it to a Boolean value. I have argued elsewhere 10 that for some purposes, truth-conditionally is simply not adequate as an answer to the question: "what does this expression mean?". Though conceptual graph theory p e r s e requires no specific commitment to a particular semantics, much of the existing CG literature favours the truth-conditional variety, possibly in respect of its classical logic roots. But to the extent that conceptual graph theory has taken up the tradition, it has also inherited nagging questions about truthconditionality. Is the truth of a statement always the only aspect of interest? Under what conditions, if any, is it meaningful to assign a truth value to a statement about the future? To an imperative statement corresponding to the sentence "Go down these stairs."? Will the truth value be the same before and after the interpreter complies with the act? What relationship do truth-conditions have with the intentions of the speaker, the intentions of the hearer, or the hearer's active response? Now conceptual graphs can and have been used with other, more progressive semantics, including situation semantics 15 and four-pole semantics 10. The point here is that as long as the meaning of a conceptual graph is thought of as only a single Boolean variable, it is easy to ignore the need, in many cases, for an ordered sequence of active steps - a procedure - to be the substance of the graph's interpretation. So if we wish to define the pragmatic of conceptual graphs in terms of conceptual graphs themselves, we need to be able to explicitly encode procedures in the CG formalism. In one sense, this is really no great imposition: procedures of one kind or another are an integral part of CG theory, e.g. the canonical formation rules. The real questions are, what formalisms should be used to encode these, and what expressions should they have inside graphs? Why would we want to make the contents of procedures (as apposed to only explicit tokens of procedures) explicit within CGs? The principle reason is that changes to declarative aspects of graphs during reasoning can affect procedures and changes in the status, or progress, of procedures can then influence reasoning, by virtue of their common elements. But this could also be viewed as a problem for two reasons: because we do not have and may not wish to introduce a suitable language into the CG
323
formalism itself, and because it would cluttered up otherwise clearly understandable graphs. Without actors betokening procedures, definitions of ACT concepts - at least, those expressed in conceptual graphs - will in a sense always be empty. Imagine by how far the expansion of the concept SAMBA would miss the mark if it could not at any point provide access to some kind of (simulated or actual) sequence of motions. One might expect the definition-graph to classify the concept, declaratively, as a subtype of LATIN-DANCE, and perhaps add, also declaratively, salient features such as modernity and tempo. But such a definition could never be wholly satisfactory as a surrogate without some representation which could replay the pattern of steps in time so as to demonstrate, or facilitate recognition of, the actual dance itself. Dictionaries attempt to capture the meaning of the word "samba" without recourse to such replays but this is one of the reasons that machine-readable forms of conventional dictionaries are, by themselves, inadequate as a basis for commonsense knowledge. And movies or simulations of acts are one of the things we want to provide in a modern multimedia dictionary. An alternative to explicit actor nodes has been proposed in Sowa's object-oriented carstarting example 16. External processes, in this case the ignition of a car's engine, could be provably initiated from a conceptual graph built on an object-oriented software model. Messages could be sent to and from objects that appeared to be concept boxes labelled with process names to other process-objects, not shown on the graph, and presumably more closely connected with the physical engine. Ellis 4 subsequently criticised this design as awkward, but his own simpler model still encounters the basic difficulty of trying to describe declaratively what is essentially a procedure, and it still seems to miss the point. Concepts and relations should not be used as surrogates for active processes; they are statements of existence relative to an ontology. A more pragmatic question lurks beyond these complaints: even if we were satisfied with this kind of solution, do we really want our knowledge formalism to commit the user to a particular computational model? Given the popularity of the object-oriented programming approach, perhaps it is not a serious disadvantage - but it seems onerous to demand that CG developer must sign up with the object-oriented paradigm, when all that might be needed is a simple escape to the code level. It is not difficult to imagine design scenarios in which this tips the balance against the adoption of CGs. Figure 1 shows how actors would be used to produce a natural model of a car, without appealing to a particular computational paradigm or language. The referent of the concept MAX-DUR, *d, is functionally related to the referents of CAPACITY and FUEL-CONS by the "pure" actor DIVI, which divides the capacity of the tank, *c, by the rate of fuel consumption, *f. In the active interpretation of this, the output of DIVI is placed in the referent field of MAX-DUR. Execution of the procedure can be either data-directed, in which processing begins with values in the input nodes, or goal-directed, in which processing begins with a requested value at the output node, and propagates backwards to the inputs. These processes are initiated by the assertion mark ! and the request mark ?, respectively. The "impure" actor START, is not relation-like, but can be read as a state-changer. It is a procedure which can be initiated by a control mark in the ENGINE concept. The existence of a particular key is a precondition for the procedure and only when the referent *k is bound to PCX999 will the precondition be satisfied. Before the signal to start arrives, the first placeholder acts like a concept which needs to be restricted to the value KEY:PCX999. The ignition process creates side-effects, including rotation, heat and noise in the outside world; these may be measured by sensors and reported back to the CG system. At the end of the START process, a tachometer reports a number of
324 J RUNNING:@*r
\ TANK
I~-~ib zx~'rl),~-~l AUTOMOBILE
t
ENGINE
J J MAX-SPEED: , ~ *s FUEL-CONS:*f
I
I I
Figure 1. Alternative model of a car. revolutions per minute, *r, back via the second placeholder, which is then data-driven to the referent field of RUNNING with the prefix @. Syntactically, the actors may be represented using a LISP-like functional notation in which the list delimiters are the < and > angle brackets, the first element is a procedure name, the last element is a place holder for the returned value, and all other elements are an ordered list of input parameters.
325
since any variable must be universally quantified. This means that actors could appear in first-order logic expressions without interfering with their quantifications. Within the predicate for the concept connected to the output of the actor, ~ places a second element: a function with the input variables as arguments. Thus the DIVI actor in Figure 1 would appear as .... A (MAX-DUR, (DIVI (a, b)) A ... If desired, the output variable *c could be equated to the function elsewhere in the expression. The above arrangement is simple to understand and allows the graph's declarative nodes to interact with the actors. Suppose it was learned that the engine of the car has been replaced with a different engine. When the graph is updated to reflect this, the new instance will have a new characteristic fuel-consumption. Because of the actor connections, the maximum duration and range will automatically alter to reflect this change; yet it is difficult to imagine natural relations which could be used to link FUEL-CONS with those two concepts. From a goal-oriented perspective, if an engine was stationary and the goal was a non-zero speed, this could trigger a search for a key, which also could not be done naturally with a relation. Notice, however, that only the actor tokens can influence and be influenced by the declarative nodes: the elements of the procedure itself are beyond reach. For this reason, we may still wish for code which had explicit statement inside a graph, perhaps as chains of linked actors representing the subroutines of complex actions. In human beings, only our highestlevel plans are available to our reflection; lower level acts, those which have become automatised, as psychologists say, are not available.
3 The Semi-automatic Trap Let us turn now to another risk facing our community: the semi-automatic trap. This is our tendency to keep building systems of logical symbols that depend at least partially on human involvement for their creation, manipulation and interpretation. That is a serious problem for builders of intelligent systems, and to a lesser degree for information-system builders and logicians. The semi-automatic trap is best understood in its historical perspective. Logic has a long history of being done by humans on paper. The symbols which are used in a typical logic have a long aetiology. Perhaps they include Greek letters, betraying their Platonic ancestry. Essentially, these symbols are passive, mnemonic devices, designed to signify objects, classes or operations by triggering the associated ideas inside human brains. They are created by human beings for human manipulation and human interpretation. For most of their history, and in most of their applications, this role for logical symbols as manual tools has been uncontroversial and unproblematic. The decades-long revolution which has placed a computer on every desk offered rich opportunities to practitioners of logic, builders of information systems and artificial intelligence researchers, among countless others. Yet the advent of computers can now be seen, with the benefit of hindsight, to have loaded the semi-automatic trap, ready to be sprung. In their ubiquitous incarnation as semi-automatic machines - that is, devices which accept symbolic input from users via a keyboard, process them, and display symbolic output for human eyes via a screen - desktop (and laptop and palmtop) computers have human dependence built in as a basic affordance. For the greater part, the software which has been developed on such machines also tends to depend on human intervention via this interface. This too seems natural enough.
326
But this built-in, natural dependence can work against us when we try to use those machines and logic symbols to build symbolic structures which can behave like human conceptual knowledge, for the following reasons. First, the culture of logical mnemonics carries certain unstated assumptions with it. For example, although a symbol could in principle have a extensional grain size of anything from a highly specific and nameless microfeature to a broad metaphysical category, the symbols used in practice tend to cluster around a narrow range of possible grains associated with convenient words used for their labels. The fact that concepts have to be named could push hand-built ontologies away from the microfeatural to a coarser resolution. Second, mnemonic symbols can easily be parasitic for their true meaning on the human viewer, that is, they could merely draw on associations, inference mechanisms and the like in the head of a developer, or user, instead of supplying them itself. It is surprising how much this blinds us to the need for an interpretative component inside the system. Third, the tradition of logic still leads us to think of conceptual knowledge in terms of verifying propositions, and that truth-conditional semantics might be sufficient as a denotation for any conceptual structures. This again leads to the neglect of active procedural output as part of meaning, as discussed in Section 2. Let me make the problem clearer by taking it to extremes. Consider for a moment the fact that natural existence proofs of intelligence - humans and (more problematically) animals - have no screens and keyboards. If, as we wish to maintain, symbolic conceptual structures exist within their brains, then keyboards and screens cannot be a necessary condition for intelligence. But think of the disservice that would be done to most intelligent machines - and surely every CG program - if the screen and keyboard were removed. This will be my basic test for a system caught in the semi-automatic trap - will it continue to function and be useful with the human-dependent I/O devices disconnected? The reader may well object that this is test is uncharitable. After all, animals (including humans) and computers are really very different. Animals arrive with a genetic legacy, which might include innate conceptual structures and the machinery to support them. Computers are general-purpose machines to which any structure must be supplied - and this is ultimately a screen and keyboard job. To make a fair comparison, then, the machine does need a screen and keyboard. Very well - let the original test be modified as follows: the builder may stand in for Nature, supplying any programs and data that the system needs, but during the design phase only. Once the program is finished (born), the screen and keyboard must come off. The test still seems absurd because we have not yet exhausted the differences between animals and computers. Animals have sense organs and bodies with actuators, and these serve as I/O channels to the world. But - and this is important to full understanding of the issue - those channels do not depend on the manipulation or scrutiny on the part of a external human, as screens and keyboards do. Even in a human being, they do not: they serve a human brain, and could be influenced by or influence an external human in various ways, but they do not depend on it. Note that if the computer had other I/O devices with this property, such as cameras, microphones, sound generators and motors, they must remain connected during our test. We only wish to disable the machine in a specific way, so that it reveals its autonomy or the lack of autonomy. Am I serious when I demand that CG-based devices be useful without their screen and keyboard? Not entirely. To disqualify screens and keyboards on the grounds that they permit a kind of epistemological cheating is to oversimplify, because it ignores the fact that these devices can also be used to stand in for more complicated, and possibly less useful, "natural" I/O such as speech and hearing. We may be very satisfied, for example, with a natural language program that communicates using ASCII text,
327
provided we stay vigilant against other uses of the screen and keyboard which commit humans to too much of the wrong kind of involvement. This is the kind that does not relate to natural communication with the functioning program and would not be possible if the program were a person i Furthermore, it oversimplifies because some purposes of logicians and informationsystem builders may correctly demand no more than semi-automation. A successful logic visualiser might be essentially a tool for human work, like a calculator or spreadsheet. In these cases, it could be argued, the semi-automatic trap is really no trap at all. Even here, though, much of the motivation of tool developers lies in the potential they see in computerising conceptual structures to free human users of the need to carry out the time-consuming, repetitive or difficult parts of logic work - and this means automation. Of course, individual systems might pass the test, with their designers successfully avoiding the seductive powers of the screen and keyboard, and using their computers to try to write truly automatic programs that collect their own data, form their own goals, build their own representations and draw their own conclusions for action. The trouble is that we can s e e m to be building systems capable of human-like conceptual processing, when what we are really doing is only building systems that help people to do so. Disguising this mistake is the fact that, at least in information-retrieval systems, even a semi-automatic program could be quite useful. In fact, some information-system builders argue that a semi-automatic "intelligence amplification" (IA) approach is the best we can hope for at present, or even that this is better than AI altogether, since it preserves a human role in these affairs. But builders of autonomous agents, intelligent reasoning systems and true (that is, non-teleoperated) robots must avoid the semi-automatic trap to build automatic machines, because these devices must function independently. These builders cannot get away with thinking representations are all there is to knowledge. Again, we can visualise this in terms of the ability of such devices to operate without a keyboard and screen plugged in, even if they were needed to start the programs. A final barb that may hold us in the semi-automatic trap is that of power. I mean this in a more specific sense than notions of technological dominance or "knowledge is power". If responsibility and power are opposite sides of the same coin, it follows that human involvement in the knowledge process grants us power over it. In the artificial realm of symbols on a blackboard, the logician presides as god, letting this or that assumption be true, assigning variables, defining axioms and applying stepwise procedures. In the methodology of conceptual graphs, we proclaim the existence of types which divide aspects of reality into meaningfully distinct atoms, forming the basis of an ontology. The authority for this act is that of the knowledge specialist, or domain expert. Such persons naturally occupy positions of power in our technocratic society. And if the ontologies that are derived from their proclamations were in turn to form an obligatory language to which all artistic, scientific, commercial or military participants in a knowledge-mediated discourse have to conform, the focus of power would become very tangible indeed. 1. One might argue that language is an exception, because it is essentially about communications with other human beings, and thus dependent on them. But human speech is based on vocal apparatus which can produce sounds for other purposes, and auditory sensors which are used to detect many kinds of sounds besides speech. And of course, both can operate meaningfully even when there is no external human present. The same cannot be said of a keyboard and screen.
328
A number of critics have warned that society could find itself mired in a kind of ideological determinism instrumented by information technology e.g. 7. Particularly applicable here is the risk of opportunism on the part of an organisation or company that establishes an comprehensive ontology defining all the concepts, relations, contexts and actors for an industry as a bid for control of that industry. If one powerful organisation controlled these element, it could be difficult or impossible for outsiders to get new ideas recognised, or to communicate ideas which fell outside those terms of reference. The concern is that the organisation could disguise its attempt to monopolise the discourse by claiming that it was simply establishing a useful knowledge standard. But engineering standards for knowledge interchange should not be permitted to lead towards standardised knowledge content. Our community should be on its guard about this, so that our innovations do not become yet another pillar of inequality. If as we oversee the construction of large, shareable ontologies we are to avoid the twin evils of hard labour and ideological monopoly, we must become willing to take our hands off the levers of power to some degree. Since humans and their institutions tend to seek to consolidate power, not relinquish it, this barb can be expected to be the sharpest of all.
3 Fully Automated Acquisition In the CG community, we tend to neglect knowledge acquisition. In a set of 148 papers from ICCS meetings of the last five years, only 17 mentioned knowledge acquisition at all, and fewer discussed the topic in any detail. Concepts and relations appear in the catalogues of practically all CG systems as a matter of design-time proclamation, which is to say, human judgement. Neglecting other means of gathering knowledge tends to lock in proclamation as the only method of establishing knowledge using CGs. That may discourage experienced knowledge engineers looking for improved technologies for their craft, who know that manual knowledgebase creation and maintenance is potentially so labour-intensive that it may make their systems unacceptably costly. Perhaps CG developers are beginning to see the cruciality of this issue: whereas only 3 of the 56 papers in 1992 concerned this topic, this had risen to 9 out of 48 papers by 1997. Now consider what the semi-automatic trap has to teach us about knowledge acquisition. If, as in the above reductio ad absurdum, conceptual graph systems were not permitted to use a screen and keyboard for more than the initial system specification, would knowledge acquisition become impossible? Evidently not, because humans and animals can learn. But, for the sake of argument, how would it change under this restriction? The term "knowledge acquisition", as it is conventionally used, means encoding knowledge which has come from asking human beings (experts). Sometimes it takes on a slightly broader sense, in which; the knowledge may come from other sources like models, or books. "Asking a human" sounds like a natural process, available to a person and not likely to be disabled by removing the screen and keyboard from a computer. But of course, what almost always actually happens is that another person elicits the knowledge from the expert, casts the knowledge into the representation formalism by hand and then types it into the system by screen and keyboard. This would not be possible in a system in which these two devices were disconnected, that is, once the system was deployed. We could, of course, imagine a system in which deployment was delayed until all the knowledge it would ever need was built-in at design time. This would be a model of
329
totally innate knowledge. New knowledge could be had within the deployed system, but only by derivation from the innate supply. Perhaps, with great foresight on the part of the designer, such a knowledge system would be adequate. By analogy, most commercial programs are sold without their source code, with all information they need sealed into the executable code. But this strategy seems inherently risky. A system closed off from external change seems to lack an essential flexibility. It is precisely this sort of inflexibility that makes us seek more advanced forms of software than conventional programs. The alternative would be to use I/O devices which are allowed to remain connected (or, in the liberal interpretation of the rule, to use the screen and keyboard for natural exchange only). To do that, the human knowledge elicitor must be replaced. This means creating not only a natural language interface, but also a program to conduct the elicitation process, automatically generating the graphs for expression as questions, and a method for automatically dealing with the conceptual graphs that result from the parsing of the expert's responses. Since I have written elsewhere about parsing and learning by asking 10, I will focus here on this method. SKB
EKB
PKB
Syllabus
Figure 2. A teachable CG knowledge machine. Figure 2 describes a CG machine containing three knowledgebases: 9 SKB, the semantic knowledgebase, consisting of conceptual, relational and actor hierarchies. 9 EKB, the episodic knowledgebase, a sequential list of conceptual graphs, representing the conceptual history of the system. 9 PKB, the procedural knowledgebase, containing the source for actors defined in the system. This could be as simple as a set of listings of Lisp functions. The acquisition process depends on a special teaching language in which a range of operations on these databases may be expressed in simple fashion. Such a language would be something like the Structured English Interface for the Deakin Toolset 11, except that additions and changes to the conceptual hierarchies as well as the construction of graphs based on them would be allowed. The procedural knowledgebase would need a theoretically different set of techniques for skill learning, which will not be addressed here. For example, the following sequence of expressions sets up a
330
situation in which a hungry bear is inside a cave, beginning with no concept of bear or cave:
NEWCON DEFCON
BEAR < ANIMAL BEAR (A'I~R FURRY ATFR COLOUR:Brown LOC PLACE EATS ANIMAL) CAVE < LANDMARK CAVE (CHRC DARK CONT ROCKS CONT BATS)
BEAR1 G105 ASSERT
JOIN (BEAR EXPR HUNGER) JOIN (CAVE CONT BEAR1) G105
NEWCON DEFCON
The "interpreter" (in the specific technical sense of a parser-executor of strings in an artificial language) of Figure 2 chooses appropriate operators such as copy, restrict, or join and decides how to apply these to update the SKB and EKB. In most cases, the opcode of an instruction should be enough to select the correct knowledgebase, since the operations appropriate to hierarchy-building and episodic memory are different. Instructions concerning operations on individual graphs would use local variables to hold the graphs until a command sent the graph to a specified knowledgebase. The course of knowledge to be learned will be introduced in a specially prepared sequence of these expressions in this language, called a syllabus. The syllabus would be written by hand, which might at first glace seem to defeat the notion of automating acquisition. However, until we are prepared to construct much more sophisticated perceptual devices (such as a camera which returns conceptual graphs describing objects and events in its field of view), the data which informs the learning process must come from such human-mediated sources. Since advanced raw-data-to-CG converters seem far off, our efforts to reduce human involvement are compromised. It might instead be hoped that the simple teaching language, beginning from a form like that described above, would evolve with experience, so that frequently recurring patterns of operations were eventually chunked up into powerful elements of a higher-level language. Ideally, the high-level form would both decouple the content of the material from the operations, thus allowing syllabuses focus primarily on content, and to be shorter and easier to write.
4 Fully Automated Interpretation Given that the goal is creating a system for intelligent reasoning and not a tool for manipulating logic, one way test that a system is not semi-automatic-trapped is to systematically replace all the mnemonics in the graphs - the type labels in the concepts, relations, actors and contexts - with "blind" labels such as random combinations of characters. If this disadvantages or disables the run-time system, it means that the symbols in the graphs are parasitic on the meanings in the user's head, and so is not fully automated. In practice, it would be useful to be able to switch between the arbitrary labels and mnemonic ones, since the mnemonics are legitimate and useful for design and debugging. Being able to turn off the mnemonics at run-time would force attention away from the graphs and onto the human-read/writable forms with which users of the system will deal. Let us assume, for convenience, that the form for users of a hypothetical system is natural language, and permit that to explain what is needed to automatically interpret graphs. Section 2 argued that a truth-conditional semantics is not enough. In 10, I
331
expressed this as the need to move beyond truth-preserving algorithms to plausibilitypreserving heuristics. What does this mean? Imagine that the natural language system is asked two questions: 1. .
"Can a rabbit fly?" "Can you arrange the names in file "customers.txt" alphabetically and send that to printerl?
To answer 1, a truth-conditional, truth-preserving approach can be tried. Once the pragmatic component of the system has recognised the form as a question, an attempt to join the definitions of RABBIT and FLY can be made, and since selectional constraints in the definition graphs should reject an attempt to fit two incompatible graphs together, an answer of "no", based on whether the join algorithm was successful, can be returned. Perhaps, though, it would be more convivial to return either the successfully joined graph or an error message that repotted what had blocked the join. This would avoid the embarrassment of a simple "yes" answer, in the event that the system had deduced that a rabbit was a suitable patient for transport by aeroplane. It is easy to show that to properly answer 2 it takes a plausibility-preserving, procedural heuristic approach to prevail. First, assume that the only procedure available which could possibly alphabetise the file is a generalised Sort function. The word "arrange" is insufficient to choose an operation, so the system searches all available acts for a suitable match. The way the match is performed is crucial to success here; it must be quite liberal if it is to cope with the many possible ways in which it might properly be summoned. Assuming the Sort function was found to have an optional parameter called "alphabetical", then it might be appropriate to use Sort(alphabetical, customers.txt). We could not know this kind of relationship with the certainty required for a truth-preserving algorithm. A heuristic enforcing only plausibility, on the other hand, could take such a liberty, and thus only it could succeed in this case. Second, in order to avoid the pragmatic howler of returning a yes-or-no answer to 2, the system must actively carry out first the sort and then the print operation. The "and" linking the two is not a Boolean conjunction, but a conditional link ordering two tasks. Successfully recognising the two clauses as a pipelined print operation and performing it is the interpretation of the question. If unsuccessful, some kind of error message representing an explanation would then be appropriate, as in 1.
5
Conclusions
By making provision for actors, CG theory has already prepared the way for progressing beyond the notion that description is all there is to representation. To address the shortcomings of formal knowledge representations which do not recognise the significance of procedural aspects of knowledge, more attention must be paid to both the tokens which mark their presence and to the active processes which substantiate those tokens. These processes cannot be completely divorced from the pragmatics of a CG system. It will not be enough to continue developing algorithms which manipulate CGs, without somehow recognising these explicitly within the graphs themselves. Ideally, the entire codification of an active process would appear in a conceptual graph, but this complicates the notation. At least actor nodes with the same names as coded procedures outside the system should be allowed for.
332
Those interested in the adoption of this formalism as a knowledge standard must also now progress beyond the notion that representations are all there is to knowledge. To create working knowledge for intelligent systems, it is important not to perpetuate passive symbols designed for human use. This engenders a kind of introspection which is compelling to system builders, and potentially aversive to commercial developers. More seriously, it carries the risk of building too much human involvement into the system. The semi-automatic trap is a gedankenexperiment designed to reveal this risk. By asking how knowledge systems would function without their screens and keyboards. it reminds us that these conduits can sometimes work against the development of true automated reasoning. Two escapes from the semi-automatic trap are briefly discussed: fully automated acquisition and fully automated interpretation. In the case of knowledge acquisition, too much human involvement is problematic because it commits the system builder to large amounts of collection and maintenance work on the knowledgebase. It also risks granting a great deal of power to any highlyresourced organisation which is able to manually create a large ontology. It would be preferrable to eliminate the human elicitor in knowledge acquisition. Although the suggested teaching experiment does not accomplish this, it may be a step in the right direction. In the case of interpretation, the ease with which humans take on the role of interpreter of symbols makes the human-readability of CGs a double-edged sword. Therefore I suggested that the mnemonic labels inside the nodes be able to be switched off, so that any parasitism of the system may be exposed. Our artificial reasoning systems will be better able to cope with the vagaries of real tasks when they use plausibility-preserving heuristics instead of truth-preserving algorithms. Truth preservation is important for maintaining the canonicity of true graphs during arbitrary transformations, but it might block sensible but unsound steps in the reasoning process. Such steps could be ubiquitous in commonsense thinking.
References 1. Brachman, J. et.al. Krypton: A Functional Approach to Knowledge Representation. IEEE Computer, 1983, 16, 10, 67-74. 2. Buchler, J. Charles Peirce's Empiricism. New York: Harcourt, Brace & Co., 1939. 3. Burk, A.W. The Collected Papers of Charles Sanders Peirce. Vol. 5. 4. Ellis, G. Object-oriented Conceptual Graphs. In G. Ellis, R. Levinson, W. Rich and J.F. Sowa (Eds.) Conceptual Structures: Applications, Implementation and Theory. Lecture Notes in AI 954, Springer-Verlag, Berlin, 1995, 114-157.
5. Hewitt, C., et. al. Knowledge Embedding in the Description System Omega. Proceedings of the First National Conference on Artificial Intelligence, Stanford, CA, 1980, 157-164. 6. Hiebert, J. Conceptual and Procedural Knowledge in Mathematics: An Introductory Analysis. In J. Hiebert (Ed.) Conceptual and Procedural Knowledge: The Case of Mathematics. Hillsdale, NJ: Lawrence Earlbaum Assoc., 1986, pp.l-27. 7. Lacroix, G. Technical Domination and Techniques of Domination in the New Bureacratic Processes. In L. Yngstrom, et. al. (Ed.s) Can Information Technology Result in Benevolent Bureacracies? The Netherlands: Elsevier Science Publishing Co., 1985, 173-178.
333 8. Lenat, D. et. al. CYC: Towards Programs with Common Sense. Communications of the ACM, 1990, 33, 30-49. 9. McCarthy, J. Recursive Functions of Symbolic Expressions and their Computation by Machine, Part 1. Communications of the ACM, 1960, 3, 4. 10. Mann, G.A. Control of a Navigating Rational Agent by Natural Language. PhD thesis, University of New South Wales, 1996. 11. Munday, C., Sobora, F. & Lukose, D. UNE-CG-KEE: Next Generation Knowledge Engineering Environment. Proceedings of the I st Australian Knowledge Structures Workshop. Armidale, Australia, 1994, 103-117. 12. Nebel, B. & v o n Luck, K. Hybrid Reasoning in BACK. In Z.W. Ras and L. Saitta (Ed.s) Methodologies for Intelligent Systems, Vol.3. North-Holland, Amsterdam, The Netherlands, 1988. 13. Rochowiak, D. A Pragmatic Understanding of "Knowing That" and "Knowing How": The Pivotal Role of Conceptual Structures. In D. Lukose, H. Delugach, M. Keeler, L. Searle & J.F. Sowa (Eds.) Conceptual Structures: Fulfilling Peirce's Dream. Lecture Notes in AI 1257, Springer-Verlag, Berlin, 1997, 25-40. 14. J.F. Sowa: Conceptual structures. Menlo Park, California: Addison-Wesley Publishing Company, 1984. 15. Sowa, J.F. Conceptual Graph Summary. In T.E. Nagle et. al. (Eds.), Conceptual Structures: Current Research and Practice. Chichester: Ellis Horwood, 1992, 339-348. 16. Sowa, J.F. Logical Foudations for Representing Object-Oriented Systems. Journal of Theoretical and Experimental Artificial Intelligence, 1993, 5. 17. von Neumann, J. The Computer & the Brain. New York: Yale University Press, 1958.
Ontologies and Conceptual Structures William M. Tepfenhart AT&T Laboratories 480 Red Hill Rd Middletown, NJ 07748 William.Tepfenhart@ att.com
Abstract. This paper addresses
an issue associated with representing information using conceptual graphs. This issue concerns the great variability in approaches that individuals use with regard to the conceptual graph representation and the ontologies employed. This great variability makes it difficult for individual authors to use results of other authors. This paper lays out all of these differences and the consequences on the ontologies. It compares the ontologies and representations used in papers presented at the International Conference on Conceptual Structures in 1997. This comparison illustrates the diversity of approaches taken within the CG community.
1 Introduction One of the problems about reading papers on conceptual structures is that there are almost as many different approaches to conceptual structures as there are authors. In the original book by Sowa 1, he described three basic representational elements: concepts, conceptual relations, and actors. Since then, other authors have modified concepts, conceptual relations, and actors in very different manners -- different in terms of how they are defined and used. In addition, there are at least four graph types: simple graphs, nested graphs, positive nested graphs, and actor graphs. These differences make comparison between papers difficult and at times impossible. However, there is an even worse problem and that is -- it is fracturing the conceptual graph community along multiple lines. This paper does not attempt to unify all of the different approaches. Such a task is difficult and the effort involved tremendous. It is not even clear that the result would be of value to any but a few. Instead, this paper lays out certain fundamental differences in the various approaches to conceptual graphs. Using the results of this paper, the interested reader will understand how to interpret papers based on very different sets of premises and perhaps be more forgiving to those who have chosen a different approach.
335
The basic elements for which differences are identified in this paper are: the descriptive emphasis, the definitional information, the conceptual grounding, the processing approaches, the ontological structures, and the knowledge structures. As will be shown, there are many degrees of freedom in how one can combine all of these different elements. This paper will not argue which combinations of these elements are meaningful, although it might seem to some readers that some are not. The next six sections of this paper address the following topics: 9 descriptive emphasis - what aspects about the world are stressed most in the ontology and how that affects where and how concepts are defined. 9 definitional information - what information is captured in the definition of concepts and how that information is to be used. 9 conceptual groundings - the semantic basis on which the meaning of the concept is founded. 9 processing approaches - how information captured within conceptual graphs is processed and the implications in terms of how concepts are defined. 9 ontological structures - how concepts are arranged in a type structure and the kinds of processing that can be performed over it. 9 knowledge structures - the graph structures which individuals use to express information and how that structure influences the ontology. Each section describes the element and gives examples of the approach. This is followed by a section that classifies individual papers according to the ontological assumptions on which they are based. The paper concludes by giving a summary of the results presented here.
2 Descriptive Emphasis One element contributing to an ontology is the descriptive emphasis. The descriptive emphasis is the part of the physical world that is stressed most within the ontology and knowledge structures. Some descriptions focus on the state while others focus on the act. The distinction between the two is significant in terms of the kind of information captured, the types of operations that are performed over them, and the kinds of inferences that can be achieved. In fact, the different emphasis controls what kinds of information must be derived from a given graph and knowledge base versus what information is trivially extracted.
2.1 State An ontology that emphases state concentrates on things and the relationships among them. Actions are expressed as changes in state and are characterized by an initial state, a final state, and the act that links the two. The ontology, of course, supports this kind of treatment directly. An example of this for 'A Cat Sat On A Mat' is,
336
Cat: * -> (on) -> Mat: * (posture) -> Standing: * -> <Sit> -> Cat: * -> (on) -> Mat: * (posture) -> Sitting: * In this example, the initial state is one in which a cat is on a mat in a standing position; the final state is one in which a cat is on a mat in a sitting position; and the link between the two is an actor that represents the movement of the cat into a sitting position. The use of an actor <Sit> expresses the semantics of an active relation although, as will be discussed in a later section, actors are not the only mechanism (computational) to express the changes that are taking place. The ontology reflects this way of viewing the physical world by having states and the objects within them captured as concepts. The concepts are defined within the concept type structure. The relationships between objects within a state are captured as conceptual relations which are defined within the relation type structure. Relationships between states are captured as active relations which can be defined as a relation within the relation type structure or as actors within an actor type structure.
2.2 Act An ontology that emphasizes acts concentrates on the transitions and the roles that things play within them. Actions that take place are characterized by the subject of the act, the recipient of the act, the location it took place, and the manner in which the subject executed the act. An example of this is, Sat: * - > (agent) -> Cat: * (location) -> Mat: * In this case, the act is expressed by Sat: * where the agent of the act is given by Cat:*, and the location is given by Mat: *. The ontology, of course, supports this kind of treatment directly. Here the objects involved and the act are expressed as concepts which are defined within the concept type structure. The relationships between the act and the participants are expressed as conceptual relationships which are defined within the relation type structure.
3 Def'mitional Information Sowa states that a concept is defined by Sowa, type a(x) is u where a is the type label and the body u is the differentia of a, and type(x) is called the genus of a. An example of this is, type CIRCUS-ELEPHANT(x) is
337
ELEPHANT: *X <- (AGNT) <- PERFORM <- (LOC) <- CIRCUS While it would appear that this definition is rather clear, it is in the treatment of the differentia that authors differ tremendously. There are two approaches: the differentia is treated as a predicate or as a prototype. In some cases, authors do not use the definitional mechanism. There is another factor complicating understanding the ontology behind many of the papers about conceptual graphs. Many authors do not give definitions for the concepts and conceptual relations employed in their papers. One must assume that they have some sort of definition that is obvious to them. More significantly, these authors do not exploit definitions or describe how they are used when processing graphs.
3.1 None While some authors assume but do not give definitions for conceptual elements, there are others who do not employ the Sowa definitional mechanism in any form or fashion. For these authors, definitional information is given by the placement within some network of connected nodes. The definition is established by all nodes to which it is linked by way of relationships.
3.2 Logic One approach treats the differentia as a predicate which is evaluated according to the rules of logic. In this approach, the definitional graph is the predicate. If the necessary information is available for the predicate evaluate to true, then this is deemed as sufficient to establish the type for an individual.
3.3 Prototype In another approach, the definitional graph is treated as a prototype. Individuals are treated and described as instances. The attributes associated with an individual are those given within the graph that constitutes the differentia those inherited from parent types. In a sense, this approach is compatible with the class systems used in Object Oriented systems.
4 Conceptual Grounding Ogden and Richards, in 2, established the meaning triangle as a means for expressing the relationships among symbols, concepts, and referents. The meaning triangle is illustrated in the figure below. In the lower left corner is the symbol which
338
corresponds to the linguistic element of a word. In the lower right corner is the referent which is related to the object. The top of the triangle is the concept which serves to link the symbol and the referent. The direct link between symbol and referent is actually a virtual link. Concept
Symbol
.......................
Referent
Certain relationships need to be explained in this figure. In particular, the link between the symbol and the concept is an invokes relationship. The idea here is that the symbol invokes in the mind of an individual the concept. Alternatively, one may view the link as the symbol expresses the concept. The relation between the referent and the concept is a little more complex. The referent is observed and expressed as a percept. The percept is then interpreted as a concept.
4.1Percept A percept based approach exploits the assertion that a concept is the interpretation of a percept which is the result of some sensation of an object. As a result, developing an ontology and grounding the semantics of concepts in the physical world is a matter of studying objects and how we observe them. Abstract concepts are introduced as a result of computational operations over perceptually grounded percepts. In the process of grounding the semantics of a concepts in percepts, the investigator must necessarily concern themselves with the nature of sensors and actuators. That is, in order to ground the concept in the physical we have to understand how we perceive the physical and can interact with it.
4.2 Linguistic A linguistic based approach to grounding the semantics of a concept is based on the view that the concept is the result of an invocation by a symbol. Hence, for every symbol there is some meaningful concept. By studying natural languages, we can get a 9very detailed view of the concepts and the type relationships that exist among.
5 Processing Approaches Given a conceptual graph, what does one do with it? There are three major approaches to processing conceptual graphs. One approach has its roots in semantic
339
networks, another in predicate logic, and a third in procedure. These three different approaches have significant effect on how concepts are defined. In reading papers on conceptual graphs, it is clear that many of them do not describe how the graphs are to be processed. The papers concentrate on capturing some domain or natural language. There is little focus on what one does with the knowledge once captured.
5.1 Semantic Network In this approach, graphs containing referents are treated as activations within a semantic network. Processing the graph is a matter of activating connected nodes until some query is resolved.
5.2 Predicate Logic In this approach, graphs containing referents are assertions that are made on sheets of assertion. Processing occurs as the result of a asserting a query. The query in the form of a conceptual graph with existential quantifiers. The resolution of the query graph and the bindings that make the graph true is the result returned. This approach is very much like a prolog style of programming.
5.3 Procedure The arrival of a graph in a working memory area is treated as an event. The event triggers processing in the form of an actor firing. The actor may be defined in terms such that it invokes additional actors to fire as a result of a change in the input graph. Actors modify the input graph until some stop condition is reached.
6 Ontological Structures Integral to the whole concept of an ontology is the type structure. In various approaches this resulting structures have different characteristics. Operations that make sense in one, do not make sense in the other. The choice of one approach over the other has significant consequences on the kinds of processing that must be performed in classification or establishing co-reference. The type structure is a partial ordering of the concepts based on type-of relations. Where individual authors disagree is on the nature of the type-of relation. In some cases, individuals allow a concept to exist in more than one type-of relation with others. Others restrict a concept to exist in a type-of relation with one concept. The result is that in some approaches the type structure is a hierarchy while in others it is a lattice.
340
6.1 Type Hierarchy In a type hierarchy, the ontology type structure is captured in the form of a tree. Even within the community that employs type hierarchies there is some disagreement about how individuals stand in relation to the hierarchy. In some, a particular individual can be classified as only a single leaf type of the lattice (this allows it to be classified as any of the parent types of the leaf). The other approach allows an individual to be classified as multiple subtypes of a single concept.
6.2 Type Lattice In a type lattice, the ontology type structure is captured in the form of a lattice. At the top of the lattice is the universal true and at the base of the lattice is the absurd. In this approach both natural types and role types appear in the lattice with concepts able to inherit from both. CAT:*
'l
~
MAT:*
7 Knowledge Structures Sowa's original book 1 described a basic conceptual graph which has become known as a simple graph and nested graphs for capturing logical expressions. Since then, additional graph types have been added. These additional graphs include positive nested graphs and actor graphs.
7.1 Simple Graphs Simple graphs are bi-partite directed graphs containing only concepts and conceptual relations. They are the most basic graph employed in the community. An example, often cited, is
PERSON
r----
PERSON
<- (CHLD) <- MOTHER
7.2 Nested Graphs Nested graphs are intended to express positive and negative propositions as needed in first order logic. The following illustrates how to capture the statement, "Every person has a mother.",
341
7.3 Positive Nested Graphs Positive nested graphs are similar in structure to nested graphs with the exception that negations are not allowed. They also differ in the sense of the processing that is performed over them. In this case, the nested graph is part of the referent field of some concept which participates in the outer graph. The nested graph provides greater description about an individual without complicating the exterior graph with the additional details. An example of a nest graph (taken partially from 6),
I
Person:Peter: **
PAINTING: A: SCENE: *:** ~
I,
THINK:*:**I
I Bucolic: *:**
7.4 Actor Graphs Actor graphs are graphs that incorporate actors in addition to concepts and conceptual relations. The actors are treated as active relations which have the potential to modify a graph. An example of an actor graph for the action that a cat moved onto a mat is,
II CA~:x t--~~--~
I CAT:x I
MAT:y IL
,J MA :Y I
342
8 A Sampling of Approaches In this section of the paper, the approaches demonstrated in the papers presented in International Conference on Conceptual Structures 1997 are mapped against the various ontological styles described in the previous sections. Individual authors of papers may find that their work has been misclassified in this paper. The fact that misclassification of an authors approach is likely is mentioned for a specific reason. In particular, it is to make the point that understanding the ontology employed by various authors is difficult, particularly since few authors bother to explain their ontology or what assumptions they make in constructing it. In some cases, it is exactly this information that is necessary for a different author to use their results. In the tables that follow, care has been taken to accurately characterize papers. A number of papers which appear in the tables will not have entries associated with them in some or all of the main columns. After serious consideration, it was decided that the lack of information in some papers about the ontological basis and concepts which are being processed constitutes a data point just as valid as when it was stated. This further underscores the need for such information to be stated.
Author
131 141 151 61 171 81 19 101 HI l121 131
141 151 ll61 ll71 181
Descriptive Emphasis State Act
Definitional Emphasis Nonc
X X X
Prototype
X X
X X
X X X X
X X X
X X X X X
X X X
X
191 201 211 22l 1231 24l
Predicate
X
X X
343
25 26 27 28 29
X
X X X
X
X
30 31 32 33 34 35 361 37
X X X X X X
X X X
38 In the table that follows the conceptual grounding and processing approaches are compared. One will notice in looking at this table, that there are a number of papers for which are no entries. This is not a mistake, some papers don't include information about these topics.
Percept 31 4 5 6 7 8 9 lOl 111 12 13 14 15 16 17 181 19 20 211 22
Processing Approach
Conceptual Grounding
Author
Linguistic
Semantic
Predicate
Procedure
X x x x
X
x x X X
x x X
X
X X X X X X
X
X X X X
X
X
344
23 24 25 26 27 28 291 301 31 32 331 34 35 36 37 38
X X X
X X
X
X X X X X
X X
X X X
X X
X X X
In the table that follows, there are several unusual entries. In some cases, there is an ontological structure defined and not a knowledge structure. That is, some papers only describe the type structure and not how the concepts are to used within graphs. In other cases, the knowledge structures are defined without any reference to the ontological structure. Author
Ontological Structure Lattice Hierarchy,
X
3 4
5 6 7 8 9 10 11 12 131 14 15 16 17 18 19 20
x x x x X X X
X X X
Knowledge Structure
Nested Graphs Positive Nested Graphs Nested Graphs Positive Nested Graphs Simple Graphs Actor Graphs Actor Graphs Simple Graphs Nested Graphs Nested Graphs Nested Graphs Nested Graphs Nested Graphs Nested Graphs Nested Graphs Simple Graphs
345
21 22 23
X X
24
25 26 27 28 29 301 31 32 33 341 35
36 37 38
X X X X X
X
Gamma Graphs Nested Graphs Fuzzy Graphs Simple Graphs Nested Graphs Actor Graphs Simple Graphs Simple Graphs Simple Graphs Simple Graphs Simple Graphs Simple Graphs Simple Graphs Simple Graphs
9 Summary This paper has attempted to outline some of the fundamental ideas that form the basis of research efforts in the area of ontologies and conceptual structures. It is hoped that the preceding sections have conveyed the difficulty in comparing and contrasting papers on conceptual structures, particularly with regard to the ontological foundations. The variety of approaches, processing styles, and assumptions make it difficult for one author to apply the results of another. One result is that much effort is being spent to solve the same problem several times because the language in which the problem is framed appears to be different. At the least, this paper gives an outline by which technical disagreements and discussion can be focused. That is, we can use the results presented in this paper as a means to argue about whether a predicate or procedural approach is most appropriate for conceptual graphs. If the different approaches are all appropriate, then when does one approach work better than another? If the community continues to use multiple approaches, then how can we use conceptual graphs as an exchange mechanism when the underlying ontologies have such different foundations?
346
10 References 1. Sowa, J.F., Conceptual Structures: Information Processing In Mind and Machine, Addison Wesley, Reading, MA, 1984. 2. Ogden, C.K., and I.A. Riehards, The Meaning Of Meaning, Harcourt, Brace, and World, New York, NY, 1946. 3. Sowa, J.F, "A Peircean Foundations for the Theory of Context," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Vedag, Berlin, 1998, (pp. 41-64). 4. Chein, M., 'q'he CORALI Project: From Conceptual Graphs to Conceptual Graphs via Labeled Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 65-79). 5. Mineau, G.W. and M-L Mugnier, "Contexts: A Formal Definition Of Worlds Of Assertions," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 80-94). 6. Chein, M. and M-L Mugnier, "Positive Nested Conceptual Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 95-109). 7. Wermelinger, M. "A Different Perspective On Canonicity," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, SpringerVerlag, Berlin, 1998, (pp. 110-124). 8. Tepfenhart, W.M., "Aggregations In Conceptual Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, SpringerVerlag, Berlin, 1998, (pp. 125-137). 9. Mineau, G.W. and R. Missaoui, 'q'he Representation Of Semantic Constraints in Conceptual Systems," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 138-152). 10. Faron, C. and J-G. Ganascia, "Representation of Defaults and Exceptions in Conceptual Graphs Formalism," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 153-167). 11. Ribiere, M. and R. Dieng, "Introduction of Viewpoints in Conceptual Graph Formalism," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 168-182). 12. Angelova G., and K. Bontcheva, "Task-Dependent Aspects of Knowledge Acquisition: A Case Study in a Technical Domain," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 183-197). 13. Richards, D. and P. Compton, "Uncovering the Conceptual Models in Ripple Down Rules," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 198-212). 14. Kremer, R., D. Lukose, and B. Gaines, "Knowledge Modeling Using Annotated Flow Chart," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 213-227). 15. Lukose, D., "Complex Modeling Constructs in MODEL-ECS," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 228-243). 16. Dick, J.P, "Modeling Cause and Effect in Legal Text," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, SpringerVerlag, Berlin, 1998, (pp. 244-259).
347 17. Raban, R., "Information Systems Modeling with GCs Logic," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 260-274). 18. Bos, C. B. Botella, and P. Vanheeghe, "Modeling and Simulating Human Behaviors with Conceptual Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 275-289). 19. Wille, R., "Conceptual Graphs and Formal Concept Analysis," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 290-303). 20. Biedermann, K., "How Triadic Diagrams Represent Conceptual Structures," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 304-317). 21. Stumme, G. "Concept Exploration - A Tool for Creating and Exploring Conceptual Hierarchies," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 318-332). 22. Prediger, S., "Logical Scaling in Formal Concept Analysis," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 332-341). 23. Ellis, G. and S. Callaghan, "Organization of Knowledge Using Order Factors," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Spdnger-Verlag, Berlin, 1998, (pp. 342-356). 24. Ohrstrom, P., "C.S. Peirce and the Quest for Gamma Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 138-152). 25. Kerdiles, G. and E. Salvat, "A Sound and Complete CG Proof Procedure Combining Projections with Analytic Tableaux," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 357-370). 26. Coa, T.H., P.N. Creasy, and V. Wuwongse, "Fuzzy Unification and Resolution Proof Procedure for Fuzz Conceptual Graph Programs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 386-400). 27. Leclere, M. "Reasoning with Type Definitions," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 401-415). 28. Coa, T.H. and P.N. Creasy, "Universal Marker and Functional Relation: Semantics and Operations," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 416-430). 29. Raban, R. and JH. S. Delugach, "Animating Conceptual Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 431-445). 30. Bournaud, I. and J-G. Ganascia, "Accounting for Domain Knowledge in the Construction of a Generalization Space," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 446459). 31. Mann, G.A., "Rational and Affective Linking Across Conceptual Cases - Without Rules," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 460-473).
348
32. Gerbe, O. "Conceptual Graphs for Corporate knowledge Repositories," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 474-488). 33. Genest, D. and M. Chein, "An Experiment in Document Retrieval Using Conceptual Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 489-504). 34. Keeler, M.A.L.F. Searle, and C. Kloesel, "PORT: A Testbed Paradigm for Knowledge Processing in the Humanities," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlinr 1998, (pp. 505-520). 35. Clark, P. and B. Porter, "Using AcceSs Paths to Guide Inference with Conceptual Graphs," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 521-535). 36. de Moor, A., "Applying Conceptual Graph Theory to the User-Driven Specifications of Network Information Systems," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 536-550). 37. Puder, A. and K. Romer, "Generic Trading Service in Telecommunication Platforms," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 551-565). 38. Polovina, S., "Assessing Sowa's Conceptual Graphs for Effective Strategic Management Decisions, Based on a Comparative Study with Eden's Cognitive Mapping," Conceptual Structures: Fulfilling Peirce's Dream, eds. D. Lukose, H. Delugach, M. Keeler, L. Searle, and J. Sowa, Springer-Verlag, Berlin, 1998, (pp. 566-580).
Manual Acquisition of Uncountable Types in Closed Worlds Galia Angelova Bulgarian Academy of Sciences, 25A Acad. G. Bonchev St., 1113 Sofia, Bulgaria galja~lml.acad.bg
A b s t r a c t . The paper considers the problem of classifying countableuncountable entities during the process of Knowledge Acquisition (KA) from texts. Since one of the main goals of KA is to identify types, means to distinguish new types, instances and individuals become particularly important. We review briefly related studies to show that the distinction countable-uncountable depends on the considered natural language, context usage and the domain; then countability is a perspective to look at a closed world since there is no universal general taxonomy. Finally we propose an internal ontological solution for mass objects which suits to a project 1 for generation of multilingual Natural Language (NL) explanations from Conceptual Graphs (CG).
1
Introduction
KA aims at (i) the identification of (task-specific) objects and relationships in the acquisition domain and (ii) the encoding of these entities in the most suitable structures of the chosen knowledge representation formalism. KA is usually performed from texts in a manual, semi-automatic or automatic manner. KA explicates the concept types, their instances and individuals as they are described in the acquisition texts. Obviously, the type fragmentariness is strongly influenced by the concrete natural language - the particular words have languagespecific semantic granularity and often this granularity is the KA hint for the semantic content of the correspondingly acquired type. Uncountable types raise a special interest. These types (often mass objects) should be recognised and encoded properly, since their instances behave in a specific manner. If KA does not identify the countable-uncountable types whatever their language citation is, there is no 'later' adjustment where this distinction would be evaluated in the context of the acquisition texts and explicated in the Knowledge Base (KB). So, in our view, the precise acquisition of uncountable concepts is one of the obligatory tasks to be performed by KA. This paper discusses KA of uncountable types from noun phrases. We summarise our experience in manual KA from technical texts (generally discussed in AB2) and the way we treat the obtained instances after a precise study of 1 DBR-MAT "Intelligent Translation System", funded by Volkswagen Foundation (1996-98), http://nats-www.informatik.uni-hamburg.de/projects/dbr-mat.
352
their (i) linguistic behaviour in the texts and (ii) conceptual behaviour in the closed domain. Section 2 presents the distinction countable-uncountable from a linguistic perspective. Since we perform KA from NL texts to provide further NL generation, the linguistic outlook is the most natural initial standpoint. Section 3 summarises briefly other related approaches to mass nouns and objects. Section 4 shows how the observation of linguistic facts affects the conceptual representation within the KB of CG. Section 5 contains the conclusion.
2
Linguistic Perspective to Countable vs. U n c o u n t a b l e
It is difficult to say whether the distinction countable-uncountable is to be drawn (i) between linguistic entities in the NL texts (as it is widely accepted, these are noun phrases), or (ii) between conceptual entities (objects in the world). Moreover, a clearly defined hierarchy of countable-uncountable entities does not exist. Below we consider the problems of such a classification. The contrastive study Moll adopts a classification of nouns after the linguist Otto Jespersen (see Fig. 1); following them we accept that the distinction countable-uncountable is one of the most important semantic characteristics of nouns. This fits very well to the KA goals to identify types; it is really important to classify the acquired concept types as types wi~h enumerable instances and individuals vs. other lypes. We can use Fig. 1 as a guide for conceptual classification of types if we interpret properly the ontological content of the hierarchy. To discuss Fig. 1, let us consider nouns and world objects which are 'named' by these nouns:
Noun
J
Countable
Concrete
Abstract
Uncountable
Concrete
Abstract I I I
Individual
C o liective
M ass
C o lective
Fig. 1. Taxonomy of nouns after Jespersen. All partitions are disjoint. The dotted lines indicate the only non-exhaustive partition.
1. C o u n t a b l e , C o n c r e t e , I n d i v i d u a l : table, student. Material world objects, with certain shape or precise limits, which exist as sets of separable concrete
353
2. 3.
4. 5.
instances and individuals. This is nearly the only class of nouns whose grammatical behaviour coincides with the individual behaviour of the respective conceptual objects. C o u n t a b l e , C o n c r e t e , C o l l e c t i v e : flock, herd. Grouping material objects which exist as enumerable instances. C o u n t a b l e , A b s t r a c t , I n d i v i d u a l : idea, thought. Abstract objects named by nouns whose grammatical features allow counting. We say 'one, three, many ideas'. The language-influenced conceptualisation is that ideas can be counted (at least in English). T h a t is why in the NL texts we meet references to different instances of the respective concept type. C o u n t a b l e , A b s t r a c t , C o l l e c t i v e : family, company. Grouping abstract objects which exist as enumerable instances. U n c o u n t a b l e , C o n c r e t e , Mass: wine, water, sand, snow, copper, butter, sugar. The semantic structure of mass nouns excludes enumeration of instances but mass nouns have the category of number because (i) they appear in singular, e.g. 'this is silver', and (ii) they express quantity. Plural forms usually indicate a modified meaning or a polysemy. Mass nouns correspond to material objects with properties that (i) the object substance can be measured but not counted, and (ii) each separate part of this stuff has the quality and meaning of the whole.
We reviewed many works to justify this taxonomy; most of the authors would agree with the interpretation of the above five classes. To show the complications of the exact classification of uncountables, however, we compile different examples mapping them into the hierarchy in Fig. 1: 1. U n c o u n t a b l e , C o n c r e t e , C o l l e c t i v e : pottery, silverware. 2. U n c o u n t a b l e , A b s t r a c t , b u t n o t M a s s a n d n o t C o l l e c t i v e : love, liberty, democracy, dispersion, music, elegance, etc. Abstract objects which seem to exist 'in one instance only'. 3. U n c o u n t a b l e , A b s t r a c t , Mass: success, knowledge, software. 4. U n c o u n t a b l e , A b s t r a c t , C o l l e c t i v e : mankind, gentry, police. If software is something like abstract mass, then why not to consider hardware as concrete mass? But on the other hand, Can hardware be measured like water? Moreover, hardware resembles pottery, because not every physical part of hardware is still hardware. But pottery is classified in Moll as uncountable, concrete, collective. To move hardware to the same class as pottery would probably mean to consider software as abstract, collective - which would contradict some other opinions on what collective is, and so on. It is difficult to distinguish abstract collective and abstract mass nouns in various cases, if we compare the opinions of different authors. Facing all these complications in building an exact taxonomy, we decided to avoid classifying each abstract object in the above categories. We hoped that the opposition countable-uncountable would provide enough conceptual evidence for the number of instances. Unfortunately, even this partition is not absolute in
354
case of multilinguality: e.g., news in English is uncountable, singular, the news is good, while in Bulgarian one says 'two news' similarly to 'two ideas' in English. So we can use the taxonomy in Fig. 1 as a basic framework supporting KA classifications, but only if we remember that it is somewhat relative, especially in particular multilingual cases. Below we continue discussing noun phrases and concept types but always bearing in mind the duality language unit - type acquired in the KB.
3
Other Approaches to Uncountability
AI usually studies the philosophical, cognitive and formal foundations of knowledge modelling. In Hall objects from the Naive Physics world are considered. Properties like countable-uncountable seem to be treated as intrinsic ones. In Gull the countability is a category in a top-level ontology of universals. WCH develops an interesting taxonomy of part-whole relations to explain the English usage of part of. Two cases concern the distinction uncountable-countable : the relations portion-mass (slice-pie) and stuff-object (steel-car). Our KA goals, however, lay at the border between support of multilingual NL processing and conceptual modelling using CG; that is why we are mostly interested either in approaches which address both layers together or in CG-related approaches. In Sol and So2 we see that mass nouns have measured individuals which correspond to concrete amounts of stuff, representing in this way different individual quantities of types WATER, TIME etc. Plural referents are only used with countable things, while mass nouns are not normally used in the plural. To represent substances by CG, Tell proposes the type definition:
type substance(x) is p h y s i c a l _ o b j e c t : {*}@++ (x) -> (has_components) -> Type_0f (physical_object) ~*} (has_internal_structure)-> Structure ...... 'A substance is a set containing an uncountable number of physical objects of various types and the members within the set have some internal structure'. Tell proposes to perform computations over sets and then substance properties can be interpreted as consequences of the relationships that exist among the instances. Tell explains compositions, states, viscosity, and reactivity of substances. This is a conceptualisation of substances at a micro-level, providing an extremely detailed description of the micro-changes that can take place over time. The NL-oriented approaches, however, always take into consideration (i) the linguistic facts, and (ii) (to some extent) the object denoted by the noun and the properties of this object. According to Lyons, the count-mass distinction is primarily a linguistic one, which is clearly seen in cases of multilinguality (remember the example of news, uncountable in English and countable in Bulgarian). R. Dale Dal investigates the domain of cooking and discusses conflicts between a naive ontology and linguistic facts. In the domain of cooking, rice and lentil are rather similar (small
355
objects of roughly the same size), whose individuals are not considered separately in recipes. The linguistic expressions of ingredients, however, represent rice as a mass noun while lentil behaves like a count noun: e.g. four ounces of rice, four ounces of lentils. 'If the count/mass distinction was ontologically based, we would expect these descriptions to be either both count or both mass' Dal. We found particularly interesting the observation that 'physical objects are not inherently count or mass, but are viewed as being count or mass' in some domains. So Dal considers physical objects from either a mass or a count perspective. 'Thus, a specific physical object can be viewed one time as a mass, and another time as a countable object: when cooking, I will in all likelihood view a quantity of rice as a mass, but if I am a scientist examining rice grains for evidence of pesticide use, I may view the same quantity of rice as a countable set of individuals'. In Dal, exactly one perspective at a time is allowed: each object in the closed domain of cooking is either mass, or count. Comparing Tell and Dal, we see that at a micro-level all objects can be treated as sets of instances; but natural language does not work at the level of atomic components. In most realistic domains the basic objects have much bigger granularity and they are denoted by words that make us treat them as count or mass. Unfortunately, the context-dependent NL usage provides flexible shifts of granularity (see Hol D. 'A road can be viewed as a line (planning a trip), as a surface (driving on it), and as a volume (hitting a pothole) .... Many concepts are inherently granularity-dependent.' Probably we could say that closed domain is such a domain, where a pre-fixed number of perspectives to each object exist and the relevant kinds of granularity are pre-fixed as well. To summarize, in NL we refer to the conceptual entities as follows: (i) when the stuff itself is referred to, an uncountable noun is typically used; in other cases the emphasis is on the object form and shape and then we refer to particular instances by means of countable nouns; (ii) in some domains the entities are treated as compositions at the level of micro-ingredients,while in other domains we see them as compositions of ingredients at a much higher level.
4
A Mixed
Count-Mass
Taxonomy
in Closed
Domains
We acquire CG in the domain of admixture separation from polluted water in order to generate domain explanations in several NLs from the underlying KB AB1. In the context of the present considerations, we try to satisfy the following requirements: (i) adequate internal conceptuMisation providing easy surface verbalisation in different NLs with a proper usage of singular-plural and count-mass nouns; (ii) clear separation between conceptual data (in the single KB) and linguistic data (in the system lexicons, one lexicon per language); (iii) conceptual structures allowing for easy integration of the closed domain into more universal ontologies. In the type hierarchy we define important domain types and integrate them under an upper model. Figure 2 represents a simplified view to the taxonomy
356
where countable and mass entities are classified as subtypes of PHYSICALO B J E C T . We acquire as concept types two important objects in the domain: oil drop and oil particle. Note that this decision is domain-dependent, since in this domain the polluting oil exists as particles and drops in the polluted water. Furthermore, OIL-DROP and OIL-PARTICLE are subtypes of the substance OIL. These two types show the borderline where the domain taxonomy is integrated into a universal taxonomy of physical objects. The ISA-KIND relation, introduced in AB2, defines the perspective of looking at particles and drops as OIL: they are typical 'quantities of stuff'. To conform to some standard, we adopted the keyword P A C K A G E R from Dal. The ISA-KIND relation indicates that the classifications OIL --+ OIL-PARTICLE and OIL -+ OIL-DROP are partitions into role subtypes, because these are subtypes that can be changed during the life time of the physical object (similarly to PROFESSION for PERSONS), while the partitions OIL --+ MINERAL-OIL and OIL --+ SYNTHETIC-OIL are classifications into natural subtypes according to the usual type-of relation. Note that the PACKAGER-perspective covers the two cases of part-whole relations mentioned in WCH: it denotes the relations portion-mass and stuff-object, which are not distinguished in the current domain and consequently, are not treated as different ones in the conceptual model. Such a conceptual solution provides flexible links to the lexicons in case of count-mass nouns. Imagine in some natural language only the word for the stuff exists (e.g. grape is a mass noun in Bulgarian and Russian); then this word is linked to the stuff-concept. But in some other languages, the related words can name typical 'packaged' quantities (like grape in English); if we acquire such quantities as types, the respective words will be connected to these special concept types. Note that it is not obligatory to have 'naming' lexicon elements in any language and for any domain types; the explanations are constructed for the existing concepts in the corresponding grammatical forms. Since the inheritance works for type-of relations, in DBR-MAT we can, for instance, generate the explanation: Each oil particle has dimension less than 0.05 mm. Here we use particle in singular, since it is a countable object and inherits the characteristic features of PARTICLE. As a subtype of PARTICLE, OIL-PARTICLE has SHAPE and DIMENSION. From the perspective of OIL, however, we talk about particles always in plural, and thus we connect countable and mass nouns in the generated explanations. For instance: Oil appears as oil particles and oil drops. Viewed as oil,
oil particles have density and relative weight. Additionally, in the KB, when instances of the types OIL-PARTICLE and OIL-DROP appear in conceptual graphs with unspecified plural referent, i.e. as OIL-PARTICLE: {*} and OIL-DROP: {*}, we can make a generalisation and replace these types by OI L. Then they are verbalised as mass nouns. It is obvious that the natural language we generate is not as flexible as a human one, but this solution is an opportunity to mix countable and uncountable perspective in one utterance. Note that we cannot produce phrases like two oil particles, because in our domain-specific KB the unspecified plural referent sets
357
. . .
/ . . .
PHYSICAL-OBJECT C O U N TAB LE
\
SUB STAN C E
CONCEPT-TYPE
/\ DRO P
PARTIC LE
OIL-DROP
0 IL
NAqI/RAL
O IL - PARTIC LE
ROLE
PROFESSION
SYNTHETIC -OIL
PACKAGER
M IN E R A L - O IL
~ IL- p~ACR_ ~ _ ~ ~
,~ACKAGER
I
~ IL-DRO P ~.....~
Fig. 2. Taxonomy mixing countable and mass objects by classification into role and n~tur~l subtypes.
from the type definition of SUBSTANCE would not be instantiated with counted sets. To conclude, such crosspoint types between countable and mass types require very careful elaboration of: (i) the type hierarchy, (ii) the type definitions of the supertypes and the 'crosspoint' type so that to assure correct generalisation and specialisation, (iii) the characteristics of both supertypes to assure correct inheritance.
5
Conclusion
This paper discusses difficulties in classifying world objects as countable and uncountable and presents a (more or less) empirical solution applied in an ongoing project. We see that KA requires extremely detailed analysis of the source texts and deep understanding of the CG structures and idiosyncrasies. It is somehow risky to consider only the NL level, since the language phenomena in the acquisition texts are often misleading (clearly seen in a multilingual paradigm). Actually the distinction countable-mass should be defined at a deeper concep-
358
tual level. We try to keep the two perspectives closely related: the uncountable stuff and the countable individual objects made by this stiff. Fig. 2 shows that we allow both count-mass perspectives together but only to specially acquired, domain dependent types. In this sense, our approach addresses the closed world of one domain. To 'open' this closed world and to integrate another closed world for another domain will probably require the addition of new 'crosspoint' types between countable-mass objects. In our view, the classification countable-uncountable is not less meaningful than the partition abstract-material. Fig. 1 differs from many upper-level ontological classifications, where abstract-real is the highest partition of the top (see FH1). But a careful analysis of the taxonomy in Fig. 1 shows that it is easy to replace the two upper layers, i.e. the classification concrete-abstract can easily become the topmost partition. Despite the problems discussed in this paper, it seems worthwhile to consider at least the countable-mass distinction of p h y s i c a l o b j e c t as one of the unifying principles for top-level ontologies.
Acknowledgements The author is grateful to the three anonymous referees for the fruitful discussion and the suggestions.
References AB1 Angelova, G., Boncheva, K.: DB-MAT: Knowledge Acquisition, Processing and NL Generation using Conceptual Graphs. ICCS-96, LNAI 1115 (1997) 115-129. lAB2 Angelova, G., Boncheva, K.: Task-Dependent Aspects of Knowledge Acquisition: a Case Study in a Technical Domain. ICCS-97, LNAI 1257 (1996) 183-197. Dal Dale, R.: Generating Referring Expressions in a Domain of Objects and Processes. Ph.D. Thesis, University of Edinburgh (1988). FH1 Fridman, N., Hafner, C.: The State of the Art in Ontology Design. A Survey and Comparative Review. AI Magazine Vol. 18(3) (1997), 53 - 74. Gull Guarino, N.: Some Organizing Principles for a Unified Top-Level Ontology. In: Working Notes AAAI Spring Symp. on Ontological Engineering, Stanford (1997). Hal Hayes, P.: The Second Naive Physics Manifesto. In Brachman, Levesque (eds.) Readings in Knowledge Representation, Morgan Kaufmann Publ. (1985) 468-485. Hol Hobbs, J.: Sketch of an ontology underlying the way we talk about the world. Int. J. Human-Computer Studies 43 (1995), 819 - 830. Mol Molhova, J. The Noun: a Contrastive English - Bulgarian Study. Publ. House of the Sofia University "St. K1. Ohridski', Sofia (1992). Sol Sowa, J.: Conceptual Structures: Information Processing in Mind and Machine. Addison-Wesley, Reading, MA (1984). So2 Sowa, J.: Conceptual Graphs Summary. In: Nagle, Nagle, Gerholz, Eklund (Eds.), Conc. Structures: Current Research and Practice, Ellis Horwood (1992) 3-52. Tel Tepfenhart, W.: Representing Knowledge about Substances. LNAI 754 (1992) 59-71. WCH Winston, M., Chaffin, R., I-Ierrmann, D.: A Taxonomy of Part-Whole Relations. Cognitive Science 11 (1987) 417-444.
A Logical Framework for Modeling a Discourse from the Point of View of the Agents Involved in It 1 Bernard Moulin, Professor Computer Science Department and Research Center in Geomatics Laval University, Pouliot Building, Ste Foy (QC) G1K 7P4, Canada Phone: (418) 656-5580, E-mail: [email protected]
A b s t r a c t . The way people interpret a discourse in real life goes well be-
yond the traditional semantic interpretation based on predicate calculus as is currently done in approaches such as Sowa's Conceptual Graph Theory, Kamp's DRT. From a cognitive point of view, understanding a story is not a mere process of identifying truth conditions of a series of sentences, but i s a construction process of building several partial models such as a model of the environment in which the story takes place, a model of mental attitudes for each character and a model of the verbal interactions taking place in the story. Based on this cognitive basis, we propose a logical framework differentiating three components in an agent's mental model: a temporal model which simulates an agent's experience of the passing of time; the agent's memory model which records the explicit mental attitudes the agent is aware of and the agent's attentional model containing the knowledge structures that the agent manipulates in its current situation
1
Introduction
Conceptual Graphs (CG) 16 have been applied in several natural language research projects and the CG notation can be used to represent fairly complex sentences, including several interesting linguistic phenomena such as attitude reports, anaphors, indexicals and subordinate sentences. However, most researchers have overlooked the importance of modeling the context in which sentences are uttered by locutors. Even modeling a simple sentence such as "Peter saw the girl who was playing in the park with a red ball" requires a proper representation of the context of utterance. For instance, the preterit "saw" cannot be modeled without referring to the time when the locutor uttered the sentence: hence, we need to represent the locutor and the context of utterance in addition to representing the sentence itself. To this end, we proposed to model the contents of whole discourses using an approach in which it is possible to explicitly represent the context of utterance of speech acts 1 An extended version of this paper can be found in reference 11. This research is sponsored by the Natural Sciences and Engineering Council of Canada and FCAR. My apologies to the reviewers because I could not answer all their questions in such a short paper.
360
8, 9, 10. Any sentence is thought of as resulting from the action of a locutor performing a speech act, which determines the context of utterance of that sentence. A major contribution of that approach was the explicit introduction of temporal coordinate systems in the discourse representation using three kinds of constructs: the narrator's perspective, the temporal localizations and the agent's perspectives. As an example let us consider the story displayed in Figure 1. It is told by an unidentified narrator using the past tense, which indicates that the reported events occurred in the past relative to the narrator's time, and hence to the moment when the reader reads the story. When the narrator reports the characters' words, the verb tense changes for the present or the future. These tenses are relative to the characters' temporal perspectives which differ from the narrator's temporal perspective that is temporally located after that date. This example shows the necessity of explicitly introducing in the discourse representation the contexts of utterance of the different speech acts performed by the narrator and the characters. The complete representation of this story can be found in 11. Monday October 20 1997, Quebec city (SI). Peter wanted to read Sowa's book ($2), but he did not have it ($3). He recalled that Mary bought it last year ($4). He phoned her ($5) and asked her ($6): "Can you lend me Sowa's book for a week?"(S7) Mary answered (S8):"Sure! ($9) Come and pick it! (SI0)". John leplied (SII):"Thanks! (SI2) I will come tomorrow" (SI3). F i g u r e 1: A s a m p l e story Note: the numbers Si are used to identify the various sentences of the text
However, even such a representation is not sufficient if we want to enable software agents to reason about the discourse content. We aim at creating a system which will be able to manipulate the mental models of the characters involved in the discourse and simulate certain mechanisms related to story understanding. We based our approach on cognitive studies that have shown that readers adopt a point of view "within the text or discourse" 2. The Deitic Shift Theory (DST) argues that the metaphor of the reader "getting inside the story" is cognitively valid. The reader often takes a cognitive stance within the world Of the narrative and interprets the text from that perspective 14. Segal completes this view by discussing about the mimesis mechanism: "A reader in a mimetic mode is led to experience the story phenomena as events happening around him or her, with people to identify with and to feel emotional about... The reader is often presented a view of the narrative world from the point of view of a character... We propose that this can occur by the reader cognitively situating him or herself in or near the mind of the character in order to interpret the text" (15 p 67 artt 68). Hence, from a cognitive point of view, understanding a story is not a mere process of identifying truth conditions of a series of sentences, but is a construction process of building several partial models such as a model of the environment in which the story takes place, a model of mental attitudes for each character and a model of the verbal interactions taking place in the story. Hence the following assumption: When understanding a discourse, a reader creates several mental models that contain the mental attitudes (beliefs, desires, emotions, etc.) that she attributes to
361
each character as well as the communicative and non-communicative actions performed by those characters.
Hence, when using CGs to model the semantic content of a discourse, we need: 1) a way of representing the context of utterance of agents' speech acts; 2) the underlying temporal structure; 3) a way of representing the mental models of each character involved in the discourse. In the next sections we address point 3) and propose an approach based on a logical framework that differentiates three components in an agent's mental model: a temporal model which simulates an agent's experience of the passing of time (Section 2); the agent's memory model which records the explicit mental attitudes the agent is aware of and the attentional model containing the knowledge structures that the agent manipulates in its current situation (Section 3).
2. A n Agent's M e n t a l M o d e l Based on A w a r e n e s s In order to find an appropriate approach to represent agents' mental models, we can consider different formalisms that have been proposed to model and reason about mental attitudes 2 1 among which the so-called BDI approach 13 5 is widely used to formalize agents' knowledge in multi-agent systems. These formalisms use a possibleworlds approach 6 for modeling the semantics of agent's attitudes. For example, in the BDI approach 13 5, an agent's mental attitudes such as beliefs, goals and intentions are modeled as sets of accessible worlds associated with an agent and a time index thanks to accessibility relations typical of each category of mental attitudes. However, such logical approaches are impaired by the problem of logical omniscience, according to which agents are supposed to know all the consequences of their beliefs. This ideal framework is impractical when dealing with discourses that reflect human behaviors, simply because people are not logically omniscient 7. In addition, it is difficult to imagine a computer program that will practically and efficiently manipulate sets of possible worlds and accessibility relations. In order to overcome this theoretical problem, Fagin et al. 4 proposed to explicitly model an agent's knowledge by augmenting the possible-worlds approach with a syntactic notion of awareness, considering that an agent must be aware of a concept before being able to have beliefs about it. In a more radical approach, Moore suggested partitioning the agent's memory into different spaces, each corresponding to one kind of propositional attitude (one space for beliefs, another for desires, another for fears, etc.), "these spaces being functionally differentiated by the processes that operate on them and connect them to the agent's sensors and effectors" 7. The approach that we propose in this paper tries to reconcile these various positions, while providing a practical framework for an agent 2 In AI litterature, elements such as beliefs, goals and intentions are usually called "mental states". However, we use the term "mental attitudes" to categorize those elements. An agent's mental model evolves through time and we use the term agent's mental state to characterize the current state of the agent's mental model. Hence, for us an agent's mental state is composed of several mental attitudes.
362
in order to manipulate knowledge extracted from a discourse. The proposed agent's framework is composed of three layers: the agent's inner time model which simulates its experience of the passing of time; the agent's memory model which records the explicit mental attitudes the agent is aware of and the attentional model containing the knowledge structures that the agent manipulates in its current situation. In order to formalize the agent's inner time model, we use a first-order, branching time logic, largely inspired by the logical language proposed in 5 and 13. It is a firstorder variant of CTL*, Emerson's Computational Tree Logic 3, extended to a possible-worlds framework 6. In such a logic, formulae are evaluated in worlds modeled as time-trees having a single past and a branching future. A particular time index in a particular world is called a world-position. The agent's actions transform one world position into another. A primitive action is an action that is performable by the agent and uniquely determines the world position in the time tree. The branches of a time tree can be viewed as representing the choices available to the agent at each moment in time. CTL* provides all the necessary operators of a temporal logic. It is quite natural to model time using the possible-worlds approach because the future is naturally thought of as a branching structure and because the actions performed by the agent move its position within this branching structure. The agent's successive world positions correspond to the evolution of the agent's internal mental state through time as a result of its actions (reasoning, communicative and non-communicative acts). The agent does not need to be aware of all the possible futures reachable from a given world position: this is a simple way of modeling the limited knowledge of future courses of events that characterizes people. An agent's successive world positions specify a temporal path that implements the agent's experience of the passing of time: this characterizes its "inner time". This inner time must be distinguished from what we will call the "calendric time" which corresponds to the official external measures of time that is available to agents and users (dates, hours, etc.).
3
The Agent's Memory Model and Attentional Model
The agent's mental attitudes are recorded in what we call the agent's memory model. Following Fagin 4 we consider that the definition of the various mental attitudes in terms of accessibility relations between possible worlds corresponds to the characterization of an implicit knowledge that cannot be reached directly by the agent. At each world position the agent can only use the instances of mental attitudes it is aware of. Following Moore's proposal of partitioning the agent's memory into different spaces, the awareness dimension is captured by projecting an agent's current world-position onto so-called knowledge domains. The projection of agent Ag's world-position Wto on the knowledge domain Attitude-D defines the agent's range of awareness relative to domain Attitude-D at time index tO in world w. The agent's range of awareness is the subset of predicates contained in knowledge domain Attitude-D which characterize the particular instances of attitudes the agent is aware of at world-position Wto . The
363
knowledge domains that we consider in this paper are the belief domain Belief-D and the goal domain Goal-D. But an agent can also use other knowledge domains such as the emotion domain Emotion-D that can be partitioned into sub-domains such as FearD, Hope-D and Regret-D. In addition to knowledge domains which represent an agent's explicit recognition of mental attitudes, we use domains to represent an agent's explicit recognition of relevant elements in its environment, namely the situational domain Situational-D, the propositional domain Propositional-D, the calendric domain Calendric-D and the spatial domain Spatial-D. The situational domain contains the identifiers of any relevant situation that an agent can explicitly recognize in the environment. Situations are categorized into States, Processes, Events, and other sub-categories which are relevant for processing temporal information in discourse 8 9: these sub-categories characterize the way an agent perceives situations. A situation is specified by three elements: a propositional description found in the propositional domain Propositional-D, temporal information found in the calendric domain Calendric-D and spatial information found in the spatial domain Spatial-D. Hence, for each situation there is a corresponding proposition in Propositional-D, a temporal interval in Calendric-D and a spatial location in Spatial-D. Propositions are expressed in a predicative form which is equivalent to conceptual graphs. The elements contained in the calendric domain are time intervals which agree with a temporal topology. The elements contained in the spatial domain are points or areas which agree with a spatial topology. Figure 2 illustrates how worlds and domains are used to model agent Peter's mental attitudes obtained after reading sentences S 1 to $4 in the text of Figure 1. Worlds are represented by rectangles embedding circles representing time indexes and related together by segments representing possible time paths. Ovals represent knowledge domains. Curved links represent relations between world positions and elements of domains (such as Spatial-D, Calendric-D, Peter's Belief-D, etc.) or relations between elements of different domains (such as Situational-D and Spatial-D, Calendric-D or Propositional-D). After reading sentences S1 to $3, we can assume that Peter is in a world-position represented by the left rectangle in Figure 2, at time index tl in world W1. This world position is associated with a spatial localization Peter's.home in the domain Spatial-D and a date dl in the domain Calendric-D. This information is not mentioned in the story but is necessary to structure Peter's knowledge. Time index tl is related to beliefs P.bl and P.b2 in Peter's Belief-D. P.bl is related to situation sl in Situational-D which is in turn related to proposition p29, to location Peter's.home in Spatial-D and to a time interval -, Now in Calendric-D. Now is a variable which takes the value of the date associated to the current time index. Proposition p29 is expressed as a conceptual graph represented in a compact linear form: Possess (AGNT- PERSON:Peter; OBJ- BOOK: Sowa's.Book) Notice that in Calendric-D we symbolize the temporal topological properties using a time axis: only the dates dl and d2 associated with time indexes tl and t2 have been represented as included in the time interval named October 201997.
364
Specification of propositions PROP(p29, Possess(AGNT-PERSON:Peter; OBJ-BOOK: Sowa's.Book)) PROP(p30, Read (AGNT-PERSON:Peter; OBJ-BOOK:Sowa's.Book)) PROP(p31, Buy (AGNT-PERSON:Mary; OBJ- BOOK: Sowa's.Book)) PROP(p32, Lend (AGNT-PERSON:Mary;PINT- PERSON: Peter; OBJ-BOOK:Sowa's,Book))
Figure 2: Worlds and Domains From sentence $2 we know that Peter wants to read Sowa's book, which is represented by the link between time index tl and the goal P.gl in Peter's Goal-D. P.gl is related to situation s4 in Situational-D which is in turn related to proposition p30 in Propositional-D. P.gl is related to a date in Calendric-D and a location in Spatial-D, but those links have not been represented completely in order to simplify the figure (only dotted segments indicate the existence of those links). In world W1, agent Peter can choose to move from time index tl to various other time indexes shown by different circles in the world rectangle in Figure 2. Moving from one time index to another is the result of performing an elementary operation. From our little story we can imagine that Peter wanted that Mary lends him the book: the corresponding elementary operation is the creation of a goal P.g2 with the status active. In Figure 2 this is represented by the large arrow linking the rectangles of worlds W and W2 on which appears the specification of the elementary operation Creates (Peter, P.g2, active). When this elementary operation is performed, agent Peter moves into a new world W2 at time index t2 associated with the spatial localization Peter's.home and date d2. Time index t2 is still related to beliefs P.bl and P.b2 in Belief-D, but also to goals P.gl and P.g2 in Peter's Goal-D. In an agent Agl's mental model certain domains may represent mental attitudes of another agent Ag2: They represent the mental attitudes that Agl attributes to Ag2. As an example, Goal
365
P.g2 in Peter's Goal-D is related to Goal rag6 in Mary's Goal-D which is contained in Peter's mental model. Goal mg6 is associated with situation s2 which is itself related to proposition p32. Beliefs and goals are formally expressed using predicates which hold for an agent Ag, a world w and a time index t as for example Peter's beliefs and goals at time index t2: Peter, W2, t2 I= BELe.bl(Peter,STATE~I(NOTp29, -, Now, Peter's.home )) Peter, W2, t2 I= BELp.b2(Peter,EVENT~(p31, dx, -) ) Peter, W2, t2 I= GOALp.gl(Peter,PROCESS~(p30, -, Quebec ), active) Peter, W2, t2 I= GOAl-,.gz(Peter,GOAL.~(Mary, PROCESSa(p32, -, Quebec), active), active) The agent's memory model gathers the elements composing the agent's successive mental states. The amount of information contained in the agent's memory model may increase considerably over time, resulting in efficiency problems. This is similar to what is observed with human beings. They record "on the fly" lots of visual, auditive and tactile but they usually do not consciously remember this detailed information over long periods of time. They remember information they pay attention to. Similarly in our framework, the agent's attentional model gathers some information extracted from the agent's memory model because of its importance or relevance for the agent's current activities. The attentional model is composed of a set of knowledge bases that structure the agent's knowledge and enable it to perform the appropriate reasoning, communicative and non-communicative actions. Among those knowledge bases, we consider the Belief-Space, Decision-Space, Conversational-Space and Action-Space. The Belief-Space contains a set of beliefs exlracted from the memory model and a set of rules enabling the agent to reason about those beliefs. Each belief is marked by the world position that was the agent's current world position when the belief was acquired or inferred. The Decision-Space contains a set of goals extracted from the memory model and a set of rules enabling the agent to reason about those goals. Each goal is marked by the world position that was the agent's current world position when the goal was acquired or inferred. The Conversational-Space models the agents' verbal interactions in terms of exchanges of mental attitudes and agents' positionings relative to these mental attitudes. In our approach a conversation is thought of as a negotiation game in which agents negotiate about the mental attitudes that they present to their interlocutors: they propose certain mental attitudes and other locutors react to those proposals, accepting or rejecting the proposed attitudes, asking for further information or justification, etc. 12. The Action-Space records all the communicative, noncommunicative and inference actions that are performed by the agent. Details and examples about the attentional model can be found in 11.
5
Conclusion
This paper is a contribution to the debate about the notion of context which has taken place for several years in the CG community. Whereas our temporal model 8, 9, 10. presented a static representation of the various contexts of utterance found in a
366 discourse, the present approach considers that the context is built up from the accumulation of knowledge in various knowledge bases (the various spaces of the attentional model) that compose the agent's mental model. The proposed logical framework provides the temporal model of discourse with semantics that can be practically implemented in an agent's system. However, the comparison of this framework with other approaches of context modeling would deserve another entire paper.
References 1. Cohen P. R.& Levesque H. J. (1990), Rational Interaction as the Basis for Communication, in Cohen P.R., Morgan J. & Pollack M. E.(edts.) (1990), Intentions in Communication, MIT Press, 221-255. 2. Duchan J. F., Bruder G.A. & Hewitt L.E. (1995), Deixis in Narrative, Hillsdale: Lawrence Erlbaum Ass. 3. Emerson E. A. (1990), Temporal and modal logic, In van Leeuwen J. (edt.), Handbook of Theoretical Computer Science, North Holland, Amsterdam, NL. 4. Fagin R., Halpern J.Y., Moses Y. & Vardi M.Y., Reasoning about Knowledge, MIT Press, 1996. 5. Haddadi A. (1995), Communication and Cooperation in Agent Systems, Springer Verlag Lecture Notes in AI n. 1056. 6. Kripke S. (1963), Semantical considerations on modal logic, Acta Philosophica Fennica, vol 16, 83-89. 7. Moore R.C. (1995), Logic and Representation, CSLI Lecture Notes, n. 39. 8. Moulin B. (1992), A conceptual graph approach for representing temporal information in discourse, Knowledge-Based Systems, vo15 n3, 183-192. 9. Moulin B. (1993), The representation of linguistic information in an approach used for modelling temporal knowledge in discourses. In Mineau G. W., Moulin B. & Sowa J. F. (eds.), Conceptual Graphs for Knowledge representation, Lecture Notes on Artificial Intelligence, Springer Verlag, 182-204. 10. Moulin B. (1997), Temporal contexts for discourse representation: an extension of the conceptual graph approach, the Journal of Applied Intelligence, vol 7 n3, 227255. 11. Moulin B. (1998), A logical framework for modeling a discourse from the point of view of the agents involved in it, Res. Rep. DIUL-RR 98-03, Laval Univ., 16 p. 12. Moulin B., Rousseau D.& Lapalme G. (1994), A Multi-Agent Approach for Modeling Conversations, Proc. of the International Conference on Artificial Intelligence and Natural Language, Pads, 35-50. 13. Rao A.S.& Georgeff M. P. (1991), Modeling rational agents within a BDI architecture, In proceedings of KR'91 Conference, Cambridge, Mass, 473-484. 14. Segal E.M. (1995a), Narrative comprehension and the role of Deictic Shift Theory, in 2, 3-17. 15. Segal E.M. (1995b), A cognitive-phenomenological theory of fictional narrative, in 2, 61- 78. 16. Sowa J. F. (1984). Conceptual Structures. Reading Mass: Addison Wesley.
Computational Processing of Verbal Polysemy with Conceptual Structures Karim Chibout and Anne Vilnat Language and Cognition Group,LIMSI-CNRS, B.P. 133, 91403 Orsay cedex, France. chibout, vilnat @lims i. fr
A b s t r a c t . Our work takes place in the general framework of lexicosemantic knowledge representation to be used by a Natural Language Understanding system. More specifically, we were interested in an adequate modelling of verb descriptions allowing to interpret semantic incoherence due to verbal polysemy. The main goal is to realise a module which is able to detect and to deal with figurative meanings. Therefore, we first propose a lexico-semantic knowledge base; then we present the processes allowing to determine the different meanings which may be associated to a given predicate, and to discriminate these meanings for a given sentence. Each verb is defined by a basic action (its supertype) specified by the case relations allowing to specify it (its definition graph), that means the object, mean, manner, goal and/or result relations which distinguish the described verb meaning from the specified basic action. This description is recursive : the basic actions are in turn defined using more general actions. To help interpreting the different meanings conveyed by a verb and its hyponyms, we have determined three major types of heuristics consisting in searching the type lattice, and/or examining the associated definitions.
1
Introduction
Our work takes place in the general framework of lexico-semantic knowledge representation to be used by a Natural Language Understanding system. More specifically, we were interested in an adequate modelling of verb descriptions allowing to interpret semantic incoherence due to verbal polysemy. The main goal is to realise a module which is able to detect and to deal with figurative meanings.We studied two complementary thrusts to model polysemy : (a) lexico-semantic knowledge representation, (b) processes to interpret the different meanings which may be associated to a given predicate, and to discriminate these meanings for a given sentence. After an outline of some metaphor examples that justified our approach, we will present links between verbs within a lexical network and the semantic structure associated with each of them. We will finally define the model of polysemy propounded from this representation formalism; in particular, selection rules within the network in order to process figurative meanings of verbs.
368
2
Polysemy,
metaphors
and
figurative
meanings
The distinction between polysemy and homonymy must be clearly distinguished : two homonyms only share the same orthography, two polysems share semantic elements. In case of homonymy, the solution is to create as many concepts as necessary. Otherwise, in case of polysemy the different senses of a word are mostly figurative meanings and derive from its core meaning. Thus, it is necessary to be able to determine this core meaning, and the derivation rules implied in this senses elaboration. The following examples illustrate this phenomenon. Lexical metaphors are created by selecting words specific semantic features . In the following example, both nouns s h a r e / s p h e r i c a l / f e a t u r e . 1)La terre est une orange. (Earth is an orange.) 1 The characteristic feature used in the comparison may also be taken in a figurative meaning, and the phrase is twice non literal. 2) Sally is a block of ice. The feature / c o l d / o f the ice (literal meaning) is assimilated to the feature / c o l d / o f human character (figurative meaning). This characteristic may be true or assumed (in the beliefs) : 3) John is a gorilla, to signify a man with violent, brutal manners; whereas the ethologist will insist on the peaceful manners of this animal. The same metaphor may convey multiple meanings depending on the context, by selecting different semantic features. In 3), gorilla may also m e a n / h a i r y / o r even/(physically) strong/. Figure interpretation consists in selecting one of the semantic characteristics among those which define the metaphoric term. When multiple meanings are possible, they are semantically related as they come from a unique representation. Polysemy is also considered as in context (re-)building process from a unique representation. We pay most attention to semantic incoherence resolution due to verbal polysemy. Analysing multiple meanings of French verbs allows us to precise the semantic representations from which they are elaborated. 4) Les vagues couraient jusquaux rochers. (The waves run towards the rocks) The verbal metaphor in 4) may be interpreted in replacing to run by to move quickly, which both are implied by the semantic description of this verb. Roughly speaking, the semantic features associated to to run are :/to m o v e / + / w i t h feet/ + / q u i c k l y / . . . Hyperonym is not the only part of the meaning which is used to build a figurative meaning. 5) La robe dtrangle la taille de la jeune fille. (The dress constricts the young girls waist, with the French verb dtrangler, which literally means to strangle, to translate the notion conveyed by to constrict). In this example to strangle is defined as "to suffocate by grasping the neck"; the semantic incoherence cannot be resolved by the hyperonym but by the selection of the f e a t u r e / g r a s p / (synonym of to constrict) which specifies the method used to do the action. To find 1- ~in this paper, the examples illustrating polysemy will generally be given in French, with a translation in English, to maintain their polysemous nature, which will probably lost their character in English. Being not English native speaker, it was difficult to always find analaguous examples, and to be sure that they convey the same senses.
369
the different meanings of a predicate, always semantically related, it is necessary to select its hyperonym , or to extract another part of its definition, or to combine both mechanisms (see for example the interpretation of to run in 4). These polysemous behaviours lead us to propose a hierarchical representation of the concepts, completed for each concept by a precise semantic description allowing to express semantic features that differentiate it from its father (direct hyperonym) and from its brothers in the hierarchy. This representation is implemented in the conceptual graph formalism ? : the hierarchy will take place in the type lattice, and semantic descriptions will be translated in type definitions. 3
Ontology,
definitions
and
conceptual
graphs
From the preceding study, it is clear that the best suited tool to build the ontology is a dictionary to obtain the different meaning components. The entries constitute rather precise descriptions generally including the hyperonym and referring to verbs whose meanings are related to the one defined. The different relations (such as mean, manner, goal,...) that specify the verb with respect to its hyperonym are also given. Yet, the definitions in a dictionary are not always homogenous concerning their structure and their content ?, ?. Thus it is impossible to rely only on a dictionary to build our network.The method used to organise verbal concepts has been divided in two steps. Firstly, we have analysed about a hundred verbs in French. These concepts have been categorised in details following precise criteria, such as a systematic definition of the kind of the relations between the verb and its semantic features. The representation of each lexical item is called conceptual schema, and corresponds to an enhanced dictionary definition. Each conceptual verb is given in terms of its nearest hyperonym (the central event) and some semantic cases which specify it. In addition to the classical case relations (agent, object, mean,...), four cases are essential for a complete verb description : the manner an event is realised, the method used to realise it, the result of the event and its intrinsic goal. For example, the verbs to cut and to cover have the following semantic descriptions : t o c u t : to divide (nearest hyperonym) a solid object (object) into several pieces (result) using an edge tool (mean) by going through the object (method) t o c o v e r : to place (nearest hyperonym) something (object) over something else (support)in order to hide it(goal1) or protect it (goal2). The verb hierarchy is organised following the case relations which are associated. A verbal concept is hyperonym (respectively hyponym) of another one if they share a common hyperonym and if the case structure of this verb presents one of the following feature : (a) lack (respectively presence) of a value defined for a given case, for example to divide is hyperonym of to cut, because the definition of to cut includes a mean and a method; (b) presence of a case with multiple value (respectively unique value), for example to cover is hyperonym of to plate and to veil which only include one of the possible goals (respectively to protect and to hide) ; (c) presence of a case with a generic value (respectively specific value), for example to decapitate is hyperonym of to guillotine; the mean case of the first
370
(edge tool) is a sub-type of the one of the second (guiliotine).This b o t t o m - u p building of the hierarchy allows us to define some large semantic classes. Thus, we determine about fifteen primitives appearing to be similar to the classical case relations, and mostly corresponding to state verbs : Owner (ex : to own), Location (ex : to live in), Container (ex : to contain), Support(ex : to support), Patient (ex: to suffer), T i m e (ex: to exist), Experiencer (ex : to know),... At the J
(a)
Acilon
F~re,C ~ r 9..
FaireCe~.r po,~ibllite .
.
.
.
.
.
.
.
.
.
.
Empecher (Prevent) Etoeffer (Suffocate)
FaireC~eml~ FaireMomir
Museler (Muzzle)
Fal~-r
.
Tue~ (Kill)
Arretex (Stop)
Fairc Est~cr
FaireCesse~Paraitrc
S~ (S/~ Divisef (Divide)
|
(Mince)
Gommer (Rubout)
--9
FaimEntrer
Cachet Dissiper Effa~r (Hide) (Dissipate) (Erase)
Asphyxie~ Etrangler Noyer Decapiter Egorgex Peigner Couper Casser Fragmentef ""' (Asl~yxiate) (Strangle) (Drown)(Decapilate)(CutThr~t)(Comb) (Cut) (Bleak) (Fragmen0
..
999 FalrcDeveairLoc
Fai,eDisnarmtm ~
Intermmpre Demeler (ntem~t) (Unravel)
Guillotiner (Guillotine)
~'lir
Imp~ter (Impo~)
Eclipsef (Eclipse)
FaimPenetrer (Penetrate) Instiller (Instill)
"9
Bds~ (Smash)
(c)
give-food:*x
~ ~ ' , , , . ~
animate:*z
Fig. 1. Extract of the hierarchy (a) and description of (c) type definition graph
to feed: (b) canonical graph and
higher level of the hierarchy, the process verbs and the action verbs derive from these state primitives. So processes are expressed as Devenir (become)/Cesser (cease) + primitive, and action verbs as FaireDevenir/FaireCesser + primitive : - Devenir Contenant -
(to fill, to eat, to drink), Devenir Temps (to born), DevenirExpdrienceur (to learn) CesserContenant (to (become) empty), CesserTemps (to die), CesserExpdrienceur (to forget) FaireDevenir Contenant (to fill, to water), FaireDevenir Temps (to create, to give birth to, to calve), FaireDevenirExpgrienceur (to teach ) - FaireCesserContenant (to empty), FaireCesserTemps (to interrupt, to kill)
-
Our study has concerned about 2000 French verbs. Thus we have constituted a large lexico-semantic network corresponding to more than 1000 verbal concepts,
371
organised inside a hierarchy (see Fig.l). For each node, the description consists in : a sub-categorisation frame, a case structure (represented in a canonical graph) and a definition (represented in a definition graph), describing how it processes its hyperonym (i.e. its super-type in the hierarchy), (see Fig.l). The association word/concept is defined in a global table. These descriptions have allowed us to build the lexico-semantic knowledge base used by the Natural Language Processing system developed at LIMSI ?. The definition graphs have been built following the method we describe in the first part of this paragraph. Thus we make sure that the definitions are not axi-hoc definitions, following a top-down building of the hierarchy, but respect the meanings of the words they represent. But, at that time we cannot verify that the constraints due to inheritance mechanismare verified : this constitutes the following step of our work. 4
Verbal
polysemy
: elements
of interpretation
As we have said it, we built the hierarchy we presented just above to be able to interpret lexical polysemy of French verbs. We assume that there exists a (proto)typical meaning associated to each verb. The prototype is the more often attested meaning. The so-called figurative meanings derive from this prototypical meaning. These figurative meanings are related to the semantic structure of the verb by taking into account either the nearest hyperonym (as in example 4), or other parts of the conceptual schema (as in example 5). But other processes are necessary to interpret metaphoric senses, based on primitives substitutions. Let us consider the interpretation of the following example: 6) La fermi@re nourrit le feu avec des branchages. (The farmer's wife f e e d s the fire with lopped branches (to keep going the fire)) The constraints expressed in the canonical graph of to feed are violated. But the definition graph (see Fig.l) includes the particular meaning of this word (in example 6) : it is given in the sub-graph corresponding to to maintain (in French entretenir which means to keep going in this context). The semantic constraints expressed in the canonical graph of to maintain are then fulfilled (particularly for the type of the object fire). Selecting parts of the semantic representation of lexical items is not the only process used to build figurative meanings ; nevertheless, as we show it just below, it is a necessary condition to be able to elaborate these meanings.Some figurative meanings rely on conceptual metaphors ?. Thus, nourrir quelqu 'an de ragots (to feed someone with ill-natured gossips), abreuver quelqu'un de connaissances (to swamp someone with knowledge) may be interpreted from the metaphor Mind is Container. Such conceptual metaphors are interesting because they are rather general : they apply not only to a given verb, but to a whole class of verbs. Thus, gaver de connaissances (to fill ones mind with knowledge), se nourrir de lectures (to improve the mind with reading), dgvorer un livre (to devour a book) will be interpreted using the metaphor Mind is Container. These interpretation processes do not invalidate our model for polysemy. The semantic representation
372
we propose is based on a hierarchy, thus it is possible to go up to the semantic primitives from which verbal items are dependant. The extracts of the type lattice in Fig.2 clarify the way the interpretation is done. Semantic primitives play a central role to interpret figurative meanings due to conceptual metaphor. Thus, all the metaphoric uses, such as abreuver quelqu'un de connaissances (to swamp someone with knowledge), for which the analogy Mind is container will be relevant, will be interpreted by substituting the primitive CONTAINER to the primitive EXPERIENCER. From the metaphoric verb, the semantic class corre-
Absorber SeRemplir Deve~nna(~'c~ (ab~j,~) (fill) / / ~ / ~ ApprcndreComprendre DP:cldffre~ Avalor "'" (learn) (understand) (decil~he~ ',swallow) ~eNourrir Boire Lira :e~d~er (drink) (read)
I,
,~br~uv7
~foe~ll~r
(inculcate) (tea~)
I ~o~r~
(proclaim)
(eat)
D~s
SeGaver (devour)(gorgeoneself)
Fig. 2. Interpretation examples
sponding to the primitive is reached. Then the substitution rule (Container -> Experiencer) is applied, and the pertinent concept (FaireApprendre for Abreuver (to water) and Lira (to read) for D4vorer (to devour) is searched for in this branch using canonical graphs. The searched concept must be described with a canonical graph expressing constraints that are verified by the arguments of the metaphoric sentence (in our examples knowledge and book) The most difficult point is due to the fact that canonical graphs don't always discriminate the pertinent concept from the others belonging to the same branch (for example FaireApprendre, Inculquer (to inculcate), Enseigner (to teach), etc. have identical canonical graphs).This technical difficulty doesn't invalidate the model proposed for conventional metaphoric senses. Conceptual metaphors are not applied casually ; it is the fact that a verbal item is related to a given primitive in its semantic structure which justifies the use of this or that metaphor. There is no "spontaneous generation" of meaning; verbs contain in their conceptual schemas the entry points towards other meanings. Following examples illustrate the classic metaphor of SPACE -> TIME : 7) couper la parole (to interrupt someone),interrompre (to interrupt)
373 8) briser une conversation (to break off a conversation)interrompre brusquement (to suddenly interrupt) 9)entrecouper ses phrases de sanglots (to interrupt one's phrases with sobs) interrompre frgquemment (to frequently interrupt) All the verbs couper, briser, entrecouper depend on the class FaireCesserEspace (expressing spatial discontinuity). Interpreting metaphors consists in substituting class FaireCesser Temps (temporal discontinuity) to this class. For the two last examples, the adverbs attached when they are interpreted belong to the definitions of the verbs (to smash briser: break suddenly... ; entrecouper : to cut frequently... About ten substitution rules of this kind have been determined. They are probably not exhaustive, but have nevertheless being tested on 1000 verbs. Moreover, the fact that common meanings are shared by a class of verbs (regrouped because they belong to a same branch) partially validate our ontology. Such figurative meaning interpretations are rather poor. The following example illustrates this point. 10) Le paysan coupait souvent par le champ de bld.(The farmer often cuts through the wheatfield) Polysemy is solved by selecting the case method ,i.e. to go through associated to cut in its definition graph (see Sect. ??). But replacing to cut by to go through looses information : the implicit notion of spatial reduction (or more exactly moving distance reduction) conveyed by to cut in this sentence is lost. A more precise interpretation will need to determine which meaning parts of the metaphoric verb have to be transferred to the inferred meaning.
5
Related
works
Lexical classifications based on semantic criteria are relatively numerous in artificial intelligence. Semantic nets are main lexical knowledge representation modes; but they essentially concern nouns. However, Levin ? proposes an English verbs summary classification founded on syntactico-semantic criteria. The hierarchy lacks accuracy : Levin gets main classes (occasionally sub-classes) in which verbs are listed; but, on no account, there are semantic relations defined between verbs within a same class (or sub-class). Verbs within a same class are assimilated to syntactic synonyms ; therefore from a semantic point of view, these verbs may convey rather distant meanings. Some authors try to build precise semantic hierarchies of English verbs on a large scale ?. They emphasise the complexity of this task, notably due to the different semantic fields implied in relations between verbs having connected meanings. Miller and his collaborators determine a particularisation relation Mlowing to group different semantic components that distinguish a verb from its hyperonym. This relation between two verbs V1 and V2 (V1 hyponym of V2) is named troponymy and is expressed by the formula "accomplish V1 is accomplishing V2 with a particular manner". For example,battle, war, tourney, duel,..are troponyms of the verbal predicate fight. Troponyms of communication verbs imply the speaker intention or his motivation to communicate, as in examine, confess, preach,.., or the communication
374
media used : fax, email, phone, telex, .... Relying on these principles, they implemented a large lexical network (Wordnet) that organise verbs and other lexical categories in terms of signified. Our work is in part inspired by their approach, but we systematically precise the kind of relation between t r o p o n y m concepts (case relations).
6
Conclusion
We have presented linguistic and computational aspects of verbal polysemy. Figurative meanings of a predicate represent as m a n y shifts in meaning from a unique semantic structure that define this verb. The resolution processes consist in a simple selection of the pertinent elements of this representation (i. e. the pertinent subgraph of the definition graph) or in the same selection plus an inference from one of these elements (conceptual metaphors). Our knowledge base has been implemented in conceptual graphs but till need to be verified concerning possible incoherence due to the inheritance mechanism. The psychological validity of the representation and of the treatment we propose is also being tested in an experiment. We don't claim that our work is exhaustive neither in the semantic representation proposed, nor in the different acceptions understanding processes. We define a general framework in which the links between the multiple senses of a verb m a y be expressed. Polysemy is one of the m a j o r characteristics of natural language, it is also one of the most complex to apprehend. Moreover, as the other contextual phenomena (anaphora, implicit, etc.), polysemy is one of the m a j o r difficulty in Natural Language Processing.
References 1. Chibout, K., Masson, N. : Un r@seau lexico-s~mantique de verbes construit & partir du dictionnaire pour le traitement informatique du fran~ais, Actes du colloque LTTAUPELF-UREF Lexicomatique et Dictionnairique, Lyon, Septembre 1995. 2. Lakoff, G., Johnson, M. : Les m6taphores dans la vie quotidienne. Collection "Propositions", les 6ditions de Minuit (1985). 3. Levin, B. : English verb classes and alternations, University of Chicago Press, 1993. 4. Martin, R. : Pour une logique du sens. Linguistique nouvelle. Presses Universitaires de France, (1983). 5. Miller, A. G., Fellbaum, C., Gross, D. : WORDNET a Lexical Database Organised on Psycholinguistic Principles. in Zernik (Ed.) : Proceedings of the First International Lexical Acquisition Workshop, I.J.C.A.I., D~troit,(1989). 6. Searle, J.R. : Metaphor in Andrew Ortony (Ed.) : Metaphor and Thought. Cambridge University Press (1979), pp. 284-324. 7. Sowa J. Conceptual Structures : processing in mind and machine. AddisonWesley.Reading, Massachussetts, (1984). 8. Vapillon J., Briffault X., Sabah G., Chibout K. : An object oriented linguistic engineering using LFG and CG, ACL/EACL Workshop : Computational Environments for Grammar Development and Linguistic Engineering, Madrid (1997).
Word Graphs: The Second Set C. H o e d e I a n d X. Liu 2 1 University of Twente, Faculty of Mathematical Sciences, P.O. Box 217, 7500 AE Enschede, The Netherlands c. hoede~math, utwente, n l
2 Department of Applied Mathematics, Northwestern Polytechnical University, 710072 Xi'an, P.R. China
A b s t r a c t . In continuation of the paper of Hoede and Li on word graphs for a set of prepositions, word graphs are given for adjectives, adverbs and Chinese classifier words. It is argued that these three classes of words belong to a general class of words that may be called adwords. These words express the fact that certain graphs may be brought into connection with graphs that describe the important classes of nouns and verbs. Some subclasses of adwords are discussed as well as some subclasses of Chinese classifier words.
K e y words: Knowledge graphs, word graphs, adjectives, adverbs, classifters. A M S S u b j e c t Classifications: 05C99, 68F99.
1
Introduction
W e refer t o t h e p a p e r of H o e d e a n d Li 1 for a n i n t r o d u c t i o n t o k n o w l e d g e g r a p h s as far as n e e d e d for this p a p e r . W e o n l y recall t h e following. W o r d s are c o n s i d e r e d to b e r e p r e s e n t a b l e b y d i r e c t e d labeled graphs. T h e vertices, or tokens, are i n d i c a t e d b y squares a n d r e p r e s e n t somethings. T h e arcs have c e r t a i n t y p e s t h a t are c o n s i d e r e d t o r e p r e s e n t t h e relationship b e t w e e n s o m e t h i n g s as recognizable b y t h e mind. T h e g r a p h s t h a t we will discuss are t h e r e f o r e c o n s i d e r e d t o b e s u b g r a p h s of a huge mind graph, r e p r e s e n t i n g t h e knowledge of a m i n d a n d t h e r e f o r e also called knowledge graph. T h e s e knowledge g r a p h s are v e r y similar t o c o n c e p t u a l g r a p h s , b u t are r e s t r i c t e d as far as t h e n u m b e r of t y p e s of r e l a t i o n s h i p is concerned. T h e r e are two t y p e s of relationships. T h e b i n a r y relationships, t h e u s u a l arcs, m a y have t h e following labels:
376
EQU : Identity SUB
: Inclusional
part-ofness
Alikeness D I S : Disparateness CAU : Causality OaD : Ordering P A R : Attribuation SKO : Informational dependency. ALI
:
The SKO-relationship is used as a loop to represent universal quantification. Next to the binary relationship there are the n-ary frame-relations. There are four of these. : Relationship of constituting elements with a concept, being a subgraph of the mind graph. NEGPAR : Negation of a certain subgraph. P O S P A R : Possibility of a certain subgraph. NECPAR : Necessity of a certain subgraph. FPAR
These four frame relationships generalize the wellknown logical operators. If a certain subgraph of the mind graph is the representation of a wellformed proposition p, this proposition is represented by the frame, ~p is represented by the same subgraph framed with the N E G P A R relationship and the modal propositions ~p and Rp are represented by the same subgraph framed with the POSPAR and the N E C P A R relationship respectively. In this way logical systems can be represented by different types of frames of very specific subgraphs. We refer to Van den Berg 2 for a knowledge graph treatment of logical systems. So logic is described by frames of propositions. If a subgraph of the mind graph does not correspond to a proposition the framing, and the representation of the frame by a token, may still take place. Any such frame may be baptized, i.e. labeled with a word. The directed ALI-relationship is used between a word and the token to type the token. Thus ALI
(
STONE
is to be read as "something like a stone". Note that the token may represent a large subgraph of the mind graph. In particular verbs may have large frame contents. Verbs are represented in the same way. So ~
ALI
HIT
377
is t h e way th e verb HIT is represented. T h e directed EQu-relationship is used between a word and a token to valuate or instantiate the token. So PLUTO
EQU
~O <
ALI
DOG
is to be read as "something like a dog equal to P l u t o " . T h e min d g r ap h is considered to be a wordless represent at i on of t h o u g h t relationships between units of perceptions. T h e words come in w hen certain subgraphs are "framed and named". At the most elementary level
the frame contents may just be one relationship. These are the first word graphs to start with. It turned out that prepositions have such very simple structures and for that reason they formed the first set of word graphs. The frame contents of frames representing nouns and verbs express the definitions of the concepts (note that frames do literally take other concepts together). A lexicon of word graphs is being constructed at the University of Twente. In order to make the theme of this paper, adwords, clear we recall the preposition OF. There were three word graphs given in total graph form, where arcs are also indicated by vertices with the type of relationship as label. These three word graphs were:
Suppose we have t he word combination RED BALL. T h e word BALL can b e represented, according to our formalism, by <
ALI
BALL
Now RED is a word a t t r i b u t e d to t he word ball in t he sense t h a t its word g r a ph is linked to t he word graph of BALL. For RED we would take t h e following word graph into t he lexicon:
RED
EQU
~
~
ALI
COLOUR
analogous to the graph for PLUTO. Now we say "red is the colour of the ball" and the word graphs are to be linked in a way that we use the word
378
OF for. As we see colour as an exterior attribute of ball we choose the
PAR-relationship to represent RED BALL by r
ALI
BALL
PAR l RED
EQU
~
r
ALI
COLOUR.
It is in this way t h a t RED is a word linked to the word BALL. It is usually called an adjective. Note that without the word RED we would still have COLOURED BALL. Also note t h a t we do not say RED COLOUR but do say T H E C O L O U R RED. It should be clarifying t h a t HAVE w a s seen as BE W I T H , BE being represented by the e m p t y frame and W I T H having word graph 9 . So the graph might also be brought under words by "the ball has colour red". Note t h a t people m a y differ in opinion on expressing RED BALL. W e have just given our view. Quite a few adjectives are similar to RED and can be seen as adwords linked by the PAR-relationship. However, there are other ways how word graphs can be linked to the word graph of a noun and a verb. One particular way is by the FPAR-relationship t h a t links the constituents of a definition to the defined concept. Suppose, for example, t h a t a stone is defined as '% structure of molecules" (which would not be precise enough, but lexica contain scores of unprecise definitions). If the type of molecules is denoted in the graph, by means o f a n E Q U - a r c , a s silicon, we m a y speak of a SILICON S T O N E and SILICON is now functioning as an adjective. This t y p e of adjective is of another n a t u r e t h a n the adjective RED, the difference being expressed by the way of linking, one time by a PAR-relationship and the other time by an F P A R relationship. T h e essential linguistic phenomenon is t h a t word graphs are linked to other word graphs. As this can be done in various ways, to nouns and to verbs, it is more natural to speak of adwords. We will discuss adjectives and adverbs from this view point. The interesting phenomenon of classifiers in Chinese is closely related to our way of viewing adwords. In Chinese it is not well-spoken to say "a spear". One should say "a stick spear", where stick is a word expressing a classifying aspect of spear. A HORSE is not I MA but should be expressed a s I PI MA, where PI is the classifier, the meaning of which seems to have been lost in the course of time. Yet the adword PI should be expressed in proper speaking. There are more t h a n 400 of these classifiers. We will discuss several of t h e m from the same view point as before and give word graphs for them.
379
In the word graph project we plan to start with studying structural parsing as soon as sufficient word graphs are available. This will take a third set of word graphs, containing the remaining word types. 2
Adwords
In this paper we cannot give an extensive treatment of the grammatical aspects of adjectives, adverbs and classifiers. We will restrict ourselves to some major subclasses of these adwords. The book of Quirk, Greenbaum, Leech and Svartnik 3 was used for reference, more specifically Chapter 5. Our examples are chosen from this book. We will not stress syntactic problems. A certain knowledge graph is brought under words by expressing by words certain of its subgraphs. The way this is done differs from language to language. In an extremely simple example we have that RED BALL in English is uttered as BALLON ROUGE in French. Any knowledge graph admits an utterance path. Usually there axe several utterance paths, i.e. ways of uttering the words, having word graphs that cover the knowledge graph, in a linear order. As our example RED BALL or BALL WITH COLOUR RED shows, there are ways of bringing a knowledge graph under words that are more precise than others. In natural language often the less precise descriptions, like RED BALL, are used. That RED is a colour and that colour can be attributed to a BALL is background knowledge for these concepts RED and BALL that enables the short but incomplete utterance path. A lexicon may contain a word graph for RED that includes the colour concept, but a word graph for BALL that does not mention the possibility of linking to another concept by means of a PAR-relationship. A machine may then not be able to create a connected knowledge graph for RED BALL, unless it is instructed to interpret the syntactical fact that both words axe uttered together as justifying the linking of their word graphs by some arc. For a more elaborate discussion of the interplay of semantics and syntax we refer to the thesis of Willems 4.
2.1
Adjectives
As word graphs are supposed to grasp the semantics of a word, according to the slogan "the structure is the meaning", we focus on the Paragraphs 5.37 to 5.41 in Quirk et al., in which they give a semantic subclassification of adjectives.
380
T h e y make the distinctions stative/dynamic, gradable/non-gradable and inherent/non-inherent. Their Table 5:2 looks as follows: stative gradable inherent +
+
+
BLACK
(coat)
+
+
-{-
--
-~-
BRAVE(man) B R I T I S H (citizen)
~-
-~-
--
NEW
-
(friend)
Adjectives are characteristically stative, most are gradable and most are inherent. The normal adjective type is all three, like B L A C K . Quirk et al. give the imperative as a way to distinguish stative from dynamic adjectives. One can say B E C A R E F U L but not B E T A L L o r B E B L A C K , B E B R I T I S H r e spectively B E NEW. One can say BE B R A V E , explaining the minus sign in the first column. B L A C K E R , BRAVER and NEWER are gradings but BRITISHER is not possible, explaining the minus sign in the second column. Inherent adjectives characterize the referent of the noun directly. T h e y consider BLACK, TRUE and BRITISH to be inherent adjectives. Before undertaking our own discussions we should reproduce their premodification examples on page 925 in which combinations of adwords are mentioned. deter- general age miners etc. THE
HECTIC
THE
EXTRAVAGANT
colour participle
GREY
A
SMALL
HIS
HEAVY
d e n o m - head inal SOCIAL LIFE
A INTRICATE
noun
LONDON SOCIAL LIFE
A
SOME
provenance
OLD
CRUMBLING
CHURCH
TOWER
CRUMBLING
GOTHIC CHURCH
TOWER
INTERCHINESE LOCKING GREEN CARVED
NEW
DESIGNS JADE
IDOL MORAL RESPONSIBILITIES
It is clear t h a t proposals have been m a d e for what Quirk et al. call sem a n t i c sets. We will do exactly that, but the basis of our proposal will be the types of relationships a noun, or verb, can have with other words. The FPAR-adwords We use the FPAR-relationship to represent the definitional contents of a concept. Any word used in the definition might
381
be called an FPAR-adword. However, usually some restrictions are made. If the definition contains a preposition like OF this word is not considered an adword. An other remark that should be made is that a definition may contain the concept of colour. In that case the adjective, say GREY, is considered to be inherent. The definition of an elephant m a y contain the statement that it is a grey animal. In BLACK COAT, however, the adjective cannot be considered to be inherent, like in the table given. The point is t h a t colour is attributed subjectively, a red ball in green light looks black. Even in white light objects m a y have different colours for colour blind persons. For this reason we used the PAR-relationship and consider RED to be a PAR-adword and colour to be non-inherent. Similarly BRAVE and BRITISH are disputable as inherent adjectives, for different reasons. Braveness is present according to a judgement. One is considered to be brave by others. BRAVE can be seen as an instantiation of judgement. Other adjectives of this t y p e are KIND and UGLY. BRITISH does not describe an inherent aspect either. Anything that is part of Britain, seen as a frame, can be called BRITISH. In this way the frame name determines the adjective for its constituents. BRITISH may therefore be called an inverse FPAR-~:lword. Examples of this t y p e of adjectives are LAMB in LAMB MEAT and CITY in CITY COUNCIL o r CHURCH in CHURCH TOWER.
We conclude that the restriction inherent/non-inherent had better be replaced by the distinction F P A R / N O N F P A R . For material objects a typical F P A R - a d w o r d expresses the sort of material. So in JADE IDOL, JADE d e scribes the material and is a typical FPAR-adword. If STEAM is HOT WATER VAPOUR then HOT is a n F P A R - a d w o r d a s is WATER, instantiating relative t e m p e r a t u r e and material of the vapour. Note that we speak of relative t e m p e r a t u r e as HOT is not a temperature, like FAST is not a velocity. Within a flame concepts m a y occur that allow a measure, like temperature or length. In those cases the corresponding FPAR-adwords are gradable, like in hot, hotter or long, longer. Usually these adwords do not indicate absolute t e m p e r a t u r e or length b u t relative t e m p e r a t u r e and relative length. In "a two meter man", the precise length TWO METER m a y be interpreted as an FPAR-adword too.
T h e P A t t - a d w o r d s We use the PAR-relationship to represent exterior attribuation. Judgements on a concept are typical exterior attribuations.
382
We already classified BRAVEas a PAR-adword. BEAUTIFULis another good example. An important class of words concerns space and time aspects. A ball may exist at some location at some moment in time. Its space-time coordinates will be seen as determined from the outside, i.e. by exterior attribuation, and therefore represented by a PAR-relationship. Adjectives like E A R L Y and S U D D E N belong to this class and also OLD and NEW. The link to the main concept, or head as Quirk et al. call it, is by a PAR-link that connects the time aspect to the concept in the following way ALI
SOMETHING
PART r
ALI
TIME
The word graphs for the adjectives embed the time aspect in a more elaborate word graph in order to express the various meanings. In these graphs the time of the speech act may play an important role, like in the description of tense, a theme that we will not discuss here. A speech act may occur at time to, whereas the intended description concerns something at time tl, oRen determined by the discourse of which the speech act is part. In a historical account one may read "the former king was tyrannical but the new king was a very kind person". The adjective F O R M E l t refers to a time before a certain time t 2 , when the king was replaced, the adjective N E W refers to a time after that time t2. The fact that this took place before to is apparent from the past tense coming forward in WAS.
The word graph for F O R M E R and NEW will contain an ORb-relationship. In E A R L Y reference to a time interval will have to be made, expressing that the first part of the time interval is meant. This also holds for O L D or ANCIENT. Differences between the three adjectives must come forward in the word graphs, but if these are left out by the speaker, in his choice of words, he might speak of "in the early days", "in the old days" or "in the ancient days" to express the same thing. The more elaborate word graphs may become quite large. This situation is similar for dictionaries, where bad dictionaries give short definitions, and good dictionaries try to give more precise definitions. We would like to recall here from 1 that in our theory the meaning of a word is in principle the whole graph considered, containing the word. This implies that different graphs, i.e. different contexts, give different meanings to a word.
383
T h e C A U - a d w o r d s In the representation of language by knowledge graphs verbs are represented by a token and CAC-relationships. Transitive verbs like WRITE are represented as
CAU
CAU
,
)~
ALI l WRITE whereas intransitive verbs like SLEEP are represented as CAU
ALI T SLEEP Consider the leftmost token. It represents "something writing" respectively "something sleeping". Thus W R I T I N G and SLEEPING are adjectives of that something and are, for obvious reasons, classified as CAu-adwords. The rightmost token in the first knowledge graph might represent a letter and can be described as "written letter". So the adjective W R I T T E N can also be classified as a CAu-adword. Again we should note, like for NEW, that the word graph should contain information referring to the time aspects. WINNING team, BOILING water and MARRIED couple give examples of CAw-adwords. The last example is somewhat tricky. Marrying usually involves two persons and "A marries B" and "B marries A". Then "A and B have got married", or both are "in the state of marriage". This brings us to a special class of adjectives, describing states. Suppose something is subject to a series of changes. At any time it is then in a certain state. In HAPPY girl the adjective describes a state the girl is in, "girl being happy" is doing the same. The verb B E Was represented by the empty frame. Anything in the frame Is. HAVE, which was defined as BE WITH, CAN and MUST are verbs that likewise correspond to the frame relationships that we distinguished. When they are used, they usually express states, focusing on the process rather than on the subject or object related to the process by a CAu-relationship. Yet the adjectives describing states are discussed in this section, as we stress the relationship with verbs. States are exemplified by adjectives like ABLAZE, ASLEEP or ALIVE, where descriptions of processes stand central. The check on the distinction stative/dynamic, by trying out the imperative, like in BE CAREFUL, corresponds to checking whether the adjective can be seen as describing a state.
384
It should be noted that predicative use of an adjective expresses a B E frame. T H E C A R IS H E A V Y instead of T H E H E A V Y C A R expresses the "being heavy" of the car explicitely. In Turkish D O K T O R D A D I R literally means DOCTOR AT BE. The very frequently used agglutination DIR expresses the BE-frame. Most of the a-adjectives, like ABLAZE, are predicative only. T H E H O U S E IS A B L A Z E c a n be said, T H E A B L A Z E H O U S E cannot be said. In T H E CAR IS HEAVY the use of the adjective HEAVY is predicative. The analogy is suggested by the word IS. However, in this case this word IS stems e.g. from A T R U C K IS ( D E F I N E D A S ) A H E A V Y C A R which is s h o r t c u t t e d t o A T R U C K IS H E A V Y o r e v e n T H E C A R IS HEAVY. This explains the predicative use of an adjective that is essentially an FPAR-adword. HEAVY is pushed into the role of a state describer like A B L A Z E . T h e A L I - a d w o r d s The ALI-relationship between two concepts expresses the alikeness of the concepts. This relationship m a y be seen as primus inter pares as the process of concept creation seems to d e p e n d heavily on the becoming aware of alikeness. P r o t o t y p e definitions express what has been seen as common properties of a set of somethings. Adjectives that are expressing that a concept looks like another concept m a y have specific endings. DISASTROUS expresses a similarity with a disaster and INDUSTRIOUS expresses a similarity with certain aspects of industry. Other endings are - I S H a s in F O O L I S H o r - L I K E a s in C H I L D L I K E , for example in combination with BEHAVIOUR. A special category of adjectives are ALI-adwords that are themselves n o u n s . T H U N D E R in T H U N D E R N O I S E o r T R A I T O R in T R A I T O R K N I G H T express that the noise is like heard when thunder occurs or that the knight acts like a traitor. Especially for this category of adjectives, nouns acting as adjectives, it becomes clear that the classification that we give in different types of adwords makes sense. 2.2
Adverbs
In our theory nouns and verbs are both represented by word graphs. In this respect nouns and verbs are describing concepts basically in the same way. However, nouns do not necessarily include CAu-relationships in their definition, whereas verbs do. But for this difference a verb may be seen as a special type of noun. This means that there is no basic difference in the way other words may act as adwords of verbs in comparison to the way other words act as adwords of nouns. This is also underlined by the possibility of substantivation of verbs. Compare TO PLAY, PLAYING and A PLAY.
385 We will discuss only a few examples. In our view time and location of the act expressed by the verb are natural aspects to consider in relation to the verb. Many adverbs refer to these aspects and are classified as PAR-adwords. We mention OFTEN, OUTSIDE, BRIEFLY~ EVER as examples. The explicit word graphs for these words may become quite large as rather complex aspects are expressed. Judgements and measurements are two aspects that are also often expressed by PAR-adwords. WELL, QUITE, EXTREMELY, ENOUGH, MUCH, ALMOST are reflecting judgements or measurements. A judgement may be interpreted as a subjective measurement, hence the treatment of these two aspects at the same time. CAU-adwords refer to influences or, in most cases, to consequences of the acts described by the verbs. Hence adverbs like AMAZINGLY or SURPRISINGLY may be mentioned. ALI-adwords include CLOCKWISE, or any of the many adverbs with ending -wlsE, but also words like TOO or AS are used as adverbs and clearly should be classifted as ALI-adwords. BRILLIANTLY, like a brilliant, is representative of another subclass of these adwords. FPAR-adwords are somewhat rare. In "the country is deteriorating economically" the adverb ECONOMICALLY indicates in what respect the country deteriorates. The country's economy must be seen as frame part and for this reason ECONOMICALLY may be classified as an FPAR-adword. Two remarks are to be made still. Firstly, there is a set of words, mentioned by Quirk et al., that are sometimes used as adverbs, but actually refer to the use of logic in language. NEVERTHELESS, HOWEVER, THOUGH, YET, SO, ELSE are such words. We would prefer to include them in a special third list of words graphs with NO and PROBABLY, to mention some other potential adverbs. Secondly, we would like to comment on an example of Quirk et al.; A FAR MOR EASILY INTELLIGIBLE EXPLANATION, showing compilation of adwords. In traditional discussion we would have to decide whether we are dealing with adjectives or adverbs. The great advantage of our theory is that this discussion is avoided. Instead one may have the discussion about the classification that is to be given to each of the adwords. However, once a knowledge graph, expressing the text, is made out of the word graphs, the way these word graphs glue together, by which type of arc, immediately gives the answer in that discussion. An important aspect of this example is that the sheer possibility of compiling adwords in language is an argument for the modelling of language in terms of knowledge graphs, built from word graphs.
386
2.3
Classifiers in the Chinese Language
In Chinese, a special class of words are the quantity words, as Chinese prefer to call them, which are also called classifiers. F P A R - c l a s s i f i e r s One of the most frequent q u a n t i t y words in KO, used in combination with a word like TUNG TSI, THING. For A THING in Chinese we should say, YI KO TUNG TSI. There are m a n y nouns for which the q u a n t i t y word KO is used. As this example already shows the q u a n t i t y word m a y be seen as a word naming a subframe of a frame carrying the n a m e of the noun. Hence here the relationship between noun and q u a n t i t y word is an FPAR-relationship, the q u a n t i t y word is an FPAR-adword and, in terms of knowledge graphs, we get the following graph.
~ FPAR l 9
ALI
NOUN
QUANTITY WORD.
Here, 9 indicates the something described by the q u a n t i t y word. Although a word like KO is not felt to have a meaning of its own by Chinese, it should refer to something felt as an essential property of the following noun. Many quantity words express the property of the noun t h a t it describes a unit. Another example YI FENG XIN for A LETTER, shows an adword FENG, t h a t in the combination is not felt to have a meaning. However, there is a verb FENG for folding and it is clear t h a t XIN (LETTER) is described in a way t h a t expresses the property t h a t letters usually consist of folded paper. For A WELL we have YI YAN JING, where the q u a n t i t y word YAN has some meaning, namely HOLE. If a well is the configuration of water coming from a hole in the ground, the hole property of a well is clearly mentioned as property not to be deleted in the description. Q u a n t i t y words like these should perhaps better be called property words or classifiers. O t h e r c l a s s i f i e r s Next to the FPAa-relationship to a noun of a property word, there are m a n y other classifiers t h a t do have a separate meaning, but are used in combination with a noun to express a certain feature. These q u a n t i t y words can be divided into 13 subclasses. We will discuss this in more detail now and start with a typical example: YI HU SHUI, A POT OF WATER. In English too a class description of water is necessary. HU, or POT, is an adword for SHUI, or WATER. A pot typically contains a
387
liquid, as a container it has a specific shape and is m a d e of some material like China, metal or class. T h e important feature is that of containing a liquid. In knowledge graph representation we have in first instance
LIQUID
POT
EQU ALII WATER
IALI
,_rn
PARI
9
SUB
IPAR ,~KI
ALI l SPACE
l ALI SPACE
T h e graph can be extended to include the other features of P O T like shape or material, b u t the containment feature gives the direct link to the noun. In terms of adwords we cannot say that POT is a eAR-adword, the linking to WATER is more complex, in fact our example is a clear example of a relationship in knowledge graph theory. T w o concepts are part of one graph and it is this graph that characterizes the relationship between the two concepts. If we have to baptize this relationship we would choose the word CONTAINER or CONTAINMENT. So HU is an adword of SHUI linked to it by a relationship of complex nature, that is however representable by the basic types of arcs. There are quite a few adwords of the t y p e CONTAINER, PING 'or BOTTLE is just one other example. We now list the 13 subclasses by giving a characterization of the class, like CONTAINER~ an example, like YI HU SHUI, A POT OF WATER and the relevant structure relating the quantity word and the noun in one other
case. 1. CONTAINMENT E x a m p l e : YI HU SHUI (a POT of water). G r a p h : see above.
2. SIMILARITY E x a m p l e : YI DI SHUI (a DROP of water)
388
Graph: LIQUID
DROP
EQU ALII ,el WATER PARI ALI l SHAPE
IALI 9 ALI
IPAR TALI SHAPE
Remark: This subclass too is quite numerous. Because of lack of space we just mention the 11 other subclasses with an example only. 3. SET E x a m p l e : YI CHUAN PUTAO (a CLUSTER of grapes) 4. TIME E x a m p l e : YI TIAN SHIDIAN (a DAY of time) 5. LENGTH Example: YI MI CHANG (a METER of length) 6. AREA E x a m p l e : YI YINGMU TUDI (an ACRE of land) 7. WEIGHT E x a m p l e : YI KE YINZI (a GRAM of silver) 8. VOLUME Example: YI SHENG SHUI (a LITER of water) 9. MONEY E x a m p l e : ZHE JIAZHI YI MEIYUAN (this costs a DOLLAR). 10. CHINESE CHARACTER E x a m p l e : "WANG" ZI BIHUA YOU SI GE ("WANG" word STROKE(S) has four element(s)). 11. NUMBER Example: YI DA WAZI (a DOZEN of socks). 12. ACTION Example: DATA YI ZHANG (hit him a PALM). 13. COMPLEXES Examples: SAN JIACI FEIJI (three TIMES of flight).
In a more elaborate version of this paper word graphs and remarks are given for these other subclasses.
389
3
Discussion
In the first paper on word graphs nouns, verbs and prepositions were discussed. In this paper a second set of word graphs has been presented, that we called adwords. Seeing adjectives, adverbs and classifiers in Chinese as instances of words that glue to other words like nouns or verbs in certain specific ways a completely different view on these wordclasses has been developed. We do not have enough space here to show that our way of classifying, according to the way graphs are linked, indeed solves quite a few problems concerning them. In fact it should be stressed that the correctness of our m e t h o d of representing words is still to be proven by showing that linguistic problems can indeed be solved. Preliminary results show that the approach is really quite promising. B u t first we have to construct a word graph lexicon. In principle we have covered most types of words already. There remain some other types, like the "logical" words or wordcompositions like e.g. DISCONNECT, and we plan to consider t h e m in a third paper. Chinese quantity words will be collected extensively in a special report. References 1. Hoede, C., Li X.: Word Graphs: The First Set, in Conceptual Structures: Knowledge Representation as Interlingua. Auxiliary Proceedings of the Fourth International Conference on Conceptual Structures, Bondi Beach, Sydney, Australia (P.W. Eklund, G. Ellis and G. Mann, eds.), ICCS '96, (1996) 81-93 2. Berg, H. van den: Knowledge Graphs and Logic: One of Two Kinds. Dissertation, University of Twente, The Netherlands, ISBN 90-9006360-9 (1993) 3. Quirk, R., Creenbaum, S., Leech, G., Svartnik, J.: A Grammar of Contemporary English. Longman (1972) 4. Willems, M.: Chemistry of Language: A graph-theoretical study of linguistic semantics. Dissertation, University of Twente, The Netherlands, ISBN 90-9005672-6 (1993)
Tuning Up Conceptual Graph Representation for Multilingual Natural Language Processing in Medicine Anne-Marie Rassinoux, Robert H. Baud, Christian Lovis, Judith C. Wagner, Jean-Raoul Scherrer Medical Informatics Division, University Hospital of Geneva, Switzerland anne-marie.rassinoux @dim.hcuge.ch
Abstract. Multilingual natural language processing (NLP), whether it concerns analysis or generation of sentences, requires a sound language-independent representation for grasping the deep meaning of narratives. The formalism of conceptual graphs (CGs), especially designed to cope with natural language semantics, constitutes a good repository for dealing with the compositionality and intricacies of medical language. This paper describes our experiment, as part of the European GALEN project, for exploiting a conceptual graph representation of medical language, upon which multilingual medical language processing is performed.
1
Introduction
Health care, like any institution managing a huge amount of textual information, has to face an important counterbalancing challenge. On the one hand, the ability to rapidly and easily access and retrieve relevant information on a patient is a crucial need. Such a functionality is better achieved when information is encoded and structured in databases or electronic patient records, thus allowing the formulation of precise queries. On the other hand, effective communication is better performed through the expressiveness of natural language, whether it is among health care providers themselves, or to directly address the patient. It appears, therefore, that both textual documents and structured information must coexist in the same environment. The approaches developed to switch from one to another are at the heart of research and development performed in the domain of medical language understanding 1. This has led to substantial and ongoing results related to both the analysis 2 and generation 3 of medical texts. This article presents substantial issues resulting from our experience in handling a unique knowledge representation - being used as input for the generation task and as output for the analysis task - for grasping the deep meaning of medical sentences. The peculiarities of medical language and their implications for knowledge representation are first described. Then the adjustments achieved to mediate between the implicitness and expressiveness of natural language (NL) on the one hand, and the accuracy and granularity of knowledge representation (KR) on the other hand, are exposed.
391
2 Background Domain knowledge model that represents medical information in a languageindependent and structured way constitutes a major cornerstone upon which multilingual applications can be built. This requires the description of a consistent view of all the relevant entities of the domain and their associated attributes. Such a description must reflect an appropriate level of generality and granularity, useful for integrating knowledge from diverse sources as well as maintaining standard representation that can be exchanged and reused in the future. These requirements are at the basis of the European GALEN project 1. This project led to the development of a common reference model (the CORE model) which is expressed in a languageindependent manner through a descriptive logic language (the GRAIL Kernel) 4. It affords a high level ontology that organizes concepts and attributes (also called semantic links or relationships) upon which multiple inheritance can be applied. Moreover, it allows composite concepts to be built from existing ones, providing that the constraints required for such compositions are available. This compositional modeling facilitates shifting between different levels of detail. This presents advantages for NLP, as such compositions allow conceptual structures to be formulated in natural language using more or less precise medical vocabulary. The importance of multilingual natural language processing was particularly emphasized during the first year's work in GALEN-IN-USE2 5. On the one hand, natural language generation is of paramount interest for information presentation as it allows knotted and complex GRAIL expressions to be naturally displayed to the user with sentences formulated in his native (or at least known) natural language. On the other hand, natural language analysis is of significant help for data capture in so far as it produces a structured representation which can then be (semi) automatically mapped to the GALEN CORE model. Therefore, linguistic tools including generation 6, 7 as well as analysis 8 of medical texts, have been developed as part of the GALEN project. Pursuing a previous in-house experiment 9 with the formalism of conceptual graph (CG) 10, the latter has been chosen as the modeling formalism for representing medical language that is handled by' NLP tools. Due to the fact that the CG formalism shares many features with the GRAIL language in which the CORE model is expressed 4, the translation from GRAIL to CG representation was a straightforward process using Definite Clause Grammar (DCG). The NLP tools have been mainly tested on a new French coding system for surgical procedures named NCAM 3 11. From this classification, more than 500 1 GALEN stands for General Architecture for Language, Encyclopaedias and Nomenclatures in medicine, and is currently funded as part of Framework IV of the EC Healthcare Telematics research program. 2 GALEN-IN-USE is the current phase of the GALEN project, whose aim is to apply tools and methods of GALEN to assist in the collaborative construction and maintenance of surgical procedure classifications. 3 NCAM stands for Nomenclature Commune des Actes M~dicaux and is currently developed by the University of Saint Etienne in France.
392
surgical procedures belonging to the urology domain were modeled, while respecting the multi-level sanctioning of the GALEN representation, and then regenerated into natural language phrases. Fig. 1 shows the CG representing the French surgical procedure <
r~st-~U~g thefocus: i cl SurgicalDeed:yI
i
~i~
(rel_isMainlyCharacterisedBy)->cl_performancei (rel_isEnactmentOf)->el GeneralisedProeess:x\\. | .. . . . . - . . . . . . . -,
1'
.
iii .
.
.
~w Language annotations
/,:
................
-~
........
-- ........
CG" l From concepts to /~, en: scopy; r: scople . r~" 9 ! ~ .1 -.,r en:surgical; fr:chirurgical t t~urglcalL~eeo/A (isMainlyCharacterisedBy)->performance/ / I (isEnactmentOf)->Inspecting~ / li en: pyelo; fr: py61o (playsClinicalRole)->SurgicalRole\/ fien: calico; fr: calico (acts SpecificallyOn)->ArbitraryBodyConstru~J/ * (hasArbitraryComponent)->RenalPelvis / en: endoscopic (hasArbitraryComponent)->CalixOfI~dney~ fr: endoscopique (hasPhysicalMeans)->Endoscope (hasSpecificSubprocess)~SurgicalApproachin.qs en: by; fr: par (hasPhysicalMeans)->Route(passesThrough)->SkinAsOrgan\\\\\.~ en: percutaneous route __ ~p.e.r.c..uta.n.6.e ........... !
i Relational contraction:
Type contraction:
cl_GeneralisedProcess: x11 (rel-hasSpecificSubpr~176 I(rel_hasPhysicalMeans)_>cl_Route: Y\~-__
cl_Route: x(rel_passesThrough)->cl_SkinAsOrgan~.
...........
:
.
.
.
ii!!!!ii!iiiii
.
.
.
.
.
.
.
.
.
.
. . . . . . . . . . . . . . . . . . . . . . .
:,',!,!~
Ouput o f the generation tool for English and French: "~ en: 'endoscopic surgical pyelocalicoscopy by percutaneous route' | fr: 'py61ocalicoscopie chirurgicale endoscopique par voie percutan6e~ Fig. 1. Operations applied during the generation task on the CG representing the French rubric ~Pydlo-calicoscopie par voie percutande~ 4
4 Internally, a concept is prefixed by c/_, a Simple relationship by rel_ and a composite relationship by reld_. For the sake of simplicity, these prefixes are omitted in the above CG.
393
3
Modeling Medical Language
Modeling medical language requires taking into account the variations in the description of medical terms, while supporting a uniform representation expressing the medical concepts characterized by attributes and values. However, the way information is modeled does not always correspond to the way information is expressed in natural language. Different compromises must therefore be set up.
3.1
Annotation of Medical Information
In order to make available and operational the semantic content of the CORE model for NLP, the major task has consisted in annotating the model in the corresponding languages treated (mainly French, English, German, and Italian). These linguistic annotations are performed at two levels. First, conceptual entities are annotated with 'content words' that correspond mostly to the syntactic categories of nouns and adjectives. Either single words, parts of words like prefixes and suffixes, or multiword expressions are permitted as annotation (see the language annotation part in Fig. 1). Second, annotations of relationships are more frequently achieved through 'function words'. The latter are conveyed either through grammatical structures, such as the adjectival structure or the noun complement (as in the examples pyelic calculus or calculus of the renal pelvis for the relationship rel_hasSpecificLocation), or directly through grammatical words such as prepositions (as in the example urethroplasty for perineal hypospadias where the preposition 'for' denotes the relationship rel_hasSpecificGoal). The annotation process, which only occurs on named concepts, enables the creation of multilingual dictionaries that settle a direct bridge between concepts and language words. Every meaningful primitive concept belonging to the GALEN CORE model needs to be annotated. Besides, composite concepts, for which a definition is maintained at the conceptual level, may be annotated based on the availability and conciseness of words in the language treated. The verbosity of medical language and the complexity of the modeling style can then be respectively tuned by annotating composite concepts and composite relationships. For example, the concept cl_PercutaneousRoute is directly annotated with concise expressions, and the relationship reld_byRouteOf, especially created for NLP purposes, allows the nested concept cl_SurgicalApproaching to be masked during linguistic treatments (see Fig. 1). However, the combinatorial aspect of the compositional approach as well as the continually growing creation of new medical terms, make the annotation task unbounded and time-consuming. This has led to the implementation of procedural treatments at the linguistic level that map syntactic structures upon semantic representation but also include the management of standard usage of prefixes and suffixes. The latter is especially important for surgical procedures that are commonly expressed through compound word forms 12. This means that the word pyelocalicoscopy is never described, as an entry in the English dictionary (as the description of the concept denoting a pyelocalicoscopy is not explicitly named in the model), but is automatically generated according to its corresponding semantic description. Automated morphosemantic treatment also implies that the linguistic
394
module be aware of abstract constructions used at the conceptual level to handle the enumeration of constituents. In Fig. 1, both the abstract concept cl_ArbitraryBodyConstruct and the relationship rel_hasArbitraryComponent are used to clarify the different body parts on which the inspection occurs.
3.2
The Relevance of the Focus for NLP
A recognized property of CG formalism, over other formalisms such as the frame system, is its ability to easily turn over the representation, i.e. to draw the same graph from a different head concept. For example, the following conceptual graph cl_Pain->(rel_hasLocation)->cl_Abdomen can be rewritten into cl_Abdomen ->(rel_isLocationOf)->cl_Pain. Even if these two graphs appear equivalent at first sight, from the conceptual viewpoint, some subtleties can be pointed out when shifting to NL. The former graph is naturally translated into abdominal pain or pain in the abdomen, whereas the second one tends to be translated into painful abdomen. In medical practice, the interpretation underlying these two clinical terms significantly differs. The key issue here is that, for NLP purposes, the head concept of a graph (such as cl_Pain in the first graph and cl_Abdomen in the second one) is precisely considered as the focus of the message to be communicated. The rest of the graph, therefore, is only there to characterize this main concept in more detail. Such an observation questions the focus-neutral property of CG formalism in' so far as linguistic tools add special significance to the head concept or focus of a graph. Indeed, the latter is interpreted as the central wording upon which the rest of the sentence is built.
3.3
Contexts or Nested Conceptual Graphs
Contexts constitute a major topic of interest for both the linguist and conceptual graph communities. Recent attempts to formally define the notion of context have come to light 13, 14, and the use of context for increasing the expressiveness of NL representation is clearly asserted 15. For GALEN modeling, contexts appear as a major way of avoiding ambiguity when representing medical language. In particular, associating a specific role with a concept (as for example, cl_SurgicalRole for identifying a surgical procedure, or cl_InfectiveRole or cl_AllergicRole for specifying a pathological role) allows for reasoning and then restricting the inference process to what is sensible to say about this concept. Such packaging of information is graphically represented through brackets delimiting the nested graph (see the CG displayed in Fig. 1 where two contexts are surrounded by bold brackets). Handling these contexts at the linguistic level results mainly in enclosing the scope of the nested graph in a single proposition, which can be expressed by a simple noun phrase or through a more complex sentence.
395
4
F o r m a l Operations to Mediate between K R and N L
The previous section emphasized the gaps that exist between KR and medical language phrases. Indeed, as KR aims to describe, in an unambiguous way, the meaning carried out by NL, such a structure is naturally more complete and accurate than that which is simply expressed in NL. Mediating between these two means of communication implies setting up specific formal operations for readjusting KR and NL expressions.
4.1
Basic Operations on CGs
Balancing the degree of granularity and thus the complexity of a conceptual representation can be achieved in two different ways. On the one hand, a conceptual graph can be contracted in order to display information in a more concise manner. The contraction operation, which consists in replacing a connex portion of a graph by an explicit entity, is basically grounded on the projection operation (see 10, pp. 99). On the other hand, a conceptual graph can be expanded in order to add and thus make explicit precise information on the semantic content of the graph. The expansion operation, which consists in replacing a composite entity by its full definition, is based on the join operation (see 10, pp. 92). As the general guideline for the generation task in the GALEN project is to produce phrases 'as detailed as necessary but as concise as possible', the projection operation appears as the central means to mediate with the complexity of KR. In order to adjust this operation for particular usage, it has been necessary to provide, in addition to the projected graph, the hanging graph, the list of cut points and finally the specializations performed during the projection. The hanging graph only embeds the remaining portions of the original graph that were connected to formal parameters (i.e. composed of one or two parts depending on the number of formal parameters, x and y, present in the definition). All other hanging subgraphs are clearly considered as cut points. Each specialization performed in the original graph, whether it concerns a relationship or a concept, is recorded in a list. Each of these components are then checked, as explained in the following section, for their particular behavior in the three following situations: the setting-up of the focus, the contraction of conceptual definitions, and the management of contexts.
4.2
Refining Basic Operations for NLP
In the simplest case, the focus of a graph is defined as the head concept of the graph. However, in KR, this solution is frequently left for the benefit of a representation that allows the focus as well as other concepts mentioned at the same level to be represented uniformly. This is the case for the example shown in Fig. 1, where the general concept cl_SurgicalDeed, representative of the type of concept to be modeled, is taken as the head concept of the graph. Then specific relationships, such as rel_isMainlyCharacterisedBy and rel_isCharacterisedBy, are respectively used to clarify the 'primary' procedure and a number of, possibly optional, additional
396
procedures. Establishing the focus of the graph in this case consists in restoring the primary procedure as the head concept of the graph, by projecting the corresponding abstraction shown in Fig. 1 on the initial graph. Then, the projected graph is straightly replaced by the specialization of the concept identified by the formal parameter x. In the example, the latter corresponds to the concept cl_Inspecting that is a descendant of cl_GeneralisedProcess in the conceptual hierarchy. Moreover, this operation prohibits the presence of cut points as well as any specialization done on concepts other than the formal parameter x. The two hanging graphs (if not empty) are then appended to the new head of the graph. In order to retain the level of detail of the conceptual representation, the type contraction does not allow specialization. Moreover, it normally prohibits the presence of cut points, which are signs of a resulting disconnected graph. However, for the generation task, such a rule can be bypassed. For example, let us consider the following graph: cl_SurgicalExcising-
( rel_actsSpecificallyOn )- > c l_Adenoma ( rel_hasLocativeAttribute )- >cl_ProstateGlandk\ Assuming that the composite concept cl_Adenomectomy exists in the model, the contraction
of its
corresponding
definition would produce the cut point But, as the type contraction in the generation process is intended to ensure the conciseness of the produced NL expressions, by translating a portion of graph by precise words, the cut point can be joined to the hanging graph. This contributes to the generation of the valid NL expression prostatic adenomectomy from the above graph. For the relational contraction, the projection operation permits the specialization on concepts and relationships, as these relational definitions, specifically introduced for NLP purposes, are commonly expressed in the most general way possible. However, the cut points are not permitted. Finally, contexts are treated first of all by looking for the definition of a composite concept already described in the model that can be successfully projected on the nested graph. This is the case in Fig. 1 for the contextual information describing the percutaneous route that is replaced by the concise concept cl_PercutaneousRoute. In all the other cases, the boundaries of the contexts are simply removed and the nested graph is merged to the main graph as performed for the surgical role in Fig. 1.
(rel_hasLocativeAttribute)->cl_ProstateGland.
5
Conclusion
Our experience with managing the conceptual graph formalism for NLP has reinforced our belief that a logical, expressive, and tractable representation of medical concepts is a requisite for dealing with the intricacies of medical language. In spite of the effort undertaken to independently manage conceptual knowledge (which in this case is mainly modeled within the GALEN project) and linguistic knowledge (which is handled by linguistic tools), it clearly appears that fine-tuning of both sources of knowledge is a requisite towards building concrete multilingual applications. Such an adjustment affects both the KR and the multilingual NLP tools, and is realized through declarative as well as procedural processes. On the one hand, it has been
397 necessary to add declarative knowledge through the specification of both multilingual annotations and language-independent definitions. On the other hand, the procedural adjustment has been mainly achieved through the implementation of morphosemantic treatment at the linguistic level, and the refinement of conceptual operations for holding the modeling style at the KR level. All these compromises have proved to be adequate for smoothly and methodically counterbalancing the granularity and complexity of KR with the implicitness and expressiveness of NL.
References 1. 2. 3. 4. 5. 6. 7.
8. 9.
10. 11.
12. 13. 14. 15.
McCray, A.T., Scherrer, J.-R., Safran, C., Chute, C.G. (eds.): Special Issue on Concepts, Knowledge, and Language in Health-Care Information Systems (IMIA). Meth Inform Med 34 (1995). Spyns, P.: Natural Language Processing in Medicine: An Overview. Meth Inform Med 35(4/5) (1996) 285-301. Cawsey, A.J., Webber, B.L., Jones, R.B.: Natural Language Generation in Health Care. JAMIA 4 (1997) 473-482. Rector, A.L., Nowlan, W.A., Glowinski, A.: Goals for Concept Representation in the GALEN project. In: Safran, C. (ed.): Proceedings of SCAMC'93. New York: McGrawHill, Inc. (1993) 414-418. Rogers, J.E., Rector, A.L.: Terminological Systems: Bridging the Generation Gap. In: Masys, D.R. (ed.): Proceedings of the 1997 AMIA Annual Fall Symposium. Philadelphia: Hanley & Belfus, Inc. (1997) 610-614. Wagner, J.C., Baud, R.H., Scherrer, J.-R.: Using the Conceptual Graphs Operations for Natural Language Generation in Medicine. In: Ellis, G. et al. (eds.): Proceedings of ICCS 95. Berlin: Springer-Verlag (1995) 115-128. Wagner, J.C., Solomon, W.D., Michel, P.-A. et al.: Multilingual Natural Language Generation as Part of a Medical Terminology Server. In: Greenes, R.A., Peterson, H.E., Protti, D.J. (eds.): Proceedings of MEDINFO95. North-Holland: HC&CC, Inc. (1995) 100-104. Rassinoux, A.-M., Wagner, J.C., Lovis, C., et al.: Analysis of Medical Texts Based on a Sound Medical Model. In: Gardner, R.M. (ed).: Proceedings of SCAMC'95. Philadelphia: Hanley & Belfus, Inc. (1995) 27-31. Rassinoux, A.-M., Baud, R.H., Scherrer, J.-R.: A Multilingual Analyser of Medical Texts. In: Tepfenhart, W.M., Dick, J.P., Sowa, J.F. (eds.): Proceedings of ICCS94. Berlin: Springer-Verlag (1994) 84-96. Sowa, J.F.: Conceptual Structures: Information Processing in Mind and Machine. Reading, MA: Addison-Wesley Publishing Compagny (1984). Rodrigues, J.-M., Trombert-Paviot, B., Baud, R. et al.: Galen-In-Use: An EU Project applied to the development of a new national coding system for surgical procedures: NCAM. In: Pappas, C., Maglaveras, N., Scherrer, J.-R. (eds.): Proceedings of MIE97. Amsterdam: IOS Press (1997) 897-901. Norton, L.M., Pacak, M.G.: Morphosemantic Analysis of Compound Word Forms Denoting Surgical Procedures. Meth Inform Med 22(1) (1983) 29-36. Sowa, J.F.: Peircean Foundations for a Theory of Context. In: Lukose, D. et al. (eds.): Proceedings of ICCS97. Berlin: Springer (1997) 41-64. Mineau, G.W., Gerb~, O.: Contexts: A Formal Definition of Worlds of Assertions. In: Lukose, D. et al. (eds.): Proceedings of ICCS'97. Berlin: Springer (1997) 80-94. Dick, J.P.: Using Contexts to Represent Text. In: Tepfenhart, W.M., Dick, J.P., Sowa, J.F. (eds.): Proceedings of ICCS'94. Berlin: Springer-Verlag (1994) 196-213.
Conceptual Graphs for Representing Business Processes in Corporate Memories Olivier Gerb@ 1 , Rudolf K. Keller 2, and Guy W. Mineau 3 1 DMR Consulting Group Inc. 1200 McGill College, Montr@al, QuEbec, Canada H3B 4G7 Olivier. Gerbe@dmr.
ca
UniversitE de MontrEal C.P. 6128 Succursale Centre-Ville, MontrEal, QuEbec, Canada H3C 3J7 keller@IRO. UMontreal.
ca
3 Universit@ Laval QuEbec, QuEbec, Canada G1K 7P4 mineau@ift,
ulaval, ca
Abstract. This paper presents the second part of a study conducted at DMR Consulting Group during the development of a corporate memory. It presents a comparison of four major formalisms for the representation of business processes: UML (Unified Modeling Language), PIF (Process Interchange Format), WfMC (Workflow Management Coalition) framework and conceptual graphs. This comparison shows that conceptual graphs are the best suited formalism for representing business processes in the given context. Our ongoing implementation of the DMR corporate memory - used by several hundred DMR consultants around the world is based on conceptual graphs, and preliminary experience indicates that this formalism indeed offers the flexibility required for representing the intricacies of business processes.
1
Introduction
Charnel Havens, EDS (Electronic D a t a Systems) Chief Knowledge Officer, presents in 5 the issues of knowledge management.
With a huge portion of a company's worth residing in the knowledge of its employees, the time has come to get the most out o/ that valuable corporate resource - by applying management techniques. The challenge companies will have to meet is the memorization of knowledge as well as its storage and its dissemination to employees throughout the organization. Knowledge may be capitalized on and managed in corporate memories in order to ensure standardization, consistency and coherence. Knowledge management requires the acquisition, storage, evolution and dissemination of knowledge acquired by the organization 14, and computer systems are certainly the only way to realize corporate memories 15 which meet these objectives.
402
DMR Consulting Group Inc. has initiated the IT Macroscope project 7, a research project that aims to develop methodologies allowing organizations: i) to use IT (Information Technology) for increasing competitiveness and innovation in both the service and product sectors; ii) to organize and manage IT investments; iii) to implement information system solutions both practically and effectively; and iv) to ensure that IT investments are profitable. In parallel with methodology development, tools for designing and maintaining these methodologies, designing training courses, and for managing and promoting IT Macroscope products were designed. These tools implement the concept of corporate memory. This corporate memory, called the Method Repository, plays a fundamental role. It captures, stores 3, retrieves and disseminates 4 throughout the organization all the consulting and software engineering processes and the corresponding knowledge produced by the experts in the IT domain. During the early stage of the development of the Method Repository, the choice of a knowledge representation formalism was identified as a key issue. That lead us to define specific requirements for corporate memories, to identify suitable knowledge representation formalisms and to compare them in order to choose the most appropriate formalism. We identified two main aspects: knowledge structure and dynamics - business processes, together with activities, events, and participants. The first part of the study 2 lead us to adopt the conceptual graph formalism for structural knowledge. Uniformity of the formalism used in the Method Repository was one issue but not the all-decisive one in adopting conceptuM graphs for the dynamic aspect, too. Rather, our decision is based on the comparison framework presented in this paper. In our comparison, we studied four major business modeling formalisms or exchange formats, UML (Unified Modeling Language), PIF (Process Interchange Format), WfMC (Workflow Management Coalition) framework, and conceptual graphs, against our specific requirements. Choosing these four formalisms for our study has been motivated by the requirement for building our solution on existing or de facto standards. Our study demonstrates that conceptual graphs are particularly well suited for representing business processes in corporate memories since they support: (i) shared activities, and (ii) management of instances. The paper is organized as follows. Section 2 introduces the basic notions of business processes as used in this paper. Section 3 defines specific requirements for the representation of business processes in corporate memories. Section 4 compares the four formalisms. Finally, Section 5 reports on the on-going implementation of the Method Repository and discusses future work.
2
Basic Notions
In this section, we present basic notions relevant to the representation of business processes. Main notions of representation of the dynamics in an enterprise are processes; activities, participants (input, output, and agent), events (preconditions and postconditions), and notions of sequence and parallelism of activity
403 executions. These notions build upon some commonly used definitions in enterprise modeling, as summarized in the following paragraph. A process is seen as a set of activities. An activity is a transformation of input entities into output entities by agents. An event marks the end of an activity; the event corresponds to the fulfilment of both the activity's postcondition and the precondition of its successor activity. An agent is a h u m a n or material resource t h a t enables an activity. An input or output is a resource t h a t is consumed of produced by an activity. The notions of sequence and parallelism define the possible order of activity executions. Sequence specifies an order of executions and parallelism specifies independence between executions. Figure 1 presents the notions of activity, agent, input, and output. Activities are represented by a circle and participants of activities are represented by rectangles and linked to their respective activities by arcs ; directions of arc define their participation: input, output or agent. There is no notational distinction between input and agent. Note t h a t this simple process representation exclusively serves for introducing terminology and for illustrating our requirements.
Fig. 1. Activity with input, output and agent.
Figure 2 illustrates the notions of sequence and parallelism by a process composed of five activities. T h e activity Write Productioa Order is the first activity of the process, the activities Build Frame and Cut Panes are executed in parallel, Assemble Window follows the activities Build Frame and Cut Panes, and finally Deliver Window terminates the process. Note t h a t we only have to consider the representation of parallel activities or sequential activities; all other cases can be represented by these two cases by splitting activities into sub-activities.
3
Requirements
This section introduces the two main requirements underlying our study: representation of processes sharing activities and management of instances t h a t are 9involved in a process. It is obvious t h a t there exists a lot of other requirements to represent a business process in a corporate memory. Since these other requirements are mostly met by all the formalisms studied, we decided to focus on the two main requirements mentioned above.
404
Fig. 2. A process as a set of activities.
3.1
Sharing Activities
Let us consider the case of two processes t h a t share a same activity. Figure 3 illustrates this settings.
Fig. 3. Sharing Activities.
The example depicted in Fig. 3 deals with the fabrication of a product which is made out of two components: a software component and a hardware component, as in a cellular phone, a microwave oven or a computer. The first process describes the development of the software component. It is composed of Design Software~ Validate Specifications, and Write Software Code. The second process describes the development of the hardware component. It is composed of activities Design Hardware, Validate Specifications~ and Build Hardware. The activity Validate S p e c i f i c a t i o n s is an activity of synchronization and is shared by the two processes. The problem in this example is the representation and identification of the two processes. Each process is composed of three activities, with one of t h e m being in common. Therefore the formalism must offer reuse of parts of process definitions or support some kind of shared variable mechanism.
To support the representation of business processes in corporate memory, a formalism must offer features to represent processes sharing the same activities.
405
3.2
Instance Management
To illustrate the problem of instance management, let us assume the example of a window manufacturer who has a special department for building non standard size windows. Figure 4 presents the window fabrication process.
Fig. 4. The Window Problem.
A fabrication order is established from a client order. A fabrication order defines the size and material of the frame and the size and thickness of the glasses to insert into the frame. The fabrication order is sent to the frame builder and glass cutter teams which execute the order. Then the frame and glasses are transmitted to the window assembly team which insert the glasses into the frame. The problem of this team is to insert the right glasses (size and thickness) into the right frames (size and material). Some frames take more time to build than others, so the frames may be finished in a different order than the glasses are. This problem can be solved by the assembly team by assembling the frame and glasses in