Случайное блуждание с максимальной энтропией - Википедия - Maximal entropy random walk

Случайное блуждание с максимальной энтропией (MERW) - популярный тип предвзятое случайное блуждание по графику, в котором вероятности переходов выбираются в соответствии с принцип максимальной энтропии, в котором говорится, что распределение вероятностей, которое лучше всего представляет текущее состояние знаний, имеет наибольшую энтропию. Хотя стандарт случайная прогулка выбирает для каждой вершины равномерное распределение вероятностей среди исходящих ребер, локально максимизируя скорость энтропии, MERW максимизирует его глобально (среднее производство энтропии), предполагая равномерное распределение вероятностей среди всех путей в данном графе.

MERW используется в различных областях науки. Прямое приложение - выбор вероятностей для максимизации скорости передачи через ограниченный канал, аналогично Кодирование Фибоначчи. Его свойства также сделали его полезным, например, при анализе сложных сетей,[1] как предсказание ссылок,[2] обнаружение сообщества,[3]надежный транспорт по сетям[4] и центральность меры.[5] Также в анализ изображений, например, для обнаружения областей визуальной заметности,[6] локализация объекта,[7] обнаружение взлома[8] или же трактография проблема.[9]

Кроме того, он воссоздает некоторые свойства квантовая механика, предлагая способ устранить несоответствие между распространение модели и квантовые предсказания, например Локализация Андерсона.[10]

Базовая модель

Оставили: базовая концепция типичного случайного блуждания (GRW) и случайного блуждания с максимальной энтропией (MERW)
Правильно: пример их эволюции на одной и той же неоднородной двумерной решетке с циклическими граничными условиями - плотность вероятности после 10, 100 и 1000 шагов при старте из одной и той же вершины. Маленькие прямоугольники представляют собой дефекты: все вершины, кроме отмеченных, имеют дополнительные петля (край к себе). Для правильных решеток (без дефектов) GRW и MERW идентичны. Хотя дефекты не сильно влияют на локальное поведение, здесь они приводят к совершенно другой глобальной стационарной вероятности. Пока GRW (и на ее основе стандарт распространение ) приводит к почти однородной стационарной плотности, MERW обладает сильным свойством локализации, запирая ходоков в энтропийные ямы по аналогии с электронами в дефектной решетке полупроводник.

Рассмотрим график с вершины, определяемые матрица смежности : если есть ребро из вершины к , 0 в противном случае. Для простоты предположим, что это неориентированный граф, что соответствует симметричной ; однако MERW можно также обобщить для направленных и взвешенные графики (Например Распределение Больцмана среди дорожек вместо униформы).

Мы хотели бы выбрать случайное блуждание в качестве Марковский процесс на этом графе: для каждой вершины и его исходящий край к , выберите вероятность ходунка, случайно использующего это ребро после посещения . Формально найти стохастическая матрица (содержащий переходные вероятности цепи Маркова) такой, что

  • для всех и
  • для всех .

Предполагая, что этот график связан, а не периодический, эргодическая теория говорит, что эволюция этого случайный процесс приводит к некоторому стационарному распределению вероятностей такой, что .

С помощью Энтропия Шеннона для каждой вершины и усредняя вероятность посещения этой вершины (чтобы иметь возможность использовать ее энтропию), мы получаем следующую формулу для среднего производства энтропии (скорость энтропии ) случайного процесса:

Это определение оказывается эквивалентным средней асимптотической энтропии (на длину) распределения вероятностей в пространстве путей для этого случайного процесса.

В стандартном случайном блуждании, называемом здесь типовым случайным блужданием (GRW), мы, естественно, выбираем, что каждое исходящее ребро является равновероятным:

.

Для симметричного это приводит к стационарному распределению вероятностей с

.

Он локально максимизирует производство энтропии (неопределенность) для каждой вершины, но обычно приводит к субоптимальному усредненному глобальному уровню энтропии. .

MERW выбирает стохастическую матрицу, которая максимизирует , или, что то же самое, предполагает равномерное распределение вероятностей среди всех путей в данном графе. Его формула получается путем вычисления сначала доминирующего собственное значение и соответствующие собственный вектор матрицы смежности, т.е. наибольший с соответствующими такой, что . Тогда стохастическая матрица и стационарное распределение вероятностей имеют вид

