Байесовские сети: от структуры к обучению параметров 0:17
Байесовские сети представляют собой мощный инструмент для компактного представления совместных распределений вероятностей путём кодирования предположений о условной независимости переменных. В курсе Stanford AA228 рассматриваются методы перехода от полностью известных сетей к обучению параметров и структуры непосредственно на основе имеющихся данных.
Основы и нотация 3:43
Для формализации работы с сетями используется стандартная нотация:
- $X_1, \dots, X_N$: набор дискретных случайных переменных.
- $R_i$: число возможных состояний (инстанциаций) узла $X_i$.
- $Q_i$: число возможных конфигураций родителей узла $X_i$.
- $P_{ij}$: $j$-я конфигурация родителей узла $X_i$.
Конфигурации родителей рассчитываются как произведение $R_i$ соответствующих родительских узлов. Важно сохранять консистентность маппинга этих конфигураций, порядок строк в таблице не имеет принципиального значения.
Обучение параметров: MLE против Байесовского подхода 7:57
Одной из центральных задач является поиск оптимальных параметров $\theta_{ijk}$, определяющих вероятность того, что $X_i = k$ при родительской конфигурации $j$.
Максимальное правдоподобие (MLE) 11:08
Метод максимального правдоподобия ищет параметры $\hat{\theta}$, максимизирующие вероятность наблюдаемых данных $D$ при известной структуре графа $G$. Оптимальные параметры рассчитываются как отношение количества наблюдений конкретного состояния к общему числу наблюдений данной родительской конфигурации:
$$\hat{\theta}{ijk} = \frac{M{ijk}}{\sum_{k'} M_{ijk'}}$$
Спикер отмечает существенный недостаток MLE: если событие не было зафиксировано в данных, модель присвоит ему вероятность 0%, что противоречит интуитивным представлениям о мире (например, если в обучающей выборке не было дождя с зонтом, модель «забудет» о такой возможности).
Байесовское обучение 19:52
Байесовский подход вместо точечной оценки ищет распределение вероятностей параметров, используя распределение Дирихле (обобщение бета-распределения) с псевдосчётчиками $\alpha$.
- Псевдосчётчики $\alpha$ интерпретируются как априорные данные: чем они выше, тем выше уверенность в модели.
- При поступлении новых данных параметры распределения Дирихле обновляются простым прибавлением наблюдаемых частот $M_{ijk}$ к априорным $\alpha_{ijk}$.
Обучение структуры графа 37:27
Для поиска наилучшей структуры графа необходимо ввести объективную меру — Байесовский счёт (Bayesian score), который позволяет оценить вероятность графа при данных $P(G|D)$.
- Баланс сложности: Использование счёта автоматически наказывает модель за избыточную сложность при малом объёме данных, предотвращая переобучение.
- Реализация: При имплементации критически важно использовать логарифмирование (log-trick) для работы с вероятностями во избежание численных ошибок и использовать встроенные функции
loggamma.
Алгоритмы поиска структуры 52:36
Из-за огромного пространства возможных структур поиск глобального оптимума является сложной задачей:
- Алгоритм K2: Жадный алгоритм с полиномиальным временем работы, требующий задания фиксированного порядка узлов, который предотвращает возникновение циклов. Не гарантирует нахождение глобального оптимума.
- Локальный поиск (Local Search): Начинается с произвольного графа. На каждом шаге совершаются базовые операции (добавление, удаление или инверсия ребра) для поиска графа с лучшим счётом.
- Методы преодоления локальных оптимумов: Случайные перезапуски (randomized restarts), имитация отжига (simulated annealing) и генетические алгоритмы.
Марковская эквивалентность
Две структуры графа называются марковски эквивалентными, если они кодируют идентичные предположения об условной независимости. Для проверки эквивалентности достаточно убедиться, что:
- Графы имеют одинаковые ненаправленные ребра.
- Графы имеют одинаковый набор «аморальных» V-структур (где родители не соединены между собой).
Поиск по пространствам эквивалентности эффективнее, так как это пространство значительно меньше пространства всех возможных графов.
