Применение метода абстракций

Для повышение эффективности резолюционных методов часто используются различные сокращающие перебор (суживающие) стратегии. Большинство суживающих стратегий реализуется путем включения в инструментальные средства создания систем ИИ специфических конструкций, управляющих перебором. Как правило, такие стратегии требуют ручной разработки высококвалифицированными специалистами. Поэтому важной представляется задача создания суживающих стратегий, которые могли бы использоваться в автоматическом режиме.

В настоящем разделе рассматривается метод абстракций, впервые предложенный и теоретически обоснованный американским исследователем Плейстедом. Коротко этот метод можно сформулировать следующим образом. По исходной задаче А строится более простая задача В таким образом, чтобы для каждого решения задачи А имелось решение задачи В, структура которого подобна решению задачи А. Таким образом, найденные решения простой задачи В могут использоваться как некие схемы для поиска возможных решений первоначальной задачи А (хотя некоторые решения задачи B могут не привести к цели). Задача В строится с помощью так называемых абстракционных отображений и называется абстракционной задачей или абстракцией задачи А. Очевидно, для успешного применения данного метода необходимо, чтобы, во-первых, абстракционная задача решалась существенно проще исходной и, во-вторых, чтобы решения абстракционной задачи позволяли сократить перебор, необходимый для поиска решений исходной задачи. Ниже мы покажем, что предлагаемая суживающая стратегия удовлетворяет обоим требованиям.

 

Как уже было сказано, теоретической основой ИИ является проблема дедукции. Проблема дедукции формулируется как для исчисления предикатов (ИП), так и для исчисления высказываний (ИВ). В последнем случае под литерами понимаются высказывания или их отрицания. Применяя метод абстракций, мы можем заменить все предикаты БЗ и цели независимо от значений их аргументов высказываниями. Такая абстракция носит название пропозициональной. Ее определение таково.

  Пусть D - дизъюнкт вида:

(L₁, L₂, …, L_k).

Тогда пропозициональная абстракция определяется абстракционным отображением

  f(D) = D ў, где D ў - дизъюнкт вида

(L ў ₁, L ў ₂, …, L ў _k), L ў _i = P, если L_i = P(l₁, …, l_n ) и L ў _i = щ P, если L_i = щ (l₁, …, l_n), 1 Ј i Ј k.

В построенной таким образом простой модели проблема дедукции решается значительно проще. В ИП задача поиска логического вывода в общем случае является NP-полной, а для получения полиномиальной оценки по времени необходимы существенные ограничения на хорновские дизъюнкты (например, использование лишь одноместных предикатов). В то же время в ИВ большинство резолюционных методов имеют оценку трудоемкости Cn², где n - число литер, присутствующих в S, а предложенный ниже метод имеет оценку Cn.

Таким образом, суживающая стратегия, которую мы будем рассматривать, построена на основе пропозициональной абстракции. В противоположность большинству известных суживающих стратегий она предусматривает настройку алгоритма поиска логических выводов на работу с конкретной БЗ. Ее целесообразно применять при работе со стационарными БЗ, т.е. такими, которые в процессе эксплуатации изменяются относительно редко. На практике стационарные и даже статические (не модифицируемые) БЗ встречаются достаточно часто. Так, например, такие БЗ используются в обучающих системах с элементами ИИ, часто называемых экспертно-обучающими системами.

Метод поиска логического вывода с использованием пропозициональной абстракции состоит из двух основных частей. Во-первых, в него включен эффективный алгоритм решения абстракционной задачи, полученной применением пропозициональной абстракции. Это алгоритм решения проблемы дедукции в ИВ. Он позволяет построить выводы дизъюнкта C, если последний является логическим следствием (ниже будут указаны некоторые особенности таких выводов, связанные с понятием мультидизюнкта). Алгоритм использует формально-грамматическую интерпретацию проблемы дедукции и предусматривает предварительную настройку на работу с конкретным множеством гипотез. Следует подчеркнуть, что предварительная настройка выполняется до задания целей, т.е. один раз для БЗ. Во-вторых, в предлагаемый метод включен алгоритм построения выводов в ИП по выводам в ИВ, полученным при решении абстракционной задачи. Рассмотрим сначала первый алгоритм, остановившись прежде всего на необходимой для него предварительной настройке.