для которого все возможные пути длины от -го к -я вершина имеет вероятность

.

Скорость его энтропии равна и стационарное распределение вероятностей является

.

В отличие от GRW, вероятности перехода MERW обычно зависят от структуры всего графа (являются нелокальными). Следовательно, их не следует воображать как непосредственно применяемые пешеходом - если случайные решения принимаются на основе местной ситуации, как это сделал бы человек, подход GRW более уместен. MERW основан на принцип максимальной энтропии, что делает его самым безопасным предположением, когда у нас нет дополнительных знаний о системе. Например, это было бы уместно для моделирования наших знаний об объекте, выполняющем сложную динамику - не обязательно случайную, как частица.

Эскиз вывода

Предположим для простоты, что рассматриваемый граф косвенный, связный и апериодический, что позволяет сделать вывод из Теорема Перрона-Фробениуса что доминирующий собственный вектор уникален. Следовательно может быть асимптотически () приблизительно (или же в обозначение бюстгальтера ).

MERW требует равномерного распределения по трассам. Номер дорожек длиной и вершина в центре

,

следовательно для всех ,

.

Аналогично вычисляя распределение вероятностей для двух следующих друг за другом вершин, получаем, что вероятность оказаться в -й вершине и следующей в -я вершина

.

Делим на вероятность оказаться в -я вершина, т.е. , дает для условная возможность из -я вершина следующая после -я вершина

.

Примеры

Слева: выбор оптимальной вероятности после символа 0 в Кодирование Фибоначчи. Справа: одномерная дефектная решетка и ее стационарная плотность на длине 1000 циклов (имеется три дефекта). В то время как в стандартном случайном блуждании стационарная плотность пропорциональна степени вершины, что приводит к разнице в 3/2, в MERW плотность почти полностью локализована в самой большой бездефектной области, аналогично основное состояние предсказано квантовая механика.

Давайте сначала посмотрим на простую нетривиальную ситуацию: Кодирование Фибоначчи, где мы хотим передать сообщение как последовательность нулей и единиц, но не используя две последовательные единицы: после единицы должен быть 0. Чтобы максимизировать количество информации, передаваемой в такой последовательности, мы должны предположить равномерное распределение вероятностей в пространстве всех возможных последовательностей, выполняющих это ограничение. Чтобы практически использовать такие длинные последовательности, после 1 мы должны использовать 0, но остается свобода выбора вероятности 0 после 0. Обозначим эту вероятность как , тогда энтропийное кодирование позволит кодировать сообщение с использованием этого выбранного распределения вероятностей. Стационарное распределение вероятностей символов для данного оказывается . Следовательно, производство энтропии , которая максимальна для , известный как Золотое сечение. Напротив, стандартное случайное блуждание выбрало бы неоптимальный . Выбирая больше уменьшает количество информации, производимой после 0, а также уменьшает частоту 1, после чего мы не можем записывать какую-либо информацию.

Более сложным примером является одномерная циклическая решетка с дефектами: скажем, 1000 узлов, соединенных в кольцо, для которых все узлы, кроме дефектов, имеют петлю (ребро к себе). В стандартном случайном блуждании (GRW) стационарное распределение вероятностей будет иметь вероятность дефекта, равную 2/3 вероятности вершин без дефекта - локализации почти нет, также аналогично для стандартных распространение, что является бесконечно малым пределом GRW. Для MERW мы должны сначала найти доминирующий собственный вектор матрицы смежности - максимизируя в:

на все позиции , куда для дефектов, 0 в противном случае. Подстановка и умножая уравнение на −1, получаем:

куда сейчас сводится к минимуму, становясь аналогом энергии. Формула внутри скобок: дискретный оператор Лапласа, что делает это уравнение дискретным аналогом стационарного Уравнение Шредингера. Как в квантовая механика, MERW предсказывает, что распределение вероятностей должно привести точно к распределению квантовых основное состояние: с его сильно локализованной плотностью (в отличие от стандартной диффузии). Принимая бесконечно малый предела, мы можем получить стандартное непрерывное стационарное (не зависящее от времени) уравнение Шредингера ( за ) здесь.[11]

