8.9. ЗАКЛЮЧИТЕЛЬНЫЕ ЗАМЕЧАНИЯ

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

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

двумерных структур. Эту сложность можно в какой-то степени обойти, каким-либо предварительно установленным образом ограничивая правила соединения. В п. 8.5.2 приводятся примеры эффективного сведения двумерных объектов к терминальным цепочкам. Другой метод обработки многомерных образов заключается в использовании грамматик деревьев, как было указано в п. 8.5.3.

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

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

Задача вывода грамматики является лингвистическим эквивалентом алгоритмов обучения, изложенных в предыдущих главах. Однако, как отмечалось ранее, известные схемы вывода грамматики все еще имеют ограниченную область приложения. Алгоритмы из § 8.7 типичны для подходов, которые могут применяться при получении грамматики с помощью обучающей выборки предложений.

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

Библиография

Исчерпывающее введение в формальные языки можно найти в книге Хопкрофта и Ульмана [1969]. С середины 60-х годов быстрыми темпами растет поток литературы по синтаксическому распознаванию образов. Первые достижения в этой области принадлежат Идену [1961], Нарасимхану [1969], Киршу [1964], Ледли [1964, 1965] и Ханкли и Ту [1968]. Представление об основных тенденциях в синтаксическом распознавании образов можно получить при изучении обзорных статей Миллера и Шоу [1968], Фу и Суэйна [1971] и Гонсалеса [1972].

Язык описания изображений, приведенный в п. 8.5.2, — результат работы Шоу [1970], а грамматика распознавания хромосом создана Ледли [1964, 1965].

Исчерпывающее изложение методов грамматического разбора можно найти в книге Ахо и Ульмана [1978]. Великолепным справочником по древовидным системам является монография Кнута [1976]. Дополнительный материал по грамматикам деревьев можно найти в работах Фу и Бхаргавы {1973], Тэтчера [1973] и Гонсалеса и Томасона [1974а]. Сведения о стохастических грамматиках — в работах Фу [1971а], Ли и Фу [1971, 1972] и Бута [1969]. Алгоритм для цепочечных грамматик, представленный в п. 8.7.1, является адаптацией результатов Фельдмана [1967, 1969], а алгоритмом, приведенным в п. 8.7.2, мы обязаны Эвансу [1971]. Дополнительная информация о выводе грамматик — работы Фельдмана, Джипса, Хорнинга и Ридера [1969],    Фу [1972], Голда [1967], Хорнинга [1969], Пао [1969] и Креспи-Регицци [1971]. Введение в проблему вывода грамматик деревьев может быть найдено в книге Гонсалеса и Томасона [19746]. В качестве справочного материала к § 8.8 рекомендуются работы Хопкрофта и Ульмана [1969] и Фу [1970].

Задачи

(см. скан)

(см. скан)