Нисходящие методы индуктивного обучения

Описанный здесь первый подход к индуктивному логическому программированию начинается с получения очень общего правила и его постепенного уточнения для достижения соответствия с данными. По сути такой же процесс происходит при обучении деревьев решений, когда дерево решений постепенно наращивается до тех пор, пока не становится совместимым с результатами наблюдений. Но для осуществления индуктивного логического программирования вместо атрибутов используются литералы первого порядка, а вместо дерева решений рассматриваются гипотезы, представляющие собой множества выражений. В этом разделе рассматривается программа Foil [1258], одна из первых программ ILP.
Предположим, что предпринимается попытка изучить определение предиката Grandfather (х,у) с использованием тех же данных о семейных отношениях, как и перед этим. По такому же принципу, как и при обучении деревьев решений, эти примеры можно разделить на положительные и отрицательные. Положительными примерами являются следующие:
{George, Anne), (Philip, Peter), {Spencer, Harry), ... а отрицательными — такие примеры:
{George, Elizabeth), {Harry, Zara), {Charles, Philip), ...
Обратите внимание на то, что каждый пример представляет собой пару объектов, поскольку Grandfather — это бинарный предикат. В целом в данном генеалогическом дереве имеется 12 положительных примеров и 388 отрицательных (все прочие пары людей).
Программа Foil строит множества выражений, в каждом из которых Grandfather (х, у) является головой предиката. Эти выражения должны классифицировать 12 положительных примеров как экземпляры отношения Grandfather{xry) и вместе с тем исключать 388 отрицательных примеров. Рассматриваемые выражения являются хорновскими выражениями, расширенными с помощью отрицаемых литералов, в которых используется отрицание как недостижение цели, по аналогии с языком Prolog. Первоначальное выражение имеет такое пустое тело:
=> Grandfather{х,у)
Это выражение классифицирует каждый пример как положительный, поэтому требует уточнения. Такую операцию можно выполнить, каждый раз вводя по одному литералу в левую часть выражения. Ниже перечислены три возможных дополнения.
Father{х,у) r=> Grandfather(xfy) Parent {х, z) => Grandfather{x,y) Father{x,z) => Grandfather {x, y)
(Обратите внимание на то, что здесь предполагается, будто выражение, определяющее предикат Parent, уже является частью фоновых знаний.) Первое из этих трех выражений неправильно классифицирует все 12 положительных примеров как отрицательные и поэтому может быть проигнорировано. Второе и третье выражения согласуются со всеми положительными примерами, но второе является неправильным применительно к большей части отрицательных примеров (этих примеров вдвое больше, чем в первом случае, поскольку в них допускается произвольная подстановка данных и о матерях, и об отцах). Поэтому предпочтительным является третье выражение.
Теперь необходимо дополнительно уточнить это выражение, чтобы исключить те случаи, в которых хявляется отцом некоторого z, но z не является родителем у. Добавление единственного литерала Parent (z,y) позволяет получить следующее выражение, которое правильно классифицирует все примеры:
Father{х,z) л Parent(z,у) => Grandfather{х,у)
Программа Foil способна найти и выбрать этот литерал, решая тем самым задачу обучения. Вообще говоря, программе Foil обычно приходится выполнять поиск среди многих неподходящих выражений, прежде чем она сможет найти правильное решение.
Этот пример может служить очень простой иллюстрацией того, как действует программа Foil. Набросок общего алгоритма этой программы приведен в листинге 19.4. По существу, алгоритм повторно составляет выражение, вводя в него один литерал за другим до тех пор, пока это выражение не начинает согласовываться с некоторым подмножеством положительных примеров и при этом не согласуется ни с одним отрицательным примером. Затем положительные примеры, охваченные данным выражением, удаляются из обучающего множества и процесс продолжается до тех пор, пока не остается ни одного положительного примера. Двумя основными процедурами, требующими пояснения, являются New-Literals, которая создает все возможные новые литералы для добавления к выражению, и Choose-Literal, которая выбирает литерал для добавления.
Листинг 19.4. Набросок алгоритма Foil, применяемого для изучения множеств хорновских выражений первого порядка на основе примеров. Функции New-Literals и Choose-Literal описаны в тексте
function Foil(examples, target) returns множество хорновских выражений inputs: examples, множество примеров
target, литерал для целевого предиката local variables: clauses, множество выражений, первоначально пустое
while множество examples содержит положительные примеры do
clause <— New-Clause(examples, target)
удалить примеры, охваченные выражением clause, из множества examples
добавить выражение clause к множеству clauses return clauses
function New-CIause(examples, target) returns хорновское выражение local variables: clause, выражение, головой которого является
target, а тело пусто 1, литерал, который должен быть добавлен
к выражению clause extended_examples, множество примеров со
значениями для новых переменных
extended_examples <— examples
while extended_examples содержат отрицательные примеры do
1 <— Choose-Literal(New-Literals(clause), extended_examples) добавить 1 к телу выражения clause
extended_examples <— множество примеров, созданных путем применения функции Extend-Example к каждому примеру в множестве ex t en ded_exampl es
return clause
function Extend-Example(example, literal) returns множество примеров if пример example согласуется с литералом literal
then return множество примеров, созданное путем дополнения примера example каждым возможным значением константы для каждой новой переменной в литерале literal
else return пустое множество
Процедура New-Literals выбирает некоторое выражение и составляет все возможные "полезные" литералы, которые могут быть добавлены к этому выражению. Рассмотрим в качестве примера следующее выражение:
Father(x,z) => Grandfather(х,у)
К нему могут быть добавлены три описанные ниже разновидности литералов.
1. Литералы, в которых используются предикаты. Литерал может быть отрицаемым или неотрицаемым, в нем может применяться любой существующий предикат (включая целевой предикат), а все параметры должны быть переменными. В качестве любого параметра предиката может использоваться любая переменная, с учетом одного ограничения: каждый литерал должен включать по меньшей мере одну переменную из предыдущего литерала или из головы выражения. Такие литералы, как Mother(z,u), Married(z,у), -лКа1е (у) и Grand fa ther (v, x), являются допустимыми, a Marri ed(u,v) — нет. Обратите внимание на то, что благодаря имеющейся возможности применять предикат из головы выражения программа Foil может использоваться для изучения рекурсивных определений.
2. Литералы равенства и неравенства. Эти литералы связывают переменные, уже присутствующие в данном выражении. Например, можно ввести литерал zx. Данные литералы могут также включать константы, заданные пользователем. Для изучения арифметических выражений могут использоваться константы 0 и 1, а для изучения функций, заданных на списках, — пустой список [ ].
3. Арифметические сравнения. При обработке функций непрерывных переменных могут быть добавлены такие литералы, как х>у и y Возникающий в результате коэффициент ветвления в этом пространстве поиска очень велик (см. упр. 19.6), но в программе Foil для его уменьшения может также использоваться информация о типе. Например, если проблемная область включает
данные не только о числах, но и о людях, то ограничения типов позволят исключить возможность выработки в процедуре New-Literals таких литералов, как Paren t (х, п), где х — человек, ал — число.
В процедуре Choose-Literal используется эвристика, немного напоминающая эвристику, основанную на приросте информации (см. с. 878), для определения того, какой литерал должен быть выбран для добавления. Точные сведения о том, как это осуществляется, не имеет в контексте данной главы слишком большого значения, к тому же было опробовано много различных вариантов таких эвристик. Одно интересное дополнительное средство программы Foil состоит в использовании принципа бритвы Оккама для устранения некоторых гипотез. Если некоторое выражение становится длиннее (согласно определенной метрике), чем общая длина положительных примеров, объясняемых с помощью этого выражения, оно больше не рассматривается в качестве потенциальной гипотезы. Такой метод предоставляет удобный способ предотвращения создания чрезмерно сложных выражений, которые обусловлены наличием шума в данных. Объяснение связи между шумом и длиной выражений приведено на с. 949.
Программа Foil и аналогичные ей программы использовались для изучения широкого ряда определений. Одна из наиболее впечатляющих демонстраций возможностей таких программ [1260] касалась решения длинной последовательности упражнений по функциям обработки списков из учебника по языку Prolog, написанного Братко [174]. В каждом случае программа показала свою способность найти в процессе обучения правильное определение функции на основе небольшого множества примеров, используя в качестве фоновых знаний ранее изученные функции.







Материалы

Яндекс.Метрика