Roberto A. Flores-Méndez
Knowledge Science Institute University of Calgary, Canada robertof@cpsc.ucalgary.ca |
Pim van Leeuwen
Faculty of Mathematics & Computer Science Vrije Universiteit, Amsterdam, The Netherlands pvleeuw@cs.vu.nl |
Dickson Lukose
Department of Mathematics & Computer Science University of New England, Australia lukose@peirce.une.edu.au |
|
|
Algorithmic | |
KADS (Wielinga, Schreiber and Breuker,
1992)
Component of Expertise (Steels, 1990) Generic Tasks (Chandrasekaran and Johnson, 1993) |
MODEL-K (Karbach and Vob, 1993)
TroTelC (Vanwelkenhuysen et al., 1990) |
|
|
DESIRE (Brazier et al., 1996) | CG-DESIRE (Moller and Willems,
1995)
[CG]->(ON)->[KADS] (Moller, 1995) MODEL-ECS (Lukose,1995) |
KADS is one of the knowledge modeling methodology developed in Europe (Wielinga et. al., 1993). Even though many modeling languages were developed (and to a large extent used successfully), these languages are quite difficult for domain experts to use. This is mainly due to the non-graphical nature of many of the earlier tools developed for modeling KADS.
The significance of the contribution of this paper is in our attempts
to demonstrate that one should be able to execute the conceptual model,
without necessarily proceeding to the "transformation" and "implementation"
of the knowledge-based system. This cannot be achieved only by using a
highly sophisticated declarative knowledge representation formalism (like
Conceptual Graphs (Sowa, 1984)), but we also require
an equivalently sophisticated representation scheme to model "processes"
that can be executed. Lukose (1995, 1996,
1997) developed a graph based executable conceptual
modeling language that is based on Conceptual Graphs and Executable
Conceptual Structures (Lukose, 1993). Figure
1.2 shows a view of categorizing modeling languages (with a typical
modeling language that fits into each of the quadrants). MODEL-ECS falls
into the bottom-right quadrant (the most sophisticated type of modeling
language).
|
|
|
|
|
|
|
|
|
The outline of this paper is as follows: Section 2 will briefly describe the KADS methodology, while Section 3 will outline MODEL-ECS. In Section 4, we will show the application of KADS to the Audio System Diagnosis domain, and in Section 5, we will show how this is done using MODEL-ECS. Finally, Section 6 concludes this paper by outlining the limitations of this approach and future research directions to overcome some of these limitations.
KADS is an implementation independent methodology for developing Knowledge-Based Systems (KBS). KADS views a KBS not as a container filled with knowledge extracted from an expert, but an operational model that exhibits some desired behaviour observed in terms of real-world phenomena. KADS attempts to reduce the complexity of the knowledge-modeling process by the use of multiple models (i.e., organizational model, application model, task model, model of expertise, model of cooperation, conceptual model, and design model). These models emphasize certain aspects of the system to be built, and abstracts from others. Models of expertise distinguish between four different knowledge categories: Strategic Knowledge, Task Knowledge, Inference Knowledge, and Domain Theory. Figure 2.1 depicts this knowledge categorization. Strategies are adopted to control the tasks that apply the inference that uses the domain knowledge. Lukose (1995) demonstrated the successful use of MODEL-ECS to carry out the knowledge level modeling of KADS. In the next section, the authors will briefly outline the syntax and semantics of the modeling constructs of MODEL-ECS that will enable us to build sophisticated problem solving methods.
In-depth description of MODEL-ECS is beyond the scope of this paper. A detailed description on the constructs available in MODEL-ECS can be found in Lukose (1997).
Figure 5.2 shows a problem map for the sub-task
generate_hypothesis. This problem map takes a system model as input
and applies the DECOMPOSE knowledge source to obtain a new hypothesis that
is added to the differential using the INCREMENT knowledge source.
Since these knowledge sources will be executed repeatedly until no more
hypotheses are produced, a loop construct is required. First, the knowledge
sources DECOMPOSE and INCREMENT are enclosed in a problem map which then
becomes the body of the loop.
The test_hypothesis problem map, which is illustrated in Figure 5.3, contains a while loop using a conditional construct and a body problem map. The conditional construct consists of a problem map containing four knowledge sources: two TRUE_TESTs and two FALSE_TESTs. These knowledge sources check whether the differential is empty OR whether a difference between a norm and an observation has been found. If so, the while loop can be exited; if not - meaning that there are still more hypotheses to be tested AND no difference between norms and observations has been found - the loop is entered again. The body problem map of the loop contains four knowledge sources: DECREMENT, SELECT, SPECIFY and COMPARE. The first knowledge source to be executed is DECREMENT, which extracts one hypothesis from the differential. This hypothesis is then used as input for the SELECT and SPECIFY knowledge sources, which are executed concurrently. SELECT produces a finding based on the selected hypothesis and the observation of the behaviour observed in the real world. SPECIFY generates a norm defining the expected behaviour for the hypothesis. After these knowledge sources have been executed, the knowledge source COMPARE will be allowed to execute. The goal of this knowledge source is to compare the norm generated by SPECIFY with the finding that is the output of SELECT. If a difference is found, it can be concluded that the hypothesis tested is - or comprises - the faulty system part.
[ACT: *x]- ->(ARG) ->[COMPLAINT: *c] ->(RSLT)->[SYSTEM_MODEL: *a] Method for Select PRE -CONDITIONS: [COMPLAINT: *c] POST-CONDITIONS: [SYSTEM_MODEL: *a] DELETE: [COMPLAINT: *c] |
|
|
|
[PRODUCE]- ->(agnt)->[COMPONENT] ->(rslt)->[ENTITY]->(stat)->[STATE] [NOT: [ENTITY]] [COMPONENT]->(stat)->[STATE] |
|
[COMPONENT] |
|
[ANT:[[COMPONENT: *c]->(stat)->[STATE: *x]]->(and)-> [[COMPONENT: *c]->(stat)->[STATE: *x]]->(and)-> [[COMPONENT: *c]->(stat)->[STATE: *x]]] ->(caus)-> [CON:[PRODUCE]- ->(agnt)->[COMPONENT] ->(rslt)->[ENTITY]] [COMPONENT]->(stat)->[STATE] |
Table 5.1 shows examples of graphs in the domain theory that can be related to the meta-classes used in the definition of the knowledge sources. Examples of specific graphs conforming to meta-class COMPLAINT may include:
[TAPE-PLAYER] -> (STAT) -> [JAMMED] [PRODUCE]- -> (AGNT) -> [AMPLIFIER] -> (RSLT) -> [OUTPUT-SIGNAL] -> (STAT) -> [DISTORTED]Two examples for the meta-classes OBSERVABLE, NORM, FINDING or DIFFERENCE are:
[ANT: [PROP: [AMPLIFIER] -> (STAT) -> [ON]] -> (AND) -> [PROP: [AMPLIFIER] -> (STAT) -> [CONNECTED]] -> (AND) -> [PROP: [AMPLIFIER-VOLUME-KNOB] -> (STAT) -> [ON]] -> (CAUS) -> [CON: [PROP: [AMPLIFIER] <- (AGNT) <- [PRODUCE] -> (RSLT) -> [OUTPUT-SIGNAL]] [AMPLIFIER-POWER-SWITCH] -> (STAT) -> [ON]Meta-classes are related to conceptual graphs in the domain. Some knowledge about the domain is needed to relate the meta-classes to the domain, and domain theories have to be defined. For example, SOUND is an ENTITY produced by another ENTITY. This can be defined as follows:
type SOUND (x) is: [ENTITY: *x]- <- (RSLT) <- [PRODUCE] -> (AGNT) -> [ENTITY:*y]
A type hierarchy tree (as illustrated in Figure 5.5) shows the IS-A relationships that may exist between the different types discerned in the domain. In addition, the "objects" in the domain are required to conform to the concept types. This information is maintained in the Conformity Relations Table. For all components (and the audio system is a component as well), knowledge of the parts that constitute a component should exist. For an amplifier, for example, this knowledge can be represented as follows:
[AMPLIFIER]- ->(PART)->[AMPLIFIER-VOLUME-KNOB] ->(PART)->[AMPLIFIER-BALANCE-KNOB] ->(PART)->[AMPLIFIER-POWER-SWITCH]This domain knowledge is necessary for the DECOMPOSE knowledge source to decompose hypotheses - the meta-class name for a component - into sub-components. Next to this, domain knowledge is also needed about the behaviour of different components. This knowledge is necessary to find the norm for a certain component: the norm is a meta-class name for the normal behaviour of a component. For example, the following knowledge about the behaviour of an amplifier may be necessary:
[AMPLIFIER]- <-(AGNT)<-[AMPLIFY]- ->(RSLT)->[OUTPUT_SIGNAL] ->(OBJ) ->[INPUT_SIGNAL]Having derived these types of domain knowledge, they can be combined into complete type definitions. For example, the type definition for an amplifier could be as follows:
[AMPLIFIER]- -> (PART) -> [AMPLIFIER-VOLUME-KNOB] -> (PART) -> [AMPLIFIER-BALANCE-KNOB] -> (PART) -> [AMPLIFIER-POWER-SWITCH] <- (AGNT) <- [AMPLIFY]- -> (RSLT) -> [OUTPUT_SIGNAL] -> (OBJ) -> [INPUT_SIGNAL]
actor graph specify_new_goal_for_generate_hypotheses (x) is: [ACT: *x]- -> (ARG) -> [FAIL] -> (OBJ) -> [GOAL: generate_hypo's] -> (RSLT) -> [GOAL: get_hypo's_from_user]For this to work, a type definition of fail should exist that defines FAIL as a subtype of ACT, and another type definition has to be brought into existence in order to define goal in terms of an entity. The pre- and post-conditions and the delete list of this actor graph could become:
PRE -CONDITIONS: [GOAL: generate_hypo's] POST-CONDITIONS: [GOAL: get_hypo's_from_user] DELETE : [GOAL: generate_hypo's]Note that this newly created actor graph can be seen as a knowledge source that produces strategic knowledge: knowledge on what (new) goal the system should try to achieve. Note also, that generate_hypo's and get_hypo's_from_user are instances that conform to the meta-class-type GOAL.
Even though MODEL-ECS is a sophisticated conceptual modeling tool, the graphical notation is fairly complex, difficult to understand by non-knowledge engineers, and somewhat cumbersome to handle. Since knowledge-modeling languages have to be usefully employed by (non-knowledge engineer) domain experts, simplicity and ease of use are two primary requirements. It therefore seems worthwhile to investigate the possibility of combining the power of a language like MODEL-ECS with the simplicity and ease of use of a simpler, but not-quite-so-expressive, language. Kremer, Lukose and Gaines (1997) attempt to use annotated flow chart diagrams as such a simpler graphical notation to be combined with MODEL-ECS. Another line of research is concerned with enabling several knowledge engineers (from different geographical locations) to interact and synchronously model problem-solving methods. This may require the use of client-server models of computation, such as WWW-based applications. An example of such a WWW-based collaborative system can be found in (Flores-Méndez, 1997).
Chandrasekaran, B. and Johnson, T. (1993). Generic tasks and Tasks Structures: History, Critique and New Directions, in J.M. David, J.P. Krivine, and R. Simmons (Eds.), Second Generation Expert Systems, Springer Verlag, Berlin, Germany.
Flores-Méndez, R. (1997). Java Concept Maps for the Learning Web, in Proceedings of the World Conference on Educational Multimedia and Hypermedia (ED-MEDIA ’97), Calgary, Alberta, Canada, June 14-17, 1997.
Karbach, W., and Vob, A. (1993). MODEL-K for Prototyping and Strategic Reasoning at the Knowledge level, in J.M. David, J.P. Krivine, and R. Simmons (Eds.), Second Generation Expert Systems, Springer Verlag, Berlin, Germany.
Kremer, R., Lukose, D., and Gaines, B. (1997). Knowledge Modeling using Annotated Flow Chart, in Proceedings of the International Conference on Conceptual Structures (ICCS '97), Seattle, Washington, USA, August 4-8, 1997.
Lukose, D. (1993). Executable Conceptual Structures, in G.W. Mineau, B. Moulin and J.F. Sowa (Eds.), Conceptual Graphs for Knowledge Representation, Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin, Germany.
Lukose, D. (1995). Using Executable Conceptual Structures for Modeling Expertise, in Gaines, B. and Musen, M. (Eds.), Proceedings of the 9th Banff Knowledge Acquisition For Knowledge-Based Systems Workshop (KAW’95), Banff Conference Centre, Banff, Alberta, Canada, 1995.
Lukose, D. (1996). MODEL-ECS: Executable Conceptual Modeling Language, in Gaines, B. and Musen, M. (Eds.), Proceedings of the 10th Knowledge Acquisition for Knowledge Based Systems Workshop (KAW'96), Voyager Inn, Banff, Alberta, Canada, November 9-14, 1996.
Lukose, D. (1997). Complex Modeling Constructs in MODEL-ECS, in Proceedings of the International Conference on Conceptual Structures (ICCS'97), Seattle, Washington, USA, August 4-8, 1997.
Moller, J-U. (1995). Operationalisation of KADS Models by using Conceptual Graph Modules, in Gaines, B. and Musen, M. (Eds.), Proceedings of the 9th Banff Knowledge Acquisition For Knowledge-Based Systems Workshop (KAW ’95), Banff Conference Centre, Banff, Alberta, Canada, 1995.
Moller, J-U. and Willems, M. (1995). CG-DESIRE: Formal Specification Using Conceptual Graphs, in Gaines, B. and Musen, M. (Eds.), Proceedings of the 9th Banff Knowledge Acquisition For Knowledge-Based Systems Workshop (KAW ’95), Banff Conference Centre, Banff, Alberta, Canada, 1997.
Punch, W.F. and Chandrasekaran, B. (1993). An Investigation of the Roles of Problem-Solving Methods in Diagnosis, in David, J.M., Krivine, J.P., and Simmons, R., (Eds.), Second Generation Expert Systems, Springer Verlag, Berlin, Germany.
Schreiber, G., Wielinga, B. and Breuker, J. (1993). KADS: A Principled Approach to Knowledge-Based System Development. Academic Press, London, UK.
Sowa, J.F. (1984). Conceptual Structures: Information Processing in Mind and Machine. Addison Wesley, Reading, Mass., USA.
Steels, L. (1990). Components of Expertise. AI Magazine, 11(2).
van Harmelen, F. and Balder, J. (1993). (ML)2: A Formal Language for KADS Models of Expertise, in G. Wielinga, B., Schreiber, A.T. and Breuker, J.A. (Eds.), Modeling Expertise in KADS: A Principled Approach to Knowledge-Based System Development, Academic Press, London, UK.
Vanwelkenhuysen, J. and Rademakers, P. (1990). Mapping a Knowledge Level Analysis onto a Computational Framework, in Proceedings of the 9th European Conference on Artificial Intelligence, Pitman Publishing, London, UK.
Wielinga, B., Schreiber, A.T. and Breuker, J.A. (1992). KADS: A Modeling Approach to Knowledge Engineering, in The KADS Approach to Knowledge Engineering Special Issue, Knowledge Acquisition, 4(1), Academic Press, London, UK.
Wielinga, B., Schreiber, A.T. and Breuker,
J.A. (1993). Modeling Expertise. KADS: A Principled Approach to Knowledge-Based
System Development, Academic Press, London, UK.