Голем (ИЛП)

Голем — это алгоритм индуктивного логического программирования, разработанный Стивеном Магглтоном и Цао Фэном в 1990 году. ^[1] Он использует технику относительного наименьшего общего обобщения, предложенную Гордоном Плоткиным , ведущую к поиску снизу вверх по решетке включений . ^[2] В 1992 году, вскоре после своего появления, Golem считался единственной системой индуктивного логического программирования, способной масштабироваться до десятков тысяч примеров. ^[3]

Описание

Голем принимает на вход определенную программу $B$ в качестве базовых знаний вместе с наборами положительных и отрицательных примеров, обозначаемых ${\textstyle E^{+}}$ и ${\textstyle E^{-}}$ соответственно. Общая идея состоит в том, чтобы построить наименее общее обобщение ${\textstyle E^{+}}$ относительно фоновых знаний. Однако если $B$ не является просто конечным набором основных атомов , то этого относительного наименее общего обобщения может не существовать. ^[4]Следовательно, вместо того, чтобы использовать $B$ напрямую, Голем использует набор ${\textstyle B^{h}}$ всех основных атомов, которые можно разделить из $B$ не более чем $за h$ шагов разрешения. Дополнительная трудность состоит в том, что если ${\textstyle E^{-}}$ непусто, это наименее общее обобщение ${\textstyle E^{+}}$ может повлечь за собой отрицательный пример. В этом случае Голем обобщает различные подмножества ${\textstyle E^{+}}$ отдельно получить программу из нескольких пунктов. ^[2] Голем также использует некоторые ограничения на пространство гипотез, гарантируя, что относительно наименьшие общие обобщения являются полиномиальными по количеству обучающих примеров. Golem требует, чтобы все переменные в заголовке предложения также появлялись в литерале тела предложения; что количество замен, необходимых для создания экземпляров экзистенциально определенных переменных, введенных в литерал, ограничено; и что глубина цепочки подстановок, необходимой для создания экземпляра такой переменной, также ограничена. ^[3]

Пример

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

par : родитель

,

fem : женщина

,

dau : дочь

,

g : Джордж

,

h : Хелен

,

m : Мэри

,

t : Том

,

n : Нэнси

и

e : Ева

.

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

{\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}}(m,h)\land {\textit {dau}}(e,t)

,

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

Относительное наименьшее общее обобщение теперь вычисляется следующим образом, чтобы получить определение дочернего отношения.

Сравните каждый положительный пример с полным базовым знанием:
${\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}}$ ,
Преобразование в нормальную форму предложения :
${\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}}$ ,
Анти-унификация каждого совместимого ^[5] пара ^[6] литералов:
- ${\textit {dau}}(x_{me},x_{ht})$ от ${\textit {dau}}(m,h)$ и ${\textit {dau}}(e,t)$ ,
- $\lnot {\textit {par}}(x_{ht},x_{me})$ от $\lnot {\textit {par}}(h,m)$ и $\lnot {\textit {par}}(t,e)$ ,
- $\lnot {\textit {fem}}(x_{me})$ от $\lnot {\textit {fem}}(m)$ и $\lnot {\textit {fem}}(e)$ ,
- $\lnot {\textit {par}}(g,m)$ от $\lnot {\textit {par}}(g,m)$ и $\lnot {\textit {par}}(g,m)$ , аналогично для всех других литералов фоновых знаний
- $\lnot {\textit {par}}(x_{gt},x_{me})$ от $\lnot {\textit {par}}(g,m)$ и $\lnot {\textit {par}}(t,e)$ и многие другие отрицательные литералы
Удалите все отрицательные литералы, содержащие переменные, которые не встречаются в положительном литерале:
- после удаления всех отрицательных литералов, содержащих другие переменные, кроме $x_{me},x_{ht}$ , только ${\textit {dau}}(x_{me},x_{ht})\lor \lnot {\textit {par}}(x_{ht},x_{me})\lor \lnot {\textit {fem}}(x_{me})$ остается вместе со всеми основными литералами из базовых знаний
Преобразуйте предложения обратно в форму Horn:
- ${\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,$ полученная Големом. Неофициально статья гласит: « $x_{me}$ называется дочерью $x_{ht}$ если $x_{ht}$ является родителем $x_{me}$ и $x_{me}$ является женщиной », что является общепринятым определением.

Ссылки

^ Магглтон, Стивен Х.; Фэн, Цао (1990). Арикава, Сэцуо; Гото, Сигэки; Осуга, Сэцуо; Ёкомори, Такаси (ред.). «Эффективная индукция логических программ» . Алгоритмическая теория обучения, Первый международный семинар, ALT '90, Токио, Япония, 8-10 октября 1990 г., Труды . Спрингер/Омша: 368–381.
^ Jump up to: ^а ^б Ниенхуйс-Чэн, Шань-хвэй; Вольф, Рональд де (1997). Основы индуктивного логического программирования . Конспекты лекций по информатике Конспекты лекций по искусственному интеллекту. Берлин Гейдельберг: Springer. стр. 354–358. ISBN 978-3-540-62927-6 .
^ Jump up to: ^а ^б Ага, Дэвид В. (1992). «Связанные алгоритмы реляционного обучения». В Магглтоне, Стивен (ред.). Индуктивное логическое программирование . Лондон: Академическая пресса . п. 247.
^ Ниенхуйс-Чэн, Шань-хвэй; Вольф, Рональд де (1997). Основы индуктивного логического программирования . Конспекты лекций по информатике Конспекты лекций по искусственному интеллекту. Берлин Гейдельберг: Springer. п. 286. ИСБН 978-3-540-62927-6 .
^ т.е. использование одного и того же символа предиката и отрицательного/неотрицаемого статуса.
^ в общем: $n$ -кортеж, когда $n положительных литералов примера$ даны

Эта искусственному интеллекту статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[1] Магглтон, Стивен Х.; Фэн, Цао (1990). Арикава, Сэцуо; Гото, Сигэки; Осуга, Сэцуо; Ёкомори, Такаси (ред.). «Эффективная индукция логических программ» . Алгоритмическая теория обучения, Первый международный семинар, ALT '90, Токио, Япония, 8-10 октября 1990 г., Труды . Спрингер/Омша: 368–381.

[:0-2] Jump up to: ^а ^б Ниенхуйс-Чэн, Шань-хвэй; Вольф, Рональд де (1997). Основы индуктивного логического программирования . Конспекты лекций по информатике Конспекты лекций по искусственному интеллекту. Берлин Гейдельберг: Springer. стр. 354–358. ISBN 978-3-540-62927-6 .

[:1-3] Jump up to: ^а ^б Ага, Дэвид В. (1992). «Связанные алгоритмы реляционного обучения». В Магглтоне, Стивен (ред.). Индуктивное логическое программирование . Лондон: Академическая пресса . п. 247.

[4] Ниенхуйс-Чэн, Шань-хвэй; Вольф, Рональд де (1997). Основы индуктивного логического программирования . Конспекты лекций по информатике Конспекты лекций по искусственному интеллекту. Берлин Гейдельберг: Springer. п. 286. ИСБН 978-3-540-62927-6 .

[5] т.е. использование одного и того же символа предиката и отрицательного/неотрицаемого статуса.

[6] в общем: $n$ -кортеж, когда $n положительных литералов примера$ даны

[1]

[2]

[3]

[4]

[5]

[6]