Английская Википедия: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, adopting an approach of generalising from examples.^[1]^[2] In 1981, Ehud Shapiro introduced several ideas that would shape the field in his new approach of model inference, an algorithm employing refinement and backtracing to search for a complete axiomatisation of given examples.^[1]^[3] His first implementation was the Model Inference System in 1981:^[4]^[5] a Prolog program that inductively inferred Horn clause logic programs from positive and negative examples.^[1] The term Inductive Logic Programming was first introduced in a paper by Stephen Muggleton in 1990, defined as the intersection of machine learning and logic programming.^[1] Muggleton and Wray Buntine introduced predicate invention and inverse resolution in 1988.^[1]^[6]

Several inductive logic programming systems that proved influential appeared in the early 1990s. FOIL, introduced by Ross Quinlan in 1990^[7] was based on upgrading propositional learning algorithms AQ and ID3.^[8] Golem, introduced by Muggleton and Feng in 1990, went back to a restricted form of Plotkin's least generalisation algorithm.^[8]^[9] The Progol system, introduced by Muggleton in 1995, first implemented inverse entailment, and inspired many later systems.^[8]^[10]^[11] Aleph, a descendant of Progol introduced by Ashwin Srinivasan in 2001, is still one of the most widely used systems Шаблон:As of.^[10]

At around the same time, the first practical applications emerged, particularly in bioinformatics, where by 2000 inductive logic programming had been successfully applied to drug design, carcinogenicity and mutagenicity prediction, and elucidation of the structure and function of proteins.^[12] Unlike the focus on automatic programming inherent in the early work, these fields used inductive logic programming techniques from a viewpoint of relational data mining. The success of those initial applications and the lack of progress in recovering larger traditional logic programs shaped the focus of the field.^[13]

Recently, classical tasks from automated programming have moved back into focus, as the introduction of meta-interpretative learning makes predicate invention and learning recursive programs more feasible. This technique was pioneered with the Metagol system introduced by Muggleton, Dianhuan Lin, Niels Pahlavi and Alireza Tamaddoni-Nezhad in 2014.^[14] This allows ILP systems to work with fewer examples, and brought successes in learning string transformation programs, answer set grammars and general algorithms.^[15]

Setting

Inductive logic programming has adopted several different learning settings, the most common of which are learning from entailment and learning from interpretations.^[16] In both cases, the input is provided in the form of background knowledge Шаблон:Mvar, a logical theory (commonly in the form of clauses used in logic programming), as well as positive and negative examples, denoted <math display="inline">E^+</math> and <math display="inline">E^{-}</math> respectively. The output is given as a hypothesis Шаблон:Mvar, itself a logical theory that typically consists of one or more clauses.

The two settings differ in the format of examples presented.

Learning from entailment

Шаблон:As of, learning from entailment is by far the most popular setting for inductive logic programming.^[16] In this setting, the positive and negative examples are given as finite sets <math display="inline">E^+</math> and <math display="inline">E^{-}</math> of positive and negated ground literals, respectively. A correct hypothesis Шаблон:Mvar is a set of clauses satisfying the following requirements, where the turnstile symbol <math>\models</math> stands for logical entailment:^[16]^[17]^[18] <math display="block">\begin{array}{llll} \text{Completeness:} & B \cup H & \models & E^+ \\ \text{Consistency: } & B \cup H \cup E^- & \not\models & \textit{false} \end{array}</math> Completeness requires any generated hypothesis Шаблон:Mvar to explain all positive examples <math display="inline">E^+</math>, and consistency forbids generation of any hypothesis Шаблон:Mvar that is inconsistent with the negative examples <math display="inline">E^{-}</math>, both given the background knowledge Шаблон:Mvar.

In Muggleton's setting of concept learning,^[19] "completeness" is referred to as "sufficiency", and "consistency" as "strong consistency". Two further conditions are added: "Necessity", which postulates that Шаблон:Mvar does not entail <math display="inline">E^+</math>, does not impose a restriction on Шаблон:Mvar, but forbids any generation of a hypothesis as long as the positive facts are explainable without it. . "Weak consistency", which states that no contradiction can be derived from <math display="inline">B\land H</math>, forbids generation of any hypothesis Шаблон:Mvar that contradicts the background knowledge Шаблон:Mvar. Weak consistency is implied by strong consistency; if no negative examples are given, both requirements coincide. Weak consistency is particularly important in the case of noisy data, where completeness and strong consistency cannot be guaranteed.^[19]

Learning from interpretations

