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




Теория

Алфавит любое конечное множество. Элементами алфавита служат символы или буквы.

Цепочка (слово, предложение, строка) в алфавите произвольная конечная последовательность символов. Цепочки обозначают малыми греческими буквами.

множество всех цепочек в алфавите . множество всех непустых цепочек в алфавите .

Конкатенация двух строк есть .

Языком в алфавите называется произвольное подмножество множества (не обязательно конечное).

Язык, порождаемый грамматикой G и о бозначенный L(G),— это множество цепочек, удовлетворяющих двум условиям:

1) каждая цепочка составлена только из терминальных символов (т. е., является терминальным предложением), 2) каждая цепочка может быть выведена из S путем соответствующего применения правил подстановки из множества Р.

Формальная грамматика это упорядоченная четверка, в которой конечное множество нетерминальных символов (нетерминалов, переменных); конечное множество терминальных символов- непроизводные символы (терминалы, константы); конечное множество правил вывода (продукций, подстановок); стартовый нетерминал.

Продукция построена из .

Дополнительно алфавит грамматики; .

Нетерминалы обозначаются заглавными латинскими буквами S, А, В, С,, терминалы – строчными латинскими буквами а, Ь, с. Смешанные цепочки из терминалов и нетерминалов обозначаются греческими буквами α, β, γ, δ,.

цепочка непосредственно выводима в грамматике из цепочки .

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

Если и , то цепочку называют сентенцией грамматики .

Языком грамматики называют множество всех сентенций данной грамматики и обозначают . Возможно, что две различные грамматики порождают один и тот же язык; тогда их называют эквивалентными.

Грамматики классифицируют по структуре их множества продукций.

§ Обобщенные грамматики (неограниченная грамматика) с правилами вида .

§ Грамматики непосредственно составляющих(контекстная грамматика грамматика составляю­щих, НС-грамматика ) с правилами вида

α1 и α2 —эле­менты алфавита V*, β принадлежит V+, а А принадлежит VN. Эта грамматика допускает замещение нетерминального символа А цепочкой β только в том случае, если А появляется в контек­сте α12, составленном из цепочек α1 и α2.

§ Контекстно-свободные грамматики(бесконтекстные) с правилами вида . Само название «бесконтекстная» ука­зывает на то, что переменная A может замещаться цепочкой β независимо от контекста, в котором появляется А.

§ Регулярные грамматики (автоматные) с правилами вида . 2) S-> в этом случае дополнительное ограничение-S не должно встречаться в правых частях никаких продукций.

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

Этот подход часто называют синтаксическим распознаванием образов, хотя в литературе часто встречаются как лингвистическое распознавание.

Предположим, у нас имеются два класса образов ω1 и ω2 и пусть образы этих классов могут быть построены из признаков, принадлежащих некоторому конечному множеству. Назовем эти признаки треминалами и обозначим множество терминалов символом VТ. В синтаксическом распознава­нии образов терминалы называются также непроизводными символами (элементами). Каждый образ может рассматри­ваться как цепочка или предложение, поскольку он составлен из терминалов множества VТ. Допустим, что существует грам­матика G, такая, что порождаемый ею язык состоит из предло­жений (образов), принадлежащих исключительно одному из классов, скажем ω1 . Очевидно, что эта грамматика может быть использована в целях классификации образов, так как задан­ный образ неизвестной природы может быть отнесен к ω1, если он является предложением языка L{G}. В противном случае образ приписывается классу ω2.Процедура, ис­пользуемая для определения, является или не является цепочка предложением, грамматически правильным для данного языка, называется грамматическим разбором (то есть решается задача распознавания).

Основным отличием синтаксического распознавания образов от всех рассмотренных ранее является непосредственное использование структуры образов в процессе распознавания.

Задача распознавания образов 3 подхода:

1. Имеем эталонные цепочки, каждая из которых принадлежит некоторому языку. Тогда x относится к тому классу с эталоном которого он наилучшим образом совпадает.

2. Каждому языку ставится в соответствие мн-во синтаксических правил данного языка, каждое такое правило устанавливает степень допуска/запрета соответствий между цепочек данного языка.

Классифицируемый образ относится к тому классу набору синтаксических правил которого он не противоречит.

3. Основана на использовании формальной грамматики.

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

Обучение распознавания лингвистических образов:

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

Иначе задачу обучения распознавания лингвистических образов называют восстановлением грамматики.

Vt - алфавит

St={x1,…..xt} обучающая выборка

St+ - часть выборки, содержащая цепочки L(G*), то есть выводимых из G

St- - часть выборки, содержащая цепочки L(G*), не выводимых их G

St- Vt* \ L(G*)

St= St+ St-

Имеем алгоритм А, который делает следующее: для St формирует грамматику Gt, которая порождает язык, который выводит цепочку из St+ и которая не выводит цепочку из St-.Пусть множество мн-во всех грамматик, которые может формировать алгоритм А. и пусть Gt . Предположим, что грамматики, которые нас интересуют, тоже находятся в этом мн-ве.

Задача восстановления грамматики G называется разрешимой, если существует такой алгоритм А, который на некотором шаге формирует грамматику Gt эквивалентную G. за конечное число шагов

Восстановленная грамматика разрешима если она существует алгоритм А, который на некотором шаге формирует грамматику Gt эквивалентную G, за конечное число шагов.

 

 

Будем говорить, что St={x1,…xt} задана в текстуальном представлении, если выполняются два условия:

1. Для любого t St=St+ (состоит из примеров языка)

2. Для любой цепочки x, x L(G*) существует t, x St+

Будем говорить,что St дана в информативном представлении, если выполняются следующие условия:

1. St= St+ St ,где St+= и St-=

2. а) x L(G*) существует t’, x St+

б) y Vt*\ L’(G*) существует t’’ и y St-

Существуют два класса алгоритмов восстановления грамматик:

 

1.алгоритм восстановления грамматик индукцией.

2.алгоритм восстановления грамматик перечислением

В восстановлении методом индукции используется эвристический подход.

эвристика — это не полностью математически обоснованный (или даже «не совсем корректный»), но при этом практически полезный алгоритм.

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

 

 



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-08-08 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: