Индуктивное логическое программирование (ILP ) - это подполе символического искусственного интеллекта, который использует логическое программирование как единое представление для примеров, базовых знаний и гипотез. С учетом кодирования известных исходных знаний и набора примеров, представленных в виде логической базы данных фактов, система ILP будет выводить гипотетическую логическую программу, которая влечет за собой все положительное и ничего из отрицательные примеры.
- Схема: положительные примеры + отрицательные примеры + базовые знания ⇒ гипотеза.
Индуктивное логическое программирование особенно полезно в биоинформатике и обработке естественного языка. Гордон Плоткин и Эхуд Шапиро заложили первоначальную теоретическую основу для индуктивного машинного обучения в логической среде. Шапиро построил свою первую реализацию (Model Inference System) в 1981 году: программу Prolog, которая индуктивно выводила логические программы из положительных и отрицательных примеров. Термин «индуктивное логическое программирование» был впервые представлен в статье Стивена Магглетона в 1991 году. Магглетон также основал ежегодную международную конференцию по индуктивному логическому программированию, представил теоретические идеи изобретения предикатов, Обратное разрешение, и обратное следствие. Muggleton первым реализовал обратное следование в системе PROGOL. Термин «индуктивный» здесь относится к философской (т. Е. Предложению теории для объяснения наблюдаемых фактов), а не к математической (т. Е. К доказательству свойства для всех членов хорошо упорядоченного множества) индукции..
Содержание
- 1 Формальное определение
- 2 Пример
- 3 Система индуктивного логического программирования
- 3.1 Поиск гипотез
- 3.2 Реализации
- 4 См. Также
- 5 Ссылки
- 6 Далее чтение
Формальное определение
Базовые знания даются в виде теории логики B, обычно в форме предложений Хорна, используемых в логическом программировании. Положительный и отрицательный примеры даны как союз и незадействованных и инвертированных ground литералов соответственно. Правильная гипотеза h - это логическое предложение, удовлетворяющее следующим требованиям.
-
«Необходимость» не налагает ограничения на h, но запрещает любое создание гипотезы, пока положительные факты объяснимы и без него. «Достаточность» требует, чтобы любая сгенерированная гипотеза h объясняла все положительные примеры . «Слабая согласованность» запрещает создание любой гипотезы h, которая противоречит фоновым знаниям B. «Сильная согласованность» также запрещает создание любой гипотезы h, которая несовместима с отрицательными примерами , учитывая базовые знания B; это подразумевает «Слабую последовательность»; если не приводятся отрицательные примеры, оба требования совпадают. Джероски требует только «Достаточность» (называемая там «Полнота») и «Сильная согласованность».
Пример
Предполагаемые семейные отношения в разделе «Пример»
В следующем хорошо известном примере изучения определений семейных отношений используются сокращения
- par: parent, fem: female, dau: дочь., g: Джордж, h: Хелен, m: Мэри, t: Том, n: Нэнси и e: Ева.
Все начинается с базовых знаний (см. рисунок)
- ,
положительные примеры
- ,
и тривиальное утверждение истинно для обозначения отсутствия отрицательных примеров.
Для получения предложения о том, как формально определить дочернее отношение dau, следует использовать подход Плоткина к индуктивному логическому программированию "относительного наименьшего общего обобщения (rlgg)".
В этом подходе используются следующие шаги.
- Релятивизируйте каждый положительный пример литерала с полным базовым знанием:
- ,
- Преобразовать в нормальную форму предложения :
- ,
- Анти-унификация каждая совместимая пара литералов:
- из и ,
- из и ,
- из и ,
- из и , аналогично для всех других литералов фоновых знаний
- из и и многие другие отрицательные литералы
- Удалите все отрицательные литералы, содержащие переменные, которые не встречаются в положительный литерал:
- после удаления всех отрицательных литералов, содержащих другие переменные, кроме , только остается вместе со всеми наземными литералами из фоновых знаний
- Преобразовать предложения обратно в форму Рога:
Результирующее предложение Хорна - это гипотеза h, полученная с помощью подхода rlgg. Игнорируя фоновые факты знаний, предложение неофициально гласит: «называется дочерью , если является родительским для и - женский ", что является общепринятым определением.
Что касается требований выше, «Необходимость» была удовлетворена, поскольку предикат dau не появляется в фоновых знаниях, что, следовательно, не может подразумевать какое-либо свойство, содержащее этот предикат, например положительные примеры находятся. «Достаточность» удовлетворяется вычисленной гипотезой h, поскольку она вместе с из базовых знаний подразумевает первый положительный пример , и аналогично h и из базовых знаний подразумевает второй положительный пример . «Слабая согласованность» удовлетворяется h, поскольку h выполняется в (конечной) структуре Эрбранда, описанной фоновыми знаниями; аналогично «Сильная консистенция».
Распространенное определение отношения бабушки, а именно. , не может быть изучен с использованием вышеуказанного подхода, поскольку переменная y встречается только в теле предложения; соответствующие литералы были бы удалены на 4-м шаге подхода. Чтобы преодолеть этот недостаток, этот шаг необходимо модифицировать так, чтобы его можно было параметризовать с помощью различных буквальных эвристик после выбора. Исторически реализация GOLEM основана на подходе rlgg.
Система индуктивного логического программирования
Система индуктивного логического программирования - это программа, которая принимает в качестве входных логических теорий и выводит правильную гипотезу H относительно теорий Алгоритм системы ILP состоит из двух частей: поиска гипотезы и выбора гипотезы. Сначала выполняется поиск гипотезы с помощью процедуры индуктивного логического программирования, затем подмножество найденных гипотез (в большинстве систем одна гипотеза) выбирается алгоритмом выбора. Алгоритм выбора оценивает каждую из найденных гипотез и возвращает те, которые имеют наивысшую оценку. Пример функции оценки включает минимальную длину сжатия, когда гипотеза с наименьшей сложностью Колмогорова имеет наивысшую оценку и возвращается. Система ILP является полной, если для любых теорий входной логики любая правильная гипотеза H относительно эти теории ввода можно найти с помощью процедуры поиска гипотез.
Поиск гипотез
Современные системы ILP, такие как Progol, Hail и Imparo, находят гипотезу H, используя принцип обратного следования теорий B, E, H: . Сначала они создают промежуточную теорию F, называемую теорией мостов, удовлетворяющую условиям и . Затем, как , они обобщают отрицание теории моста F с анти-следствием. Однако операция анти-следствия, поскольку она сильно недетерминирована, требует больших вычислительных затрат. Следовательно, поиск альтернативной гипотезы может быть проведен с использованием операции обратного подчинения (анти-подчинения), которая менее недетерминирована, чем анти-влечение.
Возникают вопросы полноты процедуры поиска гипотезы конкретной системы ПДОДИ. Например, процедура поиска гипотезы Прогола, основанная на правиле вывода обратного следования, не завершается в примере Ямамото . С другой стороны, Imparo завершается как процедурой предотвращения вовлечения, так и своей расширенной процедурой обратного подчинения.
Реализации
См. Также
Ссылки
Дополнительная литература