🤖 Вероятностный вывод в байесовских сетях: от точных методов к сэмплированию 0:05
Лекция 13 курса Stanford CS221 посвящена методам байесовских сетей — мощного инструмента для представления мира и неопределенностей в нем. В качестве отправной точки используется концепция совместного распределения вероятностей как некой «базы данных». Хотя точный вывод путем формирования этого распределения математически корректен, он становится вычислительно невозможным при наличии большого количества переменных (например, $2^{100}$ комбинаций для 100 переменных). Для решения этой проблемы используются методы аппроксимации: сэмплирование с отклонением (rejection sampling) и сэмплирование Гиббса (Gibbs sampling).
🎲 Аппроксимация: от сэмплирования с отклонением к методу Гиббса 10:15
Сэмплирование с отклонением основано на идее прогона вероятностной программы, которая возвращает выборку из совместного распределения, после чего отбрасываются все результаты, не удовлетворяющие условиям задачи. Однако, по мнению лектора, этот метод крайне неэффективен, если evidence (свидетельство) встречается редко — можно провести миллионы итераций и не получить ни одного подходящего события.
Метод Гиббса — это итеративный подход, который является частным случаем алгоритмов цепей Маркова — Монте-Карло (MCMC).
- Принцип работы: Вместо того чтобы начинать с чистого листа, алгоритм начинает с произвольного допустимого присваивания значений переменным. Затем он итеративно меняет значение одной переменной за раз, основываясь на условном распределении, зависящем от всех остальных переменных.
- Преимущества: В методе Гиббса нет стадии отбрасывания (rejection), так как каждое сэмплирование учитывает доказательства.
- Недостатки: Выборки коррелированы (не являются независимыми), что требует большего количества итераций для получения точной оценки. Также алгоритм может «застрять» при наличии жестких корреляций между переменными.
🛠 Оптимизация: Марковское одеяло 39:37
Для ускорения вычислений в методе Гиббса используется концепция «марковского одеяла» (Markov blanket). Суть идеи заключается в том, что при обновлении значения конкретной переменной нет нужды учитывать всю байесовскую сеть целиком — достаточно ограничиться её «соседями».
- Марковское одеяло: Включает в себя всех детей и родителей узла.
- Эффективность: Вычисления становятся значительно быстрее, если размер этого «одеяла» невелик, так как алгоритму приходится учитывать только локальные условные вероятности.
🔗 Условная независимость и анализ графов 58:41
Важной частью работы с байесовскими сетями является понимание независимости переменных, которая тесно связана со структурой графа. Лектор подчеркивает, что визуальная связность не всегда означает статистическую зависимость (и наоборот).
Для определения того, являются ли две переменные условно независимыми при заданных условиях, применяется алгоритм работы с графами:
- Закрасить (учесть) узлы-свидетели.
- Рекурсивно удалить все незакрашенные «листья» графа.
- Соединить родителей узлов (процесс, который лектор называет «женитьбой родителей»).
- Проверить, существует ли путь между интересующими переменными, не проходящий через закрашенные узлы.
Если такой путь отсутствует, переменные считаются условно независимыми. Этот графический подход позволяет эффективно анализировать сложные сети, не прибегая к тяжелым вычислениям с тензорами.
