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

Теория

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

?1 и ?2—элементы алфавита V*, ? в собственности V+, а А в собственности VN. Эта грамматика допускает замещение нетерминального знака А цепочкой ? лишь в том случае, если А появляется в контексте ?1A?2, составленном из цепочек ?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.метод восстановления грамматик перечислением

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

эвристика — это не всецело математически обоснованный (либо кроме того «не совсем корректный»), но наряду с этим фактически нужный метод.

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

Лекция 5: Распознавание образов


Также читать:

Понравилась статья? Поделиться с друзьями: