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

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

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

Индуктивное логическое программирование особенно полезно в биоинформатика и обработка естественного языка. Гордон Плоткин и Эхуд Шапиро заложил первоначальную теоретическую основу индуктивного машинного обучения в логической среде.^[1][2][3] Шапиро построил свою первую реализацию (систему вывода моделей) в 1981 году:^[4] а Пролог программа, которая индуктивно выводила логические программы из положительных и отрицательных примеров. Период, термин Индуктивное логическое программирование был впервые представлен^[5] в статье Стивен Магглетон в 1991 г.^[6] Магглетон также основал ежегодную международную конференцию по индуктивному логическому программированию, представил теоретические идеи изобретения предикатов, Обратное разрешение,^[7] и обратное следствие.^[8] Muggleton первым реализовал обратный вывод в ПРОГОЛ система. Период, термин "индуктивный"здесь относится к философский (т.е. предлагая теорию для объяснения наблюдаемых фактов), а не математический (то есть доказательство свойства для всех элементов упорядоченного множества) индукция.

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

В жизненный опыт дается как логическая теория B, обычно в виде Роговые оговорки используется в логическое программирование. положительный и отрицательный примеры даны как союз ${\displaystyle E^{+}}$ и ${\displaystyle E^{-}}$ незащищенных и отрицаемых земля литералы соответственно. правильная гипотеза час является логическим предложением, удовлетворяющим следующим требованиям.^[9]

${\displaystyle {\begin{array}{llll}{\text{Necessity:}}&B&\not \models &E^{+}\\{\text{Sufficiency:}}&B\land h&\color {blue}{\models }&E^{+}\\{\text{Weak consistency:}}&B\land h&\not \models &{\textit {false}}\\{\text{Strong consistency:}}&B\land h\land E^{-}&\not \models &{\textit {false}}\end{array}}}$

"Необходимость"не накладывает ограничения на час, но запрещает любое создание гипотез, если без нее можно объяснить положительные факты ".Достаточность"требуется любая выдвинутая гипотеза час объяснить все положительные примеры ${\displaystyle E^{+}}$."Слабая консистенция"запрещает выдвижение любых гипотез час что противоречит базовым знаниям B."Сильная консистенция"также запрещает выдвигать какие-либо гипотезы час это несовместимо с отрицательными примерами ${\displaystyle E^{-}}$, учитывая базовые знания B; это подразумевает "Слабая консистенция"; если не приводятся отрицательные примеры, оба требования совпадают. Джероски ^[10] требуется только "Достаточность"(там называется" Полнота ") и"Сильная консистенция".

Пример

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

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

номинал: родитель, женщина: женский, Дау: дочь, грамм: Джордж, час: Хелен, м: Мэри, т: Том, п: Нэнси, и е: канун.

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

${\displaystyle {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)}$,

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

${\displaystyle {\textit {dau}}(m,h)\land {\textit {dau}}(e,t)}$,

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

Плоткина ^[11][12] "относительное наименьшее общее обобщение (rlgg)" подход к индуктивное логическое программирование будет использоваться для получения предложения о том, как формально определить дочернее отношение Дау.

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

• Релятивизируйте каждый положительный пример в буквальном смысле с полным базовым знанием:

  ${\displaystyle {\begin{aligned}{\textit {dau}}(m,h)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\\{\textit {dau}}(e,t)\leftarrow {\textit {par}}(h,m)\land {\textit {par}}(h,t)\land {\textit {par}}(g,m)\land {\textit {par}}(t,e)\land {\textit {par}}(n,e)\land {\textit {fem}}(h)\land {\textit {fem}}(m)\land {\textit {fem}}(n)\land {\textit {fem}}(e)\end{aligned}}}$,

• Конвертировать в пункт нормальная форма:

  ${\displaystyle {\begin{aligned}{\textit {dau}}(m,h)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\\{\textit {dau}}(e,t)\lor \lnot {\textit {par}}(h,m)\lor \lnot {\textit {par}}(h,t)\lor \lnot {\textit {par}}(g,m)\lor \lnot {\textit {par}}(t,e)\lor \lnot {\textit {par}}(n,e)\lor \lnot {\textit {fem}}(h)\lor \lnot {\textit {fem}}(m)\lor \lnot {\textit {fem}}(n)\lor \lnot {\textit {fem}}(e)\end{aligned}}}$,

