Индуктивное логическое программирование - Inductive logic programming

Индуктивное логическое программирование ( ILP ) - это подполе символического искусственного интеллекта, который использует логическое программирование как единое представление для примеров, базовых знаний и гипотез. С учетом кодирования известных фоновых знаний и набора примеров, представленных в виде логической базы данных фактов, система ILP выведет гипотетическую логическую программу, которая влечет за собой все положительные и ни одного отрицательные примеры.

  • Схема: положительные примеры + отрицательные примеры + базовые знаниягипотеза .

Индуктивное логическое программирование особенно полезно в биоинформатике и обработке естественного языка . Гордон Плоткин и Эхуд Шапиро заложили первоначальную теоретическую основу для индуктивного машинного обучения в логической среде. Шапиро построил свою первую реализацию (систему вывода моделей) в 1981 году: программу на языке Prolog, которая индуктивно выводила логические программы из положительных и отрицательных примеров. Термин « индуктивное логическое программирование» был впервые представлен в статье Стивена Магглетона в 1991 году. Магглетон также основал ежегодную международную конференцию по индуктивному логическому программированию, представил теоретические идеи изобретения предикатов, обратного разрешения и обратного следования. Muggleton первым реализовал обратный вывод в системе PROGOL . Термин « индуктивный » здесь относится к философской (то есть предлагающей теорию для объяснения наблюдаемых фактов), а не к математической (то есть к доказательству свойства для всех членов хорошо упорядоченного множества) индукции.

Формальное определение

Фоновые знания даются как теория логики B , обычно в виде Хорн , используемый в логическом программировании . Эти положительные и отрицательные примеры приведены в виде конъюнкции и из unnegated и инверсных наземных литералов , соответственно. Правильная гипотеза Н является логическим предложением , удовлетворяющий следующим требованиям.

« Необходимость » не накладывает ограничения на h , но запрещает любое создание гипотезы, если положительные факты объяснимы без нее. « Достаточность » требует, чтобы любая сгенерированная гипотеза h объясняла все положительные примеры . « Слабая согласованность » запрещает поколение любой гипотезы ч , что противоречит фоновым знаниям B . « Сильная согласованность » также запрещает генерировать любую гипотезу h, которая несовместима с отрицательными примерами , учитывая фоновые знания B ; это подразумевает « слабую последовательность »; если не приводятся отрицательные примеры, оба требования совпадают. Джероски требует только « Достаточность » (называемая там «Полнота») и « Сильная согласованность ».

Пример

Предполагаемые семейные отношения в разделе «Пример»

В следующем известном примере изучения определений семейных отношений используются сокращения

par : родитель , fem : женщина , dau : дочь , g : Джордж , h : Хелен , m : Мэри , t : Том , n : Нэнси и e : Ева .

Все начинается с базовых знаний (см. Рисунок)

,

положительные примеры

,

и тривиальное утверждение верно для обозначения отсутствия отрицательных примеров.

Подход Плоткина « относительное наименьшее общее обобщение (rlgg) » к индуктивному логическому программированию должен быть использован для получения предложения о том, как формально определить дочернее отношение dau .

В этом подходе используются следующие шаги.

  • Релятивизируйте каждый положительный пример в буквальном смысле с исчерпывающими базовыми знаниями:
    ,
  • Преобразовать в нормальную форму предложения :
    ,
  • Анти-унифицируйте каждую совместимую пару литералов:
    • из и ,
    • из и ,
    • из и ,
    • from и аналогично для всех других литералов фоновых знаний
    • from and , и многие другие отрицательные литералы
  • Удалите все отрицательные литералы, содержащие переменные, которых нет в положительном литерале:
    • после удаления всех инвертированных литералов, содержащих другие переменные , остается только вместе со всеми базовыми литералами из фоновых знаний
  • Преобразуйте предложения обратно в форму Horn:

Результирующее предложение Хорна является гипотезой h, полученной с помощью подхода rlgg. Игнорируя основные факты знания, предложение неофициально гласит: « называется дочерью того, если является родителем и является женщиной », что является общепринятым определением.

Что касается вышеуказанных требований, « Необходимость » была удовлетворена, потому что предикат dau не появляется в фоновых знаниях, что, следовательно, не может подразумевать какое-либо свойство, содержащее этот предикат, например, положительные примеры. « Достаточность » удовлетворяется вычисленной гипотезой h , поскольку она вместе с исходными знаниями подразумевает первый положительный пример , и аналогично h и фоновые знания подразумевают второй положительный пример . « Слабая согласованность » удовлетворяется h , поскольку h выполняется в (конечной) структуре Эрбранда, описываемой фоновыми знаниями; аналогично « Сильная консистенция ».

Общее определение отношения бабушки, а именно. , невозможно изучить с помощью описанного выше подхода, поскольку переменная y встречается только в теле предложения; соответствующие литералы были бы удалены на 4-м шаге подхода. Чтобы преодолеть этот недостаток, этот шаг необходимо изменить так, чтобы его можно было параметризовать с помощью различных буквальных эвристик после выбора . Исторически реализация GOLEM основана на подходе rlgg.

Система индуктивного логического программирования

Индуктивная логическое программирование системы представляет собой программу , которая принимает в качестве входных логических теорий и выводит правильную гипотезы H теории WRT Алгоритм системы ILP состоит из двух частей: поиск гипотез и выбор гипотез. Сначала выполняется поиск гипотезы с помощью процедуры индуктивного логического программирования, затем с помощью алгоритма выбора выбирается подмножество найденных гипотез (в большинстве систем одна гипотеза). Алгоритм выбора оценивает каждую из найденных гипотез и возвращает те, которые имеют наивысшую оценку. Пример функции оценки включает минимальную длину сжатия, когда гипотеза с наименьшей сложностью Колмогорова имеет наивысшую оценку и возвращается. Система ILP является завершенной, если и только если для любых теорий входной логики любая правильная гипотеза H относительно этих входных теорий может быть найдена с помощью ее процедуры поиска гипотезы.

Поиск гипотез

Современные ILP система , такая как Progol, Хэйл и Imparo найти гипотезу H , используя принцип обратного следования для теорий B , E , H : . Сначала они строят промежуточную теорию F, называемую теорией мостов, удовлетворяющую условиям и . Затем они обобщают отрицание теории моста F с антиследованием. Однако операция анти-следствия, поскольку она сильно недетерминирована, является более затратной в вычислительном отношении. Следовательно, поиск альтернативной гипотезы может быть проведен с использованием вместо этого операции обратного подчинения (анти-подчинения), которая менее недетерминирована, чем анти-влечение.

Возникают вопросы о полноте процедуры поиска гипотезы конкретной системы ПДОДИ. Например, процедура поиска гипотезы Прогола, основанная на правиле вывода обратного следования, не является полной на примере Ямамото . С другой стороны, Imparo завершается как процедурой предотвращения вовлечения, так и своей расширенной процедурой обратного подчинения.

Реализации

Смотрите также

использованная литература

дальнейшее чтение