In learning from interpretations, the positive and negative examples are given as a set of complete or partial Herbrand structures, each of which are themselves a finite set of ground literals. Such a structure Шаблон:Mvar is said to be a model of the set of clauses <math display="inline">B \cup H</math> if for any substitution <math display="inline">\theta</math> and any clause <math display="inline">\mathrm{head} \leftarrow \mathrm{body}</math> in <math display="inline">B \cup H</math> such that <math display="inline">\mathrm{body}\theta \subseteq e</math>, <math>\mathrm{head}\theta \subseteq e</math> also holds. The goal is then to output a hypothesis that is complete, meaning every positive example is a model of <math display="inline">B \cup H</math>, and consistent, meaning that no negative example is a model of <math display="inline">B \cup H</math>.^[16]

Approaches to ILP

An inductive logic programming system is a program that takes as an input logic theories <math>B, E^+, E^-</math> and outputs a correct hypothesis Шаблон:Mvar with respect to theories <math>B, E^+, E^-</math>. A system is complete if and only if for any input logic theories <math>B, E^+, E^-</math> any correct hypothesis Шаблон:Mvar with respect to these input theories can be found with its hypothesis search procedure. Inductive logic programming systems can be roughly divided into two classes, search-based and meta-interpretative systems.

Search-based systems exploit that the space of possible clauses forms a complete lattice under the subsumption relation, where one clause <math display="inline">C_1</math> subsumes another clause <math display="inline">C_2</math> if there is a substitution <math display="inline">\theta</math> such that <math display="inline">C_1\theta</math>, the result of applying <math display="inline">\theta</math> to <math display="inline">C_1</math>, is a subset of <math display="inline">C_2</math>. This lattice can be traversed either bottom-up or top-down.

Bottom-up search

Bottom-up methods to search the subsumption lattice have been investigated since Plotkin's first work on formalising induction in clausal logic in 1970.^[1]^[20] Techniques used include least general generalisation, based on anti-unification, and inverse resolution, based on inverting the resolution inference rule.

Least general generalisation

A least general generalisation algorithm takes as input two clauses <math display="inline">C_1</math> and <math display="inline">C_2</math> and outputs the least general generalisation of <math display="inline">C_1</math> and <math display="inline">C_2</math>, that is, a clause <math display="inline">C</math> that subsumes <math display="inline">C_1</math> and <math display="inline">C_2</math>, and that is subsumed by every other clause that subsumes <math display="inline">C_1</math> and <math display="inline">C_2</math>. The least general generalisation can be computed by first computing all selections from <math display="inline">C</math> and <math display="inline">D</math>, which are pairs of literals <math>(L,M) \in (C_1, C_2)</math> sharing the same predicate symbol and negated/unnegated status. Then, the least general generalisation is obtained as the disjunction of the least general generalisations of the individual selections, which can be obtained by first-order syntactical anti-unification.^[21]

To account for background knowledge, inductive logic programming systems employ relative least general generalisations, which are defined in terms of subsumption relative to a background theory. In general, such relative least general generalisations are not guaranteed to exist; however, if the background theory Шаблон:Mvar is a finite set of ground literals, then the negation of Шаблон:Mvar is itself a clause. In this case, a relative least general generalisation can be computed by disjoining the negation of Шаблон:Mvar with both <math display="inline">C_1</math> and <math display="inline">C_2</math> and then computing their least general generalisation as before.^[22]

Relative least general generalisations are the foundation of the bottom-up system Golem.^[8]^[9]

Inverse resolution

Inverse resolution is an inductive reasoning technique that involves inverting the resolution operator.

Inverse resolution takes information about the resolvent of a resolution step to compute possible resolving clauses. Two types of inverse resolution operator are in use in inductive logic programming: V-operators and W-operators. A V-operator takes clauses <math display="inline">R</math> and <math display="inline">C_1</math>as input and returns a clause <math display="inline">C_2</math> such that <math display="inline">R</math> is the resolvent of <math display="inline">C_1</math> and <math display="inline">C_2</math>. A W-operator takes two clauses <math display="inline">R_1</math> and <math display="inline">R_2</math> and returns thre clauses <math display="inline">C_1</math>, <math display="inline">C_2</math> and <math display="inline">C_3</math> such that <math display="inline">R_1</math> is the resolvent of <math display="inline">C_1</math> and <math display="inline">C_2</math> and <math display="inline">R_2</math> is the resolvent of <math display="inline">C_2</math> and <math display="inline">C_3</math>.^[23]

Inverse resolution was first introduced by Stephen Muggleton and Wray Buntine in 1988 for use in the inductive logic programming system Cigol.^[6] By 1993, this spawned a surge of research into inverse resolution operators and their properties.^[23]