• Анти-унифицировать каждый совместимый ^[13] пара ^[14] литералов:
  • ${\displaystyle {\textit {dau}}(x_{me},x_{ht})}$ из ${\displaystyle {\textit {dau}}(m,h)}$ и ${\displaystyle {\textit {dau}}(e,t)}$,
  • ${\displaystyle \lnot {\textit {par}}(x_{ht},x_{me})}$ из ${\displaystyle \lnot {\textit {par}}(h,m)}$ и ${\displaystyle \lnot {\textit {par}}(t,e)}$,
  • ${\displaystyle \lnot {\textit {fem}}(x_{me})}$ из ${\displaystyle \lnot {\textit {fem}}(m)}$ и ${\displaystyle \lnot {\textit {fem}}(e)}$,
  • ${\displaystyle \lnot {\textit {par}}(g,m)}$ из ${\displaystyle \lnot {\textit {par}}(g,m)}$ и ${\displaystyle \lnot {\textit {par}}(g,m)}$, аналогично для всех других литералов фоновых знаний
  • ${\displaystyle \lnot {\textit {par}}(x_{gt},x_{me})}$ из ${\displaystyle \lnot {\textit {par}}(g,m)}$ и ${\displaystyle \lnot {\textit {par}}(t,e)}$, и многие другие отрицательные литералы
• Удалите все отрицательные литералы, содержащие переменные, которых нет в положительном литерале:
  • после удаления всех отрицательных литералов, содержащих другие переменные, кроме ${\displaystyle x_{me},x_{ht}}$, Только ${\displaystyle {\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})}$ остается вместе со всеми наземными литералами из фоновых знаний
• Преобразование предложений обратно в форму Horn:
  • ${\displaystyle {\textit {dau}}(x_{me},x_{ht})\leftarrow {\textit {par}}(x_{ht},x_{me})\land {\textit {fem}}(x_{me})\land ({\text{all background knowledge facts}})}$

Результирующая оговорка Хорна является гипотезой час полученный методом rlgg. Игнорируя исходные знания, статья неофициально гласит: "${\displaystyle x_{me}}$ называется дочерью ${\displaystyle x_{ht}}$ если ${\displaystyle x_{ht}}$ является родителем ${\displaystyle x_{me}}$ и ${\displaystyle x_{me}}$ женщина", что является общепринятым определением.

Касательно над требования, "Необходимость"было выполнено, потому что предикат Дау не появляется в фоновых знаниях, что, следовательно, не может подразумевать какое-либо свойство, содержащее этот предикат, как в положительных примерах ".Достаточность"удовлетворяется вычисленной гипотезой час, поскольку он вместе с ${\displaystyle {\textit {par}}(h,m)\land {\textit {fem}}(m)}$ из базовых знаний, следует первый положительный пример ${\displaystyle {\textit {dau}}(m,h)}$, и аналогично час и ${\displaystyle {\textit {par}}(t,e)\land {\textit {fem}}(e)}$ из фоновых знаний вытекает второй положительный пример ${\displaystyle {\textit {dau}}(e,t)}$. "Слабая консистенция"удовлетворен час, поскольку час выполняется в (конечном) Структура Herbrand описывается базовыми знаниями; аналогично для "Сильная консистенция".

Общее определение отношения бабушки, а именно. ${\displaystyle {\textit {gra}}(x,z)\leftarrow {\textit {fem}}(x)\land {\textit {par}}(x,y)\land {\textit {par}}(y,z)}$, не может быть изучен с использованием описанного выше подхода, поскольку переменная у встречается только в теле предложения; соответствующие литералы были бы удалены на 4-м шаге подхода. Чтобы преодолеть этот недостаток, этот шаг необходимо изменить так, чтобы его можно было параметризовать с помощью различных буквальная эвристика после выбора. Исторически реализация GOLEM основана на подходе rlgg.

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

