8.3. ПОСТАНОВКА ЗАДАЧИ СИНТАКСИЧЕСКОГО РАСПОЗНАВАНИЯ ОБРАЗОВ

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

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

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

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

В связи с изложенным выше подходом к распознаванию возникает ряд существенных вопросов. 1) Как наилучшим образом описывать объекты для их классификации подобным способом? 2) Как выбираются грамматики распознавания? 3) Любая задача, имеющая практическое значение, обычно искажается случайными переменными, например шумами измерения; каким образом в синтаксическом подходе можно использовать статистический аппарат с тем, чтобы учесть эти случайные переменные? 4) Одной из наиболее важных особенностей рассмотренных ранее подходов к распознаванию образов является способность строить решающие функции посредством итеративных процедур обучения; можно ли распространить концепцию обучающей выборки на синтаксическое распознавание? Каждому из этих вопросов соответствует отдельный параграф.