From 2a1cc7bd990b15a8496bf296bc50e4f85b471f94 Mon Sep 17 00:00:00 2001 From: Andrew Guschin Date: Sat, 23 Oct 2021 18:10:48 +0400 Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=B8=D0=BB=20=D1=81?= =?UTF-8?q?=D0=B5=D0=B4=D1=8C=D0=BC=D1=83=D1=8E=20=D0=BB=D0=B5=D0=BA=D1=86?= =?UTF-8?q?=D0=B8=D1=8F=20=D0=BF=D0=BE=20=D0=A2=D0=B5=D0=BE=D1=80=D0=B8?= =?UTF-8?q?=D0=B8=20=D0=B8=D0=BD=D1=84=D0=BE=D1=80=D0=BC=D0=B0=D1=86=D0=B8?= =?UTF-8?q?=D0=B8.?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- sem5/information-theory/lectures/lecture1.tex | 15 +- sem5/information-theory/lectures/lecture7.tex | 255 ++++++++++++++++++++++++++ 2 files changed, 264 insertions(+), 6 deletions(-) create mode 100644 sem5/information-theory/lectures/lecture7.tex (limited to 'sem5/information-theory/lectures') diff --git a/sem5/information-theory/lectures/lecture1.tex b/sem5/information-theory/lectures/lecture1.tex index 4a0c03d..2b112fa 100644 --- a/sem5/information-theory/lectures/lecture1.tex +++ b/sem5/information-theory/lectures/lecture1.tex @@ -52,10 +52,13 @@ По струкруте сообщения сигналы делятся на \emph{непрерывные} и \emph{дискретные}. Сигналы могут быть непрерывными и дискретными как по времени, так и по множеству значений. Возможен один из четырёх видов -сигналов: - полностью непрерывный сигнал (по времени \& множеству -значений) - непрерывный по множеству значений и дискретным по времени - -дискретный по множеству значений и непрерывным по времени - полностью -дискретный +сигналов: +\begin{itemize} + \item полностью непрерывный сигнал (по времени и множеству значений) + \item непрерывный по множеству значений и дискретным по времени + \item дискретный по множеству значений и непрерывным по времени + \item полностью дискретный +\end{itemize} Носителем сигнала всегда является объект или процесс. Однако если абстрагироваться от его физической природы, то существенными с точки @@ -122,14 +125,14 @@ $\frac{1}{\sqrt{\mu}}$, то мы получим ортонормированн \ldots{} . Получим \begin{equation*} - \int_{t_1}^{t_2} u(t) \phi_l(t) dt = + \int_{t_1}^{t_2} u(t) \phi_l(t) dt = \int_{t_1}^{t_2} \sum_{k = 1}^n C_k \phi_k(t) \phi_l(t) dt = \sum_{k = 1}^n C_k \int_{t_1}^{t_2} \phi_k(t) \phi_l(t) dt \end{equation*} Получаем \begin{equation*} - C_k = \int_{t_1}^{t_2} \phi(t) \phi_k(t) dt + C_k = \int_{t_1}^{t_2} \phi(t) \phi_k(t) dt \end{equation*} Исходя из этого получаем: diff --git a/sem5/information-theory/lectures/lecture7.tex b/sem5/information-theory/lectures/lecture7.tex new file mode 100644 index 0000000..21c1f00 --- /dev/null +++ b/sem5/information-theory/lectures/lecture7.tex @@ -0,0 +1,255 @@ +% Лекция (21.11.21) +\section{Каналы передачи информации} +Классической теорией информации является теория Шеннона. В основе её лежит +понятие, что человек принимает информацию к сведению постоянно устраняя +некоторую неопределённость. То есть чем больше случайных событий, снимающих +неопределённость системы, тем больше информации они несут. + +Дадим определение источника информации. Самым простым источником информации +является дискретный источник информации без памяти. Простейший дискретный +источник без памяти $X$ в каждый момент времени выдаёт некоторый символ $X_i$ из +конечного алфавита $X = \{x_1, x_2, \dots, x_n\}$ с вероятностью $P(x_i) = p_i$. +Как правило дискретные источники без памяти выбор символов производится +независимо друг от друга. Распределение информации при этом как правило +равномерное. В качестве примера можем привести источник без памяти двоичной +системы. $X = \{ x_1 = 0, x_2 = 1 \}$. Соответственно вероятность $0 \leq p_1 +\leq 1$, $p_2 = 1 - p_1$. При этом в данном источнике выбор очередной цифры +будет производиться независимо от прежних последовательностей и схематически +данный источник можно изобразить следующим образом: **рисунок**. + +Для определения количества информации такого источника используются следующие +три аксиомы. + +\begin{axiom} + Информация одиночного события $x_i \in X$ происходящего с вероятностью $p_i$ + имеет положительное значение. +\end{axiom} + +\begin{axiom} + Совместная информация двух независимых событий $x_i, x_j \in X$ с совместной + вероятностью $P_{ij}$ равно сумме их информаций. + \begin{equation*} + P(x_i, x_j) = P_{ij} = P_i \cdot P_j, \, I(P_{ij}) = I(P_i) + I(P_j) + \end{equation*} +\end{axiom} + +\begin{axiom} + Информация является непрерывной функцией от вероятности события. +\end{axiom} + +Следует отметить, что акс 1 и 2 утверждают то, что информация нескольких событий +не может взаимно уничтожаться. Акс 2 вводит понятие совместной информации +событий. Аксиома 3 говорит о том, что небольшое изменение вероятности событий +приводит к небольшому изменению её информации. Аксиома 2 определяет информацию +двух независимых событий. + +Согласно аксиоме 2 можно заключить, что информация события определяется +как логарифмическая функция её вероятности. Информация события происходящая +с вероятностью $P$ будет равна $I(P) = -\log(P)$. Причём основание логарифма +будет определять алфавит события и единицы измерения информации. + +Наряду с двоичным логарифмом наиболее часто используют натуральный логарифм, +при этом единицы измерения называются ``наты''. + +Исходя из аксиомы 3 можно заключить, что информация постоянно происходящего +события будет равна нулю. Соответственно информация для невозможного события +стремится к бесконечности. + +\subsection{Энтропия и избыточность} + +Рассмотрим источник события. Для его описания будем использовать информацию, +которую несут происходящие в нём события. По аналогии с термодинамикой +введём понятие \textbf{энтропии} как меры неопределённости. + +\textbf{Энтропия} --- это функция, которая возрастает, когда неопределённость +системы возрастает. Неупорядоченность системы. Таким образом, используя +информацию отдельных событий в источнике выразим энтропию следующим образом. + +Энтропия простейшего источник без памяти с алфавитом $X = \{ x_1, x_2, \dots, +x_n \}$ и соответствующими вероятностями $P = \{ p_1, \dots, p_n \}$ будет +обозначаться +\begin{equation*} + H = \sum_{i}^n -P_i \log(P_i) +\end{equation*} + +Предположим эргодичность источника (постоянство поведения). Будем рассматривать +эргодичность во времени. Если провести аналогию с теорией вероятности, то +процесс эргодичности предполагается когда мы бросаем кубик или монетку. +При этом с ростом числа испытаний среднее значение информации источника будет +вычисляться следующим образом: +\begin{equation*} + \overline{I} = \lim_{N \to \infty} \frac{1}{N} \sum_{n = 0}^{N - 1} I(n) +\end{equation*} + +Устремив данное выражение к математическому ожиданию мы получим, что данная +формула будет стремиться к формуле энтропии. Проводя аналогичные рассуждения +Шеннон положил в определение энтропии три следующих аксиомы: + +\begin{axiom} + Энтропия является непрерывной функцией вероятности. Для источников, в которых + события равновероятны и вероятность каждого события равна единица делить на + количество событий. +\end{axiom} + +\begin{axiom} + Энтропия будет возрастать с ростом числа событий. +\end{axiom} + +\begin{axiom} + Разложение процедуры выбора событий на несколько этапов не изменяет энтропию. +\end{axiom} + +Определим максимальную энтропию источника. Для этого воспользуемся теоремой +Шеннона. + +\begin{theorem} + Энтропия простейшего дискретного источника без памяти максимальна, если все + события в нём имеют одинаковую вероятность и в этом случае энтропия будет + равна логарифму от числа событий. $H_0 = \log N$ +\end{theorem} +\begin{proof} + Пусть имеется два дискретных источника $P = \{ p_i \}$ и $Q = \{ q_i \}$ + каждый из которых генерирует свои события. Всего есть $N$ событий . Для + доказательства теоремы нам понадобится верхняя оценка логарифмической функции: + $\ln x \leq x - 1$ Используя оценку получаем, что + \begin{equation*} + \ln q_i - \ln p_i = \ln \frac{q_i}{p_i} \leq \frac{q_i}{p_i} - 1 + \end{equation*} + + Умножив обе части данного равенства на вероятность $p_i$ и просуммировав по + всем событиям $N$ мы получим + \begin{equation*} + \sum_{i = 1}^N p_i (\ln q_i - \ln p_i) \leq \sum_{i = 1}^N p_i(\frac{q_i}{p_i} - 1) + \end{equation*} + + Получаем + \begin{equation*} + H(P) + \sum_{i = 1}^N p_i \ln q_i \leq \sum_{i = 1}^N q_i - \sum_{i = 1}^N p_i = 0 + \end{equation*} + + Таким образом, можем заключить, что энтропия равна + \begin{equation*} + H(P) \leq -\sum_{i = 1}^N p_i \ln q_i = + \end{equation*} + + Если предположить, что источник $Q$ содержит только равновероятные события, + то эта сумма будет равна + \begin{equation*} + = -\sum_{i = 1}^N p_i \ln \frac{1}{N} = \ln N \sum_{i = 1}^N p_i = \ln N + \end{equation*} + + Таким образом при доказательстве на источник $P$ не накладывались никакие + ограничения, то данное неравенство имеет место для любого дискретного + источника без памяти, который содержит $N$ событий. + + Получаем \begin{equation*} + H(x) \leq \log N + \end{equation*} +\end{proof} + +Соответственно максимум достигается тогда, когда имеются одинаковые события. + +\begin{corollary} + Любой источник, содержащий $N$ событий не все из которых имеют одинаковую + вероятность обладает энтропией меньшей, чем $\log N$ +\end{corollary} + +\begin{definition} + Рассмотрим источник событий, который имеет ёмкость $H_0 = \log N$. ДАнный + источник будет являться резервуаром, который никогда не переполняется + и зависит только от количества событий. + + Пусть есть источник $X$ в котором не все события равновероятны, который также + состоит из $N$ событий. + + Разность $R = H_0 - H(X)$ называется \textbf{избыточностью источника}. +\end{definition} + +\begin{equation*} + r = \frac{R}{H_0} = 1 - \frac{H(X)}{H_0} +\end{equation*} + +\begin{definition} + Введём понятие функции Шеннона. Пусть задан двоичный алфавит и есть + источник событий. $P_0 = P$, $P_1 = 1 - P_0$. Выбор символа производится + независимо, соответственно энтропия данного источника будет называться + функцией Шеннона и будет зависеть только от вероятности $P$. + + \begin{equation*} + H(P) = -P \log P - (1 - P) \log(1 - P) + \end{equation*} + + Функция Шеннона всегда положительна и симметрична относительно значения $0.5$. + **рисунок** +\end{definition} + +\subsection{Энтропия связанных источников. Понятие взаимной и условной информации.} + +При аксиономическом ... . Рассмотрим это понятие более подробно. Пусть у нас +есть два источника: $X$ и $Y$. Пусть эти источники связаны между собой. +Результатом работы данных источников будет пара $(x_i, y_i)$. +Если два источника связаны между собой, то события одного источника будут +влиять на события другого источника. То есть по событиям источника $X$ мы +можем предсказать события источника $Y$, то есть в терминах теории информации, +можно определить, что из-за влияния источника $X$ снижается неопределённость +источника $Y$. $P(x_i, y_i) \neq P(x_i) + P(y_i)$ + +То есть данные источники обмениваются какой-то дополнительной информации. Для +определения данной информации введём понятие условной вероятности. Введём +совместную вероятность через их априорные условные вероятности. + +\begin{equation*} + P(x_i, y_i) = P(x_i / y_i) P(y_i) = P(y_i / x_i) P(x_i) +\end{equation*} + +\begin{equation*} + \log P(x_i, y_i) = \log P(x_i / y_i) + \log P(y_i) = \log P(x_i / y_i) + -I(y_i) +\end{equation*} + +То есть +\begin{equation*} + I(x_i, y_i) = I(y_i) - \log P(x_i / y_i) = I(x_i) - \log P(y_i / x_i) +\end{equation*} + +Прибавляя и одновременно вычитая в первой части $I(x_i)$, а во второй части +$I(y_i)$ мы получим следующую формулу: +\begin{equation*} + I(x_i, y_i) = I(x_i) + I(y_i) - \log \frac{P(x_i / y_i)}{P(x_i)} = + I(x_i) + I(y_i) - \log \frac{P(y_i/x_y)}{P(y_i)} +\end{equation*} + +Таким образом если источники связаны, то информация пары $(x_i, y_i)$ +определяется суммой информаций этих событий за вычетом некоторой неотрицательной +величины, которая также снимает неопределённость и, следовательно, тоже является +информацией. Такую информацию называют взаимной информацией пары событий. +Обозначается +\begin{equation*} + I(x_i, y_i) = \log \frac{P(x_i/y_i)}{P(y_i)} = \log \frac{P(y_i/x_i)}{P(x_i)} +\end{equation*} + +Следует отметить, что $I(x_i, y_i)$ всегда положительная и является симметричной +относительно источников. Симметричность относительно источников показывает, +что источники обмениваются взаимной информацией друг с другом, а не в +одностороннем порядке. Возможны два граничных случая: +\begin{enumerate} + \item + Источники независимы. Тогда совместная информация равна нулю (источники не + обмениваются информацией). + \item + Источники жёстко связаны между собой. То есть события одного источника + однозначно определяют события другого источника. То есть условная + вероятность будет равна единице. В этом случае взаимная информация будет + равна информации первого источника и также равна информации второго + источника. +\end{enumerate} + +Введём понятие условной информации. Условная информация будет называться +информация $I(x_i / y_i) = -\log P(x_i / y_i)$. Тогда взаимная информация +через условную будет выражаться следующим образом: +\begin{equation*} + I(x_i, y_i) = I(x_i) + I(y_i / x_i) = I(y_i) + I(x_i / y_i) +\end{equation*} + +То есть информацию пары событий можно определить как сумму информаций событий +источника $Y$ и информации источника событий $X$ при условии, что события +$Y$ уже известно, или наоборот. \ No newline at end of file -- cgit v1.2.3