Теория шаблонов

В теории паттернов математический аппарат для представления и анализа структур опирается на «алгебру конфигураций». Базовыми элементами в ней выступают примитивные генераторы (образующие), которые моделируют относительно простые объекты. Ключевыми понятиями этой алгебры являются связность (каждый генератор обладает связями, которые могут соединяться со связями других объектов) и регулярность (из образующих путём соединения их связей конструируются регулярные конфигурации). Формальным критерием, по которому сочетание генераторов признаётся допустимым (регулярным), является соблюдение правил связей и совместимости при их объединении^[3].^[4] Важную роль в теории играют концепции инвариантности преобразований и группы подобия. Инвариантность преобразований — это свойство конфигураций и паттернов сохранять свою основу при воздействии преобразований подобия. Это позволяет формализовать постоянство формы и концепцию эквивалентности, объединяя объекты с одинаковой структурой в единый класс. Группа подобия (например, вращение, перенос, масштабирование) действует на пространстве генераторов: преобразование ${\displaystyle s}$ применяется к генератору ${\displaystyle g}$ как ${\displaystyle sg}$, и это действие распространяется на всю конфигурацию ${\displaystyle c}$ по правилу ${\displaystyle sc=s{\text{LINEAR}}(g_{1},\dots ,g_{n})={\text{LINEAR}}(sg_{1},\dots ,sg_{n})}$. Одинаковое воздействие группы на все генераторы конфигурации порождает её преобразование как единого целого, что позволяет создавать эквивалентные конфигурации и моделировать вариативность объектов^[3].

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

Пример 1: Грамматика

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

Следующие предложения были сгенерированы с помощью простых правил автомата и программного кода в теории шаблонов:

the boy who owned the small cottage went to the deep forest

the prince walked to the lake

the girl walked to the lake and the princess went to the lake

the pretty prince walked to the dark forest

Чтобы создать подобные предложения, правила перезаписываются в конечные автоматы, действующие в качестве "генераторов". Генератор начинает работу в состоянии 1, переходит в состояние 2 и записывает слово the. Из состояния 2 выбирается одно из четырёх слов: prince, boy, princess, girl. Такой упрощённый автомат иногда генерирует странные предложения, например:

the evil evil prince walked to the lake

the prince walked to the dark forest and the prince walked to a forest and the princess who lived in some big small big cottage who owned the small big small house went to a forest

Исходя из диаграммы конечных состояний, можно вывести следующие генераторы (см. справа), создающие сигнал. Генератор — это "4-кортеж": текущее состояние, следующее состояние, записываемое слово и вероятность выбора этого слова при наличии альтернатив.

Вообразим "конфигурацию" генераторов, последовательно связанных таким образом, что их вывод формирует предложение, а каждый генератор "ограничивает" (связан) только с предыдущим и следующим. Пусть границами этих связей будут 1a, 1b, 2a, 2b ..., 12a, 12b. Каждая числовая метка соответствует состоянию автомата, а буквы "a" и "b" — входной и выходной границе. Таблица ограничений (слева) эквивалентна диаграмме автомата. Для упрощения показана только половина таблицы — она симметрична.

Статистические методы и стохастическое моделирование играют ключевую роль в теории шаблонов. Для обработки шума и работы с вариациями в реальных наблюдениях математические модели должны быть частично стохастическими, что позволяет изучать внутреннюю структуру паттернов. В основе подхода лежит вероятностное моделирование: создаются модели, воспроизводящие структуру и изменчивость реальных сигналов, а для их анализа применяется байесовский статистический вывод^[5][6]. Теория также использует моделирование случайных перестановок, поскольку естественные сигналы могут изменяться путём реорганизации их области определения^[6]. Кроме того, важное значение имеет идентификация скрытых переменных, использование которых позволяет описывать структуру паттернов более ясно и чётко.