Смотрите также

Рекомендации

  1. ^ Синатра, Роберта; Гомес-Гарденьес, Хесус; Ламбьотт, Рено; Никосия, Винченцо; Латора, Вито (2011). «Максимально-энтропийные случайные блуждания в сложных сетях с ограниченной информацией» (PDF). Физический обзор E. 83 (3): 030103. arXiv:1007.4936. Bibcode:2011PhRvE..83c0103S. Дои:10.1103 / PhysRevE.83.030103. ISSN  1539-3755. PMID  21517435.
  2. ^ Ли, Ронг-Хуа; Ю, Джеффри Сюй; Лю, Цзяньцюань (2011). Предсказание ссылки: сила случайного блуждания с максимальной энтропией (PDF). Ассоциация вычислительной техники Конференция по управлению информацией и знаниями. п. 1147. Дои:10.1145/2063576.2063741.
  3. ^ Ochab, J.K .; Бурда, З. (2013). «Максимальное случайное блуждание энтропии в обнаружении сообщества». Специальные темы Европейского физического журнала. 216 (1): 73–81. arXiv:1208.3688. Bibcode:2013EPJST.216 ... 73O. Дои:10.1140 / epjst / e2013-01730-6. ISSN  1951-6355.
  4. ^ Chen, Y .; Георгиу, Т.Т .; Павон, М .; Танненбаум, А. (2016). «Надежный транспорт по сетям». IEEE Transactions по автоматическому контролю. 62 (9): 4675–4682. arXiv:1603.08129. Bibcode:2016arXiv160308129C. Дои:10.1109 / TAC.2016.2626796. ЧВК  5600536. PMID  28924302.
  5. ^ Дельвенн, Жан-Шарль; Либерт, Энн-Софи (2011). «Меры центральности и термодинамический формализм для сложных сетей». Физический обзор E. 83 (4): 046117. arXiv:0710.3972. Bibcode:2011PhRvE..83d6117D. Дои:10.1103 / PhysRevE.83.046117. ISSN  1539-3755. PMID  21599250.
  6. ^ Джин-Ган Ю; Цзи Чжао; Джинвен Тиан; Ихуа Тан (2014). «Максимальная энтропия случайного блуждания для визуальной заметности на основе региона». IEEE Transactions по кибернетике. Институт инженеров по электротехнике и радиоэлектронике (IEEE). 44 (9): 1661–1672. Дои:10.1109 / tcyb.2013.2292054. ISSN  2168-2267. PMID  25137693.
  7. ^ Л. Ван, Дж. Чжао, Х. Ху, Дж. Лу, Локализация слабо контролируемого объекта посредством случайного блуждания с максимальной энтропией, МЦИП, 2014.
  8. ^ Корус, Павел; Хуанг, Цзиву (2016). «Улучшенная локализация взлома в судебной экспертизе цифровых изображений на основе случайного блуждания с максимальной энтропией». Письма об обработке сигналов IEEE. Институт инженеров по электротехнике и радиоэлектронике (IEEE). 23 (1): 169–173. Bibcode:2016ISPL ... 23..169K. Дои:10.1109 / lsp.2015.2507598. ISSN  1070-9908.
  9. ^ Галинский, Виталий Л .; Франк, Лоуренс Р. (2015). «Одновременная многомасштабная оценка диффузии и трактография на основе путей энтропийного спектра». IEEE Transactions по медицинской визуализации. Институт инженеров по электротехнике и радиоэлектронике (IEEE). 34 (5): 1177–1193. Дои:10.1109 / tmi.2014.2380812. ISSN  0278-0062. ЧВК  4417445. PMID  25532167.
  10. ^ Burda, Z .; Duda, J .; Удача, Дж. М .; Вацлав Б. (23 апреля 2009 г.). «Локализация случайного блуждания с максимальной энтропией». Письма с физическими проверками. 102 (16): 160602. arXiv:0810.4113. Bibcode:2009ПхРвЛ.102п0602Б. Дои:10.1103 / Physrevlett.102.160602. ISSN  0031-9007. PMID  19518691.
  11. ^ Я. Дуда, Расширенное случайное блуждание с максимальной энтропией, Кандидатская диссертация, 2012.

внешняя ссылка