- •Глава 1 Представление знаний
- •1.1. Данные и знания
- •1.2. Логические модели
- •Логическое следствие и логический вывод
- •1.3. Сетевые модели
- •1.4. Продукционные модели
- •1.5. Сценарии
- •1.6. Ленемы
- •2.1. Приобретение и формализация знаний
- •Методы работы со знаниями
- •2.2. Пополнение знаний
- •2.3. Обобщение и классификация знаний
- •2.4. Дедуктивный вывод на знаниях
- •Резолюция с абстракцией
- •2.5. Неточный вывод на знаниях а. Р. Хачатрян
- •Краткая история
- •Глава 3 Общение
- •3.1. Уровни понимания
- •Основные определения
- •Классификация уровней понимания
2.2. Пополнение знаний
Л. В. Литвинцева, Д. А. Поспелов Основные определения
Проблема пополнения знаний возникла при решении задач понимания естественного языка, обучения, поиска ответов на вопросы к базе знаний, анализа ситуаций, сцен и др. Знания могут быть преставлены в виде фактов, хранящихся в базе знаний, или в виде описаний ситуаций, поступающих на вход ИС.
При описании ситуации человек обычно не стремится сообщить все подробности, относящиеся к этой ситуации. Однако большинство опущенных деталей необходимо для того, чтобы полностью понять ситуацию. В связи с этим требуются механизмы восстановления пропущенной информации. Например, если че-76
ловек воспринимает сообщение «Воронам же, гнездящимся на ветках, все нипочем», то он скорее всего не будет думать, что ветки с воронами висят в пространстве. Он представит дерево, на ветвях которого расположены гнезда, а в них вороны. Однако даже такой тривиальный вывод требует достаточно большого числа рассуждений: что ветка является частью дерева, что птицы вьют гнезда на деревьях, что деревья растут на земле и т. д. Этот простой пример предполагает использование сложной процедуры вывода на основе знаний, хранящихся в памяти.
Можно указать несколько подходов к пополнению знаний: модели «здравого смысла» [Шенк, 1980], сценарии (см. § 1.5) [Литвинцева, 1986], подход, опирающийся на идею о том, что физические закономерности внешнего мира могут быть описаны в рамках специальных псевдофизических логик [Поспелов Д., 1986J. Все эти подходы в той или иной мере используют идею продукционных правил (см. § 1.4).
Система продукций отражает закономерности, присущие заданной проблемной области. Например, для ситуаций, описывающих статические пространственные отношения между объектами, можно выбрать следующие продукции:
х <содержится в> у, у <содержится в> z=>x <содержится в> z (свойство вложенности, которое выполняется в «матрешках»);
х <находится на> у, z <находится на> x=*>z <находится над> у.
Пополняя постепенно базу знаний продукциями такого типа, можно в ИС создать достаточно мощные средства для порождения новых фактов из тех, которые в ней имеются. Процедуры пополнения знаний отличаются друг от друга структурой продукционных правил и стратегиями управления в системе продукций.
Псевдофизические логики
При определенных стратегиях управления система продукций превращается в дедуктивную логическую систему. Широкий класс таких систем называется псевдофизическими логиками (ПФЛ). В их аксиомах и правилах вывода используются не только реальные физические свойства окружающего мира, но и особенности его восприятия человеком. ПФЛ обладают рядом особенностей.
ПФЛ есть логики отношений: временных, пространственных, каузальных, действия.
Часть рассуждений в ПФЛ связана со шкалами: метрическими (абсолют* ними и относительными) и топологическими. На абсолютной метрической шкале задан некоторый масштаб и выбрана точка отсчета; на относительной указыва ется лишь расстояние между точками, а начало отсчета может «плавать». Топо логическая шкала представляет собой порядковую шкалу. На ней указываются отношения порядка (строгого, нестрогого, размытого) между упорядочиваемыми объектами. Различные абсолютные шкалы преобразуются друг в друга. Для перехода от относительной шкалы к абсолютной требуется определить абсолют ное значение начальной точки отсчета, после чего легко переводятся остальные точки шкалы. Изоморфизма между топологическими шкалами не существует.
ПФЛ содержат в качестве аксиом утверждения, вытекающие из восприя тия мира человеком, которые подтверждаются результатами соответствующих психологических экспериментов.
Совокупность ПФЛ характеризуется связями между отдельными частя ми— логиками (например, логика времени тесно связана с логиками простран ства и действий).
Существуют модели временных логик [Литвинцева и др., 1986], статической пространственной логики [Варосян и др., 1982], фрагменты логики действий и каузальной логики [Кандрашина и др., 1989].
Каждая ПФЛ является системой, включающей модель предметной области в виде понятий и отношений, существующих в ней, и модель вывода. Первая модель задает формальный язык описания знаний (ситуаций), вторая позволяет получать пополнение этих знаний.
77
Рассмотрим
примеры конкретных ПФЛ и пополнение
знаний на их основе.
Логика времени. Введем множество T*={t\, t2, t3, ...}, элементы которого назовем моментами времени, и множество Р={Р\, Р2> ■ ■ •, Рп), элементы которого назовем событиями. Будем говорить, что событие р/ происходит в момент времени tj, если ему можно приписать момент времени /,-. Если для pj существует лишь один момент времени, в который оно происходит, то событие р/ называется точечным; если оно сопоставляется с некоторой непрерывной последовательностью моментов, то оно называется интервальный.
За исходные свойства времени примем однонаправленность, линейность, непрерывность, бесконечность, гомогенность. Заметим, что из свойств однонаправленности и линейности вытекает свойство транзитивности времени.
На множестве sczPi точечных событий зададим шесть временных отношений трех типов: неметрические (г0 — одновременно, г\ — быть раньше, г2 — быть позже); метрические и частотные (r3n>L — быть раньше на п единиц (п=\, 2, 3, ...) по шкале L, г+Ч — происходить в момент t на шкале L, rsLn — происходить с частотой л на шкале L, где Leif — множество шкал).
На множестве sczP2 интервальных событий зададим 14 временных отношений: R\ — строго предшествовать во времени; R2 — строго следовать; /?3 — пересекаться и др. [Литвинцева и др., 1986].
Выбранная базовая система временных отношений не является минимальной и единственно возможной. Стремление к минимальности не всегда оправданно. Чем меньше отношений, тем более громоздкое предстаплснке ситуаций и тем больше длина вывода.
Зададим множество М правил построения ППФ в логике времени, которыми являются комбинации троек типа (piRpi), где pi, p/e=P, /?<={г„, ru ..., гъ,
R\, /?2 Ru}- Множество аксиом Г составляют продукции вида а, рЬ-V-
Имеется также три правила вывода:
П
риведем
примеры схем аксиом в логике времени:
0)
(2)
(3) (4)
(Pi гпъ'1 Pi), (Pi rlL a) |- (p{ $+»*pk),
(Pi r\ t), (pt rl'L p}) h P} r\ (t®n), где ф —операция сложения времен на шкалах,
(Pi гх Pj), (pf rx pk) \- (pt rx pk).
Посмотрим, как работают эти схемы в задаче пополнения знаний. Пусть на вход ИС поступает следующее описание ситуации в виде текста на естественном языке: «Самолет, следовавший рейсом Баку—Москва, совершил посадку в аэропорту в 15 ч 20 мин. Через 10 мин был подан трап. Затем прибыл автобус. Пассажиры покинули самолет. Через 3 мин автобус доставил их в здание аэровокзала:». Для простоты будем считать, что события данного текста точечные. Выделим их: рх~ «посадка самолета», р2 — «подача трапа>, р3 — «прибытие автобуса>, р* — «выход пассажиров из самолета», р& — «доставка пассажиров в здание аэровокзала». Описание ситуации на языке М выглядит так:
где /=15 ч 20 мин на шкале L с единицей измерения «минута».
Формальное представление событий текста обрабатывается процедурой пополнения, которая выведет следующие факты:
(Pirtt), (Plrl°'Lp2)\-(parit,).
где /.-=15 ч 30 мин на шкале L (по схеме 2);
78
(Pi r\OtL Pi) h (Pi ri Pi) (п0 схеме 3>;
(Pi ri P2). (P% ri Pt) h (Pi rx fa) (по схеме 4); (Pt r*'L Ръ) \- (Pa ri Рь) (п0 схеме 3> •
Полученные в результате вывода дополнительные факты служат для расшире ния ситуации, описанной исходным текстом. /гтдпгт,
Логика действий. Псевдофизическая логика действий (ПФЛД) представляет собой логическую систему, описывающую семантические и прагматические свойства физических действий, условия их протекания во времени и пространстве, их взаимодействие, а также цели и мотивы действующих лиц. Действия могут быть связаны между собой различными способами: во времени, в пространстве, посредством одного и того же исполнителя, одного объекта, на которое направлено действие. Наряду с этими простейшими связями существуют и более сложные зависимости. Одна из них — каузальная.
Различаются следующие типы каузальных отношений между действиями:
Л1 — необходимая и достаточная причина. Действия d\, d2 связаны отношением пи если реализация d\ всегда вызывает реализацию d$t н, наоборот, появление d% всегда вызывается d\\ чаще всего лх отражает различные физические законы реального мира (например, сверкнула молния — грянул гром).
л, достятпчняя причина, которая означает, что реализация di всегда вы зывает d2y однако из появления d2 не всегда следует появление d\ (например, «нырнул в реку, оказался в воде»).
Яд — обусловливающая причина. Действия d\, d2 связаны отношением Яз, если реализация d\ обеспечивает необходимые условия для реализации dt, которое, однако, может и не произойти (например, «вошел в комнату, включил свет»).
Опишем действия в виде предикатов dt (Sk, О/, Im, tt, lp), где в качестве аргументов выступают глубинные падежи данного действия: субъект, объект, инструмент, время реализации действия и его локализация. Введем следующие множества: множество действий £><={ii, d2, ..., dn); множество объектов О— "{Oi, 02, ..., От); множество инструментов 1—{1\, 12 //}; множество вре мен T={U, h U}\ множество локализаций L={h, ls /Р}.
На множестве действий рассмотрим множество из восьми отношений, характеризующих их взаимосвязь: Ri° — действие di является частью действия dfi #2° — действие dt приводит к результату dj; R»D—действие dt сопровождается действием d}\ RtD — субъект действия di(Sk) имеет цель dj; /?sD — субъект действия di(Sn) имеет мотив d} (считается, что в качестве результатов, целей и мотивов выступают другие действия). Сюда же относятся три каузальных отношения л/ между действиями. Выделенная группа отношений составляет базовую систему отношений ПФЛД.
Схемы аксиом ПФЛД описывают семантические и прагматические свойства физических действий. Приведем несколько схем правил, описывающих действия:
di(U)Rdj(fi)\- U <быть раньше> tf, где R={nu n2, п3);
di(ti)RiDd/(t}) \—ti <пересекается t};
<&(S/, Oj, 1э, tm)\—d'(Oh Ik, tm), где <Г={находиться около}, dt&D'cD;
di(Sit Oj, ^) |— d'(St, Oj, tk), где dr— {находиться около}, di<=D'czD\
diRt»di, djRtDdk\~dtJbdk; 6) di(Sj)\~diR^d
{переместиться
df(Su lh **)|-^W<nS«, //, tm), где tm внутрь; войти; ... и т. п.}, (*"*={находиться в};
d'(Su tj, h)\~d'R2°d"(Su th tm), где tm-U+At, ^-{переместиться изнутри; выйти; ... и т. п.}, d"={находиться вне);
d'(Sit lP, th), (/р<часть>/т)|— d'(Sit lm, h), где ^/'={войти; ... и т. п.};
10) d'(Oit lm, h), d"(Sp, Ot, tk)\~d'(SP, lmt th), где ^-{двигаться к; мчаться; помчаться; ... и т. п.}, с?'/={находиться в; сидеть; ... и т. п.}.
Схемы правил позволяют анализировать и пополнять динамические ситуация. Рассмотрим пример такого пополнения. Пусть на вход ИС поступил следующий текст: «На маленькой станции он вошел в вагон, и поезд помчался
79
I
на юг вдоль проселочной дороги. Промелькнуло несколько деревень. Он вышел, когда поезд остановился у берега». Выпишем действия, упомянутые в расск-зе; d\ — «вошел», dz — «помчался», rf3 — «промелькнуло», d±— «вышел», й$~-«остановился». Используя схемы правил, получаем:
rfi(OH, вагон, Л), (вагон<часть> поезд) \—d\(ОН), поезд, /J;
di{OU, поезд, t\)\—d'{OU., поезд, /i-t-Л/), где d'^= {находиться в};
d'(OW, поезд, ti+At), d2 (поезд, юг, Л+Д/)> da (ОН, юг, ti+At);
d4(OH, вагон, t2) \— d"(OH, вагон, г^+ДО. гДе d"= {находиться вне}.
Описанный вариант ПФЛД представляет собой попытку смоделировать рассуждения человека о физических действиях в рамках здравого смысла. Концептуальное ядро ПФЛД составляет система отношений на действиях и схемы правил (аксиом), описывающие их свойства.
Пополнение знаний на основе сценариев
Пополнение знаний можно выполнить с помощью сценариев (см. § 1.5). Опишем основные схемы рассуждений на сценариях, используемых при выводе. Часть схем является интерпретацией значений слотов сценария (СЦ).
Схема 1. Пусть в СЦ значением слота «ключ» является имя события р+, а значением слота «посылки» — список имен событий (piy p2,-..,ph). В этом случае имеют место соотношения (PiR\p>), (р^ьр*), С-=1, 2,...,«, где Н\ — отношение предшествования во времени, я3 — каузальное отношение.
Схема 2. Пусть в СЦ значением слота «ключ» является имя события /?*, а значением слота «следствия» — список имен событий {ри р2,...,рт). Тогда имеют место соотношения (piRip*), (риьр*), t=l, 2,.... А, где ^ — отношение «следовать за».
Схема 3. Обозначим множество значений слотов «посылки» через X, а мно' жество значений слота «следствие» через У. Имеют место следующие утверждения: для Vpi^X и УРз<=У верно (pt «предшествует» р^).
Схема 4. Пусть ц — значение слота «цель деятеля» в СЦ, р, — имя ключевого события. Верно следующее: (p*Riu), (р*л3ц).
Схема 5. Пусть р\* — значение слота «ключ» в СЦ1, р2* — значение аналогичного слота в СЦ2. Известно, что pt*n3pz*. Обозначим множество значений слота «посылки» в СЦ1 через Хи а в СЦ2 —через Х2; множество значений слота «следствие» в СЦ1 — через Yh а в СЦ2 — через Y2. Имеют место следующие отношения: из \р^Ху и \р^Х2 следует (ptRipj); из Ypk^Yj и Ypm€=Y2 следует {PhR\pm).
Схема 6. Рассмотрим случай схемы 5—р^лзрг*. Имеет место следующее: из Vpi€=X следует (рцг&ра*), где X=Xi{JX2.
Рассмотрим использование каузальных сценариев (КСЦ) для планирования действий во времени. Представим ситуацию «пожар», в которой находится робот. Цель его поведения — устранение пожара. Для нахождения последовательности действий, удовлетворяющей поставленной цели, планирующая система робота обращается к базе знаний, в которой находятся следующие сценарии:
1. (КСЦ «тушение пожара»: деятель (s :)
цель деятеля (р : «устранение пожара»); местоположение объекта пожара (/: be*); посылки (СЦ («поиск средств тушения» Ru транспортировка средств
тушения к объекту пожара»); ключ (/: «контакт средства тушения с огнем до полного прекращения
огня»);
следствие (р : «прекращение огня»); системное имя (sys : СЦ*1)). 2. (КСЦ «поиск средств тушения», деятель ($:);
80
цель деятеля (р: <Снахождение средств тушения»);
средства тушения (р : "Свода»);
посылки (/ («определение местонахождения средства тушения»» Ru
«движение к местонахождению средства тушения»)); кйюч (/.'«схватывание средства тушения»); следствие (р: «нахождение в месте расположения объекта средства
тушения»);
системное имя (sys : СЦ*2)).
3. (КСЦ «транспортировка средства тушения к объекту пожара»: деятель (s:)
цель деятеля (р : «наличие средства тушения в месте пожара»); посылки (/ («наличие средства тушения у деятеля» Ru «наличие координат местоположения объекта пожара»)); ключ (/: «передвижение к объекту пожара»), следствие (р ; «нахождение у объекта пожара»); системное имя (sys : СЦ*3)).
Спецификация значения слота / означает, что далее идет название процедуры, которая должна быть выполнена при реализации данного сценария. Отношение Ri представляет временное отношение «предшествовать на п единиц по шкале /,».
Общая схема построения плана достижения цели по сценариям такова:
Из описания проблемной области выбирается сценарий, значение слота «цель» которого соответствует поставленной цели (для рассматриваемого слу чая — первый сценарий).
Анализируются значения всех слотов указанного сценария и строится последовательность Пь являющаяся значением слотов «посылки» и «ключ» с их спецификациями. Для примера П: = СЦ («поиск средств тушения») Ri (СЦ «транс портировка средства тушения к объекту пожара») #i (f: «контакт средства тушения с огнем до полного прекращения огня»). Заметим, что второе отноше ние Ri получено с использованием схемы I.
3. Выполняется последовательное обращение к сценариям, указанным в П]. При этом фрагмент последовательности Пь имеющий вид (СЦ <имя>), заменяется соответствующей последовательностью Пг, построенной аналогично П|:
IIi=(f «определение местонахождения средства тушения») Ri (/ «движение к местонахождению оредства тушения») Ri (/ «схватывание средства тушения»).
В цепочке Пг отсутствуют спецификации типа СЦ, которые должны быть заменены. Следовательно, построение Пг закончено, и происходит возврат к обработке следующего фрагмента Пь
Второй фрагмент Ш со спецификацией СЦ заменяется на следующий: Пз=(/ «наличие средства тушения у робота») /?i (/ «наличие координат местоположения объекта пожара») Ri (/ «передвижение к объекту пожара»).
Последовательность Пз также не содержит спецификаций СЦ. На этом ее построение заканчивается.
Полученная расширенная последовательность П| представляет собой план действий во времени, состоящий из ммен конкретных процедур, реализация которых приводит к достижению поставленной перед роботом цели устранения пожара.
IIi=(/ «определение местонахождения средства тушения») Ri (f «движение к местонахождению средства тушения») Rt (/ «схватывание средства тушения») Ri [f «наличие средства тушения у деятеля») Rx (f «наличие координат местоположения объекта тушения») Ri (f «передвижение к объекту пожара») Rt (f «контакт средства тушения с огнем до полного прекращения огня»).
81
