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

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

1)       получение текста, описывающего сцену, наблюдае мую на улице, по ее графическому изображению и

2)       получение изображения сцены по словесному описанию.

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

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

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

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

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

Отметим, что множество М строится таким образом, что для каждой пары объектов, участвующих в ситуации, перечисляются все отношения, которые связывают объекты в этой ситуации, т.е; множество М фиксирует всю информацию о сцене, необходимую для дальнейшей работы. Вну1реннее представление знаний ориентировано на получение именно такой информации. В системе знания о сцене представлены в виде таблицы, входом в которую является упорядоченная пара объектов сцены, а результат представляет собой множество пространственных отношений, связывающих эти объекты. Список рассматриваемых отношений фиксирован (пополнение списка отношений сопровождается изменением программы). Таким образом, процесс перехода от рисунка к тексту происходит в два этапа:

1)       анализ изображения для построения таблицы;

2)       синтез текста по построенной таблице.

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

Очевидно, что текст, описывающий ситуацию, никогда не содержит всю информацию в явном виде, а отражает лишь некую часть, которая считается

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

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

Формально условия на искомую последователь-кость можно представить следующим образом.

Пусть S = (Sl,S2,...,SJ. S считается содержанием ситуации, если:

а)  5 = Р , где Р - предикат, вводящий объект х в рассмотрение (в русском языке ему соответствуют выражения типа "имеется", "находится в поле зре нии" и синонимичные им словосочетания, специфи ческие для каждого объекта, "растет дерево", "стоит дом" и т.д.);

x'R'y', то

б) S (l<i<n)^x R у, причем тройка х R у - эле мент множества М ;

если5/ = х R

г)  если Jt - объект, участвующий в ситуации, то существует S —x'R'y' такое, что х' = х; иначе говоря, число объектов совпадает с числом элементов в S;

д) если S"i R у И S =у R'z, то i> к, т.е. любой элемент вводится через уже введенный.

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

В предлагаемой системе процесс определения искомого подмножества S основан на механизме приписывания объектам и отношениям рангов чисел, которые упорядочивают для описания отношения и объекты по степени важности. Введение рангов для объектов позволяет среди пар обратных отношений, связывающих одни и те же объекты, выбрать то отношение, которое вводит объект с большим рангом через объект с меньшим рангом. Основанием для выбора рангов служат наблюдения за языковыми выражениями. Так, например, естественными считаются сочетания типа "человек в машине" или "человек под машиной", но не употребительны выражения "машина над человеком" или " машина под человеком". В исходном множестве М присутствуют (в описании соответствующих ситуаций) как те, так и другие элементы, в результирующую же последовательноств S должны попасть элементы, соответствующие естс ственным выражениям. Введение рангов для отношс ний позволяет среди всех троек вида х R у, вводящиэ объект х, выбрать такую, которая выражает самук тесную связь х с другим объектом. Именно эта связ! как наиболее информативная, сохраняется в результирующем тексте.

В экспериментальном варианте системы исследовались ситуации, описывающие уличные сцены с объектами типа "человек", "дом", "ель", "липа", "грузовик", "легковая машина", "велосипед", "шляпа", "лопата" и т.п. (хотя список объектов фиксирован, система строилась по возможности, не зависящей от конкретного набора объектов, — добавление новых объектов сводится к дополнительной кодировке исходных данных, но не приводит к изменению программы). Каждый объект представляется номером соответствующего ему эталона и референциальным индексом, указывающим номер объекта среди других объектов с тем же эталоном. Каждому эталону приписывается определенный ранг, не зависящий от конкретной ситуации. Отметим две особенности. Во-первых, некоторые объекты, определяемые в результате анализа сцены как соответствующие одному и тому же эталону, могут получить разные ранги. Например, эталон "ель" получает свой ранг в зависимости от того, каково положение соответствующего ему объекта в рассматриваемой сцене. Если объект непосредственно соответствует эталону, то этот объект получает один ранг и в результирующем тексте имеет имя "ель". Если же объект соответствует эталону с поворотом на 90 или 270 (что фиксируется в множестве М с помощью определенного одноместного отношения), то такой объект получает другой ранг и в результирующем тексте имеет имя "лежащая ель". Разные ранги приписываются из-за разной функции этих объектов. Сравним тексты: "Растет ель. Рядом с елью стоит машина" и "Лежит ель. Под елью стоит машина" - второй текст естественнее звучит так: "Стоит машина. На машине лежит ель", т.е. г("ель") <г("машина") <г("лежашая ель") - символом г{х) обозначим ранг элемента jr. Во-вторых, могут существовать объекты, идентификация которых затруднена. Например, в анализируемых нами сценах имеется объект "забор", который определяется в результате анализа сиены как два различных объекта (скажем, в случае если забор располагается по разные стороны дома или в заборе имеется калитка). Для обработки таких объектов нужны специальные правила отождествления.

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

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

Таким образом, первой частью нашей системы является система порождения описания сцены на естественном языке. Исходными данными этой части являются результаты работы процесса анализа ситуации, которые можно представить в виде списка объектов, участвующих в ситуации, и множества М троек вида х R у, где х и у — объекты ситуации, a R — отношение, связывающее эти объекты в данной конкретной сцене. Кроме того, объекты характеризуются еще н набором одноместных отношений. Указанные соображения легли в основу алгоритма, который по заданному множеству М строит последовательность S, соответствующую тексту описания сцены. В начале работы алгоритма происходит определенная корректировка исходного множества М. Во-первых, производится введение объектов, зависящих от одноместных отношений ("лежащий человек", "лежащее дерево" и т.п.). Во-вторых, производится отождествление разных объектов, если содержательно они соответствуют одному объекту ("забор"). Наконец, при выполнении заданных условий вводятся "спецотнощения" между объектами. Затем объекты упорядочиваются по рангам и для каждого объекта х выделяются такие тройки вида х R у, которые содержат R с наименьшим рангом среди других таких же троек и для которых Нх)> Ну). Из таких троек выбирается минимальное количество, исходя из следующих соображений:

