Лекции по "Алгебре"

При бесконечном повторении опыта с механизмом равновероятного выбора действий, будет накоплен некоторый суммарный штраф. Его величина определяется как математическое ожидание штрафа по формуле, хорошо известной из теории вероятностей:

Значение М* позволяет интерпретировать понятие целесообразного поведения следующим образом. Будем говорить, что автомат ведет себя целесообразно, если накопленный ею суммарный штраф меньше, чем в случае использования механизма равновероятного выбора действий. А нецелесообразным будем считать такое поведение, при котором этот суммарный штраф больше или равен М* .

Пусть, например, в опыте Трондайка Рп = 0,9, а Рл = 0,4. Если бы крыса заранее знала эти вероятности, то она, конечно, всегда бы предпочитала бежать в левый коридор. Если при наших значениях вероятностей штрафов за действия крысу поставить в условия равновероятностного выбора, то суммарное значение штрафа для нее будет равно

М = 0,5*0,9 + 0,5*0,4 = 0,65

А наилучшим поведением будет то, при котором суммарный штраф достигнет своего минимума (при выборе только левого коридора). В этом случае

М = 0*0,9 + 1*0,4 = 0,4

Опишем структуру технических устройств, обеспечивающих целесообразное поведение в любой априорно неизвестной стационарной среде.

Тема 5.4 Детерминированный автомат

Пример: Рассмотрим ситуацию, встречающуюся в народных сказках. Иванушка-дурачок встречает свадьбу. И начинает громко причитать и плакать. Такое неадекватное поведение вызывает мгновенную реакцию среды. Жестоко побитый Иванушка через некоторое время встречает похороны. Помня свою неудачу, он начинает весело смеяться и петь. И снова жестокая кара постигает нашего простодушного героя. Он снова бит.

Нарисуем граф переходов этого автомата. Состояние 1 – плясать, состояние 2 – плакать. Наша среда так же может вы давать только две ответные реакции: «Бить» или «Не бить». Сплошной чертой мы обозначим реакцию нашего автомата на поощрение (реакция «Не бить»); пунктирной линией – на наказание (реакция «Бить»).

Составим для этого примера таблицу переходов.

Строки – это состояние автомата, в момент времени t

U –это состояние окружающей среды. Обе эти переменные двоичны.

Значения переменной Х – "1" – плакать

                                                        "2" - петь

Значения переменной U – "0" – похороны

                                                        "1" - свадьба

Выходом этого автомата будем считать сведения о смене состояния автомата. "0" – если не меняет состояние

"1" – если меняет.

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

Вот как выглядит граф переходов такого автомата. Сплошной стрелкой мы показали переход при наказании, пунктирной – при поощрении. В нашем примере определено по три устойчивых состояния для каждого действия автомата. Будем считать, что состояния 1, 2, 3 – обозначают действие «плакать» нашего Иванушки, а состояния 4, 5, 6 – действие «петь». Это число называется глубиной памяти конечного автомата или степенью его инерционности. Покажем, что такой автомат достаточно быстро найдет лучшее для статической среды действие, и будет выполнять только его. Поясним эту мысль. Пусть в начале наш автомат находится в состоянии 3. А влияние среды описывается (0,9;0,1) т.е. с вероятностью 0,9 встретится свадьба и с вероятностью 0,1 – похороны. Понаблюдаем за поведением нашего Иванушки. С вероятностью 0,9 встретится свадьба, и Ивана побьют, он перейдет в состояние 4, он станет петь и опять с вероятностью 0,9 на свадьбе. По теории вероятностей, вероятность получения от среды двух свадеб подряд равна 0,81, Двух похорон подряд 0,01, а вероятность одной свадьбы и одних похорон = 0,18. Следовательно, после двух тактов взаимодействия с вероятностью 0,01 автомат окажется в состоянии 1, с Р=0,18 в прежнем положении, и с Р=0.81 в состоянии 5. С ростом числа взаимодействий качественно картина не изменится. Вероятность покинуть группу 6-4 неуклонно падает, а вероятность остаться в ней – растет.

