Комментарии 2
Сергей, у вас отличные посты. Продолжайте в том же духе.
Вопрос по loopy belief propagation. Я несколько раз сталкивался с граф. моделями, и все никак не мог понять «легитимность» этого алгоритма.
Обычно, в книжках рассуждается так. Вот есть задача марджинализации. В лоб — нерешаемо, придумываем умный способо суммирования пользуясь факторизацией графа. Называем блоки произведений-суммирований «сообщениями» и передаем эти «сообщения» вдоль графа чтобы маргинализовать нужную переменную (или группу переменных).
А потом, внезапно, берут те же «сообщения» и применяют к циклическому графу. Но ведь изначальный смысл маргинализации при этом как-то теряется, и получается что мы оперируем придумаными терминами типа «message passing», забыв откуда это вообще взялось. Так было, к примеру, в курсе pgm на курсере. И еще где-то втречал такой подход…
Не могли бы вы пояснить этот момент, ну или дать ссылку на хорошее описание этого алгоритма.
Вопрос по loopy belief propagation. Я несколько раз сталкивался с граф. моделями, и все никак не мог понять «легитимность» этого алгоритма.
Обычно, в книжках рассуждается так. Вот есть задача марджинализации. В лоб — нерешаемо, придумываем умный способо суммирования пользуясь факторизацией графа. Называем блоки произведений-суммирований «сообщениями» и передаем эти «сообщения» вдоль графа чтобы маргинализовать нужную переменную (или группу переменных).
А потом, внезапно, берут те же «сообщения» и применяют к циклическому графу. Но ведь изначальный смысл маргинализации при этом как-то теряется, и получается что мы оперируем придумаными терминами типа «message passing», забыв откуда это вообще взялось. Так было, к примеру, в курсе pgm на курсере. И еще где-то втречал такой подход…
Не могли бы вы пояснить этот момент, ну или дать ссылку на хорошее описание этого алгоритма.
Это вопрос одновременно сложный и простой. Сложная часть в том, что я действительно не умею хорошо объяснить, почему вдруг loopy belief propagation (LBP) эффективен. Простая часть ответа — в том, что для определённых достаточно широких классов сетей и распределений доказано, что действительно при каждой итерации LBP приближённое распределение становится ближе (либо по специально определённой мере, либо вообще просто по расстоянию Кульбака-Лейблера) к истинному распределению. Таким образом, LBP — это просто алгоритм приближённого вывода, находит локальный максимум «похожести» распределений, возможно, не попадает при этом в глобальный.
Пара статей на тему:
machinelearning.wustl.edu/mlpapers/paper_files/IhlerFW05.pdf
www.stanford.edu/~montanar/TEACHING/Stat375/papers/tatikonda.pdf
Пара статей на тему:
machinelearning.wustl.edu/mlpapers/paper_files/IhlerFW05.pdf
www.stanford.edu/~montanar/TEACHING/Stat375/papers/tatikonda.pdf
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вероятностные модели: борьба с циклами и вариационные приближения