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

Индуктивное логическое программирование — это один из подходов к машинному обучению. Оно представляет собой метод изучения отношений на примерах. В методе 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< X_r Y), female (Y>.

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

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

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

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

Дано:

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

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 в области искусственного интеллекта