:encoding: ISO-8859-1 An introduction to knowledge engineering ======================================== Christophe Lalanne Jan. 2008 // Applications using Neural Networks, Genetic Algorithms and Rule-Based Systems image:ike.jpg[ike.jpg] *http://www.springer.com/west/home?SGWID=4-102-22-165247224-0&changeHeader=true&SHORTCUT=www.springer.com/978-1-84628-475-5[An introduction to knowledge engineering], Simon Kendal & Malcom Creen, Springer 2005.* This book provides a gentle introduction to knowledge engineering which encompasses the acquisition, representation and management of so-called "knowledge". After reviewing the basic tools for managing knowledge-based systems, namely Expert Systems, Neural Networks, Case-Based Reasoning, Genetic Algorithms, Intelligent Agents and Data Mining, the authors develop useful concepts relating to knowledge acquisition and representation. Then, dedicated programming languages are reviewed, including expert systems shells and PROLOG, before tackling the design of common knowledge-based systems (architecture, life cycle and the like). Finally, the rest of the book is devoted to uncertain reasoning and hybrid knowledge-based systems, with a particular emphasis on probabilistic reasoning, fuzzy logic, and the integration of symbolic and connectionist systems. ***************************************************************************** This article is referenced from the http://www.aliquote.org/2008/01/introduction-to-knowledge-engineering.html#links[following post] on http://www.aliquote.org[www.aliquote.org], and is also available in link:./KnowledgeEnginneering.pdf[pdf format]. ***************************************************************************** Summary ------- Although this book should be viewed as an elementary book on such an extensive field as Knowledge-Based Systems (KBS), I shall use it as the basis for illustrating some of the classical tools tuned to Artificial Intelligence (AI) programming. The open-source statistical package http://www.cran.r-project.org[R] will be used in the following applications. Other reference textbooks related to AI and KBS include, but is not limited to: - Artificial Intelligence: A Modern Approach, by Stuart Russel and Peter Norvig (1995, Prentice Hall) http://aima.cs.berkeley.edu/[homepage of the 2nd version] - Knowledge Systems Design, by J. K. Debenham (1988, Prentice Hall) Some additional pointers can be found on the free on-line encyclopedia http://en.wikipedia.org/wiki/Knowledge-based_systems[Wikipedia]. We will mainly focus our attention on Neural Networks, Genetic Algorithms and Data Mining. These computational frameworks will be used as our starting point for Neural networks --------------- Before going down to the statistical properties of the NN approach, in particular its link to the more usual regression approach, let's remind the reader some of the main properties of an artificial NN. A classical textbook on this subject obviously is <>. Principles of neural modeling ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ It can be shown that a two-layer feedforward neural network can implement any Boolean function. Figure 1 illustrate how a two-layer network can solve the XOR problem (reproduced from <>, p. 279). .A two-layer network that can solve the XOR problem [caption="Figure 2 : "] image::img/nn_xor.png[nn_xor.png] You may recall that the XOR problem, i.e. the exclusive-OR function whose truth table is given below, usually cannot be resolved by the basic artificial neuron proposed by <>. .The XOR function [grid="all"] .-----.-----.---- x~1~ x~2~ y ----------------- 0 0 0 0 1 1 1 0 1 1 1 0 ---------------- Some applications ~~~~~~~~~~~~~~~~~ The R package `nnet` (now bundled in the `VR` package) allows to fit a single-hidden-layer neural network to a data matrix. To illustrate how such NN can uncover the properties of a dataset, we will use the well-known Fisher Iris data (Fisher, 1936). These data are measurements of the sepal length and width and petal length and width in centimetres of fifty plants for each of three types of iris; Iris setosa, Iris versicolor and Iris virginica. They most often are used to illustrate the principles underlying discriminant analysis. Indeed, though the data were collected by Dr. Edgar Anderson, R. A. Fisher published the data on Iris setosa and Iris versicolor to demonstrate the use of discriminant functions. The Iris virginica data are used to extend Fisher's technique and to test Randolph's (1934) hypothesis that Iris versicolor is a polyploid hybrid of the two other species which is related to the fact that Iris setosa is a diploid species with 38 chromosomes, Iris virginica a tetraploid and Iris versicolor having 108 chromosomes is a hexaploid. Here is what it looks like: ----------------------------------------------------------------------------- > data(iris) > pairs(iris) ----------------------------------------------------------------------------- .The Fisher's iris [caption="Figure 1 : "] image::img/iris.png[iris.png] The program link:./code/nn_ex1.java[nn_ex1.java] implements a basic hopfield neural network. Knowledge representation and management --------------------------------------- Rule-based systems ~~~~~~~~~~~~~~~~~~ Representing knowledge through a KBS can be handled using two kind of programming approach: Procedural and Declarative. Procedural programming refers to a set of procedures, or fixed instructions, that have to be performed in a specific order, while declarative programing mainly involves a set of rules (statements about given facts) for which the processing sequences are not defined by the engineer. In short, the statements provide information regarding the association between several objects, or entities, and the system decides, through its inference engine, when to apply selected rules. Among others, forward and backward chaining (also see http://www.cse.unsw.edu.au/~billw/aidict.html[The AI Dictionary]) are generally found in any rule-based system. Such a system uses the basics of propositional logic to manipulate data which in turn is stored in the system through symbols or entities related one to to each other. Relationships between entites and values are mostly represented using classical symbols, such as AND, OR, NOT, IMPLIES, FOR ALL, EXIST, etc. In _forward chaining_, the inferential procedure starts with a set of facts (i.e. logical assertions of the form IF fact1 THEN fact2) and processes them to reach conclusions about the domain of expertise. Forward chaining rules are fired for each new data that is presented to the system until it cannot reach any further conclusion. On the contrary, in _backward chaining_, the system is initialized with a given hypothesis, and, then, the veracity of this hypothesis is proved by checking the rules within the domain. In other words, the system is driven from the goal to the data while the reverse holds in the preceding case. Quoting the http://www.computer-dictionary-online.org/[Online Computer Dictionnary]: [backward chaining, (1997-07-14)] _____________________________________________________________________________ An algorithm for proving a goal by recursively braking it down into sub-goals and trying to prove these until facts are reached. Facts are goals with no sub-goals which are therefore always true. Backward training is the program execution mechanism used by most logic programming language like Prolog. Opposite: forward chaining. _____________________________________________________________________________ One can find an implementation in Java of such rule-based programming on the http://algernon-j.sourceforge.net/[Algernon's project] webpage. There is also a complete implementation of an http://www.amzi.com/ExpertSystemsInProlog/[expert system in PROLOG]. Note that among Algernon code samples, there is a Mycin-like reasoning sheme example. Mycin <> is a well-known example of the use of Expert System in the biomedical domain, and it was mainly used for training the becoming physician (other links: http://www.computing.surrey.ac.uk/ai/PROFILE/mycin.html[1], http://en.wikipedia.org/wiki/Mycin[2]). // TODO // http://www.cert.fr/dcsd/THESES/fabiani/manuscrit_fabiani/node334.html The following example is taken from the http://algernon-j.sourceforge.net/doc/examples/mini-Mycin/[Algernon example]. It shows how one of the decision rules is intanciated using this KBS: ----------------------------------------------------------------------------- ;; Rule 4 "A patient who has renal_abnormality has abnormal_urologic_anatomy" (tell ((:add-rule Assertion ;; test slots of the modified or new Assertion ((concept ?assertion "renal_abnormality") (value ?assertion :TRUE) -> (:add-instance (?assertion Assertion ) ;; Add a new assertion (concept ?assertion "abnormal_urologic_anatomy") (value ?assertion :TRUE)) )) )) ----------------------------------------------------------------------------- The following articles, related to various scientifical fields, should be of relevant interest: ============================================================================= - S. S. Joshi and B. Guilhabert, Sequence-Learning Algorithm Based on Backward Chaining, *Adaptive Behavior*, *14(1)*: 53-71 (2006) [http://adb.sagepub.com/cgi/content/abstract/14/1/53[abstract]] - R. Poli and W. B. Langdon, Backward-chaining evolutionary algorithms, *Artificial Intelligence*, *170*: 953-982 (2006) [http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/poli_2006_AIJ.pdf[pdf paper]] - T. Mszros and B. Vadsz, An Extension to the RETE Match Algorithm: Supporting both Forward and Backward Chaining, *TEMPUS JEP3815*, Budapest, Hungary (1994) [http://citeseer.ist.psu.edu/rd/13818962%2C270955%2C1%2C0.25%2CDownload/http://citeseer.ist.psu.edu/cache/papers/cs/13804/http:zSzzSzwww.mit.bme.huzSz%7EmeszaroszSzmezSzpubszSztempus94.pdf/an-extension-to-the.pdf[pdf paper]] - D. H. Fisher, M. E. Edgerton, Z. Chen, L. Tang, and L. Frey, Backward Chaining Rule Induction [http://www.vuse.vanderbilt.edu/~dfisher/IDAfinalsubmission.pdf[pdf paper]] - L. Aversano, G. Canfora, and A. Clampi, An Algorithm for Web Service Discovery through Their Composition, *IEEE International Conference on Web Services (ICWS'04)*: 332 [http://csdl2.computer.org/persagen/DLAbsToc.jsp?resourcePath=/dl/proceedings/&toc=comp/proceedings/icws/2004/2167/00/2167toc.xml&DOI=10.1109/ICWS.2004.1314755[abstract]] - R. Poli and W. B. Langdon, Backward-chaining Genetic Programming, *GECCO'05*, June 25-29 (2005) [http://cswww.essex.ac.uk/staff/poli/papers/geccobackchain2005.pdf[pdf paper]] ============================================================================= // TODO: // http://ai-depot.com/Tutorial/RuleBased-Methods.html // Semantic networks and frames ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Both methodologies-- semantic network and frames--can be thought as the precursors of the actual high-level programming languages, such as C++ or Java, which are fundamentally object-oriented languages. Semantic networks are mostly a convenient way to graphically represent associations between entities in the knowledge domain. In fact, associations allow to describe the hierarchical relations between all of the entities. Such a graphical network is illustrated in the following figure (reproduced from Kendal & Creen, p. 143). .A small semantic network [caption="Figure 2 : "] image::img/sn1.png[sn1.png] Relations, in particular inheritance relationship, can be represented using a simple oriented graph whose node contains the entities and link represent the relation between two entities. However, as shown in Figure 3 (Kendal & Creen, p. 144), adding a single property to the network can drastically reduce the power of the inference that can be made about the domain. Indeed, after setting that _grass snake eats meat_, we now arrive at differing conclusions depending on when we start to read the graph. .The same semantic network after a slight modification [caption="Figure 3 : "] image::img/sn2.png[sn2.png] For the interested reader, some links are given below: ============================================================================= - http://www.semanticresearch.com/[Semantic Research] (includes the Semantica (R) software and some white papers available as pdf, like http://www.semanticresearch.com/downloads/whitepapers/theory_whitepaper.pdf[Knowledge and Semantic Network Theory]) - http://www.ipli.com/semantic.htm[Semantic Networks, Concept Maps, Knowledge, Knowledge Representation] - http://www.sciam.com/article.cfm?articleID=00048144-10D2-1C70-84A9809EC588EF21[The Semantic Web] (from *Scientific American*) - http://www.conroeisd.net/departments/tlc/plan/mindtools.htm[Mindtools for Cognitive Thinking] - M. Hsing and A. Cherkasov, Integration of Biological Data with Semantic Networks, *Current Bioinformatics*, *1(3)* (2006) [http://colab.cim3.net/file/work/SICoP/2006-10-10/Hsing_CBIO.pdf[pdf paper]] - S. J. McGriff, Measuring cognitive structure: An overview of Pathfinder Networks and Semantic Networks (2001) [http://www.personal.psu.edu/sjm256/portfolio/kbase/Theories&Models/Cognitivism/Cognitive-Structure.pdf[pdf paper]] - M. Marko, M. A. Porter, A. Probst, C. Gershenson, and A. Das, Transforming the World Wide Web into a Complexity-Based Semantic Network (2002) [http://arxiv.org/html/cs.NI/0205080[html paper]] ============================================================================= // TODO // http://www.coe.missouri.edu/~jonassen/courses/mindtool/SemanticSoftware.html Frames technology offer a way to circumvent some of the limitations of the semantic network approach. More precisely, frames allow .Example of a set of frames [caption="Figure 4 : "] image::img/fr.png[fr.png] Dedicated programming language ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Lisp and PROLOG are certainly the most promoted programming languages for AI applications. They were created in the 1958 and 1972 and differ from procedural language in that they allow the programmer to use declarative assertion rather than inputting a raw sequence of instructions. Bibliography ------------ + [[[Berthold2003]]] Berthold, M. and Hand, D. J. (2003). _Intelligent Data Analysis. An Introduction_. Springer. + [[[Ripley1996]]] Ripley, B. D. (1996) _Pattern Recognition and Neural Networks_. Cambridge. + [[[Buchanan1984]]] Buchanan, B. G. and Shortliffe, E. H. (1984). _Rule-Based Expert Systems, The Mycin experiments of the Stanford Heuristic Programming Project_. Addison-Wesley Publishing Company. [available online at http://www.aaaipress.org/Classic/Buchanan/buchanan.html[www.aaaipress.org]] + [[[McCulloch1943]]] McCulloch, W. S. and Pitts, W. (1943). A logical calculus of the ideas immanent in nervous activity. _Bulletin of Mathematical Biophysics_, _5_, 115-133. + [[[Kabbaj1991]]] Kabbaj, A. (1991). _Intelligence Artificielle en Lisp et Prolog_. Masson.