Индуктивное логическое программирование
![]() | В статье не хватает ссылок на источники (см. рекомендации по поиску). |
Индуктивное логическое программирование (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).
Пример
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/d/dc/ILP_family1.png)
Предположим, что имеется база фактов о семье:
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)
На первом шаге обучения мы имеем только одну максимально общую гипотезу:
![Дерево гипотез для примера "Семья" после уточнения](http://upload.wikimedia.org/wikipedia/commons/8/82/ILP_family2.png)
has_daughter(X).
Она устроена тривиально - охватывает все примеры (выполняется для любого X). Но очевидно, что на некоторых примерах она дает неправильный результат - так, в базе есть и те, кто не имеют дочь (это Билл, Кейт и Пол). Таким образом, гипотеза полна (охватывает все "+"-примеры), но несовместна (охватывает некоторые "-"-примеры).
Начнем процесс уточнения гипотезы. Так как отождествлять переменные мы не можем - она всего одна - то воспользуемся вторым способом - добавление фонового предиката к телу. Мы получим уже 3 гипотезы:
has_daughter(X):-
male(Y).
has_daughter(X):-
female(Y).
has_daughter(X):-
parent(Y, Z).
![Получение правильной гипотезы для примера с семьёй](http://upload.wikimedia.org/wikipedia/commons/e/e0/ILP_family3.png)
Теперь можно воспользоваться 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.