После большого перерыва продолжаем цикл о графических вероятностных моделях (часть 1, часть 2). Сегодня мы наконец-то от постановок задач перейдём к алгоритмам; поговорим мы о самом простом, но часто полезном алгоритме вывода на фактор-графах – алгоритме передачи сообщений. Или, как его ещё можно назвать, алгоритме правильной расстановки скобок.
Пример
И начнём сразу с конкретного примера – предположим, что вам нужно подсчитать выражение
Здесь, формально говоря, четыре слагаемых, каждое из трёх сомножителей, всего три сложения и восемь умножений.
Давайте проявим чудеса сообразительности и заметим, что двойная сумма здесь раскладывается в произведение двух одиночных сумм:
Здесь внезапно осталось всего два сложения и два умножения – выгода налицо. Как вы наверняка понимаете, если бы я не поленился написать сумму побольше, выгода бы увеличилась экспоненциально – мы сворачиваем сумму экспоненциального числа слагаемых в произведение линейного числа небольших скобочек.
«Подумаешь, бином Ньютона!» – скажут мне читатели; и будут правы, это действительно на бином Ньютона весьма похоже. А внимательные читатели ещё и удивятся, зачем тут вообще был нужен игрек – действительно, он в этом примере выглядит явно лишним.
Давайте попробуем обобщить тот же самый пример – пусть теперь с нашими переменными вместо умножения происходит какая-то неизвестная функция:
Проходит ли тот же трюк, что выше? Нет, не проходит – мы не знаем никакой связи между разными значениями функции, она для нас чёрный ящик, и выносить за скобку тут нечего, придётся честно применять функцию четыре раза и складывать результаты.
Трюк будет проходить в промежуточном случае – мы по-прежнему оставим в рассмотрении довольно общую функцию, но теперь будем предполагать, что она раскладывается в произведение функции от x и y и функции от y и z (наконец-то y будет уже совсем по делу участвовать):
При такой постановке вопроса мы можем точно так же разложить большую сумму в произведение двух маленьких:
и сильно сэкономить на вычислениях. Заметим, что хотя мы предполагали некую дополнительную структуру у функции от трёх переменных, неверно, что в ней переменные x и z встречались совершенно независимо – они были связаны через y, по которому, по счастливому совпадению, нам суммировать было не нужно. Кстати, заметьте, что результат этого суммирования – функция от y.
В чём мораль этого примера? В том, что если нам нужно суммировать большую функцию, и она раскладывается в произведение функций поменьше, не исключено, что мы можем найти удачное разложение в произведение скобочек…
К вероятностным моделям
… но это и есть ситуация вывода на графической вероятностной модели! Вспомните последовательную связь между переменными, которую мы обсуждали в первой серии:
С вероятностной точки зрения она означает, что совместное распределение раскладывается как
А это и значит, что функция от трёх переменных x, y и z разложилась в произведение функции от x и y и функции от y и z, точь-в-точь как в нашем наивном примере. А суммирование соответствует задаче маргинализации: по данной модели и, возможно, значениям некоторых переменных найти маргинальное распределение вероятностей
и мы теперь понимаем, что это выражение можно существенно упростить как
Задача маргинализации – основная для графических моделей, через неё формализуется всё то, о чём мы говорили в прошлый раз: как обучить веса регрессии, как распознать речь по готовой модели и как обучить модель распознавания из тестовых примеров, как найти рейтинги игроков после очередного турнира, как найти степень вхождения тем в документы из корпуса и так далее.
Фактор-графы и граф в виде цепи
Прелесть всего этого в том, что такие рассуждения не нужно придумывать каждый раз заново, а можно обобщить. Самое прямое обобщение – на цепочку из нескольких событий, связанных последовательной связью:
На этом месте будет удобно немного изменить картинку. Мы до сих пор рисовали только переменные, а функции (распределения вероятностей) при этом подразумевались. В частности, подразумевалось разложение большой функции на множители; например, картинка выше приводит к разложению
Давайте теперь нарисуем это явно:
У нас получился двудольный граф, в котором два сорта вершин соответствуют переменным и функциям. Каждая функция связана с теми переменными, от которых она зависит, а сам граф задаёт разложение большой функции в произведение маленьких. Эта конструкция называется фактор-графом – обратите внимание, что это более общая конструкция, чем байесовская сеть доверия, теперь вероятностное содержание пропало, и мы в принципе можем говорить о разложениях абстрактных функций (не обязательно распределений) в произведение абстрактных функций поменьше (не обязательно условных распределений).
Теперь давайте применим наш трюк к задаче маргинализации относительно xk. Сначала вносим внутрь первую сумму, потом вторую, потом третью и так далее до k-й; в результате получается более компактное представление левой части суммирования, которое к тому же не пересекается с правой частью (простите за длинную формулу, но она здесь гораздо нагляднее слов):
Аналогично можно поступить и с правой частью, и в результате получается
Обратите внимание, какой алгоритм вычисления соответствует нашему трюку: мы начинаем с краёв графа (с самых внутренних скобок) и постепенно идём к середине (точнее, к k-й переменной), сворачивая по дороге суммы. Это можно представить как передачу сообщений от сторон цепочки к середине. На каждом шаге мы по сути делаем одно и то же – получаем результат предыдущих суммирований как функцию от одной переменной hi(xi), а потом сворачиваем её со следующей:
Общий случай
Общий случай алгоритма передачи сообщений – это случай, когда фактор-граф является деревом (т.е. в нём нет циклов). В этом случае можно доказать, что для маргинализации относительно какой-то вершины достаточно:
- рассмотреть эту вершину как временный корень дерева;
- передавать сообщения от листьев по направлению к корню; каждое сообщение является функцией от ровно одной переменной – той, которая соседствует с ребром, по которому это сообщение идёт;
- перемножить все сообщения, пришедшие в корень.
А чтобы определить, когда уже можно передавать сообщения выше, пригодится очень простое и всеобъемлющее правило передачи сообщений: вершина фактор-графа может передать сообщение своему соседу, если она уже получила сообщения от всех других соседей. В частности, у листьев только один сосед, поэтому они начинают передавать туда сообщения сразу же. Вот как пойдут сообщения в типичном дереве (цифрами обозначено, на каком «такте» это сообщение будет порождено; мы сейчас рассматриваем только сообщения, идущие снизу вверх).
Cообщение, которое передаёт узел-переменная – это просто произведение всех полученных им сообщений (в случае листа – тождественная единица):
А чтобы пересчитать сообщение узла-функции, надо провести частичную маргинализацию; если функция 
уже получила сообщения 
от всех переменных 
, она может передать в переменную x сообщение
Функция-лист, соответственно, передаёт своему единственному соседу саму себя (произведение получается пустое). Мы здесь предполагаем, что каждая функция, участвующая в разложении, зависит от достаточно малого числа переменных, чтобы эти суммирования можно было провести «грубой силой» (ну или хоть как-нибудь, если вдруг получится особенно хитрый случай).
Заключение и анонс следующей серии
Алгоритм передачи сообщений работает только тогда, когда фактор-граф является деревом. Если в фактор-графе есть циклы, алгоритм не работает (представьте, что кроме цикла ничего нет – с чего тогда начинать?). Однако в жизни сплошь и рядом попадаются ситуации, когда в фактор-графе циклы всё-таки присутствуют; например, модель LDA для тематического моделирования из прошлой серии вообще состоит из нескольких почти полных двудольных графов, каждый документ связан с каждой темой, там сплошные циклы в фактор-графе.
В следующий раз мы поговорим о том, что можно делать в ситуации, когда в графе циклы присутствуют. Мы уже подходим к границе того, что можно, оставаясь в своём уме, подробно объяснять в популярной статье, рассчитанной на широкую аудиторию, но некоторую интуицию я в следующий раз дать всё-таки постараюсь. А потом, наверное, перейдём к конкретным примерам.
Автор: snikolenko