Пусть имеется БЗ E в ИВ, состоящая из дизъюнктов

{D₁,..., D_m},

в которой используются высказывания Р₁,..., Р_n. Построим по Е КС-грамматику G(E), без терминальных символов и начального нетерминала: G(E) = {V_n, Q},

где V_n - множество нетерминальных символов, а Q - множество правил вывода. Множество нетерминальных символов образуем из высказываний в Е:

V_N = {Р₁,..., Р_n}.

Правила вывода грамматики построим по входящим в Е дизъюнктам. Пусть D_i = (Р_j , щ Р_l1,..., щ Р_lk ).

Построим по нему правило вывода

Р_j а Р_l1 ... Р_lk.

Если D_i = (Р_j ), то получим укорачивающее правило Р_j а e. По цели, представленной в виде

С = (щ Р_i1,..., щ Р_iq),

образуем цепочку соответствующих нетерминальных символов

w = Р_i1 ... Р_iq.

Теперь логический вывод во множестве S можно интерпретировать как вывод пустой цепочки из w: w Ю ⁺ e. Формально-грамматическая интерпретация позволит нам использовать методы теории формальных грамматик для настройки на конкретные БЗ, что, свою очередь, значительно повысит эффективность алгоритма поиска логических выводов.

Введем понятие укорачивающего символа грамматики. Нетерминальный символ A называется укорачивающим, если в данной грамматике из него возможен вывод пустой цепочки: A Ю ⁺ e. Очевидно, вывод пустой цепочки из некоторой w возможен лишь в том случае, если все входящие в w символы являются укорачивающими. Это утверждение дает возможность выполнить предварительную настройку алгоритма на работу с заданной БЗ. Настройка включает в себя выделение подмножества укорачивающих символов, которое удобно представить в виде двоичной шкалы. Разряды шкалы соответствуют нетерминалам грамматики и принимают разные значения, в зависимости от того, является ли данный нетерминал укорачивающим или нет. После построения шкалы укорачивающих символов алгоритм, распознающий свойство выводимости целей совершенно элементарен.

Нашей задачей является не только распознавание выводимости целей, но и построение выводов (по возможности всех) в случае выводимости. Поэтому предварительная настройка на работу с конкретной БЗ осуществляется алгоритмом, не только выделяющим укорачивающие символы, но и формирующим для каждого укорачивающего символа списки правил, с которых могут начинаться выводы пустой цепочки. Рассмотрим этот алгоритм.

Пусть имеется некоторая грамматика G(E). Обозначим через W формируемое подмножество укорачивающих символов грамматики, через S(А) - формируемые для каждого символа из W списки правил вывода, с которых могут начинаться выводы пустой цепочки из А. Алгоритм выделения укорачивающих символов и соответствующих им правил вывода представим в виде следующего итеративного процесса:

W₀ = { А | А а e О Q }; S₀(А) = { R | R = A а e, R О Q },

т.е. включаем в W₀ те символы грамматики, для которых в ней имеются укорачивающие правила вывода, а в соответствующие S₀ - сами укорачивающие правила. Пусть уже получены W_i и S_i(A) для всех А О W_i.

Выполним очередной шаг итеративного процесса следующим образом:

  W_i+1 = W_i И { А | А а А₁А₂ ... А_n О Q; A_i О W_i, i = 1,..., n };

S_i+1(A) = S_i(A) И { R | R = А а А ₁ А ₂ ... А_n; A_i О W_i , i = 1,..., n; R О Q\ S_i(A)},

