8.7.2. Вывод двумерных грамматик

Вопросы, возникающие в связи с двумерными грамматиками, применяемыми в распознавании, подробно обсуждались в § 8.4 и 8.5. По существу, основная сложность применения этих грамматик заключается в точном определении правил двумерного соединения. В этом разделе мы представляем простой алгоритм, разработанный Эвансом [1971], иллюстрирующий построение двумерной грамматики в процессе непосредственного обучения. Алгоритм допускает, что соответствующие двумерные позиционные дескрипторы задаются учителем. В сущности, алгоритм основывается на следующей процедуре. Имея множество непроизводных элементов и позиционных дескрипторов, мы начинаем с непроизводных элементов и, применяя дескрипторы, строим более сложные структуры. Когда процесс завершается, мы выводим грамматику, используя для этого шаги построения структур. Рассмотрим эту схему на примере.

На рис. 8.11 изображены простые непроизводные элементы, позиционные дескрипторы и выборочный образ. Выборочный образ, несомненно, является комбинацией непроизводных элементов. Для упрощения системы обозначений назовем окружность выборочного образа «объектом 1», левый глаз — «объектом 2», правый глаз — «объектом 3», нос — «объектом 4» и рот — «объектом 5». Начиная с непроизводных элементов и последовательно применяя дескрипторы, можно построить различные сложные объекты.

Рис. 8.11. Элементы двумерных грамматик.

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

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

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

На следующем шаге из порожденных объектов строятся более сложные структуры:

Следующий уровень сложности достигается дальнейшей комбинацией ранее порожденных объектов:

Заметим, что объект 18 является полным терминальным описанием исследуемого образа, т. е. объект 18 — это объект 15, находящийся внутри объекта 1, представляющего собой окружность. Объект 15 — это в свою очередь объект 10, расположенный над объектом 11. Объект 10, с другой стороны, это один глаз, расположенный слева от другого, а объект 11 — это нос, расположенный над ртом. Таким образом, объект 18 представляет собой искомый образ лица.

Грамматика, порождающая выборочный образ, легко восстанавливается по шагам, ведущим к построению объекта. Так, грамматика для этого примера выглядит следующим образом;

где

Заметим, что множество правил подстановки является, в сущности, множеством правил построения образа. Если предположить, что S представляет лицо, то правила подстановки означают только следующее. Лицо представляет собой некоторый объект В, расположенный внутри окружности. Этот объект В представляет собой некоторый объект С, расположенный над другим объектом D, причем С — горизонтальный отрезок, расположенный слева от другого горизонтального отрезка (глаза), a D - это вертикальный отрезок, расположенный над горизонтальным (нос и рот).

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

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

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

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