Что произойдет дальше? С Р=0,9 наш автомат получит поощрение и перейдет в состояние 6 и т.д. Вероятность покинуть группу 4-6 все время будет уменьшаться. Этот процесс очень похож на процесс обучения, после которого наш автомат "достаточно адекватно" ведет себя в данной статической среде. "Достаточно адекватно" потому, что существует очень малая, но ненулевая вероятность покинуть группу наиболее благоприятного поведения ( т.е. поведения когда сумма штрафов минимальна).

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

Все сказанное выше, справедливо и для автомата, у которого больше двух действий и больше двух состояний среды. Чем больше глубина памяти такого автомата, тем целесообразнее его поведение. Рассмотренный нами автомат называется автоматом с линейной тактикой.

Подчеркнем еще раз, повышение глубины памяти улучшает показатель целесообразности поведения автомата с линейной тактикой для статических сред. Более того, Цетлин показал, что если min Pi <0,5  то при увеличении глубины памяти q автомата с линейной тактикой мы получим последовательность автоматов с линейной тактикой со все увеличивающейся глубиной памяти, которая является асимптотически оптимальной. Это означает, что при q →∞ М(q, Е) → Мmin – минимальный суммарный штраф. Т.о. конструкция, предложенная Цетлиным, обеспечивает при достаточно больших значения q поведение, сколь угодно близкое к наилучшему в любых стационарных случайных средах.

Рассмотрим еще пару конструкция автоматов с линейной тактикой.

Эта конструкция предложена В.И. Кринским. Мы будем называть «доверчивым». Вот как выглядит его граф переходов.

При поступлении сигнала штраф, поведение этого автомата аналогично поведению автомата с линейной тактикой Цетлина, но при получении сигнала поощрения, этот автомат, независимо в каком состоянии лепестка он находился в данный момент, переходит в самое глубокое состояние данного лепестка. Этот автомат, как будто, склонен верить в хорошее, и положительный сигнал среды приводит его в состояние «эйфории».

Строго доказано, что автоматы Кринского ведут себя целесообразно в любых стационарных случайных средах.

Может сложиться ощущение, что любые меры по увеличению числа инерционности автомата, улучшает показатель целесообразности поведения автомата. 

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

Тема 5.5 Вероятностный автомат

Опишем теперь структуру автомата, поведение которого в той или иной мере будет отвечать требованиям среды. Этот автомат называется вероятностным. Устроен он подобно автомату с линейной тактикой, но его функции переходов и выходов являются случайными функциями. Т.е. задается вероятность переходов из одного состояния в другое, при поступлении на вход определенного сигнала. Такой автомат, как правило, задается системой матриц, в которых на пересечении i – того столбца и k –той строки указывается Р перехода из i – того состояния в k-тое. В частном случае, когда такие матрицы содержат только "0" и "1", описывается уже знакомый нам детерминированный автомат.

Выписывание таких матриц слишком громоздкая процедура, поэтому покажем вид этих матриц для автомата, показанного на рисунке.

Эти матрицы определяют детерминированную структуру нашего автомата. П+ - матрица переходов при поступлении сигнала поощрения, а П-  при поступлении сигнала штрафа.

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

Приведем наглядный пример такого автомата.

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

Ночные бабочки также способны принять сигнал от летучей мыши и определить его интенсивность. Поведение бабочки различно в зависимости от того, как далеко от нее находится летучая мышь. Будем различать три маневра бабочки.

1.        Бабочка начинала двигаться в сторону, противоположную прежнему движению.

2.        Бабочка меняла направление в вертикальной плоскости, уходя от своего прежнего курса вверх или вниз.

3.       
Бабочка начинала хаотическое движение, т.е. переходит на такую траекторию полета, которая максимально затрудняет для нападающего предсказание следующей точки на этой траектории.

