Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Лабораторная работа №3
Энтропия объединения двух систем. Оценка энтропии источника при использовании разных моделей
Предметом исследования лабораторной работы являются методы статистического контекстного моделирования нестационарного дискретного источника.
Цель работы – оценка значения частной условной энтропии нестационарного источника относительно статистики его предшествующих состояний.
В ходе работы требуется произвести моделирование игры «Чёт-нечёт» на основе данных матча двух людей; построить графики эффективности предсказания человеком, предсказаний на основе статистики контекстов разных длин и апостериорной статистики игры; вычислить значения частной условной энтропии загаданного значения относительно нескольких предшествующих ходов. Отчет по лабораторной работе оформить согласно требованиям ГОСТ 7.32-2001 «Отчет о научно-исследовательской работе. Структура и правила оформления» [].
Задачи лабораторной работы:
а) повторить теоретический материал []: энтропия объединения двух систем, частная и полная условная энтропия системы. При оформлении отчёта использовать материал разделов и , а также диаграммы приложения А;
б) произвести моделирование игры «Чёт-нечёт» с реализацией предсказания на основе:
в) произвести апробацию модели игры на данных игры двух людей; построить диаграммы результативности предсказания:
Проинтерпретировать результаты; сравнить с результатами игры с генератором случайных чисел (диаграммы приложения А).
д) выбрать один из ходов (желательно ближе к концу игры, когда имеется достаточная статистика по всем контекстам), ошибочно предсказанный контекстом глубины три, но верно предсказанный более коротким контекстом. По статистике, имеющейся к этому ходу:
Под объединением двух систем X и Y с возможными состояниями x1, x2, … xn и y1, y2, … ym понимается сложная система (X, Y), n m состояний которой (xi, yj) представляют собой комбинацию всех возможных состояний систем X и Y. Энтропия системы (X, Y) вычисляется по формуле:
, ()
где pij – вероятность того, что система находится в состоянии (xi, yj).
Если системы X и Y независимы, формулу () можно записать в виде:
H (X, Y) = H (X) + H (Y). ()
Если X и Y зависимы, Y находится в состоянии yj, а X может принять состояние xi с вероятностью p (xi | yj), то частная условная энтропия системы X относительно Y:
. ()
Среднее значение H (X | yj) по всем возможным yj является полной условной энтропией системы X относительно Y:
, ()
где p(yj)– безусловная вероятность наступления состояния yj системы Y.
В общем случае формула энтропии объединения двух систем () может быть записана как:
H (X, Y) = H (X) + H (X | Y) = H (Y) + H (Y | X). ()
Формула () является частным случаем () и максимальным значением H (X, Y) [].
Игра «Чёт-нечёт» заключается в угадывании одним игроком двоичного значения, загаданного другим игроком. При продолжительной игре каждая сторона пытается предугадать логику противника по истории прошлых ходов. Победитель определяется в зависимости от количества удачно предсказанных ходов.
Представим загадывающего как двоичный нестационарный источник X, множеством возможных сообщений которого является {0; 1}. Пусть k ходов уже сделано; x1, x2, … xk – история предыдущих загаданных значений; xk+1 – ожидаемое сообщение от X (новое загаданное значение), которое требуется предсказать; xk+1(h) – значение xk+1, предсказываемое человеком.
По ходу игры ведётся следующая статистика: число загаданных за k ходов нулей и единиц fk(0) и fk(1); количество биграмм – загаданных подряд 00, 01, 10 и 11 – fk(00), fk(01), fk(10) и fk(11); а также частоты различных комбинаций загаданных подряд трёх и четырёх значений: fk(000), fk(001), … fk(111) и fk(0000), fk(0001), … fk(1111); всего 2+4+8+16=30 счётчиков. Пусть, например, последними загаданными значениями были xk-2xk-1xk = 010. На основе накопленной статистики могут быть вычислены условные статистические вероятности того, что xk+1=1:
p (1 | 010) = fk(0101)/( fk(0100) + fk(0101)); ()
p (1 | 10) = fk(101)/( fk(100) + fk(101)); ()
p (1 | 0) = fk(01)/( fk(00) + fk(01)); ()
p (1) = fk(1)/( fk(0) + fk(1)). ()
В случае, если контекст 010 уже встречался ранее, fk(0100) и fk(0101) покажут, какое из значений встречалось следом за этим контекстом чаще. Если fk(0100) и fk(0101) не равны, сделаем предсказание xk+1(3) на основе контекста глубины три: если p (1 | 010) > 0,5, полагаем xk+1(3) равным единице и нулю в противном случае. Если fk(0100) и fk(0101) равны, обратимся к предсказанию xk+1(2), сделанному на основе статистики по контексту глубины два и вероятности p (1 | 10). Если и эта статистика не может помочь сделать предпочтение, будем использовать p (1 | 0) и предсказание xk+1(1); и так далее. Если не поможет и p (1), сделаем случайное предсказание с использованием генератора случайных чисел.
Предложенный алгоритм использует пять статистических моделей, каждая из которых способна дать собственное предсказание xk+1(3), xk+1(2), xk+1(1), xk+1(0) и xk+1(-1), где число в верхнем индексе обозначает глубину контекста; глубина ноль означает, что используется безусловные частоты значений; минус один – значения предсказать невозможно, xk+1(-1) является случайным двоичным числом с равновероятными исходами. Для простоты расчётов предпочтение отдаётся контекстам с большей глубиной; младшие контексты используются, только когда старшие не предсказывают.
Приложение А содержит диаграммы с динамикой игры в «Чёт-нечёт» с генератором случайных чисел Microsoft Excel. На обоих рисунках изображены четыре графика, отражающих эффективность предсказания с помощью оценки xk+1(-1) (синяя линия), xk+1(0) (чёрный пунктир), xk+1(3) (красные точки) и xk+1(posterior 3) (тёмно-красные треугольники). Предсказание xk+1(posterior 3) аналогично xk+1(3), только использует апостериорную статистику – значение счётчиков, которое установится после окончания игры. На обоих рисунках по горизонтальной оси отложено количество ходов, а по вертикали на рисунке – количество удачных предсказаний каждой модели, на рисунке – отношение числа удачных предсказаний к числу ходов. Диаграммы демонстрируют, что все использованные модели дают в среднем одинаковый результат (со случайным отклонением) – предсказание в 50% случаев. Неэффективность предсказания с помощью использованных моделей объясняется отсутствием контекстной зависимости в последовательности случайных чисел, сгенерированной Microsoft Excel, чего и следовало ожидать.
Список использованных источников
Методические указания по оформлению текстовых документов при выполнении учебных заданий студентами всех курсов специальности 220200 / А.В. Никонов. Режим доступа: Кафедральный сервер: [Оформление2.doc] / Омск. гос. техн. ун-т. Каф. АСОИУ. – Омск, 2002.
Куликовский Л.Ф., Мотов В.В. Теоретические основы информационных процессов: Учеб. пособие для вузов по спец. «Автоматизация и механизация процессов обработки и выдачи информации». – М.: Высш. шк., 1987. – 248 с.
Приложение А
(обязательное)
Диаграммы предсказаний генератора случайных чисел
Рисунок А. – Диаграмма удачных предсказаний генератора случайных чисел
Рисунок А. – Диаграмма коэффициента удачных предсказаний генератора случайных чисел
5