Книги по разным темам
Pages: | 1 | 2 | 3 | 4 | 5 | ... | 23 | Предположим, что имеется некоторый класс языков L, который задается определенным типом описаний. Теория формальных языков позволяет ответить на ряд вопросов, возникающих во многих прикладных задачах, в которых используются автоматно-лингвистические модели. Например, могут ли языки из класса L распознаваться быстро и просто; принадлежит ли данный язык классу L и т. д. Важной проблемой является построение алгоритмов, которые давали бы ответы на определенные вопросы о языках из класса L, например: Принадлежит цепочка Х языку L или не принадлежит Существуют два основных способа описания отдельных классов языков. Первый из них основан на ограничениях, которые налагаются на систему полусоотношений Туэ (продукций), на базе которых определяются грамматики как механизмы, порождающие цепочки символов. Другим способом является определение языка в терминах множества цепочек, с помощью некоторого распознающего устройства.
Такие устройства будем называть автоматами (автоматами-распознавателями).
Н. Хомский определил четыре типа грамматик, на основе которых оцениваются возможности других способов описания языков.
Пусть алфавит символов (непустое конечное множество), из которых строятся цепочки языка L, представляет собой алфавит терминальных символов VТ. Очевидно, что L VТ *.
Определение формальной грамматики требует наличия еще одного алфавита VN - непустого конечного множества нетерминальных символов (VN VТ = 0). Объединение этих алфавитов назовем словарем формального языка L:
V = VN VТ.
Условимся обозначать элементы алфавита VТ строчными латинскими буквами, элементы множества VN - прописными латинскими буквами, элементы словаря V* (цепочки символов словаря) - греческими буквами.
Определим также множество упорядоченных пар (полутуэвских соотношений) следующим образом:
П = {(, ) | V* VN V* V+}.
Каждая пара (, ) называется продукцией и обозначается как.
Заметим, что является элементом усеченной итерации словаря, поэтому среди продукций нет пар вида, где - пустая цепочка.
Формальная грамматика G - это совокупность четырех объектов:
G = (VT, VN, P, S), где Р - непустое конечное подмножество П, а S VN - начальный символ.
Типы грамматик по Хомскому обозначают: тип 0, тип 1, тип 2 и тип 3. Соответствующий тип грамматики определяется теми ограничениями, которые налагаются на продукцию Р.
Если таких ограничений нет, грамматика принадлежит к типу 0.
Единственное ограничение, налагаемое на длину цепочек и :
| | | |, относит грамматики к типу 1. Такие грамматики также называют контекстно-зависимыми, то есть грамматиками непосредственных составляющих (НС-грамматиками).
В том случае, когда цепочка состоит из одного символа, т. е. VN, грамматики относят к типу 2. В этом случае их называют бесконтекстными (контекстносвободными или КС-грамматиками).
Наконец, регулярными грамматиками (типа 3) называют такие, для которых VN, а VТ VN, либо VТ. Иными словами, правые части продукций регулярных грамматик состоят либо из одного терминального и одного нетерминального символов, либо из одного терминального символа.
Языком L(G), порождаемым грамматикой G, будем называть множество цепочек VТ, каждая из которых порождается из начального символа S в смысле полутуэвских соотношений Р данной грамматики. Другими словами, L(G) = { | VT* S *}.
Нетрудно видеть, что каждая регулярная грамматика является бесконтекстной, а каждая бесконтекстная грамматика является контекстно-зависимой. В свою очередь, каждая контекстно-зависимая грамматика - это грамматика типа 0. Обратное утверждение неверно. Очевидно, что имеется некоторая иерархия грамматик, которой соответствует иерархия формальных языков, каждый из них может быть порожден некоторой формальной грамматикой. При этом тип языка соответствует типу той грамматики, с помощью которой он может быть порожден.
С другой стороны, типы языков могут быть определены типами абстрактных распознающих устройств (автоматов). При этом язык определяется как множество цепочек, допускаемых распознающим устройством определенного типа. На рис. 1. приведена иерархия языков и соответствующие ей иерархии грамматик и автоматов как распознающих устройств.
юбое множество, порождаемое автоматическим устройством произвольного вида, порождается некоторой грамматикой типа 0 по Хомскому. Заметим, что для любого естественного языка, в принципе, возможно построить математическую модель, использующую такую грамматику.
Таким образом, грамматики типа 0 представляют собой порождающие устройства очень общего характера. А те формальные языки, с которыми имеют дело автоматно-лингвистические модели (язык программирования, ограниченные естественные языки), как показывает практика, всегда описываются языками типа 1 или 2.
Языки типа 3, которые называют автоматными языками, языками с конечным числом состояний, нашли широкое применение в исследовании электронных схем, а также в ряде других областей (например, исследование цепей Маркова).
Грамматика Языки Автоматы Тип Рекурсивно-перечислимые Машины множества Тьюринга Тип Линейно-ограниченные НС-языки автоматы Тип Автомат с магазинной КС-языки памятью Тип Регулярные языки Конечные автоматы Рис. 1.1. Иерархия грамматик, языков и автоматов 1.4. Распознающие устройства и автоматы Распознавание образов (объектов, сигналов, ситуаций или процессов) - едва ли не самая распространенная задача, которую человеку приходится решать практически ежесекундно от первого до последнего дня своего существования. Для решения этой задачи человек использует огромные ресурсы своего мозга, включая одновременно 10 - 12 миллиардов нейронов. Именно это дает возможность людям мгновенно узнавать друг друга, с большой скоростью читать печатные и рукописные тексты, безошибочно водить автомобили в сложном потоке уличного движения, осуществлять обработку деталей на конвейере, дешифровать аэро- и космические фотоснимки, разгадывать коды, древнюю египетскую клинопись и т. д.
Потребности в комплексной механизации и автоматизации, создании роботов, решении задач технической и медицинской диагностики, метеорологического прогноза, формализованной оценки общественных, экономических и социологических явлений и процессов, в определении наиболее вероятных направлений их трансформаций и предопределили значительные усилия научной и инженерной мысли, направленные на решение теоретических и прикладных вопросов проблем распознавания.
Распознавание представляет собой задачу преобразования входной информации в выходную, представляющую собой заключение о том, к какому классу относится распознаваемый образ. В качестве входной информации используются некоторые параметры или признаки распознаваемых образов.
1.4.1. Концепция порождения и распознавания На основе теории распознавания образов можно построить модель процесса распознавания и применительно к ней рассмотреть основные теоретические положения и понятия.
К одному из основных понятий относят понятие класс или образ.
Известно, что отдельные предметы или явления обладают общими друг с другом свойствами и имеют некоторые отличительные свойства. Классом (образом) можно назвать множество предметов или объектов, обладающих (объединенных) некоторыми общими свойствами.
Например, к классу карандаш относятся карандаши всех размеров и цветов, к классу красный карандаш относятся карандаши с красным грифелем, к классу пишущие устройства относятся карандаши, ручки, мел и пр.
Как правило, имеется набор классов или алфавит классов (образов):
A = {A1, A2,..., Ai,..., Am}, где Ai - отдельный i-класс; m - общее число классов.
Если m = 1, то никакого распознавания не нужно. Очень часто рассматривается задача отнесения объекта к одному из двух (m = 2) классов. Случай m = практически нереальный и рассматриваться не будет.
Следующее важное понятие - это объект, или реализация, или образ.
Каждый класс в алфавите образов может быть представлен некоторым количеством объектов или реализацией. Например, имеется по 100 штук красных, желтых и зеленых карандашей разных оттенков и размеров. Совокупность различных реализаций для всех классов образует множество возможных реализаций:
B = {b1, b2,..., bj,..., bT}.
В большинстве случаев Т - конечно и T >> m.
Определение понятия признак класса вызывало и вызывает большие споры.
При введении понятия класса указывается, что в класс объединяются образы, имеющие общие свойства. Эти свойства и составляют признаки данного класса. Обычно признаки задаются своими количественными значениями.
Для простоты будем считать, что все классы характеризуются одним и тем же количеством признаков N. Обозначим совокупность признаков для данного алфавита А следующим образом:
X = {x1, x2,..., xk,..., xN}.
В качестве примера можно привести диагностику какого-либо заболевания (например, гриппом). Тогда условно можно считать, что х1 - это температура;
х2 - кашель (сильный, слабый, средний, отсутствует);
х3 - покраснение горла и т. д.
Практически числовые значения признаков изменяются в некоторых пределах.
Каждый признак xk может принимать одно значение из совокупности:
xk = { xk1, xk2,..., xkp,..., xkR}.
Каждая конкретная реализация bj задается совокупностью значений признаков:
bj = { x1j1, x2j2,..., xkjk,..., xNjN}, которая называется описанием реализаций.
В теории распознавания часто прибегают к геометрической интерпретации.
Значения каждого признака откладываются по соответствующим осям прямоугольной системы координат. Если взять случай двух признаков (N = 2), то для случая трех градаций числовых значений признаков пространство признаков будет иметь вид (рис. 1.2).
Каждая из реализаций задается двумя значениями признаков:
b2 = { x13, x22}; b3 = { x13, x23} и т. д.
Количество возможных реализаций при N признаках, R градациях может быть определено как T = RN.
xb2 bx13 bbb5 bxb8 bx11 bx21 x22 x23 xРис. 1.2. Пространство признаков (N = 2) для случая трех градаций В большинстве задач распознавания имеется 2 этапа: обучение распознаванию на заданном количестве эталонных образов, принадлежность которых к определенному классу известна, и собственно распознавание, когда предъявляется реализация (объект) с неизвестной принадлежностью и требуется определить, к какому классу относится объект.
При рассмотрении моделей распознавания образов очень часто применяется понятие распознающей машины, под которой понимается некоторая система. На вход этой системы поступают объекты для распознавания, а на выходе появляются распознанные объекты, отнесенные к определенному классу.
Для каждого класса имеется определенное количество объектов, на которых происходит обучение. Геометрически в случае двух классов эти объекты будут представлены в виде двух многообразий точек (рис. 1.3).
Эти две области могут не перекрываться (рис. 1.3, а) или перекрываться (рис. 1.3, б). Очень часто в области перекрытия распознающая машина дает отказ от распознавания.
Х АВ Х А В 1 Х Х 2 а) б) Рис. 1.3. Геометрическая интерпретация объектов двух различных классов.
а) области объектов не перекрываются; б) перекрываются Одна из интерпретаций процесса обучения состоит в том, что необходимо максимально сжать множество эталонов каждого образа, максимально удалив их друг от друга. После деформации пространства признаков (в результате обучения) начинается собственно процесс распознавания. Обученной машине предъявляется образ, новая точка в деформированном пространстве, и требуется отнести ее к одному из двух образов.
Одним из способов распознавания, критерием распознавания, является классификация объектов по расстоянию от центральной точки (центров тяжести или рассеяния) множества данного образа или по сумме расстояния до всех эталонов данного образа. Если точка (объект) ближе к множеству первого образа, то его отождествляют с этим образом (рис. 1.4).
I II dd Рис. 1.4. Объект относится к I классу (d1 < d2) 1.4.2. Распознающие, порождающие и преобразующие формальные грамматики Трудности, возникающие при решении задач распознавания образов (классов) привели к разработке нового метода распознавания - структурного, получившего также название лингвистического или синтаксического. Его особенность заключается в том, что априорными описаниями классов являются структурные описания - формальные конструкции, при получении которых последовательно реализуется вначале учет иерархичности структуры объекта, а затем учет отношений, существующих между отдельными элементами этой иерархии, в пределах одних и тех же уровней между ними.
Поскольку практическая реализация структурных методов распознавания образов основана на использовании некоторых идей и методов математической лингвистики, рассмотрим ее основные понятия.
Термин формальная грамматика представляет собой общее название нескольких типов исчислений, используемых в математической лингвистике для описания строения естественных языков, а также некоторых искусственных языков, в частности, языков программирования.
Под грамматиками в математической лингвистике понимают некоторые специальные системы правил, задающие (или характеризующие) множества цепочек (конечных последовательностей) символов. Эти объекты могут интерпретироваться как языковые объекты различных уровней, например, как словоформы, словосочетания и предложения (цепочки словоформ) и т. п.
Следовательно, формальные грамматики имеют дело с абстракциями, возникающими в результате обобщения таких стандартных лингвистических понятий как словоформа, словосочетание и предложение. Из определенного набора символов (обозначающих, например, все словоформы русского языка) можно строить произвольные цепочки; одни из них естественно считать правильными или допустимыми, а другие - неправильными или недоступными.
Формальные грамматики задают правильные цепочки, если для любой предъявленной цепочки грамматика позволяет установить, является или нет эта цепочка правильной, и в случае положительного ответа дается указание о строении этой цепочки, либо грамматика позволяет построить любую правильную цепочку, давая при этом указания о ее строении, и не строит ни одной неправильной цепочки. В первом случае формальная грамматика называется распознающей, во втором - порождающей.
Pages: | 1 | 2 | 3 | 4 | 5 | ... | 23 | Книги по разным темам