Microsoft Word - brain_1_4_nou_modif.doc BRAIN. Broad Research in Artificial Intelligence and Neuroscience Volume 1, Issue 4, October 2010, ”Autumn 2010”, ISSN 2067-3957 (in progress) 69 Computational Mathematics in Medicine Angel Garrido Faculty of Sciences, National University of Distance Education, Madrid, Spain Paseo Senda del Rey, 9, 28040, Madrid, Spain algbmv@telefonica.net Abstract AI requires Logic. But its Classical version shows too many insufficiencies. So, it is very necessary to introduce more sophisticated tools, as may be Fuzzy Logic, Modal Logic, Non- Monotonic Logic, and so on [2]. Among the things that AI needs to represent are Categories, Objects, Properties, Relations between objects, Situations, States, Time, Events, Causes and effects, Knowledge about knowledge, and so on. The problems in AI can be classified in two general types [3, 4], Search Problems and Representation Problem. There exist different ways to reach this objective. So, we have [3] Logics, Rules, Frames, Associative Nets, Scripts, and so on, many times interconnect. Also it will be very useful, in the treatment of the problems of uncertainty and causality, the introduction of Bayesian Networks and particularly, a principal tool as the Essential Graph. We attempt here to show the scope of application of such versatile methods, currently fundamental in Medicine. Keywords: Graph Theory, Bayesian Networks, Computational Biology, AI in Medicine. 1. Representation Methods We can use a series of resources [4] to approach the problems in AI. Between them Logic, Rules, Associative Nets, Frames, and Scripts. The election between these methods must be based in the own characteristics of the problem and our expectation about the type of solution [2]. In many cases, we take at a time two o more tools, as in the case of the Frame System, with participation of Rules, and so on. The Rules shows a great advantage on the Classical Logic [3]. In the Classical Logic, as you known, the Reasoning was Monotonic, with inferences without contradiction with the pre-existing, in SBR. Nevertheless in the RBS, we may delete facts or affirmations of the Base of Facts, according the new inferences. This makes the Reasoning Non-Monotonic, because we can modify the conclusion. Then, appear a question: which we must to make with the conclusion of the affirmation now invalided? For this problem [2], we need to introduce the concept of Type of Dependence of a Rule, which can be Reversible, if we delete the affirmations, then we delete automatically the above inferred facts; or Irreversible, if the facts, once inferred, it is not deleted neither changed. And in the case of some applicable rules at time, which must be executed firstly? Such Rules constitutes, in each step, the Conflict Set (obviously, a dynamic set). The subjacent decision problem is called Resolution of Conflicts or Control of Reasoning. There exist different strategies, for to elect each time a Rule into the Conflict Set, as such Ordering of Rules, Control of Agendas, Criterion of Actuality and Criterion of Specificity. About the first and the second, the commentaries are un-necessaries: they consist in the disposition of the Rules in the order as must be executed. The Criterion of Actuality consists in apply first the Rules in whose antecedent there exists the more actual information. The Motor of Inference must be charged of the control of their respective moments. The Criterion of Specificity lead to execute, firstly, the more specific Rules, that is, that with more facts in its antecedent. So, between R�: if a, then b, and R�: if a and d then c, we must to select R�, because it is more specific than R�. We also have of Mechanisms of Control in RBS. For example using Refractory Mechanism. So, we prevents to execute newly a Rule, once utilized, if do not exist more information which allow or recommend such (in general, anomalous) case Rule Sets. It allows activate or neutralize Block´s Rules; Meta- BRAIN. Broad Research in Artificial Intelligence and Neuroscience Volume 1, Issue 4, October 2010, ”Autumn 2010”, ISSN 2067-3957 (in progress) 70 Rules, they are rules which treat (or reasoning) about other Rules; such Meta-Rules can collaborate in the Control of Reasoning, with the change or assignation of priorities to different Rules, according the evolution of the circumstances. It is the more general and more integrating method, between all the Representation Procedures [2, 4]. They permits introduce some different elements. For instance, by Rules on Frame Systems. We denote such System as FS. We must distinguish between Facets, as properties of the Field, and Devils, as procedures associated to the Frame System. Types of Facets: Defect value, it is the value which we assign to the Field, when it is previously inexistent; Multivalued, when more than a value is admissible; Restrictions, they will be limitations on the values in the Rang of the Field; Certainty, it gives us the credibility of the values of the Field; Interface Facets, it allow the control of the interaction with the usuary. Types of Devils: Devil of necessity, to give a value, before inexistent, to the field; Devil of modification, when it change the value of the field; Devil of deleting, if the value of the field is eliminated; Devil of assignation, it will be when we add the value to the field; Devil of access, when we reclaim the value of the field. They are structures of knowledge [2, 3, 4] which must organize the information relative to dynamical stereotyped situations, that is, ever or almost ever identical sequence of steps, or at least very similar. For instance, go to such cinema or such big store. The words and the subjacent ideas remember to movies. The elements of a Script can be Scenes, Roles, Objects, Places, Names, Conditions, Instruments, and Results. Its signification is evident according their name: for instance, the Scenes must be events described sequentially, being necessary each scene for the realization of the subsequent. With Results, we say the facts obtained, when we have finished the sequence described in the Script. 2. Searching Methods We will distinguish between Blind Search Procedures and Heuristic Procedures. In the first case, the oldest, it is possible to apply Breadth Search, and Depth Search. But with the trouble associated of Combinatorial Explosion, which appears when the so-called ramification index, or branching factor (the average cardinal of the successors of each node) increase without reasonable bounds. For this reason, it is necessary a more efficient procedure of search, by the introduction of heuristic functions, which give the estimation of the distance among the actual node and the final node. In such case, we said that will be the Heuristic Search. Between the Nets, the more actual studies to deal with Bayesian Nets, also called Belief Networks [3]. Before than their apparition, the purpose was to obtain useful systems for the medical diagnosis, by classical statistical techniques, such as the Bayes´s Rule. A Bayesian Net is a pair (G, D), with G a directed, acyclic and connected graph, and D a distribution of probability (associated with the participant variables). Such distribution, D, must verify the Property of Directional Separation, according which the probability of a variable does not depends of their not descendant nodes. 3. Expert Systems The Expert Systems (ESs, in acronym), also called Knowledge-Based Systems (KBSs), are the more usual type of AIM (Artificial Intelligence in Medicine) system in clinical use. They provide medical knowledge, generally about a very specific task, and are able to reason with data from individual patients to come up with adequate conclusion. There are many variations. But many times the knowledge within an Expert System is represented in the form of a set of rules. There are many different types of clinical task to which Expert Systems can be applied: Generating alerts and reminders, Diagnostic assistance, Therapy planning, Agents for information retrieval, Image recognition and interpretation, and so on. In the fields of treatment and diagnosis, we dispose of very important realizations, giving us for instance the subsequent tools: PIP (1971), at BRAIN. Broad Research in Artificial Intelligence and Neuroscience Volume 1, Issue 4, October 2010, ”Autumn 2010”, ISSN 2067-3957 (in progress) 71 MIT; MYCIN (1976), a Rule-Based System, due to Stanford University. It works on infectious diseases; CASNET (1979), it is due to Rutgers University, and it works with ophtalmological problems; INTERNIST (1980), due to Pittsburgh, on inner medicine; AI/RHEUM (1983), at Missoury University, on Reumathology; SPE (also 1983), at Rutgers, to analyze the electrophoresis of proteins; TIA (1984), at Maryland, on the therapy of ischemic attacks, and many others. 4. Graphs and Networks Now, we may analyze the mathematical foundations of Bayesian Networks, and its adequate representation, by an essential graph for each Markovian equivalence class. Let S and S’ two structures of Bayesian Networks (abridgedly BNs) on V, where V will be the set of nodes of the corresponding graph, subjacent to the BN. Then, according to [15], we can say that S is equivalent to S´, denoted by S Χ S’, if S can represent every probability distribution which S’ represents and vice vers. An essential graph of a structure of BN, S, is a Partially Directed Acyclic Graph (PDAG) such that their skeleton is the same that of S, and the essential edges (and only these) are directed. Let C be a class of Directed Acyclic Graphs (in acronym DAGs) Markov equivalent among them. Then, their essential graph would be the smallest graph greater than every DAG that belongs to the class. If we denote the essential graph as G*, this is equivalent to saying G* = ∪ {G: G∈C}, where such graph union is reached by the union of the nodes and edges of G, V (G*) = ∪ V (G), and E (G*) = ∪ E (G). So, G* will be the smallest of upper bound for all graphs of the represented class. Each node represents a random variable, and its edges give the relationship between them. Therefore, Bayesian Nets represent joint probabilities [13, 14, 15]. We says that two BNs are equivalent (denoted by Χ), if both represent the same JPD (joint probability distribution). The following properties hold: • Reflexive: B Χ B, ∀ B; • Symmetrical: if B Χ B’⇒ B´Χ B; • Transitive: if B Χ B’ and B’Χ B’’ ⇒ B Χ B’’. Therefore, it is an Equality Relation, also called an Equivalence Relation [17], defined on the set of BNs. On such mathematical object, it is well established a partition in equivalence classes [13], as we will see then. Let S and S’ be two of such structures of BNs on V. Then, we say that S is equivalent to S’: S Χ S’, if for each parameterization, θ, of S, there exists another parameterization, θ’, of S’, such that P (V / S, θ) = P (V / S´, θ´) Hence, S can represent every probability distribution which S´ represents and vice versa. S is equivalent to S´, denoted by S Χ S´ iff both structures induce the same set of conditional independencies (according the Global Markov Property). In a DAG, if we eliminate its directions to each directed edge [18], the remainder is its skeleton graph. And we call an immorality each configuration of the following type X → Y ← Z, where we can observe the following directed edges, X → Z and Z ← Y. But where the nodes X and Y must never be adjacent, because in such a case, the immorality remains. Recall that they are also called v-structures or head-to-head patterns, according different authors. If we connect (“wedding”) the father-nodes by a line (no-directed edge), and we transform all directed edges into non-directed edges then we say that “the graph is moralized”, or that the Moral Graph of the initial graph has been obtained. Also consider that the set of fathers of a node Y will be Pa (Y) = {X∈V (G): there exist an edge X → Y into E (G)} BRAIN. Broad Research in Artificial Intelligence and Neuroscience Volume 1, Issue 4, October 2010, ”Autumn 2010”, ISSN 2067-3957 (in progress) 72 Two models of BNs are equivalent iff both have the same skeleton and the same immoralities. In DAGs, an edge X→Y is covered, if Pa (Y) = Pa (X) ∪ {X}. Two models of BNs are equivalent iff there exists a sequence of covered edge inversions, transforming one in another model. We can denote the equivalence class of S by [S]. It induces a partition into the set of BNs, Β, in equivalence classes, Ω = Β / Χ = ∪ Β i As Classification, it must be exhaustive and mutually exclusive. Each class includes all the BNs Markov-equivalent to a given (or equivalent between them). To obtain their representation and work efficiently with it, it suffices taking an element as representative, being denominated the essential graph of such class [13, 15]. A directed edge is said to be compelled, or essential, in a structure of BN, S, if it would always be present on each structure equivalent to S. By the Verma & Pearl Theorem, we said that each edge intervening in one immorality will always be one of this type, “compelled”, or essential. But those are not all the essential edges: other edges can be compelled without participating into immoralities. An essential graph of a structure of Bayesian Network, S, is a PDAG such that its skeleton is the same of S, and the essential edges (and only these) are directed. The directed edges connecting the same pair of nodes, but showing opposed directions, into two graphs belonging the same class, C, are substituted by a line. So, G* will be the lesser of the upper bounds for every graph of the class represented Equivalence and Inclusion, by S Χ S´ iff (S ⊂ S´) ∧ (S´⊂ S) And we said that S´ is strictly included into S, if S includes S´, but S´ is not included in S. A structure of BN, S, includes another, S´, iff there exists a sequence of covered arc inversions and additions of arcs which transforms S into S´. So, a structure of BN, S, includes another, S´ iff S is able to represent any joint probability distribution that S´ can represent. Some basic references [1] Barr, A., Feigenbaum, E. A. (1981), The Handbook of Artificial Intelligence,Volumes 1-3. William Kaufmann Inc. [2] Fernández Galán, S., et al. (1998), Problemas resueltos de Inteligencia Artificial Aplicada. Búsqueda y Representación. Addison-Wesley, Madrid. [3] Garrido, A. (2004), Logical Foundations of Artificial Intelligence, FotFS V, Universität Bonn. [4] Mira, J., et al. (1995), Aspectos Básicos de la Inteligencia Artificial, Sanz y Torres, Madrid. [5] Searle, J. (1980), Minds, Brains and Programs, The Behavioral and Brain Sciences, 3, 417-424. [6] Turing, A. (1950), Computing machinery and intelligence, Mind, 59, 433-60. [7] Wiener, N. (1947), Cybernetics, MIT Press and John Wiley, New York. [8] Dubois, D., Prade, H. (2000), Fundamentals of Fuzzy Sets, Kluwer Publ., Netherlands. [9] Dubois, D., Prade, H. (1988), Possibility Theory, Plenum Press, New Jersey. [10] Garrido, A. (2006), Special Functions in A I, Opuscula Mathematica, Vol. 26, Issue Nr. 3, 457-464, AGW Publishers, Krakow University, Poland. [11] Pedryck, W. (1993), Fuzzy Control and Fuzzy Systems, Wiley and Sons Co., New York. [12] Wang, Z. (1997), A Course in Fuzzy Systems and Control, Prentice-Hall, New Jersey. More references [13] Anderson, S. A., Madigan, D. Perlman, M. D. (1997), A characterization of Markov equivalence classes for acyclic digraphs. Ann. Statist, 25, 505-541. [14] Barro, S., Marin, R. (2002), Fuzzy Logic in Medicine, Physica Verlag, Heidelberg. BRAIN. Broad Research in Artificial Intelligence and Neuroscience Volume 1, Issue 4, October 2010, ”Autumn 2010”, ISSN 2067-3957 (in progress) 73 [15] Garrido, A. (2009), Chain Graphs and Directed Acyclic Graphs Improved by Equivalence Classes and Their Essential Graphs, SIC (Studies in Informatics and Control), 17-24. [16] Gillispie, S. B., Perlman, M. D. (2002), The size distribution for Markov equivalence Classes of acyclic digraph models, AI, 141 (1/2), 137-155. [17] Gillispie, S. B., Perlman, M. D. (2001), Enumerating Markov equivalence classes of acyclic digraph models, UAI 2001, 171-177. [18] Harary, F., Palmer (1973), Graphical Enumeration, Academic Press, New York. [19] Mordeson, J. N., Malik, D. S., Cheng, S. C. (2000), Fuzzy Mathematics in Medicine, Physica Verlag, Heidelberg. [20] Pólya, G. (1987), Combinatorial enumeration of groups, graphs… Springer Verlag. [21] Robinson, P. (1973), Counting labeled acyclic digraphs, In: New Directions in the Theory of Graphs, 239-279, Academic Press, New York. [22] Steinsky, B., Grabner, P. J. (2005), Asymptotic behavior of the poles of a special generating function for acyclic digraphs, Aequationes Mathematicae, 70 (3), 268-278. [23] Steinsky, B. (2004), Asymptotic behavior of the number of labeled essential acyclic digraphs and labeled chain graphs, Graphs and Combinatorics, 20 (3), 399-411. [24] Steinsky, B. (2003), Enumeration of labeled chain graphs and labeled essential directed graphs, Discrete Mathematics, 270 (1-3), 266-277. [25] Szczepaniak, P. S., Lisoba, P. J. G., Kacprzyk, J. (2000), Fuzzy Systems in Medicine, Physica Verlag, Heidelberg. [26] Torres, A., Nieto, J. J. (2006), Fuzzy Logic in Medicine and Bioinformatics, J. of Biomedicine and Biotechnology, Vol. 2006, 1-7.