|
Aleph (ILP)
Aleph (A Learning Engine for Proposing Hypotheses) is an inductive logic programming system introduced by Ashwin Srinivasan in 2001. it is still one of the most widely used inductive logic programming systems. It is based on the earlier system Progol. Learning task The input to Aleph is background knowledge, specified as a logic program, a language bias in the form of mode declarations, as well as positive and negative examples specified as ground facts. As output it returns a logic program which, together with the background knowledge, entails all of the positive examples and none of the negative examples. Basic algorithm Starting with an empty hypothesis, Aleph proceeds as follows: * It chooses a positive example to generalise; if none are left, it aborts and outputs the current hypothesis. * Then it constructs the bottom clause, that is, the most specific clause that is allowed by the mode declarations and covers the example. * It then searches for a generali ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Prolog
Prolog is a logic programming language that has its origins in artificial intelligence, automated theorem proving, and computational linguistics. Prolog has its roots in first-order logic, a formal logic. Unlike many other programming languages, Prolog is intended primarily as a declarative programming language: the program is a set of facts and Horn clause, rules, which define Finitary relation, relations. A computation is initiated by running a ''query'' over the program. Prolog was one of the first logic programming languages and remains the most popular such language today, with several free and commercial implementations available. The language has been used for automated theorem proving, theorem proving, expert systems, term rewriting, type systems, and automated planning, as well as its original intended field of use, natural language processing. See also Watson (computer). Prolog is a Turing-complete, general-purpose programming language, which is well-suited for inte ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Inductive Logic Programming
Inductive logic programming (ILP) is a subfield of symbolic artificial intelligence which uses logic programming as a uniform representation for examples, background knowledge and hypotheses. The term "''inductive''" here refers to philosophical (i.e. suggesting a theory to explain observed facts) rather than mathematical (i.e. proving a property for all members of a well-ordered set) induction. Given an encoding of the known background knowledge and a set of examples represented as a logical database of facts, an ILP system will derive a hypothesised logic program which entails all the positive and none of the negative examples. * Schema: ''positive examples'' + ''negative examples'' + ''background knowledge'' ⇒ ''hypothesis''. Inductive logic programming is particularly useful in bioinformatics and natural language processing. History Building on earlier work on Inductive inference, Gordon Plotkin was the first to formalise induction in a clausal setting around 1970, ad ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Progol
Progol is an implementation of inductive logic programming that combines inverse entailment with general-to-specific search through a refinement graph. Features Inverse entailment is used with mode declarations to derive the bottom clause, the most-specific clause within the mode language which subsume a given example. This clause is used to guide a refinement-graph search. Unlike the searches of Ehud Shapiro's model inference system (MIS) and J. Ross Quinlan's FOIL, Progol's search has a provable guarantee of returning a solution having the maximum compression in the search-space. To do so it performs an admissible A*-like search, guided by compression, over clauses which subsume the most specific clause. Progol deals with noisy data by using a compression measure to trade off the description of errors against the hypothesis description length. Progol allows arbitrary Prolog programs as background knowledge and arbitrary definite clauses as examples. History Progo ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Logic Program
Logic programming is a programming, database and knowledge representation paradigm based on formal logic. A logic program is a set of sentences in logical form, representing knowledge about some problem domain. Computation is performed by applying logical reasoning to that knowledge, to solve problems in the domain. Major logic programming language families include Prolog, Answer Set Programming (ASP) and Datalog. In all of these languages, rules are written in the form of ''clauses'': :A :- B1, ..., Bn. and are read as declarative sentences in logical form: :A if B1 and ... and Bn. A is called the ''head'' of the rule, B1, ..., Bn is called the ''body'', and the Bi are called '' literals'' or conditions. When n = 0, the rule is called a ''fact'' and is written in the simplified form: :A. Queries (or goals) have the same syntax as the bodies of rules and are commonly written in the form: :?- B1, ..., Bn. In the simplest case of Horn clauses (or "definite" clauses), all of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Ground Expression
In mathematical logic, a ground term of a formal system is a term that does not contain any variables. Similarly, a ground formula is a formula that does not contain any variables. In first-order logic with identity with constant symbols a and b, the sentence Q(a) \lor P(b) is a ground formula. A ground expression is a ground term or ground formula. Examples Consider the following expressions in first order logic over a signature containing the constant symbols 0 and 1 for the numbers 0 and 1, respectively, a unary function symbol s for the successor function and a binary function symbol + for addition. * s(0), s(s(0)), s(s(s(0))), \ldots are ground terms; * 0 + 1, \; 0 + 1 + 1, \ldots are ground terms; * 0+s(0), \; s(0)+ s(0), \; s(0)+s(s(0))+0 are ground terms; * x + s(1) and s(x) are terms, but not ground terms; * s(0) = 1 and 0 + 0 = 0 are ground formulae. Formal definitions What follows is a formal definition for first-order languages. Let a first-order language be gi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Clause (logic)
In logic, a clause is a propositional formula formed from a finite collection of literals (atoms or their negations) and logical connectives. A clause is true either whenever at least one of the literals that form it is true (a disjunctive clause, the most common use of the term), or when all of the literals that form it are true (a conjunctive clause, a less common use of the term). That is, it is a finite disjunction or conjunction of literals, depending on the context. Clauses are usually written as follows, where the symbols l_i are literals: :l_1 \vee \cdots \vee l_n Empty clauses A clause can be empty (defined from an empty set of literals). The empty clause is denoted by various symbols such as \empty, \bot, or \Box. The truth evaluation of an empty disjunctive clause is always false. This is justified by considering that false is the neutral element of the monoid (\, \vee). The truth evaluation of an empty conjunctive clause is always true. This is related to the conc ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Refinement Graph
Theta-subsumption (θ-subsumption, or just subsumption) is a decidable relation between two first-order clauses that guarantees that one clause logically entails the other. It was first introduced by John Alan Robinson in 1965 and has become a fundamental notion in inductive logic programming. Deciding whether a given clause θ-subsumes another is an NP-complete problem. Definition A clause, that is, a disjunction of first-order literals, can be considered as a set containing all its disjuncts. With this convention, a clause c_1 θ-subsumes a clause c_2 if there is a substitution \theta such that the clause obtained by applying \theta to c_1 is a subset of c_2. Properties θ-subsumption is a weaker relation than logical entailment, that is, whenever a clause c_1 θ-subsumes a clause c_2, then c_1 logically entails c_2 . However, the converse is not true: A clause can logically entail another clause, but not θ-subsume it. θ-subsumption is decidable; more precisely, ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