На рисунке изображен граф смены состояний вероятностного автомата. Его особенность состоит в том, что для каждой группы состояний (они обведены на рисунке пунктиром) существует ненулевая вероятность перейти в особое состояние, описывающее гибель автомата. Состояние 1 можно интерпретировать следующим образом: 1 – с Р=0,3 летучая мышь обнаруживает бабочку, а с Р=0,7 – пропускает ее. 2 – мышь определяет направление своего движения и с р= 0,8 цель при этом не теряется. 3 – летучая мышь настигает бабочку и уничтожает ее с Р=0,95. Что может противопоставить преследователю бабочка? Для простоты изложения будем рассматривать каждую из групп состояний автомата, как определенную среду, задаваемую стратегией бабочки. Е1 – это прямой полет. Е2 – изменение направления движения в горизонтальной или вертикальной плоскости, а Е3 – хаотическое движение. Действия бабочки сводятся к смене сред, переключению их. При этом автомат может реализовывать действие только в состоянии 2 или 3. На рисунке это показано двойными стрелками переходов.

Составьте сами таблицу состояний этого автомата.

В приведенном примере действия, позволяющие бабочке максимально увеличить вероятность своего спасения, достаточно просты и прозрачны. Однако в общем случае выбор оптимальной последовательности переключений действий автомата, максимизирующий продолжительность его жизни далеко не тривиален. Наша же цель: показать принципы действия вероятностного автомата достигнута.

Тема 5.6 Автомат с переменной структурой

Для начала рассмотрим такую ситуацию. Предположим, что вы на своей машине ежедневно добираетесь от дома до работы. В вашем распоряжении есть два возможных маршрута, и вы вольны выбрать любой из них. Т.к. вы всегда выезжаете в одно и то же время, то обстановка по каждому из маршрутов как бы стационарна. И анализируя эту обстановку, вы убедились, что один из маршрутов лучше другого: времени тратиться меньше – движение здесь менее интенсивное, чем по другому маршруту, да и светофоров здесь не так много. Но вот беда: время от времени из-за каких-то ремонтных работ скорость движения здесь резко снижается, образуются пробки, и можно потерять много времени пока они ликвидируются. В этих условиях данный маршрут становится намного хуже другого. Вы бы потеряли куда меньше времени, выбрав  в эти неудачные дни другой маршрут. Если нет никакой информации о частоте ремонтных работ на трассе первого маршрута, то выезжая из дома нет никаких шансов угадать, по какому маршруту лучше сегодня ехать. Однако, день за днем, вы накапливаете информацию. Учитесь на своем горьком опыте. Выясняется, что чаще всего пробки образуются в среду и пятницу и вероятность этих пробок достаточно велика. Тогда выбирая в остальные дни недели первый маршрут, вы в среду и пятницу без колебаний выбираете менее хороший маршрут поездки.

Но ни автомат с линейной структурой, ни вероятностный автомат Крылова не могут приспособиться к часто меняющейся динамической среде, поскольку его таблицы переходов не меняются в процессе функционирования. Поэтому рассмотрим модель автомата с переменной структурой. Это уже знакомый нам вероятностный автомат в начале функционирования находящийся в безличном состоянии, с наперед заданными вероятностями переходов.

Если, выполнив какое-то действие, автомат получил сигнал штраф, то в матрице переходов он уменьшает значение вероятности этого перехода на  заданную величину , но сумма всех элементов строк должна быть равна 1, поэтому все ненулевые элементы строки необходимо изменить на величину /h, где h – количество ненулевых элементов строки.

Пусть для определенности в начальный момент времени автомат находился в состоянии 1, и совершил действие 1, соответствующее этому состоянию. С помощью равновероятного выбора по матрице П+ перешел в состояние 4. И пусть после этого он получил сигнал штраф. Получение такого сигнала заставляет автомат считать свой переход 1 – 4 ошибкой. Эта информация фиксируется следующим образом. Вероятность П+14 уменьшается на , а все остальные элементы строки увеличиваются на /3.  Для удобства положим  = 0.03. Тогда после этого шага матрица П- не изменится, а матрица П+ будет выглядеть так: