Введение

Индуктивное логическое программирование (ILP) — это подраздел символического искусственного интеллекта, использующий логическое программирование как единую форму представления для примеров, фоновых знаний и гипотез. Термин «индуктивный» здесь относится к философской (то есть предлагающей теорию для объяснения наблюдаемых фактов), а не к математической (то есть доказывающей свойство для всех элементов хорошо упорядоченного множества) индукции. Получив кодировку известных фоновых знаний и набор примеров, представленных в виде логической базы данных фактов, ILP-система выводит гипотетическую логическую программу, которая логически следует из всех положительных примеров и не следует ни из одного отрицательного примера. Схема: положительные примеры + отрицательные примеры + фоновые знания ⇒ гипотеза. Индуктивное логическое программирование особенно полезно в биоинформатике и обработке естественного языка.

История

Основываясь на более ранних работах по индуктивному выводу, Гордон Плоткин первым формализовал индукцию в клаузальной форме около 1970 года, приняв подход обобщения из примеров. В 1981 году Эхуд Шапиро представил несколько идей, которые сформировали эту область в своем новом подходе к выводу моделей – алгоритме, использующем уточнение и обратный проход для поиска полной аксиоматизации заданных примеров. Его первой реализацией стала система вывода моделей в 1981 году: программа на Prolog, которая индуктивно выводила логические программы на основе клауз Хорна из положительных и отрицательных примеров. В начале 1990-х годов появилось несколько влиятельных систем индуктивного логического программирования. FOIL, представленный Россом Квинланом в 1990 году, основывался на усовершенствовании алгоритмов обучения AQ и ID3. Golem, представленный Мугглтоном и Фенгом в 1990 году, вернулся к ограниченной форме алгоритма наименьшего обобщения Плоткина. Система Progol, представленная Мугглтоном в 1995 году, впервые реализовала обратную логическую зависимость и вдохновила множество последующих систем. Aleph, потомок Progol, представленный Ашвином Шринивасаном в 2001 году, до сих пор является одной из наиболее широко используемых систем по состоянию на 2022 год. В отличие от ориентации на автоматическое программирование, свойственной ранним работам, в этих областях использовались методы индуктивного логического программирования с точки зрения реляционного извлечения данных. Успех этих первоначальных приложений и отсутствие прогресса в восстановлении более крупных традиционных логических программ определили фокус этой области. В последнее время классические задачи автоматизированного программирования вновь оказались в центре внимания, поскольку введение метаинтерпретативного обучения делает изобретение предикатов и обучение рекурсивным программам более осуществимым. Эта техника была впервые применена в системе Metagol, представленной Мугглтоном, Дианхуаном Линем, Нильсом Пахлави и Алирезой Тамаддони Нежадом в 2014 году. Это позволяет системам ILP работать с меньшим количеством примеров и принесло успехи в обучении программам преобразования строк, грамматикам множеств ответов и общим алгоритмам.

Обстановка

Индуктивное логическое программирование использует несколько различных сценариев обучения, наиболее распространенными из которых являются обучение на основе логического следования и обучение на основе интерпретаций. В обоих случаях входные данные предоставляются в виде фоновых знаний B, логической теории (обычно в форме клауз, используемых в логическом программировании), а также положительных и отрицательных примеров, обозначаемых + и – соответственно. Выход представляется в виде гипотезы H, которая сама является логической теорией и обычно состоит из одной или нескольких клауз. Эти два сценария различаются форматом представления примеров.

Учиться на примере

С 2022 года обучение на основе логического следования является наиболее распространенным подходом в индуктивном логическом программировании. Полнота требует, чтобы любая сгенерированная гипотеза h объясняла все положительные примеры, а согласованность запрещает генерацию любой гипотезы h, несовместимой с отрицательными примерами, при наличии базовых знаний B. В постановке концептуального обучения Мугглтона "полнота" называется "достаточностью", а "согласованность" – "сильной согласованностью". Добавляются еще два условия: "Необходимость", которая постулирует, что B не выводит , не накладывает ограничений на h, но запрещает генерацию гипотезы, если положительные факты объяснимы без нее. "Слабая согласованность", которая утверждает, что из не должно следовать противоречие, запрещает генерацию любой гипотезы h, противоречащей базовым знаниям B. Слабая согласованность вытекает из сильной согласованности; если отрицательные примеры не заданы, оба требования совпадают. Слабая согласованность особенно важна при работе с зашумленными данными, где полнота и сильная согласованность не могут быть гарантированы. Используемые методы включают наименее общую генерализацию, основанную на антиунификации, и обратное разрешение, основанное на инверсии правила вывода разрешения.

Наименьшее обобщение

Алгоритм наименее общего обобщения принимает на вход два клаузы и и выдает наименее общее обобщение и , то есть клаузу , которая субумирует и , и которая субумируется каждой другой клаузой, субумирующей и . Наименее общее обобщение можно вычислить, сначала вычислив все селекции из и , которые являются парами литералов, имеющих один и тот же символ предиката и статус отрицания/неотрицания. Затем наименее общее обобщение получается как дизъюнкция наименее общих обобщений отдельных селекций, которые могут быть получены с помощью синтаксической антиунификации первого порядка. Для учета фоновых знаний индуктивные системы логического программирования используют относительно наименее общие обобщения, которые определяются с точки зрения субумпции относительно фоновой теории. В общем случае, такие относительные наименее общие обобщения не гарантированно существуют; однако, если фоновая теория B является конечным множеством заземленных литералов, то отрицание B само по себе является клаузой. В этом случае относительное наименее общее обобщение можно вычислить, дизъюнктивно объединив отрицание B с обеими клаузами и , а затем вычислив их наименее общее обобщение, как и раньше. Относительно наименее общие обобщения являются основой системы Golem, работающей снизу вверх. Инверсная резолюция была впервые представлена Стивеном Магглетоном и Рэйем Бантином в 1988 году для использования в индуктивной логической системе программирования Cigol. Imparo находят гипотезу H, используя принцип обратной импликации. Однако операция антиимпликации вычислительно более затратна, поскольку она сильно недетерминирована. Поэтому альтернативный поиск гипотез может быть проведен с использованием операции обратной субумпции (антисубсумпции), которая менее недетерминирована, чем антиимпликация. Возникают вопросы о полноте процедуры поиска гипотез конкретной индуктивной логической системы программирования. Например, процедура поиска гипотез Progol, основанная на правиле обратной импликации, не является полной, как показано на примере Ямамото. С другой стороны, Imparo является полной как по процедуре антиимпликации, так и по ее расширенной процедуре обратной субумпции.

Метаинтерпретирующее обучение

Вместо явного поиска в графе гипотез, метаинтерпретирующие или метауровневые системы кодируют программу индуктивного логического программирования в логическую программу метауровня, которая затем решается для получения оптимальной гипотезы. Формализмы, используемые для выражения спецификации задачи, включают Prolog и программирование на основе множеств ответов (answer set programming), при этом существующие системы Prolog и решатели для множеств ответов используются для решения ограничений. Примером системы на основе Prolog является Metagol, которая построена на метаинтерпретаторе в Prolog, а ASPAL и ILASP основаны на кодировании задачи индуктивного логического программирования в программировании на основе множеств ответов.