Хайкин С. - Нейронные сети (778923), страница 141
Текст из файла (страница 141)
В момент времени п этот вектор распределения состояний определяется следую)цим образом: (и) (и — 1)р (11.21) Итеративно используя выражение (11.21), получим: (и) (и-1)р (и-2)р2 (и — 3)рз что в конечном счете приводит к следующей формуле: )т(п) эт(0) рп (! 1.22) К1 К2 .. ЛК К1 П2 КК 1пп Р" = и сО (11.23) К1 И2 ° ° ° ИК где к — вектор-строка, состоящий из элементов к„к„..., я)г. После перестановки слагаемых из выражения (11.22) получим следующую формулу: — к=е. к (с) Так как по определению 2; к( ) = 1, вектор к не будет зависеть от начально1=1 го распределения.
где )С(~) — начальное значение вектора распределения состояний. Другими словами, вектор распределения состояний цепи Маркова в момент времени п является произведением исходного значения этого вектора на а-ю степень стохастической матрицы Р. Обозначим символом р(и) у-й элемент матрицы Р. Предположим, что при устремлении п к бесконечности вероятность р, стремится к некоторому значению к), не (и) зависящему от 1, где кт — стационарная вероятность состояния 11 Соответственно при больших и матрица Р" достигает своей предельной формы квадратной матрицы с идентичными строками: 11.3. Цепи Маркова 701 Теперь можно сформулировать теорему об эргодичности (егяод)с((у бтеогепз) для цепей Маркова [711, [294): Пусть эргодическая цепь Маркова с состояниями х„хз,..., хк и стохастической матрицвй Р= [р, 1 является песократимой.
Тогда эта цепь имеет единственное стационарное распределение, к которому опа сходится из любого начального состоянии. Это значит, что существует едипствеппыи набор чисел (Нз 15, такой, что к 1цп р," = и, для всех т, и ьо х > 0 для всех 2', к. нз = 1, з=-1 к х = ~ н,р, длявсвх)'= 1,2,...,К. (11.24) (11.25) (11.2б) (11.27) И наоборот, предполоэкии, что цепь Маркова яаиется иесократимой и апериоди- ческой, а и!ахате существуют числа [х.)~ з, удовлетворяющие условияи (11.25)— (11.27). Тогда эта цепь является эргодической, величины х вычисляются по формуле (11.24), а среднее время возврата в состояние 2' равно 1/н . ° Начиная с любо~о исходного состояния, вероятности перехода в цепи Маркова сходятся к стационарному распределению, если такое распределение существует.
° Если цепь эргодичсская, то стационарное распределение в цепи Маркова полностью не зависит от ес начального распределения. Пример 11.1 Рассмотрим цепь Маркова с диаграммой переходи состояяий, показанной на рис. 1!.1. Эта цепь имеет два состояния — х~ и хя. Стохастическая матрица этой цепи имеет следующий вид; 1/4 3/4 1/2 !/2 Эта матрица удовлетворяет условиям (1 !. 14) и (11.15). Предположим, что начальным состоянием является следующее: кю) = [!/б, б/б).
По формуле (1!.2!) получим следующий вектор распределения состояний для момента времени и = 1: Распределение вероятности [хз)~, называется инвариантпым или стационарным. Такое название объясняется тем, что по достижении такого распределения оно сохраняется. В свете теоремы об эргодичности можно утверждать следующее. 702 Глава 11. Стохастические машиныи их аппроксимациив статистической механике Рис.
11.1. Диаграмма перехода со- стояний в цепи Маркова для приме- ра 11.1 ко! = аю1Р = ~1/6 5/6] = ~п/24 13/24~ . ~1/2 1/2~ Возводя стохастическую матрицу Р в степени 2, 3 и 4, получим 0,4375 0,5625~ 0,3750 0,6250~ ' 0,4001 0,5999~ 0,3999 0,6001~ ' 0,4000 0,6000~! 0,4000 0,6000~ Таким образом, кг = 0,4000, а лз = 0,6000.
В данном примере сходимость к стационарному состоянию была обеспечена всего за 4 итерации. Так как обе величины, хг и хг, больше нуля, оба состояния являются положительно рекуррентными, а сеть — несократимой. Также заметим, что данная цепь является апериодической, так как наибольший общий делитель всех чисел и > 1, таких, что (Р")о > О, равен единице. Исходя из сказанною, делаем вывод о том, что цепь Маркова на рис.
!1.! является эргодической. Пример 11.2 0 0 1 1/3 1/6 1/2 3/4 1/4 0 =[ Диаграмма перехода состояний этой цепи представлена на рис. 11.2. Применяя выражение (! !.27), получим следующую систему уравнений: Е кг = -кз+ -кз, з з кз = екз+ Ткз, 1 1 хз л! + злз 1 Рассмотрим цепь Маркова, имеющую сгохастическую матрицу, содержащую отдельные нулевые элементы: 11.3. Цепи Маркова 793 Рис. 11.2.
Диаграмма перехода состояний дпя сети Маркова из примера 11.2 Пололнтельно рсктррснгное Нерекуррелтнос I Итак, данная цепь Маркова является эргоднческой со стационарным распределением, определяемым величинами яг, яг н яз Классификация состояний На основе представленного материала можно создать диаграмму классов, к которым может принадлежать состояние [рис. 11.3) [294], [633]. Принцип детального баланса Выражения (11.25) и (11.26) подчеркивают тот факт, что числа к, являются вероятностями. Выражение (11.27) также является критичным, так как выполнение этого Апернодическое Рис. 11.3. Классификация состояний !лн р,и' = л, цепи Маркова и связанного с ними по- прн л-+ ведения Решив эту систему уравнений, находим следующие значения; пг = 0,3953, яг = О, 1395, яз = 0,4652.
Периодическое !!шр е!ййл лрнл-ь г ! где о' — целое число большееднннцн 704 Глава 11. Стохвстические машиныи нх аппроксимациив статистической механике условия требуется для того, чтобы цепь Маркова была несократимой и, таким образом, существовало стационарное распределение. Это последнее условие является записью принципа детильного баланса (рппс1р!е оТ «!е!айек! Ьа!апсе), известного в кинетике первого порядка. Этот принцип утверждает, что в состоянии термального равновесия частота возникновения любого перехода равна соответствующей частоте обратного перехода !877): (11.28) Лгргг Пгрзг. Для вывода соотношения (1!.27) можно переставить порядок суммирования в правой части уравнения: к к к 1Г тГ, 'юч = г — г,); = 2; гг*.1, =, г=1 г=1 г=1 Во второй строке этого выражения использовался принцип детального баланса, а в последней — тот факт, что вероятности перехода в цепи Маркова удовлетворяют следующему условию (см.
(11.15), где роли 1 и 7' поменялись местами): к ~ р„. = 1 для всех ~. Обратите внимание, что принцип детального баланса предполагает, что распределение (к,) является стационарным. 11.4. Алгоритм Метрополиса Теперь, когда стало понятно строение цепей Маркова, их можно использовать для вывода стохастического алгоритма моделирования развития физических систем до состояния термального равновесия. Этот алгоритм получил имя своего создателя— Метрополиса (Ме!горо!га а!йог!гЬт) [730).
Он представляет собой модифицированный алгоритм Монте-Карло, введенный еше в раннюю эпоху моделирования достижения температурного равновесия стохастическими системами, состоящими из атомов. Предположим, что случайная переменная Х„, представляюшая произвольную цепь Маркова, в момент времени и находится в состоянии х,. Сгенерируем случайным образом новое состояние х1, представляющее собой реализацию другой случайной переменной У„. Предполагается, что генерация этого нового состояния удовлетворяет условию симметрии: 11.4.
Алгоритм Метрополиса 705 Обозначим символом ЬЕ разницу в энергии, возникающую при переходе системы из состояния Х, = х, в состояние У„= х,. Если эта величина отрицательна, то переход приводит к состоянию с меньшей энергией и такой переход принимается. После этого новое состояние считается точкой старта следующего шага алгоритма (т.е. мы принимаем Х„ь, = У„). Если же разница в энергии положительна, алгоритм продолжает работу по вероятностной схеме в этой же точке. Выбираем случайное число с, равномерно распределенное в диапазоне (О, 1).
Если Е ( ехр( — ЬЕ(Т), где Т вЂ” рабочая температура, переход принимается, при этом считается, что Х„ь, = У„. В противном случае переход отвергается, при этом полагается, что Х„,ь1 — — Х„(т е. на следующем шаге алгоритма используется старая конфигурация). Выбор вероятности перехода 1. Неотрицательностгп то ) 0 длЯ всех (1,2). 2.
Нормировка; т„= 1 для всех т'. Х:"= 3. Сииметрия: т; = т,, для всех (т, т). Пусть я; означает установившееся значение вероятности, в котором находится цепь Маркова в состоянии х„1 = 1, 2,..., К. Тогда симметрию т, и частное к /л; можно использовать для определения требуемого множества вероятностей переходов (115]: т „(-„х) для -~- ( 1, для — ' ) 1. (11.29) Пусть цепь Маркова имеет априорные вероятности перехода т;, удовлетворяющие следующим трем условиям. 706 Глава 11. Стохастнческне машинын нх аппрокснмацнна статистической механике Для обеспечения нормировки вероятностей перехода к значению единицы введем следующее определение вероятности отсутствия перехода: (11.30) кфир пф где а,, — вероятность перехода, определенная как а;, =пп'и 1,— ' (11.31) Теперь возникает один важный вопрос: как выбрать частное х,lх,? Для того чтобы ответить на этот вопрос, следует выбрать такое распределение вероятностей, которое требуется для перехода распределения вероятности цепи Маркова в распределение Гиббса: хг = — ехр В этом случае отношение вероятностей к,!х, принимает простую форму: — ' = ехр (11.32) где (11.33) Используя частное распределений вероятности, можно избежать зависимости от функции разбиения У.
По своему определению вероятности перехода являются неотрицательными числами, нормированная на единицу (см. (11.14) и (11.15)). Более того, они удовлетворяют принципу детального баланса, определенного выражением (11.28). Этот принцип является достаточным условием температурного равновесия. Чтобы продемонстрировать, как выполняется принцип детального баланса, рассмотрим следующие случаи. Случай 1. ЬЕ < 0 Предположим, что при переходе из состояния х; в состояние хт произошло отрицательное изменение энергии. Из выражения (11.32) получим х,lл,>1, после чего с помощью (11.29) получим: я,ргт = п,т,, = к,т,, 11.5.
Метод моделирования отжига 707 (к, к,р,, =к, — г„=к,т„. Исходя из этого, принцип детального баланса удовлетворяется при ЬЕ<0. Случай 2. ЬЕ > О Теперь предположим, что при переходе из состояния х, в х, произошло положительное изменение энергии. В этом случае к lк,<1, откуда с помощью выражения (11.29) получим: /'к, к;р„= к, — т„= к,т„= к,т„ к,р„= к,т,, При этом снова удовлетворяется принцип детального балаиса. Чтобы получить общую картину, давайте проясним использование алриорлых вероятностей перехода, которые обозначены символом тчь Эти вероятности перехода иа самом деле являются вероятностными моделями случайного шага в алгоритме Метрополиса. Из ранее представленного описания этого алгоритма известно, что за случайным шагом следует случайное решение.
Отсюда можно заключить, что вероятности перехода рьо определенные по формулам (11.29) и (11.30) в терминах алриориых вероятностей перехода т, и стационарных вероятностей к„иа самом деле являются подходящими для алгоритма Метрополиса. Важно отметить, что стационарное распределение, генерируемое алгоритмом Метрополиса, ие однозначно определяет цепь Маркова. Распределение Гиббса в состоянии равновесия может быть сгенерировано с использованием правила, отличного от метода Монте-Карло, применяемого в алгоритме Метрополиса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
