Теория паттернов - Pattern theory

Теория паттернов, сформулированный Ульф Гренандер, является математическим формализм описать познание мира как узоры. Он отличается от других подходов к искусственный интеллект в том, что он не начинается с предписания алгоритмы и оборудование для распознавания и классификации моделей; скорее, он предписывает словарь, чтобы сформулировать и преобразовать концепции шаблонов точным языком. Теория паттернов имеет широкий математический охват. алгебра и статистика, а также локальные топологические и глобальные энтропийные свойства.

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

Определить скрытые переменные из набор данных используя данные реального мира, а не искусственные стимулы, что раньше было обычным явлением.
Сформулируйте априорные распределения для скрытых переменных и модели для наблюдаемых переменных, которые образуют вершины Гиббс -подобный граф.
Изучите случайность и изменчивость этих графиков.
Создайте базовые классы стохастический применяемые модели путем перечисления деформаций шаблонов.
Синтезируйте (сэмплируйте) модели, а не просто анализируйте с их помощью сигналы.

В Брауновский университет Pattern Theory Group была основана в 1972 году Ульфом Гренандером.^[1] В настоящее время в этой группе работают многие математики, среди которых следует отметить Медалист Филдса Дэвид Мамфорд. Мамфорд считает Гренандера своим «гуру» в теории образов.^{[нужна цитата ]}

Пример: грамматика естественного языка

Грамматический автомат

Генераторы грамматики

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

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

мальчик, которому принадлежал небольшой коттедж, ушел в глухой лес

принц пошел к озеру

девушка подошла к озеру а принцесса пошла к озеру

красивый принц пошел в темный лес

Для создания таких предложений правила перезаписи в конечных автоматах действуют как генераторы создать предложения следующим образом: если машина запускается в состоянии 1, она переходит в состояние 2 и записывает слово «the». Из состояния 2 он записывает одно из 4 слов: принц, мальчик, принцесса, девочка, выбранные наугад. Вероятность выбора любого данного слова определяется Цепь Маркова соответствующий автомату. Такой упрощенный автомат иногда генерирует более неудобные предложения:

злой злой принц подошел к озеру

принц пошел в темный лес, а принц пошел в лес, а принцесса, которая жила в каком-то большом маленьком большом коттедже, владевшая маленьким большим маленьким домом, пошла в лес

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

Представьте, что конфигурация генераторов связана линейно, так что ее выходные данные образуют предложение, так что каждый генератор «привязывается» к генераторам до и после него. Обозначим эти связи как 1x, 1y, 2x, 2y, ... 12x, 12y. Каждая числовая метка соответствует состоянию автомата, а каждая буква «x» и «y» соответствует входящим и исходящим связям. Тогда следующая таблица связей (слева) эквивалентна диаграмме автомата. Для простоты показана только половина таблицы облигаций - на самом деле таблица симметричный.

	1x	1 год	2x	2 года	3x	3 года	4x	4 года	5x	5лет	6x	6лет	7x	7лет	8x	8лет	9x	9лет	10x	10лет	11x	11лет	12x	12лет
1x	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	1	—	—
1 год		—	1	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—
2x			—	1	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—
2 года				—	1	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—
3x					—	—	—	—	—	—	—	—	—	1	—	—	—	—	—	—	—	—	—	—
3 года						—	1	—	—	—	—	—	—	—	1	—	—	—	—	—	—	—	—	—
4x							—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—
4 года								—	1	—	1	—	—	—	—	—	—	—	—	—	—	—	—	—
5x									—	—	—	—	—	—	—	—	—	—	—	—	—	—	—	—
5лет										—	1	—	—	—	—	—	—	—	—	—	—	—	—	—
6x											—	—	—	—	—	—	—	—	—	—	—	—	—	—
6лет												—	1	—	—	—	—	—	—	—	—	—	—	—
7x													—	1	—	—	—	—	—	—	—	—	—	—
7лет														—	—	—	—	—	—	—	—	—	—	—
8x															—	—	—	—	—	—	—	—	—	—
8лет																—	1	—	—	—	—	—	—	—
9x																	—	—	—	—	—	—	—	—
9лет																		—	1	—	—	—	—	—
10x																			—	—	—	—	—	—
10лет																				—	1	—	—	—
11x																					—	1	—	—
11лет																						—	1	—
12x																							—	—
12лет																								—

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