Top-down search

The ILP systems Progol,^[11] Hail ^[24] and Imparo ^[25] find a hypothesis Шаблон:Mvar using the principle of the inverse entailment^[11] for theories Шаблон:Mvar, Шаблон:Mvar, Шаблон:Mvar: <math>B \land H \models E \iff B \land \neg E \models \neg H</math>. First they construct an intermediate theory Шаблон:Mvar called a bridge theory satisfying the conditions <math>B \land \neg E \models F</math> and <math>F \models \neg H</math>. Then as <math>H \models \neg F</math>, they generalize the negation of the bridge theory Шаблон:Mvar with anti-entailment.^[26] However, the operation of anti-entailment is computationally more expensive since it is highly nondeterministic. Therefore, an alternative hypothesis search can be conducted using the inverse subsumption (anti-subsumption) operation instead, which is less non-deterministic than anti-entailment.

Questions of completeness of a hypothesis search procedure of specific inductive logic programming system arise. For example, the Progol hypothesis search procedure based on the inverse entailment inference rule is not complete by Yamamoto's example.^[27] On the other hand, Imparo is complete by both anti-entailment procedure ^[28] and its extended inverse subsumption ^[29] procedure.

Metainterpretive learning

Rather than explicitly searching the hypothesis graph, metainterpretive or meta-level systems encode the inductive logic programming program as a meta-level logic program which is then solved to obtain an optimal hypothesis. Formalisms used to express the problem specification include Prolog and answer set programming, with existing Prolog systems and answer set solvers used for solving the constraints.^[30]

And example of a Prolog-based system is Metagol, which is based on a meta-interpreter in Prolog, while ASPAL and ILASP are based on an encoding of the inductive logic programming problem in answer set programming.^[30]

List of implementations

1BC and 1BC2: first-order naive Bayesian classifiers:
ACE (A Combined Engine)
Aleph
Atom Шаблон:Webarchive
Claudien Шаблон:Dead link
DL-Learner Шаблон:Webarchive
DMax
FastLAS (Fast Learning from Answer Sets)
FOIL (First Order Inductive Learner)
Golem
ILASP (Inductive Learning of Answer Set Programs)
Imparo^[28]
Inthelex (INcremental THEory Learner from EXamples) Шаблон:Webarchive
Lime
Metagol
Mio
MIS (Model Inference System) by Ehud Shapiro
Popper
PROGOL
RSD
Warmr (now included in ACE)
ProGolem ^[31]^[32]

Probabilistic inductive logic programming

Probabilistic inductive logic programming adapts the setting of inductive logic programming to learning probabilistic logic programs. It can be considered as a form of statistical relational learning within the formalism of probabilistic logic programming.^[33]^[34]

Given

background knowledge as a probabilistic logic program Шаблон:Mvar, and
a set of positive and negative examples <math display="inline">E^{+}</math> and <math display="inline">E^{-}</math>

the goal of probabilistic inductive logic programming is to find a probabilistic logic program <math display="inline">H</math> such that the probability of positive examples according to <math display="inline">{H \cup B}</math> is maximized and the probability of negative examples is minimized.^[34]

This problem has two variants: parameter learning and structure learning. In the former, one is given the structure (the clauses) of Шаблон:Mvar and the goal is to infer the probabilities annotations of the given clauses, while in the latter the goal is to infer both the structure and the probability parameters of Шаблон:Mvar. Just as in classical inductive logic programming, the examples can be given as examples or as (partial) interpretations.^[34]

Parameter Learning

Parameter learning for languages following the distribution semantics has been performed by using an expectation-maximisation algorithm or by gradient descent. An expectation-maximisation algorithm consists of a cycle in which the steps of expectation and maximization are repeatedly performed. In the expectation step, the distribution of the hidden variables is computed according to the current values of the probability parameters, while in the maximisation step, the new values of the parameters are computed. Gradient descent methods compute the gradient of the target function and iteratively modify the parameters moving in the direction of the gradient.^[34]

Structure Learning

Structure learning was pioneered by Daphne Koller and Avi Pfeffer in 1997,^[35] where the authors learn the structure of first-order rules with associated probabilistic uncertainty parameters. Their approach involves generating the underlying graphical model in a preliminary step and then applying expectation-maximisation.^[34]

In 2008, De Raedt et al. presented an algorithm for performing theory compression on ProbLog programs, where theory compression refers to a process of removing as many clauses as possible from the theory in order to maximize the probability of a given set of positive and negative examples. No new clause can be added to the theory.^[34]^[36]