а)   если х R у & х R у &. у R у , to вычеркивается тройка х R у (т.е. из двух объектов у и у выбира ется такой, с которым х связан отношением R непо средственно);

б)   если х R у & х R у & Ну) <Ну), то вычеркива ется тройка х R у . Если при этом объекту х будет соответствовать одна тройка, то эта тройка и войдет в результирующую последовательность. Если же для объекта х останется несколько троек х R у , х R у, ..., х R у (заметим, что при этом Ну )= HyJ= — — Ну)), то строится новый объект вида у & у Si. ... & у (содержательно этот объект соответствует сово купности объектов у , у , ..., у ) и в результирующую последовательность входит тройка вида xR(y &у & ...

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

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

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

Здесь используется словарь объектов и отношений, а также определенные лингвистические закономерности, среди которых отметим: актуальное членение, определяющее порядок слов в порождаемом предложении; введение определений ("над человеком {имеется} шляпа" —>■ "человек в шляпе"); выбор глагола для введения тех или иных объектов ("солнце светит", "облако плывет", "домик стоит", "елка растет"); склейка двух предложений с помощью слова "который"; выражение рсференциалькых индексов для разных объектов одного класса; формирование новых понятий и т.д. [1, 3]. Попутно проводится автоматическое редактирование получаемых текстов.

Второй частью системы является система ответов на вопросы по содержанию сцены.

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

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

Разумеется, в задачу системы не входит анализ и построение ответов на все возможные вопросы относительно описываемых объектов. В соответствии с этим рассматриваются три типа вопросов: общие вопросы ("верно пи, что X связан с Y отношением Л?"), вопросы об отношении ("каким отношением связан X с У?") и вопросы об объектах ("какой X связан с У отношением R?"). Разумеется, лексическое выражение вопросов более разнообразно. В частности, основные объекты X к У могут быть выражены не одним словом, а громоздким словосочетанием. Еще одно усложнение вопросов состоит в объединении основных типов с помощью логических операций И, ИЛИ и НЕ.

Анализ вопроса опирается на словарь основ, сопоставляющий каждому слову его семантическую характеристику и правила построения структуры вопроса одного из трех перечисленных выше типов. Процедура построения ответа предусматривает поиск в сцене основных объектов AT и У, определение связывающего их отношения и синтез ответа, форма которого зависит от типа и формы исходного вопроса [2].

И наконец, третьей частью системы является процесс построения изображения сцены по ее описанию на естественном (русском) языке. Этот процесс состоит из трех этапов.

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

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

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

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

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

Словарная информация ДЛЯ каждого слова представляет собой строку символов. Первый символ строки определяет "грамматический тип" слова. Затем следует список номеров эталонов, с которыми связано слово.

Рассматриваются следующие классы слов. /- существительные. Следующий за этим символом список указывает множество эталонов, которые могут обозначаться данным словом.

v - глаголы. Следующий за этим символом список указывает множество эталонов, которые могут вводиться данным глаголом.

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

г— названия отношений. Далее указывается номер называемого словом отношения.

1— определение. Далее указывается множество эталонов, к которым применимо определение. к - слово "который". I - союз "ии.

п — количественное числительное. Следующий символ указывает значение слова.

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

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

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

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

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

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

Второй этап - графический планировщик.

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

Каждому следующему объекту приписываются координаты, которые определяются как функция от координат хозяина и связывающего отношения. На основе этой информации по отношению R, которым каждый очередной объект связан с предыдущим, вычисляются координаты очередного объекта. Кроме того, по отношению R для каждой такой пары определяется последовательность выдачи изображений. Порядок выдачи существенен: сначала должны быть нарисованы объекты заднего плана, затем переднего (например для различения или интерпретации отношений "за" и "перед"). Первому объекту сцены приписываются условные координаты [0; 0], а координаты свободных объектов определяются фиксировано для каждого типа.

Третий этап — построитель изображений.

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

Программы, реализующие систему, написаны на языке Turbo-C с использованием графического пакета < graphic.h >.

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

Список литературы

1.     Ильин Г.М., Игнатова В.Н. Автоматический синтез текстов на естественном (русском) языке для описания сцен, распозна ваемых роботом. / Проблемы оптимизации дискретных систем. - Л.: Изд-во Ленинтр. ун-та. - Вып.25, Вычислительна! техника и вопросы кибернетики. - 1990. - С. 171-184.

2.     Ильин Г.М., Игнатова В.Н. Независимый семантический анализ вопросов в системе распознавания, описания и воспро изведения сцен. Автоматическое распознавание и синтез рече вых сигналов. // Труды / АН УССР. Ин-т кибернетики им. В.М. Глушхова. - Киев, - 1989. - С. 149-152.

3.     Ильин Г.М., Игнатова В.Н. Формальное построение содержа ния ситуации, распознаваемой роботом. / Робототехника. Л.: Леникгр. политехи, ин-т., 1977. - С. 22-28.