home *** CD-ROM | disk | FTP | other *** search
/ ftp.umcs.maine.edu / 2015-02-07.ftp.umcs.maine.edu.tar / ftp.umcs.maine.edu / pub / WISR / wisr6 / proceedings / ascii / fensel.ascii < prev    next >
Text File  |  1993-10-19  |  13KB  |  270 lines
  1.  
  2.  
  3.  
  4.  
  5. Reuse  of  Problem-Solving  Methods  in  Knowledge  Engineering
  6.  
  7.  
  8.  
  9.                                                  Dieter Fensel
  10.  
  11.  
  12.  
  13.   Institut fur Angewandte Informatik und Formale Beschreibungsverfahren (AIFB)
  14.  
  15.             University of Karlsruhe, P.O. Box 6980, 76128 Karlsruhe, Germany
  16.  
  17.                                             Tel: 49-721-6084754
  18.  
  19.                                              Fax:  49-721-693717
  20.  
  21.                                  E-mail:  fensel@aifb.uni-karlsruhe.de
  22.  
  23.  
  24.  
  25.                                                     Abstract
  26.  
  27.  
  28.       The paper proposes the combination of two kinds of software reuse in knowledge engineering.
  29.   On the one hand, a lot of work has been done to develop generic problem-solving methods which
  30.   can be applied to different domains and tasks. These reusable methods simplify the process of
  31.   building  a  knowledge-based  system  by  providing  a  predefined  model  of  the  problem-solving
  32.   process which guides the further acquisition of domain knowledge. One the other hand, several
  33.   formal knowledge specification languages have been developed which allow the description of a
  34.   model of expertise at a high but precise conceptual level. In the paper it is argued that formal
  35.   languages can also be used to improve the reuse of predefined problem-solving methods.
  36.  
  37.  
  38.   Keywords: Reuse, requirements specification, formal specifications, source-code libraries, prob-
  39.   lem-solving methods, knowledge engineering
  40.  
  41.  
  42.   Workshop Goals: Learning and networking, discussing reuse of formal specifications and the
  43.   use of formal specifications for reuse.
  44.  
  45.  
  46.   Working Groups: Reuse and formal methods, Domain analysis.
  47.  
  48.  
  49.  
  50.                                                     Fensel- 1
  51.  
  52.  
  53. 1      Background
  54.  
  55.  
  56.  
  57. During the last four years I have worked in the domain of knowledge engineering. The main part of
  58. my work was concerned with the development of the formal and operational knowledge specification
  59. language KARL [1] (i.e., reuse by a very-high-level language cf.  [2]).  A second line of research on
  60. reuse was the formal specification of reusable problem-solving methods in KARL. Currently, the
  61. development  and  description  of  generic  and  reusable  problem-solving  methods  is  an  important
  62. branch of research in knowledge engineering.  The description of the problem-solving behaviourof
  63. an expert system by a generic problem-solving method characterizes the so-called second generation
  64. expert systems [3].  My work ispart of the MIKE-pro ject (Mo del-based and Incremental Knowledge
  65. Engineering, cf.  [4]) at the University of Karlsruhe which aims at developing methods and tools
  66. for the process of building knowledge-based systems.
  67.  
  68.  
  69.  
  70. 2      Position and  Comparison
  71.  
  72.  
  73.  
  74. First, the rationale of reusable problem-solving methods is discussed. Second, the development of
  75. formal and operational knowledge specifi
  76.  
  77.  
  78.  
  79. 2.1     Reuse of Problem-Solving Methods
  80.  
  81.  
  82.  
  83. During the last decade, several problem-solving methods have been discoveredin the domain of
  84. experts  systems.  [5 ]  analysed  several  expert  systems  for  diagnosis  and  remodelled  the  so-called
  85. problem-solving method heuristic classification, which was implicitly used by all of these exp ert
  86. systems without being explicitly represented. In spite of various differences all systems have three
  87. steps  in  common:  a  data-abstraction,  i.e.,  concrete  values  are  mapped  on  intervals; a  heuristic
  88. match  from  abstract  problem  descriptions  to  abstract  solutions;  the  hierarchical  refinement  of
  89. these solutions until a final solution has been found.
  90. Thus, Clancey describes a problem-solving method without referring to implementational details
  91. of the used knowledge representation formalism ofthe different systems or to the domain specific
  92. knowledge they used. The description of a problem-solving method independently from its imple-
  93. mentation and from an application domain are the essential necessities for its reuse.  In[6 ] a whole
  94. set of different problem-solving methods is described at this level. These problem-solving methods
  95. are described by defining: the single steps called knowledge sources or inference actions; the struc-
  96. tural dependencies of these single steps by a so-called inference structure; and the control flow, i.e.
  97. the sequence of these single steps.  Such a problem-solving metho dis often called interpretation
  98. model because it can be used as an guideline for the knowledge acquisition process. Once selected,
  99. the method can guide the elicitation and interpretation of the experts domain knowledge required
  100. for solving the specific task.  A more operational point of view on reuse is taken by theroblem-
  101. solving methods.
  102. To overcome theseshortcomings of application generators, [7 ]prop oses alibrary of reusable mecha-
  103. nisms or generic tasks. These methods have a finer grain size than conventional expert system shells.
  104. A complete problem-solving process must be modelled by several mechanisms.  These approaches
  105. are analogous to the source-code library idea in software engineering. The main characteristics of
  106. these approaches is that currently these mechanisms are only described by code and by informal
  107. descriptions  of  the  code.  Therefore, there  is  little  support  for  the  selection,  specialization,  and
  108. integration  of  these  mechanisms.  The  lack  of  descriptions  that  abstract  from  implementational
  109.  
  110.  
  111.  
  112.                                                          Fensel- 2
  113.  
  114.  
  115. details, but do not lead to imprecise natural-language descriptions, makes it difficult to compare
  116. such mechanisms, and to provide a precise description of their problem-solving capability. Mathe-
  117. maows developers to address such components through their names.  Currently, there exist neither
  118. exhaustive libraries of reusable mec
  119.  
  120.  
  121.  
  122. 2.2     Reuse by Formal Specification Languages
  123.  
  124.  
  125.  
  126. A further  line  of  software  reuse  is  the  development  of  specific  formal  or  op erational  knowledge
  127. specification languages. Very high-level languages (VHLL) are executable like high-level languages
  128. but they aim to increase the level of abstraction. "The primary concern in VHLLs is not efficiency in
  129. program execution but rather efficiency in implementing and mo difying programs" [2 ]. In VHLLs,
  130. the  automatic  code-generation  is  similar  to  that  of  application  generators.   Yet,  the  VHLLs  are
  131. application-independent general-purpose languages of higher complexity (e.g.,  they use first-order
  132. logic). Languages like (ML)2 [8 ], KARL, or MoMo [9 ] use the KADS-I model of expertise (cf. [10 ])
  133. as conceptual model for their language constructs.  In Europe the KADS-I model of expertise is
  134. widely accepted as the appropriate conceptual framework for the sp ecification of knowledge-based
  135. systems. The languages differ in whether they aim more at formalization or operationalization of
  136. a model of ex
  137.  
  138.  
  139.  
  140. 2.3     Reuse of Problem-Solving Methods by Formal Methods
  141.  
  142.  
  143.  
  144. Currently, reuse  by  problem-solving  methods  and  reuse  by  Very-high-level  languages  converges.
  145. KADS-I proposed a set of standardized elementary inference actions. [11 ] formally describes this
  146. set of elementary inference actions in (ML)2.  The granularity of these reusable blocks is less or
  147. equal to the above mentioned problem-solving mechanisms.  Asecond example is the specification of
  148. several problem-solving methods in KARLlike the board-game method, chronological backtracking,
  149. cover-and-differenciate, propose-and-exchange, etc.
  150. These formal descriptions of reusable components have the following advantages compared to pure
  151. informal  descriptions  by  natural  language  and  graphics:  Natural-language  documents  have  an
  152. ambiguous and vague semantics;  there is a high cognitive distance between the specification and
  153. the implementation, i.e. the specification is not an appropriate means for defining the behaviour of
  154. the implementation; as the specification is not executable, there is little support in evaluatingit;
  155. and as the specification is informal, there is no support in verifying its correctness and completeness
  156. by formal methods.
  157. Secondly, formal descriptions of reusable componentResearch which aims at improving the usability
  158. of the mechanism library and the formal specification languages approach by their combination will
  159. have to address two main topics:
  160. Study of the formal semantics of the languages: The selection and modification of problem-solving
  161. methods or mechanisms can be supported by formal reasoning based on the semantical properties
  162. of the specifications of the methods or mechanisms in these languages. It requires further research
  163. to decide which of the several declarative semantics for formal specification languages is best suited
  164. for that purpose.  (ML)2 and KARL both use dynamic logic for specifying procedural knowledge
  165. but differ significantly in their way of integrating this with the specification of static knowledge.
  166. A further possibility is exemplified by the language DESIRE [12 ] which employs partial temporal
  167. logic as semantics.
  168. Study of the formal properties of the problem-solving methods: The formal specification of a problem-
  169. solving method is the precondition for formally supporting its reuse. The complexity of the search
  170. process for appropriate problem-solving methods according to a given formal description of a task
  171.  
  172.  
  173.                                                          Fensel- 3
  174.  
  175.  
  176. (cf. [13 ]) can be significantly reduced by deriving pre- and postconditions from these for
  177.  
  178.  
  179.  
  180. References
  181.  
  182.  
  183.  
  184.   [1] D. Fensel, "The Knowledge Acquisition and Representation Language KARL," Tech. Rep. Ph
  185.       D. thesis, University of Karlsruhe, Institut fuer Angewandte Informatik und Formale Beschrei-
  186.       bungsverfahren, 1993.
  187.  
  188.  
  189.   [2] C. W. Krueger, "Software Reuse," ACM Computing Survey,vol. 24, no. 2, pp. 131-184, June
  190.       1992.
  191.  
  192.  
  193.   [3] J.-M.  David,  J.-P.  Krivine,  and  R.  Simmons,  Second  Generation  Expert  Systems.   Berlin:
  194.       Springer-Verlag, 1993.
  195.  
  196.  
  197.   [4] J.  Angele,  D.  Fensel,  D.  Landes,  S.  Neub ert,  and  R.  Studer,  "Model-based  and  Incremen-
  198.       tal Knowledge Engineering:  The MIKE  Approach," in J.  Cuena  (ed.),  Knowledge Oriented
  199.       Software Design, IFIP Transactions, A-27, (Amsterdam), North-Holland, 1993.
  200.  
  201.  
  202.   [5] W. Clancey, "Heuristic Classification," Artificial Intel ligence, vol. 27, pp. 289-350, 1985.
  203.  
  204.  
  205.   [6] J. Breuker, B. Wielinga, M. Someren, R. de Hoog, G. Schreiber, P. de Greef, B. Bredeweg,
  206.       J. Wielemaker, and J.-P. Billault, "Mo del-Driven Knowledge Acquisition: Interpretation Mod-
  207.       els," Tech. Rep. ESPRIT project P1098, report, University of Amsterdam, 1987.
  208.  
  209.  
  210.   [7] M. Musen, "Overcoming the Limitations of Role-Limiting Methods," Knowledge Acquisition,
  211.       vol. 4, no. 2, pp. 165-170, June 1992.
  212.  
  213.  
  214.   [8] F. v. Harmelen and J. Balder, "(ML)2:  A Formal Language for KADS Conceptual Models,"
  215.       Knowledge Acquisitionn, vol. 4, no. 1, pp. 127-161, March 1992.
  216.  
  217.  
  218.   [9] A.  Voss, H.  Voss, J.  Walther,  and  T.  Hemman,  "Model-Driven  Prototyping  -  Prototyping-
  219.       Driven Modelling in Knowledge-Based Systems," in Proceedings of Requirements Engineering
  220.       RE93  -  Prototyping  -,  (Bonn),  H.  Zllighoven  (ed.),  Teubner  Verlag,  Stuttgart,  25-27  April,
  221.       1993.
  222.  
  223.  
  224. [10]  B.  Wielinga,  A.  Schreiber,  and  J.  Breuker,  "KADS:  A Modelling  Approach  to  Knowledge
  225.       Engineering," Knowledge Acquisition, vol. 4, no. 1, pp. 5-53, March 1992.
  226.  
  227.  
  228. [11]  M. Aben, "CommonKADS Inferences," Tech.Rep. ESPRIT Pro ject P5248 KADS-II, KADS-
  229.       II/M2/TR/UvA/041/1.0, University of Amsterdam, 1993.
  230.  
  231.  
  232. [12]  I.  A.  van  Langevelde,  A.  W.  Philipsen, and  J.  Treur,  "Formal  Specification  of  Composi-
  233.       tional Architectures," in Proceedings of the 10th European Conference on Artificial Intelligence
  234.       (ECAI92), (Vienna, Austria), August 3-7,1992.
  235.  
  236.  
  237. [13]  H.  Akkermans,  B.  Wielinga,  and  G.  Schreiber,  "Steps  in  Constructing  Problem  Solving
  238.       Methods," in Knowledge Acquisition for Knowledge-Based Systems, 7th European Workshop,
  239.       EKAW93, (Toulouse and Caylus, France), Lecture Notes in AI, no 723, Springer-Verlag, Berlin,
  240.       September 6-10, 1993.
  241.  
  242.  
  243. [14]  S. Marcus, Automating Know ledge Acquisition for Experts Systems. Boston: KluwerAcademic
  244.       Pub., 1988.
  245.  
  246.  
  247. [15]  F. Puppe, Systematic Introduction to Expert Systems: Knowledge Representation and Problem-
  248.       Solving Methods. Berlin: Springer-Verlag, 1993.
  249.  
  250.  
  251.                                                          Fensel- 4
  252.  
  253.  
  254. 3      Biography
  255.  
  256.  
  257.  
  258. Since 1989 Dieter Fensel is working as a scientist at the University of Karlsruhe. He holds a Diploma
  259. in computer science from the Technical University of Berlin and a Diploma in social science from
  260. the Free University of Berlin.  He received his Ph.D. in economic science from the University of
  261. Karlsruhe in 1993.  His thesis was concerned with the development of the Knowledge Acquisition
  262. and Representation Language KARL. He developed the modelling primitives and the formal (i.e.,
  263. declarative)  semantics  of  KARL.  Currently,  he  is  working  on  reuse  of  formal  specifications  and
  264. use of formal specifications for reuse.  Further activities are concerned with the development and
  265. application of machine learning algorithms.
  266.  
  267.  
  268.  
  269.                                                          Fensel- 5
  270.