Индуктивное логическое программирование

Индуктивное логическое программирование (Inductive Logic Programming, ILP) — раздел машинного обучения, который использует логическое программирование как форму представления примеров, фоновых знаний и гипотез. Получив описания уже известных фоновых знаний и набор примеров, представленных как логическая база фактов, система ILP может породить логическую программу в форме гипотез, объясняющую все положительные примеры и ни одного отрицательного.

Схема: положительные примеры + отрицательные примеры + фоновые знания => гипотезы

Термин Индуктивное логическое программирование был впервые использован в статье Стивена Магглтона (Stephen Muggleton) в 1991 году. Термин «индуктивное» здесь употребляется в философском (предложение теории для объяснения наблюдаемых фактов), а не в математическом (доказательство свойства членов множества) смысле.

Задача ILP

Задача – найти полное и совместное определение целевого предиката в терминах фоновых знаний.

Полное (complete) – охватывает все «+»-примеры
Совместное (consistent) – не охватывает ни одного «-»-примера

"Гипотеза объясняет примеры" означает:

Для «+»-примера: факты из базы фактов и гипотеза позволяют вывести этот пример
Для «-»-примера: факты из базы фактов и гипотеза не позволяют вывести этот пример (отрицание как неудача)

Правила в языке Prolog

Обычно реализации ILP делаются на языке Prolog. Для понимания дальнейшего примера, напомним о том, как устроены правила в этом языке программирования.

В нем правило — это импликация, например: имеет_сына(X):-родитель(X,Y), !женщина(Y). (X имеет сына, если X - родитель Y, и Y - не женщина) Голова правила — это заключение импликации. Тело правила — это посылка импликации (конъюнкция «,» литералов). Литерал - атомарная формула языка Prolog, либо её отрицание. Если есть несколько правил с одинаковой головой, то их можно объединить в одно, соединив их тела дизъюнкцией «;»

Уточнение гипотез

Уточнение гипотез (refinement) представляет собой итерационный процесс: Берется более общая гипотеза H1, которая объясняет все «+»-примеры и некоторые «-» примеры. Она уточняется так, чтобы объяснять меньше «-» - примеров. Результат: гипотеза H2, которая объясняет только подмножество примеров, объясняемых H1

Способы уточнения гипотез:

Отождествление переменных

Было:

has_daughter(X) :- 
    parent(Y,Z).

Стало:

has_daughter(X) :- 
    parent(X,Z)

Добавление фонового предиката к телу

Было:

has_daughter(X) :-.

Стало:

has_daughter(X) :- 
    parent(Y,Z).

Пример

Предположим, что имеется база фактов о семье:

male(john).
male(bill).
male(paul).
parent(john, kate).
parent(mary, kate).
parent(bill, paul).
parent(kate, paul).
female(mary).
female(kate).

Фоновыми знаниями для этой задачи будут предикаты "родитель", "мужчина" и "женщина":

parent(X,Y)
male(X)
female(X)

Мы хотим научить ILP-систему предикату "имеет дочь". Определим его как целевой предикат:

has_daughter(X)

Для этого предиката положительные примеры будут:

has_daughter(mary)
has_daughter(john)

Отрицательные примеры:

has_daughter(bill)
has_daughter(kate)
has_daughter(paul)

На первом шаге обучения мы имеем только одну максимально общую гипотезу:

Дерево гипотез для примера "Семья" после уточнения

has_daughter(X).

Она устроена тривиально - охватывает все примеры (выполняется для любого X). Но очевидно, что на некоторых примерах она дает неправильный результат - так, в базе есть и те, кто не имеют дочь (это Билл, Кейт и Пол). Таким образом, гипотеза полна (охватывает все "+"-примеры), но несовместна (охватывает некоторые "-"-примеры).

Начнем процесс уточнения гипотезы. Так как отождествлять переменные мы не можем - она всего одна - то воспользуемся вторым способом - добавление фонового предиката к телу. Мы получим уже 3 гипотезы:

has_daughter(X):-
    male(Y).

has_daughter(X):-
    female(Y).

has_daughter(X):-
    parent(Y, Z).

Получение правильной гипотезы для примера с семьёй

Теперь можно воспользоваться 1 способом уточнения гипотез и отождествить переменные (т.е. заменить Y на X) Получим:

has_daughter(X):-
    male(X).

has_daughter(X):-
    female(X).

has_daughter(X):-
    parent(X, Z).

Первая из полученных гипотез звучит так: "X имеет дочь, если X - мужчина". Она имеет контрпример в лице Мэри, которая имеет дочь, однако не является мужчиной. Поэтому здесь ветвь дерева обрезается: гипотеза уже неполна (не охватывает Мэри, которая имеет дочь) и несовместна (охватывает примеры "Билл" и "Пол", у которых нет дочерей). Аналогично будет и в случае гипотезы "Х имеет дочь, если X - женщина".

Единственная ветвь, которая ведет к правильной гипотезе - это цепочка уточнений с правой стороны, включающая предикат "родитель". В итоге, мы получаем гипотезу:

has_daughter(X):-
    parent(X, Z),
    female(Z).

Именно она является полной и совместной.

Возможности

Обучение рекурсивным понятиям, таким как "потомок".
Мультипредикатное обучение (одновременное изучение нескольких предикатов, когда один предикат определяется в терминах другого)

Недостатки

Требуется вручную указать количество и тип переменных в целевом предикате
Высокая вычислительная сложность (NP-полная задача). При добавлении литералов увеличивается число переменных в предикате. Любое подмножество переменных может быть отождествлено между собой, что сразу дает экспоненциальный рост сложности.

Эвристики

Возможные ограничения для уменьшения временных затрат:

Ограничение на максимальную глубину поиска
Ограничение на максимальное число литералов в теле предиката
Введение параметра "стоимость гипотезы": Cost(H) = количество_переменных(H) + 10*количество_литералов(H) + 10*NegCover(H)

Сферы применения ILP

Медицина (диагностика ревматических заболеваний)
Органическая химия (предсказание вторичной структуры белка)
Механика сплошных сред (предсказание деформации, качественные модели динамических систем)
Фармакология (задача структура-активность)

Литература

Иван Братко. Алгоритмы искусственного интеллекта на языке PROLOG = Prolog Programming For Artificial Intelligence. — М.: «Вильямс», 2004. — С. 640. — ISBN 0-201-40375-7.