Иерархический SMT

Иерархический SMT (от англ. Hierarchical Sequential Monte Carlo, иерархический последовательный метод Монте-Карло) — это класс вычислительных алгоритмов, предназначенных для аппроксимации сложных вероятностных распределений, характеризующихся иерархической структурой. Метод объединяет принципы байесовского вывода, иерархического моделирования и методов Монте-Карло по схеме марковской цепи (MCMC) с последовательным важностным отбором (SMC), также известным как фильтр частиц. Основное отличие иерархического SMT от классического SMC заключается в том, что он позволяет эффективно оценивать параметры и скрытые переменные в моделях, где одни параметры (гиперпараметры) влияют на распределение других параметров, образуя многоуровневую структуру. Метод применяется в задачах, где требуется совместное обучение иерархических моделей, например, в машинном обучении, обработке сигналов, биоинформатике и экономике.

История

Иерархический SMT возник как развитие идей последовательного Монте-Карло, которые были формализованы в 1990-х годах в работах Н. Гордона, Д. Салмонда и А. Смита (алгоритм фильтра частиц). Однако классический SMC был ориентирован на модели с фиксированными параметрами, не учитывающими иерархию. В начале 2000-х годов, с ростом интереса к иерархическим байесовским моделям, исследователи начали адаптировать SMC для работы с многоуровневыми структурами. Ключевой вклад внесли работы П. Дель Мораля (2006), который предложил обобщённую схему последовательного важностного отбора для иерархических моделей, и А. Дусе (2010), который развил методы сглаживания и фильтрации в иерархических контекстах. В 2010-х годах иерархический SMT получил развитие в области машинного обучения, в частности, в работах по вариационному выводу и глубокому обучению, где он использовался для обучения вероятностных нейронных сетей. В России исследования в этой области ведутся, в частности, в Вычислительном центре РАН и на факультете вычислительной математики и кибернетики МГУ имени М. В. Ломоносова.

Основные принципы

Иерархическая модель

Иерархическая байесовская модель предполагает, что наблюдаемые данные \( y \) порождаются скрытыми переменными \( x \), которые, в свою очередь, зависят от гиперпараметров \( \theta \). Совместное распределение имеет вид:

\[ p(y, x, \theta) = p(y | x) \cdot p(x | \theta) \cdot p(\theta) \]

где:

• \( p(y | x) \) — функция правдоподобия,
• \( p(x | \theta) \) — априорное распределение скрытых переменных,
• \( p(\theta) \) — априорное распределение гиперпараметров.

Цель вывода — оценить апостериорное распределение \( p(x, \theta | y) \), которое часто является многомерным и сложным для аналитического вычисления.

Последовательный метод Монте-Карло (SMC)

Классический SMC аппроксимирует апостериорное распределение последовательности скрытых состояний \( x_{1:T} \) по мере поступления данных \( y_{1:T} \). Он использует набор взвешенных частиц (выборок), которые эволюционируют во времени через этапы предсказания, обновления и пересэмплирования. В иерархическом SMT эта схема обобщается на случай, когда гиперпараметры \( \theta \) также являются случайными и подлежат оценке.

Иерархический SMC

Иерархический SMT объединяет два уровня частиц:

1. Верхний уровень — частицы для гиперпараметров \( \theta \).
2. Нижний уровень — для каждого набора гиперпараметров запускается свой набор частиц для скрытых переменных \( x \).

Алгоритм работает следующим образом:

• Начальная инициализация: генерируется \( N \) частиц для \( \theta \) из априорного распределения \( p(\theta) \).
• Для каждой частицы \( \theta^{(i)} \) запускается стандартный SMC для \( x \) с использованием \( p(x | \theta^{(i)}) \).
• Веса частиц верхнего уровня обновляются на основе маргинального правдоподобия, вычисленного по нижнему уровню.
• Периодически выполняется пересэмплирование на обоих уровнях для борьбы с вырождением весов.

Классификация и виды

