Индуктивное логическое программирование - 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 завершается как процедурой предотвращения вовлечения, так и своей расширенной процедурой обратного подчинения.
Реализации
- 1BC и 1BC2: наивные байесовские классификаторы первого порядка:
- ACE (комбинированный двигатель)
- Алеф
- Атом
- Claudien
- DL-Learner
- DMax
- FastLAS (быстрое обучение на основе наборов ответов)
- ФОЛЬГА (индуктивное обучение первого порядка)
- Голем
- ILASP (Индуктивное изучение программ с набором ответов)
- Imparo
- Inthelex (Ученик инкрементальной теории из примеров)
- Лайм
- Метагол
- Mio
- MIS (Система вывода моделей) Эхуда Шапиро
- ПРОГОЛ
- ОСБ
- Warmr (теперь входит в ACE)
- ProGolem
Смотрите также
- Здравый смысл
- Формальный анализ концепции
- Индуктивное мышление
- Индуктивное программирование
- Индуктивная вероятность
- Статистическое реляционное обучение
- Изучение пространства версий
использованная литература
дальнейшее чтение
- Muggleton, S .; Де Раэдт, Л. (1994). «Индуктивное логическое программирование: теория и методы» . Журнал логического программирования . 19–20: 629–679. DOI : 10.1016 / 0743-1066 (94) 90035-3 .
- Lavrac, N .; Дзероски, С. (1994). Индуктивное логическое программирование: методы и приложения . Нью-Йорк: Эллис Хорвуд. ISBN 978-0-13-457870-5. Архивировано из оригинала на 2004-09-06 . Проверено 22 сентября 2004 .
- Наглядный пример установления связи между дедушкой и бабушкой системой Atom . http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html