Разработанный в 1990 году Россом Куинланом , [1] FOIL изучает безфункциональные предложения Хорна , подмножество исчисления предикатов первого порядка . Учитывая положительные и отрицательные примеры некоторой концепции и набор предикатов фоновых знаний , FOIL индуктивно генерирует логическое определение концепции или правило для этой концепции. Индуцированное правило не должно включать в себя какие-либо константы ( color(X,red) становится color(X,Y), red(Y) ) или функциональные символы, но может допускать отрицательные предикаты; рекурсивные концепции также можно изучить.
Как и алгоритм ID3 , FOIL поднимается на холм, используя метрику, основанную на теории информации , для построения правила, охватывающего данные. Однако, в отличие от ID3, FOIL использует метод «разделяй и властвуй», а не « разделяй и властвуй» , фокусируясь на создании одного правила за раз и сборе непокрытых примеров для следующей итерации алгоритма. [ нужна цитата ]
Предположим, что задача 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 показали, что дополнения к базовому алгоритму могут уменьшить это пространство поиска, иногда радикально. [ нужна цитата ]
Алгоритм FOCL [3] ( комбинированный обучающийся первого порядка ) расширяет FOIL различными способами, которые влияют на то, как FOCL выбирает литералы для проверки при расширении строящегося предложения . Допускаются ограничения на пространство поиска, а также предикаты, определенные на правиле, а не на наборе примеров (так называемые интенсиональные предикаты); самое главное, потенциально неверная гипотеза допускается в качестве начального приближения к изучаемому предикату. Основная цель FOCL — включить методы обучения на основе объяснений (EBL) в эмпирические методы FOIL.
Однако даже если FOCL не предоставляет дополнительных знаний по сравнению с FOIL, он использует стратегию итеративного расширяющего поиска, аналогичную поиску в глубину : сначала FOCL пытается изучить предложение, не вводя свободных переменных. Если это не удается (нет положительного выигрыша), допускается одна дополнительная свободная переменная за каждую ошибку до тех пор, пока количество свободных переменных не превысит максимум, используемый для любого предиката.