Индуктивный обучающийся первого порядка

В машинном обучении индуктивный обучающийся первого порядка ( FOIL ) представляет собой алгоритм обучения, основанный на правилах.

Фон

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

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

Алгоритм

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

Входной список примеров и предикатов, которые необходимо выучить.

Выходные данные Набор предложений Хорна первого порядка.

ФОЛЬГА( Pred , Pos , Neg )

Пусть Pos будет положительным примером.

Пусть Pred будет предикатом, который нужно выучить.

Пока Pos не станет пустым, выполните:

Пусть Neg будет отрицательным примером.

Установить тело пустым

Вызов LearnClauseBody

Добавить Pred ← Body в правило

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

Процедура LearnClauseBody

Пока Neg не станет пустым, выполните:

Выберите букву Л

Соедините L с телом

Удалить из Neg примеры, не удовлетворяющие L

Пример

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

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

Комбинированный обучающийся первого порядка

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

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

Ограничения

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

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

Правила эксплуатации

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

Входные данные Литерал для использования, Список положительных примеров, Список отрицательных примеров

Выходной литерал в оперативной форме

Операционализация (буквальный, Положительные примеры, Отрицательные примеры)

Если Литерал работает

Возвратный литерал

Инициализируйте OperationalLiterals пустым набором

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

Рассчитайте информационную выгоду предложения по положительным и отрицательным примерам.

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

Для каждого литерала L в предложении

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

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

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

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

Ссылки

http://www.csc.liv.ac.uk/~frans/KDD/Software/FOIL_PRM_CPAR/foil.html

^ Дж. Р. Куинлан. Изучение логических определений из отношений. Машинное обучение, том 5, номер 3, 1990 г. [1]
^ Пусть Var будет наибольшим количеством различных переменных для любого предложения в правиле R , исключая последнее соединение. Пусть MaxP — количество предикатов с наибольшей арностью MaxA . Тогда приблизительное количество узлов, сгенерированных для изучения R, равно: NodesSearched ≤ 2 * MaxP * (Var + MaxA – 1). ^МаксА, как показано Паццани и Киблер (1992).
^ Перейти обратно: ^а ^б Майкл Паццани и Деннис Киблер. Полезность знаний в индуктивном обучении. Машинное обучение, том 9, номер 1, 1992 г. [2]

[Quinlan1990-1] Дж. Р. Куинлан. Изучение логических определений из отношений. Машинное обучение, том 5, номер 3, 1990 г. [1]

[2] Пусть Var будет наибольшим количеством различных переменных для любого предложения в правиле R , исключая последнее соединение. Пусть MaxP — количество предикатов с наибольшей арностью MaxA . Тогда приблизительное количество узлов, сгенерированных для изучения R, равно: NodesSearched ≤ 2 * MaxP * (Var + MaxA – 1). ^МаксА, как показано Паццани и Киблер (1992).

[Pazzani-3] Перейти обратно: ^а ^б Майкл Паццани и Деннис Киблер. Полезность знаний в индуктивном обучении. Машинное обучение, том 9, номер 1, 1992 г. [2]

[1]

[2]

[3]