Программные продукты и системы

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

Приведем классификацию глаголов, необходимую для анализа действий и их взаимосвязей.

1. Глаголы (в список их входит около 600), описывающие физические действия.

Эта группа включает в себя около 400 глаголов направленного действия, которые могут быть разделены на 4 подгруппы по типу физического движения: чисто колебательные, вращательные, поступательные и сложные движения, являющиеся комбинацией трех первых.

Глаголы, описывающие совокупности действий или состояний (например шить, танцевать).

Глаголы, обозначающие звуковые явления (говорить, звенеть).

Глаголы, выражающие акты восприятия (видеть, слышать).

Глаголы со значением наличия или отсутствия чего-либо (иметь, получать).

Глаголы, обозначающие процедуры взаимоотношений (награждать, дарить).

Глаголы, выражающие проявление чувств и психических состояний (плакать, смеяться).

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

ПРИНЦИПЫ ОРГАНИЗАЦИИ ФРЕЙМОВЫХ СЕТЕЙ ПЕРЕХОДОВ

Опишем общую структуру FTN (Frame Transition Network)-flnarpaMM переходов, в основу которых положен принцип сетевых грамматик Вудса. Их назначение состоит в декларативно-процедурном задании грамматики для анализа и интерпретации широкого спектра языков от формального до ограниченного естественного языка (ЕЯ).

FTN представляют конечный набор поименованных диаграмм переходов, изображаемых ориентированными взвешенными мультиграфами. Каждая вершина диаграммы означает некоторое состояние и соответствует определенному нетерминальному символу формальной грамматики. Вершины бывают трех типов: начальные вершины (обозначают состояние, с которого начинается анализ; в каждой диаграмме FTN имеется одна начальная вершина); концевые вершины (отличают состояние успешного окончания анализа); промежуточные вершины (все остальные вершины FTN).

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

Интерпретация FTN-сети для некоторого входного предложения заключается в следующем:

из начального состояния необходимо перейти в конечное по одному из путей;

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

если не существует ни одного пути, ведущего из данной вершины в концевую, то происходит возврат на шаг назад и повторяется попытка выбора нового пути,ведущего к концевой вершине.

Если из начальной вершины нельзя пройти ни по одному пути в концевую вершину, то анализ заканчивается неудачей.

Формализм фреймовых сетей переходов (FTN-формализм) позволяет строить модели контек-стнозависимых грамматик. Грамматику, которую можно задавать при помощи FTN-формализма, будем далее называть FTN-грамматикой. Под FTN-процессором следует понимать программу, реализующую FTN-грамматику, заданную при помощи FTN-формализма.

ФРЕЙМ-ПРЕДСТАВЛЕНИЕ FTN И ЕГО ИНТЕРПРЕТАЦИЯ

Каждая FTN-конструкция задается отдельным фреймом, синтаксис которого представлен на рисунке 1. Имя фрейма является именем FTN-диаграммы. Слоты определяют ее вершины с множеством выходящих дуг. Название вершины совпадает с именем слота. Каждая дуга перехода определена значением слота, а ее семантика уточняется множеством комментариев к этому значению.

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

Комментарии, связанные с дугой, определяют:

— вершину (состояние) FTN, в которую перейдет процессор после сопоставления дуги, причем имя вершины перехода может быть получено в процессе вычисления;

- приоритет или порядок, согласно которому FTN-процессор будет обрабатывать дуги, исходящие из данной вершины.

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

Дугам могут быть приписаны предикаты побочных действий.

Рис. I. Синтаксис фрейм-структуры FTN-диаграммы в расширенной нотации Бзкуса-Наура

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

Предикаты, называемые преддействиями, запускаются перед сопоставлением с дугой. Предикаты, обрабатываемые после сопоставления дуги, называются предикатами постдействий. В процессе работы FTN-процессора используется механизм автоматического возврата, работающий по принципу BACK-TRACKING.

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

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

Если именем FTN-дуги является системное имя GO_TO, то для прохождения по дуге не требуется сопоставления и поглощения слов из текущего предложения. Для реализации возможности вычисления имени дуги необходимо к описателям дуги добавить комментарий (STATUS: EVAL), который укажет FTN-процессору на то, что имя дуги должно быть получено в процессе вычисления. Если GO: опущен, либо задает переход на несуществующую вершину - это означает, что FTN-процессор находится в концевой вершине.

Проблема сохранения среды в FTN решается следующим образом: переменные, создаваемые и означиваемые специальными функциями 1SETQ и 1SET, являются локальными в пределах интерпретации создающей их FTN-конструкции. FTN-процессор обеспечивает их автоматическое сохранение и восстановление, используя системный стек. Переменные, определяемые функциями SET, SETQ, являются глобальными. Их значения доступны в пределах обработки любой FTN-конструкции.

ФРЕЙМЫ СЛОВАРНЫХ СТАТЕЙ

