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

Вид материала

Содержание

Занятие № 3. Условная энтропия. Решение задач на условную энтропию
Задачи занятия
Решение задачи № 1 / 3
Задача № 2/3.
Задача № 3\3.
Домашнее задание

Подобный материал:

1 2 3 4 5

Занятие № 3. Условная энтропия. Решение задач на условную энтропию

Цель занятия: введение понятия условной энтропии для решения соответствующих задач.

Задачи занятия:

Ввести понятие условной энтропии;
Обозначить тип задач, решаемых с применением условной энтропии;
Ввести алгоритм решения задач на условную энтропию;
Разобрать набор задач;
Ввести свойства энтропии, привести доказательство;

План занятия:

Проблемная ситуация через задачу 1 / 3
Разбор Графа условной энтропии в общем виде;
Применение общих подходов к конкретной ситуации;
Решение задач 2 / 3 – 4 / 3
Свойства энтропии. Доказательство свойства № 5.
Домашнее задание.

Ход занятия:

Задача № 1/3. Какую энтропию содержит опыт угадывания простой цифры при извлечении из цифровой азбуки при условии, что одна карточка утеряна?

А

нализ условия показывает, что задача отличается от предыдущих, т.к. есть дополнительное условие. Такие задачи принято относить к условной энтропии.

Условной энтропией опыта β относительно опыта α называется математическое ожидание условной энтропии опыта β относительно всех исходов опыта α: Н (β/α) = ∑Р(А_i) Н (β/А_i), где Н (β/А_i) – условная энтропия опыта β относительно исхода А_i

Н

(β/А_i) = ∑ [Р(В_j/А_i) log (Р(В_j/А_i))^-1] Граф нахождения условной энтропии выглядит следующим образом:

Решение задачи № 1 / 3:

Н (β /α) = Р(А₁) Н (β/А₁)+ Р(А₂) Н (β/А₂)

Опыт α = {утеряна одна карточка} = {А₁, А₂}

А₁ = {утеряна карточка с простой цифрой}, n(А₁) = 4, Р(А₁)= 4/10 =2/5,

А₂= {утеряна карточка с непростой цифрой}, n(А₂) = 6, Р(А₂)= 6 /10 =3/5

β = {угадывание карточки с простой цифрой}

Н (β/А₁) определяется с учетом того, что утеряна карточка с простой цифрой и их осталось 3 среди 9 карточек: Н (β/А₁) = 3/9 log 9/3 + 6/9 log 9/6 = log3-2/3, аналогично считаем

Н (β/А₂) = 4 /9 log 9/4 + 5/9 log 9/5 = 2log3-5/9 log5 -8/9;

Н (β /α)=2/5(log3-2/3) + 3/5(2log3-5/9 log5 -8/9) = (8/5log3- 1/3log5 – 4/5) = 1,6 *1,6 –0,33*2,33 – 0,8 ≈ 1(бит).

П

остроим граф двух зависимых опытов α и β:

опыт α

Ответ: 1 бит.

Задача № 2/3. Какую неопределенность содержит опыт угадывания четности суммы очков случайно взятой кости домино, если известно, что одна кость утеряна?

Р

опыт α
ешение: утеряна может быть кость с четной суммой или с нечетной, что задает предварительный опыт α:

Ответ: 17/7log3 -20/63log5 – 11/63log11 – 32/21(бит)

Задача № 3\3. Найти энтропию угадывания простых цифр при извлечении двух карточек из цифровой азбуки.

Решение: Из десяти цифр четыре являются простыми: 2,3,5,7.

Вероятность угадать простую цифру равна 4/10=2/5; Вероятность угадать непростую цифру равна 6/10 = 3/5.

Карточки с какими цифрами вытащены (простыми или непростыми – неизвестно)

Если первой выбрана карточка с простой цифрой, то вероятность для второй карточки 3/9 или 6/9; если первой выбрана карточка с непростой цифрой, то вероятность для второй карточки 5/9 или 4/9. Построим граф двух зависимых опытов α и β, учитывая, что Р(Пр, Пр)=2/15; Р(Пр, Пр)=4/15; Р(Пр, Пр)=4/15; Р(Пр, Пр)=1/3

опыт β

опыт α

Ответ:

Задача № 4/3. Найти энтропию угадывания простых цифр при извлечении трех карточек из цифровой азбуки.

Решение: Из десяти цифр четыре являются простыми: 2,3,5,7.

Вероятность выбрать простую цифру равна 4/10=2/5;

Вероятность выбрать непростую цифру равна 6/10 = 3/5.

Карточки с какими цифрами вытащены вторыми простыми или непростыми – неизвестно.

Н (α βγ)= 1/30log30 + 3(1/10log10) + 4(1/6 log6) = (1/30 + 1/30log5 +1/30log3 + 3/10 + 3/10log5 +2/3 + 2/3 log3)= (1/3 log5 + 7/10 log3 +1)(бит).

Ответ: (1/3 log5 + 7/10 log3 +1)(бит)

После решения такого количества задач можно обозначить свойства энтропии:

Н(α) ≥0 (очевидно)
Н(α) = 0, если Р (А_i) = 1, а все Р (А_j) = 0 (очевидно)
Н(α) – max, если все Р(А_i)=1/n, т.е. равновероятны
Н(αβ) = Н(α) + Н(β), если α и β - независимы
Н(αβ) = Н(α) + Н(β/α), в общем случае, если α, β содержат по два исхода
0 ≤Н(β/α) ≤ Н(β)
Н(α₁, …. α_k) ≤ Н(α₁) + …. Н( α_k)

Доказательство: 5. Н(αβ) = Н(α) + Н(β/α), в общем случае, если α, β содержат по два исхода

Пусть α={A_{1 ,}A₂} β={В_{1 ,}В₂}, тогда αβ = { A₁В_{1 ,}A₂ В_2, A₁В_2, A₂ В₁}

Н (α β)= -[Р(A₁В₁)log Р(A₁В₁)+Р(A₁В₂)log Р(A₁В₂)+Р(A₂В₁) log Р(A₂В₁) + Р(A₂В₂) log Р(A₂В₂)] = -Р(А₁)Р(В₁/А₁)[logР(A₁)+logР(В₁/A₁)] - Р(А₁)Р(В₂/А₁)[logР(A₁)+log Р(В₂/A₁)] - Р(А₂)Р(В₁/А₂)

[log Р(A₂)+ log Р(В₁/A₂)] - Р(А₂)Р(В₂/А₂)[ log Р(A₂)+ log Р(В₂/A₂)] = Н(α) + Р(А₁)Н(β/А₁) + Р(А₂) Н(β/А₂) = Н(α) + Н(β/α)

Домашнее задание: №1. Какую степень неопределенности содержит опыт извлечения двух костей домино относительно «дуплей»?

№ 2. Найти энтропию угадывания дней рождения двух случайно встреченных людей.

№3. Найти энтропию угадывания месяцев рождения двух случайно встреченных.

Blog

Содержание

Занятие № 3. Условная энтропия. Решение задач на условную энтропию