т.е. включаем в W_i+1 все символы из W_i ите символы грамматики, для которых найдутся правила вывода, все символы правых частей которых включены в W_i. В соответствующие S_i+1 включим правила из S_i, а также правила, обладающие указанным выше свойством и не входящие в S_i. Отметим, что S_i+1 - это упорядоченные множества (списки) и вновь включаемые в них правила вывода попадают в концы списков.

Алгоритм закончит работу, когда на некотором шаге j+1 окажется, что имеют место равенства S_j+1(A) = S_j(A) для всех А О V_N. Примем W = W_j и S(A) = S_j(A) для каждого А О W. Для оценки числа шагов алгоритма докажем следующие две леммы.

Лемма 1. Пусть на j -омшаге алгоритма получено W_j = W_j-1. Тогда S_j+1(A) = S_j(A) для любого А О W_j.

Доказательство. Доказывая утверждение от противного, предположим, что для некоторого А найдется правило R = А а h такое, что R П S_j(A) и R О S_j+1(A). Так как правило R не попало в S_j(A), найдется символ A_i, который входит в цепочку h и A_i П W _j-1. Но R включено в S_j+1(A) и, следовательно, A_i О W_j. Поэтому W_j № W_j-1. Получили противоречие, доказывающее наше утверждение.

Лемма 2. Число шагов алгоритманастройки не превышает числа нетерминальных символов грамматики.

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

 Важное свойство формируемых алгоритмом настройки подмножеств S сформулировано в следующей теореме.

Теорема 1. На всех шагах любого вывода А Ю ⁺ e могут применяться лишь правила из подмножеств S.

Доказательство. Докажем это утверждение от противного. Не умаляя общности, мы можемрассматривать левосторонние выводы. Пусть на некотором шаге вывода к цепочке w _j = B x, B О V_N, x О V_N*,было примененоправило R = B а h такое, что R П S(B). Так как мы исследуем вывод пустой цепочки, в нем должна найтись цепочка w _k = x, k > j. Поэтому существует вывод h Ю ⁺ e, и все символы цепочки h укорачивающие, а тогда найдется такое i, что в W_i, входят все символы цепочки h и R О S_i(B). Так как S_i(B) Н S(B), R О S(B). Получили противоречие, доказывающее наше утверждение.

Подмножество W позволяет сформировать двоичную шкалу нетерминальных символов, которая вместе со списками S является результатом работы алгоритма предварительной настройки.

Теперь можно описать алгоритм решения абстракционной задачи. Выводимость цели C проверяется построением соответствующей цепочки нетерминальных символов грамматики и просмотром значений шкалы для символов этой цепочки. C выводима в том и только том случае, если шкала покажет, что все символы цепочки являются укорачивающими. Для перебора всех вариантов ее вывода нужно в построенной по данной БЗ КС-грамматике перебрать выводы пустой цепочки из цепочки, соответствующей С. Такой перебор легко осуществить, пользуясь списками S. Отметим, что при этом не будут перебираться тупиковые варианты. Это выгодно отличает предлагаемый метод от других алгоритмов, построенных на основе метода резолюций.

Проиллюстрируем описанный алгоритм, включая предварительную настройку, следующим примером.

Пример 1. Пусть задана следующая БЗ в ИВ: E = {

(1) (p, щ r, щ t,),                  (5) (q, щ u),

(2) (p, щ q, щ r,),                      (6) (r),

(3) (p, щ q, щ s,),                  (7) (t, щ q, щ u),

(4) (q, щ s, щ t, щ u),                  (8) (u) }.

Соответствующая этой БЗ грамматика выглядит так:

V_N = { p, q, r, s, t, u }.

В Q войдут следующие правила вывода:

                1) p а rt; 2) p а qr; 3) p а qs; 4) q а stu;

                5) q а u; 6) r а e; 7) t а qu; 8) u а e.

Применим итерационный алгоритм настройки. Правила вывода будем представлять своими номерами.

Wi	Символы		Si	P	Q	r	s	t	u
W0	r, u		S0			6			8
W1	q, r, u		S1		5	6			8
W2	p, q, r, t, u		S2	2	5	6		7	8
W3	p, q, r, t, u		S3	2,1	5	6		7	8

