Случайное блуждание с максимальной энтропией

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

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

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

Базовая модель [ править ]

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

Рассмотрим граф с вершинами, определяемый матрицей смежности : если есть ребро от вершины до , 0 в противном случае. Для простоты предположим, что это неориентированный граф , который соответствует симметричному ; однако MERW также может быть обобщен для ориентированных и взвешенных графов (например, распределение Больцмана между путями вместо равномерного).${\ displaystyle n}$ ${\ Displaystyle А \ в \ влево \ {0,1 \ вправо \} ^ {п \ раз п}}$${\ displaystyle A_ {ij} = 1}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle A}$

Мы хотели бы выбрать случайное блуждание в качестве марковского процесса на этом графе: для каждой вершины и ее исходящего ребра выбираем вероятность того, что пешеход будет случайным образом использовать это ребро после посещения . Формально найдите стохастическую матрицу (содержащую переходные вероятности цепи Маркова) такую, что${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle S_ {ij}}$${\ displaystyle i}$ ${\ displaystyle S}$

• ${\ Displaystyle 0 \ leq S_ {ij} \ leq A_ {ij}}$для всех и${\displaystyle i,j}$
• ${\displaystyle \sum _{j=1}^{n}S_{ij}=1}$для всех .${\displaystyle i}$

Предполагая, что этот граф связан, а не периодичен , эргодическая теория утверждает, что эволюция этого случайного процесса приводит к некоторому стационарному распределению вероятностей , так что .${\displaystyle \rho }$${\displaystyle \rho S=\rho }$

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

${\displaystyle H(S)=\sum _{i=1}^{n}\rho _{i}\sum _{j=1}^{n}S_{ij}\log(1/S_{ij})}$

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

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

${\displaystyle S_{ij}={\frac {A_{ij}}{\sum \limits _{k=1}^{n}A_{ik}}}}$.

Для симметричного это приводит к стационарному распределению вероятностей с${\displaystyle A}$${\displaystyle \rho }$

${\displaystyle \rho _{i}={\frac {\sum \limits _{j=1}^{n}A_{ij}}{\sum \limits _{i=1}^{n}\sum \limits _{j=1}^{n}A_{ij}}}}$.

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

MERW выбирает стохастическую матрицу, которая максимизирует или, что эквивалентно, предполагает равномерное распределение вероятностей среди всех путей в данном графе. Его формула получается путем сначала вычисления доминирующего собственного значения и соответствующего собственного вектора матрицы смежности, т. Е. Наибольшего с соответствующим таким, что . Тогда стохастическая матрица и стационарное распределение вероятностей имеют вид${\displaystyle H(S)}$ ${\displaystyle \lambda }$ ${\displaystyle \psi }$${\displaystyle \lambda \in \mathbb {R} }$${\displaystyle \psi \in \mathbb {R} ^{n}}$${\displaystyle \psi A=\lambda \psi }$

${\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}}$

для которого каждый возможный путь длины от -й до -й вершины имеет вероятность${\displaystyle l}$${\displaystyle i}$${\displaystyle j}$

${\displaystyle {\frac {1}{\lambda ^{l}}}{\frac {\psi _{j}}{\psi _{i}}}}$.

Скорость энтропии равна, а стационарное распределение вероятностей равно${\displaystyle \log(\lambda )}$${\displaystyle \rho }$

${\displaystyle \rho _{i}={\frac {\psi _{i}^{2}}{\psi ^{2}}}}$.

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

Эскиз вывода [ править ]

Предположим для простоты, что рассматриваемый граф является непрямым, связным и апериодическим, что позволяет сделать вывод из теоремы Перрона-Фробениуса о единственности доминирующего собственного вектора. Следовательно, можно асимптотически ( ) аппроксимировать (или в обозначениях бра-кета ).${\displaystyle A^{l}}$${\displaystyle l\rightarrow \infty }$${\displaystyle \lambda ^{l}\psi \psi ^{T}}$${\displaystyle \lambda ^{l}|\psi \rangle \langle \psi |}$

MERW требует равномерного распределения по трассам. Количество путей с длиной и вершиной в центре равно${\displaystyle m_{il}}$${\displaystyle 2l}$${\displaystyle i}$

${\displaystyle m_{il}=\sum _{j=1}^{n}\sum _{k=1}^{n}\left(A^{l}\right)_{ji}\left(A^{l}\right)_{ik}\approx \sum _{j=1}^{n}\sum _{k=1}^{n}\left(\lambda ^{l}\psi \psi ^{\top }\right)_{ji}\left(\lambda ^{l}\psi \psi ^{\top }\right)_{ik}=\sum _{j=1}^{n}\sum _{k=1}^{n}\lambda ^{2l}\psi _{j}\psi _{i}\psi _{i}\psi _{k}=\lambda ^{2l}\psi _{i}^{2}\underbrace {\sum _{j=1}^{n}\psi _{j}\sum _{k=1}^{n}\psi _{k}} _{=:b}}$,

следовательно для всех ,${\displaystyle i}$

