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

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

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

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

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

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

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

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

Обычно реализации 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)

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

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