В программировании набора ответов, в чем разница между моделью и наименьшей моделью?

Я посещаю занятия по искусственному интеллекту, и мы работаем с программированием наборов ответов (в частности, Clingo). На данный момент мы говорим в основном о теории, и у меня возникают проблемы с разграничением моделей и наименьших моделей. У меня есть следующие определения:

Удовлетворяющие правила, модели, наименьшие модели и наборы ответов определенной программы

  1. Программа называется определенной, если в теле ее правил нет слова «не».
  2. Говорят, что множество S удовлетворяет правилу вида a :- b1,..., bm, а не c1,..., не cn. если его тело удовлетворяется S (т. е. b1 … bm находятся в S и ни одно из c1 … cn не принадлежит S), следует, что его голова должна удовлетворяться S (т. е. a находится в S).
  3. Говорят, что набор S удовлетворяет программе, если он удовлетворяет всем правилам этой программы.
  4. Набор S называется набором ответов определенной программы P, если (a) S удовлетворяет P (также называется S является моделью P) и (b) никакое строгое подмножество S не удовлетворяет P (т. е. S является наименьшая модель P).

С вопросом (снят со слайдов лекции, а не домашнего задания):

P is defined as:
a :- b,e.
b. 
c :- d,b.
d.

Which of the following are models and least models?
{}, {b}, {b,d}, {b,d,c}, {b,d,c,e}, {b,d,c,e,a}

Может ли кто-нибудь дать мне знать, что ответ на вопрос выше? Я, вероятно, могу понять разницу оттуда, хотя, если бы кто-то мог объяснить разницу в просторечии (а не в определении из учебника), это было бы замечательно. Я не уверен, на каком форуме разместить этот вопрос - пожалуйста, дайте мне знать, если его следует разместить где-то еще.

Спасибо


answer-set-programming clingo
person rphello101    schedule 21.09.2014    source источник

Ответы (1)


arrow_upward
2
arrow_downward

Прежде всего, обратите внимание, что в этом разделе ваших слайдов речь идет о наборах ответов положительной программы P (также называемой определенной программой). , хотя в нем также упоминается нет. Положительная программа — это простой случай, так как для положительной программы P всегда существует единственная наименьшая модель LM(P), которая является пересечение всех его моделей.

Разрешение правил не в телах правил усложняет ситуацию. тело правила находится справа от :-.

Ответом на вопрос будет: набор за набором:

  • S={} не является моделью, так как b и d являются фактами b. d.
  • S={b} не является моделью, так как d является фактом d.
  • S={b,d} не является моделью, так как c подразумевается c :- d,b., а c нет в S
  • S={b,d,c} – это модель
  • S={b,d,c,e} не является моделью, так как a подразумевается a :- b,e., а a нет в S
  • S={b,d,c,e,a} – это модель

Так какая модель самая маленькая? Это S={b,c,d}, так как никакое строгое подмножество S не удовлетворяет P.

Мы можем прийти к наименьшей модели положительной программы P двумя способами:

  • Перечислить все модели и взять их пересечение (здесь {b,c,d}∩{a,b,c,d,e}={b,c,d}).
  • Начиная с фактов (здесь b. d.) и итеративно добавляя подразумеваемые атомы (здесь c :- b,d.) к S, повторяя до тех пор, пока S не станет моделью, и останавливаясь на этом этапе.

Как сказано на ваших слайдах, определение набора ответов для позитивной программы P таково: S — это набор ответов P< /strong>, если S — наименьшая модель P. Чтобы быть более строгим, на самом деле это тогда и только тогда, поскольку наименьшая модель LM(P) уникальна.

И последнее замечание, чтобы вы не запутались в них позже, ограничение :- a, b на самом деле просто сокращение для x :- not x, a, b. Таким образом, программы, содержащие ограничения, не являются положительными программами; хотя поначалу они могут выглядеть так, поскольку тело ограничения, по-видимому, не содержит not.

person vukk    schedule 23.09.2014