Иерархический SMT можно классифицировать по нескольким признакам:

По способу обновления гиперпараметров

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

По типу модели

• Линейные гауссовские модели: аналитически решаемые случаи, где иерархический SMC может быть заменён фильтром Калмана.
• Нелинейные негауссовские модели: основная область применения иерархического SMT, где требуется численная аппроксимация.

По числу уровней

• Двухуровневые: один уровень гиперпараметров и один уровень скрытых переменных.
• Многоуровневые: более двух уровней иерархии, например, в моделях глубокого обучения.

Применение

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

Машинное обучение

• Обучение вероятностных нейронных сетей: иерархический SMC позволяет оценивать веса сети и гиперпараметры (например, параметры регуляризации) одновременно.
• Байесовская оптимизация: метод используется для аппроксимации апостериорного распределения в задачах оптимизации чёрных ящиков.
• Тематическое моделирование: в моделях типа LDA (Latent Dirichlet Allocation) иерархический SMC применяется для оценки распределений тем и гиперпараметров.

Обработка сигналов

• Трекинг объектов: в задачах слежения за движущимися объектами иерархический SMC позволяет учитывать изменение динамики (например, ускорение) как гиперпараметр.
• Обработка аудиосигналов: метод используется для разделения источников звука при неизвестной акустической среде.

Биоинформатика

• Филогенетика: иерархический SMC применяется для оценки эволюционных деревьев и скорости мутаций.
• Анализ экспрессии генов: метод позволяет моделировать иерархические зависимости между генами и условиями эксперимента.

Экономика и финансы

• Стохастическая волатильность: иерархический SMC используется для оценки параметров моделей волатильности, где волатильность сама является скрытым процессом.
• Прогнозирование временных рядов: метод применяется для совместного обучения моделей ARIMA и GARCH с иерархическими гиперпараметрами.

Преимущества и недостатки

Преимущества

• Гибкость: иерархический SMC может работать с любыми нелинейными и негауссовскими моделями.
• Адаптивность: метод позволяет обновлять оценки в реальном времени по мере поступления данных.
• Точность: при достаточном числе частиц иерархический SMC даёт состоятельные оценки апостериорного распределения.

Недостатки

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

Реализации

Иерархический SMT реализован в нескольких библиотеках для научных вычислений:

• PyMC (Python): библиотека для вероятностного программирования, поддерживающая иерархические модели и SMC.
• Stan (C++/Python): программный пакет для байесовского вывода, включающий алгоритмы MCMC и SMC.
• BayesFlux (Julia): библиотека для байесовского обучения нейронных сетей с использованием иерархического SMC.
• MATLAB Statistics Toolbox: содержит функции для SMC, которые могут быть расширены для иерархических моделей.

Интересные факты

• Иерархический SMT является одним из немногих методов, который позволяет одновременно оценивать параметры модели и их априорные распределения, что делает его мощным инструментом для автоматического выбора модели.
• В 2018 году группа исследователей из Массачусетского технологического института (MIT) предложила модификацию иерархического SMC для обучения глубоких вероятностных моделей, что позволило улучшить качество генерации изображений.
• В России иерархический SMC применяется в задачах обработки радиолокационных сигналов для оценки параметров движущихся целей, что связано с работами Института радиотехники и электроники РАН.

Источники

• Doucet, A., de Freitas, N., & Gordon, N. (2001). Sequential Monte Carlo Methods in Practice. Springer.
• Del Moral, P. (2004). Feynman-Kac Formulae: Genealogical and Interacting Particle Systems with Applications. Springer.
• Murphy, K. P. (2012). Machine Learning: A Probabilistic Perspective. MIT Press.
• Carpenter, B., et al. (2017). Stan: A Probabilistic Programming Language. Journal of Statistical Software.
• Salakhutdinov, R., & Hinton, G. (2009). Deep Boltzmann Machines. Proceedings of the International Conference on Artificial Intelligence and Statistics.