Так как W₂ = W₃, работа алгоритма закончена. Настройка на заданную БЗ произведена: W = W₂, S(a) = S₃(a), a О W. Имеем шкалу (1 - символ укорачивающий, 0 - символ неукорачивающий):

 

p	q	r	s	t	u
1	1	1	0	1	1

Пусть цель C = p & q & s. Ее отрицание щ С =   (щ p, щ q, щ s). Этому дизъюнкту соответствует цепочка w = pqs. Находим в шкале значения символов w: 110. Так как s - неукорачивающий, C невыводим.  

Пусть C = p & q. Его отрицание щ С =   (щ p, щ q). Этому дизъюнкту соответствует цепочка w = pq. Значения символов w в шкале 11. Следовательно, C выводим. Найдем все его выводы, перебирая варианты вывода из w пустой цепочки с учетом подмножеств S:

1) pq, qrq, urq, rq, q, u, e (при использовании на первом шаге правила 2).

2) pq, rtq, tq, quq, uuq, uq, q, u, e (при использовании на первом шаге правила 1).

Мы видим, что наш алгоритм не применял в процессе перебора правило 3, так как оно не входит в S(р). По полученным выводам в грамматике легко построить выводы C в исходной БЗ (предоставим это читателю). Отметим лишь, что в каждой цепочке выводов можно оставить лишь по одному вхождению каждого символа и сократить совпадающие цепочки. Такое преобразование следует выполнять, если нас интересуют выводы в ИВ. Если же поиск выводов в ИВ рассматривается как метод решения абстракционной задачи, то выводы нужно оставить в их первоначальном виде.

Перейдем к описанию второго алгоритма предлагаемого метода – алгоритма построения выводов в ИП по выводам в ИВ, полученным применением пропозициональной абстракции. Этот алгоритм должен учитывать особенность, связанную с тем, что в дизъюнктах ИП литерами могут оказаться одни и те же предикаты с различными значениями аргументов. При применении пропозициональной абстракции таким предикатам соответствуют одни и те же высказывания. Сокращение повторяющихся литер в дизъюнктах ИВ недопустимо, так как приводит к несоответствию между выводами в ИП и ИВ. Во избежание подобного обстоятельства в рамках пропозициональной абстракции используется понятие мультидизъюнкта - это дизъюнкт ИВ, который может содержать несколько экземпляров одного и того же высказывания (в том числе и литеры вида p и щ p, хотя дизъюнкты, содержащие подобные литеры, являются тавтологиями и обычно исключаются из рассмотрения). Мультидизъюнкты являются объектами и результатами действия m-абстракции и m-резолюции, которые определяются аналогично понятиям абстракции и резолюции. Выводы в множестве мультидизъюнктов ИВ строятся с помощью m-резолюции и поэтому будут соответствовать по своей структуре выводам в исходном множестве дизъюнктов ИП.    

Описываемый алгоритм для построения выводов целей в ИП использует выводы в ИВ, полученные в результате решения абстракционной задачи, как схемы выводов в ИП. Построение выводов в ИП производится последовательным просмотром всех схем с одновременным восстановлением аргументов предикатов и выполнением унификации. Если на каком-либо этапе просмотра очередной схемы унификация окажется невозможной, то данная схема является непродуктивной, т.е. выводы в ИП, соответствующие этой схеме отсутствуют. Если все схемы окажутся непродуктивными, то выводы в ИП отсутствуют и соответствующая цель невыводима.

