Индуктивный ученик первого порядка - First-order inductive learner

В машинное обучение, индуктивный ученик первого порядка (ФОЛЬГА) - алгоритм обучения на основе правил.

Фон

Разработан в 1990 г. Росс Куинлан,^[1] FOIL учится без функциональности Роговые оговорки, подмножество исчисление предикатов первого порядка. Приведены положительные и отрицательные примеры некоторых концепций и набор фоновых знаний. предикаты, FOIL индуктивно генерирует логическое определение понятия или правило для этого понятия. Индуцированное правило не должно содержать никаких констант (цвет (X, красный) становится цвет (X, Y), красный (Y)) или функциональные символы, но могут допускать отрицательные предикаты; рекурсивные концепции также можно изучить.

Словно Алгоритм ID3, FOIL подъем на холм с использованием метрики, основанной на теория информации создать правило, охватывающее данные. Однако, в отличие от ID3, FOIL использует отделяй и властвуй метод, а не разделяй и властвуй, сосредотачиваясь на создании одного правила за раз и сборе непокрытых примеров для следующей итерации алгоритма.^{[нужна цитата ]}

Алгоритм

Алгоритм FOIL следующий:

Вход Список примеров

Вывод Правило в логике предикатов первого порядка

ФОЛЬГА (Примеры)

Позволять Поз быть положительным примером

Позволять Пред быть предикатом, который нужно выучить

До тех пор Поз пусто делать:

Позволять Отрицательный быть отрицательными примерами

Набор Тело опустошать

Вызов LearnClauseBody

Добавить Пред ← Тело к правилу

Удалить из Поз все примеры, удовлетворяющие Тело

Процедура LearnClauseBody

До тех пор Отрицательный пусто делать:

Выберите буквальный L

Присоединиться L к Тело

Удалить из Отрицательный примеры, которые не удовлетворяют L

пример

Предположим, задача FOIL - изучить концепцию дед (X, Y) учитывая отношения отец (X, Y) и родитель (X, Y). Кроме того, предположим, что наше текущее тело состоит из дед (X, Y) ← родитель (X, Z). Это можно расширить, объединив Body с любым из литералов отец (X, X), отец (Y, Z), родитель (U, Y)или многие другие - чтобы создать этот литерал, алгоритм должен выбрать как имя предиката, так и набор переменных для предиката (по крайней мере, одна из которых должна присутствовать уже в незавершенном литерале предложения). Если FOIL расширяет предложение дедушка (X, Y) ← верно соединяя буквальный родитель (X, Z), он вводит новую переменную Z. Положительные примеры теперь состоят из этих значений <X, Y, Z> такой, что дед (X, Y) правда и родитель (X, Z) правда; отрицательными примерами являются те, где дед (X, Y) правда, но родитель (X, Z) ложно.

На следующей итерации FOIL после родитель (X, Z) был добавлен, алгоритм будет рассматривать все комбинации имен предикатов и переменных, так что по крайней мере одна переменная в новом литерале присутствует в существующем предложении. Это приводит к очень большому пространству поиска.^[2] Несколько расширений теории FOIL показали, что дополнения к основному алгоритму могут сократить это пространство поиска, иногда значительно.^{[нужна цитата ]}

Расширения

В ВОЛС алгоритм^[3] (Комбинированный ученик первого порядка) расширяет FOIL множеством способов, которые влияют на то, как FOCL выбирает литералы для проверки при расширении строящегося предложения. Допускаются ограничения в пространстве поиска, как и предикаты, которые определены в правиле, а не в наборе примеров (называемых содержательный предикаты); самое главное, потенциально неверная гипотеза разрешается в качестве начального приближения к предикату, который нужно изучить. Основная цель ВОЛС - объединить методы обучение на основе объяснений (EBL) в эмпирические методы FOIL.

