Visual presentation of knowledge structures has been an attractive feature of semantic networks since their inception (Quillian, 1968). In knowledge acquisition, in particular, the presentation of formal knowledge to those from whom it has been elicited is important to its validation (Gaines and Shaw, 1992b). There are many techniques for such acquisition but they ultimately result in an operational knowledge base with formal semantics. However, the expression of this knowledge base in the formal language used by the system is usually not very comprehensible to non-programmers (Nosek and Roth, 1990). A visual language that is both comprehensible and formal offers attractive possibilities not only for comprehension but also for editing, and for parts of the knowledge acquisition process itself.
The early development of semantic nets resulted in criticisms that the semantics of particular diagrams was not well-defined (Woods, 1975; Brachman, 1977). Nodes, arcs and their labels could be used very freely and ambiguously and diagrams were subject to differing interpretations. In the 1970s there were proposals for network formalisms with well-defined semantics (Cercone and Schubert, 1975; Brachman, 1979; Fahlman, 1979), and this became feasible as formal semantics were developed for terminological knowledge representation systems (Borgida, Brachman, McGuiness and Resnick, 1989; Baader and Hollunder, 1991; Borgida and Patel-Shneider, 1994). A formal semantics for concept maps for terminological logic systems has been specified (Gaines, 1991), a major example of its application in the solution of a room allocation system has been given (Gaines, 1994b), and the relationship between the maps and the knowledge representation data structures has been analyzed in detail (Gaines, 1994a).
Figure 7 shows a semantic network representing some knowledge about software copyright disputes (Madan, 1994) represented for a terminological logic system. At the top left is a general definition of a primitive concept "legal dispute." Immediately below it the concept "copyright dispute" is defined as a "legal dispute" whose "claim" role includes "copyright violation." Below this the concept "software copyright dispute" is defined as a "copyright dispute" whose "domain" role includes "software." Below this the concept "user interface copyright dispute" is defined as a "software copyright dispute" whose "basis" role includes "user interface similarity." This concept is the premise of the rule "ui copyright cases," and when an individual satisfying this premise is recognized then the rule fires and the conclusion is asserted that the individual has its "cases for plaintiff" role filled by "Cross vs Mirror" and "PrintShop vs PrintMaster," and its "cases against plaintiff" role filled by "Apple vs Microsoft."
Figure 7 Concept map for a semantic network for terminological knowledge representation
On the right in Figure 7, the individual "Case D87OE" is asserted to be an instance of a "legal dispute" whose "claim" role is filled by "copyright violation," "domain" role by "software," and "basis" role by "user interface similarity."
When the "Compile" button is clicked the semantic network is converted to an equivalent textual form as shown in Figure 8.
Figure 8 Textual form of knowledge structure compiled from Figure 7
Figure 9 shows inference taking place when the knowledge structure of Figure 8 is loaded into a KRS knowledge representation server, or that of Figure 7 is "pasted" into the server window and automatically compiled. The trace in the upper part shows the inferences being made. Clicking on the button "Graph-Ind" causes the results of inferences about individuals to be graphed as a concept map as shown in the lower part. It can be seen that "Case D87OE" has been inferred to have its "cases for plaintiff" role filled by "Cross vs Mirror" and "PrintShop vs "PrintMaster," and its "cases against plaintiff" role filled by "Apple vs Microsoft."
Figure 9 Inference from knowledge structure of Figures 7 and 8 output as concept map
As in previous examples, the popup menus in Figures 7 and 9 provide links to a database of associated information, in this example a database of legal background material, case summaries and transcripts. This enables the nodes that have been added through inference to be used to retrieve further information that has been inferred to be relevant to the case described. More generally, this can be seen as a technique whereby deductive inference can been used to create new links between hypermedia structures.
It may seem a rhetorical device to leave the definition of a concept map to this late stage in the article. However, it should be clear from the many example given, and the many more to be found in the literature cited, that the term "concept map" is used to encompass a wide range of diagrammatic knowledge representations. As in Wittgenstein's (1953) analysis of the problem of developing a clear, unambiguous and complete definition of the commonly understood term, "game," neither the term "concept" nor the term "map" have precise definitions. Each term is commonly used colloquially, and both have a variety of different precisifications as technical terms in different disciplines. The compound term "concept map" inherits connotations from these varying usages, and has usages of its own. Hence, it has appropriate to exemplify the term in a range of applications before addressing its definition.
In explicating, or deconstructing, the notion of concept map based on the examples in the literature, one finds a need for three levels of analysis: from an abstract perspective concept maps as nodes linked by arcs may be seen as representations of graphs, using the term as defined in mathematics (Berge, 1958); from a visualization perspective concept maps may be seen as diagrams, using the term to mean a drawing with reasonably well-understood semiotics for some community (Bertin, 1983); from a discourse perspective concept maps may seen as a way of representing and communicating knowledge through visual languages (Chang, Ichikawa and Ligomenides, 1986; Saint-Martin, 1990). Each perspective draws out different common threads from the many exemplars of concept maps in the literature.
From an abstract perspective, the basic concept map data structure is a sorted hypergraph consisting of typed nodes some of which are linked. Each node has a type, a unique identifier and a content (which may itself be structured, for example, as label plus other data). A node may enclose other nodes giving the graph a hypergraph structure (Berge, 1973) in which a single link may connect sets of nodes. Links may be directed or undirected, represented visually by lines between nodes with, or without, arrow heads. Links may themselves be typed in some applications.
From a visualization perspective, to provide a consistent relation between the visual features as signs and their semiotic infrastructure, the visual attributes of nodes and links need to be in one-to-one unique correspondence with their types. The node type may determine, and itself be determined by, the node shape, frame color, fill color, whether the type name is displayed and, if so, in what type face, style, size and color, and whether part of the content is displayed and, if so, in what type face, style, size and color. If the links are types, their types may determine, and be determined by, line thickness, color, cross-hatching, or other forms of decoration. Visual attributes that are not part of this determination may be used for other purposes, such as emphasis, but it is important that such usage does not obscure the primary relation.
From a discourse perspective, the abstract structure represented as a diagram in visual terms consistent with it has meaning as knowledge representation and communication because it is subject to interpretation by some reference community. In this there is an exact parallel between natural language and visual language--the abstract grammatical structures and their expressions in a medium take on meaning only through the practices of a community of discourse. Some communities may find it appropriate to use language in a loose, associative fashion, whereas others may wish to use it with technical precision, and usage may well be mixed with informal and formal sub-languages combined in actual discourse.
These three perspectives provide the framework for the development of tools to support concept mapping activities, and were the basis of the design of KMap as an open architecture concept mapping tool used to produce the maps shown in this article.
gaines@cpsc.ucalgary.ca 22-Nov-95