Синтаксис словарной статьи представлен на рисунке 2. Морфологические, синтаксические и семантические категории задаются в виде значений соответствующих слотов. Доступ к значениям категорий при анализе осуществляется посредством специальных команд в процессе выполнения побочных действий.

В слоте "-*11 словарных статей перечислены имена вакантных атрибутов (слотов), которые могут быть заполнены при сопоставлении экземпляров данного фрейма с другими сущностями. Заполнение будет возможным только в том случае, когда кандидат на заполнение успешно сопоставится со значением слота. Пассивность либо активность сущностей определяется в зависимости от контекста и может быть задана на дугах FTN функцией "IW.

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

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

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

Рис. 2. Синтаксис фрейм-структуры словарной статьи в расширенной нотации Бэкуса-Наура

Процедуры преддействий активизируются в процессе работы FTN-процессора всякий раз пе ред сопоставлением текущего слова предложения и терминальной дуги, а процедуры постдейст вий - непосредственно после сопоставления текущего слова предложения и терминальной дуги Процедуры возвратных действий активизируются только в случае выполнения двух условий: а процесс анализа успешно завершен (т.е. достигнута конечная вершина FTN); б) терминальная дуга, связанная со словом, содержащим процедуры преддействий, лежит на пути, соединяющие начальную вершину FTN с ее конечной вершиной.

ОБЩАЯ СХЕМА ФУНКЦИОНИРОВАНИЯ FTN-ПРОЦЕССОРА

Общая схема обработки текста в FTN представлена на рисунке 3. Информация от пользователя поступает на вход ЛП в виде печатного текста, содержащего анафоры (местоименные и именные ссылки) и эллипсисы (неполные конструкции). Исходный текст проходит этапы синтаксического и семантического анализа-

Этап морфологического анализа (МА) вырожден ввиду представления морфологической информации декларативно, т.е. в словаре системы хранятся все возможные словоформы каждого слова с соответствующей морфологической информацией. По сути дела, в декларативном МА нет собственно анализа, а хранится его результат.

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

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

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

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

Задача FTN-ннтерпретатора сводится к решению двух проблем: 1) установление взаимосвязи фактов, выраженных а тексте, с конкретными знаниями системы (выполнение данной задачи при отсутствии непосредственного совпадения фактов текста со знаниями приводит к необходимости вывода дополнительных знаний); 2) собственно обработка входного текста, т.е. вывод или вычисление ответа (в случае вопроса) или объединение информации из текста со знаниями системы (для утвердительных предложений).

Рис. 3. Общая схема обработки текста в FTN

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

FTN-среда представляет множество списков, стеков и переменных, используемых функциями побочных действий, в которых хранится информация о текущем состоянии FTN-процессора, в том числе ссылки на обрабатываемые структуры, результаты сопоставления и т.п. Установление местоименных ссылок происходит при сопоставлении фрейма, задающего местоимение, с сущностями стека контекста и базы знаний. Референт ссылки устанавливается на основании совпадения синтаксических и семантических категорий сущности кандидата и местоимения.

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

ПРИНЦИП СОПОСТАВЛЕНИЯ ФРЕЙМОВ

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

Сущность определяется совокупностью атрибутов и их значений. Каждый атрибут реализуется отдельным слотом. Атрибуты могут быть самых различных типов: синтаксические (род, число, падеж), семантические (форма, размер и т.п.), ролевые (агент, инструмент и т.п.). На состав и назначение атрибутов не накладывается никаких ограничений. Все они определяются разработчиком

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

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

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

Одна и та же сущность может выступать как в активной, так и в пассивной роли. Например, сущность слова зеленый практически всегда выступает пассивно и служит заполнителем слота цвет. Сущность шар может быть в активной роли {синий шар) либо в пассивной (шар лежит на столе). Пассивность либо активность таких сущностей определяется в зависимости от контекста и может быть задана на дугах FTN.

Для того, чтобы подключить семантику (в том числе процедуры формирования логического вывода, отрисовки объектов и т.п., используемые в проекте ТЕКРИС) к синтаксическому анализу, необходимо добавить операции семантического сопоставления к побочным действиям на дугах FTN. Процедуры семантического сопоставления имеет смысл включать в возвратные побочные действия FTN-диаграмм. В этом случае они будут активизированы только в случае установления факта синтаксической корректности входной фразы.

АЛГОРИТМ СОПОСТАВЛЕНИЯ ФРЕЙМОВ

Операция сопоставления представляется одной из основных при заполнении атрибутов и будет постоянно использоваться' в дальнейшем, поэтому имеет смысл определить ее более строго.

Фрейм F1 сопоставим с фреймом F2 (обозначение: F1>>F2), если выполнено одно из условий:

а) F1 и F2 — фреймы, причем их имена совпадают (Fl = F2);

б) F1 и F2 - фреймы, причем F1 является АКО-экземпляром фрейма F2 (обозначение: АКО

(Fl, P2));

