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

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

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

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

Формальное определение [ править ]

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

Необходимость: B ⊭ E + Достаточность: B ∧ час ⊨ E + Слабая консистенция: B ∧ час ⊭ ложный Сильная консистенция: B ∧ час ∧ E - ⊭ ложный {\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}}}

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

Пример [ править ]

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

par : родитель , fem : женщина , dau : дочь , g : Джордж , h : Хелен , m : Мэри , t : Том , n : Нэнси и e : Ева .

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

${\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) " подход к индуктивному логическому программированию должен быть использован для получения предложения о том, как формально определить дочернее отношение dau .

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

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

  ${\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)}$from и аналогично для всех других литералов фоновых знаний${\displaystyle \lnot {\textit {par}}(g,m)}$${\displaystyle \lnot {\textit {par}}(g,m)}$
  • ${\displaystyle \lnot {\textit {par}}(x_{gt},x_{me})}$from and , и многие другие отрицательные литералы${\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}})}$

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

Что касается вышеуказанных требований, « Необходимость » была удовлетворена, потому что предикат dau не появляется в фоновых знаниях, что, следовательно, не может подразумевать какое-либо свойство, содержащее этот предикат, например положительные примеры. « Достаточность » удовлетворяется вычисленной гипотезой h , поскольку она, вместе с исходными знаниями, подразумевает первый положительный пример , и аналогично h и фоновые знания подразумевают второй положительный пример . " Слабая согласованность " удовлетворяется h , поскольку h выполняется в (конечном)${\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, описанная базовыми знаниями; аналогично « Сильная консистенция ».

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

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

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

Поиск гипотез [ править ]

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

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

Реализации [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]