Наиболее эффективная стратегия построения выводов в ИП – это параллельное построение выводов в грамматике, схем в ИВ и выводов в ИП. Алгоритм, реализующий эту стратегию, назовем параллельным. Каждый шаг его работы заключается в применении некоторого правила вывода для построения вывода в грамматике, использовании соответствующего правилу мультидизъюнкта в абстракционной задаче для резолюции и в попытке использования соответствующего дизъюнкта для резолюции в исходной задаче. Эта попытка будет успешной, если найдется соответствующий унификатор. Параллельный алгоритм оперативно выявляет непродуктивные схемы еще в процессе их построения - если на некотором шаге унификация окажется невозможной. Предусматривается также удаление алгоритмом "лишних" литер. Если одинаковым литерам в мультидизъюнктах схемы соответствуют одинаковые литеры в дизъюнктах вывода в ИП, то повторяющиеся литеры исключаются в схеме, и в выводе, а из цепочки вывода удаляются соответствующие им символы. Формальное описание параллельного алгоритма достаточно громоздко. Поэтому проиллюстрируем этот алгоритм следующими двумя примерами.

Пример 2. Пусть в ИП задана следующая БЗ:

E = { (1) (q(c), щ p(a), щ p(b)), (2) (p(a)), (3) (p(b)), (4) r(d)) }.

Пропозициональные m-абстракции, построенные по множеству E:

f(E) = { (1) (q, щ p, щ p), (2) (p), (3) (p), (4) (r) }.

Грамматика, построенная по множеству f(E):

G(f(E)) = { V_N, Q }; V_N = { q, p, r }; Q = { (1) q ® pp, (2) p ® e, (3) p ® e, (4) r ® e }.

Двоичная шкала символов:

 

q	p	r
1	1	1

Списки правил, выделенных для укорачивающих символов грамматики:

S(q) = (1), S(p) = (2, 3), S(r) = (4).

Пусть задана цель:

C = q(c) & r(d).

Ее отрицание:

щ C = (щ q(c), щ r(d)).

M-абстракция:

f(щ C) = (щ q, щ r).

Соответствующая цепочка w = qr. Имеем из шкалы значения 11. Следовательно, m-абстракция цели выводима. Используя параллельный алгоритм, построим вывод исходной цели, формируя вывод в грамматике с указанием применяемых правил и соответствующие им схемы. 

 

Вывод в G(f(E)) и номера правил	Вывод в f(E)	Вывод в E	Унификатор
qr     (1)	(щ q, щ r)	(щ q(c), щ r(d))	L
ppr   (2)	(щ p, щ p, щ r)	(щ p(a), щ p(b), щ r(d))	L
pr     (2)	(щ p, щ r)	(щ p(b), щ r(d))	Унификатор отсутствует

 

Так как провести унификацию для продолжения вывода в E оказалось невозможным, возник тупик, означающий, что текущая схема непродуктивна. Алгоритм прекращает работу с ней и, осуществляя перебор, переходит к работе со следующей схемой. Эта схема строится применением на последнем шаге вместо правила 2 в G(f(E)) правила 3: 

 

