Алгоритм распространения доверия |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2021-08-24 19:25 Длинная статья про алгоритм распространения доверия - belief propagation. Этот алгоритм используется для быстрого решения таких задач, как вероятностные выводы, декодирование сигналов, сэмплирование конфигураций спиновых стекол и т.д. Декодирование турбо-кодов, используемых в сетях 3G и 4G, разгадывание кроссвордов и судоку тоже можно рассматривать как разновидности алгоритма распространения доверия. Например, при вероятностном выводе у нас имеется граф событий (как на картинке слева - состояния и симптомы пациента, который то ли здоров, то ли простужен - это нам нужно выяснить), соединенных друг с другом причинно-следственными связями. Эти связи задаются количественно условными вероятностями P(x_i | x_j), а вероятности некоторых событий P(x_i) уже известны из эксперимента. Задача состоит в том, чтобы вычислить маргинальные вероятности других событий по цепочкам причинно-следственных связей. Перечисленные выше задачи могут быть сведены к задаче о неориентированной марковской сети. В этой задаче совместная вероятность всех событий p({x_i}) получается перемножением одноузельных ?_i(x_i) и парных ?_ij(x_i, x_j) факторов. На картинке справа сверху показано, как сеть причинно-следственных связей может быть сведена к марковской цепи: кружочки означают события, а квадраты - действующие на них факторы. С точностью до переобозначений задача о марковской сети сводится к модели спинового стекла, где парные факторы отвечают за взаимодействие спинов, а одноузельные - за внешние поля. Для расчета вероятностей событий нужно провести маргинализацию совместного распределения, то есть P(x_k) - это сумма p({x_i}) по всем переменным кроме x_k. При большом числе узлов проведение такого расчета "в лоб" требует экспоненциально большого времени, и алгоритм распространения доверия позволяет решить ее значительно быстрее. В алгоритме распространения доверия считается, что узлы обмениваются между собой "сообщениями" m_ij(x_j), как показано на рисунке справа внизу. Величина m_ij(x_j) определяет "веру" узла i в то, что узел j находится в состоянии x_j. Оценка искомой вероятности P(x_i) получается перемножением одноузельного фактора ?_i(x_i) и сообщений, приходящих в наш узел от всех соседних узлов. Доверие распространяется по сети последовательно, от каждого узла к соседним, поэтому расчет величин m_ij(x_j) - очень быстрый процесс, если граф не имеет замкнутых петель. А при наличии петель возникают проблемы: можно повторять вычисления, обходя петли много раз и надеясь на сходимость, которая не обязательно достигается. В этих случаях используются разные приближения и обобщения метода. https://www.semanticscholar.org/paper/Understanding-belief-propagation-and-its-Yedidia-Freeman/05a281df21f4cb2b01e7751c50a4cba3ae0b992f Источник: www.semanticscholar.org Комментарии: |
|