Теория шаблонов
Теория шаблонов (порт. Teoria dos Padrões), сформулированная Ульфом Гренандером (англ. Ulf Grenander), представляет собой математический формализм для описания знаний о мире как о совокупности шаблонов. В отличие от других подходов к искусственному интеллекту, теория шаблонов не начинает изложение с предписания алгоритмов и методов для распознавания и классификации шаблонов, а формирует словарь для точной формулировки и переформулирования понятий шаблона на строгом языке.
Помимо нового алгебраического словаря, статистический подход теории проявляется в следующих целях:
- Идентифицировать скрытые переменные (англ. hidden variables) в наборе данных, используя реальные данные, а не искусственные стимулы, что было распространено на момент возникновения теории.
- Задавать априорные распределения для скрытых переменных и модели для наблюдаемых переменных, которые образуют вершины графа, аналогичного графам типа Гиббса (англ. Gibbs).
- Исследовать случайность и изменчивость в таких графах.
- Создавать основные классы стохастических моделей путём перечисления возможных деформаций шаблонов.
- Синтезировать (генерировать) полные сигналы посредством моделей, а не лишь частично анализировать их.
Теория шаблонов охватывает широкий спектр математических областей — алгебру, статистику, а также локальные и глобальные свойства, как в малых, так и в больших масштабах.
Группа по теории шаблонов при Брауновском университете (США) была создана в 1972 году самим Ульфом Гренандером. В работе группы принимают участие многие ведущие прикладные математики, в том числе лауреат медали Филдса Дэвид Мамфорд, который значительно расширил область теории шаблонов.
Алгебраические основы
Следующий пример иллюстрирует алгебраические определения, приведённые ниже.
- Пример 1: Грамматика
| 1x | 1y | 2x | 2y | 3x | 3y | 4x | 4y | 5x | 5y | 6x | 6y | 7x | 7y | 8x | 8y | 9x | 9y | 10x | 10y | 11x | 11y | 12x | 12y | |
| 1x | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | 1 | - | - |
| 1y | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | |
| 2x | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||
| 2y | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | |||
| 3x | - | - | - | - | - | - | - | - | - | 1 | - | - | - | - | - | - | - | - | - | - | ||||
| 3y | - | 1 | - | - | - | - | - | - | - | 1 | - | - | - | - | - | - | - | - | - | |||||
| 4x | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||||||
| 4y | - | 1 | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | |||||||
| 5x | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||||||||
| 5y | - | 1 | - | - | - | - | - | - | - | - | - | - | - | - | - | |||||||||
| 6x | - | - | - | - | - | - | - | - | - | - | - | - | - | - | ||||||||||
| 6y | - | 1 | - | - | - | - | - | - | - | - | - | - | - | |||||||||||
| 7x | - | 1 | - | - | - | - | - | - | - | - | - | - | ||||||||||||
| 7y | - | - | - | - | - | - | - | - | - | - | - | |||||||||||||
| 8x | - | - | - | - | - | - | - | - | - | - | ||||||||||||||
| 8y | - | 1 | - | - | - | - | - | - | - | |||||||||||||||
| 9x | - | - | - | - | - | - | - | - | ||||||||||||||||
| 9y | - | 1 | - | - | - | - | - | |||||||||||||||||
| 10x | - | - | - | - | - | - | ||||||||||||||||||
| 10y | - | 1 | - | - | - | |||||||||||||||||||
| 11x | - | 1 | - | - | ||||||||||||||||||||
| 11y | - | 1 | - | |||||||||||||||||||||
| 12x | - | - | ||||||||||||||||||||||
| 12y | - |
Если мы хотим представить языковые шаблоны, наиболее очевидными кандидатами на роль примитивов могут быть слова. Однако некоторые фразы показывают, что слово само по себе может не быть подходящей атомарной единицей. В поисках других примитивов в качестве кандидата можно рассматривать правила грамматики. Грамматики могут быть представлены с помощью конечных автоматов или контекстно-свободных грамматик. Ниже приведён пример грамматики, реализованной конечным автоматом.
- Следующие предложения были сгенерированы с помощью простых правил автомата и программного кода в теории шаблонов:
- 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" — входной и выходной границе. Таблица ограничений (слева) эквивалентна диаграмме автомата. Для упрощения показана только половина таблицы — она симметрична.