в) F1 и F2 - фреймы, АКО (Fl, F2) - не выполнимо, в каждом из этих фреймов есть слот с име-

нем SELF, тогда, если значения слотов SELF в Fl и F2 совпадают, то F1 > > F2, иначе F1 > > F2 не выполнимо;

г) F1 и F2 - фреймы, причем F1 не является АКО-экземпляром F2 и для каждого значения V2

слота S* фрейма F2 может быть найдено значение VI в одноименном слоте S фрейма F1, которое с ним сопоставимо (т.е. VI > >V2);

д) F1 - фрейм, F2 - атом, причем F2 совпадает со значением слота SELF фрейма F1;

е) F1 - атом, F2 - фрейм, причем атом F1 удовлетворяет предикатам аспекта SREQUIRE слота

SELF фрейма F2;

ж) F1 - атом, F2 - атом, причем они совпадают (Fl = F2).

Заметим, что с пустым фреймом или слотом сопоставляется любой объект. Слот SELF используется в концевых точках процесса сопоставления. При сопоставлении фреймов можно указывать список слотов, на которых необходимо производить это сопоставление. Функция сопоставления возвратит Т в результате успешного сопоставления и NIL — в противном случае.

РЕАЛИЗАЦИЯ МЕХАНИЗМА УСТАНОВЛЕНИЯ РЕФЕРЕНТНЫХ ССЫЛОК И ВОССТАНОВЛЕНИЯ ЭЛЛИПСИСОВ В FTN

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

• Примечание. Список слотов, участвующих в процессе сопоставления, задается в каждом конкретном случае. По умолчанию в мэтчинге участвуют все слоты фрейма. Для функгри! семантического сопоставления /■«=, мэтчинг осуществляется по слотам, имена которых связаны со значением слота "-*" вдоль «сей АКО-цепочки.

ны в стек локального контекста *OBJECT_STACK*. При обработке очередного предложения выделяемые сущности сопоставляются с локальным контекстом. Если конкретная сущность сопоставилась с несколькими кандидатами на референта, то все они заносятся в слот REFERENCE данной сущности и участвуют во всех дальнейших сопоставлениях, в результате'которых должен остаться один из кандидатов, который и станет референтом сущности. Такие возможности реализуются функцией 1#, при обращении к которой следует указать второй (непустой) аргумент. В этом случае, после создания новой сущности, будет проведен поиск ее референта в контексте и, в случае успеха, новая сущность будет заменена ее референтом.

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

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

Факт наличия эллипсиса может быть установлен в случае незаполнения обязательных атрибутов сущности либо при отсутствии глагола в предложении. В первом случае инициализация процесса восстановления эллипсиса может быть возложена на саму сущность. Во втором случае в FTN могут быть предусмотрены дуги, обрабатываемые при отсутствии глагола. Их обработка может заключаться в поиске недостающего глагола в контексте.

ПРЕДСТАВЛЕНИЕ ЛОГИЧЕСКИХ ЗАКОНОМЕРНОСТЕЙ

Для представления логических закономерностей в языке FRL удобно использовать присоединенные процедуры, причем можно комбинировать прямой и обратный типы вывода, помещая соответствующие процедуры в аспекты SIF-ADDED и SIF-NEEDED соответственно.

Для иллюстрации вышесказанного рассмотрим фрагмент фрейма отношения НА:

(fassertq НА

(REQUIRMENTS (Sif-needed ((«= (1! ;frame 'АКТ1 'SIZE) (!! :framc 'AKT2 'SIZE)))))

(R-RELATTON (Sif-added ((progn

(check-&-add-rel '(HA :akt2 >x) '{НАД :aktl >x» (check-&-add-rel '(РЯДОМ :afct2 Ж) '(РЯДОМ :akll >x)) (check-&-add-rel '(РЯДОМ >х :aktl) "(РЯДОМ >х :akt2))

В аспекте SIF-NEEDED слота REQUIRMENTS содержится процедура, которая сравнивает размеры (значения свойств SIZE) заполнителей ролей АКТ1 и АКТ2 для экземпляра отношения НА, т.е. здесь представлено правило псевдофизической логики пространства: "Больший объект не может находиться НА меньшем объекте".

Для представления продукций вида (a R1 Ь) & (b R2 с) = > (a R3 с) можно использовать аспект SIF-ADDED. В приведенном выше примере отношения НА таким образом представлены правила:

(а НА Ь) & (Ь НА с) => (а НАД с)

(а НА Ь) & (Ь РЯДОМ с) => (а РЯДОМ с)

(а НА Ь) & (а РЯДОМ с) => (Ь РЯДОМ с)

Функция Check-&-add-rel проверяет, содержится ли среди экземпляров отношения НА хотя бы один, сопоставимый с дескриптором (НА :akt2 >x). Если да, то в базу фактов заносится экземпляр отношения НАД.