Теория информации
Мысль изреченная есть ложь. Так однажды высказался уважаемый русский поэт Фёдор Тютчев.
...Как сердцу высказать себя?
Другому как понять тебя?
поймет ли он, чем ты живешь?
Мысль изреченная есть ложь,
Взрывая, возмутишь ключи,
— Питайся ими— и молчи...
Написано на тему стихотворения «Молчи»( «Silentium!» - «Силенциум!») немецкого поэта, участника революции 1848 г. в Германии Л. Пфау (1821—1894).
Это стихотворение цитируется, как совет внимательно относиться к слову — далеко не всякая высказанная мысль понимается другим человеком адекватно, правильно.
Теперь объясним более сложно. Есть передатчик, передающий сигналы из некого множества X. Есть приемник, принимающий сигналы, образующие множество Y. Есть источники шумов. Это может быть реальный шум, мешающий нам слышать, что говорит другой, а может быть «шум» из-за разности образования, воспитания, темперамента.
Так что если передатчик послал сигнал из множества X, приемник, получив (услышав) Y, может только с некоторой вероятностью понять, что же ему сказано. А передатчик с некоторой вероятностью догадываться, что же понял приемник.
Как редко мы слышим по телевидению интервью или читаем статью в газете, где абсолютно понятно, что говорит автор. Это подкрепляется примерами, оборотами, шутками или цитированием. Но как часто мы этого не понимаем, а хуже понимаем не то, что нам посылает источник.
Это и есть модель канала (без памяти).
А теперь об информации.
Я пишу, Вы читаете. Интересно сколько Вы получаете информации от меня. Я не говорю о пользе, а количестве. Если Вы ничего не знали о теории информации, то для вас может даже и много. А если Вы знаете её лучше меня, то я ничего не прибавлю к Вашему знанию. Таким образом, Вы получили от меня информации 1, - если ничего не знали и 0- если знали все. Между этими крайними положениями можно давать разные оценки, в зависимости от того насколько я рассеял Ваше невежество (по научному - энтропию, неопределенность).
Это очень приблизительное объяснение результатов теории Клода Шеннона, которую он опубликовал у 1948 году в статье «Математическая теория связи».
Возможность заранее знать результат (существование нулевой информации) может хорошо использоваться на практике.
Весьма вероятно создание канала с предсказанием. На передающем и приемном концах ставятся предсказатели. На передающем, получив предыдущую фразу, предсказатель вырабатывает следующую фразу и если следующая фраза совпадает с предсказанием, то информация в канал не передается. На приемном конце такой же предсказатель, не получив фразу передает предсказанную фразу пользователю.
Например, 31 декабря на передающем конце для передачи поступило слово «Поздравляю». Понятно, что дальше вероятней всего будет с «Новым Годом». Таким образом, можно сохранить производительность канала.
Более важным является предсказание области попадания ракеты. При вылете ракеты почти всегда можно, с некоторой вероятностью, предсказать, в какую точку она направлена. Тогда противоракетная система может направить перехватчик заранее в прогнозируемую точку, а это экономит время подлета (даже при нескольких коррекциях маршрута), особенно дорого при минимальных расстояниях.
Очень интересный эксперимент рассказывает в своей статье «Три подхода к определению понятия информации». А.Н.Колмогоров. Сотрудники проводили исследования энтропии стихотворных текстов. При этом учитывался жанр, размер и прочие ограничения.
После установления информационной связи в текстах, некоторые сотрудники до того точно предсказывали текст, что создавалась иллюзия телепатической связи с автором.
Сам Шеннон очень иронично относился к использованию его теории в других областях жизни.
В 1956 году он написал статью “The Bandwagon.” IRE Transactions on Information .
Бандвагон (Bandwagon) в английском языке имеет много оттенков. Прямой перевод – это праздничная повозка. Поскольку “band” (оркестр, джаз) и “wagon” (повозка, карета). После того, как какой-то кандидат выигрывал на выборах, сооружалась повозка или грузовик с джаз - оркестром, украшенный цветами, и сторонники этого победителя ездили по городу, возвещая его победу.
Этот же термин обозначает мода, повальное увлечение.
Шеннон внес некоторую игру слов, в теории связи термин «band» означает полосу пропускания, определению величины которой Шеннон посвятил большую часть своих работ.
Он писал.
«Здание нашего несколько искусственно созданного благополучия слишком легко может рухнуть, как только в один прекрасный день окажется, что при помощи нескольких магических слов, таких, как информация, энтропия, избыточность..., нельзя решить всех нерешенных проблем».
Его скептицизм базировался на том, что невозможно открыть все тайны природы одним ключом. Кроме этого, он понимал, что его теория не универсальна, что предложенные им для измерения количества информации новая мера и новые единицы измерения (биты) не учитывают таких важных свойств информации, как ее ценность и смысл.
Некоторую трагичность и торжественность его теории предавало то, что его оценка была приложением к задачам связи теории термодинамики далекой, казалось бы, от передачи данных.
Эта теория была разработана австрийским ученым Людвигом Эдвардом Больцманом.
Современный ученый произносит имя Больцмана с глубоким почтением. Работы Больцмана послужили фундаментом современной статистической физики.
Но в то время его теория не нашла понимания в физическом обществе. На этой почве у него развилась депрессия, и он покончил с собой в гостиничном номере, повесившись на оконном шнуре. На могильном камне выбита установленная им формула.
Клод Эльвуд Шеннон был человек другого склада. Теоретик и инженер, шутник и жонглер. На одном из своих последних Конгрессов по теории информации, он к изумлению аудитории прожонглировал тремя шарами. В MIT окна скромного кабинета выходили на разлив реки Чарльз Ривер, что всегда навевает позитив.
В 1965 он был в СССР. Его принимали торжественно, но, как правило, он прерывал пустые речи, выходил к доске и читал лекцию о своих текущих результатах или мыслях. Тогда за ним могли следовать только посвященные в математику и владеющие языком люди.
Игры с автоматами.
Он интересовался играми автоматов, и первый сконструировал автомат для игры «в чет - нечет». Этот автомат всегда выигрывал у человека. Он впервые показал, что человек не может вырабатывать чисто случайные сигналы. Автомат запоминает закономерности, невольно принимаемые человеком и после некоторого периода накопления статистики (обучения) начинает выигрывать.
Из собственного опыта вспоминаю, что на принципе обучения мы сделали программы эксплуатации сложной аппаратуры. Заранее настроить контроль на определение ошибок в этой системе было невозможно. Поэтому решили, что при возникновении ошибок автомат включал сигнализацию, вызывал оператора. Оператор регистрировался и автомат начинал запоминать действия оператора и результаты воздействий на каждом этапе. Через несколько дней он наивно подражал действию и манере этого человека. Когда в его памяти накопились данные о работе нескольких операторов, он начинал выбирать методики, и определять какая оптимальнее.
Самое интересное, что мы заметили, что существует «отрицательное образование».
Мы с детства знаем и повторяем: « Учись мой сын! Наука сокращает нам опыты быстротекущей жизни».
Но однажды моя помощница принесла результаты анализа обучающей системы, и сказала, что при решении математических уравнений описания поведения автомата появились отрицательные значения некоторых его действий. Я сказал: «Отбрось их, знания могут быть только положительными».
Не прошло и недели, как автомат с отрицательными характеристиками обучения чуть не вывел систему их строя.
Более того, совершенствование неправильных знаний шло гораздо более быстрыми темпами, чем в случае обретения положительных знаний. Вот вам и урок для жизни.
Но продолжим об автоматах или как их дальше называли «виртуальных зверюшках».
Исследованием этих «зверюшек» интенсивно занимались в СССР М.Л.Цетлин, Д.А.Поспелов, В.И.Варшавский и их коллективы. Теорией игр и принятием решений занималась Елена Ивановна Вентцель – она же очень интересная писательница И. Грекова (этот псевдоним перекликается с математическим знаком «Игрек -Y»)
Интересны моделирование на автоматах поведение настоящих «зверюшек».
Обычно место исследования выбирается T-образный лабиринт, доходя до стенки этого лабиринта «зверюшка» (мышка, червяк, крыса) должна выбрать один из двух путей, например, пойти налево или направо.
При этом на каждой из сторон её ждет сюрприз, например, слева приятный (вкусная еда) или неприятный (резкий звук, неприятный запах).
Довольно быстро «зверюшка» начинает безошибочно выбирать направление приятного сюрприза. При смене мест «сюрпризов» автомат быстро адоптируется. Так же если неприятности носят временный вероятностный характер, автомат быстро распознает, где меньше вероятность и выбирает эту сторону.
Однако в случае наибольшей неопределенности (равной вероятности «сюрпризов») человек выигрывает у автомата. Причина в том, что человек обычно выходит из заданного множества обстоятельств и начинает учитывать то, что находит сам. Например, он начинает думать, отчего происходят изменения сюрпризов, и добивается их исключения или стабилизации процесса. Так что об эре умных автоматов говорить рано.
На одной из выставок демонстрировался автомат, принимающий решения. Рядом с ним лежали картонные фигурки: прямоугольники, треугольники, окружности, эллипсы. Когда перед камерой автомата помещали фигурку, то независимо от её размера он писал её название: – окружность, эллипс.
Я показал ему кулак, и он испортился (в программе этого не было).
Невольно вспоминается Павел Коган:
Я с детства не любил овал!
Я с детства угол рисовал!
Так что об эре умных автоматов говорить рано.
А теперь поговорим как эти «виртуальные зверюшки» имитируют жизнь.
К цели можно идти по разному. Все они, как и мы, перед тем как сделать шаг выбирают, куда его делать. На каждом шагу есть целый набор (веер решений) и надо выбрать одно направление. Конечно, «зверюшек» и нас интересует, как добраться до цели, при этом с наибольшим выигрышем и наименьшими потерями. Выбирая путь по разному.
Одних интересует наибольшая вероятность достижения финиша. Других волнует цена этого события. Если вероятность мала, а выигрыш велик, кто- то может рискнуть, Кто-то предпочтет наименьший выигрыш, но наверняка.
Среди этого веера есть пути, которые заведомо имеют нулевую вероятность и сразу отбрасываются. Есть такие, которые позволяют 100 –процентно выиграть часть средств. А многие требуют сделать шаг, и, сделав его производить оценку дальше с новых позиций. И так делая шаг за шагом, все достигают конечной точки. Каждый по-своему и за свою цену.
Как вслед Шекспиру говорил другой автор:
«Жизнь есть театр..., разные цены на одно и то же зрелище».
Как же нам заранее оценить, какой из этих путей оптимален. Тут можно рассуждать вероятностно, оценкой информации и ценой снятия неопределенности, а можно сделать, посчитав сложность и цену алгоритма (Колмогоровская оценка) программы, которая нас приводит из одной точки к другой.
Рассмотрим обе тактики.
Давайте попробуем спланировать нашу жизнь.
Предположим, что для достижения конечной цели должны состояться (или не состояться) три события A, B и C. Они могут наступить в произвольном порядке. Для определенности начнем с порядка сначала A, потом B,. потом C.
Итак, мы строим «дерево»:
1. Если произошло A, то это может дать следующие результаты.
1.1.После того, как произошло событие A, цель может быть достигнута, и дальше ничего не зависит ни от B, ни от C.
1.2. После наступления события A, цель не может быть достигнута и это тоже делает дальнейшие шаги нецелесообразными.
1.3. Ситуация не ясна и нужно посмотреть, что будет если произойдет событие B.
2. Если произошло событие не A (A не произошло), то анализ ситуаций делается таким же образом в три шага.
3.Аналогично анализируется ситуация, что будет, если произойдет B (или не произойдет). На этом шаге добавляется еще одна возможность, из многих возможных путей некоторые приводят к одному и тому же результату, тогда такие веточки объединяются.
На последнем шаге все веточки объединяются, поскольку они приводят к желаемому результату. Так мы можем расписать все пути. Заметим даже при этом примитивном анализе, мы не учитывали, а что если события произойдут не в том порядке, который мы рассматривали. Учет этого приводить часто к очень большому комбинаторному перебору.
Но все же такое планирование позволяет провести анализ возможных действий.
И найти оптимальные из них, которые приводят к наибольшему выигрышу при малых потерях.
Как всегда исследователей ждал сюрприз. Наименьшие потери, иногда даже и маленький выигрыш будет тогда, когда вы ничего делать не будете.
Когда был получен такой результат, пришлось ввести дополнительное условие надо не просто составлять план, а одновременно, что-то создавать. Учитывая сложность достижения и построенного объекта можно судить о проигрыше или выигрыше.
Но тут опять была неожиданность, чтобы все это в общем случае рассчитать нет другого пути, как сначала построить объект, а потом считать потери и затраты.
Опять пытливые умы начали искать выход из положения. Они задали вопрос, а что если исследовать закономерные стратегии, произвольные тогда можно сводить к теоретическим исследованиям.
Например, есть задача в теории вероятности называемая «петербургская игра» или «петербургский парадокс».
Рассматривается следующая задача. Вступая в игру, игрок платит некоторую сумму, а затем подбрасывает монету (вероятность каждого исхода — 50 %), пока не выпадет орёл. При выпадении орла игра заканчивается, а игрок получает выигрыш, рассчитанный по следующим правилам. Если орёл выпал при первом броске, игрок получает 20, при втором броске — 21 и так далее: при n-ном броске — 2n-1. Другими словами, выигрыш возрастает от броска к броску вдвое, пробегая по степеням двойки — 1, 2, 4, 8, 16, 32 и так далее.
Нужно определить, какой размер вступительного взноса делает такую игру справедливой. Парадокс заключается в том, что вычисленное значение этого справедливого взноса равно бесконечности, то есть выше любого возможного выигрыша.
Не будем углубляться в способ решения этой задачи, но описанный в ней алгоритм полезен для жизни.
Вывод из этого, что не играй в игру, в которой ты нем можешь влиять на ход игры. Например, в казино каждый следующий ход определяет крупье, а не Вы. Вы не можете влиять на величину ставки, как в обычной игре. Так что не рискуйте.
Однако наука пошла дальше. Когда же вы можете играть. Лучше всех это решил немецкий математик Феллер. Он предложил игру, где игрок ставит, только если определит количество бросаний. И тогда нашел формулу, показывающую вероятность беспроигрышной игры. Также были решения, при котором число повторений игры определялась ограничением поставленной суммы. Тогда алгоритм может быть задан.
Как всегда в результате парадокс. Вы может выиграть, если будете переделывать правила игры под себя.
Как говорила моя внучка при игре в карты: « Мы играем не правильно!»
- А как правильно?
- Так чтобы я выигрывала.
Теперь посмотрим динамическую игру без планирования.
Мы делаем шаг за шагом и на каждом шагу, и после сделанного шага делаем оценку, что мы достигли и решить, куда двигаться дальше. Эту остановку назовем состоянием. Итак, сделав шаг, можно двинутся дальше или, поняв, что он неверный вернутся обратно. Если сделано несколько шагов, то обратно можно вернуться на несколько шагов или даже в начало и двигаться в другом направлении, как говорят теоретики, образуя «розу цепочек состояний». Любопытное рассмотрение возможного поведения людей и «зверюшек», показало, что у человека больше способностей для выбора большего числа продолжений.
Еще удивительней оказалось поведения коллектива автоматов.
Автоматы показали, что при голосовании, где каждый преследует свою выгоду, принимаются не оптимальные решения, а удовлетворяющие в среднем, что мы, как правило, и наблюдаем в жизни.
Теперь коротко можно говорить об играх с противником. Это не природа, которая может быть непредсказуемой, но она не играет в свою пользу против вас. Это сознательный противник. На каждый Ваш ход он отвечает так, чтобы обыграть вас. Вам нет выхода и делая каждый ход, вы должны, кроме своей выгоды, уменьшать вред, который противник может нанести своим ответом.
Самый интересный вывод, что если собрались два абсолютно умных противника им не выиграть друг у друга.
Выиграть можно тогда, когда один из противников ошибается или другой рискует. Риск заключается в том, что он готовит ход, который противник не ожидает.
Наиболее известен, ход маршала Жукова при обороне Ленинграда, когда он предугадал, что немецкий фельдмаршал фон Лееб пойдет в обход Пулковских высот. Были сняты войска с других направления и брошены на Пулковские высоты. Город был беззащитен, если бы его атаковали с других направлений.
Но немецкая военная школа была непреклонна. И когда началось наступление в обход Пулковских высот, эта была победа до начала сражения.
Вот такая математика.
Можно продолжать и дальше на тему математика и жизнь. Но я посмотрю насколько это кому-то интересно кроме меня. А может мой передатчик не может передать эту информацию Вашему приемнику.