In the same year, Meert, W. et al. introduced a method for learning parameters and structure of ground probabilistic logic programs by considering the Bayesian networks equivalent to them and applying techniques for learning Bayesian networks.^[37]^[34]

ProbFOIL, introduced by De Raedt and Ingo Thon in 2010, combined the inductive logic programming system FOIL with ProbLog. Logical rules are learned from probabilistic data in the sense that both the examples themselves and their classifications can be probabilistic. The set of rules has to allow one to predict the probability of the examples from their description. In this setting, the parameters (the probability values) are fixed and the structure has to be learned.^[38]^[34]

In 2011, Elena Bellodi and Fabrizio Riguzzi introduced SLIPCASE, which performs a beam search among probabilistic logic programs by iteratively refining probabilistic theories and optimizing the parameters of each theory using expectation-maximisation.^[39] Its extension SLIPCOVER, proposed in 2014, uses bottom clauses generated as in Progol to guide the refinement process, thus reducing the number of revisions and exploring the search space more effectively. Moreover, SLIPCOVER separates the search for promising clauses from that of the theory: the space of clauses is explored with a beam search, while the space of theories is searched greedily.^[40]^[34]

References

Шаблон:Reflist Шаблон:Free-content attribution

Партнерские ресурсы
Криптовалюты	Обмен криптовалют - www.bestchange.ru Криптовалютная биржа CoinEx Криптовалютная биржа Binance HIVE OS - операционная система для майнинга e4pool - Мультивалютный пул для майнинга.
Магазины	AliExpress — глобальная виртуальная (в Интернете) торговая площадка, предоставляющая возможность покупать товары производителей из КНР; computeruniverse.net - Интернет-магазин компьютеров(Промо код 5 Евро на первую покупку:FWWC3ZKQ);
Хостинг	DigitalOcean - американский провайдер облачных инфраструктур, с главным офисом в Нью-Йорке и с центрами обработки данных по всему миру;
Разное	Викиум - Онлайн-тренажер для мозга Like Центр - Центр поддержки и развития предпринимательства. Gamersbay - лучший магазин по бустингу для World of Warcraft. Ноотропы OmniMind N°1 - Усиливает мозговую активность. Повышает мотивацию. Улучшает память. Санкт-Петербургская школа телевидения - это федеральная сеть образовательных центров, которая имеет филиалы в 37 городах России. Lingualeo.com — интерактивный онлайн-сервис для изучения и практики английского языка в увлекательной игровой форме. Junyschool (Джунискул) – международная школа программирования и дизайна для детей и подростков от 5 до 17 лет, где ученики осваивают компьютерную грамотность, развивают алгоритмическое и креативное мышление, изучают основы программирования и компьютерной графики, создают собственные проекты: игры, сайты, программы, приложения, анимации, 3D-модели, монтируют видео. Умназия - Интерактивные онлайн-курсы и тренажеры для развития мышления детей 6-13 лет SkillBox - это один из лидеров российского рынка онлайн-образования. Среди партнеров Skillbox ведущий разработчик сервисного дизайна AIC, медиа-компания Yoola, первое и самое крупное русскоязычное аналитическое агентство Tagline, онлайн-школа дизайна и иллюстрации Bang! Bang! Education, оператор PR-рынка PACO, студия рисования Draw&Go, агентство performance-маркетинга Ingate, scrum-студия Sibirix, имидж-лаборатория Персона. «Нетология» — это университет по подготовке и дополнительному обучению специалистов в области интернет-маркетинга, управления проектами и продуктами, дизайна, Data Science и разработки. В рамках Нетологии студенты получают ценные теоретические знания от лучших экспертов Рунета, выполняют практические задания на отработку полученных навыков, общаются с экспертами и единомышленниками. Познакомиться со всеми продуктами подробнее можно на сайте https://netology.ru, линейка курсов и профессий постоянно обновляется. StudyBay Brazil – это онлайн биржа для португалоговорящих студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт. Автор24 — самая большая в России площадка по написанию учебных работ: контрольные и курсовые работы, дипломы, рефераты, решение задач, отчеты по практике, а так же любой другой вид работы. Сервис сотрудничает с более 70 000 авторов. Более 1 000 000 работ уже выполнено. StudyBay – это онлайн биржа для англоязычных студентов и авторов! Студент получает уникальную работу любого уровня сложности и больше свободного времени, в то время как у автора появляется дополнительный заработок и бесценный опыт.

Английская Википедия:Inductive logic programming

Содержание