Система индуктивного логического программирования - это программа, которая принимает в качестве входных логических теорий ${\displaystyle B,E^{+},E^{-}}$ и выводит правильную гипотезу ЧАС по теориям ${\displaystyle B,E^{+},E^{-}}$ Алгоритм системы ILP состоит из двух частей: поиска гипотез и выбора гипотез. Сначала выполняется поиск гипотезы с помощью процедуры индуктивного логического программирования, затем подмножество найденных гипотез (в большинстве систем одна гипотеза) выбирается алгоритмом выбора. Алгоритм выбора оценивает каждую из найденных гипотез и возвращает те, которые имеют наивысшую оценку. Пример функции оценки включает минимальную длину сжатия, когда гипотеза с наименьшим Колмогоровская сложность имеет наивысший балл и возвращается. Система ILP является полной, если и только если применимы любые теории входной логики. ${\displaystyle B,E^{+},E^{-}}$ любая правильная гипотеза ЧАС Относительно этих входных теорий можно найти с помощью процедуры поиска гипотез.

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

Современные системы ILP, такие как Progol,^[6] Град ^[15] и Импаро ^[16] найти гипотезу ЧАС используя принцип обратного следования^[6] для теорий B, E, ЧАС: ${\displaystyle B\land H\models E\iff B\land \neg E\models \neg H}$. Сначала они строят промежуточную теорию F называется мостовой теорией, удовлетворяющей условиям ${\displaystyle B\land \neg E\models F}$ и ${\displaystyle F\models \neg H}$. Тогда как ${\displaystyle H\models \neg F}$, они обобщают отрицание теории моста F с анти-следствием.^[17] Однако операция анти-следствия, поскольку она сильно недетерминирована, требует больших вычислительных затрат. Следовательно, поиск альтернативной гипотезы может быть проведен с использованием вместо этого операции обратного подчинения (анти-подчинения), которая менее недетерминирована, чем анти-влечение.

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

Реализации

• 1BC и 1BC2: наивные байесовские классификаторы первого порядка:
• ACE (комбинированный двигатель)
• Алеф
• Атом
• Claudien
• DL-Learner
• DMax
• FastLAS (быстрое обучение на основе наборов ответов)
• ФОЛЬГА
• Голем (ILP)
• ILASP (Индуктивное изучение программ с набором ответов)
• Imparo^[19]
• Inthelex (Ученик дополнительной теории из примеров)
• Лайм
• Метагол
• Mio
• MIS (Система вывода моделей) Эхуда Шапиро
• ПРОГОЛ
• RSD
• Warmr (теперь входит в ACE)
• ProGolem ^[21][22]

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

• Здравый смысл
• Формальный анализ концепции
• Индуктивное мышление
• Индуктивное программирование
• Индуктивная вероятность
• Статистическое реляционное обучение
• Изучение пространства версий

Рекомендации

