Часть IV
Динамические модели
409 ГЛАВА
23 Марковские модели с дискретным состоянием
23.1 Марковские модели
Временные ряды - это наборы данных, для которых составляющие их точки данных могут быть упорядочены естественным образом. Этот порядок часто соответствует основному физическому измерению, обычно времени, хотя может использоваться любое другое измерение. Рассматриваемые нами модели временных рядов представляют собой вероятностные модели для набора случайных величин v1 , . . . , vT с отдельными переменными vt, индексированными временным индексом t. Эти индексы являются элементами набора индексов T . Для неотрицательных индексов, T = N+ , модель представляет собой процесс с дискретным временем. Процессы с непрерывным временем, T = R, являются естественными в определенных областях применения, но требуют дополнительных обозначений и концепций. Поэтому мы фокусируемся исключительно на моделях с дискретным временем. Вероятностная модель временных рядов требует определения совместного распределения p(v1 , . . . , vT ). В случае, когда наблюдаемые данные vt дискретны, общая таблица вероятностей для p(v1 , . . . , vT ) содержит экспоненциально большое количество записей. Мы не можем ожидать, что независимо друг от друга определяют все экспоненциально увеличивающиеся элементы и, следовательно, вынуждены создавать упрощенные модели, в которых эти элементы могут быть параметризованы способом с меньшей размерностью. Такие упрощения лежат в основе моделирования временных рядов, и мы обсудим некоторые классические модели в следующих разделах.
Определение 107 (запись временных рядов).
Для данных временных рядов v1 , . . . , vT нам нужна модель p(v1:T ). Для соответствия причинно-следственной природе времени имеет смысл рассмотреть разложение
с условным обозначением p(vt |v1:t;1 ) = p(v1 ) для t = 1. Часто естественно предполагать, что влияние ближайшего прошлого более значимо, чем отдаленного, и в марковских моделях для прогнозирования будущего требуется лишь ограниченное число предыдущих наблюдений.
Определение 108 (цепь Маркова). Марковская цепочка, определенная на основе дискретных или непрерывных переменных v1:T, - это цепочка, в которой выполняется следующее предположение об условной независимости:
411Маркова модели
Рисунок 23.1: (а): Цепь Маркова первого порядка. (b): Цепь Маркова второго порядка.
где L ; 1 - порядок цепи Маркова, а vt =; при t < 1. Для цепи Маркова первого порядка
Для стационарной цепи Маркова переходы p(vt = s` |vt;1 = s) = f (s`, s) не зависят от времени. В противном случае цепь нестационарна, p(vt = s` |vt;1 = s) = f (s` , s, t).
23.1.1 Равновесное и стационарное распределение Марковской цепи
Стационарное распределение p; марковской цепи с матрицей переходов M определяется условием
В матричной записи это можно записать как векторное уравнение
, так что стационарное распределение пропорционально собственному вектору с единичным
собственным значением матрицы перехода. Обратите внимание, что может существовать более одного стационарного распределения. Смотрите упражнение (217) и [122].
Учитывая состояние x1, мы можем итеративно извлекать выборки x2 , ... , xt из цепи Маркова, извлекая выборку из p (x2 | x1 = x1 ), а затем из p (x3 | x2 ) и т.д. Поскольку мы многократно отбираем новое состояние из цепочки, то распределение в момент времени t для начального распределения p1 (i) = ; (i, x1) равно
Если при t ; ; значение p; не зависит от исходного распределения p1 , то значение p; называется равновесным распределением цепи. Пример цепи Маркова, которая не имеет равновесного распределения, приведен в упражнении (218).
Пример 95 (PageRank\ Ранг Страницы). Несмотря на кажущуюся простоту, цепочки Маркова нашли интересное применение в поиске информации и поисковых системах. Определите матрицу
1, если веб-сайт j содержит гиперссылку на веб-сайт i
0 в противном случае
Исходя из этого, мы можем определить марковскую матрицу переходов с элементами
Равновесное распределение этой цепи Маркова имеет следующую интерпретацию: если переходить по ссылкам случайным образом, переходя с веб-сайта на веб-сайт, компонент равновесного распределения p; (i) равен относительному числу посещений веб-сайта i. Это имеет естественную интерпретацию как "важность" веб-сайта i; если веб-сайт
412 ПРОЕКТ от 9 марта 2010 г. Mодели Маркова
изолирован в сети, его будут посещать нечасто в результате случайного перехода; если на веб-сайт ссылается много других пользователей, его будут посещать чаще.
Простая поисковая система работает следующим образом. Для каждого веб-сайта i собирается список слов, связанных с этим веб -сайтом. Выполнив это для всех веб-сайтов, можно составить "обратный" список веб-сайтов, содержащих слово w. Когда пользователь выполняет поиск по слову w, возвращается список веб-сайтов, на которых это слово отображается, ранжированный в соответствии с важностью сайта (как определено равновесным распределением). Это краткое изложение того, как работали ранние поисковые системы, infolab.stanford.edu/;backrub/google.html.
Рисунок 23.2: Диаграмма перехода между состояниями для модели Маркова с тремя состояниями цепь. Обратите внимание, что диаграмма переходов состояний не является графической моделью – она просто отображает ненулевые значения матрицы переходов p(i|j). Отсутствие связи между j и i указывает на то, что p(i|j) = 0.
23.1.2. Подгонка марковских моделей
При заданной последовательности v1:T подгонка стационарной цепи Маркова по принципу Максимального Правдоподобия соответствует настройке переходов путем подсчета количества наблюдаемых переходов (первого порядка) в последовательности:
Чтобы показать это, для удобства запишем p(v;= i|v; -1 = j) ; ;i|j , так что вероятность равна (при условии, что v1 равна известно):
Берем логарифмы и добавляем ограничение Лагранжа для нормализации,
Дифференцируя относительно ;i|j и приравнивая к нулю уравнение (23.1.10), мы сразу же приходим к интуитивной настройке. Для набора временных рядов, v1:Tтn , n = 1, . . . , N , переход задается путем подсчета всех переходов по времени и точкам данных. Параметр Максимального Правдоподобия для начального первого временного шага распределения равен p(v1 = i) ; ;n I [v1n = i].
Байесовская аппроксимация
Для простоты мы предполагаем факторизованный априор при переходе
Удобным выбором для каждого условного перехода является распределение Дирихле с гиперпараметрами uj , p(;·|j ) = Dirichlet (;·|j |uj )\Дирихле \, поскольку это сопряжено с категориальным переходом и
где ;j =;Tt=2 I [vt;1 = i, vt = j], что является числом переходов j ; i в наборе данных.
ПРОЕКТ от 9 марта 2010 413 Марковa модели
Рисунок 23.3: Смесь цепей Маркова первого порядка. Дискретная скрытая переменная dom(h) = {1, ... , H} индексирует Марковскую цепь p(vt |vt;1 , h). Такие модели могут быть полезны в качестве простых инструментов кластеризации последовательностей.
версия
23.1.3 Смесь Марковских моделей
Задан набор последовательностей V = {v1:Tn , n = 1, . . . , N }, как мы могли бы сгруппировать их? Чтобы уменьшить количество обозначений в связи с этим мы предполагаем, что все последовательности имеют одинаковую длину T, а расширение до разных длин является простым. Один из простых подходов заключается в использовании нескольких Марковских моделей. Предполагая, что данные i.i.d., p(V) = ;n p(v1:Tn ), мы определяем комбинированную модель для одной точки данных v 1:T . Здесь мы предполагаем, что каждая компонентная модель является Марковской первого порядка
Графическая модель представлена на рис.23.3. Кластеризация может быть выполнена путем нахождения Максимального значения Параметров Правдоподобия p(h), p(vt |vt;1, h) и последующее назначение кластеров в соответствии с p(h|v1:Tn). Ниже мы обсудим применение алгоритма EM к этой модели для определения параметров Максимального Правдоподобия.
Алгоритм EM
В соответствии с предположением о данных i.i.d. логарифмическая вероятность равна
На M-шаге нашей задачей является максимализировать энергию
Вклад параметра p(h) в энергию равен
Определив
старый
можно рассматривать максимизацию (23.1.17) как эквивалент минимизации
таким образом, оптимальным выбором на M-шаге является установка pnew =^ pold , а именно
новый
Для тех, кого этот аргумент не устраивает, для получения того же результата можно использовать прямую максимизацию, включающую член Лагранжа, обеспечивающий нормализацию p (h).
414 ЧЕРНОВИК от 9 марта 2010 Маркова модели
Аналогично, M-шаг для p(vt |vt;1 , h) равен
Начальный член p(v1 |h) обновляется с помощью
На E-шаге устанавливается
старое значение
После инициализации алгоритм EM выполняет итерации (23.1.20),(23.1.21), (23.1.22) и (23.1.23) до тех пор, пока не будет достигнута сходимость.
Для длинных последовательностей явное вычисление произведения многих слагаемых может привести к неполному вычислению вывода. Поэтому на практике лучше всего работать с логарифмами,
Таким образом, любые большие константы, общие для всех h, могут быть удалены, и распределение может быть точно вычислено. Смотрите mixMarkov.m.
Пример 96 (Кластеризация генов). Рассмотрим 20 вымышленных последовательностей генов, представленных ниже в произвольно выбранном порядке. Каждая последовательность состоит из 20 символов из набора {A, C, G, T}. Задача состоит в том, чтобы попытаться объединить эти последовательности в две группы, основываясь на (возможно, биологически нереалистичном) предположении, что ген последовательности в одном и том же кластере следуют стационарной Марковской цепочке.
Простой подход состоит в предположении, что последовательности генерируются из двухкомпонентной смеси H = 2 Марковских моделей и обучают модель с использованием Максимального Правдоподобия. Вероятность имеет локальные оптимумы, так что процедуру необходимо выполнить несколько раз и выбрать решение с наибольшей вероятностью\ правдоподобием. Которое можно, тогда присвоить каждой из последовательностей, исследуя p(h = 1|v1:Tn ). Если эта апостериорная вероятность больше 0.5, мы присвоим класс 1, в противном случае - класс 2. Используя эту процедуру, мы находим следующие кластеры:
где последовательности в первом столбце относятся к кластеру 1, а последовательности во втором столбце - к кластеру 2. В этом случае данные в (23.1.25) на самом деле были получены с помощью двухкомпонентной марковской смеси, и апостериорное назначение (23.1.26) согласуется с известными кластерами. Смотрите демонстрацию demoMixMarkov.m
ЧЕРНОВИК от 9 марта 2010 года 415 Скрытые марковские модели
Рисунок 23.4: Скрытая марковская модель первого порядка со "скрытыми’ переменными dom(ht ) = {1, ... , H}, t = 1 : T . "Видимые" переменные vt могут быть как дискретными, так и непрерывными.
23.2 Скрытые Марковские Модели
Скрытая Марковская модель (HMM) определяет марковскую цепочку для скрытых (или "латентных") переменных h1:T . Наблюдаемые (или ‘видимые’) переменные зависят от скрытых переменных через коэффициент излучения p(vt |ht ). Это определяет совместное распределение
для которого графическая модель представлена на рис.23.4. Для стационарного HMM распределения переходов \ транзакции\ p(ht|ht;1) и выбросов \эмиссии\ p(vt|ht) постоянны во времени. Использование HMM широко распространено, и в разделе (23.5) приведен перечень многих применений HMM.
Определение 109 (Переходное распределение). Для стационарного HMM распределение переходов p(ht+1 |ht) определяется матрицей переходов H ; H
и начальное распределение
Определение 110 (Распределение выбросов). Для стационарного HMM и распределения выбросов p(vt |ht ) с дискретными состояниями vt ; {1, . . . , V } мы определяем матрицу выбросов V ; H
Для непрерывных выходных данных ht выбирает одно из H возможных распределений выходных данных p(vt |ht ), ht ; {1, . . . , H}.
В инженерном сообществе и сообществе машинного обучения термин HMM обычно относится к случаю дискретных переменных ht, и мы придерживаемся этого правила. В статистике термин HMM часто относится к любой модели со структурой независимости в уравнении (23.2.1), независимо от формы переменных ht (см., например [54]).
23.2.1 Классические проблемы логического вывода
Фильтрация
Предсказание
Сглаживание
Вероятность \правдоподобность
Наиболее вероятный скрытый путь
(Вывод о настоящем)
(Вывод о будущем)
(Вывод о прошлом)
(Выравнивание Витерби)
Наиболее вероятная проблема со скрытым контуром в инженерной литературе называется выравниванием по Витерби. Все эти классические задачи логического вывода просты, поскольку распределение является односвязным, так что для этих задач можно использовать любой стандартный метод логического вывода. Факторный граф и деревья соединений для
416 ЧЕРНОВИК от 9 марта 2010 г. Скрытые марковские модели
Рисунок 23.5: (а): Факторный граф для HMM первого порядка на рис. 23.4. (b): Дерево соединений на рис. 23.4.
HMM первого порядка приведены на рис. 23.5. В обоих случаях, после соответствующей настройки факторов и потенциалов клика, фильтрация соответствует передаче сообщений слева направо и вверх; сглаживание соответствует действующему расписанию передачи/поглощения сообщений как в прямом, так и в обратном направлении по всем ребрам. Также несложно напрямую получить соответствующие рекурсии. Это поучительно, а также полезно при построении компактных и численно стабильных алгоритмов.
23.2.2 Фильтрация p(ht |v1:t )
Сначала мы вычисляем общее предельное значение p(ht , v1:t ), из которого затем путем нормализации может быть получено условное предельное значение p(ht |v1:t ). Рекурсия для p(ht , v1:t ) получается путем рассмотрения:
Исключения следуют из допущений модели об условной независимости. Следовательно, если мы определим
уравнение (23.2.7), приведенное выше, дает ;-рекурсию
корректор
предсказатель
при
Эта рекурсия интерпретируется так, что отфильтрованное распределение ;(ht;1 ) перемещается динамикой вперед на один временной шаг, чтобы выявить новое "предшествующее" распределение в момент времени t. Затем это распределение модулируется с помощью наблюдения vt, включающего новые данные в отфильтрованное распределение (это также называется методом предсказания-коррекции). Поскольку каждое значение ; меньше 1, а рекурсия включает умножение на значения, меньшие 1, значения ; могут стать очень маленькими. Поэтому, чтобы избежать числовых проблем, рекомендуется работать с логарифмом log;(ht ), см. HMMforward.m.
Нормализация дает отфильтрованное апостериорное значение
Если нам нужны только отфильтрованные апостериорные данные, мы можем изменять масштаб ; по своему усмотрению. В этом случае альтернативой работе с (логическими?) log;-сообщениями является работа с нормализованными ;-сообщениями, чтобы сумма компонентов всегда была равна 1.
ЧЕРНОВИК от 9 марта 2010 г. 417 Скрытые марковские модели
Мы можем записать уравнение (23.2.7), приведенное выше, непосредственно как рекурсию для отфильтрованного распределения
Интуитивно понятно, что термин p(ht;1 |v1:t;1 ) приводит к удалению всех узлов на графе до времени t; 1 и замене их влияния измененным "предшествующим" распределением на ht . Можно интерпретировать p(vt |ht )p(ht |ht;1 ) как вероятность, что приводит к заднему\ последующему\ значению p(ht , ht;1 |v1:t ) в соответствии с байесовской корректировкой. На следующем временном шаге предыдущее заданное значение становится новым предшествующим.
23.2.3 Параллельное сглаживание p(ht |v1:T )
Существует два основных подхода к вычислению p(ht |v1:T). Возможно, наиболее распространенным в литературе по HMM является параллельный метод, который эквивалентен передаче сообщений на факторных графах. В этом случае сглаженная апостериорная информация разделяется на вклады из прошлого и будущего:
прошлое
будущее
Термин ;(ht ) получается из "прямой" ;-рекурсии (23.2.9). Термин ;(ht ) может быть получен используя "обратную" ;-рекурсию, как показано ниже. Прямая и обратная рекурсии независимы и, следовательно, могут выполняться параллельно, а их результаты объединяются для получения сглаженного апостериорного результата. Этот подход также иногда называют сглаживанием с двумя фильтрами.
;-рекурсия
Определяя
приведенное выше уравнение (23.2.16) дает ;-рекурсию
с ;(hT ) = 1. Что касается прямого прохода, рекомендуется работать в логарифмическом пространстве, чтобы избежать числовых трудностей. Если требуется только апостериорное распределение, можно также выполнить локальную нормализацию на каждом этапе, поскольку важна только относительная величина компонентов ;. Сглаженная апостериорная
величина тогда задается как
Вместе взятые ; ; ; рекурсии называются алгоритмом Прямого-Обратного хода.
23.2.4 Корректирующее сглаживание
Альтернативой параллельному методу является создание рекурсии непосредственно для сглаженной апостериорной части. Этого можно достичь, осознав, что привязка к настоящему делает будущее излишним:
418 ЧЕРНОВИК от 9 марта 2010 г. Скрытые марковские модели
Это дает рекурсию для ;(ht ) ; p(ht |v1:T ):
с помощью ;(hT ) ; ;(hT ). Слагаемое p(ht |ht+1 , v1:t ) может быть вычислено с использованием отфильтрованных результатов p(ht |v1:t ):
где константа пропорциональности определяется путем нормализации. Это форма изменения динамики, как если бы мы меняли направление стрелки от скрытого к скрытому в HMM. Эта процедура, также называемая сглаживанием Рауха-Тунга-Штрибеля 1, является последовательной, поскольку нам нужно сначала выполнить ;-рекурсии, после с которого может начаться ;-рекурсия. Это так называемая сглаживающая коррекция, поскольку она "корректирует" отфильтрованный результат. Интересно, что после выполнения фильтрации подтверждающие состояния v1:T не нужны во время последующей ;-рекурсии.
Рекурсии ; ; ; и ; ; ; связаны через
Вычисление попарного предельного значения p(ht , ht;1 |v1:T )
Чтобы реализовать алгоритм EM для обучения, раздел (23.3.1), нам требуются такие термины, как p(ht , ht;1 |v1:T ). Они могут быть получены путем передачи сообщений либо по факторному графу, либо по дереву соединений (для которого попарно маргиналы содержатся в кликах, см. рис.23.4, б). В качестве альтернативы, явная рекурсия выполняется следующим образом:
Перестраиваясь, мы, следовательно, имеем
Смотрите HMMsmooth.m.
Вероятность \ правдоподобность\ p(v1:T )
Вероятность последовательности наблюдений может быть вычислена по формуле
Альтернативное вычисление можно найти, используя разложение
Каждый коэффициент может быть вычислен с помощью
1Чаще всего эту терминологию используют для случая непрерывной переменной, хотя мы используем ее здесь и для случая дискретной переменной.
ЧЕРНОВИК от 9 марта 2010 г.
419 Скрытых марковских моделей
(а) ‘Скрипы’
(б) ‘Удары’
Рисунок 23.6: Локализация взломщика. Скрытая переменная ht ; {1, . . . , 25} обозначает позиции, определенные на сетке 5 ; 5 первого этажа дома. (a): Представление вероятности того, что "пол будет скрипеть" в каждом из 25 положений, p(v creak\ скрипа |h). Светлые квадраты представляют вероятность 0,9, а темные - 0,1. (b): Представление вероятности p(v bump\ ударов |h) того, что грабитель наткнется на что-нибудь в каждой из 25 позиций.
где конечный член p(ht;1 |v1:t;1 ) - это отфильтрованный результат.
В обоих подходах для определения вероятности выходной последовательности требуется только прямое вычисление (фильтрация). При необходимости можно также вычислить вероятность, используя (23.2.13),
, который действителен для любого значения 1 ; t ; T .
23.2.5 Наиболее вероятное совместное состояние
Наиболее вероятный путь h1:T из p(h1:T |v1:T) совпадает с наиболее вероятным состоянием (для фиксированного v1:T) из
Наиболее вероятный путь можно найти, используя версию факторного графа с максимальным продуктом или с максимальным поглощением на дереве соединений. В качестве альтернативы, можно получить явный вывод, рассмотрев:
Сообщение µ(hT -1 ) передает информацию от конца цепочки до предпоследнего временного шага. Мы можем продолжить в том же духе, определив рекурсию
при µ(hT ) = 1. Это означает, что эффект максимизации в течение h2 , . . . , hT сжимается в сообщение µ(h1 ) , так что наиболее вероятное состояние h;1 задается формулой
После вычисления, обратный поиск дает
Этот частный случай алгоритма максимального произведения называется алгоритмом Витерби. Аналогично, можно использовать алгоритм N -max-product \максимального произведения, раздел (5.2.1), для получения N -наиболее вероятных скрытых путей.
Пример 97 (Пример локализации). Вы спите наверху в своем доме и просыпаетесь от шума, доносящегося снизу. Вы понимаете, что грабитель находится на первом этаже, и пытаетесь понять, где он прячется. прислушиваясь к его движениям. Вы мысленно делите первый этаж на сетку 5 ; 5. Для каждого положения сетки вы знаете вероятность того, что, если кто-то займет это положение, половица скрипнет, рис.23.6а).
420 ЧЕРНОВИК от 9 марта 2010 г. Скрытые марковские модели
(а) Скрипы и неровности
(б) Фильтрация
(в) Сглаживание
(г) Витерби
(д) Истинное положение взломщика
Рисунок 23.7: Определение местоположения взломщика во времени за 10 временных шагов. (а): Каждая панель представляет собой видимой информации vt = (vt creak, vtbump) \ скрип , удар\, где vt = 1 означает, что раздался ‘скрип половицы’ (в противном случае vtcreak = 2) и vtbump = 1 означают "врезался во что-то" (и в противном случае находится в состоянии 2). Имеется 10 панелей, по одной на каждый момент времени t = 1, . . . , 10. Левая половина панели обозначает vt1, а правая - vt2. Более светлый цвет обозначает наличие скрипа или неровности, более темный — отсутствие. (b): Отфильтрованное распределение p (ht |v1:t), представляющее, где, по нашему мнению, находится взломщик. (c): Сглаженное распределение p (ht |v1:10), позволяющее нам определить, куда, по нашему мнению, направился взломщик. (d): Наиболее вероятный (Viterbi) путь взломщика arg maxh1:10 p(h1:10 |v1:10 ). (e): Фактический путь взломщика.
Аналогично, вы знаете для каждого положения вероятность того, что кто-то наткнется на что-то в темноте, рис.23.6, б. Скрип половицы и столкновение с предметами могут происходить независимо друг от друга. Кроме того, вы предполагаете, что взломщик будет перемещаться только на один квадрат сетки – вперед, назад, влево или вправо за один временной интервал. Основываясь на серии сигналов "удар/отсутствие удара" и "скрип/отсутствие скрипа", рис.23.7а, вы пытаетесь определить, основываясь на своих знаниях о первом этаже, где может находиться взломщик.
Мы можем представить сценарий, используя HMM, где h ; {1, . . . , 25} обозначает квадрат сетки. Переменная visible имеет разложенную на множители форму v = vcreak \скрип ; vbump \удар, и, используя наш стандартный код, мы формируем новую переменную visible с 4 состояниями, используя
Основываясь на предыдущей информации, мы можем предположить, где может находиться взломщик, в виде отфильтрованного распределения p(ht |v1:t), рис.23.7. После того, как грабитель ушел в момент T = 10, прибывает полиция и пытается установить в зависимости от последовательности скрипов и ударов, которые вы предоставили. В любой момент времени t информация о том, где мог находиться взломщик, представлена сглаженным распределением p(ht |v1:10 ). Единственное наилучшее предположение полиции о последовательности действий грабителей основывается на наиболее вероятном совместном аргументе скрытого состояния maxh1:10 p(h1:10 |v1:10 ).
23.2.6 Самоблокировка и похищенные роботы
У робота есть внутренняя сетчатая карта его окружения, и для каждого местоположения h ; {1, . . . , H} он знает вероятные показания датчиков, которые он ожидает увидеть в этом месте. Робота ‘похищают’ и помещают где-то в окружающей среде. Затем робот начинает двигаться, собирая информацию с датчиков. Основываясь на этих показаниях v1:t и предполагаемые перемещения m1:t, робот пытается определить свое местоположение. Из-за проскальзывания колес по полу запланированное действие робота, например "двигаться вперед", может оказаться неудачным. Учитывая всю имеющуюся у робота информацию, он хотел бы вывести значение p(ht |v1:t , m1:t ). Эта задача отличается от задачи взломщика сценарий, в котором робот теперь знает о предполагаемых движениях, которые он совершает. Это должно дать больше информации
ЧЕРНОВИК от 9 марта 2010 г.421 Обучение HMMs
Рисунок 23.8: Модель самолокализации робота. Каждый раз, когда робот совершает запланированное движение, mt. В качестве обобщающей модели, зная предполагаемое перемещение mt и текущее положение на сетке ht, робот имеет представление о том, где он должен находиться на следующем временном шаге и какие показания датчика vt+1 он ожидает там получить. Основываясь только на информации датчика v1:T и предполагаемых перемещениях m1:T, задача состоит в том, чтобы сделать вывод распределение по местоположениям робота p(h1:T |m1:T , v1:T ).
о том, где он может находиться. Это можно рассматривать как дополнительную "видимую" информацию, хотя более естественно думать об этом как о дополнительной входной информации. Моделью этого сценария является, см. рис.23.8,
Известны видимые переменные v1:T, а также предполагаемые движения m1:T . Модель показывает, что движения, выбранные роботом, являются случайными (следовательно, не требуется принимать решения о том, куда двигаться дальше). Мы предполагаем, что робот обладает полным знанием условных распределений, определяющих модель (он знает "карту" своего окружения и все вероятности перехода в другое состояние и выбросов). Если наш интерес заключается только в локализации робота, поскольку входные данные m известны, то эта модель фактически является формой зависящей от времени HMM:
для зависящего от времени перехода p(ht |ht;1 , t) , определяемого предполагаемым перемещением mt;1 . В этом случае любая требуемая задача логического вывода выполняется в соответствии со стандартными стационарными алгоритмами HMM, хотя и при замене не зависящих от времени переходов p (ht |ht-1) известными зависящими от времени переходами.
При самолокализации и картографировании (SLAM) робот не знает карту своего окружения. Это соответствует необходимости изучать переходный процесс и распределение выбросов "на лету" по мере изучения окружающей среды.
23.2.7 Модели естественного языка
Простая порождающая модель языка может быть получена из буквенных переходов (так называемой биграммы). В приведенном ниже примере мы используем это в HMM для устранения неправильных наборов текста.
Пример 98 (Короткие пальцы). Машинистка с "короткими пальцами", как правило, нажимает либо на нужную клавишу, либо на соседнюю. Для простоты предположим, что всего 27 клавиш: от строчной буквы a до строчной буквы z и пробел. Для моделирования этого мы используем распределение выбросов Bij = p(v = i|h = j), где i = 1, ... , 27, j = 1, ... , 27, как показано на рис.23.9. База данных о частотах перехода от буквы к букве (www.data-compression.com/english.shtml), дает матрицу перехода Aij = p(h` = i|h = j) в английском языке. Для простоты мы предполагаем, что p(h1 ) является однородным. Также мы предполагаем, что каждое нажатие клавиши приводит к однократному нажатию. Учитывая введенную последовательность kezrninh, какому наиболее вероятному слову это соответствует? Путем составления списка из 200 наиболее вероятных скрытых последовательностей (с использованием алгоритма N -max-product) и исключения тех , которых нет в стандартном словаре английского языка (www.curlewcommunications.co.uk/wordlist.html), наиболее вероятным словом, которое было задумано, является "learning \обучение". Смотрите демонстрацию программы demoHMMbigram.m.
23.3 Обучение HMMs
Учитывая набор данных V = {v1 , ... , vN } из N последовательностей, где последовательность vn = v1:T имеет длину Tn , мы ищем n матриц перехода A, матрицу выбросов\ излучения\ B и начальный вектор a, которые, скорее всего, были сгенерированы
422
ЧЕРНОВИК от 9 марта 2010 г.
Рисунок 23.9: (а): матрица перехода от буквы к букве для английского языка p (h` = i|h = j). (b): Матрица выделения букв для машинистки с "короткими пальцами", которая с большой вероятностью нажмет на клавишу или соседние с ней клавиши на клавиатуре.
V. Мы делаем предположение о том, что каждая последовательность генерируется независимо, и предполагаем, что мы знаем количество скрытых состояний H. Для простоты мы сосредоточимся здесь на случае дискретных видимых переменных, предполагая также, что мы знаем количество состояний V .
23.3.1 Алгоритм EM
Применение EM к модели HMM называется алгоритмом Баума-Уэлча и соответствует общей
стратегии, описанной в разделе (11.2).
M-шаг
Исходя из исходных данных, M-шаг определяется путем максимизации ‘энергии’:
относительно параметров A, B, a; hn обозначает h1:Tn . Используя форму HMM, мы получаем
где для компактности мы исключаем индекс последовательности из переменных h. Чтобы избежать возможной путаницы, мы записываем pnew (h1 = i) для обозначения (новой) записи таблицы для вероятности того, что исходная скрытая переменная находится в состоянии i. Оптимизируя уравнение (23.3.2) относительно p(h1) (и применяя p(h1) в качестве распределения), мы получаем
, что является средним числом случаев, когда первая скрытая переменная находилась в состоянии i. Аналогично,
это число раз, когда происходит переход из скрытого состояния i в скрытое состояние i`, усредненное по всем временам (поскольку мы предполагали стационарность) и обучающим последовательностям. Нормализуя, мы получаем
ПРОЕКТ от 9 марта 2010 г. 423 Изучаем HMMs
Наконец-то,
, что является ожидаемым числом случаев, когда для наблюдения, находящегося в состоянии j, скрытым состоянием будет i. Константа пропорциональности определяется требованием нормализации.
E-шаг
При вычислении M-го шага выше величин pold (h1 = i|vn ), pold (ht = i, ht+1 = i`|vn ) и pold (ht = i|vn ) получены путем логического вывода с использованием методов, описанных в разделе (23.2.1).
Уравнения (23.3.3,23.3.5,23.3.6) повторяются до тех пор, пока они не будут сходиться. Смотрите HMMem.m и demoHMMlearn.m.
Инициализация параметров
Алгоритм EM сходится к локальным максимумам вероятности, и, как правило, нет никакой гарантии, что алгоритм найдет глобальный максимум. Вопрос о том, как наилучшим образом инициализировать параметры, является сложным, поскольку подходящая инициализация распределения выбросов часто имеет решающее значение для успеха[229]. Практическая стратегия заключается в инициализации выбросов p(v|h) на основе предварительной настройки более простой модели нестационарной смеси ;h p(v|h)p(h) к данным.
Непрерывные наблюдения
Для непрерывного векторного наблюдения vt с dim vt = D нам требуется модель p(vt |ht), отображающая дискретное состояние ht в виде распределения по выходным данным. Использование непрерывного вывода не изменяет ни одно из стандартных уравнений передачи логических сообщений, так что логический вывод может быть выполнен для практически произвольно сложных распределений выбросов. Действительно, при фильтрации, сглаживании и выводе Витерби нормализация Z излучения\ выброса\ p(v|h) = ;(v, h)/Z не требуется. Однако для обучения требуется постоянная нормирования выбросов, поскольку она зависит от параметров модели.
23.3.2 Смешанный выброс
Для создания более полной модели выбросов (особенно для непрерывных наблюдений) одним из подходов является использование смеси
, где kt - дискретная переменная суммирования. Для целей обучения полезно рассматривать kt как дополнительные скрытые переменные, чтобы можно было получить обновления для каждого компонента модели выбросов. Чтобы достичь этого, рассмотрим вклад излучения в энергию (предполагая, что последовательности одинаковой длины):
В нынешнем виде параметры каждого компонента p(vt |kt , ht ) связаны в приведенном выше выражении. Один из подходов заключается в рассмотрении
из которого мы немедленно получаем связанный логарифм
и логарифм
424 ПРОЕКТ от 9 марта 2010 г., Обучение HMMs
Используя это в качестве энергетического вклада (23.3.8), мы получаем оценку энергетического вклада
Теперь мы можем максимизировать эту нижнюю границу энергии (вместо самой энергии). Вклад каждого компонента выбросов p(v = v|h = h, k = k) равен
Затем вышеуказанное может быть оптимизировано (M-шаг) для фиксированного q (kt = k|hnt = h), при этом эти распределения обновляются с использованием
Вклад в энергетическую зависимость от веса смеси определяется как
, так что обновление веса смеси с шагом M составляет
В этом случае алгоритм EM состоит из цикла EM "выбросов", в котором фиксируются переходы и q(hnt = h|v1: T n), в течение которого обучаются выбросы p(v|h, k), а также обновляется q(k = k|hn = h). Цикл EM "переход" фиксирует распределение выбросов p(v|h) и определяет наилучший переход p(ht |ht;1).
Альтернативой приведенному выше выводу является рассмотрение k в качестве скрытых переменных, а затем использование стандартных алгоритмов EM для совместных скрытых переменных (ht, kt ). Читатель может показать, что эти два подхода эквивалентны.
23.3.3 HMM-GMM
Распространенным компонентом модели выбросов смеси для непрерывного наблюдения является гауссова
таким образом, kt , ht индексирует средние векторы K ; H и ковариационные матрицы. Обновления EM для этих средств\ значений\ и ковариации легко вывести из уравнения (23.3.12), см. упражнение(232). Эти модели являются часто используется в приложениях отслеживания, в частности в распознавании речи (обычно при условии, что ковариации являются диагональными).
23.3.4 Различающее обучение
HMMs можно использовать для контролируемого обучения последовательностей. То есть для каждой последовательности v1:T соответствует метка класса cn . Например, мы могли бы связать конкретного композитора c с последовательностью v1:T и захотеть создать модель, которая будет предсказывать композитора для новой музыкальной последовательности. Генеративный подход к использованию HMM для классификации заключается в подготовке отдельного HMM для каждого класса, p(v1:T |c) и последующем использовании правила Байеса для формирования классификации для новой последовательности v1:T* с использованием
Однако, если данные зашумлены и их трудно моделировать, такой генеративный подход может не сработать, поскольку большая часть выразительных возможностей каждой модели используется для моделирования сложных данных, а не для фокусирования на
ЧЕРНОВИК от 9 марта 2010 года
425 Связанные модели
Рисунок 23.10: Явная длительность HMM. Переменные счетчика ct детерминированно ведут обратный отсчет до нуля. Когда они достигают единицы, разрешается переход h, и производится выборка нового значения для ct.
границы принятия решения. В таких приложениях, как распознавание речи, часто сообщается об улучшении производительности, когда модели обучаются дискриминационным образом. В случае дискриминационного обучения см., например [150], определяется новая единая дискриминантная модель, сформированная из C HMMS с использованием
и затем максимизирует вероятность набора наблюдаемых классов и соответствующих наблюдений v1:T . Для единичной пары данных (cn , v1:T n) логарифмическая вероятность равна
Первое слагаемое, приведенное выше, представляет собой производящий вероятностный термин, а последнее слагаемое учитывает различие. Хотя получение обновлений в стиле EM затруднено из-за различающих терминов, вычисление градиента является простым с использованием метода, описанного в разделе (11.7).
В некоторых приложениях на каждом временном шаге доступна метка класса ct вместе с данными наблюдения vt . При наличии обучающей последовательности v1:T, c1:T (или, в более общем случае, набора последовательностей) цель состоит в том, чтобы найти оптимальный класс последовательности c;1:T для новой последовательности наблюдений v1:T;. Один из подходов заключается в обучении порождающей модели
и затем использовать Витерби для формирования класса c;1: T = arg maxc1:tp(c1:T |v1:T ). Однако этот подход может оказаться неоптимальным с точки зрения классовой дискриминации. Дешевым заменителем является раздельное обучение дискриминационной классификационной модели p(ct |vt ). С помощью этого можно сформировать выборку (здесь написано для непрерывного vt ).
где ~p(vt ) определяется пользователем. При вычислении локальной нормализации ;vt ~p(ct |vt ) ~p(vt ) может возникнуть проблема, если единственным использованием p(vt |ct ) является поиск оптимальной последовательности классов для новой последовательности наблюдений v1:T;
, то локальные нормализации не играют никакой роли, поскольку они не зависят от c. Следовательно, во время декодирования Витерби мы можем заменить термин p(vt |ht) на ~p(ct |vt ), не влияя на оптимальную последовательность. Использование модели таким образом является частным случаем общей гибридной процедуры, описанной в разделе (13.2.4). Подход является неоптимальным, поскольку обучение классификатора отделено от обучения модели перехода. Тем не менее, это эвристика исторически пользуется некоторой поддержкой в сообществе распознавания речи.
23.4 Связанные модели
23.4.1 Модель явной длительности
Для HMM с самопереходом p(ht = i|ht-1 = i) ; yi вероятность того, что скрытая динамика остается в состоянии i в течение ; временных шагов, равна yi;, которая экспоненциально уменьшается со временем. На практике, однако, мы бы
426
ПРОЕКТ от 9 марта 2010 года, связанный с моделями
Рисунок 23.11:Ввод-вывод первого порядка скрытой Марковской модели. Входные x и выходные v узлы заштрихованы, чтобы подчеркнуть, что их состояния известны в течение- в процессе обучения. Во время тестирования входные данные известны, а выходные предсказаны.
часто предпочитают ограничивать динамику, чтобы она оставалась в одном и том же состоянии в течение минимального количества временных шагов или имела заданное распределение длительности. Способ обеспечить это - использовать скрытую переменную счетчика ct, которая в начале инициализируется длительностью, выбранной из распределения длительностей pdur (ct ) , с максимальной длительностью Dmax . Затем на каждом временном шаге счетчик уменьшается на 1, пока не достигнет 1, после чего отсчитывается новая длительность:
Переход в состояние ht возможен только при ct = 1:
Включение переменной счетчика c определяет совместное распределение скрытых переменных (c1:T, h1:T), которое обеспечивает восстановление h за требуемое минимальное количество временных интервалов, см. рис.(23.10). Поскольку dim ct ; ht = Dmax H, наивно вычислительная сложность вывода в этой модели равна примерно О(Т Н2 Dmax 2 ). Однако, когда выполняется прямая и обратная рекурсии, детерминированный характер переходов означает, что это может быть уменьшено примерно до О(Т Н2 Dmax ) [199] – смотрите также упражнение(233).
Скрытая полумарковская модель обобщает явную модель длительности в том смысле, что после выборки новой длительности ct модель выдает распределение p(vt:t+ct -1 |ht), определенное на сегменте следующих наблюдений ct[216].
23.4.2 Вход-выход HMM
IOHMM[31] - это HMM с дополнительными входными переменными x1:T, см. рис.23.11. Каждый вход может быть непрерывным или дискретным и модулировать переходы
IOHMM может использоваться в качестве условного предиктора, где выходные данные vt представляют прогноз в момент времени T. В случае непрерывных входов и дискретных выходов таблицы p(vt |ht , xt ) и p(ht |ht;1 , xt ) обычно параметризуются с использованием нелинейной функции, например
Затем следует вывод, аналогичный стандартному HMM. Определяющий
прямой проход дается с помощью
ПРОЕКТ от 9 марта 2010 г. 427 Связанных моделей
Рисунок 23.12: Линейная цепная CRF. Поскольку входные данные x учитываются, распределение представляет собой просто линейный граф коэффициентов цепочки. Таким образом, вывод попарных значений p(yt , yt;1 |x) прост с использованием передачи сообщений.
Обратный проход ; равен
для чего нам нужно
Вероятность может быть найдена из ;hT ;(hT ).
Смещение направления
Рассмотрим прогнозирование распределения выходных данных p(vt |x1:T ) с учетом как прошлой, так и будущей входной информации x1:T . Поскольку скрытые состояния остаются ненаблюдаемыми, мы имеем p(vt |x1:T ) = p(vt |x1:t ). Таким образом, предсказание использует только прошлую информацию и отбрасывает любую контекстуальную информацию о будущем. Это ‘смещение направления" иногда считается проблематичным (особенно при моделировании на естественном языке) и мотивирует использование ненаправленных моделей, таких как условные случайные поля.
23.4.3 Линейные цепные CRFs
Линейные цепные условные случайные поля (CRF) являются расширением неструктурированных CRF, которые мы кратко обсуждали в разделе (9.4.6), и применяются для моделирования распределения набора выходных данных y1:T при заданном входном векторе x. Например, x может представлять предложение на английском языке, а y1:T должно представлять перевод на французский. Обратите внимание, что вектор x не обязательно должен иметь размерность T . Линейный элемент первого порядка цепочка CRF имеет вид
, где ; - свободные параметры потенциалов. На практике обычно используются потенциалы вида
, где fk,t (yt , yt;1 , x) - это "характеристики’, смотрите также раздел (9.4.6). Учитывая набор пар последовательностей ввода-вывода, xn, y1:T n , n = 1, . . . , N (предполагая, что все последовательности имеют одинаковую длину T для простоты), мы можем узнать параметры ; с максимальной вероятностью. В соответствии со стандартным предположением о распределении данных логарифмическая вероятность равна
Читатель может легко проверить, что логарифмическая вероятность является вогнутой, так что целевая функция не имеет локального оптимума. Градиент задается формулой
Таким образом, обучение требует вывода предельных значений p(yt , yt;1 |x, ;). Поскольку уравнение (23.4.11) соответствует линейному графику коэффициентов цепочки, см. рис. (23.12), вывод попарных граничных значений прост
428 ЧЕРНОВИК 9 марта 2010 года Модели, относящиеся к
Рисунок 23.13: Использование линейной цепочки CRF для изучения последовательностей из таблицы(23.1). (а): Изменение логарифмической вероятности при подъеме по градиенту. (b): Вектор обученных параметров ; в конце обучения.
используя передачи сообщений. Этого можно достичь, используя либо стандартную передачу сообщений по факторному графу, либо используя явный алгоритм, см. упражнение(227).
Найти наиболее вероятную выходную последовательность для нового входного сигнала x; несложно, поскольку
снова соответствует простой линейной цепочке, для которой вывод максимального произведения дает требуемый результат, см. также упражнение(226).
В некоторых приложениях, особенно при обработке естественного языка, размерность K вектора признаков f1 , ... , fK может составлять многие сотни тысяч. Это означает, что запоминание Гессиана невозможно для обучения на основе Ньютона, и обычно предпочтительны методы с ограниченной памятью или методы сопряженного градиента [288].
Таблица 23.1: Подмножество из 10 обучающих последовательностей ввода-вывода. Каждая строка содержит входные данные xt (верхняя запись) и выходные данные yt (нижняя запись). Имеется 10 входных состояний и 3 выходных.
Пример 99 (Линейная цепная CRF). В качестве модели для данных, приведенных в таблице(23.1), линейная модель CRF имеет потенциалы ;(yt , yt;1 , xt ) = exp ( ;i ;i fi (yt , yt;1 , xt )), где мы задаем бинарные функции признаков, сначала отображая dim(x) ; dim (y)2 функций, каждая из которых указывает на уникальное целое число i(a, b, c) от 1 до dim (x) ; dim (y)2
То есть каждая совместная конфигурация yt , yt;1 , xt сопоставляется с индексом, и в этом случае вектор признаков f будет тривиально содержать только одну ненулевую запись. Эволюция алгоритма обучения подъему по градиенту такова показано на рисунке (23.13). На практике можно было бы использовать функции с расширенным набором признаков, определенные для поиска признаков входной последовательности x, а также для создания вектора признаков с более чем одним ненулевым значением. Смотрите проект demoLinearCRF.m.
от 9 марта 2010 г. 429 заявок
Рисунок 23.14: Динамическая байесовская сеть. Возможные переходы между переменными в одном и том же временном интервале не показаны.
Рисунок 23.15: Связанный HMM. Например, вверх- каждая HMM может моделировать речь, и чем ниже уровень, тем больше соответствующий видеоряд. Верхние скрытые элементы соответствуют фонемам, а нижние - положению рта; таким образом, эта модель отражает ожидаемую связь между положением рта и фонемами.
23.4.4 Динамические Байесовские сети
DBN определяется как сеть убеждений, воспроизводимая во времени. Для многомерного xt с dim xt = D, DBN определяет совместную модель
где x\i (t) обозначает набор переменных в момент времени t, за исключением xi (t). Форма каждого p(xi (t)|x\i (t), x(t;1)) выбирается таким образом, чтобы общее распределение оставалось ациклическим. На каждом временном шаге t существует набор переменных xi (t), i = 1, . . . , X, некоторые из которых могут наблюдаться. В DBN первого порядка каждая переменная xi (t) имеет родительские переменные, взятые из набора переменных в предыдущем временном интервале, xt-1, или из текущего временного интервала. В большинстве приложений модель является однородной во времени, так что можно полностью описать распределение в с точки зрения модели с двумя временными срезами, рис.23.14. Обобщение на модели более высокого порядка является простым. Связанный HMM - это специальный DBN, который может использоваться для моделирования связанных "потоков" информации, например видео и аудио, см. рис.(23.15)[209].
23.5 Приложения
23.5.1Отслеживание объектов
HMM используются для отслеживания движущихся объектов, основываясь на понимании динамики объекта (закодированном в распределении переходов) и понимании того, как объект с известным положением будет наблюдаться (закодированном в распределении выбросов). При наличии наблюдаемой последовательности скрытое положение может быть затем выведено. В качестве примера можно привести взломщика (10). HMMS применялись во многих контекстах отслеживания, включая отслеживание людей в видео, подачу музыки и многое другое[54, 229, 51].
23.5.2 Автоматическое распознавание речи
Многие системы распознавания речи используют HMMS[300]. Грубо говоря, непрерывный выходной вектор vt в момент времени t представляет, какие частоты присутствуют в речевом сигнале в небольшом интервале времени t. Эти акустические векторы обычно формируются на основе дискретного преобразования Фурье речевого сигнала в течение небольшого промежутка времени t с дополнительными преобразованиями, имитирующими слуховую обработку человеком. В качестве альтернативы могут быть использованы соответствующие формы линейного кодирования наблюдаемой формы акустического сигнала[131].
Соответствующее дискретное скрытое состояние ht представляет собой фонему – базовую единицу человеческой речи (в стандартном английском языке их 44). Обучающие данные тщательно обрабатываются лингвистом, который
430
ПРОЕКТ приложения от 9 марта 2010
определяет фонему ht для каждого момента времени t и множества различных наблюдаемых последовательностей vt . Затем дается каждая акустический вектор vt и связанную с ним фонему ht можно использовать с максимальным правдоподобием, чтобы сопоставить смесь (обычно изотропных) гауссиан p(vt |ht ) с vt . Это формирует распределение выбросов \излучения \ для HMM.
Используя базу данных помеченных фонем, можно выучить фонемный переход p(ht |ht;1) (путем простого подсчета) и сформировать распределение переходов для HMM. Обратите внимание, что в этом случае, поскольку "скрытая" переменная h и наблюдение v известны во время обучения, обучение HMM является простым и сводится к обучению распределений выбросов и переходных процессов независимо друг от друга.
Для новой последовательности "акустических" векторов v1:T мы можем затем использовать HMM для определения наиболее вероятной последовательности фонем во времени, arg maxh1:T p(h1:T |v1:T ), которая учитывает как то, как фонемы отображаются в виде акустических векторов, так и предшествующие языковые ограничения вероятных переходов от фонемы к фонеме. Тот факт, что люди говорят с разной скоростью, может быть устранен с помощью искажения во времени \обернуть время\, при котором скрытая фонема остается в одном и том же состоянии в течение некоторого количества временных шагов.
Модели HMM обычно обучаются на основе предположения о "чистоте" основной речи. На практике шум искажает речевой сигнал сложным образом, так что результирующая модель становится неподходящей, а производительность значительно снижается. Чтобы учесть это, традиционно перед отправкой сигнала в стандартный распознаватель HMM пытаются устранить шумы.
Если HMM используется для моделирования одного слова, естественно ограничить последовательность скрытых состояний, чтобы она перемещалась "вперед" во времени, последовательно посещая набор состояний (поскольку порядок фонем в слове известен). В этом случае структура матриц перехода является верхнетреугольной (или нижнетреугольной, в зависимости от по вашему определению), или даже треугольная матрица с полосами. Такие прямые ограничения описывают так называемую матрицу перехода слева направо .
23.5.3 Биоинформатика
В области биоинформатики HMM широко применяются для моделирования генетических последовательностей. Особенно успешным оказалось множественное выравнивание последовательностей с использованием форм ограниченных HMM. Другие приложения включают поиск генов и моделирование семейства белков[163, 84].
23.5.4 Маркировка частей речи
Рассмотрите предложение ниже, в котором каждое слово было в языковом плане с метками
hospitality_NN an_AT is_BEZ excellent_JJ virtue_NN ,_,
but_CC not_XNOT when_WRB the_ATI guests_NNS have_HV
to_TO sleep_VB in_IN rows_NNS in_IN the_ATI cellar_NN !_!
Нижние индексы обозначают лингвистический тег, например, NN - это тег имени существительного в единственном числе, ATI - это тег артикля и т. д. При наличии обучающего набора таких помеченных последовательностей задача состоит в том, чтобы пометить новую последовательность слов. Один из подходов заключается в том, чтобы использовать ht в качестве метки, а vt в качестве слова и сопоставить HMM с этими данными. Для обучающих данных используются как метки, так и слова, так что обучение переходу и распределению выбросов с максимальной вероятностью может быть достигнуто простым подсчетом. Учитывая новую последовательность слов, наиболее вероятная последовательность тегов может быть определена с помощью алгоритма Витерби.
Более современные средства определения частей речи, как правило, используют условные случайные поля, в которых входная последовательность x1:T является предложением, а выходная последовательность y1:T является последовательностью тегов. Одна из возможных параметров для линейной цепочки CRF заключается в использовании потенциала вида ;(yt;1 , yt );(yt , x), в котором первый фактор кодирует грамматическую структуру языка, а второй - априори вероятный признак yt [166].
ДРАФТ от 9 марта 2010 года 431 Упражнения
23.6 Код
demoMixMarkov.m: Демонстрация смеси марковских моделей
mixMarkov.m: Демонстрация смеси марковских моделей
demoHMMinference.m: Демонстрация вывода HMM
HMMforward.m: Прямая ;-рекурсия
HMMbackward.m: Прямая ;-рекурсия
HMMgamma.m: Рекурсия ;-коррекции RTS
HMMsmooth.m: Одиночное и попарное ; ; ;-сглаживание
HMMviterbi.m: Алгоритм наиболее вероятного состояния (Витерби)
demoHMMburglar.m: Демонстрация локализации взломщика
demoHMMbigram.m: демонстрация набора текста короткими пальцами
HMMem.m: Электронный алгоритм для HMM (Баум-Уэлч)
demoHMMlearn.m: демонстрация электронного алгоритма для HMM (Баум-Уэлч)
demoLinearCRF.m: демонстрация изучения линейной цепочки CRF
Следующий линейный цепной CRF-потенциал особенно прост, и на практике можно было бы использовать более сложный вариант.
linearCRFpotential.m: Линейный потенциал CRF
Следующие процедуры определения вероятности и градиента действительны для любого линейного потенциала CRF ;(yt;1 , yt , x).
linearCRFgrad.m: Линейный градиент CRF
linearCRFloglik.m: Логарифмическая вероятность линейного CRF
23.7 Упражнения
Упражнение 217. Стохастическая матрица Mij в виде неотрицательных элементов с ;i Mij = 1. Рассмотрим собственное значение ; и собственный вектор e, такие как ;j Mij ej = ;ei . Суммируя по i, показываем, что если ;i ei > 0, то ; должно быть равно 1.
Упражнение 218. Рассмотрим цепь Маркова с матрицей переходов
Покажите, что эта цепочка Маркова не имеет равновесного распределения, и укажите стационарное распределение для этой цепочки.
Упражнение 219. Рассмотрим HMM с 3 состояниями (M = 3) и 2 выходными символами, с
матрицей перехода состояний слева направо
, где Aij ; p(h(t + 1) = i|h(t) = j), матрица выбросов Bij ; p(v(t) = i|h(t) = j)
и вектор вероятности начального состояния a = (0.9 0.1 0.0)T . Учитывая, что наблюдаемая последовательность символов равна v1:3 = (0, 1, 1):
1. Вычисляем p(v1:3 ).
2. Вычисляем p(h1 |v1:3 ).
3. Найдите наиболее вероятную последовательность скрытых состояний arg maxh1:3 p(h1:3 |v1:3 ).
432 ЧЕРНОВИК от 9 марта 2010 г. Упражнения
Упражнение 220. Это упражнение следует из примера(98). Учитывая строку из 27 символов длиной rgenmonleunosbpnntje vrancg, набранную "короткими пальцами", какое предложение на английском языке является наиболее правильным ? В списке расшифрованных последовательностей, какое значение имеет log p(h1:27 |v1:27 ) для этой последовательности? Вам нужно будет соответствующим образом изменить demoHMMbigram.m.
Упражнение 221. Покажите, что если вероятность перехода Aij = p(ht = i|ht;1 = j) в HMM инициализирована как равен нулю при обучении EM, то он будет оставаться равным нулю на протяжении всего обучения.
Упражнение 222. Рассмотрим задачу: Найдите наиболее вероятную совместную последовательность вывода v1:T для HMM. То есть
, где
1. Объясните, почему для этой задачи, как правило, невозможно найти локальный алгоритм передачи сообщений, и обсудите вычислительную сложность нахождения точного решения.
2. Объясните, как адаптировать алгоритм максимизации математического ожидания для создания рекурсивного алгоритма, например нахождение приблизительного значения v1:T; . Объясните, что это гарантирует улучшение решения на каждой итерации. Кроме того, объясните, как алгоритм может быть реализован с использованием локальной передачи сообщений.
Упражнение 223. Объясните, как обучить HMM с помощью EM, но с ограниченной матрицей переходов. В частности, объясните, как обучить матрицу переходов с верхнетреугольной структурой.
Упражнение 224. Напишите программу, которая будет соответствовать совокупности марковских моделей L-го порядка.
Упражнение 225.
1. Используя соответствие A = 1, C = 2, G = 3, T = 4, определите матрицу переходов p размером 4 ; 4, которая создает последовательности вида
А, С, Г, Т, А, С, Г, Т, А, С, Г, Т, А, С, Г, Т, . . .. (23.7.6)
Теперь определим новую матрицу перехода
Определите матрицу перехода q размером 4 ; 4, которая создает последовательности вида
Т, Г, С, А, Т, Г, С, А, Т, Г, С, А, Т, Г, С, А, . . . .(23.7.8)
Теперь определите новую матрицу перехода
Предположим, что вероятность нахождения в начальном состоянии цепи Маркова p(h1) постоянна для всех четырех состояний A, C, G, T . Какова вероятность того, что цепь Маркова pnew сгенерировала последовательность S, заданную формулой
S ; A, A, G, T, A, C, T, T, T, A, C, C, T, A, C, G, C (23.7.10)
2. Аналогично, какова вероятность того, что S был сгенерирован qnew? Имеет ли смысл, что S имеет более высокую вероятность при pnew по сравнению с qnew?
ПРОЕКТ от 9 марта 2010 г. 433 Упражнения
3. Используя функцию randgen.m, сгенерируйте 100 последовательностей длиной 16 из цепочки Маркова, определенной с помощью pnew. Аналогично, сгенерируйте по 100 последовательностей длиной 16 из цепочки Маркова, определенной с помощью qnew. Объедините все эти последовательности в массив ячеек v таким образом, чтобы v{1} содержал первую последовательность и v{200} последняя последовательность. Используйте MixMarkov.m, чтобы узнать оптимальные параметры максимального правдоподобия, которые сгенерировали эти последовательности. Предположим, что существует H = 2 вида цепей Маркова. Результат, возвращаемый в phgvn, указывает апостериорную вероятность присвоения последовательности. Согласны ли вы с найденным решением?
4. Возьмите последовательность S, определенную в уравнении (23.7.10). Определите распределение выбросов, которое имеет 4 выходных состояния, таких что
Используя это распределение выбросов и переход, заданный pnew, определенный в уравнении (23.7.7), адаптируем demoHMMinferenceSimple.m подходит для нахождения наиболее вероятной скрытой последовательности hp1:16, которая сгенерировала наблюдаемую последовательность S. Повторите это вычисление, но для перехода qnew, чтобы получить hq1:16 . Какую скрытую последовательность – hp1:16 или hq1:16 - предпочтительнее? Обоснуйте свой ответ.
Упражнение 226. Выведите алгоритм, который найдет наиболее вероятное совместное состояние
для произвольно определенных потенциалов ;t (ht;1 , ht ).
1. Сначала рассмотрим
Покажите, как максимизация по hT может быть реализована внутри произведения \продукта\ и что результат максимизации может быть интерпретирован как сообщение
2. Выведите рекурсию
3. Объясните, как приведенная выше рекурсия позволяет вычислить
4. Объясните, как после вычисления наиболее вероятного состояния для h1 можно эффективно вычислить оставшиеся оптимальные состояния h2, ... , hT.
Упражнение 227. Выведите алгоритм, который будет вычислять попарные маргиналы
из совместного распределения
для произвольно определенных потенциалов ;t (ht;1 , ht ).
434 ПРОЕКТ от 9 марта 2010 г. Упражнения
1. Сначала рассмотрим
Покажите, как суммирование по h1 может быть перенесено в продукт и что результат максимизации может быть интерпретирован как сообщение
2. Выведите рекурсию
3. Аналогично, покажите, что можно ввести суммирование hT внутри продукта, чтобы определить
и что, вводя hT -1 и т.д., можно определять сообщения
4. Покажите, что
Упражнение 228. HMM второго порядка определяется как
Следуя подходу, аналогичному подходу к HMM первого порядка, явно выведите алгоритм передачи сообщений для вычисления наиболее вероятного совместного состояния
Упражнение 229. Поскольку вероятность HMM может быть вычислена только с помощью фильтрации, в принципе, нам не нужно сглаживание, чтобы максимизировать вероятность (в отличие от подхода EM). Объясните, как вычислить градиент вероятности с использованием только отфильтрованной информации (т.е. с использованием только прямого прохода).
Упражнение 230. Выведите обновления EM для сопоставления HMM с распределением выбросов, полученным с помощью смеси переменных Гаусса.
Упражнение 231. Рассмотрим HMM, определенный для скрытых переменных H = {h1 , . . . , hT } и наблюдений V = {v1 , . . . , vT }
Покажите, что задняя часть p (H | V) является цепью Маркова
где ~p(ht |ht;1 ) и ~p(h1 ) - соответственно определенные распределения.
ПРОЕКТ от 9 марта 2010 года 435 упражнений
Упражнение 232. Для обучения HMM с использованием гауссовой смеси излучений (модель HMM-GMM) в разделе(23.3.3) выведите следующие формулы обновления EM для средних значений и ковариаций:
и
, где
Упражнение 233. Рассмотрим модель длительности HMM, определенную уравнением (23.4.2) и уравнением (23.4.1) с распределение выбросов p(vt |ht ). Наш интерес состоит в том, чтобы получить рекурсию для отфильтрованного распределения при
1. Покажите, что :
2. Используя это, выведите
3. Покажите, что правая часть приведенной выше формулы может быть записана в виде
4. Покажите, что рекурсия для ; тогда задается как
и для c > 1
5. Объясните, почему вычислительная сложность отфильтрованного вывода в модели длительности составляет около O(T H2 D max).
6. Выведите эффективный алгоритм сглаживания для этой модели длительности.
436 ЧЕРНОВИК главы от 9 марта 2010 г.
24 Глава
Марковские модели с непрерывным состоянием
24.1Наблюдаемые линейные динамические системы
Во многих практических приложениях, использующих временные ряды, данные, естественно, непрерывны, особенно для моделей физической среды. В отличие от Марковских моделей с дискретным состоянием, описанных в главе(23), распределения с непрерывным состоянием не закрываются автоматически при выполнении таких операций, как продукты\ произведения и маргинализация. К поэтому при разработке практических алгоритмов, для которых можно эффективно выполнять логический вывод и обучение, мы сильно ограничены в форме непрерывного перехода p(vt |vt;1 ). Простым, но мощным классом таких переходов являются линейные динамические системы. Детерминированная наблюдаемая линейная динамическая система1 (OLDS) определяет временную эволюцию вектора vt в соответствии с уравнением обновления в дискретном времени
где At - матрица перехода в момент времени t. Для случая, когда At инвариантна по отношению к t, процесс называется не зависит \ инвариант\ -от- времени, что мы и предполагаем, если явно не указано иное.
Мотивация для обучения OLDSs заключается в том, что многие уравнения, описывающие физический мир, могут быть записаны в виде OLDS. Старые модели интересны тем, что их можно использовать в качестве простых моделей прогнозирования: если vt описывает состояние окружающей среды в момент времени t, то Avt предсказывает состояние окружающей среды в момент времени t+1. Как таковые, эти модели имеют широкое применение во многих отраслях науки, от инженерии и физики до экономики.
Уравнение ОЛДСА (24.1.1) является детерминированным, так что, если мы укажем v1 , будут определены все будущие значения v2 , v3 , ... . Для dim v = V;мерного вектора его эволюция описывается выражением
где ; = diag (;1 , ... , ;V ) - диагональная матрица собственных значений, а P — соответствующая матрица собственных векторов A. Если ;i > 1, то при большом t значение vt будет увеличиваться. С другой стороны, если ;i < 1, то ;t;1 i будет стремиться к нулю. Поэтому для стабильных систем нам не требуются собственные значения, величина которых превышает 1, а только единица собственные значения будут влиять на результат в долгосрочной перспективе. Обратите внимание, что собственные значения могут быть сложными, что соответствует вращательному поведению, см. Упражнение(234). В более общем плане мы можем рассмотреть аддитивный шум на v и определить стохастический OLDS.
Определение 111 (Наблюдаемая Линейная Динамическая Система \OLDS).
1Мы используем терминологию "наблюдаемая \O" LDS \СПД, LDS, чтобы отличить ее от более общей модели пространства состояний LDS \СПД, LDS. Однако в некоторых текстах термин LDS применяется к моделям, обсуждаемым в этой главе.
437 Авторегрессионные модели
, где ; t - вектор шума, выбранный из Гауссовского распределения.,
Это эквивалентно Марковской модели первого порядка
При t = 1 мы имеем начальное распределение p(v1 ) = N (v1 |µ1 , ;1 ). При t > 1, если параметры не зависят от времени, µt ; µ , Ai ; A, ;t ; ;, процесс называется не зависящим от времени.
24.1.1 Стационарное распределение с шумом
Рассмотрим одномерную линейную систему
Если мы начнем с некоторого состояния v1 , а затем для t > 1 выполним рекурсивную выборку в соответствии с vt = avt;1 + nt , будет ли распределение vt , t » 1 имеет тенденцию к устойчивому, фиксированному распределению? Предполагая, что мы можем представить распределение vt;1 как Гауссово со средним значением µt;1 и дисперсией ;2t;1 , v t;1 ~ N (vt;1 |µt;1 , ;2 t;1 ), тогда, используя <;t > = 0 , мы имеем
так что
Предполагая, что существует фиксированная дисперсия ;;2 для случая бесконечного времени стационарное распределение удовлетворяет
Аналогично, среднее значение задается как µ; = a; µ1 . Если a ; 1, то дисперсия (и среднее значение) увеличивается бесконечно с увеличением t. При a < 1 среднее значение стремится к нулю, но дисперсия остается конечной. Несмотря на то, что величина vt;1 уменьшается в a раз на каждой итерации, аддитивный шум в среднем увеличивает величину, так что она остается стабильной в долгосрочной перспективе. В более общем плане для системы, обновляющей вектор vt в соответствии с
для существования устойчивого состояния требуется, чтобы все собственные значения A были ; 1.
24.2 Авторегрессивные модели
Скалярная авторегрессионная модель, не зависящая от времени, определяется
как
где a = (a1 , . . . , aL )T называются коэффициентами AR, а ;2 - инновационным шумом. Модель
предсказывает будущее на основе линейной комбинации предыдущих L наблюдений. В качестве сети убеждений модель AR может быть записана как Марковская модель L-го порядка:
438 ЧЕРНОВИК от 9 марта 2010 г. Авторегрессивных моделей
Рисунок 24.1: Примерка модели AR 3-го порядка к точкам обучения. Ось х представляет время, а ось y - значение временных рядов. Сплошная линия - среднее значение прогноза, а пунктирные линии - ± одно стандартное отклонение. Смотрите демонстрацию demoARtrain.m
при
Вводим вектор из L предыдущих наблюдений
мы можем записать более компактно
Модели дополненной реальности широко используются для прогнозирования финансовых временных рядов (см., например, [272]), поскольку они способны фиксировать простые тенденции в данных. Другой распространенной областью применения является обработка речи, в которой для одномерного речевого сигнала, разбитого на окна длиной T, коэффициенты AR наилучшим образом описывают сигнал в каждом окне определяется[215]. Затем эти коэффициенты AR формируют сжатое представление сигнала и затем передаются для каждого окна, а не для самого исходного сигнала. Затем сигнал может быть приблизительно восстановлен на основе коэффициентов AR. Такое представление используется, например, в телефонах и известно как линейный прогнозирующий вокодер[257].
24.2.1 Обучение AR-модели
Обучение коэффициентов AR с Максимальным Правдоподобием является простым в лоб и основано на
Дифференцируя w.r.t. a и приравнивая нулю, мы получаем
так, чтобы это было оптимально
Эти уравнения могут быть решены методом исключения по Гауссу. Аналогично, оптимально,
Выше мы предполагали, что доступны "отрицательные" моменты времени, чтобы упростить обозначение. Если время до начала периода, в течение которого мы узнаем коэффициенты, недоступно, требуется небольшая корректировка, чтобы начать суммирование с t = L + 1.
При наличии обученного a можно делать прогнозы на будущее, используя vt+1 = ~vtT a. Как мы видим, модель способна фиксировать тенденцию в данных.
ПРОЕКТ от 9 марта 2010 г. 439 Авторегрессионных моделей
Рисунок 24.2: Изменяющаяся во времени модель дополненной реальности АR как скрытая LDS. Поскольку данные наблюдений известны, эта модель представляет собой изменяющуюся во времени латентную LDS, для которой сглаженный вывод определяет изменяющиеся во времени коэффициенты AR.
24.2.2AR-модель в виде OLDS
Мы можем записать уравнение (24.2.1) в виде OLDS, используя
Мы можем записать уравнение (24.2.1) в виде OLDS
где мы определяем блочные матрицы
В этом представлении первый компонент вектора обновляется в соответствии со стандартной моделью AR, а остальные компоненты являются копиями предыдущих значений.
24.2.3 Изменяющаяся во времени модель дополненной реальности AR
Альтернативой методу Максимального Правдоподобия является рассмотрение обучения коэффициентов AR как проблемы вывода в скрытой модели LDS, которая подробно обсуждается в разделе (24.3). Если at - это скрытые коэффициенты AR, то термин
можно рассматривать как распределение выбросов скрытого LDS, в котором скрытая переменная находится в точке at , а матрица выбросов, зависящая от времени задается ^vt;1T . Путем размещения простого скрытого перехода,
мы рекомендуем, чтобы коэффициенты AR медленно менялись со временем. Это определяет модель
тогда нас интересует условное значение p(a1: T |v1:T), из которого мы можем вычислить апостериорное значение, наиболее вероятное последовательность коэффициентов AR. Затем могут быть применены стандартные алгоритмы сглаживания для получения изменяющегося во времени коэффициентов AR, смотрите в разделе demoARlds.m.
Определение 112 (Дискретное преобразование Фурье DFT). Для последовательности x0:N -1 значение DFT f0:N -1 определяется как
fk - это (комплексное) представление того, сколько частот k присутствует в последовательности x0:N -1 . Мощность компонента k определяется как абсолютная длина комплексного fk .
440 ЧЕРНОВИК от 9 марта 2010 г. Авторегрессионные Модели
Рисунок 24.3: (а): Необработанная запись 5-секундной песни соловья (с дополнительным фоновым пением птиц). (b): спектрограмма (a) с частотой до 20 000 Гц. (c): Группировка результатов на панели (b) с использованием модели гауссовой смеси из 8 компонентов. Индекс (от 1 до 8) компонента, наиболее вероятно ответственного за наблюдение, указан вертикально черным цветом. (d): 20 коэффициентов AR, полученных с использованием ;v2 = 0,001, ;h2 = 0,001, см. таблицу (e): Группировка результатов на панели (d) с использованием модели Гауссовой смеси состоит из 8 компонентов. Компоненты AR сгруппированы примерно в соответствии с различными режимами воспроизведения песен.
Определение 113 (спектрограмма). При заданном временном интервале x1:T спектрограмма в момент времени t представляет частоты, присутствующие в окне, локализованном вокруг t. Для каждого окна вычисляется Дискретное Преобразование Фурье, из которого мы получаем вектор логарифмической мощности на каждой частоте. Затем окно перемещается (обычно) на один шаг вперед и DFT вычисляется повторно. Обратите внимание, что при логарифмировании небольшие значения в исходном сигнале могут преобразоваться в заметно ощутимые значения на спектрограмме.
Пример 100 (Соловей). На рисунке(24.3, а) мы показываем исходную акустическую запись 5-секундного фрагмента песни соловья freesound.org/samplesViewSingle.php?id=17185. Спектрограмма также отображается на графике и показывает, какие частоты присутствуют в сигнале в зависимости от времени. Пение соловья очень сложное, но, по крайней мере, локально, может быть очень повторяющимся. Простой способ определить, какие сегменты повторяются, - это провести кластерный анализ спектрограммы. На рисунке (24.3,в) мы показываем результаты подбора модели Гауссовой смеси, раздел (20.3), с 8 компонентами, из которой мы видим, что компоненты повторяются локально во времени. Альтернативное представление сигнала дается с помощью изменяющегося во времени коэффициентов AR, раздел (24.2.3), как показано на рисунке (24.3d). Кластеризация GMM с 8 компонентами, рис.(24.3e)
ЧЕРНОВИК от 9 марта 2010 г. 441. Скрытые линейные динамические системы
Рисунок 24.4: (скрытая) СПД. Как скрытые, так и видимые переменные распределены по Гауссу.
в этом случае получается несколько более четкое изображение различных фаз пения соловья, чем это видно из спектрограммы.
24.3 Скрытые Линейные Динамические Системы
Скрытая LDS определяет стохастическую линейную динамическую систему в скрытом (или "скрытом") пространстве на последовательности векторов h1:T . Каждое наблюдение vt является линейной функцией скрытого вектора ht . Эта модель также называется линейной гауссовой моделью пространства состояний 2. Модель также можно рассматривать как форму LDS для совместных переменных xt = (vt , ht ), в которой отсутствуют части вектора xt. По этой причине мы также будем называть эту модель Линейной динамической системой (без префикса "скрытая").
Определение 114 (Скрытая линейная динамическая система).
переходная модель
модель выбросов
где ;ht и ;vt - векторы шума. At называется матрицей переходов, а Bt - матрицей выбросов. Термины ;ht и ;vt означают скрытое смещение и смещение выходного сигнала соответственно. Модели перехода и выбросов определяют Марковскую модель первого порядка
с переходами и выбросами, заданными Гауссовыми распределениями
Эта (скрытая) ЛДС может быть представлена в виде сети убеждений на рис. 24.4, причем расширение на более высокие порядки интуитивно понятно. Можно также включить внешний ввод ot в каждый момент времени, который добавит Cot к среднему значению скрытой переменной и Dot к среднему значению наблюдения.
Ниже приведены явные выражения для распределений переходов и выбросов для случая, не зависящего от времени, с ;vt = 0, ;ht = 0. Каждая скрытая переменная представляет собой многомерный гауссовский распределенный вектор ht , с
который утверждает , что ht+1 имеет среднее значение , равное Aht , с гауссовыми флуктуациями , описываемыми ковариационной матрицей ;H . Аналогично,
описывает выходной сигнал vt со средним значением Bht и ковариацией ;V .
2 Эти модели также часто называют фильтрами Калмана. Здесь мы избегаем этой терминологии, поскольку слово "фильтр" относится к определенному виду логического вывода и может привести к путанице между алгоритмом фильтрации и самой моделью.
442 ЧЕРНОВИК от 9 марта 2010 года Заключения \Логический Вывод
Рисунок 24.5: Одиночный фазор, изображенный в виде двух затухающих пространственных вращений ht+1 = ;R;ht с коэффициентом затухания 0 < ; < 1. При проекции на ось y фазор формирует затухающую синусоиду.
Пример 101. Рассмотрим динамическую систему, определенных на двух размерных векторах ht :
R; поворачивает вектор ht на угол ; за один временной интервал. В соответствии с этим LDS h будет отображать точки на окружности во времени. Используя скалярную проекцию ht, например,
элементы vt , t = 1, . . . , T описывают синусоиду во времени, см. рис.24.5. Используя диагональ блока R = blkdiag (R;1 , ... , R;m ) и, взяв скалярную проекцию расширенного m ; 2-мерного вектора h, можно построить представление сигнала в терминах m синусоидальных составляющих.
24.4 Вывод
Учитывая последовательность наблюдений v1:T, мы хотим рассмотреть фильтрацию и сглаживание, как мы это делали для HMM, раздел (23.2.1). Для HMM, при выводе различных рекурсий передачи сообщений, мы использовали только структуру независимости, закодированную сетью убеждений. Поскольку ЛСД имеет ту же структуру независимости, что и HMM, мы можем использовать те же предположения о независимости при выводе обновлений для ЛСД. Однако при их реализации нам нужно решить проблему, заключающуюся в том, что теперь мы имеем дело с непрерывными скрытыми переменными, а не с дискретными состояниями. Тот факт, что распределения являются Гауссовыми, означает, что мы можем точно обрабатывать непрерывные сообщения. При переводе уравнений передачи сообщений HMM мы сначала заменяем суммирование на интегрирование. Например, рекурсия фильтрации (23.2.7) становится
Поскольку произведение двух Гауссиан является другим Гауссианом, а интеграл от Гауссиана является другим Гауссианом, результирующее значение p (ht | v1: t ) также является Гауссианом. Это свойство Гауссианов замыкать означает, что мы можем представить p (ht;1 | v1:t;1 ) = N (ht;1 |ft;1 , Ft;1 ) со средним значением ft;1 и ковариацией Ft;1 . Действие уравнения (24.4.1) эквивалентно преобразованию среднего значения ft;1 и ковариации Ft;1 в среднее значение ft и ковариации Ft для p(ht |v1:t ). Наша задача, описанная ниже, состоит в том, чтобы найти явные алгебраические формулы для этих обновлений.
Численная стабильность
Перевод методов логического вывода при передаче сообщений, которые мы разработали для HMM, в LDS в значительной степени прост. Действительно, можно было бы просто запустить стандартный алгоритм суммирования (хотя и для непрерывных переменных), см. демонстрацию sumprodgausscanonlds.m. В длинных временных рядах могут возникать числовые нестабильности, которые могут привести к крайне неточным результатам, в зависимости от параметров перехода и распределения выбросов, а также метода обновления сообщений. По этой причине были разработаны специализированные процедуры \манипуляции, которые являются достаточно численно стабильными при определенных параметрических режимах[283]. Для HMM в разделе (23.2.1) мы обсудили два альтернативных метода сглаживания: параллельный ;-подход и последовательный ;-подход. ;-рекурсия подходит, когда значения ковариации излучения \выброса\ и перехода невелики, а ;-рекурсия обычно предпочтительнее в более стандартном случае малых значений ковариации.
ЧЕРНОВИК от 9 марта 2010 г. 443 вывода
Аналитические сокращения
При выводе рекурсий логического вывода нам необходимо часто умножать и интегрировать Гауссианы. Хотя в принципе это просто, это может быть утомительно с алгебраической точки зрения, и там, где это возможно, полезно прибегать к известным сокращениям. Например, можно использовать общий результат, заключающийся в том, что линейное преобразование Гауссовой случайной величины является другой Гауссовой случайной величиной. Аналогичным образом удобно использовать формулы обусловливания, а также интуицию изменения динамики. Эти результаты изложены в разделе (8.6), и ниже мы приводим наиболее полезные из них для наших целей.
Рассмотрим линейное преобразование Гауссовой случайной величины:
где предполагается, что x и ; генерируются в результате независимых процессов. Чтобы найти распределение p(y), одним из подходов было бы записать это формально в виде
и вычисляем интеграл (заполняя квадрат). Однако, поскольку Гауссова переменная при линейном преобразовании является другой Гауссовой переменной, мы можем воспользоваться коротким путем и просто найти среднее значение и ковариацию преобразованной переменной. Ее среднее значение задается как
Чтобы найти ковариацию, рассмотрим смещение переменной h от ее среднего значения, которое мы запишем как
Ковариация, по определению, равна < ;h;hT >. Для y смещение равно
Так что ковариация равна
Поскольку звуки \ шумы \ ; и х предполагаются независимыми, <;;;xТ> = 0 мы имеем
24.4.1 Фильтрация
Мы представляем отфильтрованное распределение в виде Гауссова уравнения со средним значением ft и ковариацией Ft ,
Это называется представлением момента. Затем наша задача состоит в том, чтобы найти рекурсию для ft , Ft в терминах ft;1 , Ft;1 . Удобный подход состоит в том, чтобы сначала найти совместное распределение p(ht , vt | v1: t;1 ), а затем задать для vt условие нахождения распределения p(ht |v1:t ). Член p(ht , vt |v1:t;1 ) - это Гауссиан, статистику которого можно найти из соотношений
Используя вышеизложенное и предполагая неизменность во времени и нулевые смещения, мы легко находим
444 ПРЕДВАРИТЕЛЬНЫЙ от 9 марта 2010 г. Вывод
Алгоритм 20 ЛДС Прямой переход. Вычислите отфильтрованные значения p(ht |v1:t ) ; N (ft , футы ) для LDS с параметрами ;t = A, B, ;h , ;v , h, vt . Также возвращается логарифмическая вероятность L = log p(v1:T ).
{f1 , F1 , p1 } = LDSFORWARD(0, 0, v1 ; ;t ) .
F0 ; 0, f0 ; 0,
L ; log p1
для t ; 2, T do
{ft , Ft , pt } = LDSFORWARD(ft;1 , Ft;1 , vt ; ;)
L ; L + логарифмический
конец pt для
функции ldsforward(f , F, v; ;)
. Среднее значение p(ht , vt |v1:t;1 )
. Ковариация p(ht , vt |v1:t;1 )
. Найдите p(ht |v1:t ) с помощью условной функции:
. Вычислить p(vt |v1:t;1 )
возвращает конечную функцию f , F , p
Конец Функции
В приведенном выше примере, используя наше моментальное представление пересылаемых сообщений
Тогда, используя условие3, p(ht |vt , v1:t;1 ) будет иметь среднее значение
и ковариация
Записывая вышеизложенное явно, мы получаем среднее значение:
и ковариация
где
Процедура фильтрации представлена в алгоритме(20) с единственным обновлением в LDSforwardUpdate.m.
Можно записать обновление ковариации в виде
, где мы определяем матрицу коэффициента усиления Калмана
В алгоритме(??) мы приводим рекурсию в стандартной инженерной нотации. Смотрите также LDSsmooth.m. Ожидается, что итерация будет численно стабильной, когда ковариации шума малы.
3 p(x |y) - Гауссово значение со средним значением µx + ;xy ;;1 yy (y ; µy) и ковариацией ;xx ; ;xy ;yy ;yx .
ЧЕРНОВИК от 9 марта 2010 г. 445 Вывод
Симметризация обновлений
Потенциальная числовая проблема с обновлением ковариации (24.4.20) заключается в том, что это разница двух положительно определенных матриц. Если имеются числовые ошибки, то Ft может не быть положительно определенным или симметричным. Используя тождество Вудбери, определение (132), уравнение (24.4.18) можно записать более компактно в виде
Хотя это положительно полуопределенное значение, оно является дорогостоящим с числовой точки зрения, поскольку включает в себя две инверсии матрицы. Альтернативой является использование определения K, из которого мы можем записать
Следовательно, мы приходим к симметричному обновлению Джозефа[104].
Левая часть представляет собой сложение двух положительно определенных матриц, чтобы результирующее обновление для ковариации было более численно стабильным. Аналогичный метод можно использовать в обратном порядке, описанном ниже. Альтернативой является отказ от прямого использования ковариационных матриц и использование их квадратного корня в качестве параметра, вместо этого выводя обновления для них[226, 38].
24.4.2 Сглаживание: метод коррекции Рауха-Тунга-Штрибеля
Сглаженное заднее значение p (ht | v1:T ) обязательно является Гауссовым, поскольку оно является условной границей большего Гауссова. Представив апостериорное значение в виде гауссовой функции со средним значением gt и ковариацией Gt ,
мы можем сформировать рекурсию для gt и Gt следующим образом:
Член p(ht |v1:t , ht+1 ) может быть найден путем вычисления совместного распределения
который получается обычным способом путем нахождения его среднего значения и ковариации: член p(ht |v1:t ) является известным Гауссовым от фильтрации со средним значением ft и ковариационным значением Ft . Следовательно, совместное распределение p(ht , ht+1 |v1:t ) означает, что
и элементы ковариации
Чтобы найти p (ht | v1:t , ht + 1), мы можем использовать условные Гауссовы результаты, см. определение(78). Полезно использовать результат обращения системы, раздел (8.6.1), который интерпретирует p(ht |v1:t , ht+1) как эквивалентную линейную систему, движущуюся назад во времени:
446 ЧЕРНОВИК от 9 марта 2010 года Заключения
Алгоритм 21 выполняет обратный проход ЛДС. Вычисляет сглаженные значения p(ht |v1:T ). Для этого требуются отфильтрованные результаты из алгоритма(20).
GT ; FT , gT ; fT
для t ; T ; 1, 1 выполните
{gt , Gt } = LDSBACKWARD(gt+1 , Gt+1 , ft , Ft ; ;)
завершение
функции ldsbackward(g, G, f , F; ;)
. Статистика p(ht , ht+1 |v1:t )
. Изменение динамики p(ht |ht+1 , v1:t )
. Обратное распространение
возвращает
конечную функцию g0 , G0
и
при
Используя изменение \ обратимость \ динамики, уравнение (24.4.31) и предполагая, что ht + 1 распределено по Гауссу, тогда легко вычислить статистику p(ht |v1:T ). Среднее значение задается с помощью
и ковариация
Эта процедура называется сглаживанием по методу Рауха-Тунга-Штрибеля-Кальмана[231]. Это называется методом ‘коррекции’ поскольку он берет отфильтрованную оценку p(ht |v1:t ) и "корректирует" ее, чтобы сформировать сглаженную оценку p(ht |v1:T ). Процедура описана в алгоритме(21) и подробно описана в LDSbackwardUpdate.m. Смотрите также LDSsmooth.m.
Момент пересечения
Преимущество приведенной выше интерпретации изменения динамики заключается в том, что перекрестный момент (который необходим для обучения) сразу же получается из
24.4.3 Вероятность
Мы можем вычислить вероятность, используя разложение
в котором каждое условное значение p(vt |v1:t;1 ) является гауссовым в vt . Несложно показать, что член p(vt |v1:t;1 ) имеет среднее значение и ковариацию
Логарифмическая вероятность затем определяется по формуле
ПРОЕКТ от 9 марта 2010 г. 447 Примечания
24.4.4 Наиболее вероятное состояние
Поскольку модус \мода\ гауссовой функции равен ее среднему значению, нет разницы между наиболее вероятным задним состоянием сустава\ присоединения
и множеством \набором наиболее вероятных граничных состояний
Следовательно, наиболее вероятная последовательность скрытых состояний эквивалентна сглаженной последовательности средних значений.
24.4.5 Независимость от времени и уравнения Риккати
Как отфильтрованные рекурсии ковариации Ft, так и сглаженные рекурсии ковариации Gt не зависят от наблюдений v1:T, зависит только от параметров модели. Это общая характеристика линейных гауссовых систем. Обычно ковариационные рекурсии быстро сходятся к значениям, которые являются достаточно постоянными на протяжении всей динамики, с заметными различиями только на границах t = 1 и t = T . На практике ковариации часто не зависят от времени и аппроксимируются одной независимой от времени ковариацией. Это приближение значительно снижает требования к хранилищу. Сходящийся отфильтрованный F удовлетворяет рекурсии
что может быть связано с формой алгебраического уравнения Риккати. Метод решения этих уравнений заключается в том, чтобы задать ковариацию равной ;. При этом новая F находится с использованием правой части (24.4.43) и впоследствии рекурсивно обновляется. В качестве альтернативы, используя тождество Вудбери, сходящаяся ковариация удовлетворяет
, хотя эта форма менее удобна в численном отношении для формирования итерационного решателя для F, поскольку она требует двух матричных инверсий.
Пример 102 (Ньютоновский анализ траектории). В воздух запускается игрушечная ракета с неизвестной массой и начальной скоростью. Кроме того, неизвестны постоянные ускорения, создаваемые двигательной установкой ракеты. Известно лишь, что применяются законы Ньютона, и прибор может измерять вертикальную высоту и горизонтальное расстояние ракеты в каждый момент времени x(t), y(t) от начала координат. Основываясь на зашумленных измерениях x(t) и y(t), наша задача состоит в том, чтобы определить положение ракеты в каждый момент времени.
Хотя это, возможно, наиболее целесообразно рассматривать с точки зрения динамики непрерывного времени, мы будем переведем это в приближение к дискретному времени. Закон Ньютона гласит, что
где m - масса объекта, а fx (t), fy (t) - горизонтальная и вертикальная силы соответственно. Следовательно в их нынешнем виде эти уравнения не имеют формы, непосредственно пригодной для использования в рамках ЛДС. Наивный подход заключается в перепараметризации времени для использования переменной t таким образом, чтобы t ; ~t;, где t - целое число, а ; - единица времени. Таким образом, динамика равна
ПРОЕКТ от 9 марта 2010 г. 448 "Изучение линейных динамических систем"
Рисунок 24.6: Оценка траектории Ньютоновского баллистического объекта на основе наблюдений за помехами (маленькие кружки). Все временные метки известны, но на графике они опущены. Точки ‘x’ - это истинные положения объекта, а крестики "+" - это расчетные сглаженные средние положения <xt , yt |v1: t> объекта, нанесенные на график через каждые несколько временных шагов. Смотрите demoLDStracking.m
, где y`(t) ; dy/dt . Мы можем написать уравнение обновление для x` и y`,
Это уравнения дискретной разности во времени, индексируемые как ~t. Прибор, который измеряет x(t) и y(t), не совсем точен. Для простоты мы обозначим ax (t) = fx (t)/m(t), ay (t) = fy (t)/m(t) – эти ускорения будут предполагаться примерно постоянными, но неизвестными :
где ;x и ;y - малые шумовые коэффициенты. Начальные распределения ускорений предполагаются неопределенными, используется нулевое среднее значение по Гауссу с большой дисперсией.
Мы описываем приведенную выше модель, рассматривая x(t), x` (t), y(t), y` (t), ax (t), ay (t) в качестве скрытых переменных, что приводит к H = 6-мерной LDS с матрицами переходов и выбросов, как показано ниже:
Мы придаем большое значение их начальным значениям и пытаемся определить неизвестную траекторию. Демонстрация приведена на рис. 24.6. Несмотря на значительные помехи при наблюдении, траектория объекта может быть точно определена.
24.5 Обучение Линейных Динамических Систем ЛДС\ LDS
Хотя во многих приложениях, в частности, для описания известных физических процессов, параметры LDS известны, во многих задачах машинного обучения нам необходимо изучать параметры LDS на основе v1:T . Для простоты предположим, что мы знаем размерность H LDS.
24.5.1 Проблемы с идентификацией \Выводы способности идентифицировать
Интересный вопрос заключается в том, можем ли мы однозначно идентифицировать (обучить) параметры LDS. В решении, полученном путем произвольной перестановки скрытых переменных, всегда присутствуют тривиальные избыточности, переворачивая их знаки. Чтобы показать, что потенциально существует гораздо больше эквивалентных решений, рассмотрим следующие LDS
ЧЕРНОВИК от 9 марта 2010 г. 449 Обучение линейным динамическим системам
Теперь мы попытаемся преобразовать эту исходную систему в новую форму, которая будет выдавать точно такие же результаты, как и v1:T. Для обратимой матрицы R мы рассмотрим
, которая может быть представлена как новая скрытая динамика
где ; ; RАR;1 , ;t ; Rht, ^; ht ; R; h t. Кроме того, мы можем снова выразить выходы, которые будут функцией преобразованного значения h:
Следовательно, при условии, что мы не накладываем никаких ограничений на A, B и ;H, существует бесконечное пространство эквивалентных решений, ; = RA R;1 , ^B = BR;1 , ^;H = R;H RT , все с одинаковым значением вероятности. Это означает, что непосредственная интерпретация полученных параметров должна выполняться с некоторой осторожностью. Эту избыточность можно уменьшить, наложив ограничения на параметры.
24.5.2 Алгоритм EM
Для простоты мы предполагаем, что у нас есть единственная последовательность v1:T, к которой мы хотим подогнать LDS, используя Максимум Вероятности. Поскольку LDS содержит скрытые переменные, одним из подходов является использование алгоритма EM. Как обычно, на M-м шаге алгоритма EM требуется, чтобы мы максимально увеличили количество энергии
относительно параметров A, B, a, ;, ;V , ;H . Благодаря форме LDS энергия разлагается
как
Несложно получить в лоб, что M-шаг для параметров задается через (угловые скобки <·> обозначают математическое ожидание относительно сглаженного заднего значения p(h1:T |v1:T )):
Если B будет изменено в соответствии с приведенным выше, первое уравнение может быть упрощено до
Аналогично, если A обновляется в соответствии с алгоритмом EM, то второе уравнение может быть упрощено до
450 ПРОЕКТ от 9 марта 2010 г. "Изучение линейных динамических систем"
Таким образом, требуемая статистика включает сглаженные средние значения, ковариации и перекрестные моменты. Возможность изучения нескольких временных рядов проста, поскольку энергия просто суммируется по отдельным последовательностям.
Эффективность алгоритма EM для LDS часто сильно зависит от инициализации. Если мы уберем скрытые связи, модель будет тесно связана с Факторным Анализом (LDS можно рассматривать как временное расширение Факторного Анализа). Таким образом, одним из методов инициализации является изучение матрицы B с использованием Факторного Анализа, рассматривая наблюдения как независимые во времени.
24.5.3 Методы подпространства
Альтернативой EM и обучению LDS с Максимальным Правдоподобием является использование метода подпространства[281, 249]. Главное преимущество этих методов в том, что они позволяют избежать трудностей с конвергенцией, присущих EM. Чтобы обосновать методы подпространства, рассмотрим детерминированную LDS
В соответствии с этим предположением, vt = Bht = BAht;1 и, в более общем плане, vt = BAt h1 . Это означает, что система с низкой размерностью лежит в основе всей видимой информации, поскольку все точки в точке At h1 лежат в H-мерном подпространстве, которое затем проецируется для формирования наблюдения. Это предполагает, что некоторая форма метода идентификации подпространства позволит нам изучить A и B.
Учитывая набор векторов наблюдений v1 , . . . , vt , рассмотрим блочную матрицу Ханкеля, сформированную из суммирования векторов. Для матрицы порядка L это матрица Vl ; T ; L + 1. Например, для T = 6 и L = 3 это
Если v генерируются из LDS (без помех\ без шума), мы можем записать
Теперь мы находим SVD для M,
где W называется расширенной матрицей наблюдаемости. Матрица ^S будет содержать сингулярные значения вплоть до размерности скрытых переменных H, а остальные сингулярные значения будут равны 0. Из уравнения (24.5.17) это означает, что матрица выбросов B содержится в ^U1:V,1:H . Оцененные скрытые переменные затем содержатся в подматрице W1:H,1:T ;L+1 ,
Основываясь на соотношении ht = Aht;1, можно затем найти наилучшую оценку по методу наименьших квадратов для A, минимизировав
, для которого оптимальным решением является
где † обозначает псевдоинверсию, см. LDSsubspace.m. Оценки для ковариационных матриц также могут быть получены из остаточных ошибок при подгонке блочной матрицы Ханкеля (;V ) и расширенной матрицы наблюдаемости (;H ). Хотя этот вывод формально справедлив только для случая отсутствия шума, тем не менее, можно применить его в случае ненулевого шума и надеяться получить оценку для A и B, которая будет правильной в среднем значении. В дополнение к самостоятельному формированию решения, метод подпространства представляет собой потенциально полезный способ инициализации алгоритма EM.
ПРОЕКТ от 9 марта 2010 г. 451 Переключение авторегрессионных моделей
Рисунок 24.7: Модель AR с переключением первого порядка. С точки зрения логического вывода, основанного на v1:T, это HMM.
24.5.4 Структурированная LDSs
Многие физические уравнения являются локальными как во времени, так и в пространстве. Например, в моделях погоды атмосфера разделена на ячейки hi (t), каждая из которых содержит давление в данном месте. Уравнения, описывающие изменение давления, зависят только от давления в текущей ячейке и небольшом количестве соседних ячеек в предыдущий момент времени t ; 1. Если мы используем линейную модель и измеряем некоторые аспекты ячеек в каждой из них время, то погода может быть описана с помощью LDS с высокоструктурированной матрицей разреженных переходов A. На практике погодные модели нелинейны, но часто используются локальные линейные приближения[254]. Аналогичная ситуация возникает при визуализации мозга, при которой вокселы (локальные кубики активности) зависят только от своих соседей по предыдущему временному интервалу[101].
Еще одно применение структурированной LDSs заключается в анализе независимых от времени компонентов. Это определяется как обнаружение набора независимых скрытых динамических процессов, из которых проецируются наблюдаемые данные. Если каждый независимый динамический процесс сам по себе может быть описан с помощью LDS, это приводит к структурированной LDS с блочной диагональной матрицей переходов A. Такие модели могут использоваться для выделения независимых компонентов при предварительном знании вероятных базовых частот в каждом из временных компонентов[59]. Смотрите также упражнение(199).
24.5.5 Байесовский LDS
Распространение на определение приоритетных параметров перехода и излучения LDS в целом приводит к вычислительным трудностям при вычислении вероятности. Например, для предшествующего значения A вероятность равна p(v1:T ) = ;A p(v1:T |A)p(A), который трудно оценить, поскольку зависимость вероятности от матрицы A является сложной функцией. Приблизительное рассмотрение этого случая выходит за рамки данной книги, хотя мы кратко отметим, что в этом контексте популярны методы выборки [54, 98] в дополнение к детерминированным вариационным приближениям [27, 23, 59].
24.6 Переключение АвтоРегрессионных Моделей
Для временного ряда скалярных значений v1:T модель переключения AR L-го порядка может быть записана как
где теперь у нас есть набор коэффициентов AR ; = {a(s), ;2 (s), s ; {1, . . . , S}} . Сами дискретные переменные переключения имеют Mарковский переход p(s1:T ) = ;tp(st |st;1 ), так что полная модель имеет вид
24.6.1 Вывод
Учитывая наблюдаемую последовательность v1:T и параметры ;, вывод прост, поскольку это форма HMM. Чтобы сделать это более очевидным, мы можем написать
, где
452 ЧЕРНОВИК от 9 марта 2010 г. Примеры переключателей авторегрессивных моделей
обученные \выборки\ переключатели
Рисунок 24.8: Обучение Переключающейся Модели AR. На верхнем графике показаны данные для обучения \тренировок. Цвет указывает, какая из двух моделей дополненной реальности активна в данный момент. Хотя эта информация приведена здесь, предполагается, что алгоритму обучения она неизвестна, как и коэффициенты a(s). Однако мы предполагаем, что порядок L = 2 и количество переключателей S = 2 известны. На нижнем графике показана временная серия снова после тренировки, в ходе которой мы окрашиваем точки в соответствии с наиболее вероятной сглаженной моделью AR на каждом временном шаге. Смотрите демонстрацию demoSARlearn.m.
Обратите внимание, что распределение излучения \ выбросов ^p(vt |st ) зависит от времени. Тогда рекурсия фильтрации равна
Сглаживание может быть достигнуто с помощью стандартных рекурсий, модифицированных для использования зависящих от времени выбросов, см. Демонстрационный вывод demoSARinference.m .
24.6.2 Обучение с Максимальной Вероятностью с использованием ЕМ
Чтобы соответствовать набору коэффициентов AR и инновационных отклонений, a(s), ;2 (s), s = 1, . . . , S, используя Максимальное значение Вероятности после обучения для набора данных v1:T мы можем использовать алгоритм EM.
M-шаг
С точностью до пренебрежимо малых констант энергия определяется как
, которое нам нужно максимизировать по отношению к параметрам ;. Используя определение выбросов и изолируя зависимость от a, мы имеем
При дифференцировании относительно a(s) и приравнивании к нулю оптимальное значение a(s) удовлетворяет линейному уравнению
, которая может быть решена с помощью исключения по Гауссу. Аналогичным образом можно показать, что обновления, которые максимизируют энергию относительно ;2
Обновление для p(st |st;1 ) выполняется в соответствии со стандартным правилом EM для HMM, уравнением (23.3.5), см. SARlearn.m. Здесь мы не включаем обновление для предыдущего p(s1 ), поскольку в начале последовательности недостаточно информации, и предполагаем, что p(s1) является плоским. При использовании высокочастотных данных маловероятно, что изменение в переключателе переменная является допустимой в каждый момент времени t. Простым ограничением для учета этого является использование модифицированного перехода
в противном случае
ПРОЕКТ от 9 марта 2010 г. Код 453
Рисунок 24.9: (а): Модель AR с скрытым переключением (второго порядка). Здесь st указывает, какая из 10 доступных моделей AR активна в момент времени t. Квадратные узлы подчеркивают, что это дискретные переменные. То ‘чистый" сигнал AR vt, который не наблюдается, искажается дополнительным шумом, образуя зашумленные наблюдения ~vt. В терминах вывода, обусловленного ~v1:T , это может быть выражено как переключение LDS, см. главу(25). (б): Реконструкция сигнала с использованием модели скрытого переключения AR в (а). Вверху: зашумленный сигнал ~v1:T; внизу: реконструированный чистый сигнал v1:T. Пунктирные линии и цифры показывают наиболее вероятный параметр сегментации состояний arg maxs1:Tp(s1:T |~v1:T ).
Электронный \ E- \ шаг
Для M-шага требуется сглаженная статистика pold (st = s|v1:T ) и pold (st = s, st-1 = s`|v1:T ), которая может быть получено на основе логического вывода HMM.
Пример 103 (Обучение переключающейся AR-модели). На рис.24.8 обучающие данные генерируются Переключающейся AR-моделью, так что мы точно знаем, какая модель сгенерировала какие части данных. На основе обучающих данных (при условии, что метки st неизвестны) с помощью EM подбирается модель коммутации AR. В этом случае задача проста, так что можно получить хорошую оценку обоих наборов параметров AR и какие переключатели были использованы в данный момент.
Пример 104 (Моделирование частей речи). На рисунке (24.9) показан фрагмент речевого сигнала, описанный с помощью переключаемой AR-модели. Каждая из 10 доступных AR-моделей отвечает за моделирование динамики базовой части речи [90][192]. Модель была обучена на множестве примеров последовательностей, используя S = 10 состояний с матрицей перехода слева направо. Интерес состоит в том, чтобы определить, когда каждая субъединица с наибольшей вероятностью будет активна. Это соответствует вычислению наиболее вероятного пути переключения s1:T с учетом наблюдаемого сигнала p(s1:T |~v1:T ).
24.7 Код
В приведенном ниже коде Линейной Динамической Системы приведена только простейшая форма рекурсий. Не предпринималось никаких попыток обеспечить численную стабильность.
LDSforwardUpdate.m: Прямая трансляция \ прогон ЛДС
LDSbackwardUpdate.m: обратная трансляция \ прогон ЛДС
LDSsmooth.m: Линейная Динамическая Система: фильтрация и сглаживание
LDSforward.m: Альтернативный прямой алгоритм LDS (см. главу SLDS)
LDSbackward.m: Альтернативный обратный алгоритм LDS (см. главу SLDS)
Демонстрация demosumprodgausscanonlds.m: Алгоритм суммирования для сглаживания логического вывода
demoLDStracking.m: Демонстрация отслеживания в Ньютоновской системе
454 ЧЕРНОВИК упражнений от 9 марта 2010 года
LDSsubspace.m: Обучение подпространства (метод матрицы Ханкеля)
demoLDSsubspace.m: Демонстрация метода обучения подпространства
24.7.1 Модели авторегрессии
Обратите внимание, что в коде вектор авторегрессии a имеет в качестве последней записи первый коэффициент AR (т.е. в порядке, обратном порядку, представленному в тексте).
ARtrain.m: Обучение коэффициентов AR (исключение по Гауссу).
demoARtrain.m: Демонстрация адаптации AR-модели к данным
ARlds.m: Обучение коэффициентов AR с использованием демонстрации LDS
demoARlds.m: Демонстрация обучения коэффициентов AR с использованием демонстрации LDS
demoSARinference.m: Демонстрация для вывода в модели авторегрессии с переключением
В SARlearn.m используется небольшая подтасовка, так как мы не рассматриваем полностью случай с самого начала, когда есть недостаточно информации для определения модели AR. Для длинных временных рядов это будет иметь незначительный эффект, хотя может привести к небольшому снижению логарифмической вероятности в соответствии с алгоритмом EM.
SARlearn.m: Обучение SAR с использованием демонстрации EM
demoSARlearn.m: Демонстрация процесса обучения SAR
HMMforwardSAR.m: Переключение авторегрессионного прямого перехода HMM
HMMbackwardSAR.m: Переключение авторегрессии на обратный переход
24.8 Упражнения
Упражнение 234. Рассмотрим двумерную линейную модель
где
R; - это матрица вращения, которая поворачивает вектор ht на угол ; за один временной интервал.
1. Записав
исключите yt, чтобы записать уравнение для xt + 1 в терминах xt и xt;1 .
2. Объясните, почему собственные значения матрицы вращения (в общем случае) являются мнимыми.
3. Объясните, как смоделировать синусоиду, вращающуюся с угловой скоростью ;, используя двумерную модель LDS.
4. Объясните, как смоделировать синусоиду, используя модель AR.
5. Объясните взаимосвязь между дифференциальным уравнением второго порядка ; = ;;x, которое описывает Гармонический Генератор и разностное уравнение второго порядка, аппроксимирующее это дифференциальное уравнение. Возможно ли найти разностное уравнение, которое точно соответствует решению дифференциального уравнения в выбранных точках?
Упражнение 235. Покажите, что для любой антисимметричной матрицы M,
экспоненциальная матрица (в MATLAB это expm)
ЧЕРНОВИК от 9 марта 2010 г. 455 Упражнения
ортогональна, а именно
Объясните, как затем можно построить случайные ортогональные матрицы с некоторым контролем над углами комплексных собственных значений. Обсудите, как это соотносится с частотами, встречающимися в LDS, где A — матрица перехода.
Упражнение 236. Запустите демонстрационную программу demoLDStracking.m, которая отслеживает баллистический объект с помощью линейной динамической системы, см. пример(102). Измените demoLDStracking.m таким образом, чтобы в дополнение к позициям x и y также учитывалась скорость x. Сравните точность отслеживания с учетом этой дополнительной информации и без нее.
Упражнение 237. nightsong.mat содержит небольшой стереофонический фрагмент песни соловья, записанный на частоте 44100 Гц.
1. Постройте исходную форму сигнала, используя plot(x(:,1))
2. Загрузите программу myspecgram.m с сайта labrosa.ee.columbia.edu/matlab/sgram/myspecgram.m и постройте спектрограмму
y=myspecgram(x,1024,44100); imagesc(log(abs(y)))
3. Процедура demoGMMem.m демонстрирует подгонку смеси гауссиан к данным. Вероятности комбинированного распределения содержатся в phgn. Напишите процедуру для кластеризации данных demo v=log(abs(y)), используя 8 Гауссовых компонент, и объясните, как можно разделить ряд x на разные области.
4. Изучите стандартный demoARlds.m, который соответствует коэффициентам авторегрессии, используя интерпретацию в виде линейной динамической системы. Адаптируйте стандартный demoARlds.m для обучения коэффициентов AR в данные x. Вам почти наверняка потребуется выполнить подвыборку данных x – например, взяв каждую четвертую точку данных. Используя полученные коэффициенты AR (используйте сглаженные результаты), составьте Гауссову смесь из 8 компонентов. Сравните и сопоставьте свои результаты с результатами, полученными с помощью модели Гауссовой смеси, соответствующей спектрограмме.
Упражнение 238. Рассмотрим учебную задачу с контролем, в которой мы строим линейную модель выходного сигнала yt масштабирующего устройства на основе векторного входного сигнала xt :
где ;yt - нулевой средний гауссовский шум. Доступны обучающие данные D = {(xt , yt ), t = 1, . . . , T }.
1. Для не зависящего от времени весового вектора wt ; w объясните, как найти единичный весовой вектор w и дисперсию шума ;2 по Максимальному Правдоподобию.
2. Расширьте приведенную выше модель, включив в нее переход
где ;wt - нулевой средний гауссовский шум с заданной ковариацией ;; w1 имеет нулевое среднее значение. Объясните, как преобразовать нахождение <wt |D> в сглаживание в соответствующей линейной динамической системе. Напишите процедуру W = LinPredAR(X,Y,SigmaW,sigmaY), который принимает матрицу входных данных X = [x1 , . . . , xT ], где каждый столбец содержит входные данные и вектор Y = [y1 , . . . , yT ]T ; SigmaW - это аддитивный весовой шум, а SigmaY - предполагаемый известный выходной шум, не зависящий от времени. Возвращаемое значение W содержит сглаженные средние значения.
456 ЧЕРНОВИК от 9 марта 2010 года
Главa 25
Переключение линейных динамических систем
25.1 Вступление
Сложные временные ряды, которые плохо поддаются глобальному описанию с помощью единой Линейной Динамической Системы, могут быть разделены на сегменты, каждый из которых моделируется потенциально разными LDS. Такие модели могут обрабатывать ситуации, в которых базовая модель "перескакивает" с одной настройки параметра на другую. Например, один LDS вполне может представлять нормальные потоки на химическом заводе. Когда происходит обрыв трубопровода, динамика системы меняется от одного набора линейных уравнений потока к другому. Этот сценарий можно смоделировать, используя наборы из двух линейных систем, каждая из которых имеет разные параметры. Дискретная скрытая переменная в каждый момент времени st ; {нормальная, неработоспособная \ normal, pipe broken} указывает, какой из LDS является наиболее подходящим в текущий момент времени. Это называется переключающим LDS и используется во многих дисциплинах, от эконометрики до машинного обучения [13, 110, 174, 161, 160, 60, 57, 218, 303, 175].
25.2 Переключающиеся СПД \ ЛДС
В каждый момент времени t переменная переключения st ; 1, . . . , S описывает, какой из набора LDS должен использоваться. Наблюдаемая (или "видимая") переменная vt ; RV линейно связана со скрытым состоянием ht ; RH посредством
Здесь st описывает, какая из множества матриц излучения B(1), ... , B(S) активна в момент времени t. Наблюдаемый шум ;v (st ) вычисляется по гауссу со средним значением ;v(st ) и ковариацией ;v (st ). Динамика перехода в непрерывное скрытое состояние ht является линейной,
и переключающая переменная st выбирает единственную матрицу перехода из доступного набора A(1), . . . , A(S). То Гауссовский переходный шум ;h (st ) также зависит от переменной switch st. Динамика st сама по себе является Марковской, с переходом p(st |st;1 ). В более общей "расширенной" модели ASLD переключатель st зависит как от предыдущего st;1, так и от ht;1. Модель определяет совместное распределение (см. рис.25.1).
при
457Гауссова суммарная фильтрация
Рисунок 25.1: Структура независимости доменных имен. Квадратные узлы st обозначают дискретные переменные переключения; ht - непрерывные скрытые переменные, а vt - непрерывные наблюдаемые переменные. Дискретное состояние st определяет, какая линейная динамическая система из конечного набора линейных Динамических систем работает в момент времени t. В SLDS ссылки от h до s обычно не рассматриваются.
В момент времени t = 1 p(s1 |h0 , s0 ) обозначает предыдущее значение p(s1 ), а p(h1 |h0 , s1 ) обозначает значение p(h1 |s1 ).
SLDS можно рассматривать как сочетание скрытой Марковской модели и Линейной Динамической Системы \LDS. SLDS также называют Cкачкообразной Марковской моделью/процессом \ JM, переключающим Фильтром Калмана \KF, Переключающей Линейной Гауссовой Моделью Пространства Состояний \SLDGSS, Условной Линейной Гауссовой Моделью \CLGM.
25.2.1 Точный логический вывод является трудноразрешимым с точки зрения вычислений
Как точный отфильтрованный, так и сглаженный логический вывод в SLDS является трудноразрешимым, масштабируясь экспоненциально со временем. Как в качестве неофициального объяснения рассмотрим отфильтрованный апостериорный вывод, для которого, по аналогии с уравнением (23.2.9), прямой проход равен
На временном шаге 1, p(s1 , h1 |v1 ) = p(h1 | s1 , v1 )p (s1 | v1 ) - это индексированный набор Гауссиан. На временном шаге 2 из-за суммирования по состояниям s1 , p(s2 , h2 |v1:2 ) будет индексированным набором S Гауссиан; аналогично на временном шаге 3, это будет S2 и, в общем случае, приведет к S t;1 Гауссианам в момент времени t. Даже при малом t число поэтому компоненты, необходимые для точного представления отфильтрованного распределения, являются трудноразрешимыми с точки зрения вычислений. Аналогично, сглаживание также является трудноразрешимым. Причина трудноразрешимости SLDS отличается от "структурной трудноразрешимости", с которой мы сталкивались ранее. В SLDS, в терминах кластерных переменных x1:T , с xt ; (st , ht ) и видимыми переменными v1:T , график распределения является односвязным. Таким образом, с чисто теоретической точки зрения графов можно было бы предвидеть небольшие трудности в проведении логического вывода. Действительно, как мы видели выше, вывод алгоритма фильтрации прост, поскольку граф является односвязным. Однако численная реализация алгоритма является трудноразрешимой, поскольку для описания сообщений требуется экспоненциально увеличивающееся число терминов.
Чтобы справиться с этой трудноразрешимой задачей, было введено несколько схем аппроксимации [98, 110, 174, 161, 160]. Здесь мы сосредоточимся на методах, которые аппроксимируют условные значения switch st, используя ограниченную смесь Гауссиан. Поскольку точные апостериорные распределения представляют собой смеси Гауссиан, хотя при экспоненциально большом количестве компонентов цель состоит в том, чтобы исключить компоненты с малым весом таким образом, чтобы результирующая аппроксимация точно отражала апостериорное значение.
25.3 Фильтрация по Гауссовой Сумме
Уравнение (25.2.4) описывает точную рекурсию фильтрации с экспоненциально увеличивающимся со временем числом компонентов. В целом, влияние древних наблюдений будет гораздо менее значимым, чем влияние недавних наблюдений. Это говорит о том, что "время действия" ограничено и что, следовательно, соответствующий ограниченного числа компонентов в Гауссовой смеси должно быть достаточно для точного представления отфильтрованной апостериорной части[6].
Наша цель - сформировать рекурсию для p (st , ht | v1: t ), основанную на приближении Гауссовой смеси p (ht | st , v1: t). Учитывая приближение отфильтрованного распределения p(st , ht |v1:t ) ; q(st , ht |v1:t), точное уравнение рекурсии (25.2.4) аппроксимируется формулой
458 черновик от 9 марта 2010 г. Фильтрация по сумме по Гауссу
Это приближение к отфильтрованному заднему значению \постериору на следующем временном шаге будет содержать в S раз больше компонентов, чем на предыдущем временном шаге, и, чтобы предотвратить экспоненциальный рост компонентов смеси, нам нужно будет впоследствии сжать смесь q(st+1, ht+1 |v1:t+1) подходящим образом. Мы разберемся с этой проблемой после вычисления q(st+1 , ht+1 |v1:t+1 ).
Для получения обновлений полезно разбить новое отфильтрованное приближение из уравнения (25.2.4) на непрерывную и дискретную части:
и вывести отдельные отфильтрованные формулы обновления, как описано ниже.
25.3.1 Непрерывная фильтрация
Точное представление p(ht |st , v1:t ) представляет собой смесь из O(st;1) компонентов. Поэтому, чтобы сохранить вычислительную выполнимость, мы аппроксимируем это с помощью ограниченной смеси I-компонентов
где q(ht | it , st , v1:t ) - это Гауссово значение, параметризованное средним значением f (it , st ) и ковариацией F(it , st ). Строго говоря, мы должны использовать обозначение ft (it , st ), поскольку для каждого момента времени t у нас есть набор средних значений, индексируемых it , st , хотя мы не используем эти зависимости в используемых здесь обозначениях.
Важным замечанием является то, что многие методы приближают p(ht | st , v1:t ), используя один Гауссиан. Естественно, это приводит к смешению Гауссианов для p(ht | v1: t ) =; st p(ht |st , v1:t )p(st |v1:t ). Однако при выполнении единственного Гауссовского приближения к p (ht | st , v1: t ) представление апостериорного значения может быть плохим. Наша цель здесь - сохранить точное приближение к p (ht | st , v1: t ), используя смесь Гауссиан.
Чтобы найти рекурсию для аппроксимирующего распределения, мы сначала предполагаем, что нам известно отфильтрованное приближение q(ht , st |v1:t), а затем распространяем его, используя точную динамику. Для этого сначала рассмотрим соотношение
Везде, где это возможно, мы теперь подставляем точную динамику и оцениваем каждый из двух вышеперечисленных факторов. Полезность декомпозиции обновления таким образом заключается в том, что новое отфильтрованное приближение имеет вид смесь по Гауссу, где q(ht + 1 |st , it , st + 1 , v1: t + 1 ) - это Гауссова смесь, а q (st , it |st +1 , v1:t+1 ) - это веса или пропорции смешивания компонентов. Ниже мы опишем, как вычислить эти слагаемые в явном виде. Уравнение (25.3.4) создает новую Гауссову смесь с I ; S компонентами, которую мы свернем обратно к I компонентам в конце вычисления.
Вычисляя q(ht + 1 |st , it , st + 1 , v1: t + 1 )
Мы стремимся найти рекурсию фильтрации для q(ht + 1 |st , it , st + 1 , v1: t + 1 ). Поскольку это зависит от состояний переключения и компонентов, это соответствует единственному этапу продвижения LDS, который можно оценить, рассмотрев сначала совместное распределение
и последующее кондиционирование на vt+1. В приведенном выше примере мы использовали точную динамику, где это было возможно. Уравнение(25.3.5) утверждает, что мы знаем отфильтрованную информацию до момента времени t, в дополнение к знанию состояний переключателя st , st+1
ЧЕРНОВИК от 9 марта 2010 г. Фильтрация по сумме по Гауссу 459
и индексируйте его по компоненту смеси it. Чтобы облегчить задачу с обозначениями, мы получаем это для ;ht , ;vt ; 0 для всех t. Точная динамика движения вперед тогда задается как
Учитывая индекс компонента смеси it,
мы распространяем эту гауссову функцию с помощью точного уравнения динамики (25.3.6). Тогда q(ht + 1 |st , it , st + 1 , v1: t + 1 ) является Гауссовой функцией с ковариационными и средними элементами
Эти результаты получены путем интегрирования уравнений прямой динамики (25.2.1,25.2.2) по ht, используя результаты, приведенные в разделе (8.6.3).
Чтобы найти q(ht + 1 |st , it , st + 1 , v1: t + 1 ) , мы определяем q(ht + 1 |st , it , st + 1 , v1: t + 1 ) на vt+ 1, используя стандартные Гауссовы формулы кондиционирования, см. определение(78), для получения
при
где требуемые количества определены в уравнении (25.3.8).
Вычисляем весa смеси q(st , it | st + 1 , v1: t + 1 ).
С точностью до константы нормализации массу смеси в уравнении (25.3.4) можно найти из
Первый множитель в уравнении (25.3.11), q(ht + 1 |st , it , st + 1 , v1: t + 1 ) является Гауссовым со средним значением µv и ковариацией ;vv , как указано в уравнении (25.3.8). Последние два множителя q(it | st , v1: t ) и q(st | v1: t ) получены из предыдущей отфильтрованной итерации. Наконец, q(st+1 | it , st , v1: t ) определяется из
расширенные SLDS
стандартные SLDS
, где приведенный выше результат для стандартных SLDS следует из допущений о независимости, присутствующих в стандартных SLDS. В ASLD член в уравнении (25.3.12), как правило, необходимо вычислять численно. Простым приближением является вычисление уравнения (25.3.12) по среднему значению распределения q(ht | it , st , v1: t ) . Чтобы учесть информацию о ковариации, альтернативой может быть получение выборок из гауссовой функции q(ht | it , st , v1: t ) и, таким образом, аппроксимация среднего значения q(st | ht , st ) путем выборки. Обратите внимание, что это не приравнивает фильтрацию по гауссовой сумме к процедуре последовательной выборки, такой как фильтрация по частицам, раздел (27.6.2). Выборка здесь точная, и проблем со сходимостью не возникает.
Завершение рекурсии
Теперь мы в состоянии вычислить уравнение (25.3.4). Для каждого значения переменной st+1 у нас есть смесь I ; S Гауссиан. Чтобы предотвратить экспоненциальное увеличение числа компонентов со временем, мы численно сворачиваем q(ht + 1 | st + 1 , v1: t + 1 ) обратно в I Гауссиан, чтобы сформировать
Для получения смеси меньшего размера можно использовать любой выбранный метод. Простой подход в лоб заключается в многократном смешивании компонентов с малым весом, как описано в разделе (25.3.4). Таким образом, определяются новые коэффициенты смеси q( it+1 | st + 1, v1: t +1 ) , it+1 ; 1, . . . , I. На этом завершается описание того, как сформировать рекурсию для непрерывного отфильтрованного апостериорного приближения q(ht +1 | st , v1: t +1 ) в уравнении (25.3.2).
460 ЧЕРНОВИК от 9 марта 2010 г. Фильтрация суммы по Гауссу
Рисунок 25.2: Фильтрация по Гауссовой Сумме. В крайнем левом столбце показано предыдущее приближение гауссовой смеси q(ht | it , v1: t ) для двух состояний S = 2 (красное и синее) и трех компонентов смеси I = 3, где вес смеси представлен площадью каждого овала. Существует S = 2 различных линейных системы, которые переводят каждый из компонентов смеси в новое отфильтрованное состояние, при этом цвет стрелки указывает, какая динамическая система используется. После одного временного шага каждый компонент смеси разделяется на дополнительные S компонентов, так что совместное приближение q(ht +1 | st +1 , v1: t +1 ) содержит S 2 I компонентов (средний столбец). Чтобы сохранить представление вычисляемая смесь гауссианов для каждого состояния st + 1 сводится обратно к I компонентам. Это означает, что каждое окрашенное состояние должно быть аппроксимировано меньшей I компонентной смесью гауссианов. Есть много способов добиться этого. Наивный, но эффективный с точки зрения вычислений подход заключается в том, чтобы просто игнорировать компоненты с наименьшим весом, как показано в правой колонке, см. mix2mix.m.
25.3.2 Дискретная фильтрация
Рекурсия для распределения переменной switch st в уравнении (25.3.2) имеет вид
Скорость вращения приведенного выше уравнения пропорциональна
для которого все члены были вычислены во время рекурсии для q(ht +1 | st +1 , v1: t +1 ) . Теперь у нас есть все величины, необходимые для вычисления аппроксимации суммы Гаусса для прямого прохождения фильтрации. Схематическое представление фильтрации по сумме Гаусса приведено на рис. (25.2), а псевдокод представлен в алгоритме(22). Смотрите также SLDSforward.m.
25.3.3 Вероятность p(v1:T )
Вероятность p(v1:T ) может быть найдена из
где
В приведенном выше выражении все члены были вычислены при формировании рекурсии для отфильтрованного апостериорного значения q(ht +1 | st +1 , v1: t +1 ) .
25.3.4 Свертывающиеся гауссианы
Задана смесь из N гауссианов
мы хотим свести это к меньшей K < N смеси гауссиан. Мы описываем простой метод, преимущество которого заключается в вычислительной эффективности, но недостаток заключается в отсутствии пространственной информации о
ЧЕРНОВИК от 9 марта 2010 г. 461 Сглаживание суммы по Гауссу
Алгоритм 22 Прямого прохождения aSLDS . Аппроксимирует отфильтрованное апостериорное значение p(st |v1:t ) ; at , p(ht |st , v1:t ) ;wt (it , st )N (ht ft (it , st ), Ft (it , st )). Также возвращает приблизительное логарифмическое значение вероятности L ; log p(v1:T ). Это число компонентов в каждом приближении гауссовой смеси. Нам требуется, чтобы I1 = 1, I2 ; S, It ; S ; It;1 . ;(s) = A(s), B(s), ;h(s), ;v (s), h(s), v(s).
для s1 ; 1 до S выполните
{f1 (1, s1 ), F1 (1, s1 ), p} = LDSFORWARD(0, 0, v1 ; ;(s1 ))
;1 ; p(s1 )p
конец
для от t ; 2 до T делать
для st ; 1 до S делать
для i ; 1 к It;1 и s ; 1 к S делаем
{µx|y (i, s), ;x|y (i, s), p} = LDS ВПЕРЕД(ft;1 (i, s), Ft;1 (i, s), vt ; ;(st ))
p; (st |i, s) ; hp(st |ht;1 , st;1 = s)ip(ht;1 |it;1 =i,st;1 =s,v1:t;1 )
p0 (st , i, s) ; wt;1 (i, s)p; (st |i, s)в конце;1 (s)p
для
Сверните смесь гауссианов It;1 ; S , определяемую значениями µx|y ,;x|y и весами
0
p(i,
PIts |st ) ; p (st , i, s) в гауссову с ее компонентами, p(ht |st , v1:t ) ;
Это определяет новые значения ft (it , st ), ковариации
it =1 p(it |st , v1:t )p(ht |st , it , v1:t ).
Ft (it , st ) и смесь взвешивает wt (it , st ) ; p(it |st , v1:t ).
Вычисляем на (st ) ; i,s p0 (st , i, s)
конец для
нормализации на P
L ; L + log st ,i,s p0 (st , i, s)
конец для
смеси используется[277]. Сначала мы опишем, как свести смесь к одному гауссову закону. Этого можно достичь, найдя среднее значение и ковариацию распределения смеси (25.3.17). Это
Чтобы затем разложить смесь на K-компонентную смесь, мы можем сначала сохранить K ; 1 Гауссианов с наибольшими весами смеси. Оставшиеся N ; K + 1 Гауссианов просто объединяются в одну Гауссиану используя описанный выше метод. Альтернативные эвристические методы, такие как рекурсивное объединение двух Гауссиан с наименьшими весами в смеси, также являются разумными.
Более сложные методы, которые сохраняют некоторую пространственную информацию, несомненно, были бы потенциально полезными. Метод, представленный в [174], является подходящим подходом, который рассматривает удаление Гауссианов, которые пространственно схожи (а не только компоненты с малым весом), тем самым сохраняя ощущение разнообразия возможных решений. В приложениях с многотысячными временными интервалами скорость может быть фактором, определяющим, какие из них предпочтительным является метод свертывания Гауссианов.
25.3.5 Связь с другими методами
Гауссову суммарную фильтрацию можно рассматривать как форму "аналитической фильтрации частиц", раздел (27.6.2), в котором вместо точечных распределений (дельта-функций), которые распространяются, используются Гауссовы коэффициенты. Операция свертывания до меньшего числа Гауссиан аналогична повторной выборке при фильтрации частиц. С тех пор, как Гауссова функция более выразительна, чем дельта-функция, поэтому фильтр суммы Гаусса, как правило, является улучшенным методом аппроксимации по сравнению с использованием точечных частиц. Численное сравнение приведено в [17].
25.4 Сглаживание Гауссовой Суммы
Аппроксимация сглаженного заднего значения p(ht | st , v1: t ) . более сложна, чем фильтрация, и требует дополнительных приближений. По этой причине сглаживание более подвержено сбоям, поскольку для выполнения аппроксимаций необходимо выполнить больше предположений. Здесь мы предполагаем, что Гауссовская
462 ЧЕРНОВИК от 9 марта 2010 г. Сглаживание суммы по Гауссу
аппроксимация с суммарной фильтрацией была выполнена, а затем аппроксимация обратного прохождения ;, аналогичная описанной в разделе (23.2.4). По аналогии с уравнением сглаживающей рекурсии RTS (23.2.20), точное значение обратного прохода для SLDS показывает
, где p(ht +1 | st +1 , v1: T ) = p( st +1 |v1: T )p(ht +1 | st +1 , v1: T ) состоит из дискретных и непрерывных
компонентов сглаженной апостериорной информации на следующем временном шаге. Рекурсия выполняется в обратном направлении во времени, начиная с инициализации p(ht +1 | st +1 , v1: T ), заданной отфильтрованным результатом (в момент времени t = T отфильтрованные и сглаженные последующие значения совпадают). Помимо того, что количество компонентов смеси будет увеличиваться с каждым разом. на этом этапе вычисление интеграла по ht + 1 в уравнении (25.4.1) проблематично, поскольку член условного распределения в ht + 1 не является гауссовым. По этой причине более полезно получить приблизительную рекурсию, начав с точного соотношения
, что может быть выражено более непосредственно в терминах динамики SLDS следующим образом
При формировании рекурсии мы предполагаем доступ к распределению p( st + 1 , ht + 1 |v1: t ) из будущего временного интервала. Однако нам также требуется распределение p(ht +1 | st , st +1 , v1: T ), которое напрямую неизвестно и должно быть выведено, что само по себе является сложной вычислительной задачей. В подходе с поправкой на Математическое Ожидание (EC) [17] предполагается приближение (см. рис.25.3)
что приводит к приблизительной рекурсии для сглаженной задней части,
, где <·>ht+1 представляет собой усреднение по отношению к распределению p(ht +1 | st +1 , v1: T ). При выполнении приближенной рекурсии (25.4.5) мы получим смесь Гауссиан, которая растет с каждым временным шагом. Чтобы избежать проблемы экспоненциального взрыва, мы используем приближение конечной смеси q(ht +1 , st +1 | v1: T ) :
и подключите это к приведенной выше приблизительной рекурсии. Из уравнения (25.4.5) рекурсия для приближения определяется как
Что касается фильтрации, то там, где это возможно, мы заменяем приблизительные термины их точными аналогами и определяем апостериорные значения с помощью
Чтобы уменьшить нагрузку на обозначения, здесь мы описываем метод только для случая использования однокомпонентной аппроксимации как при прямом, так и при обратном проходах. Переход к использованию смеси для аппроксимации каждого значения p(ht +1 , st +1 | v1: T ) концептуально прост и приведен в разделе (25.4.4). В единственном Гауссовском случае мы предполагаем, что у нас есть Гауссово приближение, доступное для
ЧЕРНОВИК от 9 марта 2010 г. 463 Сглаживание суммы по Гауссу
Рисунок 25.3: Обратный проход EC приблизительно равен p(ht +1 , st +1, st | v1: T ) на p(ht +1 | st +1 , v1: T ). Это объясняется тем , что st влияет на ht +1 только косвенно, через ht . Однако на ht, скорее всего, сильно повлияет v1:t, так что незнание состояния st , скорее всего, будет иметь второстепенное значение. Узел, заштрихованный зеленым, - это переменная, для которой мы хотим найти позиционное значение. Значения узлов, заштрихованных синим, известны, а узел, заштрихованный красным, указывает на известную переменную, которая считается неизвестной при формировании аппроксимации.
25.4.1 Непрерывное сглаживание
Для заданного st , st + 1, рекурсия в стиле RTS для сглаженной непрерывности получается из уравнения (25.4.7), дающего
Чтобы вычислить уравнение (25.4.10), мы затем выполняем однократное обновление обратной рекурсии LDS, см. раздел (24.4.2).
25.4.2 Дискретное сглаживание
Второе среднее значение в уравнении (25.4.7) соответствует рекурсии для дискретной переменной и задается как
Среднее значение q( st | ht +1 , st +1, v1: t ) по отношению к q (ht +1 | st +1 , v1: T ) не может быть получено в замкнутом виде. Простой подход заключается в приближении среднего значения к среднему значению1
где <ht +1 , st +1, v1: T > - среднее значение ht +1 по отношению к q(ht +1 | st +1, v1: T ).
Замена ht +1 на его среднее значение дает приближение
где
и Z обеспечивает нормализацию по st . ;(st +1 , st +1| v1: T ) - это отфильтрованная ковариация ht+1 с учетом st , st+ 1 и наблюдений v1:t , которая может быть взята из ;hh в уравнении (25.3.8). Также могут быть рассмотрены аппроксимации, учитывающие информацию о ковариации, хотя на практике может быть достаточно приведенного выше простого (и быстрого) метода [17, 192].
25.4.3 Измельчение смеси
Из раздела (25.4.1) и раздела (25.4.2) теперь у нас есть все члены уравнения (25.4.8) для вычисления приближения к уравнению (25.4.7). Из-за суммирования по st+1 в уравнении (25.4.7) количество компонентов смеси умножается на S на каждой итерации. Чтобы предотвратить экспоненциальный рост количества компонентов, уравнение смеси (25.4.7) затем сводится к одному гауссову уравнению
Процесс получения смеси обсуждается в разделе (25.4.4).
1 В общем случае это приближение имеет вид <f (x)> ; f (<x>).
ЧЕРНОВИК от 9 марта 2010 г. 464 Сглаживание суммы по Гауссу
Алгоритм 23 aSLD: Обратный проход EC. Приближает значения p(st |v1:T ) и p(ht |st , v1:T )
к P используя смесь гауссианов. JT = IT , Jt ; S ; It ; Jt +1 . Для этой процедуры tt =1
нужны результаты алгоритма(22).
ГТ ; ФТ , ГТ ; футов , ут ; мас
для T ; T ; 1 в 1 делать
для S ; 1 до S, типоразмер S0 ; 1 до S, Я ; 1 к нему , Дж 0 ; 1 к JT+1 делать
(µ, ;)(я, е, Дж, 0 , С0 ) = LDSBACKWARD(ГТ+1 (Дж, 0 , С0 ), ГТ+1 (Дж, 0 , С0 ), м (я, ю), м (я, х), ;(С0 ))
p(it , st |jt+1 , st+1 , v1:T ) = hp(st = s, it = i|ht+1 , st+1 = s0 , jt+1 = j0 , v1:t )ip(ht+1 |st+1 =s0 ,jt+1 =j0 ,v1:T )
p(i, s, j0 , s0 |v1:T ) ; p(st+1 = s0 |v1:T )ut+1 (j0 , s0 )p(it , st |jt+1 , st+1 , v1:T )
завершите для
для st ; 1 , чтобы выполнить
Сверните смесь, определяемую весовыми коэффициентами p(it = i, st+1 = s0 , jt+1 = j0 |st , v1T ) ;
p(i, st , j0 , s0 |v1:T ), значения µ(it , st , jt+1 , st+1 ) и ковариации ;(it , st , jt+1 , st+1 ) для
смеси с Jt компонентами. Это определяет новые средние значения gt (jt , st ), ковариации Gt (jt , st ) и веса смеси
P ut (jt , st ).
p(st |v1:T ) ; it ,j 0 ,s0 p(it , st , j 0 , s0 |v1:T )
конец для
конца для
25.4.4 Использование смесей для выравнивания \сглаживания
Переход к смешанному случаю прост и основан на представлении
Аналогично случаю с одним компонентом,
Среднее значение в последней строке приведенного выше уравнения можно вычислить, используя те же методы, что и в случае с одним Гауссом. Чтобы приблизить q (ht |jt+1 , st+1 , it , st , v1:T), мы рассматриваем это как предельное значение совместного распределения
Как и в случае с одной смесью, проблемным членом является q (ht+1 |it , st , jt+1 , st+1 , v1:T)). Аналогично уравнению (25.4.4), мы делаем предположение
это означает, что информация о текущем состоянии переключателя st , it игнорируется. Затем мы можем сформировать
Затем эту смесь можно измельчить до состояния смеси меньшего размера любым выбранным способом, чтобы получить
Результирующая процедура описана в алгоритме(23), включая использование смесей как в прямом, так и в обратном проходах.
ЧЕРНОВИК от 9 марта 2010 г. 465 Сглаживание суммы по Гауссу
25.4.5 Связь с другими методами
Классическим сглаживающим приближением для SLDS является обобщенный псевдоБайесовский алгоритм (GPB) [13, 160, 159]. В GPB все начинается с точной рекурсии
Величину p(st |st+1 , v1:T ) трудно получить , и GPB использует приближение
Подставляя это в уравнение (25.4.22), мы получаем
Рекурсия инициализируется с помощью приблизительного отфильтрованного значения p(sT |v1:T ). Вычисление сглаженной рекурсии для состояний переключения в GPB эквивалентно выполнению обратного прохода RTS по скрытому Марковской алгоритму\ модели, независимо от обратной рекурсии для непрерывных переменных. Единственная информация
, которую метод GPB использует для формирования сглаженного распределения p(st |v1:T ) из отфильтрованного распределения p(st |v1:t ) является Марковским переключающим переходом p(st+1 |st ). Это приближение отбрасывает информацию из будущего, поскольку информация, передаваемая через непрерывные переменные, не учитывается. В отличие от GPB, EC Метод сглаживания по Гауссу сохраняет будущую информацию, передаваемую через непрерывные переменные. Как для EC GPB формирует аппроксимацию для p(ht |st , v1:T ), используя рекурсию (25.4.8), где q(st |st+1 , v1:T ) определяется как q(st |st+1 , v1:t ). В SLDSbackward.m можно выбрать либо EC, либо GBP.
Пример 105 (Поток трафика). В качестве примера моделирования и вывода с помощью SLDS можно рассмотреть простую сеть транспортных потоков, рис.25.4. Здесь представлены 4 перекрестка\ соединения a, b, c, d и транспортные потоки вдоль дорог в указанном направлении. Транспортный поток доходит до перекрестка в точке а, а затем направляется по другим маршрутам до точки d. Поток, выезжающий с перекрестка, должен соответствовать потоку, въезжающему на перекресток (с точностью до уровня шума). На перекрестках a и b установлены переключатели светофоров\ соединений, которые, в зависимости от их состояния, по-разному распределяют движение по дорогам.
Используя ; для обозначения чистого (без шума) потока, мы моделируем потоки с использованием линейной системы переключения:
Определяя потоки в момент времени t с помощью 6;мерной векторной скрытой переменной ht, мы можем записать приведенные выше уравнения потока в виде
для набора соответствующим образом определенных матриц A(s), индексируемых переменной switch s = sa sb , которая принимает 3 ; 2 = 6 состояний. Мы дополнительно включаем шумовые условия для моделирования парковки или отмены парковки автомобилей в течение одного временной интервал. Ковариация ;h является диагональной с большей дисперсией в точке входа a для моделирования того, что общий объем трафика, поступающего в систему, может изменяться.
Измерения расхода в сети с помехами производятся при
466 ЧЕРНОВИК от 9 марта 2010 г. Сглаживание суммыпо Гауссу
Рисунок 25.4: Представление транспортного потока между перекрестками \соединениями\ в точках a, b, c, d со светофорами в точках a и b. Если sa = 1, то a ; d и a ; b переносят 0,75 и 0,25 потока из a соответственно. Если sa = 2, то весь поток из a проходит через a ; d; для sa = 3, весь поток проходит через a ; b. При sb = 1 поток, выходящий из b, делится поровну между b ; d и b ; c. При sb = 2 весь поток, выходящий из b, проходит по b ; c.
Рисунок 25.5: Изменение потока трафика во времени, измеренное в двух точках сети. Датчики измеряют общий поток в сеть ;a (t) и общий поток из сети ;d (t) = ;a;d (t) + ;b;d (t) + ;c;d (t). Общий поток в точке a изменяется случайным образом. Обратите внимание, что поток, измеренный в точке d, может на мгновение упасть до нуля, если весь трафик направляется через a ; b ; c за два последовательных временных шага.
наряду с шумовым измерением общего расхода из системы при d,
Модель наблюдения может быть представлена как vt = Bht + ; vt, используя постоянную проекционную матрицу B размером 2 ; 6. Переменные переключателя следуют простому марковскому переходу p(st |st;1 ), который заставляет переключатели оставаться в одном и том же состоянии, предпочитая переход в другое состояние. Подробности смотрите в demoSLDStraffic.m.
Учитывая описанную выше систему и априор, который инициализирует весь поток в точке a, мы извлекаем образцы из модели, используя прямая (наследственная) выборка, которая формирует наблюдения v1:100 , рис.(25.5). Используя только наблюдения и известную структуру модели, мы затем пытаемся определить скрытые переменные переключения и транспортные потоки, используя Гауссову Суммарную фильтрацию и сглаживание (метод EC) с 2 компонентами смеси для каждого состояния переключения, рис.25.6.
Мы отмечаем, что наивное приближение HMM, основанное на дискретизации каждого непрерывного потока в 20 ячеек, будет содержать 2 ; 3 ; 206 или 384 миллиона состояний. Поэтому даже для задач небольшого размера наивное приближение, основанное на дискретизации, непрактично.
Пример 106 (Следование ценовому тренду). Ниже приведена простая модель ценового тренда акции, которая предполагает, что цена имеет тенденцию продолжать расти (или падать) в течение некоторого времени, прежде чем изменить направление:
здесь h1 обозначает цену, а h2 - направление. В каждый момент времени существует только одна переменная наблюдения, которая представляет собой цену плюс небольшое количество шума. Существует два состояния переключения, dom(st) = {1, 2}. Когда st = 1, модель функционирует нормально, при этом направление равно предыдущему направлению плюс небольшое количество шума ;2h ( st = 1). Однако, когда st = 2, направление выбирается из гауссовой функции с большой дисперсией. Переход p(st|st;1 ) задается таким образом, что более вероятна нормальная динамика, а при st = 2, скорее всего, на следующем временном шаге динамика вернется к нормальному состоянию. Более подробная информация приведена в SLDSpricemodel.mat. На рис. 25.7 мы строим некоторые выборки из модели, а также сглаженный вывод о распределении переключателей, показываем, как мы можем апостериорно определить вероятные изменения в направлении изменения цены акций. Смотрите также упражнение(239).
ЧЕРНОВИК от 9 марта 2010 г. 467 Моделей для переустановки
Рисунок 25.6: Учитывая наблюдения из рисунка(25.5), мы выводим потоки и состояния переключения всех скрытых переменных. (а): Правильные скрытые потоки во времени вместе с состоянием переменной переключения, используемой для генерации данных. Цвета соответствуют потокам на соответствующих цветных краях/узлах на рис. 25.4. (b): Отфильтрованные потоки, основанные на приближении прямого прохождения гауссовой суммы I = 2. На графике представлены 6 компонентов вектора <ht |v1:t> с задним распределением состояний светофоров sa и sb p(sat |v1:t ), p(sbt |v1:t ) показаны на графике ниже. (c): Сглаженные потоки <ht |v1:T > и соответствующие сглаженные состояния переключения p (st |v1:T) с использованием приближения сглаживания гауссовой суммы (EC с J = 1).
Рисунок 25.7: Верхняя панель представляет собой временной ряд ‘цен’. Цены, как правило, продолжают расти или падать с редкими изменениями направления. На основе применения простой модели SLDS для учета такого поведения, вероятность существенного изменения направления цен приведена в таблице ниже на основе сглаженное распределение p(st = 2|v1:T ).
25.5 Сброс моделей
Модели сброса - это специальные модели переключения, в которых состояние переключения отделяет настоящее от прошлого, восстанавливая положение скрытой динамики (они также известны как модели точки изменения). Хотя эти модели являются довольно общими, может быть полезно рассмотреть конкретную модель, и здесь мы рассмотрим модель точки изменения SLDS с двумя состояниями. Мы используем состояние st = 0 для обозначения того, что LDS продолжает стандартную динамику. Однако при st = 1 непрерывная динамика возвращается к предыдущему значению:
, где
аналогично запишем
Для простоты мы предполагаем, что динамика переключения является Mарковской первого порядка с переходом p(st |st;1). В рамках этой модели динамика соответствует стандартному LDS, но когда st = 1, ht сбрасывается на значение, полученное из
468 ЧЕРНОВИК от 9 марта 2010 г. Модели сброса
Рисунок 25.8: Структура независимости модели сброса. Квадратные узлы ct обозначают двоичные переменные сброса, а st динамика состояния. ht - это непрерывные переменные, а vt - непрерывные наблюдения. Если динамика сбрасывается, зависимость непрерывного ht от прошлого прерывается.
Гауссово распределение, независимое от прошлого. Такие модели могут представлять интерес для прогнозирования, когда временной ряд следует тенденции, но внезапно меняется, и прошлое забывается. Хотя это может показаться не большим изменением в модели, но эта модель более удобна в вычислительном плане и масштабируется с помощью O (T 2) , по сравнению с O(T2T )в обычных SLDS с двумя состояниями. Чтобы убедиться в этом, рассмотрим рекурсию фильтрации
Теперь мы рассмотрим два случая
Уравнение(25.5.6) показывает, что p(ht , st = 1|v1:t ) не является моделью смеси в ht, а содержит только один компонент, пропорциональный p1 (vt |ht )p1 (ht ). Если мы используем эту информацию в уравнении (25.5.5), то получим
Предполагая, что ;(ht;1 , st;1 = 0) - это распределение смеси с K компонентами, тогда ;(ht , st = 0) будет смесью с K + 1 компонентами. Таким образом, в общем случае ;(ht , st = 0) будет содержать T компонентов, а ;(ht , st = 1) - один компонент. Таким образом, в отличие от случая с полным SLDS, количество компонентов растет только линейно со временем, в отличие от экспоненциальной\ в геометрической прогрессии. Это означает, что вычислительные усилия для выполнения точной фильтрации по шкале O(T2).
Формализм длины цикла
Можно также описать модели сброса, используя формализм "длины цикла", используя в каждый момент времени t скрытую переменную rt, которая описывает длину текущего сегмента[3]. Если происходит изменение, переменная длины цикла сбрасывается на ноль, в противном случае она увеличивается на 1:
, где Pcp - это вероятность сброса (или "точка изменения"). Общее распределение задается как
Окончательный ВАРИАНТ от 9 марта 2010 г. 469 Переустановите модели
с учетом того, что если rt = 0 , то p(vt |vt;rt :t;1 ) = p(vt ). Графическую модель этого распределения сложно нарисовать, поскольку количество ссылок зависит от длины цикла rt. Прогнозы могут быть сделаны с помощью
, где отфильтрованная ‘длина цикла’ p(rt |v1:t ) задается прямой рекурсией:
что показывает, что отфильтрованный вывод масштабируется с помощью O( T2 ).
25.5.1 Модель сброса Пуассона
Структура точек изменения не ограничивается только условно Гауссовыми случаями. Чтобы проиллюстрировать это, рассмотрим следующую модель2: В каждый момент времени t мы наблюдаем количество yt, которое, как мы предполагаем, распределено по Пуассону с неизвестной положительной интенсивностью h. Интенсивность постоянна, но в определенные неизвестные моменты времени t она переходит на новое значение. Индикаторная переменная ct указывает, является ли время t моментом такого изменения или нет. Математически модель представляет собой:
Символы G, BE и PO обозначают Гамма-распределения, распределения Бернулли и распределения Пуассона соответственно:
Учитывая наблюдаемые значения v1:T , задача состоит в том, чтобы найти апостериорную вероятность изменения и связанную с ней уровни интенсивности для каждой области между двумя последовательными точками изменения. Объединив приведенные выше определения в уравнении общих обновлений (25.5.5) и уравнении (25.5.6), мы видим, что ;(ht , ct = 0) представляет собой гамма-потенциал, а ;(gt , ct = 1) представляет собой смесь гамма-потенциалов, где гамма-потенциал определяется как
через тройку (a, b, l). Для шага обновления корректора нам нужно вычислить произведение Пуассоновского члена на модель наблюдения p(vt |ht ) = PO(vt ; ht ). Полезным свойством распределения Пуассона является то, что, согласно наблюдениям, скрытая переменная имеет Гамма-распределение:
Следовательно, для обновления уравнения требуется умножение двух Гамма-потенциалов. Приятным свойством Гамма-плотности является то, что произведение двух Гамма-плотностей также является Гамма-потенциалом:
2 Этот пример написан Тейланом Джемгилом.
ПРОЕКТ от 9 марта 2010 г. 470 Устанавливает модели
, где
Таким образом, ;-рекурсии для этой модели сброса замкнуты в пространстве смеси гамма-потенциалов, при этом на каждом временном шаге в смеси присутствует дополнительный гамма-потенциал. Аналогичный подход может быть использован для формирования сглаживающих рекурсий.
Пример 107 (Катастрофы на угольных шахтах). Мы иллюстрируем алгоритм на наборе данных о катастрофах на угольных шахтах [144]. Набор данных включает количество смертельных аварий на шахтах в Англии за год в течение 112 лет с 1851 по 1962 год. В статистической литературе широко распространено мнение, что изменение интенсивности (ожидаемого значения числа стихийных бедствий) произошло примерно в 1890 году, после введения новых правил охраны труда и техники безопасности. На рис. 25.9 мы показываем граничные значения p(ht |y1:T) вместе с плотностью фильтрации. Обратите внимание, что мы не ограничиваем количество точек изменения и в принципе допускаем любое их количество. Сглаженная плотность предполагает резкое снижение около t = 1890.
Количество аварий
интенсивность фильтрации
сглаженная интенсивность
Рисунок 25.9: Оценка точек изменения. (Вверху) набор данных о катастрофах на угольных шахтах. (Посередине) Отфильтрованная оценка предельной интенсивности p(ht |v1:t) и (внизу) сглаженная оценка p(ht |v1:T). Мы оцениваем это сочетание- рассмотрим гамма-распределения на фиксированной сетке h и покажем плотность в зависимости от t. Здесь более темный цвет означает более высокую вероятность.
25.5.2 HMM-сброс
Модель сброса, определенная уравнениями (25.5.1,25.5.3) выше, полезна во многих приложениях, но ограничена, поскольку рассматривается только одна динамическая модель. Важным расширением является рассмотрение набора доступных динамических моделей, индексированных по st ; {1, . . . , S}, со сбросом, который устраняет зависимость непрерывной переменной от прошлого[93, 57]:
Состояния st соответствуют Марковской динамике p(st |st;1, ct;1), см. рис.25.10. Сброс происходит, если состояние st изменяется, в противном случае сброс не происходит:
Вычислительная сложность фильтрации для этой модели составляет около О(S2 Т2), что можно понять по аналогии с восстановлением ;-рекурсий в уравнениях(25.5.5,25.5.6) при замене ht на (ht , st ). Чтобы убедиться в этом, мы рассмотрим рекурсию фильтрации для двух случаев
ДРАФТ от 9 марта 2010 года 471 Упражнения
Рисунок 25.10: Структура независимости модели HMM-reset\ сброс. Квадратные узлы ct обозначают дискретные переменные переключения; ht являются непрерывными скрытыми переменными, а vt — непрерывными наблюдениями. Дискретное состояние ct определяет, какие Линейные Динамические системы из конечного набора Линейных Динамических систем работает в момент времени t.
Из уравнения (25.5.27) мы видим, что ;(ht , st , ct = 1) содержит только одну составляющую, пропорциональную p1 (vt |ht , st )p1 (ht |st ). Таким образом, это в точности аналогично стандартной модели сброса, за исключением того, что теперь нам нужно индексировать набор сообщений с помощью st, поэтому каждое сообщение требует O (S) шагов для вычисления. То есть вычислительные усилия для выполнения точных масштабов фильтрации в обычном режиме равны O(S2T2).
25.6 Код
SLDSforward.m: SLDSвперед
SLDSbackward.m: SLDS назад (Коррекция Математического Ожидания)
mix2mix.m: Сворачивает набор Гауссиан в меньший набор Гауссиан
SLDSmargGauss.m: Маргинализация Гауссовой смеси SLDS
SLDS logeps.m: Логарифмирование со смещением для обработки логарифма(0)
demoSLDStraffic.m: Демонстрация Транспортного Потока \ TF\ с использованием переключающейся линейной динамической системы SLDS
25.7 Упражнения
Упражнение 239. Рассмотрим настройку, описанную в примере(106), для которой полная модель SLDS приведена в SLDSpricemodel.m, в соответствии с обозначениями, используемыми в demoSLDStraffic.m. Учитывая данные в векторе v, ваша задача состоит в том, чтобы подогнать модель прогнозирования к данным. Для этого приблизьте отфильтрованное распределение p(h(t), s(t)|v1:t), используя смесь из I = 2 компонентов. Таким образом, прогноз цены на следующий день равен
где p(h(t)|v1:t ) = ;st p(h(t), st |v1:t ).
1. Вычислите среднюю ошибку прогнозирования
mean_abs_pred_error=mean(abs(vpred(2:end)-v(2:end)))
среднее значение
2. Вычислите среднюю ошибку наивного прогнозирования
mean_abs_pred_error_naive=mean(abs(v(1:end-1)-v(2:end)))
что соответствует утверждению, что завтрашняя цена будет такой же, как и сегодняшняя. Возможно, вас заинтересует SLDSmargGauss.m.
Упражнение 240. Данные на рисунке(25.11) являются наблюдаемыми ценами, полученными в результате периодического процесса возврата к среднему значению, содержащегося в meanrev.mat. Существует два состояния S = 2. Существует истинная (скрытая) цена pt и наблюдаемая цена vt (которая отображается на графике). Когда s = 1, истинная базовая цена возвращается к среднему значению m = 10 с коэффициентом r = 0,9. В противном случае истинная цена определяется случайным образом:
472 ЧЕРНОВИК от 9 марта 2010 года Упражнения
Рисунок 25.11: Данные, полученные в результате периодического процесса возврата к среднему значению. Смотрите упражнение(240).
где
Наблюдаемая цена vt соотносится с неизвестной ценой pt через
Известно, что 95% времени st+1 находится в том же состоянии, что и в момент времени t, и что в момент времени t = 1 любое из состояний s одинаково вероятно. Также при t = 1, p1 ~ N (p1 |m, 0,1). Основываясь на этой информации и используя Гауссову Фильтрацию Суммы с I = 2 компонентами (используйте SLDSforward.m), какова вероятность того, что в момент времени t = 280 динамика является результатом случайного блуждания, p(s280 = 2|v1:280 )? Повторите это вычисление для сглаживания p(s280 = 2|v1:400 ) на основе использования Коррекции Математического Ожидания с I = J = 2 компонентами.
ДРАФТ от 9 марта 2010 года 473 Упражнения
474 ЧЕРНОВИК от 9 марта 2010 г.
Глава 26
Распределенные Вычисления
26.1 Вступление
То, как естественные организмы обрабатывают информацию, является увлекательной темой и одной из важнейших задач науки. Хотя эта тема все еще находится на ранней стадии своего развития, можно выделить несколько общих свойств- считается, что большинство таких систем обладают следующими свойствами: паттерны хранятся в наборе нейронов; запоминание паттернов устойчиво к шуму; передача данных между нейронами носит бинарный характер и является стохастической; обработка информации распределена и имеет высокую модульность. В этой главе мы обсудим некоторые классические модели игрушек, которые были разработаны в качестве испытательного стенда для анализа таких свойств[62, 76, 65, 132]. В частности, мы рассмотрим некоторые классические модели с вероятностной точки зрения.
26.2 Стохастические Сети Хопфилда
Сети Хопфилда - это модели биологической памяти, в которых паттерн представлен активностью набора из V взаимосвязанных нейронов. Термин "сеть" здесь относится к набору нейронов, см. рис. 26.1, а не к Сети Убеждений, представляющей распределение нейронных состояний, развернутое во времени, рис.26.2. В момент времени t нейрон i запускает vi (t) = +1 или находится в состоянии покоя vi (t) = -1 (не запускается) в зависимости от состояний нейронов в предшествующий момент времени t ; 1. Очевидно, что нейрон i запускается в зависимости от потенциала
где wij характеризует эффективность, с которой нейрон j передает двоичный сигнал нейрону i. Пороговое значение ;i относится к предрасположенности нейрона к возбуждению. Записывая состояние сети в момент времени t как v(t) ; (v1 (t), ... , vV (t)), вероятность того, что нейрон i сработает в момент времени t + 1, моделируется как
где ;; (x) = 1/(1 + e;;x ) и ; определяет уровень стохастического поведения нейрона. Вероятность нахождения в состоянии покоя определяется нормировкой
Эти два правила могут быть компактно записаны в виде
что непосредственно следует из 1 ; ;; (x) = ;; (;x).
475 Обучающие последовательности
Рисунок 26.1: Изображение сети Хопфилда (для 5 нейронов). Взаимосвязанность нейронов описывается весовой матрицей с элементами wij. Граф представляет собой моментальный снимок состояния всех нейронов в момент времени t, которые одновременно обновляются в зависимости от состояния сети в предыдущий момент времени t ; 1.
В пределе ; ; ; нейрон детерминированно обновляет
В синхронной сети Хопфилда все нейроны обновляются независимо и одновременно, так что мы можем представить временную эволюцию нейронов в виде динамической Байесовской сети, рис.26.2
Учитывая это игрушечное \инструментальное\ описание того, как нейроны обновляются, как мы можем использовать сеть для выполнения интересных задач, например, для хранения набора паттернов и вызова их по какому-либо сигналу. Шаблоны будут сохранены в весах, и в следующем разделе мы расскажем, как узнать подходящие параметры wij и ;i для обучения временных последовательностей, основанных на простом локальном правиле обучения.
26.3 Последовательности Обучения
26.3.1 Единая последовательность
Учитывая последовательность состояний сети, V = {v(1), . . . , v(T )}, мы хотели бы, чтобы сеть "сохраняла" эту последовательность таким образом, чтобы ее можно было вызвать по некоторому сигналу. То есть, если сеть инициализирована в правильном начальном состоянии обучающей последовательности v(t = 1), то оставшаяся часть обучающей последовательности для t > 1 должна быть воспроизведена в соответствии с уравнением детерминированной динамики (26.2.5) без ошибок.
Двумя классическими подходами к изучению временной последовательности являются правила Хебба 1 и ПсевдоОбратные \PI правила[132]. Как в стандартном случае Хебба, так и в случае PI пороговые значения ;i обычно устанавливаются равными нулю.
Стандартное правило Хебба
1Дональд Хебб, нейробиолог, фактически заявил[127]:
Давайте предположим, что постоянство или повторение ревербераторной активности (или "следа") имеет тенденцию вызывать длительные клеточные изменения, которые повышают ее стабильность. . . Когда аксон клетки А находится достаточно близко, чтобы возбуждать клетку В, и неоднократно или настойчиво участвует в ее возбуждении, происходит некоторый процесс роста или метаболические изменения происходят в одной или обеих клетках таким образом, что эффективность A, как одной из клеток, запускающих B, повышается.
Это утверждение иногда интерпретируется как означающее, что веса относятся исключительно к уравнению корреляционной формы (26.3.1) (обсуждение см. в [270] ). Это может серьезно ограничить производительность и привести к нежелательным артефактам хранения, включая локальные минимумы[132].
476 ЧЕРНОВИК от 9 марта 2010 г. Обучающие последовательности
Рисунок 26.2: Динамическое Bайесовское Cетевое представление сети Хопфилда. Сеть работает, одновременно генерируя новый набор состояний нейронов в соответствии с уравнением (26.2.6). Уравнение(26.2.6) определяет Марковскую матрицу перехода, моделирующую вероятность перехода v(t) ; v(t+1) и, кроме того, накладывает ограничение на то, что нейроны являются условно независимыми, учитывая предыдущее состояние сети.
Правило Хебба можно обосновать математически, рассмотрев
Если паттерны не коррелируют, то термин "интерференция"
будет относительно небольшим. Чтобы убедиться в этом, сначала отметим, что для случайно нарисованных паттернов среднее значение ; равно нулю, поскольку ;; t, а паттерны случайным образом равны ±1. Таким образом, дисперсия определяется как
При j; k все члены независимы и в среднем дают нулевой вклад. Следовательно
Когда ;; ;`, все члены являются независимыми и имеют нулевое среднее значение и нулевой вклад. Следовательно
При условии, что число нейронов V значительно больше длины последовательности T , тогда
средний размер интерференции будет небольшим. В этом случае член vi (t + 1) в уравнении (26.3.4) доминирует, что означает, что знак ;j wij vj (t) будет таким же, как у vi(t + 1), и вспоминается \ повторно вызывается\ правильная последовательность шаблонов. Правило Хебба способно сохранять случайную (некоррелированную) временную последовательность длиной 0,269V с временными шагами[85]. Однако правило Хебба плохо работает в случае коррелированных паттернов, поскольку интерференция из других паттернов становится значимой[132, 65].
Псевдообратное правило
Правило PI находит матрицу [W]ij = wij, которая решает линейные уравнения
ПРОЕКТ от 9 марта 2010 г. 477 Обучающие последовательности
При этом условии sgn (; j wijvj(t)) = sgn (vi (t + 1)) = vi (t + 1), чтобы шаблоны были правильно восстановлены. В матричной записи нам требуется
где
При T < V задача недоопределена. Одно из решений задается псевдообратным:
Правило псевдоинверсии (PI) может хранить любую последовательность из V линейно независимых шаблонов. Хотя оно и привлекательно по сравнению со стандартным алгоритмом Хебба с точки зрения его способности хранить более длинные коррелированные последовательности, это правило страдает из очень малых областей притяжения для моделей, коррелирующих во времени, см. рис. 26.3.
Правило максимального правдоподобия Хебба
Альтернативой приведенным выше классическим алгоритмам является рассмотрение этого как проблемы хранения шаблонов в DBN, уравнение (26.2.6) [19]. Во-первых, нам нужно уточнить, что мы подразумеваем под ‘хранением’. Учитывая, что мы инициализируем сеть в состоянии v(t = 1), мы хотим, чтобы оставшаяся последовательность была сгенерирована с высокой вероятностью. То есть мы хотим настроить параметры сети таким образом, чтобы вероятность
является максимальным 2 . Кроме того, мы можем надеяться, что последовательность будет восстановлена с высокой вероятностью не только при инициализации в правильном состоянии, но и для состояний, близких (на расстоянии Хэмминга) к правильному исходному
состоянию v(1).
Из;за Марковской природы динамики условная вероятность равна
Это результат переходов из заданных состояний в заданные. Поскольку вероятности этих переходов известны (26.2.6,26.2.2), можно легко оценить условную вероятность. Последовательность логарифмической (условной) вероятности равна
Затем наша задача состоит в том, чтобы найти веса w и пороговые значения ;, которые максимизируют L(w, ;). Решения в замкнутой форме не существует, и поэтому веса необходимо определять численно. Это соответствует простой вычислительной задаче, поскольку логарифмическое правдоподобие является выпуклой функцией. Чтобы показать это, мы вычисляем Гессиан (пренебрегая ; для наглядности изложения – это не влияет на выводы):
, где мы определили
2 Статические паттерны также можно рассматривать в этой структуре как набор паттернов, которые соотносятся друг с другом.
ЧЕРНОВИК от 9 марта 2010 г. 478 Обучающие последовательности
номер нейрона
Обучающая последовательность
Максимальное правдоподобие
Хебб
Псевдоинверсия
Рисунок 26.3: Крайняя левая панель: Последовательность тренировок с высокой временной корреляцией, которую мы хотим сохранить. Другие панели показывают временную эволюцию сети после инициализации в правильном исходном состоянии, но с 30%-ным уровнем помех \шума. При восстановлении использовались детерминированные обновления ; = ;. Правило Максимального Правдоподобия было разработано с использованием 10 пакетных периодов с ; = 0,1. Смотрите также demoHopfield.m
Несложно показать, что Гессиан является отрицательно определенным (см. упражнение (244)), и, следовательно, вероятность имеет единственный глобальный максимум. Чтобы увеличить вероятность появления последовательности, мы можем использовать простой метод, такой как градиентный подъем3
где
Скорость обучения ; выбирается эмпирически как достаточно малая для обеспечения сходимости. Уравнение правила обучения (26.3.19) можно рассматривать как модифицированное правило обучения Хебба, основное правило Хебба задается, когда ;i (t) ; 1. По мере продвижения обучения ;i (t) обычно стремится к значениям, близким либо к 1, либо к 0, и, следовательно, правило обучения можно рассматривать как асимптотически эквивалентное внесению изменений только в случае разногласий (ai (t) и vi (t + 1) имеют разные знаки).
Эта пакетная процедура обучения может быть легко преобразована в интерактивную, в которой обновление происходит сразу после представления двух последовательных шаблонов.
Объем памяти правила ML Hebb
Правило ML Hebb способно сохранять последовательность из V линейно независимых шаблонов. Чтобы убедиться в этом, мы можем сформировать обучающий набор ввода-вывода для каждого нейрона i, {(v(t), vi (t + 1)), t = 1, . . . , T ; 1}. Каждому нейрону соответствует весовой вектор wi ; wij , j = 1, . . . , V , который формирует логистический регрессор или, в пределе ; = ;, персептрон[132]. Таким образом, для точного запоминания паттернов нам нужно только, чтобы паттерны в последовательности были линейно разделены. Это будет иметь место, если паттерны линейно независимы, независимо от выходных сигналов vi (t + 1), t = 1, . . . , T ; 1.
Связь с правилом персептрона
В пределе, когда активация велика, |ai | » 1
При условии, что активация и желаемый следующий результат совпадают по знаку, обновление для нейрона i не производится. В это ограничение, уравнение (26.3.19), называется правилом персептрона[132, 80]. Для активации a, близкой к
3 Естественно, можно использовать более сложные методы, такие как метод Ньютона или метод сопряженных градиентов. В теоретической нейробиологии упор делается на небольшие изменения в стиле градиента, поскольку они считаются биологически более правдоподобными.
ПРОЕКТ от 9 марта 2010 г. 479 Обучающие последовательности
правильная доля
длина последовательности=50
Максимального правдоподобия (M=10)
Обученный шуму максимального правдоподобия
персептрон (M=0)
персептрон
Хебба
псевдоинверсия
вероятность переворота
Рисунок 26.4: Доля нейронов, правильная для конечного состояния сети T = 50, для сети Хопфилда из 100 нейронов, обученной хранить последовательности длиной 50 паттернов. После инициализации в правильном начальном состоянии при t = 1 сеть Хопфилда обновляется детерминистически, при этом случайно выбранный процент нейронов переключается после обновления. Коррелированная последовательность длиной T = 50 была получена путем переключения с вероятностью 0,5, 20% от предыдущего состояния сети. Доля правильных значений значение 1 указывает на точное воспроизведение конечного состояния, а значение 0,5 указывает на результативность, не превышающую случайного угадывания конечного состояния. Для достижения максимальной вероятности было использовано 50 периодов обучения при ; = 0,02. При повторном вызове использовались детерминированные обновления ; = ;. Представленные результаты являются средними по 5000 моделированиям, что приводит к стандартным ошибкам порядка размеров символов.
границе принятия решения небольшое изменение может привести к изменению знака нейронного возбуждения. Чтобы избежать этого, обычно используется критерий стабильности
, где M - эмпирически выбранный положительный порог.
Пример 108 (Сохранение коррелированной последовательности). На рис. 26.3 мы рассматриваем сохранение высококоррелированной временной последовательности длиной T = 20 из 100 нейронов с использованием трех правил обучения: Хебба, Максимального Првадоподобия\ Вероятности и ПсевдоИнверсия. Последовательность выбрана с высокой степенью корреляции, что представляет собой сложную задачу обучения. Пороговые значения ;i установлены на нулевое значение для облегчения сравнения. Исходное состояние обучающей последовательности, искаженное 30%-ным шумом, представляется обученным сетям, и мы хотим, чтобы обучающая\ тренирующая\ последовательность была сгенерирована из этого исходного зашумленного состояния. Хотя правило Хебба работает в допустимых пределах для некоррелированных паттернов, сильные корреляции в этой обучающей последовательности приводят к плохим результатам. Правило PI способно сохранять последовательность длиной 100, но не является устойчивым к отклонениям от правильного начального состояния. Правило Максимального Правдоподобия хорошо работает после небольшого обучения.
Стохастическая интерпретация
С помощью простых манипуляций правило обновления веса в уравнении (26.3.19) можно записать в виде
Таким образом, стохастическим правилом онлайн;обучения является
где ~v i(t + 1) равно 1 с вероятностью ;; (ai (t)), и -1 в противном случае. При условии, что скорость обучения ; мала, это стохастическое обновление будет приближено к правилу обучения (26.3.18,26.3.19).
Пример 109 (Повторение последовательностей в условиях постоянного шума). Мы сравниваем эффективность правила обучения с Максимальным Правдоподобием (с нулевыми пороговыми значениями ;) со стандартным правилом Хебба, ПсевдоИнверсией и правилом Персептрона для обучения одной временной последовательности. Сеть инициализируется с повреждением из-за шума
480 ЧЕРНОВИК от 9 марта 2010 г. Последовательности обучения
Рисунок 26.5: (а): Исходная двоичная видеопоследовательность T = 25 на наборе из 81 ; 111 = 8991 нейронов. (b): Реконструкции, начинающиеся с исходного состояния, возмущенного шумом на 20%. Реконструкция в любой момент времени также нарушается случайным образом. Несмотря на высокий уровень шума, основа привлекательности последовательности шаблонов очень широка, и шаблоны\ выборки \ немедленно возвращаются к последовательности шаблонов даже после одного временного шага.
версия правильного исходного состояния v(t = 1) из обучающей последовательности. Затем выполняется динамика (в ; = ;) для того же количества шагов, что и длина обучающей последовательности, и измеряется доля битов вызванного конечного состояния, которые совпадают с конечным состоянием v(T ) обучающей последовательности, рис.26.4. На каждом этапе динамики (кроме последнего) состояние сети было искажено шумом путем изменения состояния каждого нейрона с заданной вероятностью изменения. Обучающие последовательности создаются, начиная со случайного начального состояния, v(1), и затем случайным образом, выбирая 20% нейронов для переключения, каждый из выбранных нейронов переключается с вероятностью 0,5, что дает случайную обучающую последовательность с высокой степенью временной корреляции.
Стандартное правило Хебба работает относительно плохо, особенно при малых скоростях переключения, в то время как другие методы работают относительно хорошо, будучи надежными при малых скоростях переключения. По мере увеличения скорости переключения псевдообратное правило становится нестабильным, особенно при более длительной временной последовательности, которая предъявляет больше требований в сети. Правило персептрона может работать так же хорошо, как и правило Максимального Правдоподобия, хотя его эффективность в решающей степени зависит от правильного выбора порогового значения M. Результаты обучения Персептрона M = 0 неудовлетворительны при малых скоростях переключения. Преимущество правила Максимального Правдоподобия заключается в том, что оно хорошо работает без необходимости точной настройки параметров. Во всех случаях использовалось пакетное обучение.
На рис.26.5 приведен пример более крупной сети, состоящей из сильно коррелированных последовательностей. Для благодаря таким коротким эпизодам "бассейн притяжения" очень велик, и видеоряд может быть надежно сохранен.
26.3.2 Множественные последовательности
В предыдущем разделе подробно описывалось, как обучить сеть Хопфилда для одной временной последовательности. Теперь мы рассмотрим обучение набора последовательностей {;n , n = 1, . . . , N }. Если мы предположим, что последовательности независимы, логарифмическая вероятность набора последовательностей равна сумме отдельных последовательностей. Задан градиент
, где
Логарифмическая вероятность остается выпуклой, поскольку она является суммой выпуклых функций, так что и здесь можно использовать стандартные алгоритмы обучения на основе градиента.
ПРОЕКТ от 9 марта 2010 г. 481 Извлекаемые модели непрерывных скрытых переменных
26.3.3 Логические сети
Сеть Хопфилда - это одна из частных параметров таблицы p(vi (t + 1) = 1|v(t)). Однако, можно рассмотреть менее ограниченные параметры – действительно, можно было бы рассмотреть полностью неограниченный случай, в котором каждый нейрон i имел бы связанные с ним 2V родительских состояний. Такое экспоненциально большое количество состояний непрактично, и интересным ограничением является то, что у каждого нейрона есть только K родительских элементов, так что каждая таблица содержит 2K записей. Обучение параметров таблицы по Максимальному Правдоподобию является простым делом, поскольку логарифмическая вероятность является выпуклой функцией записей таблицы. Следовательно, для заданной любой последовательности (или набора последовательностей) можно легко найти параметры, которые максимизируют вероятность восстановления последовательности. Метод Максимального Правдоподобия также создает большие области притяжения для соответствующей стохастической динамической системы. Такие модели представляют потенциальный интерес для Искусственной Жизни и Случайных Булевых сетей, в которых макроскопическое поведение определяется локальными правилами обновления[158].
26.3.4 Устранение неоднозначности последовательности
Ограничением сетей первого порядка, определенных только на основе видимых переменных (таких как сеть Хопфилда), является что наблюдаемый переход p(vt+1 |vt = v) одинаков каждый раз, когда встречается совместное состояние v. Это означает, что если последовательность содержит подпоследовательность, такую как a, b, a, c, то это не может быть восстановлено с высокой вероятностью, поскольку a переходит в разные состояния в зависимости от времени. Хотя можно было бы попытаться решить проблему устранения неоднозначности последовательности, используя Марковскую модель более высокого порядка для учета более длительного временного контекста, мы потеряли бы биологическую правдоподобность. Альтернативой является использование скрытых переменных способ устранения неоднозначности последовательности. В модели Хопфилда способность запоминания может быть увеличена с помощью скрытых переменных путем создания последовательности в совместном скрыто-видимом пространстве, которая является линейно независимой, даже если последовательность видимых переменных сама по себе таковой не является. В разделе (26.4) мы обсудим общий метод, который расширяет возможности динамических Байесовских сетей, определенных только на основе видимых переменных, таких как сеть Хопфилда, для включения непрерывных нелинейно обновляемых скрытых переменных, не требуя дополнительных аппроксимаций.
26.4 Управляемые модели непрерывных скрытых переменных
Динамическая Байесовская сеть со скрытыми переменными имеет вид
Как мы видели в главе(23), при условии, что все скрытые переменные дискретны, логический вывод в этих моделях прост. Однако во многих физических системах более естественно предполагать непрерывность h(t). В главе(24) мы видели, что одна из таких гибких непрерывных моделей h (t) задается линейными гауссовыми переходами и выбросами - LDS. Хотя это и полезно, мы не можем представить нелинейные изменения в скрытом процессе, используя только LDS. Модель LDS Переключения, описанная в главе (25), способна моделировать нелинейную непрерывную динамику (посредством переключения). хотя мы видели, что это приводит к вычислительным трудностям. По вычислительным причинам мы, по-видимому, ограничены либо чисто дискретным h (без ограничений на дискретные переходы), либо чисто непрерывным h (но вынуждены использовать простую линейную динамику). Есть ли способ получить непрерывное состояние с нелинейной динамикой, для которой апостериорный вывод остается приемлемым? Ответ - да, при условии, что мы предполагаем, что скрытые переходы являются детерминированными[14]. При условии использования видимых переменных это делает распределение скрытых единиц измерения тривиальным. Это позволяет при необходимости учитывать богатую нелинейную динамику в скрытом пространстве.
26.4.1 Детерминированные скрытые переменные
Рассмотрим Сеть Убеждений, определенную на основе последовательности видимых переменных v1:T . Чтобы обогатить модель, мы включили дополнительные непрерывные скрытые переменные h1:T, которые будут следовать нелинейному Марковскому переходу. Чтобы сохранить для удобства вывода мы ограничиваем скрытую динамику детерминированной, описываемой
Здесь ;(x) представляет собой дельта-функцию Дирака для непрерывных скрытых переменных. Функция f (возможно, нелинейная) параметризует CPT. Хотя ограничение на детерминированные CPT представляется серьезным, модель
482 ПРОЕКТ от 9 марта 2010 г. Поддающиеся вычислению модели непрерывных скрытых переменных
Рисунок 26.6: (а): Динамическая Байесовская Сеть первого порядка с детерминированными скрытыми CPT (представленными ромбами), то есть скрытый узел, безусловно, находится в единственном состоянии, определяемом его родителями. (b): Обработка видимых переменных формирует направленную цепочку в скрытом пространстве, которая является детерминированной. Вывод о скрытой единице может быть получен только путем прямого распространения. (c): Интегрирование скрытых переменных дает направленный видимый граф в каскадном стиле, который позволяет каждому v (t) зависеть от всех v (1 : t ; 1).
сохраняет некоторые привлекательные черты: Предельное значение p(v(1 : T )) не является Марковским и связывает все переменные в последовательности, см. рис. 26.6c, в то время как вывод о скрытой единице p(h(1 : T )|v(1 : T )) является детерминированным, как показано на рис. 26.6б).
Настраиваемые параметры скрытого и видимого CPT представлены значениями ;h и ;v соответственно. Для обучения логарифмическая вероятность выполнения одной обучающей последовательности ; равна
, где значения скрытых единиц измерения вычисляются рекурсивно с использованием
Чтобы максимизировать логарифмическую вероятность с использованием градиентных методов, нам нужны производные от параметров модели. Их можно рассчитать следующим образом:
, где
Следовательно, производные могут быть вычислены только с помощью детерминированного прямого распространения ошибок. Случай обучения нескольких независимо сгенерированных последовательностей V n , n = 1, . . . , N является простым расширением.
26.4.2 Расширенная сеть Хопфилда
Чтобы сделать модель детерминированной скрытой переменной более наглядной, мы рассмотрим случай непрерывной скрытой единицы измерения и дискретные двоичные видимые единицы измерения, vi (t) ; {-1, 1}. В частности, мы ограничимся рассмотрением модели Хопфилда, дополненной скрытыми переменными, которые имеют простую линейную динамику (нелинейное расширение см. в упражнении(245)):
детерминированный скрытый переход
ПРОЕКТ от 9 марта 2010 г. 483 Нейронные модели
Эта модель обобщает рекуррентную стохастическую гетероассоциативную сеть Хопфилда[132], включающую детерминированные- статистические скрытые единицы, зависящие от прошлых состояний сети. Параметрами модели являются A, B, C, D. Для обучения на основе градиента нам требуются производные по каждому из этих параметров. Производная логарифмической вероятности для общего параметра ; равна
, где
Это дает (где все индексы суммируются по размерам величин, к которым они относятся):
Если мы предположим, что h(1) - это заданное фиксированное значение (скажем, 0), мы можем рекурсивно вычислить производные путем прямого распространения. Таким образом, обучение на основе градиента для этой расширенной сети Хопфилда легко реализовать. Эта модель расширяет возможности оригинальной модели Хопфилда, поскольку способна разрешать неоднозначные переходы в таких последовательностях, как a, b, a, c, см. пример(110) и demoHopfieldLatent.m. С точки зрения динамической системы, обученная сеть является аттрактором с обучающей последовательностью в качестве стабильной точки и демонстрирует, что такие модели способны обучать рекуррентные сети аттракторов более эффективно, чем те, у кого нет скрытых юнитов.
Пример 110 (Устранение неоднозначности последовательности). Последовательность на рис. 26.7а содержит повторяющиеся шаблоны и, следовательно, не может быть надежно воспроизведена с помощью модели первого порядка, содержащей только видимые переменные. Иметь дело с для этого мы рассмотрим сеть Хопфилда с 3 видимыми элементами и 7 дополнительными скрытыми элементами с детерминированной (линейной) скрытой динамикой. Модель была обучена с использованием градиентного подъема, чтобы максимизировать вероятность бинарной последовательности на рис. 26.7а. Как показано на рисунке (26.7, б), обученная сеть способна правильно воспроизвести последовательность, даже если она инициализирована в неправильном состоянии, не испытывая трудностей с тем фактом, что переходы между последовательностями неоднозначны.
26.5 Нейронные модели
Управляемая детерминированная модель скрытой переменной, представленная в разделе (26.4), предоставляет возможность расширить такие модели, как сеть Хопфилда, чтобы включить в них более биологически реалистичные процессы без потери вычислительной управляемости. Сначала мы обсудим общую структуру обучения в классе моделей нейронных сетей [15, 223], являющиеся частным случаем моделей детерминированных латентных переменных [14] и обобщением модели спайк-реакции теоретической нейробиологии[108].
484 ЧЕРНОВИК от 9 марта 2010 г. Нейронные модели
Рисунок 26.7: (а): Последовательность обучения состоит из случайного набора векторов (V = 3) за T = 10 временных шагов. (b): Реконструкция с использованием H = 7 скрытых единиц измерения. Исходное состояние v(t = 1) для восстановленной последовательности было установлено на правильное начальное значение для обучения, хотя одно из значений было изменено. Обратите внимание, что этот метод позволяет устранение неоднозначности последовательности в том смысле, что можно вспомнить переходы в форме a, b, . . . , a, c.
26.5.1 Стохастически активирующиеся нейроны
Мы предполагаем, что нейрон i возбуждается в зависимости от мембранного потенциала ai (t) через
Чтобы быть точным, мы берем по всему
Здесь мы определяем состояние покоя как vi (t + 1) = 0, так что
Выбор сигмовидной функции ;(x) не является фундаментальным и выбран просто для удобства анализа. Логарифмическая вероятность последовательности видимых состояний V равна
и тогда градиент логарифмического правдоподобия равен
, где мы использовали тот факт, что vi ; {0, 1}. Здесь wij - параметры мембранного потенциала (см. ниже). Мы используем уравнение (26.5.5) как обычное для следующих моделей, в которых мембранный потенциал ai (t) описывается с возрастающей сложностью.
26.5.2 Мембранный потенциал Хопфилда
В качестве первого шага мы покажем, как обучение сети Хопфилда, описанное в разделе (26.3.1), может быть восстановлено как частный случай вышеупомянутой структуры. Мембранный потенциал Хопфилда равен
где wij характеризует эффективность передачи информации от нейрона j к нейрону i, а bi - пороговое значение. Применяя принцип Максимального Правдоподобия к этой модели для обучения временной последовательности V путем настройки параметров wij (bi фиксированы для простоты), мы получаем правило (пакетного) обучения (используя dai /dwij = vj (t) в уравнении (26.5.4))
, где скорость обучения ; выбрана эмпирически как достаточно малая для обеспечения сходимости. Уравнение (26.5.7) соответствует уравнению (26.3.19) (в котором используется кодировка ±1).
ЧЕРНОВИК от 9 марта 2010 г. 485 Нейронные модели
номер нейрона
Исходные
Реконструированный
значения x
Реконструкция Хебба
Рисунок 26.8: Обучение в условиях депрессии: U = 0,5, ; = 5, ;t = 1, ; = 0,25. Несмотря на кажущуюся сложность динамики, определение соответствующих весовых коэффициентов нейронных связей является простым делом с использованием Максимального Правдоподобия. Реконструкция с использованием стандартного правила Хебба, напротив, оставляет желать лучшего[15].
26.5.3 Динамические синапсы
В более реалистичных синаптических моделях генерация нейромедиаторов зависит от конечной скорости выработки клеточных субкомпонентов, а на количество высвобождаемых везикул влияет история возникновения [1]. Свободно проще говоря, когда нейрон активируется, он высвобождает химическое вещество из локального резервуара, который пополняется с меньшей скоростью, чем может активироваться сам нейрон. Если нейрон активируется постоянно, его способность продолжать активацию ослабевает, поскольку запас высвобождаемого химического вещества истощается. Это можно объяснить с помощью механизма подавления, который влияет на мембранный потенциал
для коэффициентов депрессии xj (t) ; [0, 1]. Простая динамика для этих факторов депрессии такова[280]
где ;t, ; и U представляют временные шкалы, время восстановления и параметры усиливающегося эффекта соответственно. Обратите внимание, что динамика коэффициента депрессии в точности соответствует форме детерминированных скрытых переменных.
Несложно включить эти динамические синапсы принципиальным образом, используя систему обучения с максимальным правдоподобием. Для потенциала Хопфилда динамика обучения просто задается уравнениями (26.5.5,26.5.9), где
Пример 111 (Обучение в условиях депрессии). На рис. 26.4 мы демонстрируем обучение случайного временного последовательность из 20 временных шагов для совокупности из 50 нейронов с динамическими депрессивными синапсами. После обучения wij обученная сеть инициализируется в первом состоянии обучающей последовательности. Остальные состояния последовательности были затем корректно восстановлены путем повторения обученной модели. Также отображаются соответствующие сгенерированные коэффициенты xi (t). Для сравнения мы отображаем результаты использования динамики, установив значение wij с помощью временного правила Хебба, уравнение (26.3.1). Низкая эффективность корреляции, основанной на Хеббе правило в целом демонстрирует необходимость сочетания динамической системы с соответствующим механизмом обучения.
26.5.4 Негерметичные модели интеграции и пожаротушения \Leaky integrate, fire
Модели негерметичные модели интеграции и огня \ Leaky integrate и fire \ делают еще один шаг в направлении биологического реализма, в котором мембранный потенциал увеличивается, если он получает возбуждающий стимул (wij > 0), и уменьшается, если он получает тормозящий стимул (wij < 0). После срабатывания мембранный потенциал сбрасывается до низкого значения, ниже порога срабатывания, а затем постепенно повышается до уровня покоя (см., например, [62, 108]). Модель, которая включает в себя такие эффекты, как
486 ЧЕРНОВИК от 9 марта 2010 г. Упражнения
Начиная с vi ; {0, 1}, если нейрон i активируется в момент времени t ; 1, потенциал сбрасывается до ;fired, установленного в момент времени t. Аналогично, при отсутствии синаптического ввода потенциал восстанавливается до ;rest с постоянной времени -1/ log ;[15].
Несмотря на усложнение мембранного потенциала по сравнению со случаем Хопфилда, получение соответствующей динамики обучения для этой новой системы проста, поскольку, как и прежде, скрытые переменные (здесь мембранные потенциалы) обновляются детерминированным образом. Производными потенциала являются
Путем инициализации производной dai(t=1)/dwij= 0, уравнения (26.5.5,26.5.11,26.5.12) определяют рекурсию первого порядка для градиента, которая может быть использована для адаптации wij обычным способом wij ; wij + ;dL/dwij . Мы могли бы также применить синаптическую динамику к этому случаю, заменив член vj (t) в уравнении (26.5.12) на xj (t)vj (t).
Несмотря на подробное обсуждение свойств нейронных реакций для сетей, обученных таким образом хотя это выходит за рамки этих заметок, интересным следствием уравнения правил обучения (26.5.12) является зависящее от времени скачка окно обучения, что качественно согласуется с экспериментальными результатами [223, 186].
Подводя итог, можно сказать, что при условии, что мы имеем дело с детерминированной скрытой динамикой, потенциально могут быть изучены произвольно сложные пространственно- временные паттерны и сгенерированы при поиске сигналов для очень сложной нейронной динамики. Модель импульсной реакции [108] можно рассматривать как частный случай детерминированной скрытой переменной модель, в которой скрытые переменные были явно интегрированы.
26.6 Код
demoHopfield.m: Демонстрация обучения последовательности Хопфилда
HebbML.m: Обучение набору последовательностей с использованием метода максимального правдоподобия при подъеме по градиенту
HopfieldHiddenNL.m: Сеть Хопфилда с дополнительными нелинейными скрытыми переменными
demoHopfieldLatent.m: демонстрация сети Хопфилда с детерминированными скрытыми переменными
HopfieldHiddenLikNL.m: Сеть Хопфилда с вероятностью последовательности скрытых переменных
26.7 Упражнения
Упражнение 241. Рассмотрим очень большую сеть Хопфилда V »1, используемую для хранения одной временной последовательности длина v(1 : T ), T «V . В этом случае может быть сложно сохранить весовую матрицу w. Объясните, как обосновать предположение
где ui (t) - два параметра, и выведите правило обновления для двух параметров u.
Упражнение 242. Сеть Хопфилда используется для хранения необработанной несжатой двоичной видеопоследовательности. Каждое изображение в последовательности содержит 106 двоичных пикселей. Сколько часов видео могут сохранить 106 нейронов при скорости 10 кадров в секунду?
Упражнение 243. Выведите уравнение обновления (26.3.22).
Упражнение 244. Покажите, что уравнение Гессена (26.3.16) является отрицательно определенным. То есть
для любого значения x ;0.
ДРАФТ от 9 марта 2010 г. 487 Упражнения
Упражнение 245. Для расширенной сети Хопфилда из раздела (26.4.2) со скрытой динамикой
выведите производные рекурсии, описанные в разделе (26.4.2).
488 ЧЕРНОВИК от 9 марта 2010 года,
23-26Байесовские рассуждения смыслы и машинное обу
© Copyright: Джон Темплтон, 2025
Свидетельство о публикации №125110906800
Свидетельство о публикации №125110906800
Рецензии