Введение. индуктивное логическое программирование — это один из подходов к машинному обучению

Индуктивное логическое программирование — это один из подходов к машинному обучению. Оно представляет собой метод изучения отношений на примерах. В методе ILP в качестве языка определения гипотез используется логика предикатов.

Поэтому результатом обучения становится формула логики предикатов, обычно программа Prolog.

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

Кроме того, пользователь задает некоторые фоновые предикаты, которые могут использоваться при написании намеченной новой программы.

Ниже приведен пример использования такого метода автоматического программирования на языке Prolog. Предположим, что уже имеются предикаты parent (X, Y), male(X) и female(X), определяющие некоторые семейные отношения

(см. рис. 1.1 в главе 1). Теперь необходимо найти определение нового предиката has_daughter (X), Допустим, что даны некоторые примеры, относящиеся к этому новому предикату.

В частности, ниже приведены два положительных примера.

has daughter(torn), has daughter(bob)

Двумя отрицательными примерами являются следующие:

has daughter(pam), has_daughter(jim)

Задача обучения состоит в том, что нужно найти определение предиката has_daughter(X) в терминах предикатов parent, male и female таким образом, чтобы этот предикат принимал истинное значение для всех заданных положительных примеров и ложное значение — для всех заданных отрицательных, примеров. Программа ILF может выработать следующую гипотезу в отношении предиката has_daughter:

has daughter! X) :-parent< Xr Y), female ( Y>.

Эта гипотеза объясняет все заданные примеры.

На приведенном выше примере можно отметить типичное отличие такого, реляционного {основанного па отношениях) обучения от обучения на основе атрибутов и значений. В этом примере свойство has daughter объекта X определено не только в терминах атрибутов X. Вместо этого для определения наличия у объекта х свойства has daughter рассматривается другой объект, Y, связанный с X, и проверяются свойства объекта У.

Теперь необходимо определить некоторые технические термины, применяемые в методе ILP. В приведенном выше примере предикат, который должен быть получен в результате обучения, has_daughter, называется целевым предикатом. Заданные предикаты parent, male и female называются фоновыми знаниями (Background Knowledge — ВК), или фоновыми предикатами.

Это — знания, известные ученику до начала обучения. Итак, фоновые предикаты фактически определяют язык, на котором ученик может выражать гипотезы, относящиеся к целевому предикату.

Теперь мы можем обычным образом сформулировать задачу ILP, как описано ниже.

Дано:

1. множество положительных примеров Ef и множество отрицательных примеров Е.;

2. фоновые знания ВК, заданные как множество логических формул, такое, что примеры Е. невозможно вывести логически из ВК

Найти: гипотезу Н, заданную как множество логических формул, такое, что

1. все положительные примеры в Е+ можно вывести логически из ВК и Н;

2. ни одного отрицательного примера в Е- нельзя вывести логически из ВК и И.

Принято также использовать такую формулировку, что н вместе с ЗК должны охватывать все положительные примеры и не должны охватывать ни одного из отрицательных примеров. Подобная гипотеза И называется полной (охватывающей все положительные примеры) и достоверной (совместимой только с положительными примерами, т.е. не охватывающей ни одного отрицательного примера).

Обычно и ВК, и — представляют собой множества предложений Prolog, иными словами, программы Prolog. Поэтому с точки зрения автоматического программирования на языке Prolog приведенная выше формулировка задачи обучения соответствует следующей. Предположим, что целевым предикатом является р

?- р(а) . — Положительный пример

по % Не может быть выведен логически из ВК

?- р{Ь) . % Отрицательный пример

по % Не может быть выведен логически из ВК

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

Теперь предположим, что вызвана на выполнение система ILP, которая автоматически осуществляет логический вывод дополнительного множества предложений Н и добавляет их к программе вк. После этого возможный диалог с расширенной таким образом программой, состоящей из предложений ВК и Н, может представлять собой следующее:

?- р(а). % Положительный пример

yes % Может быть выведен логически из ВК и Н

?-р(Ь). % Отрицательный пример

по % Не может быть выведен логически из ВК и Н

Широко известными задачами в области ILP является автоматическое формирование программ Prolog для конкатенации или сортировки списков. Такие программы создаются на основании положительных примеров того, как должна осуществляться конкатенация или сортировка списков, а также отрицательных примеров того, как эти действия не должны выполняться. В настоящей главе разрабатывается программа 1LP под названием HYPER и применяется для решения таких задач.

Рассмотрим, в чем состоят отличия метода ILP от других, нелогических подходов к машинному обучению, которые, по сути, представляют собой своего рода обучение на основе атрибутов и значений. Преимущества ILP состоят в том, что в этом методе используются мощный язык гипотез и перспективный способ включения фоновых знаний в процесс обучения. Язык гипотез позволяет применять реляционные определения, которые могут даже предусматривать рекурсию.

Обычно такая ВОЗМОЖНОСТЬ не обеспечивается при использовании других подходов к машинному обучению.

В методе ILP в качестве фоновых знаний, по сути, может применяться любая программа Prolog. Это дает возможность пользователю подготавливать для использования в обучении конкретные знания о проблемной области и представлять их наиболее естественным способом. Применение фоновых знаний позволяет пользователю подготавливать качественное представление задачи и задавать в процессе обучения конкретные ограничения, относящиеся к рассматриваемой задаче.

В отличие от этого, в процессе обучения на основе атрибутов и значений фоновые знания обычно могут быть представлены только в весьма ограниченных формах, например в форме допустимых новых атрибутов. С другой стороны, метод ILP является гораздо более гибким. Например, если задача состоит в изучении свойств химических веществ, то в качестве фоновых зияний могут задаваться молекулярные структуры, которые определены в виде атомов и связей между ними.

А если задача обучения состоит в автоматическом формировании модели физической системы по результатам наблюдений за ее действиями, то в состав фоновых знаний может быть включен весь математический аппарат, который рассматривается как приемлемый для описания моделируемой проблемной области. Если же речь идет о процессах, происходящих в физическом мире, то в состав фоновых знаний могут быть включены аксиомы, позволяющие формировать рассуждения о времени и пространстве.

Как правило, при разработке приложений ILP основные усилия направлены на подготовку качественного представления примеров наряду с соответствующими фоновыми знаниями. После этого для осуществления логического вывода применяется система ILP общего назначения.

За возможность применения мощного языка гипотез и разнообразных фоновых знаний в методе ILP приходится платить. Чем больше вариантов рассматривается в задаче обучения, тем выше становится комбинаторная сложность. Поэтому методы обучения на основе атрибутов и значений, например с использованием деревьев решения, являются намного более эффективными по сравнению с методом JLP.

В связи с этим по соображениям эффективности для решения таких задач обучения, для которых являются приемлемыми представления в виде атрибутов и значений, рекомендуется использовать методы обучения на основе атрибутов и значений.

В данной главе разрабатывается программа ILP, называемая HYPER (HYPothesis refinER), которая формирует программы Prolog путем постепенного усовершенствования некоторых начальных гипотез. Для иллюстрации основных идей вначале будет создана простая и малоэффективная версия этой программы, называемая MINTHYPER. Затем на ее основе будет разработана программа HYPER.

Часть II. Применение языка Prolog в области искусственного интеллекта

Рандомно подобранные статьи с сайта:

Различие между дедуктивным и индуктивным умозак-ем


Похожие статьи:

admin