1. Плоткин Г.Д. Автоматические методы индуктивного вывода Кандидатская диссертация, Эдинбургский университет, 1970.
2. Шапиро, Эхуд Ю. Индуктивный вывод теорий из фактов, Отчет об исследовании 192, Йельский университет, факультет компьютерных наук, 1981. Перепечатано в J.-L. Лассез, Г. Плоткин (ред.), Computational Logic, MIT Press, Кембридж, Массачусетс, 1991, стр. 199–254.
3. Шапиро, Эхуд Ю. (1983). Отладка алгоритмической программы. Кембридж, Массачусетс: MIT Press. ISBN  0-262-19218-7
4. Шапиро, Эхуд Ю. "Система вывода модели. »Труды 7-й международной совместной конференции по искусственному интеллекту - Том 2. Morgan Kaufmann Publishers Inc., 1981.
5. Люк Де Рэдт. Перспектива индуктивного логического программирования. Семинар по текущим и будущим тенденциям в логическом программировании, Шейкертаун, появится в Springer LNCS, 1999. CiteSeerX: 10.1.1.56.1790
6. Muggleton, S.H. (1991). «Индуктивное логическое программирование». Вычислительная техника нового поколения. 8 (4): 295–318. CiteSeerX  10.1.1.329.5312. Дои:10.1007 / BF03037089.
7. Muggleton S.H. и Бунтин В. "Машинное изобретение предиката первого порядка путем обращения разрешения "," Труды 5-й Международной конференции по машинному обучению, 1988 г. "
8. Muggleton, S.H. (1995). «Инвертирующий вывод и Прогол». Вычислительная техника нового поколения. 13 (3–4): 245–286. CiteSeerX  10.1.1.31.1630. Дои:10.1007 / bf03037227.
9. Магглетон, Стивен (1999). «Индуктивное логическое программирование: проблемы, результаты и проблема изучения языка в логике». Искусственный интеллект. 114 (1–2): 283–296. Дои:10.1016 / с0004-3702 (99) 00067-3.; здесь: Раздел 2.1
10. Джероски, Сашо (1996), «Индуктивное логическое программирование и обнаружение знаний в базах данных», в Файяд, США; Пятецкий-Шапиро, Г .; Smith, P .; Утурусами Р. (ред.), Достижения в области обнаружения знаний и интеллектуального анализа данных, MIT Press, стр. 117–152.; здесь: Раздел 5.2.4
11. Плоткин, Гордон Д. (1970). Мельцер, Б .; Мичи, Д. (ред.). «Заметка об индуктивном обобщении». Машинный интеллект. 5: 153–163.
12. Плоткин, Гордон Д. (1971). Мельцер, Б .; Мичи, Д. (ред.). «Дальнейшее примечание об индуктивном обобщении». Машинный интеллект. 6: 101–124.
13. то есть использование одного и того же предикатного символа и отрицательного / отмененного статуса
14. в целом: п-набор когда п приведены положительные примеры литералов
15. Рэй, О., Брода, К., и Руссо, А. М. (2003). Гибридное абдуктивное индуктивное обучение. В LNCS: Vol. 2835. Материалы 13-й международной конференции по индуктивному логическому программированию (стр. 311–328). Берлин: Springer.
16. Кимбер, Т., Брода, К., и Руссо, А. (2009). Индукция при неудаче: изучение связанных теорий Хорна. В LNCS: Vol. 5753. Материалы 10-й международной конференции по логическому программированию и немонотонным рассуждениям (стр. 169–181). Берлин: Springer.
17. Ёситака Ямамото, Кацуми Иноуэ и Кодзи Иванума. Обратное подчинение для полной пояснительной индукции. Машинное обучение, 86 (1): 115–139, 2012.
18. Акихиро Ямамото. Какие гипотезы можно найти с обратным следствием? В индуктивном логическом программировании, страницы 296–308. Спрингер, 1997.
19. Тимоти Кимбер. Изучение определенных и нормальных логических программ путем индукции при сбое. Кандидатская диссертация, Имперский колледж Лондона, 2012 г.
20. Дэвид Тот (2014). Импаро завершается обратным отнесением. arXiv: 1407.3836
21. Магглетон, Стивен; Сантос, Хосе; Тамаддони-Нежад, Алиреза (2009). «ProGolem: система, основанная на относительном минимальном обобщении» (PDF). ILP.
22. Сантос, Хосе; Нассиф, Хусам; Пейдж, Дэвид; Магглетон, Стивен; Штернберг, Майк (2012). «Автоматическая идентификация особенностей взаимодействия белок-лиганд с использованием индуктивного логического программирования: пример связывания гексозы» (PDF). BMC Bioinformatics. 13: 162. Дои:10.1186/1471-2105-13-162. ЧВК  3458898. PMID  22783946.

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

• Muggleton, S .; Де Раэдт, Л. (1994). «Индуктивное логическое программирование: теория и методы». Журнал логического программирования. 19–20: 629–679. Дои:10.1016/0743-1066(94)90035-3.
• Lavrac, N .; Дзероски, С. (1994). Индуктивное логическое программирование: методы и приложения. Нью-Йорк: Эллис Хорвуд. ISBN  978-0-13-457870-5. Архивировано из оригинал на 2004-09-06. Получено 2004-09-22.
• Наглядный пример установления родства бабушек и дедушек Атомная система. http://john-ahlgren.blogspot.com/2014/03/inductive-reasoning-visualized.html