Вывод в G(f(E)) и номера правил	Вывод в f(E)	Вывод в E	Унификатор
pr     (3)	(щ p, щ r)	(щ p(b), щ r(d))	L
r       (4)	(щ r)	(щ r(d)	L
e	L	L

 

Один вывод найден, но работа алгоритма не закончена, так как имеется еще одна схема, которая строится применением на втором шаге вместо правила 2 правила 3:

 

Вывод в G(f(E)) и номера правил	Вывод в f(E)	Вывод в E	Унификатор
ppr   (3)	(щ p, щ p, щ r)	(щ p(a), щ p(b), щ r(d))	Унификатор отсутствует

 

Возник тупик, означающий, что текущая схема непродуктивна. Так как перебор схем исчерпан, параллельный алгоритм заканчивает работу, построив единственный вывод цели. Данный пример иллюстрирует необходимость использования m-абстракции. Если бы в мультидизъюнкте (щ p, щ p, щ r) вывода в f(E) была удалена одна из литер щ p, выводы в грамматике, и в f(E) оказались бы неадекватными выводам в E.

Пример 3 [1]. Пусть задана следующая БЗ в ИП (a и b - константы, x - переменная):

E = { (1) (p(a), щ q(x), щ r(b)), (2) (p(x), щ t(x)), (3) (q(b), щ p(a), щ t(a)), (4) (t(b)), (5) (t(a)) }.

Пропозициональные m-абстракции, построенные по множеству E:

f(E) = { (1) (p, щ q, щ r), (2) (p, щ t), (3) (q, щ p, щ t), (4) (t), (5) (t) }.

Грамматика, построенная по множеству f(E):

G(f(E)) = { V_N, Q }; V_N = { p, q, r, t }; Q = { (1) p ® qr, (2) p ® t, (3) q ® pt, (4) t ® e, (5) t ® e }.

Двоичная шкала символов:

 

p	q	r	t
1	1	0	1

 

Списки правил, выделенных для укорачивающих символов грамматики:

S(p) = (2), S(q) = (3), S(t) = (4, 5).

Пусть задана цель:

C = q(x) & p(x).

Ее отрицание:

щ C = (щ q(x), щ p(x)).

M-абстракция:

f(щ C) = (щ q, щ p).

Соответствующая цепочка w = qp. Имеем из шкалы значения 11. Следовательно, m-абстракция цели выводима. Используя параллельный алгоритм, построим вывод исходной цели, формируя вывод в грамматике с указанием применяемых правил и соответствующие им схемы. 

Вывод в G(f(E)) и номера правил	Вывод в f(E)	Вывод в E	Унификатор
pq     (3)	(щ q, щ p)	(щ q(x), щ p(x))	(x = b)
ptp    (2)	(щ p, щ t, щ p)	(щ p(a), щ t(a),   щ p(b))	(x = a)
ttp	(щ t, щ t, щ p)	(щ t(a), щ t(a),    щ p(b))

 

В дизъюнкте вывода в E литера щ t(a) оказалась представленной двумя копиями. Поэтому параллельный алгоритм удаляет одну из них, а также соответствующие копию в мультидизъюнкте вывода в f(E) и символ в цепочке вывода в G(f(E)):

 

Вывод в G(f(E)) и номера правил	Вывод в f(E)	Вывод в E	Унификатор
tp    (4)	(щ t, щ p)	(щ t(a), щ p(b))	Унификатор отсутствует

Возник тупик, означающий, что текущая схема непродуктивна. Алгоритм прекращает работу с ней и, осуществляя перебор, переходит к работе со следующей схемой. Эта схема строится применением на последнем шаге вместо правила 4 в G(f(E)) правила 5: 

 

Вывод в G(f(E)) и номера правил	Вывод в f(E)	Вывод в E	Унификатор
tp   (5)	(щ t, щ p)	(щ t(a), щ p(b))	L
p    (2)	(щ p)	(щ p(b))	(x = b)
t     (4)	(щ t)	(щ t(b))	L
L	L	L

 

Один вывод найден, но работа алгоритма еще не закончена, так как имеется еще одна схема:

 

 

Вывод в G(f(E)) и номера правил	Вывод в f(E)	Вывод в E	Унификатор
t   (5)	(щ t)	(щ t(b))	Унификатор отсутствует

 

Здесь вновь возник тупик, и так как перебор схем исчерпан, алгоритм заканчивает работу, построив единственный вывод цели. Отметим, что параллельный алгоритм не пытался строить вывод путем резольвирования литеры     щ p(a) с дизъюнктом 1: (p(a), щ q(x), щ r(b)). Это вызвано тем, что правило 1 грамматики p ® qr не попало в S(p). Из обоих примеров также хорошо видно, что непродуктивные схемы удаляются из рассмотрения уже в процессе их построения. Если бы алгоритм строил схемы и выводы последовательно, непродуктивные схемы формировались бы полностью. 

Можно доказать полноту рассмотренного метода поиска логического вывода с предварительной настройкой, а также идентичность выводов, полученных данным методом, с выводами, полученными входной линейной резолюцией. В то же время, очевидно, что метод с предварительной настройкой во многих случаях эффективнее входной линейной резолюции. Было произведено сравнение этих двух методов и получены статистически значимые результаты, показывающие предпочтительность метода с предварительной настройкой.