Глава 7. ГРАММАТИЧЕСКАЯ КЛАССИФИКАЦИЯ ОБРАЗОВ

7.0. Лингвистический подход к анализу образов

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

Изучение в вычислительных науках лингвистики вызвано тем, что между программой и конструкцией машины, способной распознавать цепочки символов, представляющих собой правильно построенные выражения (предложения) на языке, определяемом порождающей грамматикой, существует некоторое соответствие. Как и в гл. 2, пусть — грамматика, — порождаемый ею язык, Т — множество терминальных символов, использующихся в — цепочка терминальных символов и Т — множество всех цепочек, которые можно построить из Т. Задача лингвистического распознавания языка (или, что то же самое, задача лингвистической классификации образов) состоит в том, чтобы за конечное число шагов выяснить, принадлежит ли произвольная цепочка множеству или Если можно построить алгоритм, осуществляющий это, то язык называют рекурсивным, а грамматику разрешимой. Существуют нерекурсивные языки. Для них можно построить алгоритм, который будет распознавать любую цепочку но нельзя гарантировать, что он будет останавливаться для всех цепочек Такие языки называются рекурсивно перечислимыми. Любой язык, определяемый порождающей грамматикой, рекурсивно перечислим. Если грамматика относится к типу 1

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

Классификация цепочек дает нам более общий подход к распознаванию образов, чем рассматриваемая до сих пор векторная классификация. Векторы представляют собой цепочки конечной длины, поэтому их можно описать с помощью некоторой порождающей грамматики. Так как каждому классу принадлежит только конечное число векторов, то „язык", соответствующий векторам некоторого (не обязательно непрерывного) подпространства евклидова пространства описаний, можно рассматривать как конечный. Конечные языки могут порождаться регулярными (типа 3) грамматиками. Но ранее мы говорили, что задача лингвистической классификации образов разрешима для более широкого класса грамматик типа 1. Поэтому лингвистический подход к классификации образов должен быть более общим. Кроме того, в гл. 2 указывалось, что алгоритм распознавания для языков типа 3 можно было бы выработать программой, не прибегающей к динамической памяти. Это наводит на мысль, что программы векторной классификации должны быть с вычислительной точки зрения, как правило, проще. Так именно и обстоит дело в действительности, хотя эти программы и могут быть довольно большими. Все рассмотренные в гл. 3—6 алгоритмы классификации образов можно написать на Фортране, при условии что память фиксирована и достаточно велика. Быть может, это и не очевидно, но это верно как для последовательных, так и для параллельных алгоритмов (Хант, 1967).

Тот факт, что задачу классификации векторов можно было бы интерпретировать как задачу классификации цепочек, подчас не оказывает существенной помощи ни в практическом, ни в интуитивном плане. А что можно сказать о задачах классификации цепочек, не имеющих формулировки на языке классификации векторов? В самом общем смысле это те задачи, в которых принадлежность объекта какому-то классу зависит не от булевой комбинации наличия или отсутствия признаков, а от соотношения (возможно, сложного) между составными частями объекта. Ясно, что лингвистические задачи как раз такого характера. Миллер и Шоу (1968) указывают на то, что другого способа работы трансляционной части алгоритма компиляции не существует. Отсутствует, например, множество признаков, отличающее программу на Фортране от бессмысленной цепочки символов, пробитых перфоратором.

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

Любит Мэри Джон

Джон любит Мэри

Мэри любит Джона

Джон любим Мэри

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

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

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

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

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

Бедняки должны получать поддержку правительства. Те, кто отказываются работать, не должны получать поддержки правительства.

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

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