Более сложный пример можно найти в грамматика ссылок теория естественный язык.

Алгебраические основы

Исходя из этого примера, мы имеем следующие определения:

А генератор ${displaystyle g {in} G}$ , нарисованный как
является примитивом теории паттернов, который генерирует наблюдаемый сигнал. Структурно это величина с интерфейсами, называемая связями. ${displaystyle b {in} B}$ , который соединяет ${displaystyle g}$ для формирования генератора сигналов. 2 соседних генератора подключены, если их значения связи совпадают. Собственные карты подобия ${displaystyle s {in} S}$ s: G -> G выражают инварианты мира, на который мы смотрим, такие как преобразования твердого тела или масштабирование.
Склеивает генераторы клея в конфигурация, c, что создает сигнал на фоне Σ, с глобальными функциями, описываемыми локально таблицей связи облигаций, называемой ${displaystyle ho}$ . В логический функция ${displaystyle ho}$ - главная компонента регулярного 4-набора , который определяется как
${displaystyle ho (c) = prod _ {{ext {соседние связи}} b ', b''in c} ho (b', b '').}$
${displaystyle ho}$ похоже, улавливает понятие допустимых соседей генератора. То есть, регулярность - это закон домена стимула, определяющий через таблицу связей, какие соседи являются приемлемыми для генератора. Это законы стимульной области. Позже мы ослабим регулярность логической функции до значения вероятности, она будет фиксировать, какие соседи стимула являются вероятными.Σ физическое расположение генераторов. В видении это может быть двухмерная решетка. На языке это линейное расположение.
An изображение (C mod R) фиксирует понятие наблюдаемой Конфигурации в отличие от той, которая существует независимо от любого аппарата восприятия. Образы - это конфигурации, различающиеся только своими внешними связями, наследующие трансформации композиции и подобия конфигурации. Формально изображения представляют собой классы эквивалентности, разделенные правилом идентификации «~» с 3 свойствами:
1. ext (c) = ext (c ') всякий раз, когда c ~ c'
2. sc ~ sc 'всякий раз, когда c ~ c'
3. sigma (c1, c2) ~ sigma (c1 ', c2') всякий раз, когда c1 ~ c1 ', c2 ~ c2' все регулярны.
Конфигурация, соответствующая физическому стимулу, может иметь множество изображений, соответствующих правилу идентификации восприятия многих наблюдателей.
А шаблон - это повторяющиеся компоненты изображения, определяемые как S-инвариантное подмножество изображения. Сходства - это эталонные преобразования, которые мы используем для определения шаблонов, например преобразования твердого тела. На первый взгляд, это определение подходит только для текстурных узоров, в которых минимальное фрагмент изображения повторяется снова и снова. Если бы мы увидели изображение объекта, такого как собака, он не повторяется, но кажется знакомым и должен быть образцом.
А деформация представляет собой преобразование исходного изображения, которое учитывает шум в окружающей среде и ошибку в аппарате восприятия. Гренандер выделяет 4 типа деформаций: шум и размытие, многомасштабное наложение, искривление домена и прерывания.
Пример 2 Направленная граница

Конфигурация

Изображение

Генераторы
Эта конфигурация генераторов, генерирующих изображение, создается примитивами, сплетенными вместе таблицей связывания, и воспринимается наблюдателем с правилом идентификации, которое сопоставляет генераторы, отличные от «0» и «1», в один граничный элемент. Девять других не показанных генераторов создаются путем поворота каждого из генераторов, отличных от «0» и «1», на 90 градусов. Имея в виду особенность «направленных границ», генераторы приготовлены с некоторой мыслью и интерпретируются следующим образом: генератор «0» соответствует внутренним элементам, «1» - внешнему, «2» и его вращения - прямые элементы. , а остальные - поворотные элементы.
С логической регулярностью, определенной как Продукт (все связи nbr), любые конфигурации даже с одним генератором, нарушающим таблицу связей, не рассматриваются. Таким образом, разрешены только функции в чистом виде, когда все соседние генераторы придерживаются таблицы связей. Это жесткое условие можно ослабить с помощью вероятностных мер вместо таблиц логических облигаций.
${displaystyle p (c) = prod _ {{ext {соседние связи}} b ', b''in c} A (b', b '')}$
Новая регулярность больше не диктует идеальную направленную границу, но определяет вероятность конфигурации в терминах функции акцептора A (). Такие конфигурации могут иметь примеси и недостатки по отношению к интересующему признаку.
С помощью генераторов и полных таблиц облигаций можно выполнить сложную часть анализа структуры. При рассмотрении нового класса сигналов и функций задача разработки генераторов и таблицы связей становится гораздо более сложной.
Опять же, как и в грамматиках, определение генераторов и таблиц связей требует некоторого размышления. Столь же тонкий факт, что конфигурация - это не сигнал, который мы наблюдаем. Скорее, мы наблюдаем его изображение как силуэтные проекции правила идентификации.

Таблица истинности логических связей
Связь Значения	0	1	2	3	4	5
0	1	—	—	—	1	—
1		1	—	—	—	1
2			—	1	—	—
3				—	—	—
4					—	—
5						—

Энтропия

Теория паттернов определяет порядок с точки зрения интересующей особенности, заданной п(c).

Энергия (c) = −log п(c)

Статистика

Теория паттернов Гренандера. Байесовский вывод in, похоже, смещен в сторону реконструкции изображения (например, память с адресацией по содержанию ). Это изображение I-деформированное, найти I. Однако Мамфорд интерпретирует теорию шаблонов шире, и он определяет PT как включающий многие другие хорошо известные статистические методы. Критерии Мамфорда для включения темы в качестве теории паттернов - это те методы, которые "характеризуются общими приемами и мотивациями", такими как ХМ, EM алгоритм, динамическое программирование круг идей. Темы в этом разделе будут отражать подход Мамфорда к теории образов. Его принципы статистической теории паттернов заключаются в следующем:

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

Статистическая PT повсеместно использует условную вероятность в форме Теорема Байеса и Марков Модели. Оба эти понятия используются для выражения связи между скрытыми состояниями (конфигурациями) и наблюдаемыми состояниями (изображениями). Марковские модели также фиксирует локальные свойства стимула, напоминая о назначении таблицы связей для регулярности.

Общая настройка следующая:

Позволять s = скрытое состояние данных, которые мы хотим знать. я = наблюдаемое изображение. Теорема Байеса дает:

п (s | я ) п(я) = п (s, я ) = п (я|s ) п(s)

Чтобы проанализировать сигнал (распознавание): зафиксируйте i, максимизируйте p, выведите s.

Чтобы синтезировать сигналы (выборка): исправить s, сгенерировать i, сравнить с изображениями реального мира

Следующие примеры условной вероятности иллюстрируют эти методы в действии:

Условная вероятность для местной собственности

N-граммовые текстовые строки: см. Теорию паттернов Мамфорда на примерах, глава 1.

MAP ~ MDL (MDL дает представление о том, почему вероятностная формулировка MAP имеет аналитический смысл)

Условная вероятность для скрытых наблюдаемых состояний

Теорема Байеса для машинного перевода

Предположим, мы хотим перевести Французский предложения к английский. Здесь скрытые конфигурации - это предложения на английском языке, а наблюдаемый сигнал, который они генерируют, - предложения на французском языке. Теорема Байеса дает п(е|ж)п(ж) = п(е, ж) = п(ж|е)п(е) и сводится к основному уравнению машинного перевода: максимизировать п(е|ж) = п(ж|е)п(е) над соответствующими е (Обратите внимание, что п(ж) не зависит от е, и поэтому выпадает, когда мы максимизируем более е). Это сводит проблему к трем основным расчетам:

п(е) для любого данного е, с использованием N-граммовый метод и динамическое программирование
п(ж|е) для любого данного е и ж, используя выравнивания и алгоритм максимизации ожидания (EM)
е который максимизирует произведение 1 и 2, опять же, используя динамическое программирование

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

Теперь мы сосредоточимся на п(ж|е) в разложении на три части выше. Две другие части, п(е) и максимизации е, использует те же методы, что и N-грамма модель. Учитывая французско-английский перевод большого набора обучающих данных (такие наборы данных существуют из Канадский парламент ):

       NULL И программа была реализована Le program a ete mis en application

пара предложений может быть закодирована как выравнивание (2, 3, 4, 5, 6, 6, 6), который читается следующим образом: первое слово во французском языке происходит от второго английского слова, второе слово во французском языке происходит от третьего английского слова и т. Д. Хотя выравнивание - это прямое кодирование перевода, более удобный в вычислительном отношении подход к выравниванию - разбить его на четыре параметра:

Плодородие: количество слов во французской строке, которые будут связаны с ней. Например. п(3 | реализовано) = вероятность того, что «реализовано» переводится тремя словами - рождаемость.
Ложность: мы вводим артефакт NULL как слово, чтобы представить вероятность подбрасывания ложного французского слова. Например. $п 1$ и его дополнение будет $п 0 = 1 - п 1$ .
Перевод: переведенная версия каждого слова. Например. т(а | has) = вероятность перевода английского слова has на французский язык a.
Искажение: фактические позиции во французской строке, которые будут занимать эти слова. Например. d(5 | 2, 4, 6) = искажение французского слова второй позиции, перемещающееся на пятую позицию английского слова для предложения из четырех слов и французского предложения из шести слов. Мы кодируем выравнивания таким образом, чтобы легко представлять и извлекать априорные значения из наших обучающих данных, и новая формула становится

{displaystyle {egin {align} p (f | e) & = {ext {Сумма всех возможных выравниваний an of}} p (a, f | e) & = n_ {0} (v_ {0} | sum _ {j = 1} ^ {l} {v_ {j}}) cdot prod _ {j = 1} ^ {l} n (v_ {j} | e_ {j}) v_ {j}! cdot prod _ {j = 1} ^ {m} t (f_ {j} | e_ {a_ {j}}) cdot prod _ {j: a_ {j} ot = 0} ^ {m} d (j | a_ {j}, l , m) конец {выровнен}}}

Для простоты демонстрации алгоритма EM мы проведем простое вычисление, включающее только вероятности перевода т(), но излишне говорить, что этот метод применяется ко всем параметрам во всей красе. Рассмотрим упрощенный случай (1) без слова NULL (2), где каждое слово имеет фертильность 1 и (3) вероятность искажения отсутствует. Наш корпус обучающих данных будет содержать пары из двух предложений: до н.э → ху и б → у. Перевод английского предложения из двух слов «b c» на французское предложение «х у»Имеет два возможных выравнивания, включая слова из одного предложения, выравнивания:

                         б в б в б | | х | х у х у у

называется Parallel, Crossed и Singleton соответственно.

Чтобы проиллюстрировать алгоритм EM, сначала установите желаемый параметр единообразно, то есть

т(Икс | б ) = т(у | б ) = т(Икс | c ) = т(у | c ) = ¹⁄₂

Затем EM выполняет итерацию следующим образом

Итерации алгоритма EM

Вероятность совмещения для «пересекающего совмещения» (где б подключается к у) получил импульс от второй пары предложений б/у. Это еще больше укрепило т(у | б), но как побочный эффект также усиливается т(Икс | c), потому что Икс подключается к c в том же «перекрестном выравнивании». Эффект повышения т(Икс | c) обязательно означает понижение версии т(у | c), потому что они в сумме равны одному. Итак, хотя у и c совпадают, анализ показывает, что они не являются переводами друг друга. С реальными данными EM также подвержена обычным ловушкам локальных экстремумов.

HMM для распознавания речи

Вибрационный пробой «лыжи»

В течение многих десятилетий, распознавание речи казалось, что она зашла в тупик, поскольку ученые искали описательное и аналитическое решение. В звуковая волна p (t) ниже получается произнесением слова «лыжи».

Его четыре отдельных сегмента имеют очень разные характеристики. Можно выбрать один из множества уровней генераторов (скрытых переменных): намерение говорящего мозг, состояние рот и голосовые связки, или сами «телефоны». Телефоны являются генератором выбора, и он кодирует слово шумным, очень разнообразным способом. Ранние работы по распознаванию речи пытались сделать этот вывод детерминированно, используя логические правила, основанные на двоичных характеристиках, извлеченных из p (t). Например, в таблице ниже показаны некоторые функции, используемые для различения Английские согласные.

В реальных ситуациях сигнал дополнительно усложняется фоновыми шумами, такими как легковые автомобили проезжая мимо или артефакты, такие как кашель в середине предложения (2-е подкрепление Мамфорда). Детерминированный подход, основанный на правилах, потерпел неудачу, и современное состояние (например, Дракон Естественно ) заключается в использовании семейства точно настроенных HMM и байесовских оценок MAP, чтобы добиться большего. Подобные истории разыгрываются в видении и других категориях стимулов.

Детерминированный подход к распознаванию речи
	п	т	k	б	d	грамм	м	п	ж	s	v	z
Continuant	—	—	—	—	—	—	—	—	$+$	$+$	$+$	$+$
Озвучен	—	—	—	$+$	$+$	$+$	$+$	$+$	—	—	$+$	$+$
Носовой	—	—	—	—	—	—	$+$	$+$	—	—	—	—
Губной	$+$	—	—	$+$	—	—	$+$	—	$+$	—	$+$	—
Корональный	—	$+$	—	—	$+$	—	—	$+$	—	$+$	—	$+$
Передний	$+$	$+$	—	$+$	$+$	—	$+$	$+$	$+$	$+$	$+$	$+$
Резкий	—	—	—	—	—	—	—	—	$+$	$+$	$+$	$+$

(См. Теорию паттернов Мамфорда: математика восприятия)

Марковский стохастический процесс схематически представлен следующим образом:

{displaystyle dots, x_ {k}, x_ {k + 1}, dots Pr (x, s) = prod _ {k} p_ {1} (x_ {k} | x_ {k-1}) p_ {2} (s_ {k} | x_ {k})}

экспоненты, алгоритм EM

Смотрите также

дальнейшее чтение

2007. Ульф Гренандер и Майкл Миллер Теория паттернов: от представления к выводу. Издательство Оксфордского университета. Мягкая обложка. (ISBN 9780199297061)
1994. Ульф Гренандер Общая теория паттернов. Оксфордские научные публикации. (ISBN 978-0198536710)
1996. Ульф Гренандер Элементы теории паттернов. Издательство Университета Джона Хопкинса. (ISBN 978-0801851889)

внешняя ссылка

Группа Теории Паттернов в Университете Брауна
Теория паттернов: идеи и примеры Гренандера - видеолекция Дэвида Мамфорда
Теория паттернов и приложения - страница аспирантуры с материалами выпускника Университета Брауна

[1] "Домашняя страница Ульфа Гренандера". 22 января 2009 г. Архивировано с оригинал на 22 января 2009 г.

[1]