Открыть сервисСервис

Индуктивно-связанная логика

Индуктивно-связанная логика (ИЛ, англ. Inductive Logic Programming, ILP) — направление машинного обучения и логического программирования, в котором из набора примеров (положительных и отрицательных) и фонового знания автоматически выводятся логические программы, обычно в форме правил на языке логики первого порядка. ИЛ сочетает методы индуктивного вывода с механизмами логического вывода, что позволяет моделировать сложные зависимости между объектами, отношениями и свойствами, недоступные для традиционного статистического обучения.

Основные понятия

В индуктивно-связанной логике задача обучения формулируется как поиск гипотезы — логической программы H — такой, что H вместе с фоновым знанием K объясняет все положительные примеры и не противоречит отрицательным. Формально: K ∧ H ⊨ e⁺ для всех положительных примеров e⁺ и K ∧ H ⊭ e⁻ для отрицательных.

Ключевые компоненты задачи ИЛ:

  • Фоновое знание (background knowledge) — набор фактов и правил, известных заранее и используемых при выводе (например, «родитель — это отец или мать»);
  • Положительные примеры — описания объектов или отношений, которые гипотеза должна объяснять;
  • Отрицательные примеры — описания, которые гипотеза не должна объяснять;
  • Гипотеза — искомая логическая программа, обычно в виде набора правил первого порядка.

Методы поиска гипотез

Основные алгоритмы ИЛ делятся на две группы: поиск по субгипотезам (поиск в пространстве гипотез) и поиск по моделям (поиск в пространстве интерпретаций).

Поиск по субгипотезам

Классический алгоритм — FOIL (First Order Inductive Learner, 1990, Рон Куми, Тим О’Нилл). Он строит правила пошагово, расширяя антецедент правила так, чтобы покрыть как можно больше положительных примеров и не затронуть отрицательных. Критерий выбора расширения — информационный выигрыш, аналогичный приросту информации в деревьях решений.

Другой известный алгоритм — Progol (Стив Мугглтон, 1995), использующий режимное обобщение (mode-directed inverse entailment). Progol строит компактные гипотезы, минимизируя сложность программы при объяснении примеров.

Поиск по моделям

Алгоритмы ALEPH и АЛЕФ (Софи Лаврач, 1998) и Golem (Ясухиро Мори, 1994) строят гипотезы, вычисляя минимальные покрытия отрицательных примеров. Golem использует алгоритм минимальных покрытий (Minimal Model Construction), основанный на идее, что гипотеза должна быть минимальной по объяснению.

Языки представления

ИЛ традиционно работает с логикой первого порядка, однако существуют варианты, использующие логику второго порядка, индуктивную логику Дэвида Пирса (1991) и вероятностные расширения — Probabilistic ILP (PILP), где гипотезы снабжаются вероятностными весами.

Ряд систем использует аналоговый вывод (analogical reasoning), где гипотезы строятся по аналогии с уже известными примерами. К таким системам относятся Аналогия (Маргарет Митчелл, 1993) и Аналогия-2 (Джонатан Лавин, 2004).

Применение

ИЛ применяется в задачах, где важны отношения между объектами и структурные зависимости:

  • Биоинформатика — выявление закономерностей в структурах белков и ДНК, предсказание функций генов;
  • Химия — предсказание свойств молекул на основе их структуры (QSAR-модели);
  • Обработка естественного языка — извлечение правил грамматики и семантических зависимостей;
  • Анализ данных — обнаружение закономерностей в базах данных и графах знаний.

Связь с другими направлениями

ИЛ пересекается с объяснимым искусственным интеллектом (Explainable AI, XAI), поскольку гипотезы в форме логических правил легко интерпретируются человеком. В отличие от «чёрных ящиков» — нейронных сетей — модели ИЛ предоставляют прозрачное объяснение принятого решения.

ИЛ также связан с обучением с подкреплением и обучением на основе прецедентов (case-based reasoning), где аналогичные задачи решаются на основе сходства с ранее решёнными.

Критика и ограничения

Основные ограничения ИЛ — вычислительная сложность поиска в пространстве гипотез (задача NP-полна в общем случае) и чувствительность к шуму в данных. Кроме того, качество гипотез сильно зависит от выбора фонового знания и языка представления.

Источники

  • Muggleton S. Inductive Logic Programming // New Generation Computing. 1991.
  • Lavrac N., Dzeroski S. Inductive Logic Programming: Techniques and Applications. — Ellis Horwood, 1997.
  • Quinlan J. R. Learning Logical Definitions from Relations // Machine Learning. 1990.
  • De Raedt L. Logical and Relational Learning. — Springer, 2008.
Заметили ошибку или не согласны с информацией в статье? Напишите нам support@bfometr.ru