Однако даже когда FOCL не предоставляет дополнительных знаний по FOIL, он использует стратегию итеративного расширения поиска, аналогичную поиск в глубину: first FOCL пытается изучить предложение, не вводя свободных переменных. Если это не удается (нет положительного прироста), разрешается одна дополнительная свободная переменная на каждый сбой, пока количество свободных переменных не превысит максимальное значение, используемое для любого предиката.

Ограничения

В отличие от FOIL, который не накладывает ограничений на типизацию своих переменных, FOCL использует типизацию как недорогой способ включения простой формы базовых знаний. Например, предикат живет в (X, Y) может иметь типы живет в (человек, местоположение). Однако, возможно, потребуется ввести дополнительные предикаты - без типов, nextDoor (X, Y) может определить, действительно ли человек Икс и человек Y живут по соседству друг с другом, или два места находятся рядом друг с другом. С типами два разных предиката nextDoor (человек, человек) и nextDoor (расположение, расположение) необходимо, чтобы эта функциональность сохранялась. Однако этот механизм типизации устраняет необходимость в таких предикатах, как isPerson (X) или isLocation (Y), и не нужно учитывать живет в (А, В) когда А и B определены как личные переменные, что сокращает пространство поиска. Кроме того, набор текста может повысить точность результирующего правила, исключив из рассмотрения невозможные литералы, такие как живет в (А, В) который, тем не менее, может показаться высоким получение информации.

Вместо того, чтобы реализовывать тривиальные предикаты, такие как равно (X, X) или между (X, X, Y), FOCL вводит неявные ограничения на переменные, дополнительно сокращая пространство поиска. У одних предикатов все переменные должны быть уникальны, у других - коммутативность (смежный (X, Y) эквивалентно смежный (Y, X)), третьи могут потребовать, чтобы конкретная переменная присутствовала в текущем разделе, и многие другие потенциальные ограничения.

Правила работы

Операционные правила - это те правила, которые определены экстенсивно, или как список кортежей, для которых истинен предикат. FOIL допускает только рабочие правила; FOCL расширяет свою базу знаний, позволяя сочетать правила, называемые нерабочими правилами, а также частично определенные или неправильные правила для устойчивости. Разрешение частичных определений сокращает объем необходимой работы, поскольку алгоритм не должен генерировать эти частичные определения для себя, а неправильные правила не добавляют существенно к необходимой работе, поскольку они отбрасываются, если они не оцениваются как обеспечивающие положительный информационный прирост. Неоперационные правила выгодны, поскольку отдельные правила, которые они объединяют, могут не обеспечивать получение информации сами по себе, но полезны, когда используются вместе. Если литерал с наибольшим объемом информации в итерации FOCL не функционирует, он вводится в действие, и его определение добавляется в строящийся пункт.

Входы Буквальное введение в действие, Список положительных примеров, Список отрицательных примеров

Вывод Буквальный в операционной форме

Ввести в действие (буквальные, положительные примеры, отрицательные примеры)

Если Буквальный работает

Вернуть Буквальный

Инициализировать ОперационныеЛитералы в пустой набор

По каждому пункту определения Буквальный

Вычислить информационное преимущество предложения по сравнению с положительными примерами и отрицательными примерами

Для статьи с максимальным выигрышем

Для каждого буквального L в пункте

Добавить Operationalize (L, Положительные примеры, отрицательные примеры) ОперационныеЛитералы

Операционное правило может быть буквальным lessThan (X, Y); неработающее правило может быть между (X, Y, Z) ← lessThan (X, Y), lessThan (Y, Z).

Начальные правила

Добавление нерабочих правил в базу знаний увеличивает размер пространства, в котором должна проводиться поиск ВОЛС. Вместо того, чтобы просто предоставить алгоритму целевую концепцию (например, дед (X, Y)), алгоритм принимает в качестве входных данных набор нерабочих правил, которые он проверяет на правильность и реализует для своей изученной концепции. Правильная целевая концепция явно улучшит время вычислений и точность, но даже неправильная концепция даст алгоритму основу для работы и улучшит точность и время.^[3]