${\displaystyle \rho _{i}=\lim _{l\rightarrow \infty }{\frac {m_{il}}{\sum \limits _{k=1}^{n}m_{kl}}}=\lim _{l\rightarrow \infty }{\frac {\lambda ^{2l}\psi _{i}^{2}b}{\sum \limits _{k=1}^{n}\lambda ^{2l}\psi _{k}^{2}b}}=\lim _{l\rightarrow \infty }{\frac {\psi _{i}^{2}}{\sum \limits _{k=1}^{n}\psi _{k}^{2}}}={\frac {\psi _{i}^{2}}{\sum \limits _{k=1}^{n}\psi _{k}^{2}}}={\frac {\psi _{i}^{2}}{\psi ^{2}}}}$.

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

${\displaystyle {\frac {\psi _{i}A_{ij}\psi _{j}}{\sum \limits _{i'=1}^{n}\sum \limits _{j'=1}^{n}\psi _{i'}A_{i'j'}\psi _{j'}}}={\frac {\psi _{i}A_{ij}\psi _{j}}{\psi A\psi ^{\top }}}={\frac {\psi _{i}A_{ij}\psi _{j}}{\lambda \psi ^{2}}}}$.

Деление на вероятность оказаться в -й вершине, т. Е. Дает для условной вероятности, что -я вершина будет следующей после -й вершины${\displaystyle i}$${\displaystyle \rho _{i}}$ ${\displaystyle S_{ij}}$${\displaystyle j}$${\displaystyle i}$

${\displaystyle S_{ij}={\frac {A_{ij}}{\lambda }}{\frac {\psi _{j}}{\psi _{i}}}}$.

Примеры [ править ]

Давайте сначала рассмотрим простую нетривиальную ситуацию: кодирование Фибоначчи , когда мы хотим передать сообщение как последовательность нулей и единиц, но не используя две последовательные единицы: после 1 должен быть 0. Чтобы максимизировать количество информацию, передаваемую в такой последовательности, следует предполагать равномерное распределение вероятностей в пространстве всех возможных последовательностей, выполняющих это ограничение. Чтобы практически использовать такие длинные последовательности, после 1 мы должны использовать 0, но остается свобода выбора вероятности 0 после 0. Обозначим эту вероятность как , тогда энтропийное кодирование позволит кодировать сообщение с использованием этого выбранного распределения вероятностей. Стационарное распределение вероятностей символов для данного оказывается${\displaystyle q}$${\displaystyle q}$${\displaystyle \rho =(1/(2-q),1-1/(2-q))}$. Следовательно, производство энтропии , которое максимизируется , известно как золотое сечение . Напротив, стандартное случайное блуждание выбрало бы неоптимальное . Хотя выбор большего размера уменьшает объем информации, производимой после 0, он также снижает частоту 1, после чего мы не можем записывать какую-либо информацию.${\displaystyle H(S)=\rho _{0}\left(q\log(1/q)+(1-q)\log(1/(1-q))\right)}$${\displaystyle q=({\sqrt {5}}-1)/2\approx 0.618}$${\displaystyle q=0.5}$${\displaystyle q}$

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

${\displaystyle (\lambda \psi )_{x}=(A\psi )_{x}=\psi _{x-1}+(1-V_{x})\psi _{x}+\psi _{x+1}}$

для всех позиций , где для дефектов, 0 в противном случае. Подставляя и умножая уравнение на −1, получаем:${\displaystyle x}$${\displaystyle V_{x}=1}$${\displaystyle 3\psi _{x}}$

${\displaystyle E\psi _{x}=-(\psi _{x-1}-2\psi _{x}+\psi _{x+1})+V_{x}\psi _{x}}$

где сейчас минимизируется, становясь аналогом энергии. Формула внутри скобок представляет собой дискретный оператор Лапласа , что делает это уравнение дискретным аналогом стационарного уравнения Шредингера . Как и в квантовой механике , MERW предсказывает, что распределение вероятностей должно вести именно к одному из основных квантовых состояний : с его сильно локализованной плотностью (в отличие от стандартной диффузии). Взяв бесконечно малый предел, мы можем получить здесь стандартное непрерывное стационарное (не зависящее от времени) уравнение Шредингера ( для ). ^[11]${\displaystyle E=3-\lambda }$${\displaystyle \rho _{x}\propto \psi _{x}^{2}}$${\displaystyle E\psi =-C\psi _{xx}+V\psi }$${\displaystyle C=\hbar ^{2}/2m}$

См. Также [ править ]

• Принцип максимальной энтропии
• Центральность собственного вектора
• Цепь Маркова
• Локализация Андерсона

Ссылки [ править ]

Внешние ссылки [ править ]

• Габор Симони, Ю. Линь, З. Чжан, «Среднее время первого прохождения для случайных блужданий с максимальной энтропией в сложных сетях» . Научные отчеты, 2014.
• Модели электронной проводимости с использованием случайных блужданий с максимальной энтропией Демонстрационный проект Wolfram