Индуктивное логическое программирование (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 Медицина (диагностика ревматических заболеваний) Органическая химия (предсказание вторичной структуры белка) Механика сплошных сред (предсказание деформации, качественные модели динамических систем) Фармакология (задача структура-активность)
Литература
Категория:Логическое программирование Категория:Искусственный интеллект