An MML-based tool for evaluating the complexity of (stochastic) logic programs

An MML-based tool for evaluating the complexity of (stochastic) logic theories MSc Thesis Enginyeria del Programari, Mètodes Formals i Sistemes d'Informació Héctor Castillo Andreu Departament de Sistemes Informàtics i Computadors Universitat Politècnica de València Advisors: José Hernández-Orallo, Maria José Ramírez-Quintana and Cèsar Ferri September 2012 Copyright c  Héctor Castillo Andreu This document is distributed under Creative Commons Attribution-ShareAlike (http://creativecommons.org/licenses/bysa/3.0/deed.en) license: you can copy, share and also modify the document, but you need to recognise the authory and distribute the results using this same license. Abstract Theory evaluation is a key problem in many areas: machine learning, scientic discovery, inverse engineering, decision making, software engineering, design, human sciences, etc. If we have a set of theories that are able to explain the same set of phenomena, we need a criterion to choose which one is best. There are, of course, many possible criteria. Model simplicity is one of the most common criteria in theory evaluation. The Minimum Message Length (MML) is a solid approach to evaluate theories relative to a given evidence or data. Theories can be expressed in specic or general (Turing-complete) languages. First-order logic, and logic programming in particular, is a Turingcomplete language. Evaluating the simplicity of a theory or program described in a Turing-complete language is much more dicult than just counting the number of lines or bits. It is, in fact, the problem of calculating its Kolmogorov complexity, which is uncomputable. Few works in the literature have been able to present accurate and eective approximations for a Turing-complete language. In this work, we present the rst general MML coding scheme for logic programs. With this scheme, we can quantify the bits of information required to code (or send) a theory, a set of data or the same data given the theory. Moreover, we extend the expressiveness of the language to stochastic logic programs, which are not only able to model the truth value of any set of phenomena, but also their probability. As a result, we extend the coding scheme to stochastic logic programs. This opens up the applicability of model selection to many dierent problems which have a stochastic or probabilistic character, such as games, social phenomena, language processing, Markov processes, etc. As a realization of the above-mentioned schemes, we present a software tool which is able to code and evaluate a set of alternative (stochastic) theories (programs) against a set of examples. We illustrate the application of the tool to a variety of non-probabilistic and probabilistic scenarios. iii List of Contents Abstract iii 1 Introduction 1 1.1 Asimpleexample......................... 2 1.2 Objectives............................. 3 1.3 Organization ........................... 4 2 Background 7 2.1 Theory evaluation . . . . . . . . . . . . . . . . . . . . . . . . 7 2.2 TheMMLprinciple........................ 10 2.3 Logicprograms.......................... 12 2.4 Inductive Logic Programming (ILP) . . . . . . . . . . . . . . 14 2.5 Stochastic Logic Programs . . . . . . . . . . . . . . . . . . . . 17 2.5.1 SSLD-derivation approaches . . . . . . . . . . . . . . . 20 2.5.2 Our method for SSLD-derivation . . . . . . . . . . . . 21 2.6 Previous approaches for coding logical theories . . . . . . . . 27 2.6.1 The Model Complexity Approach . . . . . . . . . . . . 28 2.6.2 The Proof Complexity Approach . . . . . . . . . . . . 29 3 Coding scheme 31 3.1 Coding of non-stochastic programs . . . . . . . . . . . . . . . 31 3.1.1 Cost of the signature: cost(ΣP) ............. 32 3.1.2 Cost of coding rule heads: cost(H) ........... 33 3.1.3 Cost of the bodies: cost(B) ............... 35 3.1.4 Cost of the variables: cost(V) .............. 35 3.1.5 Cost of the background knowledge . . . . . . . . . . . 37 3.2 Coding of stochastic programs . . . . . . . . . . . . . . . . . . 38 3.3 Coding the examples ( cost(E|T) )................ 39 4 The tool 45 4.1 Interfaces of the software tool . . . . . . . . . . . . . . . . . . 45 4.2 Transformations of the user code . . . . . . . . . . . . . . . . 48 4.2.1 Canonizing the input program . . . . . . . . . . . . . 48 4.2.2 Solving the problem with predicate **/2 ........ 50 4.2.3 Avoiding direct execution of objectives . . . . . . . . . 51 iv List of Contents v 4.3 Introducing probabilities in Prolog . . . . . . . . . . . . . . . 51 4.3.1 The pre-process of the user code . . . . . . . . . . . . 51 4.3.2 Management of the repetitions in the evidence . . . . 52 4.3.3 How we handle real and rational numbers . . . . . . . 53 4.3.4 Euler's Totient and the F function . . . . . . . . . . . 55 4.4 Analyzing the evidence . . . . . . . . . . . . . . . . . . . . . . 56 4.4.1 Overlapping heads . . . . . . . . . . . . . . . . . . . . 56 4.4.2 Executing the rules when solving an example . . . . . 58 4.4.3 Obtaining the probabilities of the root predicates . . . 59 4.4.4 Repeated predicates in the body of the rule without reduction ......................... 60 4.4.5 The problem with factorial . . . . . . . . . . . . . . . 60 4.5 About the cost of stochastic programs . . . . . . . . . . . . . 62 4.6 The treatment of the knowledge base . . . . . . . . . . . . . . 62 5 Examples 63 5.1 Animal classication . . . . . . . . . . . . . . . . . . . . . . . 63 5.2 Language analysis: speaker recognition . . . . . . . . . . . . . 70 5.2.1 English language parser . . . . . . . . . . . . . . . . . 71 5.2.2 Experimenting with speeches . . . . . . . . . . . . . . 74 5.3 A probabilistic graph . . . . . . . . . . . . . . . . . . . . . . . 78 6 Conclusions and future work 87 6.1 Conclusions............................ 87 6.2 Futurework............................ 88 A Coding numbers 89 A.1 Coding positive integers . . . . . . . . . . . . . . . . . . . . . 89 A.2 Coding rational numbers . . . . . . . . . . . . . . . . . . . . . 90 Appendices 89 B A short introduction to Prolog 93 B.1 SyntaxofProlog ......................... 93 B.2 Programming with Prolog . . . . . . . . . . . . . . . . . . . . 94 C Prolog interpreters and probabilities 97 C.1 Systems implementing probabilities in logic programming . . 97 C.2 Which compiler to use . . . . . . . . . . . . . . . . . . . . . . 100 C.3 Othertools ............................101 C.4 Restrictions............................103 D User manual of the tool 105 D.1 How to install the program . . . . . . . . . . . . . . . . . . . 105 vi List of Contents D.2 Organization ...........................105 D.3 Modiers .............................109 D.4 Codeerrors ............................113 D.5 Website organization . . . . . . . . . . . . . . . . . . . . . . . 113 E Source code of example speaker recognition 117 E.1 Language analysis: source code . . . . . . . . . . . . . . . . . 117 References 129 List of Figures and Tables Figure 1.1 Same data could apply to dierent models . . . . . . . 1 Figure 2.1 Estimating the probability of p(0,1) . The derivation of other examples is not illustrated here. . . . . . . . . 20 Table 2.1 Probabilities before normalization of p/2 in program P4 22 Figure 2.2 An example of SLD-tree with free-variables . . . . . . 23 Figure 2.3 An example of SLD-tree with innite derivations . . . 26 Table 3.1 Code lengths of the programs and their parts using our approach EC ....................... 43 Table 3.2 Code lengths of the programs using the dierent approaches. Here L=L(T) + L(E|T) . .......... 43 Figure 4.1 Combinations generated by the tool from inputs . . . 46 Table 4.1 Example of number of outputs of the tool using a combination of dierent les . . . . . . . . . . . . . . . . . 47 Figure 4.2 Calling the tool without arguments . . . . . . . . . . . 47 Figure 4.3 Calling the tool with a program . . . . . . . . . . . . . 47 Figure 4.4 Initial main page of the Web based version . . . . . . 48 Figure 4.5 Results screen of the Web-based version . . . . . . . . 49 Figure 4.6 Execution schema to check for debug and execution of predened predicates . . . . . . . . . . . . . . . . . . . 59 Table 5.1 Comparison of cost between models covering all the positive evidence . . . . . . . . . . . . . . . . . . . . . 69 Table 5.2 Comparison of cost between models covering almost theevidence........................ 70 Figure 5.1 Developed parser for language processing . . . . . . . 72 Figure 5.2 Experiment with speeches . . . . . . . . . . . . . . . . 74 Table 5.3 Cost in bits of the syntax models . . . . . . . . . . . . 77 Table 5.4 Cost in bits of the lexicon models . . . . . . . . . . . . 77 Table 5.5 Cost in bits of the word models . . . . . . . . . . . . . 78 Figure 5.3 Network representing the reachability of the nodes of the probabilistic example . . . . . . . . . . . . . . . . 80 Figure 5.4 SSLD-resolution tree for predicate path/2 ....... 84 vii Figure B.1 The backtracking in Prolog . . . . . . . . . . . . . . . 96 Table C.1 Benchmark between Prolog compilers in ms of CPU usage, from [10] . . . . . . . . . . . . . . . . . . . . . 101 Figure C.1 Aspect of Eclipse with ProDT plug-in . . . . . . . . . 102 Figure C.2 Aspect of Eclipse with PDT plug-in . . . . . . . . . . 102 Figure D.1 Example of normalization (left not normalized, right normalized)........................111 Table D.1 Table of data returned with modier tabled . . . . 112 Figure D.2 Aspect of the Website . . . . . . . . . . . . . . . . . . 114 Table D.2 Table of program code errors . . . . . . . . . . . . . . 116 List of Source Code 2.1 ProgramP1............................ 12 2.2 ProgramP2............................ 13 2.3 ProgramP3............................ 13 2.4 ProgramP4............................ 19 2.5 ProgramP5............................ 22 2.6 ProgramP6............................ 25 3.1 ProgramP7............................ 34 3.2 ProgramP8............................ 39 3.3 Program P5 without probabilities . . . . . . . . . . . . . . . . 41 4.1 Vanilla meta-interpreter used to estimate evidence . . . . . . 57 5.1 Evidence (Animal classication) . . . . . . . . . . . . . . . . . 64 5.2 Knowledge base (Animal classication) . . . . . . . . . . . . . 65 5.3 Base model (Animal classication) . . . . . . . . . . . . . . . 67 5.4 Model 1 (Animal classication) . . . . . . . . . . . . . . . . . 67 5.5 Model 2 (Animal classication) . . . . . . . . . . . . . . . . . 67 5.6 Model 3 (Animal classication) . . . . . . . . . . . . . . . . . 68 5.7 Model 4 (Animal classication) . . . . . . . . . . . . . . . . . 68 5.8 Model 2 modied (Animal classication) . . . . . . . . . . . . 69 5.9 Model 3 modied (Animal classication) . . . . . . . . . . . . 69 5.10 A probabilistic program . . . . . . . . . . . . . . . . . . . . . 78 5.11 Output of the probabilistic program . . . . . . . . . . . . . . 80 D.1 Process to limit in a shell script . . . . . . . . . . . . . . . . . 113 E.1 A parser for English language . . . . . . . . . . . . . . . . . . 117 viii List of Figures and Tables ix E.2 DCG used in the parser . . . . . . . . . . . . . . . . . . . . . 124 E.3 Lexicon used in the DCG . . . . . . . . . . . . . . . . . . . . 127 Chapter 2 Background In this chapter, we will rst explain theory evaluation, the MML principle and its use for model selection. We will also introduce some fundamentals of logic programming, inductive logic programming and stochastic logic programming. At the end of the chapter, we will review some previous approaches for coding logical theories, such as the Model Complexity ( MC ) and the Proof Complexity ( PC ). 2.1 Theory evaluation In the 1970s, Len Bickman, Carol Weiss and Joseph Wholey started to use the concept of model in the quest of a simplication of the huge amount of data in the international aid and development area. Since that initial proposal, many renements and variations have been added to the basic concept, as we can see in [58]. A logic model from a given domain (a collection of entities) gives us an appropriate semantic entity, using a function which, for each symbol in the domain, species an appropriate semantic value. It is an abstract representation of a domain of information (a program, but also a project, a policy, a machine...) that is intended to produce particular results. The key is to extract the relationships (the outputs) among the resources (the inputs) that are used, and the benets or changes that result, as a sequence of events. We can consider a specic stage of an activity, or the whole. We could analyze the process from left to right, or from top to bottom. Any of these analyses could generate a logic model that summarizes the behavior of a system in the form of patterns (not only rules) that govern it. Many models take some inputs and generate some output data. A model must describe the semantics of those inputs and return also the outputs in the same type of representation. Since those representations are created by 7 8 CHAPTER 2. BACKGROUND human beings, we must consider that the same domain of information might have many dierent models, and all of them could be valid. As a result, one of the big issues in modeling, design and any other abstraction processes is to determine how well the model represents the domain. This problem is known as theory evaluation, in very general terms. Theory evaluation (or selection) has been addressed from many dierent points of view. In philosophy of science, for instance, we may nd criteria for theory evaluation, such as accuracy, performance, generalizability [17] [13] [11] [53], explanatory power [51], coherence [52], consilience [24] 1 , reinforcement [20], information gain [21], aesthetics [32] and, of course, simplicity [25]. Similar criteria can be found when models are used in engineering and social sciences. This usually contrasts to the view of a theory or model in software engineering and database design, especially in software requirement analysis [19], where the criteria are, apparently, dierent. Nonetheless, the notion of simplicity has also been advocated in software engineering as a way of reducing maintenance costs [22]. Even though the notions of accuracy and simplicity are the most common criteria for model selection and evaluation, both concepts are understood in many dierent ways. Most especially, the relation between accuracy and simplicity is always at stake, because a very simple model can be highly inaccurate, and a very detailed, accurate model can be extremely complex. As a result, the idea of a compromise between accuracy and simplicity has been a recurrent issue in philosophy, science and engineering. The basic idea can be traced back to Ockham's Razor, which says that the simplest model is the best one, all the other things being equal. The original assert is attributed to William of Ockham (14th-century): Entia non sunt multiplicanda praeter necessitatem (Entities must not be multiplied beyond necessity). It is a good principle to explain the phenomena by the simplest possible hypothesis. Around 1960, Ray Solomono founded the theory of universal inductive inference , which set the basics for a formal notion of inductive inference, based upon Ockham's Razor and Kolmogorov complexity (an area of research that despite its name, was endeavored by Solomono himself). Kolmogorov or algorithmic complexity [31] is a measure of the amount of computational resources needed to describe the object, given a descriptive language for the strings or sequences. In other words: given a Turing machine T , the algorithmic complexity of a string S , denoted by KT(S) , is the length of the shortest input given to T which causes T to output S . It is also known as algorithmic entropy. It is named after the Russian mathematician Andrey Kolmogorov. Still, simplicity can be understood in many other ways, and not only as 1 The integration of principles from dierent disciplines especially when forming a comprehensive theory. 2.1. Theory evaluation 9 the length of description. For example, in computer science, and programming in particular, we are usually interested in the economy of the computational resources needed by a program, such as time and space complexity. This has led to an enormous amount of work and results in algorithmic and theoretical computer science. Even if we restrict to program size, the calculation of the size, length or descriptional complexity of a model or theory T , denoted by L(T) , has been attempted in the past for many dierent kinds of representation languages: graphs can be evaluated by a function of the number of nodes and arrows, trees by the number of leaves, propositional formulae by the number of terms in their canonical CNF 2 expression, computer programs by the number of lines, variables or loops, etc. As we have already said, in this work we focus on logical models (i.e., logic programs) as representation language. Logic programming is a declarative Turing-complete language, which has a simple syntax and a clear semantics. All this makes logic programs very suitable for knowledge representation. The applications of properly evaluating the simplicity of logic programs are countless, since logic programs can be used to represent models of any parcel of the world, specications in software engineering, including database models, cryptographic models, biological models, social models, etc. Even though logic programs are Turing-complete, there is an important limitation when modeling stochastic processes and events, which are very frequent phenomena. Many real-world problems appear with stochastic or probabilistic evidence, where the data from which we can construct a model is probabilistic in nature. Domains such as meteorology, social processes, transportation, games, networks, just to name a few, are stochastic in nature and are better described by stochastic models. Stochastic, probabilistic and Bayesian logic programs are extensions of logic programming to consider these domains. These approaches tighten better for phenomena where the examples in the evidence are just a sample from a probability distribution. Thus, the theory must represent not only the things that are possible and impossible, but also how likely the phenomena are. For instance, a logic program can state whether the fact rains('10/10/2011',valencia) is true, but a stochastic logic program can state the probability of rains(X,valencia) :- October(X) . In fact, the view of a logic program as dening a distribution on examples, makes it very easy to dene the cost of coding an evidence E given a theory T as L(E|T) = −loge∈Ep(e|T) . In this way, the cost will be higher the lower the probabilities that the theory assigns to the examples and lower otherwise. This makes the coding of theory and data given the theory: L(T) + L(E|T) fully in accordance with Shannon's information theory, as we will see below. 2 A formula is in conjunctive normal form (CNF) if it is a conjunction of clauses, where a clause is a disjunction of literals. 10 CHAPTER 2. BACKGROUND 2.2 The MML principle The Minimum Message Length (MML) principle can be seen as a proper restatement of Ockham's Razor in the area of information theory: since models are not usually equal in goodness of t accuracy to the observed data, the one generating the shortest overall message is more likely to be correct (including the cost of coding the exceptions or details not well covered by the theory). The message is composed of the set of rules of the model plus the evidence concisely encoded using that model. The MML principle was invented by Chris Wallace in 1968 [56]. The MML principle is related to Kolmogorov complexity [57] [31]. In fact, we know that the calculation of the shortest representation for a set of data (i.e., its Kolmogorov complexity) is undecidable in general. Most MML coding schemes can be seen, then, as robust approximations of the Kolmogorov complexity of the theory, K(T) plus the Kolmogorov complexity of the data given the theory, K(D|T) . Let us see now how the MML principle derives from rst principles. This will help us to understand it better. If we have one hypothesis H that covers the problem data D , and we have a way to determine (or estimate) the probabilities of each of the facts of the theory, we have enough information to apply Bayes' Theorem: P(H|D) = P(H)·P(D|H) P(D) where P(H) is the prior probability of hypothesis H P(D) is the prior probability of the evidence D P(H|D) is the posterior probability of hypothesis H given the data P(D|H) is the likelihood of H (2.1) Shannon 3 says that, in an optimal code, the message length of an event E , MsgLen(E) , where E has probability P(E) , is given by: MsgLen(E) = −log2(P(E)) (2.2) So, we have: MsgLen(H|D) = MsgLen(H) + MsgLen(D|H)−MsgLen(D) (2.3) 3 From the well-known theorem in Mathematical Theory of Communication of Claude E. Shannon [50] 2.2. The MML principle 11 MsgLen(H) can usually be estimated. The same happens with the calculation of MsgLen(D|H) . However, deriving MsgLen(D) is more problematic. However, we can see that for two rival hypotheses H and H0 : MsgLen(H|D)−MsgLen(H0|D) = MsgLen(H) + MsgLen(D|H) −MsgLen(H0)−MsgLen(D|H0) (2.4) Clearly, the MsgLen(D) is a constant that vanishes when comparing two or more theories. So if we have a situation where we need to transmit the hypothesis and the data using a Shannon's communication channel, and both sender and receiver have previously agreed on a coding for data and the hypothesis, the best hypothesis H will be the one that transmits both the hypothesis and the data given that theory ( MsgLen(H) + MsgLen(D|H) ) using fewer bits. Then the Minimum Message Length encoding gives a trade-o between hypothesis complexity, MsgLen(H) , and the goodness of t to the data, MsgLen(D|H) . The MML principle is one way to justify and realize Ockham's razor, as we have seen before. So, even when hypotheses are not equal in goodness of t to the observed data, the one generating the shortest overall message is more likely to be correct (where the message consists of a statement of the model, followed by a statement of data encoded concisely using that model). This is the trade-o found by the MML principle, which is better, the better the coding is. Using the same Ockham's Razor formalization, Jorma Rissanen in 1978 dened the concept of the Minimum Description Length (MDL) [48], which says that the best hypothesis for a given set of data is the one that minimizes the length of the theory plus the length of the data coded by the theory. Let us remark rst that this concept appeared ten years after Wallace's MML principle, but MDL principle has become more popular than the MML principle. The dierence between MDL and MML is very subtle and it is a source of ongoing confusion, especially because the MDL principle has been changing over time. For a good account of the dierences, see [2] [55, sec. 10.2] [12, sec. 6.7]. Part of the confusion comes from the way the source paper of the MML principle [56] is cited by the source paper of MDL [48]. In the rest of this work, we will just use the term MML, as being the oldest original term, except for papers which explicitly use the term MDL, but with the same philosophy. 12 CHAPTER 2. BACKGROUND 2.3 Logic programs A logic program, based on Horn-clause logic, is a nite set of rules or clauses of the form: A:−B1, . . . , Bn (2.5) Where n≥0 , A is an atom called head , and the symbols Bi are literals that together constitute the body of the rule. If n= 0 , the rule is a fact in which the symbol :− is dropped in the representation and assumed present. An atom is a predicate term together with its arguments, each argument being also a term. An atom is called ground if it does not contain any variables. A literal is dened as an atom or the negation of an atom (using the predicate not/1 or the symbol ¬ ). We can have dierent kinds of terms: • A predicate term : an expression p(t1, . . . , tm) , with m≥0 . The arity of the predicate symbol is m , so in the expression p(t1, . . . , tm) we say that f is an m -ary predicate symbol . Each ti is again a term (for instance, another variable or function symbol, but not a predicate term). The expression p(t1, . . . , tm) must have an interpretation or denition in the logic program. • A variable : a term which can be assigned to any value in the logic program. By convention they are represented by uppercase letters ( A, B, C... , or more commonly, X, Y, Z... ). The arity of a variable is 0. • A function term : an expression of the form f(t1, . . . , tm) , with m≥0 . It is like a predicate term that cannot appear at the top level of an atom. The symbol f is known as the function symbol or functor. • A constant : with a xed value (numbers, for instance). We could consider them as function symbols with arity 0. For example, the small program P1 below (Listings 2.1) denes the predicates uncle/2 , father/2 and brother/2 , has the variables X,Y,Z and constants adam , peter , tom . This is known as the signature of the program. Note that the number of terms that can be constructed with this signature is nite. Listing 2.1: Program P1 uncle(X,Y):- father(Z,Y),brother(X,Y). brother(X,Y):- brother(Y,X). brother(adam,peter). father(tom,adam). 2.3. Logic programs 13 But if we look at program P2 (Listings 2.2), the introduction of the function term suc/1 makes the number of possible terms innite. Listing 2.2: Program P2 odd(suc(0)). odd(suc(suc(X))):- odd(X). The Herbrand Base B(P) for a logic program P is the set of all possible ground atoms formed by using its signature. On the other hand, the set of all ground terms constructed only from functors and constants is called the Herbrand Universe U(P) . Listing 2.3: Program P3 p(0). q(suc(X)):-p(X). Let us explain this with an example, using programs P2 and P3 . The Herbrand Universe and the Herbrand Base of P2 is: U(P2) = {0,suc(0),suc(suc(0)),suc(suc(suc(0))),...} B(P2) = {odd(0),odd(suc(0)),odd(suc(suc(0))),...} Since here we have only the predicate odd/1 , there are no big dierences between the Herbrand Base and the Herbrand Universe in this case. But, let us see program P3 : U(P3) = {0,suc(0),suc(suc(0)),...} B(P3) = { p(0),p(suc(0)),p(suc(suc(0)),..., q(0),q(suc(0)),q(suc(suc(0))),... } A Herbrand interpretation I is a specic subset of the Herbrand Base. One possible interpretation for the program P2 is this: IP2 = {odd(suc(0)),odd(suc(suc(suc(0))))} A Herbrand model is a Herbrand interpretation which is a model of every formula in its own set. For example, {odd(suc(0)),odd(suc(suc(0)))} is a model of {odd(suc(0))} for program P2 . Notice that the Herbrand base of a program is always a Herbrand model of the program. A Herbrand model is minimal if no proper subset of it is also a model. The usual terminology for any partial ordering is that least means unique minimal. So sometimes we speak of the least Herbrand model . More formally, we will dene the least Herbrand model (if it exists) as the intersection of all Herbrand models for a program P , denoted by M(P) , and it is unique. In our example, for programs P2 and P3 , we have: 14 CHAPTER 2. BACKGROUND M(P2)={0,odd(suc(0)),odd(suc(suc(0))),odd(suc(suc(suc(0)))),...} M(P3)={p(0),q(suc(0))} Every denite clause program P has an operator TP (the immediate consequence operator) associated with it, which maps subsets of atoms from P to subsets of atoms from P . Or, what is the same, it maps Herbrand interpretations of the program to Herbrand interpretations of the program. Our operator TP has a xpoint interpretation I where TP(I) = I , and also we can dene the least xpoint as TP↑ω . With this basis, the process that allows the inference of facts from denite programs 4 can use one of these two dierent strategies: • Top-down : it produces a resolvent between a head of clause and a goal. Using again the program P2 seen in the previous example, to solve odd(suc(suc(X))):-odd(X) , we unify the rule with odd(suc(0)) , using the substitution {X= suc(0)} . Then we recursively solve the new goal obtained from the right-hand side of the rule (if there is). The top-down approach corresponds to SLD-resolution, a concept that we will introduce later on in section 2.5. • Bottom-up : The resolvent is obtained between a fact and the body of a clause. This is also known as the hyper-resolution. In our example, we start from odd(suc(0)) and we apply that in the right of the other clause. The bottom-up approach corresponds to hyper-resolution (sometimes called unit-resolution). 2.4 Inductive Logic Programming (ILP) Deductive inference derives consequences E from a prior theory T . Similarly, inductive inference derives a general belief T from E , but since it is a hypothesis we are going to name it as H . In both deduction and induction T ( H ) and E must be consistent and H|=E . It is usual to separate the above elements into examples ( E ), background knowledge ( B ), and hypothesis ( H ), and state that B∧H|=E . E consists of ground clauses, and can be separated into positive examples ( E+ , composed by denite clauses) and negative examples ( E− , composed by ground unit headless Horn clauses). The problem is dened as nding the theory that is always true with each example in E+ and also false with each in E− . On some occasions, we only have positive examples, and we only consider E+ . 4 A denite program is a program composed only by denite clauses. A denite clause is a clause where we have exactly one positive literal. These representations are equivalent: ¬p1∨ ¬p2∨. . . ∨ ¬pn∨u u ←p1∧p2∧. . . ∧pn but we are going to use the second one. 2.4. Inductive Logic Programming (ILP) 15 So, the inductive inference will generate a hypothesis H subject to the following requirements: necessity B6` E+ consistency B6` e for every e in E− coverage B∪H`E+ (2.6) The necessity condition ensures that the background knowledge does not already entail the examples (because then there would be no necessity of the new hypothesis). The consistency condition asserts that the negation of the hypothesis is not entailed by the background knowledge and examples (because then the hypothesis would be against what we already know) and the coverage condition ensures that the background knowledge and the hypothesis entail the observations. Application areas of ILP are many and include: learning drug structureactivity rules, learning rules for predicting protein secondary structure, learning rules from chess databases, learning rules for nite element mesh design, learning qualitative models of transport system and many others [40]. The idea of carrying out induction by inverting deduction was rst mathematically investigated by Stanley Jevons [36], solving by tabulation the inductive Problem involving two propositional symbols. But the initial research in ILP was conducted by G.D. Plotkin [43] with the lgg and rlgg operators. This is an example of a bottom-up approach, where hypothesis are obtained by generalizing examples. One of the rst operative approaches, the Duce system, is also bottom-up : it was presented in 1987 by Stephen Muggleton [34]. It suggests high-level domain features to the user (or oracle on the basis of a set of example object description. Six transformation operators are used to successively compress the given examples by generalization and feature construction: • Inter-construction : It takes a group of rules, like: X←B∧C∧D∧E Y←A∧B∧D∧F (2.7) and replaces them with the new rules (where the new one is the most specic generalization of the other two rules): X←C∧E∧Z Y←A∧F∧Z Z←B∧D (2.8) • Intra-construction : The application of the distribution law of Boolean equations: X←B∧C∧D∧E Y←A∧B∧D∧F (2.9) 22 CHAPTER 2. BACKGROUND one, so 1 2×1 2=1 4 . We will assign to the branch a probability of 1 4 . Listing 2.5: Program P5 0.5 :: sum(0,W,W). 0.5 :: sum(s(X),Y,s(Z)):-sum(X,Y,Z). But we have not nished, because we have to solve the substitution W/s(s(0)) . To estimate this last substitution, we will need the signature (which is {0/0, s/1} ). As we have only two function symbols, each time we will select one of them we will have a probability of 1 2 . In W/s(s(0)) we have used this selection three times, so the probability of this last substitution is 1 23=1 8 . Thus, with our approximation the probability for this example is 1 4×1 8= 1 32 . In this case, since there are no overlapping rules and no other exceptional issue, we get the right probability for this example on program P5 . Overlapping heads If we look again at the program P4 (Listings 2.4), we can determine the probabilities of predicate p/2 calculating the probabilities of all the combinations, to discover that the sum is greater than 1 : Obtained probability Normalized probability p(0,0) 0.09375 0,06117 p(0,1) 0.49375 0,32216 p(0,2) 0.07875 0,05138 p(1,0) 0.09375 0,06117 p(1,1) 0.09375 0,06117 p(1,2) 0.07875 0,05138 p(2,0) 0.1875 0,12234 p(2,1) 0.1875 0,12234 p(2,2) 0.225 0,14681 Total 1.53262 1 Table 2.1: Probabilities before normalization of p/2 in program P4 We have overlapping heads in program P4 . This is a specic problem of the stochastic programs, where the probabilities of the assigned rules can hide dierent paths for the same fact. The solution here will be to apply an a posteriori normalization process for the predicates. For instance, with p/2 , we have determined a sum of 1.53262 (Table 2.1), so we will divide by this value to have the real probability of each partial probability (for instance, p(2,2) it will be 0.225/1.53262 = 0,14681 ). 2.5. Stochastic Logic Programs 23 The problem with free variables There could be SSLD-derivations that have variables without instantiation. So, the estimation of the probability of a predicate with this kind of derivations will generate an innite loop in our proposed approach if we do not introduce some corrections. For example in this simple program, the variable Z1 is not bound with the head of the rule. The same happens with the variable Z2 with the body of the second rule. We give Z1 and Z2 the name of free variables: p(X,Y):-r(X),r(Z1). q(X,Z2):-r(X). r(_). If we try to generate the SLD-tree for p( X1 , X2 ) and for q( X1 , X2 ) , we can see that our solver is unable to nd a valid assignment for the free variables: p(X1,X2) r(X1),r(Z) {X/X1} q(X1,X2) r(X1) {X/X1} Figure 2.2: An example of SLD-tree with free-variables In fact, it is impossible to determine a priori which the value of probability is for all the derivations of those predicates using the solver described in the previous chapter. Since it is a non-assigned variable (a free variable), its possible assignments depend on the dierent symbols that we have in the signature (if the free variable is in the head of the rule) or on the probability of the predicate that remains with a free variable, if the predicate is in the body of the rule. In our example (Figure 2.2) the free variables that remain without assignation after the unication/matching process of Prolog are two: Y in the head of p/2 and Z in the body of r/1 . In this situation, the success of the unication is not being discussed. The only problem is that the probability of that assignment is aected by this non-assigned variable, which could take any value from the signature of the program as we have said. So, we need to apply some corrections to the solver. 24 CHAPTER 2. BACKGROUND The solution for free variables The changes necessary in the process of solving a predicate dier if the free variable is in the head, in the body or also if the predicate of the head is also present in the body of that rule (due to the recursion). Let us see each of them separately: • Free variables in the head of the rule:  If there is a free variable in the head of a rule the dierent combinations that we could have are all the dierent we can build with the signature (because there is no limitation in the rule to the apparition of any symbol here, because there is no bound between the free variable and any rule).  So, the number of dierent possibilities to instantiate a value to the free variable is given by the division by the number of elements of the signaturem if the arity of the function symbols is equal to zero. That is, if we have q(X,Y):-s(X) and a signature S = {a/0, b/0, c/0} , it is clear that we will have only q(_,0) , q(_,1) and q(_,c) as possibilities.  But maybe the signature could contain a function symbol with a greater arity, for example S = {0/0, s/1} . Here the possibilities for the given are innite combinations of that symbols for that variable: 0 , s(0) , s(s(0)) , etc...  So generalizing, the solution will be to trace from the beginning where the free variables are in the head of a rule. This is because if we postpone this analysis after solving it against the Prolog interpreter, the arguments of the head will have variables that maybe are bound with the body of the rule, maybe not. And we need to separate those two groups of variables to compute the cost. So, the probability of the evidence will be the result of dividing the probability of the rule by the number of elements of the signature, raised to the power of the number of dierent symbols that are in the assignment of that free variable in the example: 2.5. Stochastic Logic Programs 25 ProbExample =Prob(Pred)Y k=1...a 1 length(S) where Prob(Pred) = Probability of the predicate length(S) = Length of the signature (only function symbols) a= Number of dierent elements in the free position (2.19) For example, we have determined that the probability of the example r(0,t(0,s(0))) using the goal r(X1,X2) as root of the tree, over the program P6 (Listing 2.6) is 0.8 , using the assignment X1/0 . Listing 2.6: Program P6 r(X,_):-p(X). 0.8 :: p(0). 0.2 :: p(s(_)). 0.3 :: q(X):-X<1,r(X,Y). 0.7 :: q(1). 0.25 :: r(0,1). 0.25 :: r(0,2). 0.5 :: r(1,2). Variable X2 remains as a free variable. If we have the signature S = {0/0, s/1,t/2} , with the example r(0,t(0,s(0))) (notice that the second argument is using exactly four symbols from the signature) the estimated probability for this example would be: ProbExample = 0.81 3 1 3 1 3 1 3= 0.009876 • Free variables in the body of the rule:  The other problem is when there are free variables in the body: in this case, the probability is not going to depend on the number of symbols of the signature. Although we have a free variable, all the combinations done with the signature are not going to be valid, because this predicate is dened and it has rules that make to success or not some combinations we can made with the signature. 26 CHAPTER 2. BACKGROUND For instance, in Program P6 (Listings 2.6) we have a free variable Y in q(X):-r(X,Y) . So, we must analyze the valid subtrees of predicate r( X1 , X2 ) that can be applied here. On the one hand, there are invalid combinations of the signature ( r(2,0) , r(2,1) ,...). On the other hand, the rst bound variable of the predicate r/2 makes that only r(0,1) and r(0,2) are valid subtrees.  So, we need to check the rule after each solving step, checking if there are new variables after the substitutions. If there are, we will need to obtain the probability of the whole predicate that has free variables, in the same way we are calculating a new example. For instance, if we have: 0.7 :: r(A,B):-Bis A,p(C). 0.3 :: r(A,0). ... % we do not include the rules for p/1. To calculate r(X1, X2) , we will need rst p(X) because in the rule r/2 this predicate appears with a free variable. If we suppose that p/1 has an estimated probability of 0.25 , then we will multiply by this factor the result for the rule r/2 to obtain the real probability of that evidence. Although, a limitation in the depth of SSLD-derivations must be considered, since they could be innite. If we look again at program P5 (Listings 2.5), the function symbol s/1 makes innite the growth of the SSLD-tree for predicate sum/3 , as we show in Figure 2.3. sum(X1,X2,X3) sum(s(X1),X2,s(X3)) sum(0,X2,X2) sum(s(s(X1)),X2,s(s(X3))) {X1/0,X2/X3} 0.5 {X1/s(X1),X3/s(X3)} 0.5 sum(s(s(s(X1))),X2,s(s(s(X3)))) 0.5 {X1/s(X1),X3/s(X3)} 0.5 {X1/s(X1),X3/s(X3)} {X2/0} 0.5 sum(0,0,0) sum(0,s(X2),s(X2)) {X2/s(X2)} 0.5 Figure 2.3: An example of SLD-tree with innite derivations In this SSLD-tree, if we use a low value for the maximum depth inside the tree, the sum of the probabilities for the predicate is going to be nearby 1, but not all the stochastic logic programs are going to have a so simple structure in which the prune of the SSLD-tree is not going to trim important facts that need more depth in the derivation. 2.6. Previous approaches for coding logical theories 27 2.6 Previous approaches for coding logical theories Measuring the length or cost of a theory expressed as a logic program is not a new area of research. As we have pointed out at the beginning of this chapter, there are other previous works for coding logic programs. However, most approaches have been based on the semantics of the program, rather than its syntax. Two exceptions are the so-called Model Complexity ( MC ) [8] and the Proof Complexity ( PC ) [35], which present a way of coding L(D|T) and L(T) . Here, however, the complexity of the program, L(T) , is measured in a very simplistic way, just counting the number of rules, literals, etc., in a program, so disregarding repetitions, structure and other redundancies in how the program is expressed. One of the crucial issues in MML is that the coding must be ecient. Otherwise, the evaluation of the length of the program might be misleading. Also, there are several problems about how the MC and PC approaches calculate the cost of the examples given the theory, L(D|T) , especially for cases where the program covers an innite number of examples, which is a very common situation. Let us start with the coding of the program, L(T) , which is common for both approaches. Two conditions are assumed for these approaches: • Examples must be ground. • Function-free logic programs are used, in order to avoid innite least Herbrand models. With these conditions, assuming that well-formed logic programs have an unambiguous probabilistic context-free grammar, the length in bits of the coding T is calculated as −log2Pr(T) , where Pr(T) is the product of the production probabilities used in the derivation of T . For each atom in the theory T with arity n , the code length of the atom is log2| P |+n·log2(| X |+| F |) , where P represents the predicate terms of the theory, X the variables and F the function terms. In addition to this, to identify the number of variables v needed to express T , we must send a code of length log2( X ) + 1 bits before. To sum up, the number of bits required to code a logic program is the sum of: •log2(v+ 1) bits for the variables, where v=| X | . • 1 bit per program. • 2 bits per rule in the program. • 2 bits per literal in the body of each rule. • The bits for coding all atoms in the program, using the coding scheme seen above. 28 CHAPTER 2. BACKGROUND The previous scheme works for function-free programs. In the next chapter we will extend this to programs including functions, using a MML-coding scheme. In the following two subsections we will analyze how examples are coded given the program, i.e. L(D|T) , in both the model complexity and proof complexity approaches. 2.6.1 The Model Complexity Approach The Model Complexity ( MC ) [8] was presented by D. Conklin and I. H. Witten in 1995. In it, the best theory for a concept is dened to be the one that minimizes the number of bits required to communicate the examples, that involves the encoding and transmission of the theory T and the same examples using that theory T , while they refer to this as a MDL approach, it certainly follows the MML philosophy. First, the coding requires the denition of the content Q(T) , dened as: Q(T) = O∩MT, E ⊆O (2.20) where O are the possible observations and MT is the least Herbrand model of the logic program T ( MT is nite). Q(T) is just the set of ground facts derived from T . With this, there are three possible situations: 1. E6⊂ Q(T) . There are examples not covered by the theory. In this case we must increase the theory to cover those examples, so leading to cases 2 and 3. 2. E⊆Q(T) . The theory covers all the examples, and perhaps other observable atoms: this is the situation that the MC considers, sending a code of length (in bits): LMC(E|T) = log2 |Q(T)| |E|! (2.21) which is large enough for identifying a subset of Q(T) of either size |E| or size |Q(T)| . One extra bit allows the communication of which of these is the case. 3. E=Q(T) . The theory covers all and only all the examples: the ideal but not usual situation. This is a particular case of 2. There are, however, some problems with this approach: 1. It cannot be applied when Q(T) is innite. This happens frequently if we have function symbols. 2.6. Previous approaches for coding logical theories 29 2. As expected, adding a new positive example to the evidence would need fewer bits than adding an example as a rule to the theory, but this asymmetry depends highly on the size of the evidence. The disadvantages are partially solved with the Evidence Complexity ( EC ) approach, which we are going to introduce in chapter 3.3. 2.6.2 The Proof Complexity Approach The other approach for L(E|T) was proposed by Muggleton, Srinivasan and Bain in 1992 [35] called the proof complexity measure ( PC ), dened as the bits required to code the proof of each example given the theory. The proof complexity of an example e is calculated as the sum of the logarithm of the choice-points involved in the SLD-refutation of e . In each step of a refutation, if G is the actual goal, the choice-points are the number of program clauses whose heads unify with the atom of G selected by the selection function. Therefore, LPC(E|T) = X A∈E LPC(A|T) (2.22) where LPC(A|T) is the code length of an atom A wrt. a theory T . In this case, only the given evidence is coded, never the absent examples (those elements in Q(T) which are not in E ). This is counter-intuitive, since LPC(E|T)>0 when Q(T) = E . Even with a perfect-covering program, we have that LPC(E|T) is not zero. The following chapter is then devoted to a coding scheme which considers programs with function symbols (for both L(T) and L(E|T) ) and tries to solve the problems of both the MC and PC approaches. Also, one of the important things of a coding scheme, especially if it is used for theory selection, is that it must be as ecient as possible. The MC and PC approaches, as we will see, contain several sources of redundancy in their codes. Chapter 3 Coding scheme In this chapter we will detail the process of coding theory and data in the form of (stochastic) logic programs, using the MML principle. The organization of the chapter is as follows: we start with the coding of non-stochastic programs. Next we analyze how to extend the coding to stochastic programs. Finally, we focus on the coding of examples. In the non-stochastic section, we split the coding of the signature from the coding of the parts of the rules (heads, body, variables). There is also a subsection dedicated to how background knowledge should be handled. 3.1 Coding of non-stochastic programs A preliminary version of this scheme was presented in [23] in 2007. The goal of the rst scheme was to overcome some of the problems found in the MC and PC approaches seen in the previous chapter. However, the original version contained some glitches and did not properly address the necessary normalization for stochastic programs. Consequently, we present a new scheme based on the previous one, but including an important number of changes and extensions. To determine the MML cost of a program we will need to analyze the terms of each rule: the head, the body and also the variables that are used. For a non-empty program P with m rules r1, r2, . . . , rm , the cost of encoding P is done by the formula: cost(P) = CodeLength(m) + cost(ΣP) + X 1≤i≤m cost(ri) (3.1) Where ΣP represents the signature, and CodeLength the cost of transferring the number of rules, which is calculated as: 31 38 CHAPTER 3. CODING SCHEME 3.2 Coding of stochastic programs Stochastic programs can be coded in the same way as non-stochastic programs, but we need to send the bits for probabilities of each rule. These probabilities are real numbers but they will be approximated and transformed to rational numbers. A real number x can be approximated by a rational number. Of course, since rational numbers are dense on the real line, we can make the dierence between x and its rational approximation p q as small as we wish. The problem is that, as we try to make p q closer and closer to x , we may have to use larger and larger p and q and, clearly, more bits. So, the reasonable question to ask here is how well we can approximate x by rational denominators which are not too large. The idea has been to use a precision threshold. The way real numbers are transformed to rational numbers and the way they are later coded it is fully explained in Appendix A. Basically, we nd a close rational approximation and we code the denominator and ignore the numerator (among all the values which are not reducible). As an example, if we have this program: 0.25 :: p(0). 0.25 :: p(1). 0.50 :: p(X):-X> 20. The cost of coding this stochastic program is the same as this other equivalent program without probabilities but increasing it with the cost of coding the three real numbers: p(0). p(1). p(X):-X> 0. Using the procedures we have seen till now, the MML cost of the program without probabilities is 31.43476 bits. Now, we will add the extra probabilistic cost of 11.03707 due to the coding of the probabilities of the three rules, because: • The rst probability has a cost of Cost(1/4) = CodeLength(4) + log2(2) = 4.518535 + 1 = 5.518535 bits. • The second clause the same. • The third probability 1/2 has a cost of Cost(1/2) = CodeLength(2) + log2(1) = 2.518535 bits. However, we actually do not need to communicate this last probability of 1/2 because it is redundant since the probabilities are supposed to be normalized, so they must add up to 1. • So, we obtain summing up the three values the total of 11.03707 . 3.3. Coding the examples ( cost(E|T) ) 39 3.3 Coding the examples ( cost(E|T) ) The evidence consists of facts. The coding cost for the evidence will depend on the probability of each example observed, deriving the cost of coding it as the −log2 of the probability. 1This leads to this denition of the Evidence Complexity approach ( EC ): Cost(E|T) = −log2p(E|T) (3.12) Where p(E|T) represents the probability of the evidence, given the program T . This does not solve the problem by itself, because there are many dierent ways to estimate p(E|T) . For stochastic programs, this probability is derived by the specic method used for deriving the probabilities. However, for non-stochastic programs we need to derive a way to get the probabilities. Basically, as we detail regard below, we consider a non-stochastic program as a stochastic one where the probabilities are set uniformly. Then, the idea is to use the program as a stochastic example generator and compare E (the examples) with M(T) (the Minimal Herbrand Model of T ). This is highly related to the PC approach, but we have to derive the probabilities with some conditions. The rst condition is that the probability for each rule with the same predicate on the head must have a uniform distribution. We will suppose that ∀e∈Q(T) : p(e|T)>0 (if not, that example can be removed). Q(T) , as seen in equation 2.20, is the set of ground facts derived from T . The second condition is: X e∈Q(T) p(e|T)=1 (3.13) In case this second condition does not hold we can normalize the probabilities. For instance, for the small program P8 : Listing 3.2: Program P8 even(0). even(s(s(X))) :- even(X). Each rule will have a probability of 0.5 . The probability of each possible observable fact is computed by SSLD-resolution: p(even(0)) = 0.5 , p(even(s(s(0)))) = 0.25 , p(even(s(s(s(s(0))))) = 0.125, . . . Another consideration is that the evidence could have or not repeated examples. Also we may cover other facts that are not at the evidence. Examples not covered by the program are not allowed: if there are examples not covered by the program, we will add these examples to the program. Therefore, we have four dierent combinations: 40 CHAPTER 3. CODING SCHEME 1. No repeated examples and E=Q(T) : This is the simplest case, since Q(T) covers all examples in E and nothing else, from the set of logic consequences of Q(T) we will obtain E , and therefore we do not need to transmit L(E|T) . 2. No repeated examples and E⊂Q(T) : In this case we have two options: To code E wrt. Q(T) using the probabilities, or to code the exceptions, i.e. Q(T)−E . We select the cheapest option and then we add an additional bit to inform about our selection. 3. Repeated examples and E=Q(T) : From Q(T) we can deduce E , but in this situation some of the elements of E appear more than once, therefore we need to code the number of times that every element appears ( Ne ). This costs Pe∈ECodeLength(Ne) . 4. Repeated examples and E⊂Q(T) : This case is very similar to the previous one, but here we have that some logical consequences of T do not appear in E , then we need to code E wrt. Q(T) using the probabilities. Another option could be to code the number of times that every element appears ( Ne ) where Ne can be 0; this costs Pe∈ECodeLength(Ne+ 1) . Considering these ways of coding the evidence, we select the case that the evidence contains repeated examples (4), because we can use it for both stochastic and non-stochastic programs and evidence. It is also easy to code each example just using their probabilities. To simplify the coding scheme, we have preferred to consider the case with repeated examples, without distinguish whether the number of repetitions is high or not. If we had a huge number of repetitions, a more optimal coding could be found (consider reading [23]). With this, we rst need to code the length of the given evidence as CodeLength(|E|) . Now, we compute the probability of the sample as the product of the single probabilities: p(E|T) = Qe∈Ep(e|T) . The cost of coding this is −log2p(E|T) = Pe∈E−log2p(e|T) . We have to correct this expression because the order does not matter. Since the order is not important, there will be some combinatorial term corresponding to the number of possible permissible syntactically dierent but semantically equivalent orderings. A corresponding term should be subtracted from the message length. In this case, the number of dierent possible orders is given by the permutations with repetition of the elements of E . To sum up, with the evidence we will proceed as follows: 3.3. Coding the examples ( cost(E|T) ) 41 cost(E|T) = CodeLength(|E|) + Pe∈E−log2p(e|T)−log2|E|! Qei∈Enr |ei|! where |ei|= number of times that example ei is in E Enr = the evidence without repeated examples (3.14) Here the term log2|E|! Qei∈Enr |ei|! is a reduction because the order does not matter. Let us see the process using an example. If we have the program P8 (Listing 3.2) just seen and the evidence is this: even(0). even(0). even(0). even(s(s(0)). even(s(s(0)). Then the cost of coding this will be: Cost(E|P) = CodeLength(5) + Pe∈E−log2p(e|P)−log2(5! 3!·2! ) = 5.3378 −3·log20.5−2·log20.25 −3.3219 = 5.3378 + 3 + 4 −3.3219 = 9.0959 bits (3.15) It is interesting to compare the results of this coding scheme with the other approaches we reviewed in section 2.6, the Model Complexity ( MC ) and the Proof Complexity ( PC ). Imagine again the program P5 that we have seen in section 2.5.1, which comes from [23]: Listing 3.3: Program P5 without probabilities sum(0,X,X). sum(s(X),Y,s(Z)):-sum(X,Y,Z). And the evidence composed by the following set of examples (with no repetitions): sum(0,0,0). sum(0,s(s(0)),s(s(0))). sum(s(0),s(0),s(s(0))). sum(s(s(0)),s(s(0)),s(s(s(s(0))))). sum(0,s(0),s(0)). sum(s(0),s(s(0)),s(s(s(0)))). sum(s(0),0,s(0)). To code the evidence, we give the same probability for each rule. So the cost of L(E|T) using our proposal, the ( EC ), is for this example 22.77 bits. The MC cannot be applied for this problem, because the program 42 CHAPTER 3. CODING SCHEME is not nite. For the PC approach, the cost of coding L(E|T) is 37 bits. It is clear then the advantages of EC approach against the other two. Let us then to use an extra example to compare the three dierent approaches (our EC , the MC , and the PC ). This example appears in [23] and also in [8], and it is related with reachability in a network. Suppose we have this knowledge base of which node reaches which other: linked(0,1). linked(0,3). linked(1,2). linked(3,2). linked(3,4). linked(4,5). linked(4,6). linked(6,8). linked(7,6). linked(7,8). One vertex can reach another if there is a path between them in the graph, and we have obtained from this knowledge six dierent theories that cover the evidence: T1reach(X, Y ). T2reach(0,1). reach(0,2). reach(0,3). reach(0,4). reach(0,5). reach(0,6). reach(0,8). reach(1,2). reach(3,2). reach(3,4). reach(3,5). reach(3,6). reach(3,8). reach(4,5). reach(4,6). reach(4,8). reach(6,8). reach(7,6). reach(7,8). T3reach(X, Y ) : −linked(X, Y ). reach(0,2). reach(0,4). reach(0,5). reach(0,6). reach(0,8). reach(3,5). reach(3,6). reach(3,8). reach(4,8). T4reach(X, Y ) : −linked(X, Y ). reach(X, Y ) : −linked(X, Z). T5reach(X, Y ) : −linked(X, Y ). reach(X, Y ) : −linked(X, Z), linked(Z, Y ). reach(0,5). reach(0,6). reach(0,8). reach(3,8). T6reach(X, Y ) : −linked(X, Y ). reach(X, Y ) : −linked(X, Z), reach(Z, Y ). The Table 3.1 presents the code lengths of these programs using this scheme. The rst ve columns show the cost in bits of coding each part of the theories, whose sum is in the sixth column, representing the cost of coding only T . The seventh column includes the cost of expressing E wrt. T for the programs. 3.3. Coding the examples ( cost(E|T) ) 43 T Rules Lexicon Heads Bodies Variables LEC (T)LE C (E|T) 1 1.52 18.21 3.00 1.52 1.00 34.90 109.00 2 9.00 18.21 177.46 28.87 0.00 233.54 109.71 3 7.37 18.21 87.06 19.19 3.80 135.64 125.34 4 2.52 18.21 6.00 11.04 8.98 46.75 97.44 5 5.93 18.21 43.36 21.36 12.88 101.75 128.74 6 2.52 18.21 6.00 15.29 12.88 25.25 104.17 Table 3.1: Code lengths of the programs and their parts using our approach EC Really, the interest now is to compare the cost of coding E wrt. T with the three dierent approaches. The following table compares the evaluation of each theory according to the Model Complexity approach, the Proof Complexity approach and the Evidence Complexity approach we are using: MC T6T1T4T5T3T2 PC T1T4T6T5T3T2 EC T6T1T4T5T3T2 The ranking of theories is from cheapest to most expensive, from left to right. The results for MC and PC come from [8] and are in Table 3.2. T LEC LPC/MC (T)LMC (E|T)LMC LP C (E|T)LPC 1 143.9 12.5 60.4 72.9 120.5 133.0 2 343.2 178.5 0.0 178.5 80.7 259.2 3 261,9 111.7 0.0 111.7 96.3 208.0 4 144,2 43.7 47.4 91.1 110.6 154.3 5 230,5 94.5 0.0 94.5 101.9 196.5 6 129,4 53.8 0.0 53.8 106.1 160.0 Table 3.2: Code lengths of the programs using the dierent approaches. Here L=L(T) + L(E|T) . While MC and EC obtain almost identical rankings, LPC diers in their preferences. Both ( MC and EC ) rank the correct theory ( T6 ) as the best, and T2 as the worst. LPC selects the most general theory T1 as the best theory. This fact is mainly because LPC needs to always encode E , even when it can be derived from T . For that reason, it gives preference to short theories even though being too general. So, in this example we see that EC inherits the good properties of MC when O (possible observations) is nite. But the good thing is that EC is also applicable to problems with function symbols, to problems with repeated examples and also for stochastic programs. We will see more coding and examples in chapter 6. Chapter 4 The tool In this chapter we present a software tool that implements the MML coding scheme seen in the previous chapter. This chapter is organized as follows: rst we will present the interfaces of the tool. Next, we will analyze some problems that have appeared, such as the necessary canonization of the code, some changes applied to special predicates in the compiler and also the control of the execution of the user code. Later on, we will explain how the probabilities have been introduced in the Prolog language, and how a meta-interpreter is used to determine the probability of the examples. There is a nal section dedicated to free variables, another dicult problem that we have addressed. 4.1 Interfaces of the software tool The tool is an interpreted Prolog source le that needs to be executed in the Yap Prolog compiler, which load also some extra available libraries available in that compiler. The results are returned in the standard output ( stdout ). The tool receives the data to analyze from les referenced in the command line. It will return the cost of each combination in the Cartesian product of two dierent kinds of les that we could use: the program and the evidence les. The content of each kind of les is: • The program or programs to analyze (at least one program is compulsory). • The evidence. It could be composed by dierent les also, The dierent examples sources must be compatible as evidence with the dierent programs. 45 46 CHAPTER 4. THE TOOL stdout mml_cost arguments stdin p1 .. pn program e1 .. em +evidence kb1..kbq +knowledge base kb1..qp3e1... kb1..qp3e2... kb1..qp3em... ... kb1..qpne1 kb1..qpne2 kb1..qpnem kb1..qp2e1 kb1..qp2e2 kb1..qp2em kb1..qp1e1 kb1..qp1e2 kb1..qp1em kb1..q stdin e1 kb1..qstdin e2 kb1..qstdin em Figure 4.1: Combinations generated by the tool from inputs • The knowledge base. This kind of les is not going to be included in the Cartesian product to generate the results. Despite the others, if you introduce more than one KB source, they'll be merged together. In the Figure 4.1, we can see that if we have p1. . . pn items considered as programs, combined with the e1. . . em dierent evidences, we obtain the matrix of n×m outputs. If there is also (or only) an input program in the stdin , it will also be combined with the m evidence sets. For instance, if we have these command line arguments: cat p4 | ./mml_cost p1 p2 p3 --examples=e1,e2 --kb=kb1,kb2 We will have eight dierent outputs from the tool (see Table 4.1) using the dierent program sources (three as arguments p1 , p2 and p3 , and also in the standard input p4 ) with the example les ( e1 and e2 ). The knowledge base will be considered in each one of those eight combinations, and it will contain the direct merge of kb1 and kb2 . Let us introduce some screenshots of the tool in a Windows environment as an example: the Figure 4.2 shows the help that the tool gives to us if we do not use any argument. Figure 4.3 shows the results of an execution with a program which has evidence and knowledge base. If we had introduced a second program in the command line (compatible with the evidence and knowledge base done) then a second evaluation for that program would have done. Notice also that the tool analyzes the correctness of the user code ( P , B and E ). So, a warning has been issued here due to not assigned variables in the user code. 4.1. Interfaces of the software tool 47 Program Examples KB #1 stdin (p4) e1 kb1+kb2 #2 stdin (p4) e2 kb1+kb2 #3 p1 e1 kb1+kb2 #4 p1 e2 kb1+kb2 #5 p2 e1 kb1+kb2 #6 p2 e2 kb1+kb2 #7 p3 e1 kb1+kb2 #8 p3 e2 kb1+kb2 Table 4.1: Example of number of outputs of the tool using a combination of dierent les Figure 4.2: Calling the tool without arguments Figure 4.3: Calling the tool with a program There is also a Web wrapper for the tool for those without a console or an installation. All the options available from the command-line are 54 CHAPTER 4. THE TOOL A is 1 rdiv 4 ?- A is rational(0.1). A = 3602879701896397 rdiv 36028797018963968 ?- A is rationalize(0.1). A = 1 rdiv 10 The documentation of the compiler says that the function rational/1 returns a oating point number, the rational number that exactly represents the oat. As oats cannot exactly represent all decimal numbers the results may be surprising. The function rationalize/1 , unlike the rst one, is only accurate within the rounding error of oating point numbers, generally producing a much smaller denominator. However, since the denominator is just the most important part of the rational numbers that we are going to use in the estimation of the cost, nally our own implementation for rational numbers was used. In order to approximate a real number to the nearest rational one, there are many dierent techniques [16]. The three simplest ones are this: 1. Removing common factors from the fractions. It is always correct but unable to manage 0.33333 in order to get 1/3 , because it will be instead approximated by 33333/100000 (that is actually exactly the equivalent to our oat number, but not an approximation, as we wanted, and also a bit inecient). 2. By brute force (sequential testing). If we have the real number R : (a) We obtain Q as the division of 1 R . (b) Then the oat number R is transformed to n Q·n , where n= 1...k , till we have Q ·n−round( Q ·n)< Precision . This method requires more steps, but it is more precise. 3. And the fastest method, which is the one implemented here: decimal inversion, which is not easy to understand. First we isolate the fractional part of the number, because we need only the decimal part to get the denominator through inversion. After trimming the number, we invert the fractional part and we proceed using this pseudo-code: getDenominator(num) { var decimal =num_int(num); if (Math.abs(decimal)<Precision) return 1; else { 4.3. Introducing probabilities in Prolog 55 num = 1/decimal; return num*getDenominator(num); } } With this function we will obtain the denominator, and despite we have only the fractional part of the original number, there is no dierence: Trimming the integer part will not aect the denominator q, because the denominator for the number and the decimal are the same. A number 1.4 is represented as 7 5 before trimming, and after trimming and leave only the decimal part, it is 2 5 , so the denominators for both are the same. 4.3.4 Euler's Totient and the F function In chapter 3, we developed the basics of the cost of coding some aspects of the programs. There were two dierent functions that we needed to develop in Prolog because they were not part of any library: • The Euler's Totient (as seen in Appendix A.2) needs the Phi function (also known as Euler's Phi function or ϕ(n) ) used in the coding of the numerators of rational numbers. It is dened for a given integer number m as the amount of numbers from 1 to m−1 without common divisors with m . If m= 1 then the Euler's Totient is dened as 1 (instead of 0). The formula that represents this is: ϕ(n) = n·Y p|n (1 −1 p) (4.1) Where the product is over the distinct prime numbers dividing n ( Qp|n means that p iterates over prime numbers in the range 1. . . n ). A direct (but non-ecient) implementation for obtaining this with Prolog: totientPhi(Number ,Result) :- totientPhi(Number ,Result ,1,0). totientPhi(_, 1, Acum,Result):- Result is Acum + 1. totientPhi(M,N,Acum,Result):- (coprime(M,N), NewAcum is Acum + 1 ; NewAcum is Acum ), 56 CHAPTER 4. THE TOOL NewN is N1, totientPhi(M,NewN,NewAcum,Result). But a more ecient implementation was the following: totientPhi(Number ,Result) :- totientPhi(Number ,Result ,1,0). totientPhi(M,Phi,M,Phi). totientPhi(M,Phi,K,C) :- K<M,coprime(K,M),!, C1 is C+ 1, K1 is K+ 1, totientPhi(M,Phi,K1,C1). totientPhi(M,Phi,K,C) :- K<M,K1 is K+ 1, totientPhi(M,Phi,K1,C). • And the other complex thing was to obtain the special function used for coding the variables of the rules (described as function F in the code), which is obtained from the number of variables nv : V ariableProd(d, nv)=(nv)d−X i=1 nv−1 nv i!·V ariableProd(d, i) (4.2) • Obviously the binomial coecient of two numbers nv and i or nv i was not implemented in Prolog, so the code used for this was: binomialCoefficient(N,N,Result):- !,factorial(N,Result). binomialCoefficient(N,K,Result) :- N>=K, NMinusK is N-K, factorial(NMinusK,FactNMinusK), factorial(N,FactN), factorial(K,FactK), Result is (FactN / (FactK*FactNMinusK)) . 4.4 Analyzing the evidence 4.4.1 Overlapping heads To obtain the probability of an example, the simplest method could be to use the Prolog interpreter, and if it success, to use then the labeled probability 4.4. Analyzing the evidence 57 of the rule to recover the probability. Since there can be dierent successful paths in the resolution (because dierent rules can be used), this is not enough for us and will need to solve using a dierent mechanism: a metainterpreter, adapting the concepts of the well-known Vanilla meta-interpreter to our needs. The simplest possible meta-interpreter has only one clause which directly calls Prolog interpreter: solve(A):-call(Goal). But it is just the direct execution of code in Prolog what we want to avoid. The Vanilla meta-interpreter is a meta-interpreter for Logic Programming (and then, for Prolog) specied in rules of Logic-Programming (so, in Prolog). It was rst introduced by [29] in 1982, and extended with the years. It will allow us to intercept the solving procedure as we are going to describe. The core of the Vanilla meta-interpreter is this: Listing 4.1: Vanilla meta-interpreter used to estimate evidence builtin(Ais B). builtin(A=B). builtin(A>= B). builtin(read(X)). builtin(A>B). builtin(A<B). builtin(A=:= B). builtin(A=< B). builtin(functor(T,F,N)). builtin(write(X)). solve(true):- !. solve((A,B)) :-!, solve(A), solve(B). solve(A):- builtin(A), !, A. solve(A) :- clause(A,B), solve(B). The meta-interpreter shown in Listings 4.1 allows us to generate the SSLDtree of execution of a goal without arrive to execute the Goal in the Prolog interpreter. There is no call to call/1 , so we are not going never to execute any predicate of the program we are analyzing. Instead of that, we are unfolding the SSLD-tree, obtaining in each step all the dierent branches, launching again till we success with all the expanded terms, and later summing the returned probabilities of the branches. To obtain the probabilities then, we only will need to add to the Vanilla meta-interpreter some code able to catch and sum the values we have stored in the clauses of the program with the predicate mml_prob/1 : solve( ( mml_prob(Number), Other ), ResultProb ):- number(Number),!, 58 CHAPTER 4. THE TOOL solve(Other,Branch ), ResultProb is Number *Branch. Later, in a second visit to the generated tree of probabilities, we will normalize the values (because the probability of each predicate must be 1). 4.4.2 Executing the rules when solving an example There are some predened predicates in Prolog that could aect the behavior of the calculations. For instance, the debug/0 predicate will be executed and it interacts with the same MML coding. So, since those predicates involved with debugging conict with our purposes (their presence would increase the information and then the cost for the MML coding), we will ignore them during the execution when we are executing the evidence to nd its probability. During that process of executing the rules of the program to analyze an example, we need to analyze whether each term to execute is or is not a predened predicate (using predefined_predicate/2 from Yap Prolog). If it is, they will be discarded. Once we have discarded those predicates, the next step is to execute the others using with_output_to_chars/2 , used to send the output of the execution of the goal to a string instead to current_output : executeTransparently(debug):-!. executeTransparently((spy _)):-!. [...] executeTransparently(Term ):- copy_term(Term,NewCopy),with_output_to_chars( NewCopy,_). With this technique, all these predicates are ignored and not executed during the evaluation of examples: • debug/0 , nodebug/0 , which switches the debugger on/o. • spy/1 , nospyall , nospy/1 , which set/unset spy-points on predicates. • trace/0 , notrace/0 , which switch on/o the debugger and also implies the same with the tracing. • leash/1 , which sets leashing mode to certain value. • source/0 , no_source/0 : these two predicates are not for debugging, but when we analyze the program we need to ensure that we are obtaining its source. If in the middle of the code a no_source appears, the tool will have no more access to the source. To avoid this, we block that predicates also. • halt/1 and halt/0 , to abort the execution of program. 4.4. Analyzing the evidence 59 The schema of execution of items of clauses is shown in Figure 4.6. predefined_predicate(_,Term) copy_term(Term,B), with_output_to_chars(B,_) Is in the list of debug predicates? ? Use again the Vanilla meta-interpreter to obtain new derivations Yes No New terms Ignore it ? No Yes Figure 4.6: Execution schema to check for debug and execution of predened predicates 4.4.3 Obtaining the probabilities of the root predicates The rst step to estimate the probability of a fact is to know the value of all the facts with the same functor name, because we need to normalize. That is: p(3). --> p(X). q(3,1). --> q(X,Y). Till now, we have built a Vanilla meta-interpreter to estimate the probability of the example (for instance p(3) ). Unfortunately, this meta-interpreter is not going to be useful for estimate p(X) , because we need to control some extra problems in the solving process with only variables and no assignments. As we introduced in subsection , the approach has a maximum depth limit used in the go round SSLD-derivations used to estimate the probability of the root predicates (with the success branches labeled with the probabilities). This is because we can have innite SSLD-derivations in some programs. The arbitrary value used in the tool is 20 (it could be changed using the modier maxrecursion ), considered enough to avoid the loss of successful normal branches of the program. But there is another limitation involved with inequalities and equality predicates. For instance, if we have this two predicates, describing relationships in an intensional way: p(X):-X==a;X\=b. q(X):-X>0. 60 CHAPTER 4. THE TOOL Our Vanilla meta-interpreter will fail with both predicates, due to the impossibility of assign all the values to the variable if we are deriving p( X1 ) or q( X1 ) . It is possible at least to solve p/1 with the signature. But q/1 represents the list of all positive numbers, so the probability of the predicate also it will be problematic. In our tool, the equalities and inequalities of the bodies of the rules are problematic and they will make not to solve covered examples of a program: they are not going to success. Our Vanilla meta-interpreter does not know how to obtain values to instantiate if there are equalities and inequalities like the one described in the example. We also need in this second meta-interpreter to control the apparition of new free variables in the rule we are analyzing. In each branch of the SSLD-tree our meta-interpreter must check if there are new free variables and compute them in the probability of the step. So, the solution will be to use a dierent Vanilla meta-interpreter enriched to control both free variables and predicates that could fail (all the comparisons). 4.4.4 Repeated predicates in the body of the rule without reduction There is also another problem not really related with free variables, but with a similar treatment. We can have an innite SSLD-tree if in the body of a rule if it appears the same predicate without any reduction in the body: it is an odd situation, because we cannot refute this program and it will also fail in an interpreter. For example: 0.4 :: r(A,B):-r(A,B),B > 0. 0.6 :: r(A,B):-B is A. Here the predicate r/2 appears again in the rst rule at the body, so we have an innite left-recursion. In this situation, the tool will fail with an error (the same that it will happen if we execute this program with an interpreter), because it has rules without sense (a non-terminating program). 4.4.5 The problem with factorial In our development of the tool, we looked for a mathematical library able to manage huge numbers. Despite the chosen library GMP 1 seemed to t our requirements, Yap Prolog has some problems determining the cost of the evidence, which we have seen in the previous section 3.1.4: 1 GMP (GNU Multiple Precision Arithmetic Library, http://gmplib.org ) is a free library for arbitrary precision arithmetic, operating on signed integers and oating point. Theoretically, there is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. 4.4. Analyzing the evidence 61 cost(E|T) = CodeLength(|E|) + log2p(E|T) = Pe∈E−log2p(e|T)−log2|E|! Qei∈Enr |ei|! where |ei|= number of times that example ei is in E (4.3) The problem is just the term log2|E|! Qei∈Enr |ei|! . If we have for instance this evidence: 500 # p(0). 300 # q(1). 100 # r(2). where we have a total of 900 examples (many of them repeated), let us see what happens when we estimate the problematic term using inside Yap Prolog using the normal operators: log2 |E|! Qei∈Enr |ei|!!= log2|900|! 500! 300! 100!= log2 7.7105 101980 1.220 101134 300! 100!! (4.4) The real representation of these big numbers is as integer values, but when the compiler tries to calculate the division, we obtain an innite result. We renounce to solve this problem for any example le with more than around seven hundred examples inside. We will solve the problem for a range between two hundred and seven hundred examples. Also, we will issue an error whenever the maximum value is exceeded. We will proceed as follows. In all the evidence sets, the fraction that causes the problem has a factorial in the numerator that could be simplied: since always a < b a! b!=a...b for instance 15! 10! = 15 14 13 12 11 = 360360 (4.5) The other thing we are going to do is to apply at the same time the multiplications for the factorial in the denominator and in the denominator, inside the recursive function: a! b!= factorial(a,b) =a b factorial(a-1,b-1) Both techniques together give us the possibility of having a big numerator before applying the division by a big denominator, making a division each time we apply a multiplication, and also simplifying the operations. 62 CHAPTER 4. THE TOOL 4.5 About the cost of stochastic programs When the tool determines the cost of the probabilities of each rule in a stochastic program, by default it only codes the probabilities of the necessary clauses, since probabilities are assumed to be normalized. This is the coding explained in the previous chapter 3.1, but there are also two more possibilities that are available in the tool using the modier rulesprob=x . With an example it will be easier to understand the dierences between them. If we have this simple program: 0.5 :: p(X):-X>0,q(X). [1] 0.5 :: p(X):-X<0,r(X). [2] 1 :: q(3). [3] The three options are: • The default behavior, in which we only sum up the cost of the probabilities of the necessary clauses (without any option, or using the command-line modier rulesprob=zerobitslast ). We will code the probability 0.5 of rule [1] only (the probability 0.5 of rule [2] is unnecessary because it is the last rule of p/1 . Also, the probability of rule [3] is not necessary because it is 1 . • Using the criterion of ignoring only the probabilistic cost of the last rule of each predicate ( rulesprob=notlast ), we will sum up [1] and [2] , even if q/1 has a probability of 1 . • Using the option to code every probability ( rulesprob=all ), then the three probabilities of the rules will be summed up. 4.6 The treatment of the knowledge base As we have described in section 3.1.5, the knowledge base is not really part of the model we want to analyze, and since this previous knowledge is shared between sender and receiver, we do not need to transfer it. But there are some situations in which maybe the user will nd it easier to have a set of common code for dierent models. The common code could then be seen as the knowledge base, and the dierent models as the programs. The tool will then estimate the cost of the common code as the knowledge base, and it will report it in the results separately. This option is enabled with the command-line option kb=files . The tool will check that no rule in the knowledge base will appear also dened with the same predicate name in the program (and the same in the other direction). Chapter 5 Examples In order to see this work in practice, we will give some examples where we will apply the MML coding to evaluate and compare several theories using our tool. We are going to include three small examples in this chapter. The chapter starts addressing the classical well known problem of animal classication, using dierent theories, and we will use the tool to compare them and select which one is the most optimal (in terms of the MML principle). There is a second example where we address a language analysis problem and the possibility of using the MML principle to identify the authorship of a document by determining the model of how a user uses that language. Finally, the last example also shows the use of probabilities: a probabilistic graph, and a closer look at how the tool works. 5.1 Animal classication This classical logical problem involving classication of animals was rst used in 1985 by Winston and Horn [59], and it is a well-known example in ILP. We have eight known attributes of animals, here shown as mode declarations used in Progol: has_milk(+animal). has_gills(+animal). has_eggs(+animal). has_gills(+animal). habitat(+animal ,#habitat). has_legs(+animal ,#nat). homeothermic(+animal). has_covering(+animal ,#covering). 63 70 CHAPTER 5. EXAMPLES So, if we recalculate after the removal of the positive examples, the results are these 2 : Model Base Model Model 1 Model 2 Model 3 Model 4 modied modied Total cost 1402.42929 1358.30051 1290.35762 1373.40119 1381.12335 Program 128.95529 101.50541 79.32713 111.70902 121.91262 Rules 5.33789 4.51929 3.76870 4.51929 4.51929 Lexicon 21.18376 21.18376 21.18376 21.18376 21.18376 Heads 54.72518 39.81679 29.86259 39.81679 39.81679 Bodies 47.70847 35.98557 24.51208 46.18917 56.39278 Vars 0.00000 0.00000 0.00000 0.00000 0.00000 Examples 144.47527 127.79637 82.03176 132.69345 130.21200 Knowledge Base 1128.99873 1128.99873 1128.99873 1128.99873 1128.99873 No. of E+ covered 16/16 16/16 11/16 15/16 14/16 No. of E− covered 0/42 2/42 0/42 0/42 0/42 Accuracy 58/58 56/58 53/58 57/58 56/58 100.00% 96.55% 91.38% 98.28% 96.55% Table 5.2: Comparison of cost between models covering almost the evidence With this data, the best model now seems to be the modied Model 2, with less cost and only a few less accuracy. And this decision has been possible easily due to this MML tool we are explaining here. 5.2 Language analysis: speaker recognition Another area in which the MML tool could help to decide between models is language analysis. In this area, a model that ts data perfectly is not possible, so in the majority of situations an approximate model is used. Approximate models may have dierent accuracies and complexities. Generating a language model from scratch is dicult and time-consuming. However, if we already have a general model, we can specialize it to several contexts. In general, if we can determine the frequencies of each rule from evidence, we would be able to transform a non-stochastic model (with only rules) into a stochastic one (with probabilities attached to the rules). This will help us (applying the MML tool) to identify which pattern (another set of examples) corresponds to which theory (language or theory). The example we are going to show is about speeches. If we can generate a model from dierent speeches, and we have dierent frequencies of each rule in the model for several speakers, we could apply the tool to determine to which speaker another speech corresponds. The new speech will t better 2 Same as we had in Table 5.1: the cost of evidence are not ∞ in our tool but 83.54547 for Model 1, 56.78051 for Model 2 and 92.44255 for Model 3. But in accordance with the MML principle, the negative examples covered must cost innite. 5.2. Language analysis: speaker recognition 71 in terms of cost with the previous calculated model of that speaker. The reason is that each person tends to use some particular type of sentences and vocabulary, so even if the language is the same, analyzing the number of occurrences of each type of sentence or specic words in a text could guide us to recognize the speaker. Our purpose is to analyze syntactically the sentences, obtaining the whole syntax of each individual sentence. Even though it was not the purpose of this thesis to develop a whole parser able to recognize the English language or a dierent one, a basic analyzer has been developed using Prolog, whose code is available in Appendix E.1. We explain the basics of the parser below. 5.2.1 English language parser Our parser is based on a Denite Clause Grammar (DCG). The DCG notation was developed as the result of research in natural language parsing in 1980 by Fernando Pereira and David Warren [15], and it is widely used in Prolog for language parsing. We have also used a DCG to analyze the Prolog source code. DCGs are closely related to the concept of attribute grammars from which Prolog was originally developed, and usually they are identied only with Prolog. They represent a grammar as a set of denite clauses in rst-order logic from which we derive the language: sentence --> noun_phrase,verb_phrase. noun_phrase --> det,noun. verb_phrase --> verb ,noun_phrase. det --> [the]. noun --> [cat]. verb --> [eats]. In the past the use of Prolog in natural language processing (NLP) was common [42], but nowadays the research in this area is focused on other languages and tools, like NLTK [3]. Despite this, we have decided to use a top-down parser in Prolog because we prefer to obtain the models to use in our MML tool directly in the Prolog language. The parser is specially constructed to avoid being left-recursive, because Prolog will go into an innite loop on left-recursive grammars. The state of the art with NLP demonstrates that language analysis is still a big problem, so our capacity of recognition is less than the third of the total amount of sentences with this parser. But it could be considered rather well for this example and our purpose. The process we have followed to obtain models from speeches using a DCG can be depicted in Figure 5.1 and goes as follows: • First, we introduce a speech in the English language into language.pl , a tool which converts the input stream into a list of sentences suitable 72 CHAPTER 5. EXAMPLES To be or not to be, that is the question: Wheter ‘tis Nobler in the mind to suffer speech [to,be,or,not,to,be] [that,is,the,question] [wheter,\’tis,nobler,…] sentences stochastic models sentence(np(prep,verb),conj,s…) sentence(np(prep),vp(verb)…) sentence(np(prep,verb),conj,s…) prep.verb. conj. verb.verb... to.be.or.not.to. be... 0.255 :: sentence(np(prep,verb),conj,s…). 0.532 :: sentence(np(prep),vp(verb)…). ... 0.255 :: lex(prep). 0.532 :: lex(verb). 0.255 :: lex(noun). ... 0.055 :: word(be). 0.015 :: word(i). 0.011 :: word(to). ... language.pl grammar.pl filter.sh (awk) tokens.pl wordnet.pl Irregulars.pl syntactic model lexical model word model models Figure 5.1: Developed parser for language processing for Prolog syntax. Each sentence is also a list of words, transformed into Prolog terms. • Then, the same language.pl program loads the DCG to analyze the sentences from grammar.pl and tries to obtain the syntactic equivalence for this sentence: ?s([my,tailor ,is,rich],X) X=attributive_sentence(np(det(my),noun( tailor)), vp(verb(is),adj(rich)) ) The syntactic model of the speech is built using the syntactic equivalence of the recognized sentences. • Our DCG also uses the ANSI Prolog version of the WordNet database 3 in wordnet.pl , in order to recognize the nouns, verbs, adjectives and adverbs. The rest of lexical items of the English language are loaded 3 WordNet is a lexical database for the English language [33]. It groups English words into sets of synonyms called synsets , provides short, general denitions, and records the various semantic relations between these synonym sets. Our purpose with the WordNet database is only to have a dictionary of the English language. 5.2. Language analysis: speaker recognition 73 from tokens.pl (prepositions, determiners, etc) and from irregulars.pl (irregular verbs, which are not present in WordNet ). • The sentences from which we are not able to obtain its syntactic relationships are ignored (around two thirds of the total, according to the complexity of the speech). • Since our intention is to test the MML tool, we are also going to consider two extra dierent models of the speeches: rst, a model of the vocabulary used (named here word model). And second, a model of the lexicon of the speech (so a model of how many times a noun, a verb or another lexical item appears in the speech). These models are generated together with the syntactic one with language.pl using a dierent command line modier. • The results of language.pl are a collection of rules of the three different models, many of them repeated (two sentences with the same syntactic form will generate the same rule, and the same in the lexical model). We need then to apply some lters using tools like awk , uniq and sort to transform the results into a notation for the number of occurrences of each item (and also the item): $ ./language.pl | sort | uniq -c \ | grep -v "^$" | awk '{ print $1 " :: " $2 }' \ | sort -g -r 85 :: sentence(np(det,noun)),conj,noun),vp(verb,noun)) 53 :: sentence(np(det,noun)),vp(verb)) ... This is not yet a normalized stochastic logic model (the left numbers are not a percentage), but our MML tool is able to normalize this without our intervention, so these values are suitable as input of the MML tool. The DCG we have developed is able to manage armative, negative, interrogative and imperative sentences, with subordinated sentences also. Obviously it is not intended to cover a real speech, especially because the order in a sentence could be altered (increasing the diculty of recognizing the parts of the sentence) and also some parts could be missed (because they are assumed). Some techniques like gap threading have been applied to solve this, but it makes the DCG more complex. For example, these two real sentences from George Orwell's novel 1984 are really complex (they are represented in the Prolog syntax we are using): 74 CHAPTER 5. EXAMPLES [ [thirty,to,forty,group,!, yapped,a,piercing, female, voice], [was,only,a,bundle,of,blankets,that,she,was, carrying] ] The rst sentence has an incorrect order, so our DCG is not going to recognize it, and the second one has and assumed subject. To have them recognized, they must be rewritten like this: [ [a,piercing,female,voice,yapped,thirty,to,forty,group,!], [it,was,only,a,bundle,of,blankets,that,she,was,carrying] ] Then, the incorrect order of sentences is not going to be recognized by our parser. The use of gap techniques could solve that, since our intention is not really to develop a precise parser for the English language. Also, it is problematic with our DCG to recognize personal nouns. In order to avoid this, we will transform the speech to lowercase, and consider the personal nouns as simple nouns. Also, shorts forms like Ive are going to be expanded. Obama Speech Obama Speech Obama Speech Obama Speech Obama Speech Bush Speech Bush Speech Bush Speech Bush Speech Bush Speech 0.255 :: sentence(np(prep,verb),conj,s…) 0.532 :: sentence(np(prep),vp(verb)…) ... 0.155 :: sentence(np(prep,verb),conj,s…) 0.232 :: sentence(np(det,prep),vp(verb)…) ... ? Speech Obama Speech Obama Speech Bush Speech Bush Speech evidence program 1212 bits 1312 bits MML tool WordNet knowledge base Figure 5.2: Experiment with speeches 5.2.2 Experimenting with speeches With this parser and the MML tool, we are going to analyze some speeches of two American presidents: Barack Obama and George W. Bush (son). The decision of selecting them is because we consider the language used in the speeches rather modern and simple. 5.2. Language analysis: speaker recognition 75 We used some speeches of each president, extracted from the Internet: http://www.presidentialrhetoric.com/speeches http://obamaspeeches.com We will select ve of them to create the model and we will use three extra speeches as evidence. Applying the parser to the merge of the ve speeches will generate a unique model for each president, one for Obama and another for Bush. A unique syntactic model, but also unique lexical and word models. Applying the parser to each one of the three example speeches of each president we generate three syntactic models, three lexical and three for the words. If we apply the MML tool to the model of each president together with one of this evidence models, the most probable president that has produced this speech introduced as evidence is the one that should generate the lowest cost with the model as program. This is depicted in Figure 5.2 (in the gure, the evidence speech ts better as an Obama's speech, due to the lower cost of 1212 bits). We could include also wordnet.pl and tokens.pl as knowledge base in our analysis with the MML tool, but since it is the same to all of them, it is not going to give us any relevant information. It will only increase the cost and also the computational time necessary to compute the results, so we are going to ignore it. With the rst ve speeches of each president, we obtain these two syntax models of their language: % Bush syntactic model: 12 :: imperative_sentence(verb_phrase(verb,noun_phrase(noun))) 13 :: affirmative_sentence(noun_phrase(noun),verb_phrase(verb)) 3 :: imperative_sentence(verb_phrase(verb,noun_phrase(noun), prop_pred(prep,noun_phrase(det,noun)))) 3 :: imperative_sentence(verb_phrase(verb,noun_phrase(noun), prop_pred(prep,noun_phrase(noun)))) 4 :: affirmative_sentence(connector, affirmative_sentence(noun_phrase(noun), verb_phrase(verb(aux,verb,verb),noun_phrase(noun)))) 4 :: affirmative_sentence(noun_phrase(noun), verb_phrase(verb(aux,aux,verb))) 4 :: imperative_sentence(verb_phrase(verb)) 7 :: affirmative_sentence(noun_phrase(noun), verb_phrase(verb,noun_phrase(det,noun))) ... % Obama: 2 :: affirmative_sentence(noun_phrase(noun),verb_phrase( verb,noun_phrase(det,noun,prop_pred(prep, noun_phrase(noun))))) 76 CHAPTER 5. EXAMPLES 2 :: affirmative_sentence(noun_phrase(noun), verb_phrase(verb,noun_phrase(noun))) 2 :: affirmative_sentence(noun_phrase(noun), verb_phrase(verb(verb,prep), noun_phrase(det,noun))) 4 :: affirmative_sentence(noun_phrase(noun), verb_phrase(verb,noun_phrase(det,noun))) 4 :: imperative_sentence(verb_phrase(verb)) 8 :: affirmative_sentence(noun_phrase(noun), verb_phrase(verb)) ... The same with the models of the lexicon: % Bush lexical model: 460 :: lex(adj). 858 :: lex(adv). 681 :: lex(aux). 689 :: lex(connector). 2104 :: lex(det). 3423 :: lex(noun). 1906 :: lex(prep). 36 :: lex(qmark). 4017 :: lex(verb). 189 :: lex(wh). % Obama lexical model: 304 :: lex(adj). 862 :: lex(adv). 574 :: lex(aux). 535 :: lex(connector). 1914 :: lex(det). 2657 :: lex(noun). 1627 :: lex(prep). 24 :: lex(qmark). 3238 :: lex(verb). 219 :: lex(wh). And nally, a model of frequency of occurrence of each word in the speeches (we discard the words that appear less than ten times): % Bush word model: 33 :: word(would). 20 :: word(years). 5.2. Language analysis: speaker recognition 77 113 :: word(you). ... % Obama word model: 24 :: word(would). 17 :: word(years). 69 :: word(you). 10 :: word(young). 17 :: word(your). ... With all these models, it is now possible to analyze the other speeches we have (three of each president) to ask the MML tool to calculate the lengths of the coding, and discover the attribution to a president. In the results, we provide the cost in bits obtained from the MML tool only for the evidence, because the cost of transferring the model is not relevant for the comparison we want to make here. Remember that in the attribution to a president, the one with the most reduced value is the one that ts best: Examples Bush Obama Speech Obama #1 8 79.19680 77.11631 Speech Obama #2 3 33.44175 26.90248 Speech Obama #3 2 22.47810 17.89818 Speech Bush #1 9 66.26869 66.66219 Speech Bush #2 3 26.96017 28.22441 Speech Bush #3 2 15.23098 17.20021 Table 5.3: Cost in bits of the syntax models With respect to the syntax models shown in the Table 5.3, the few number of recognized sentences in the speeches (around a quarter of the total) makes that in our comparison, the values are rather similar (in the rst model of Bush, the dierence is less than a bit). But in all the situations, the MML tool has been able to identify the correct author of the speech. Examples Bush Obama Speech Obama #1 440 424.25036 423.02164 Speech Obama #2 501 640.18616 635.88235 Speech Obama #3 822 1281.44781 1281.29256 Speech Bush #1 1848 4272.77811 4286.86068 Speech Bush #2 2031 4884.13975 4900.03561 Speech Bush #3 1031 2094.55003 2105.75096 Table 5.4: Cost in bits of the lexicon models Our second perspective, focused on identifying the authority of the speech attending to the lexicon that the speech has, is shown in Table 5.3. Here 78 CHAPTER 5. EXAMPLES the amount of examples is huge because we have used all words, not only the ones from the recognized sentences. The alignment to the right speaker is correct, although in some cases the margin is small. Examples Bush Obama Speech Obama #1 609 1879.75577 1766.46546 Speech Obama #2 1423 5558.68996 5973.74698 Speech Obama #3 2765 11597.30464 10969.02078 Speech Bush #1 1323 4938.43965 6107.28398 Speech Bush #2 1298 5386.01222 5124.47835 Speech Bush #3 2886 13548.21633 12468.35593 Table 5.5: Cost in bits of the word models And nally, in the analysis of the word models in Table 5.5, we have determined three mismatches that shown that the model based in the frequency of words is not a good classier of the speeches. This may be because there might be speeches which are thematic or address some specic issues, which makes them align better with speeches from other speakers. In any case, from the number in the three tables, we can say which speeches are more distinctively Obama-like or Bush-like. Overall, this example shows how a representation of natural language text patterns in the form of stochastic logic programs can be used for model selection. 5.3 A probabilistic graph We are going to use an example extracted from ProbLog [9] to illustrate how the tool works, instead of using it for comparing theories (section 5.1) or evidences (section 5.2). Also this example is going to show the limitations of the developed tool. The example is available for testing ProbLog on the website of the University of Lovaine (http://dtai.cs.kuleuven.be/problog): Listing 5.10: A probabilistic program %% :- use_module(library(problog)). % probabilistic facts 0.9::dir_edge(1,2). 0.8::dir_edge(2,3). 0.6::dir_edge(3,4). 0.7::dir_edge(1,6). 0.5::dir_edge(2,6). 0.4::dir_edge(6,5). 0.7::dir_edge(5,3). 0.2::dir_edge(5,4). % Now comes the background knowledge 5.3. A probabilistic graph 79 % definition of acyclic path using list of visited nodes path(X,Y) :- path(X,Y,[X],_). path(X,X,A,A). path(X,Y,A,R) :- X\==Y, edge(X,Z), absent(Z,A), path(Z,Y,[Z|A],R). % using directed edges in both directions edge(X,Y) :- dir_edge(Y,X). edge(X,Y) :- dir_edge(X,Y). % checking whether node hasn't been visited before absent(_,[]). absent(X,[Y|Z]):-X\= Y,absent(X,Z). In Figure 5.3 it is drawn the network representing the reachability of the nodes of this simple program. So simple that is going to cause a failure in the tool when we look for successful derivations of predicate edge/2 . The reason lies in the predicate absent/2 , whose second rule contains an inequality that blocks the Vanilla meta-interpreter to obtain the successful subgoals. This happens only in our solver (used to estimate the probability of predicate absent/2 ), because we have variables without assignations, and it is not the same to compare two values when Prolog solves the predicate (for instance: 1 1 ), than to compare the meta-interpreter a value and a variable ( X 1 ). Although the MML tool cans obtain the cost of the rules, if we analyze it together with the evidence, no one of the examples in the evidence will success for our Vanilla meta-interpreter. So to continue with this analysis, we are going to dene the predicate absent/2 in an extensional way (the purpose of the predicate is to check whether node has not been visited before, and then, it is not present in the list of the second argument): absent(1,[2]). absent(1,[5]). absent(1,[6,5]). absent(2,[1]). absent(2,[1,6,5]). absent(2,[5]). absent(2,[6,5]). absent(3,[1,]). absent(3,[1,2]). absent(3,[1,6,5]). absent(3,[2]). absent(3,[2,1]). absent(3,[2,1,6,5]). absent(3,[5]). absent(3,[5,6,1,2]). absent(3,[6,1,2]). 86 CHAPTER 5. EXAMPLES edge(5,_875386):-dir_edge(_875386,5). (prob :0.04167) dir_edge(6,5). (prob:0.08333) Fourth block 182 tesis/examples/prob2.pl +examples:tesis/examples/examples.prob.pl 183 Total cost: 1019.48514 bits 184 Cost of program: 441.53204 bits 185 Cost of 15 rules: 8.36748 bits 186 Cost of lexicon: 25.66265 bits 187 of 5predicates [absent/2,edge/2,path/4,path/2,dir_edge/2] 188 and 6function symbols [1/0,2/0,3/0,4/0,5/0,6/0] 189 Cost of heads: 117.35825 bits 190 Cost of bodies: 104.76314 bits 191 Cost of vars: 68.02227 bits 192 Probabilistic cost: 500.21824 bits 193 Cost of 8examples: 77.73486 bits And nally the last block, where we obtain the cost in bits. If there were also function symbols, they would appear also. This last block is the only part of the output that was not originally preceded by double dash, because is the normal output returned when the debugging is not used. Chapter 6 Conclusions and future work 6.1 Conclusions The general objective has been achieved: We have developed a MML coding scheme for non-stochastic and stochastic logic programs and a tool implementing it. With regard to the specic objectives: • After reviewing the state of the art about the MML principle, we have introduced some changes in the way that the cost is calculated in [23]: the formula used to code the signature is dierent, and now it is also more clear when the probability of a rule needs to be coded and when not. The problem with the cost of the signature was related to the correction term for the relevance of the order (otherwise it could generate negative results for large signatures). • The objective of developing a tool has these ve achieved subgoals:  An interpreter of a logic language (Yap Prolog) has been selected to do the implementation.  After reviewing dierent ways to implement the probabilities, we have selected the most clear to the end user, the one used in ProbLog.  The extension of Yap Prolog to manage the probabilities has also been done.  The tool is able to manage probabilities.  The tool is also able to insert the number of repetitions in the examples, to avoid these repetitions in the input le. • The tool has been tested using dierent scenarios, some of them explained in this document. We have shown how it can be used for 87 88 CHAPTER 6. CONCLUSIONS AND FUTURE WORK model selection, as in the animal example, by calculating Cost(T) + Cost(E|T) . We have also seen how to use to just calculate Cost(E|T) in the language example. This problem contains innite minimal models and many examples, and the evidence has repetitions. Finally, we have shown how complex programs are dealt with the last example (probabilistic graph). Note that only the rst problem can be handled by the MC and PC approaches. All this shows how the tool can be applied to many dierent scenarios and applications. There is a suite of examples available on the Web page and also in the distributed code. During the developing of the tool, dierent particularities and problems have appeared that have aected the process. The major part of those problems was related to the limitations that the use of a particular Prolog compiler introduces: the user programs to be analyzed are also loaded in the Prolog compiler, so their access without any limitation or modication has been a bit dicult many times. 6.2 Future work The implementation done has not covered all the options in [23]: there are other possibly more ecient coding schemes for programs without repeated examples and also for programs with a huge amount of repetitions. The tool works only in a specic platform of Prolog, the Yap compiler. The reason is the interaction with the user and the I/O, where each compiler uses dierent syntax, and also because there is not a standard way to manage large numbers with large precision. With some changes, it could be adapted to run with other compiler, like SICStus or SWI-Prolog. The work conducted is suitable for analyzing stochastic logic programs, as examples in sections 5.2 and 5.3, but there are also other dierent possibilities: • Estimate the best probabilities of a stochastic program where the initial values have been randomly (e.g. uniformly) assigned, by brute force. • Compare ILP platforms, if each dierent ILP tool (Progol, FOIL...) generates a dierent model from facts, our MML tool is able to determine the best one. Appendix A Coding numbers The cost of coding a number will depend on whether it is an integer or a real or a rational. In computer terminology, we usually refer to real numbers and rational numbers indistinctly, because real numbers are usually represented by oating point numbers, which are rational numbers in the end. In fact, we are going to approximate real numbers using rational numbers, because the cost of coding the probabilities is calculated from the rational approximation of the real number. A.1 Coding positive integers An integer number n > 0 is coded in binary form as a sequence of k binary digits, where k= (log2n)+1 . The rst digit of this string is 1 , but it is also necessary to use a prex code to distinguish them from other representations. The prex code used by Wallace [55] is suitable for this. He used a string corresponding to an integer n , which is obtained as the function head(n) followed by 0 , where head(n) is the following function to transform an integer to a binary representation: head(1) = Λ (an empty string) head(n) = head(k−1) followed by the k=dlog2(n)e digits of n, with n > 1 (A.1) In this case, the code string length is CodeLength(n) = length(head(n))+ 1 , and that is optimal and universal, as Wallace explained, because the expected string length required to encode an integer n selected from some nite-entropy distribution is nite using the CodeLength code, which means that the CodeLength code is feasible for this kind of distributions. The function CodeLength , as we have introduced in section 3.1, equals to: CodeLength(m) = log∗m+C (A.2) 89 90 APPENDIX A. CODING NUMBERS Where C= log2(2.8665064) is a normalization constant chosen to satisfy P∞ n=1 2−log∗n= 1 . Sometimes the authors use log∗ when they are speaking about CodeLength . We want to be distinguish those terms to avoid confusion. The iterated logarithm log∗ is the number of times the logarithm function must be iteratively applied before the result is less than or equal to 1, and it can be obtained using a recursive function: log∗(m) = (0 if m≤1 1 + log∗(log m) if m > 1 (A.3) Since this recursive denition is not optimal for eective calculations, we need to compute a feasible approximation to the value of log∗ for a certain n : for that, Rissanen [49] has suggested the following approximation to the log∗ function: log∗n= log2n+ log2log2n+ log2log2log2n (A.4) So, the coding cost of any integer value that we are going to apply in the toolkit will be: CodeLength(n) = log2n+ log2log2n+ log2log2log2n+. . . +C (A.5) A.2 Coding rational numbers As mentioned elsewhere, we use rational numbers for probabilities. Rational numbers can approximate a real number to any given precision (and this precision is going to be a modiable value in the toolkit), so there is no eective loss in generality if we assume that probabilities are represented as rational numbers. In particular, the following denitions will be used to code the probabilities of rules, which will be a rational number between 0 (excluded, because that rule then could be ignored) and 1 (higher values will be normalized, because they represent probabilities). Despite other coding systems which approximate real numbers, the chosen one is the one given by Dalgleish [7], in which the denominator of the rational number is the relevant part to estimate the cost of coding that number n/m , with n and m being natural numbers: Cost(n m) = CodeLength(m) + log2φ(m), where n > 0 m > 0 n≤m (A.6) A.2. Coding rational numbers 91 From the real number n m , we rst encode the denominator m , and then there are φ(m) choices for the numerator, where φ is the Euler's totient function. The Euler's totient φ(m) is the cardinality of the set of integers x such that it satises 1≤x < m and the greatest common divisor of x and m is 1. The rst term of the previous formula ( CodeLength ) codes only the denominator m using the technique described for integer numbers. Like the denominator cannot be 0, we do not have to add an extra bit here. To code the numerator n such that there are no common factors with m we must code only the Euler's totient. As example, the cost of coding the real number 0.33333 (approximated by the rational 1/3) is the cost of code CodeLength(3) + log 2 , since φ(3) = |{1,2}| = 2 . Appendix B A short introduction to Prolog The language used to develop the tool is Prolog, because it is per se the most suitable logic language to use: the major part of the examples and code interesting to use lately in the tool is available in this language, it is robust and mature. The name of the Prolog language comes from an abbreviation for programmation en logique , the French words for programming in logic. It is an old language created in 1972 by a group led by Alain Comerauer and Philippe Roussell in Marseille (France). It is a logic programming language and was rst associated with articial intelligence and computational linguistics. It was one of the rst logic programming languages created and nowadays remains among the most popular programming languages, at least in academics. The language is now used in many areas, such as: games, expert systems, automated answering systems and control systems. Prolog is said to be a declarative language, i.e., the logic is expressed by relations and the execution is done by calling queries over these relations (dened by clauses). The goal is to nd a resolution refutation of one negated query. If this negated query is refuted successfully then the query is set to false. Prolog allows the use of impure predicates for checking whether the value of a predicate may have some side eects, such as printing a value to the screen. But this is also one of the most important problems when programming in Prolog: since everything must be solved by resolution, the control the user input/output and the management of streams is a bit harder than with other language paradigms. B.1 Syntax of Prolog Prolog programs describe relations dened in a set of clauses: each clause has a head and a body (then is known as a rule) or only a head (and then is known as a fact). The head must have only a term, but in the body of the 93 94 APPENDIX B. A SHORT INTRODUCTION TO PROLOG rule we could form compound predicates by conjunction of terms (with the special predicate ,/2 ) or by disjunction of them (using the special predicate ;/2 ). Due to the relational nature of many built-in predicates, they can typically be used in several directions, so length/2 can be used to determine the length of a list ( length([a,b,c],X) ), but also to generate a list skeleton of a given length ( length(List,5) ), and also both things if the arguments are not assigned. The most elemental term is a constant. They are usually words written in Prolog code without any special syntax, although we must surrounded them by single quotes if it starts by capital letter or contain spaces or non-English symbols. Numbers can be oat or integer numbers, and in recent implementations of Yap Prolog (versions higher than 6.0), there is no a big limitation to precision if we have compiled it with the multi-precision library GMP, that is the common situation in the major part of packages available for Windows/Unix platforms nowadays. Variables are strings starting with a capital letter and followed by more letters, numbers and/or underscore characters. The single underscore is called an anonymous variable and it means any term. This type of variable does not represent the same value everywhere it occurs within a predicate denition. B.2 Programming with Prolog A Prolog program is a set of procedures (the order does not matter), each of them composed by one or more clauses (and here the order of the clauses is important, due to the evaluation of each of them is performed in a top-down fashion. The objective then is to describe relations using the clauses (facts or rules). A fact is a rule without any body, which could be considered equivalent to a rule with the only body true. A goal is the opposite concept: a rule without any head. Once the facts and rules are built it is possible to make queries to that knowledge (using goals), or modify them in the IDB 1 . The reasoning system that makes logical programming dierent to other paradigms is that it consists in unifying the rules we have introduced with the goals. The idea of unication in Prolog is close to the concept of matching . The Prolog compiler matches two terms if they are equal of if they contain variables that can be instantiated in such a way that the resulting terms 1 IDB is the Intensional DataBase of a Prolog compiler, where the rules from the program are stored. The other database is the EDB or Extensional Database, where the facts of the logic during execution are analyzed. B.2. Programming with Prolog 95 are equal. So the process of matching for the compiler generates a SLDresolution 2 with all the possible matches unifying the goal with the rules of the program by backtracking. This operational strategy needs to create a choice-point each time that multiple clause heads could match with a given call, store it, unify with the rst clause which has not used yet, and continue with that goal until it success or fails. If it fails in the course of executing the program (or if the user retries for more possibilities) then all variable bindings that were made since the most-recent choice-point with other clauses are undone, and Prolog follows with the next unused clause of that choice-point. This execution strategy is called chronological backtracking. The following example shows this: % lectures(X, Y): person X lectures in course Y lectures(turing , 9020). lectures(codd , 9311). lectures(backus , 9021). lectures(ritchie , 9201). lectures(minsky , 9414). lectures(codd , 9314). % studies(X, Y): person X studies in course Y studies(fred, 9020). studies(jack, 9311). studies(jill, 9314). studies(jill, 9414). studies(henry, 9414). studies(henry, 9314). % year(X, Y): person X is in year Y year(fred , 1). year(jack , 2). year(jill , 2). year(henry, 4). In order to illustrate what happens when Prolog tries to nd a solution and backtracks, we draw in Figure B.1 a proof tree with the goal: lectures(codd ,Course),studies(Student ,Course) where there are four derivations that are true (the bold lines) and many others that are false. The negation is implemented by the predicate +/1 , which drives Prolog to try to prove the goal without the negation. If a proof of that non-negated goal can be found, the original goal fails. If no proof can be found, then the original goal success. 2 Selective Linear Denite clause resolution 102 APPENDIX C. PROLOG INTERPRETERS AND PROBABILITIES Figure C.1: Aspect of Eclipse with ProDT plug-in Figure C.2: Aspect of Eclipse with PDT plug-in Also for the development of some specic les for the Website we describe later, we needed the Web Development Tools for Eclipse ( http://www. eclipse.org/webtools ), a more common and known plug-in for Eclipse. C.4. Restrictions 103 The other important tool, as said, it was an RCS. We will use Git ( http: //git-scm.com ): a distributed revision control and source code management system, created by Linus Torvalds for the Linux kernel development. It is distributed because each copy of the RCS data for control a directory of code is a full repository with complete history and tracking of the code, not dependent on network access or a central server. Since it is also distributed using the GNU license, it is very common nowadays over the well-known CVS and Subversion . The perfect partner for a RCS tool is a Web page that provides a repository to store a back-up or collaborate with others. Even though this second thing was unnecessary (there is no team when you are developing alone), an Assembla ( https://www.assembla.com ) repository has been used. The address of the repository is opened for access to consult the sources of the project (even though it was available at the same time in the Web page of the research group) in https://www.assembla.com/spaces/mml-cost/ new_items . The change set of the almost three hundred commits done to the source (including Prolog, PHP and also the same L A TEX generation of this document) can be viewed there. C.4 Restrictions Because this tool is written in Prolog, its use to analyze Prolog programs needs to set some limitations over the program syntax, due to the limitations of access to the predicates of the code introduced by the user. For instance, if some user wants to analyze a program, it is loaded as a module in Prolog, the loading introduces some special predicates ( mml_prob/1 , mml_rep/1 ...), and so the use of these words is not allowed in the user code. Another important limitation: if the user program has modules, the tool will not be able to analyze the code of these other modules. So, the use of modules is forbidden. As a result, by design, the tool is able to work only with programs introduced by the user that: • Do not use any predicate starting with the prex 'mml_' . • Do not use modules or dierent les. • Do not contain denitions of the same predicate in the knowledge base le and the program le. Appendix D User manual of the tool D.1 How to install the program The tool is distributed as Prolog source les, so no binary dependence of the platform or compilation is needed. The only requisite to run the tool is to have the Yap Prolog compiler previously installed, and to have it available in the path. Despite other Prolog compilers, Yap does not include some useful libraries by default, such the GMP library we are using in the tool. So, it is also important to install or compile Yap with this mathematical library. Without this library being active, the tool also will run, but when an operation overloads the machine (easily except for really simple programs), our tool will exit with an error. Inside the ZIP le there are two executables scripts, one for Windows with the extension BAT , and a shell script for Unix/Linux with no extension. These are the entry points to the tool and they must not be removed. D.2 Organization The code is divided in dierent les: ve of them are modules located in a subdirectory. This subdirectory with the modules and the other three les could be moved to any directory in a computer, if there is a Yap compiler available in the local execution path: This tool could be run on any platform compatible with Yap Prolog (Linux, Windows, Solaris, Mac OS X and HP-UX), but it has been tested only on Windows and Linux. In the main directory, the purpose of the mml_cost and mml_cost.bat les is only to provide the executables les needed to run the tool in both platforms, and mml_cost.yap is the entry point that manages the modules: • mml_cost : Shell script for Linux platforms: it calls mml_cost.yap . 105 106 APPENDIX D. USER MANUAL OF THE TOOL lib/ functions.yap code_load.yap cost_calculate.yap example_analyze.yap program_analyze.yap mml_cost.yap mml_cost mml_cost.bat • mml_cost.bat : Script for Microsoft platforms: it calls mml_cost.yap . • mml_cost.yap : Entry point to the tool. It loads the ve modules and it is in charge of answering the user with the results of the code, or to notice the errors. • lib/functions.yap : Math involved predicates, global modiers, print options. • lib/code_load.yap : It manages the loading of the user code. It also intercepts the special function predicates ::/2 and #/2 to transform them, removing also non-desired predicates involved with debugging. • lib/program_analyze.yap : It obtains the body of all the clauses of the program and processes them (determining the number of variables, number and type of symbols, etc). • lib/cost_calculate.yap : It determines the cost of the user code already loaded as modules and previously tokenized. • lib/example_analyze.yap : It transforms and analyzes the user example les, in a similar way to the lib/cost_calculate.yap , but considering only the evidence (it also detects and fails when a body of a clause is found). In any Microsoft/Linux platform, the behavior of the tool is exactly the same: the Yap Prolog compiler is the responsible of transforming the calls to les in order to t the specic platform format, so there is no necessity to use dierent code in dierent platforms. D.2. Organization 107 Rather dierent is the behavior of the tool depending of which version of Yap Prolog we are going to use: the stable version used in many Linux distributions (Debian, Ubuntu...) is still Yap Prolog 5, instead of Yap Prolog 6. The old one does not have the predened predicates between/3 and is_list/3 . This problem is detected when we load the code and solved declaring them in functions.yap , but there is a more important dierence that aects the precision of integer and oat calculations: only in Yap Prolog 6 can we have the precision library GMP attached when the code is compiled, and this library is compulsory to make calculations that clearly aect the results (if we have a probability of 0.0019, the result of cost will be hugely dierent from a probability of 0.002). To avoid problems with this lack of precision, the functions.yap will halt when max_precision value (a Yap Prolog ag) is not enough to make mathematical calculations. When we call the program without using any modier, the tool will fail indicating that you need to call the program with at least one user code le (as a program le) to analyze. It is possible to run the program directly reading from the standard input using the special modier  , in this way: $ echo -e "p(0,1).\np(_,_)." | ./mml_cost -- The modiers will start always with a double dash and the others arguments without them will be considered as les to load as user program code: $ mml_cost --help It determines the MML cost of a Prolog program Arguments: --examples=e1,e2... Files with the examples as clauses --kb=kb1,kb2... Files with the knowledge base --debug Detailed evaluation process --warnings=off With 'on', warnings issued by Prolog also abort the execution of the tool --precision=0.00001 Maximum error allowed in operations You can also use num. of digits (<=15) --dialect=cprolog Dialect type: cprolog,iso,sicstus --predefined Show the cost of predef predicates and numbers --normalize=on Normalize to 1 the sum of probs with same predicate ('off' to disable) --rulesprob=zerobitslast Treatment done to probs of rules: -zerobitslast: Only the relevant (def) 108 APPENDIX D. USER MANUAL OF THE TOOL -notlast: The last rule prob is ignored -all: All of them --tabled Show summarized results --maxrecursion=20 Max SLD-resolution derivations [file1.pl..fileN.pl] At least one file with a prolog program (-- for stdin) You can use '::' to indicate the probability of a clause: 0.25 :: f(X,Y):-X>0,Y is 3. And also '#' in the examples to indicate the repetitions: 32 # f(0,1). ~> Like writing f(0,1) 32 times So the usual way to call the program will be this (we could omit the examples or the Knowledge Base le): $ mml_cost program_code.pl --examples=example_code.pl \ --kb=kb_file.pl This will produce an answer from the tool in which it sums up all the costs, separated by each part: program_code.pl + example_code.pl + kb_file.pl Total cost: 106.91945 bits Cost of program: 106.91945 bits Cost of 5 rules: 5.33713 bits Cost of lexicon: 25.66446 bits of 3 predicates [sum/3,pos/1,even/1] and 2 function symbols [0/0,s/1] Cost of heads: 24.92481 bits Cost of bodies: 31.10245 bits Cost of vars: 19.89060 bits If we need to use more les, we must consider that the cost results will be calculated for each combination of program code and example code. This is applicable to programs and examples, but not to knowledge base (KB). If we indicate more than a KB le, all of the KB les will be merged, so when we call the tool as this: $ mml_cost p1.pl p2.pl --examples=e1.pl,e2.pl \ --kb=kb1.pl,kb2.pl That is exactly the same as calling the program in this way: $ mml_cost p1.pl --examples=e1.pl --examples=e2.pl \ --kb=kb1.pl --kb=kb2.pl p2.pl D.3. Modiers 109 The same type of results as we have seen in the previous example will be produced, but now it will be repeated four times: p1-e1 , p1-e2 , p2-e1 and p2-e2 . Taking into account that we have called the program with two program les and two example les, so we must take care that the example les have examples that match with both desired program les. D.3 Modiers Since there are many modiers (parameters) available from command line, it is necessary to explain which the purpose of each of them is, and explain which the default values are when we do not indicate one: • examples : It accepts the le (or les separated by comma) containing the evidence of the program to analyze. • kb : It accepts the KB le or les separated by comma to load. KB is code which is not present in the same user program code but is required by it. It will be treated separately. Notice that the predened predicates (part of ISO Prolog and also the specic of Yap Prolog) are ignored and are not the same as the KB. Also notice that any other symbol that appears in the code that is not dened in the KB, in the user program or predened in Prolog, will be considered a symbol function. • debug : Detailed evaluation process, where you could see the solving process performed with the evidence, or also the normalization done to the clauses of the programs. • warnings : Its default value is 'o'. By switching it to 'on', warnings abort the execution of the program. For example, if you introduce a variable which is not assigned, the Prolog compiler will issue a warning that in the normal behavior, is ignored. If you activate this modier, then the tool will exit abnormally. • precision : By default the value is 0.00001 (5 digits). This it will be used as a resolution in the output of oat values and also (and this is more important) as the maximum error allowed for a rational number. So, with precision 0.0001: 0.3333 *1 3 but 0.333 *333 1000 You can also use the amount of digits you want (i.e., 6 instead of 0.000001). The maximum resolution allowed by Yap Prolog numeric library GMP is 15 (so 1/1015 ). 110 APPENDIX D. USER MANUAL OF THE TOOL • dialect : The Yap Prolog developers decided to allow for a change between the specic syntax of CProlog, SICStus and ISO Prolog (ISO/IEC 13211-1)). By default, the dialect used is CProlog, but there is the possibility to change to the two others. The most important consideration about the dialects is the incompatibility between SICStus dialect and the use of evidence ( examples , due to the impossibility of modifying code). • predefined : Shows the cost of the predened predicates in Prolog: without this modier, they are ignored, and the same applies to numbers. These are the predicates like write/1 , nl/0 , is/2 ... For instance, if we have this program: p(X):-X is 3+2+r(a)+s(0),write(0),nl. Without this modier, the tool reports that the signature is formed by the function symbols {a/0,s/1} and the predicate symbols {p/1,r/1} . With the modier, we obtain new function symbols: {a/0,s/1,3/0,2/0,0/0} and the predicate symbols will be: {p/1,r/1,+/2,is/2,write/1,nl/0} . • normalize : By default, we normalize the sum of probabilities of rules with same predicate to make them 1. This could be disabled by using the off value with this modier. Let us see rst what the normalization implies. If we have this as the whole program: 0.3 :: p(0,X):-X > 0. 0.3 :: p(1,X):-X < 0. Since the sum of both probabilities is less than 1, the code will be transformed into: 0.5 :: p(0,X):-X > 0. 0.5 :: p(1,X):-X < 0. And the same probability of 0.5 will be assigned in this other one situation (even though is >1, we could deduce that each clause must have a probability of 0.5): 1 :: p(0,X):-X > 0. 1 :: p(1,X):-X < 0. D.3. Modiers 111 When there are clauses without probability (but at least one has probability, otherwise the program will not be considered as a stochastic one), then the tool also deduces the probabilities which are not present by assuming a uniform distribution: 0.6 :: p(0,X):-X > 0. p(1,X):-X < 0. % --> prob. will be 0.2 p(3,0). % --> prob. will be 0.2 Then if we disable the normalization using this modier, the tool will fail for any of these examples: whenever there is one clause without probability, the sum of them is not 1, etc. 0.8 :: p(a). 0.1 :: p(b). 0.4 :: q(a). q(b). q(c). r(a). * 0.8888 :: p(a). 0.1111 :: p(b). 0.4 :: q(a). 0.3 :: q(b). 0.3 :: q(c). 1 :: r(a). Figure D.1: Example of normalization (left not normalized, right normalized) • rulesprob : Another important modier is this involved with the treatment applied to the clauses. Using the Example we are going to explain the dierences between the three possible treatments:  Value notlast : The last rule probability of each dierent predicate is not code, since it can be inferred from the rest because probabilities are assumed to be normalized. So, in this situation (Figure , right), we will code 0.8888 , 0.4 and 0.3 , adding an extra bit for each one of the predicates.  Value all : All of them are considered (for this example, the six probabilities).  Value zerobitslast : Only the relevant clauses are considered for evaluating the cost, so in this situation we will only code 0.8888 , 0.4 and 0.3 , but without the addition of an extra bit per predicate. This is the default behavior. • tabled : Instead of showing the results as we have seen, they are returned as a tabular list. This option will generate this as output of an execution: ;ej4+exampl+kb;Total;Program;CRule,CLexicon;NP;NF;CHeads; 118 APPENDIX E. SOURCE CODE OF EXAMPLE SPEAKER RECOGNITION processArgs( [ Argument |RestArgs ], Files ,Acc ):- (name(Argument,"--syntax" ),set_value(mode,syntax ) ; name(Argument,"--lexicon" ),set_value(mode ,lexicon ) ; name(Argument,"--word" ),set_value(mode ,word ) ; name(Argument,"--np" ),set_value(onlynp ,yes ) ; name(Argument,"--nowarnings" ),set_value(warnings,no ) ), processArgs(RestArgs,Files,Acc ). processArgs( [ Argument |RestArgs ], Files ,Acc ):- verifyFile(Argument), processArgs(RestArgs,Files, [Argument|Acc] ). processArgs( [], Files,Files ). % if the file doesn't exists , or is not readable , we exit with error : verifyFile(File ):- file_exists(File , 4 ),! ; exists(File ),!, showError('Error: File not readable: ''~p''~n',[File]), halt(1) ; File == '-?',helpMessage ; File == '-h',helpMessage ; showError('Error: File not found: ''~p''~n',[File]), halt(1). helpMessage :- nl,write(' Basic analysis of speech'),nl, write(' --syntax (by default) | --lexicon | --word'),nl, write(' --np (also accept the noun_phrase without verbs'),nl, write(' [file1..fileN] Files to analyze together'),nl, write(' '),nl, write(' The content of the file must be English sentences divided'),nl, write(' by dots. Non-English characters are forbidden.'),nl, write(' Last line of each file must be an empty line or its content'),nl, write(' will be ignored'),nl,nl. transform1 ([],[]). % list of sentences transform1([Elem|List],[Elem1|List1]):- transform2(Elem,Elem1), transform1(List,List1). transform2 ([],[]). % sentence = list of words transform2([Elem|List],[Elem1|List1]):- name(Elem1,Elem), % word transform2(List,List1). executeProgram( [], Result1 ,_):-transform1(Result1,Result2), analyzeSentences(Result2) ,!. E.1. Language analysis: source code 119 executeProgram( [File|FileList], Acum ,Output ):- open(File ,'read',Stream), % A sentence not ended in a file is considered ended , so a final '.' is % supposed: readLines(Stream , [], Acum ,NewAcum ), close(Stream), executeProgram(FileList,NewAcum,Output ). readLines(Stream ,CurrentSentence,SentencesIn,Result ):- % Acum = [current sentece] % Input = [previous sentences] % Output = <result > (% When this first predicate fails , we have ended: read_line_to_codes(Stream ,ThisLine),!, (ThisLine==end_of_file,!, (CurrentSentence==[],!, Result=SentencesIn ; append(SentencesIn,CurrentSentence,Result ) ) ; processLine(ThisLine, [], CurrentSentence,NewCurrentSentence, SentencesIn,SentencesOut ), readLines(Stream ,NewCurrentSentence ,SentencesOut,Result ) ) ; (CurrentSentence==[],!, Result=SentencesIn ; append(SentencesIn,CurrentSentence,Result ) ) ). % We have ended the line , so we output the results to readLines /4: processLine( [], Word ,CurrentSentence,NewCurrentSentence, Sentences,Sentences ):- Word\==[],!, append(CurrentSentence,[Word],NewCurrentSentence ) ; NewCurrentSentence=CurrentSentence. % New sentence (.), we exclude empty words and empy sentences: processLine( [46|List],Word , CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- (Word\==[],!, append(CurrentSentence,[Word],NewSentence) ; NewSentence =CurrentSentence ), (NewSentence \== [],!, append(SentencesIn,[NewSentence],NewSentencesIn) ; NewSentencesIn =SentencesIn ), processLine(List , [], [], FinalPendentSentence , NewSentencesIn,SentencesOut ). 120 APPENDIX E. SOURCE CODE OF EXAMPLE SPEAKER RECOGNITION % Question mark , so a new sentence also: processLine( [63|List],Word , CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- (Word\==[],!, append(CurrentSentence,[Word],NewSentence) ; NewSentence =CurrentSentence ), (NewSentence \== [],!, append(NewSentence,[[63]],NewSentence1 ), append(SentencesIn,[NewSentence1],NewSentencesIn) ; NewSentencesIn =SentencesIn ), processLine(List , [], [], FinalPendentSentence , NewSentencesIn,SentencesOut ). % hyphen also a new word: processLine( [45|List],Word , CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- (Word\==[],!, append(CurrentSentence,[Word],NewSentence) ; NewSentence =CurrentSentence ), (NewSentence \== [],!, append(SentencesIn,[NewSentence],NewSentencesIn) ; NewSentencesIn =SentencesIn ), processLine(List , [], [], FinalPendentSentence , NewSentencesIn,SentencesOut ). % same with ; or : processLine( [58|List],Word , CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- (Word\==[],!, append(CurrentSentence,[Word],NewSentence) ; NewSentence =CurrentSentence ), (NewSentence \== [],!, append(SentencesIn,[NewSentence],NewSentencesIn) ; NewSentencesIn =SentencesIn ), processLine(List , [], [], FinalPendentSentence , NewSentencesIn,SentencesOut ). processLine( [59|List],Word , CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- (Word\==[],!, append(CurrentSentence,[Word],NewSentence) ; NewSentence =CurrentSentence ), (NewSentence \== [],!, append(SentencesIn,[NewSentence],NewSentencesIn) E.1. Language analysis: source code 121 ; NewSentencesIn =SentencesIn ), processLine(List , [], [], FinalPendentSentence , NewSentencesIn,SentencesOut ). % New word, but we exclude empty words ( ) or (,): processLine( [32|List],[], CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- processLine(List , [], CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ). processLine( [32|List],Word ,CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- append(CurrentSentence,[Word],NewCurrentSentence), processLine(List , [], NewCurrentSentence ,FinalPendentSentence , SentencesIn,SentencesOut ). processLine( [44|List],Word ,CurrentSentence,FinalPendentSentence , SentencesIn,SentencesOut ):- append(CurrentSentence,[Word],NewCurrentSentence), processLine(List , [], NewCurrentSentence ,FinalPendentSentence , SentencesIn,SentencesOut ). % Any other thing , we add it to the current word: processLine( [Char|List],Word ,CurrentSentence,FinalPendentSentence ,SentencesIn,SentencesOut ):- (between(65,90,Char), % we lowercase the char always: NewChar is Char + 32 ; NewChar is Char ), append(Word,[NewChar],NewWord), processLine(List ,NewWord,CurrentSentence, FinalPendentSentence , SentencesIn,SentencesOut ). % [2] Speech analysis % -------------------------------------------------------- analyzeSentences(Sentences):- length(Sentences,X), set_value(counter ,0), analyzeSentences1(Sentences), (get_value(mode,syntax ),!, (get_value(warnings,yes ),!,write('% There are '),write(X), write(' sentences in the speech '),get_value(counter,Y), write('('),write(Y),write(' recognized)'),nl ; true ) ; get_value(mode,lexicon ),!, get_value(counter ,Y), (get_value(warnings,yes ),!, write('% There are '),write(Y),write(' tokens in the speech'), nl ; true ) ; get_value(counter ,Y), (get_value(warnings,yes ),!, 122 APPENDIX E. SOURCE CODE OF EXAMPLE SPEAKER RECOGNITION write('% There are '),write(Y),write(' words in the speech '), nl ; true ) ). analyzeSentences1([]). analyzeSentences1([Sentence|List]):- analyzeSentences2(Sentence), (get_value(mode ,syntax),!, (s(Sentence ,Result ), write(Result),write('.'),increment_counter,nl ; write('% '),write(Sentence),nl ) ; true ), analyzeSentences1(List). analyzeSentences2([]). analyzeSentences2([Word|Sentence]):- testWord(Word), analyzeSentences2(Sentence). increment_counter :- get_value(counter ,Value), Value1 is Value+1, set_value(counter ,Value1). % :-[tokens]. :-[grammar]. % we identify if the token is recognized by our system: testWord(Word):- % we use term_hash/2 to obtain an unique name that represents the word ,to avoid the % problem with word('?'),word('8th') and this kind of problems: (get_value(mode ,word),write('word('),term_hash(Word,X),write(X), write('). % '),write(Word),nl, increment_counter;true) , det([Word]) ,!, (get_value(mode ,lexicon),write('lex(det).'), increment_counter,nl;true) ; prep([Word]),!, (get_value(mode,lexicon),write('lex(prep).'), increment_counter,nl;true) ; wh([Word]),!, (get_value(mode ,lexicon),write('lex(wh).'), increment_counter,nl;true) ; qmark([Word]),!, (get_value(mode ,lexicon),write('lex(qmark).'), increment_counter,nl;true) ; prorel([Word]),!, (get_value(mode ,lexicon),write('lex(prorel).') ,increment_counter,nl;true) ; E.1. Language analysis: source code 123 aux([Word]) ,!, (get_value(mode ,lexicon),write('lex(aux).'), increment_counter,nl;true) ; connector([Word]) ,!,(get_value(mode ,lexicon),write('lex(connector) .'),increment_counter,nl;true) ; verb([Word]),!, (get_value(mode,lexicon),write('lex(verb).'), increment_counter,nl;true) ; adv([Word]) ,!, (get_value(mode ,lexicon),write('lex(adv).'), increment_counter,nl;true) ; noun([Word]),!, (get_value(mode,lexicon),write('lex(noun).'), increment_counter,nl;true) ; adj([Word]) ,!, (get_value(mode ,lexicon),write('lex(adj).'), increment_counter,nl;true) ; (get_value(warnings,yes ),!, write('% not recognized! '),write(Word),nl ; true ). % [3] Output the model % -------------------------------------------------------- % -------------------------------------------------------- % -------------------------------------------------------- :-initialization(main). 124 APPENDIX E. SOURCE CODE OF EXAMPLE SPEAKER RECOGNITION Listing E.2: DCG used in the parser % ----------------------------------------------- s(X,Y):- sentence(sentence(Z), X, [] ),!,transform(Z,Y) ; get_value(onlynp ,yes ),noun_phrase(Z,X,[]),transform(Z,Y). % ----------------------------------------------- sentence(sentence(X) ) --> affirmative_sentence(X) ; subject_interrogative_sentence(X) ; object_interrogative_sentence(X) ; imperative_sentence(X). imperative_sentence(imperative_sentence(S1,S2 ) ) --> adv_phrase(S1),verb_phrase(S2),!. imperative_sentence(imperative_sentence(S1 ) ) --> verb_phrase(S1),!. % they know what they are doing: affirmative_sentence(affirmative_sentence(S1,S2,S3,S4 ) ) --> noun_phrase(S1),verb1(S2),wh([S3]), affirmative_sentence(S4),!. affirmative_sentence(affirmative_sentence(S1,S2,S3 ) ) --> adv_phrase(S1),noun_phrase(S2), verb_phrase(S3 ),!. affirmative_sentence(affirmative_sentence(S1,S2,S3 ) ) --> noun_phrase(S1),verb_phrase(S2),adv_phrase(S3) ,!. affirmative_sentence(affirmative_sentence(S1,S2 ) ) --> noun_phrase(S1), verb_phrase(S2) ,!. affirmative_sentence(affirmative_sentence(S1,S2 ) ) --> connector([S1]),affirmative_sentence(S2) ,!. object_interrogative_sentence(object_interrogative_sentence(S1,S2, S3,S4,S5,S6 ) ) --> wh([S1]),aux([S2]),noun_phrase(S3),verb_phrase (S4),prep([S5]),qmark([S6]) ,!. % what progress will we have made? object_interrogative_sentence(object_interrogative_sentence(S1,S2, S3,S4,S5,S6 ) ) --> wh([S1]),noun([S2]),aux([S3]),noun_phrase(S4), verb_phrase(S5),qmark(S6),!. object_interrogative_sentence(object_interrogative_sentence(S1,S2, S3,S4,S5 ) ) --> wh([S1]),aux([S2]),noun_phrase(S3),verb_phrase (S4),qmark(S5) ,!. subject_interrogative_sentence(subject_interrogative_sentence(S1, S2,S3 ) ) --> wh([S1]),verb_phrase(S2),qmark([S3]) ,!. adv_phrase(adv_phrase(S1,S2 ) ) --> prep([S1]),noun_phrase(S2) ,!. adv_phrase(adv_phrase(S1 ) ) --> adv([S1]) ,!. % like we remove commas , the adjectives could appear as: "a tiny and marvellous" or E.1. Language analysis: source code 125 % also "a tiny , wonderful house": adj_compl(adj_compl(S1,S2,S3 ) ) --> adj([S1]),connector([S2]),adj ([S3]) ,!. adj_compl(adj_compl(S1,S2 ) ) --> adj([S1]),adj([S2]) ,!. adj_compl(adj_compl(S1,S2 ) ) --> adv([S1]),adj([S2]) ,!. % manner complement adj_compl(adj_compl(S1 ) ) --> adj([S1]) ,!. noun_phrase(noun_phrase(S1,S2,S3,S4,S5) ) --> det([S1]), adj_compl( S2),noun([S3]), connector([S4]), noun_phrase(S5) ,!. noun_phrase(noun_phrase(S1,S2,S3,S4) ) --> det([S1]), noun([S2]), connector([S3]), noun_phrase(S4),!. noun_phrase(noun_phrase(S1,S2,S3,S4) ) --> adj_compl(S1),noun([S2]) ,connector([S3]), noun_phrase(S4),!. noun_phrase(noun_phrase(S1,S2,S3) ) --> det([S1]), noun([S2]), prop_pred(S3),!. noun_phrase(noun_phrase(S1,S2,S3) ) --> adj_compl(S1), noun([S2]), prop_pred(S3),!. noun_phrase(noun_phrase(S1,S2,S3) ) --> det([S1]), adj_compl(S2), noun([S3]) ,!. noun_phrase(noun_phrase(S1,S2,S3) ) --> det([S1]), noun([S2]), rel_phrase(S3),!. noun_phrase(noun_phrase(S1,S2,S3) ) --> det([S1]), noun([S2]),noun ([S3]) ,!. noun_phrase(noun_phrase(S1,S2,S3) ) --> noun([S1]), connector([S2]) ,noun([S3]) ,!. noun_phrase(noun_phrase(S1,S2) ) --> det([S1]), noun([S2]) ,!. noun_phrase(noun_phrase(S1,S2) ) --> noun([S1]),prop_pred(S2),!. noun_phrase(noun_phrase(S1,S2) ) --> adj_compl(S1),noun([S2]) ,!. noun_phrase(noun_phrase(S1) ) --> noun([S1]) ,!. noun_phrase(noun_phrase(S1) ) --> adj_compl(S1),!. prop_pred(prop_pred(S1,S2) ) --> prep([S1]),noun_phrase(S2),!. prop_pred(prop_pred(S1,S2) ) --> prep([S1]),verb([S2]),noun_phrase( S3),!. % to reaffirm our situation rel_phrase(rel_phrase(S1,S2) ) --> prorel([S1]), affirmative_sentence(S2). rel_phrase(rel_phrase(S1,S2) ) --> prorel([S1]),verb_phrase(S2). % transitive: verb_phrase(verb_phrase(S1,S2,S3) ) --> verb1(S1),noun_phrase(S2), adv([S3]) ,!. verb_phrase(verb_phrase(S1,S2,S3) ) --> verb1(S1),noun_phrase(S2), prop_pred(S3),!. verb_phrase(verb_phrase(S1,S2,S3) ) --> verb1(S1),prop_pred(S2), noun_phrase(S3),!. % oi+od verb_phrase(verb_phrase(S1,S2,S3) ) --> verb1(S1),noun_phrase(S2), noun_phrase(S3),!. % oi+od, but oi without prep verb_phrase(verb_phrase(S1,S2,S3) ) --> verb1(S1),adj_compl(S2), prop_pred(S3),!. % attributive sentences verb_phrase(verb_phrase(S1,S2) ) --> verb1(S1),noun_phrase(S2),!. % intransitive: verb_phrase(verb_phrase(S1,S2) ) --> verb1(S1),adj_compl(S2) ,!. % attributive sentences 126 APPENDIX E. SOURCE CODE OF EXAMPLE SPEAKER RECOGNITION verb_phrase(verb_phrase(S1,S2) ) --> verb1(S1),adv([S2]) ,!. verb_phrase(verb_phrase(S1,S2) ) --> verb1(S1),prop_pred(S2) ,!. verb_phrase(verb_phrase(S1) ) --> verb1(S1) ,!. % negation: verb1(verb(S1,S2,S3 ) ) --> aux([S1]),aux([S2]),verb([S3]) ,!. verb1(verb(S1,S2,S3 ) ) --> aux([S1]),verb([S2]),verb([S3]) ,!. verb1(verb(S1,S2,S3 ) ) --> aux([S1]),adv([S2]),verb([S3]) ,!. % are now threated verb1(verb(S1,S2 ) ) --> aux([S1]),verb([S2]) ,!. verb1(verb(S1,S2 ) ) --> verb([S1]),prep([S2]) ,!. verb1(S1 ) --> verb([S1]) ,!. verb([verb(X)]) --> [X], {verb([X])}. det([det(X)]) --> [X], {det([X])}. noun([noun(X)]) --> [X], {noun([X])}. adj([adj(X)]) --> [X], {adj([X])}. adv([adv(X)]) --> [X], {adv([X])}. prep([prep(X)]) --> [X], {prep([X])}. wh([wh(X)]) --> [X], {wh([X])}. qmark([qmark(X)]) --> [X], {qmark([X])}. prorel([prorel(X)]) --> [X], {prorel([X])}. aux([aux(X)]) --> [X], {aux([X])}. connector([connector(X)]) --> [X], {connector([X])}. % ----------------------------------------------- :-[tokens]. % ----------------------------------------------- % inside we have only adj(),adj(), then: transform(A,A):- atomic(A),!. transform(A,B):- A=.. [B,C],atomic(C),!. % [a,b] --> [a',b'] transform( [], [] ):-!. transform( [Elem|List], [Elem1|List1] ):-!, transform(Elem ,Elem1), transform(List ,List1). transform(A,B):- A=.. [C|List],!, transform(List ,List1), B=.. [C|List1]. % ----------------------------------------------- E.1. Language analysis: source code 127 Listing E.3: Lexicon used in the DCG :-use_module(library(lists)). det([the]). det([that]). det([those]). det([a]). det([an]). det([this]). ... prep([to]). prep([at]). prep([on]). prep([in]). prep([since]). ... wh([who]). wh(['when']). wh([where]). wh([how]). wh([what]). wh([which]). wh([whose]). wh([whom]). qmark([?]). prorel([who]). prorel([that]). prorel([which]). aux([does]). aux([do]). ... aux([should]). connector([and]). connector([or]). connector([but]). ... % ----------------------------------------------- % nouns: s(100004475,1,' organism ',n,1,9). % plural: +s noun([X]):- wordnet:s(_,_,X,n,_,_),! ; X\== 'is',remove_es(X,Y), wordnet:s(_,_,Y,n,_,_),!. % verbs: s(200001740,1,'breathe',v,1,22). % 3rd person: +es|+s % past: +ed :-[irregulars]. verb([X]):- wordnet:s(_,_,X,v,_,_),! ; remove_es(X,Y1), wordnet:s(_,_,Y1,v,_,_) ; We can only see a short distance ahead, but we can see plenty there that needs to be done. Alan Turing