Теория

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

α₁ и α₂—эле­менты алфавита V^*, β принадлежит V⁺, а А принадлежит V_N. Эта грамматика допускает замещение нетерминального символа А цепочкой β только в том случае, если А появляется в контек­сте α₁Aα₂, составленном из цепочек α₁ и α₂.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

V_t - алфавит

S_t={x₁,…..x_t} обучающая выборка

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

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

S_t^- V_t* \ L(G^*)

S_t= S_t⁺ S_t^-

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

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

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

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

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

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

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

1. S_t= S_t⁺ S_t ,где S_t⁺= и S_t^-=

2. а) x L(G^*) существует t’, x S_t’⁺

б) y V_t*\ L’(G^*) существует t’’ и y S_t’^-

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

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

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

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

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

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

Теорема о разрешимости для информативного представления

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

Теорема о неразрешимости для текстуального представления грамматик

(алгоритм восстановления грамматик перечислением):

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

Приведенные теоремы важны по следующим причинам:

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

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

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

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

Вывод цепочечных грамматик:

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

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

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

Алгоритм Фельдмана.

1. Постановка задачи:

Дано: множество выборочных цепочек {x_i}.

Требуется: подвергнуть {x_i} обработке с помощью адаптивного (Адаптивный алгоритм — алгоритм, который пытается выдать лучшие результаты путём постоянной подстройки под входные данные). обучающегося алгоритма, на выходе которого воспроизводится грамматика G, согласованная с данными цепочками.

Иными словами, множество цепочек {x_i} является подмножеством языка L(G), порождаемого грамматикой G.

2. Суть метода:

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

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

3. Алгоритм + пример, чтобы понятнее было.

Сам алгоритм:

Алгоритм можно разделить на три части.

Первая часть формирует нерекурсивную грамматику.

Вторая часть преобразует её в рекурсивную грамматику.

Затем, в третьей части, происходит упрощение этой грамматики.

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

Часть 1.

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

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

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

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

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

,

где —правило остатка.

Вторая цепочка — . Для порождения этой цепочки к грамматике добавляются следующие правила:

Поскольку цепочка и предыдущая цепочка имеют одинаковую длину, требуется остаточное правило длины 2. Заметим также, что работа первой части алгоритма приводит к некоторой избыточности правил подстановки. Например, вторая цепочка может быть с равным успехом получена введением следующих правил подстановки:

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

Для порождения третьей цепочки требуется добавление к грамматике только одного правила: .

Для порождения четвертой цепочки требуется добавление к грамматике только одного правила: .

Для порождения пятой цепочки требуется добавление к грамматике только одного правила: .

Для порождения шестой цепочки требуется добавление к грамматике только одного правила: .

Для порождения седьмой цепочки требуется добавление к грамматике только одного правила: .

Для порождения восьмой цепочки требуется добавление к грамматике только одного правила: .

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