Podręcznik

Źródło informacji jest matematycznym modelem bytu fizycznego, który w sposób losowy generuje (dostarcza, emituje) sukcesywnie symbole. Przyjmując stochastyczny model źródła informacji dobrze opisujący niepewność zakładamy, iż informacja jest realizacją pewnej zmiennej losowej (procesu losowego czy dokładniej łańcucha (Łańcuchem stochastycznym nazwiemy proces stochastyczny z argumentem ziarnistym) o określonych właściwościach statystycznych. Model informacji, w którym zakładamy, że ma on charakter realizacji zmiennej, łańcucha lub procesu stochastycznego o znanych właściwościach statystycznych (istnieją i są znane rozkłady prawdopodobieństwa informacji), nazywany jest modelem z pełną informacją statystyczną lub krócej - modelem probabilistycznym. 

Ze względów praktycznych szczególnie interesujące są probabilistyczne modele źródeł informacji, a analiza została ograniczona do dyskretnych źródeł informacji. Dla takich modeli obowiązują twierdzenia graniczne, w tym prawa wielkich liczb, z których wynika, że przy dostatecznie dużej liczbie niezależnych obserwacji częstości występowania określonych postaci informacji będą zbliżone do prawdopodobieństw ich występowania. Częstościowe określanie prawdopodobieństw jest tym dokładniejsze, im liczniejsze zbiory są podstawą wyznaczenia prawdopodobieństw.

W kontekście implementacji metod kodowania wygodniej jest mówić o wagach symboli. Jest to liczba wystąpień danego symbolu wogóle lub też w określonym kontekście. Podzielona przez liczbę wystąpień wszystkich symboli jest miarą częstości występowania symbolu, przybliżeniem (estymacją) prawdopodobieństwa.

Proces generacji informacji modelowany za pomocą źródła informacji $S$ polega na dostarczaniu przez źródło sekwencji (ciągu) symboli $\mathbf{s}=(s_1,s_2,\ldots)$) wybranych ze skończonego alfabetu $A_{S}$(czyli $s_{i}\in A_{S}$) według pewnych reguł opisanych zmienną losową o wartościach $s$. Bardziej ogólnie probabilistycznym modelem ciągu informacji elementarnych jest sekwencja zmiennych losowych $(S_1,S_2,\ldots)$  traktowana jako proces stochastyczny (dokładniej łańcuch). Właściwości źródła określone są wtedy przez parametry procesu stochastycznego (prawdopodobieństwa łączne, charakterystyka stacjonarności itd.). Stacjonarność źródła w naszych rozważaniach jest rozumiana w kontekście procesu, którego realizacją jest dana informacja. Rozważmy przestrzeń symboli (dyskretnych próbek) generowanych ze źródła jako zbiór wszystkich możliwych sekwencji symboli wraz z prawdopodobieństwami zdarzeń rozumianych jako występowanie rozmaitych zestawów tych sekwencji. Zdefiniujmy także przesunięcie jako transformację $T$określoną na tej przestrzeni sekwencji źródła, która przekształca daną sekwencję na nową poprzez jej przesunięcie o pojedynczą jednostkę czasu w lewo (jest to modelowanie wpływu czasu na daną sekwencję), czyli  $T(s_{1},s_{2},s_{3},\ldots)=(s_{2},s_{3},s_{4},\ldots)$. Jeśli prawdopodobieństwo dowolnego zdarzenia (zestawu sekwencji) nie ulegnie zmianie poprzez przesunięcie tego zdarzenia, czyli przesunięcie wszystkich sekwencji składających się na to zdarzenie, wtedy transformacja przesunięcia jest zwana niezmienniczą (inwariantną), a proces losowy jest stacjonarny. Teoria stacjonarnych procesów losowych może być więc traktowana jako podzbiór teorii procesów ergodycznych, odnoszącej się do śledzenia zachowania średniej po czasie oraz po próbkach procesów w całej definiowanej przestrzeni.

Warto przypomnieć, że w źródle będącym realizacją procesu ergodycznego każda generowana sekwencja symboli ma te same właściwości statystyczne. Momenty statystyczne procesu, rozkłady prawdopodobieństw itp. wyznaczone z poszczególnych sekwencji zbiegają do określonych postaci granicznych przy zwiększaniu długości sekwencji, niezależnie od wyboru sekwencji. W rzeczywistości nie jest to prawdziwe dla każdej sekwencji procesu ergodycznego, ale zbiór przypadków, dla których jest to fałszywe, występuje z prawdopodobieństwem równym 0. Stąd dla stacjonarnych procesów ergodycznych możliwe jest wyznaczenie parametrów statystycznych (średniej, wariancji, funkcji autokorelacji itp.) na podstawie zarejestrowanej sekwencji danych (symboli, próbek) $\{s_{i}\}_{i=1,2,\ldots}$, co jest wykorzystywane w praktycznych algorytmach kodowania, opartych na przedstawionych poniżej uproszczonych modelach źródeł informacji.

Model bez pamięci - DMS

Najprostszą postacią źródła informacji $S$ jest dyskretne źródło bez pamięci DMS (discrete memoryless source), w którym sukcesywnie emitowane przez źródło symbole są statystycznie niezależne. Źródło DMS jest całkowicie zdefiniowane przez zbiór wszystkich możliwych wartości $s$ zmiennej losowej, tj. zbiór symboli tworzących alfabet $A_{S}=\{a_{1},a_{2},\ldots,a_{n}\}$, oraz zbiór wartości prawdopodobieństw występowania poszczególnych symboli alfabetu: $P_S=\{p_1,p_2,\ldots,p_n\}$, gdzie$\Pr(s=a_{i})=P(a_{i})=p_i$, $p_{i}\geq 0$ i $\sum_{s\in A_S}P(s)=1$.

Można sobie wyobrazić, że źródło o alfabecie $A_{S}$ zamiast pojedynczych symboli generuje bloki $N$ symboli z alfabetu źródła, czyli struktura pojedynczej informacji jest ciągiem $N$ dowolnych symboli źródła. W takim przypadku można zdefiniować nowe źródło $S^{N}$ o $n^{N}$ elementowym alfabecie, zawierającym wszystkie możliwe $N$ - elementowe ciągi symboli. Rozszerzony alfabet takiego źródła jest następujący:$A_{S}^{N}=\underbrace{A_{S}\times A_{S}\times \cdots \times A_{S}}_{N}$, czyli $A_{S}^{N}=\{(a_{i_{1}},a_{i_{2}},\ldots,a_{i_{N}}): \forall_{j\in \{1,\ldots,N\}} a_{i_{j}}\in A_{S}\}=(\mathbf{a}_{1},\mathbf{a}_{2},\ldots,\mathbf{a}_{i},\ldots \mathbf{a}_{n^{N}})$. Prawdopodobieństwo i-tego elementu alfabetu wynosi $P(\mathbf{a}_{i})=P(a_{i_{1}})P(a_{i_{2}})$$\cdots P(a_{i_{N}})$ (mamy do czynienia ze źródłem bez pamięci). Źródło $S^{N}$ jest nazywane rozszerzeniem stopnia $N$ źródła $S$.

Model z pamięcią (warunkowy) - CSM

Jakkolwiek model DMS spełnia założenia prostej, wygodnej w analizie struktury, to jednak w wielu zastosowaniach jest nieprzydatny ze względu na małą zgodność z charakterem opisywanej informacji. Założenie o statystycznej niezależności kolejnych zdarzeń emisji symbolu jest bardzo rzadko spełnione w praktyce. Aby lepiej wyrazić rzeczywistą informację zawartą w zbiorze danych, konstruuje się tzw. model warunkowy źródła - CSM (conditional source model), zwany także modelem z pamięcią w odróżnieniu od modelu DMS. Jest to ogólna postać modelu źródła informacji, którego szczególnym przypadkiem jest DMS, a także często wykorzystywany model źródła Markowa.

Modele źródeł z pamięcią, najczęściej ograniczoną, pozwalają z większą dokładnością przewidzieć pojawienie się poszczególnych symboli alfabetu źródła (strumień danych staje się lepiej określony przez model źródła). Koncepcja pamięci źródła jest realizowana poprzez określenie kontekstu (czasowego), który ma wpływ na prawdopodobieństwo wyemitowania przez źródło konkretnych symboli w danej chwili. W każdej kolejnej chwili czasowej t, po wcześniejszym odebraniu ze źródła sekwencji symboli $\mathbf{s}^{t}=(s_{1},s_{2},\ldots,s_{t})$, można na podstawie \mathbf{s}^{t} (tj. przeszłości) wnioskować o postaci kolejnego oczekiwanego symbolu   poprzez określenie rozkładu prawdopodobieństw warunkowych P(\cdot |\mathbf{s}^{t}).

Zbiór wszystkich dostępnych z przeszłości danych $\mathbf{s}^{t}$ stanowi pełny kontekst wystąpienia symbolu $s_{t+1}$. Kontekst C wykorzystywany w obliczanym rozkładzie $P(\cdot |C)$ do modelowania lokalnych zależności danych dla różnych źródeł informacji stanowi zwykle skończony podzbiór $\mathbf{s}^{t}$. Może być także wynikiem redukcji alfabetu źródła, przekształceń wykonanych na symbolach $\mathbf{s}^{t}$ itp. Reguły określenia C mogą być stałe w całym procesie generacji symboli przez źródło lub też mogą ulegać adaptacyjnym zmianom (np. w zależności od postaci ciągu symboli wcześniej wyemitowanych przez źródło).

Model źródła S z pamięcią jest określony poprzez:

•  alfabet symboli źródła $A_S=\{a_1,a_2,\ldots,a_n\}$,
• zbiór kontekstów C dla źródła S postaci $A_C^S=\{\mathbf{b}_{1},\mathbf{b}_{2},\ldots,\mathbf{b}_{k}\}$,
• prawdopodobieństwa warunkowe $P(a_{i}|\mathbf{b}_{j})$ dla i =1,2,...,n oraz j =1,2,...,k, często wyznaczane metodą częstościową z zależności

gdzie $N(a_{i},\mathbf{b}_{j})$ - liczba łącznych wystąpień symbolu $N(a_{i},\mathbf{b}_{j})$ i kontekstu $\mathbf{b}_{j}, N(\mathbf{b}_{j})$ - liczba wystąpień kontekstu $\mathbf{b}_{j}$, przy czym jeśli $N(\mathbf{b}_{j})=0$ dla pewnych j (taki kontekst wystąpienia symbolu jeszcze się nie pojawił), wtedy można przyjąć każdy dowolny rozkład przy tym kontekście (wykorzystując np. wiedzę a priori do modelowania źródła w takich przypadkach),

• zasadę określania kontekstu C w każdej 'chwili czasowej' t jako funkcję f(\cdot ) symboli wcześniej wyemitowanych przez źródło.

Załóżmy, że źródło emituje sekwencję danych wejściowych \$mathbf{s}^t=(s_1,s_2,\ldots,s_l,\ldots,s_t)$, gdzie $s_{l}\in A_{S}$. Sekwencja kontekstów wystąpienia tych symboli jest określona przez funkcję $f(\cdot )$ oraz $A_{C}^{S}$ i przyjmuje postać: $\textbf{c}^t=(\mathbf{c}_{1},\mathbf{c}_{2},\ldots,\mathbf{c}_{l},\ldots,\mathbf{c}_{t})$, gdzie$\mathbf{c}_l=f(s_1,s_{2},\ldots,s_{l-1})\in A_C^S$ dla $l=2,\ldots,t$ (w przypadku symbolu $s_1$ brak jest symboli wcześniej wyemitowanych przez źródło, można więc przyjąć dowolny kontekst $\mathbf{c}_1)$. W ogólności $f(\cdot )$ wyznaczająca kontekst następnego symbolu $s_{t+1}$ musi być określona jako przekształcenie wszystkich możliwych sekwencji symboli z $A_S$ o długości t lub mniejszej w $A_C^S$. Ponieważ $\mathbf{s}^t$ jest jedyną dostępną sekwencją symboli wygenerowaną przez źródło S prawdopodobieństwa warunkowe określane są na podstawie $\mathbf{s}^t$ według zależności (1.2).

Istotnym parametrem modelu CSM jest rząd kontekstu C, który określa liczbę symboli tworzących kontekst $\mathbf{c}_l$ dla kolejnych symboli emitowanych przez źródło. Rozważmy prosty przykład sekwencji $\mathbf{s}^t$ ze źródła $S$ modelowanego rozkładem $P(a_i|\mathbf{b}_j)$ przy kontekstach kolejnych symboli $\mathbf{c}^l$ rzędu 1. Niech kontekst C stanowi symbol bezpośrednio poprzedzający kodowaną wartość $s_l: \mathbf{c}_l=f(s_1,s_2,\ldots,s_{l-1})=s_{l-1} dla i=2,\ldots,t$ oraz $\mathbf{c}_1=a_r\in A_S$ dla pewnego $1\leq r\leq n$. Wtedy $A_C^S=A_S$, a ten model CSM jest modelem źródła Markowa pierwszego rzędu. Generalnie, model źródła Markowa rzędu m jest bardzo powszechnie stosowaną realizacją CSM (model DMS jest modelem źródła Markowa rzędu 0).

Model źródła Markowa

Źródło Markowa rzędu m jest źródłem, w którym kontekst $C^{(m)}$ wystąpienia kolejnych symboli $s_{l}$ generowanych przez źródło S stanowi skończona liczba m poprzednich symboli $\mathbf{c}_l^{(m)}=(s_{l-1},s_{l-2},\ldots,s_{l-m})$, czyli dla dowolnych wartości l oraz $t\geq m P(s_{l}|s_{l-1},s_{l-2},\ldots,s_{l- t})=P(s_{l}|\mathbf{c}_l^{(m)})$. Zatem prawdopodobieństwo wystąpienia symbolu $a_{i}$ z alfabetu źródła zależy jedynie od m symboli, jakie pojawiły się bezpośrednio przed nim, przy czym określone jest przez zbiór prawdopodobieństw warunkowych (oznaczenia jak przy definicji źródła CSM):

dla wszystkich I oraz$j_{1},j_{2},\ldots,j_{m}=1,2,\ldots,n$.

Często źródło Markowa analizowane jest za pomocą diagramu stanów, jako znajdujące się w pewnym stanie, zależnym od skończonej liczby występujących poprzednio symboli - zobacz rys. 1. Dla źródła Markowa pierwszego rzędu jest n takich stanów, dla źródła rzędu m mamy n^m stanów.

Rys. 1 Diagramy stanów prostych modeli Markowa z alfabetem binarnym: a) ogólny model rzędu 1 z przejściami pomiędzy poszczególnymi stanami, b) model rzędu 2 z przykładowymi wartościami prawdopodobieństw warunkowych. Stany opisane są wszystkimi możliwymi kombinacjami kontekstów, zaś odpowiednie przejścia pomiędzy stanami źródła odzwierciedlają wystąpienie kolejnej danej źródłowej; w kontekście prawy symbol oznacza ten bezpośrednio poprzedzający, zaś lewy - to symbol jeszcze wcześniejszy.

Przy kompresji danych obrazowych efektywny kontekst budowany jest zwykle z najbliższych w przestrzeni obrazu pikseli, przy czym sposób określenia kontekstu może zmieniać się dynamicznie w trakcie procesu kodowania, np. zależnie od lokalnej statystyki. Popularną techniką jest taka kwantyzacja kontekstu (tj. zmniejszanie kontekstu w celu uzyskania bardziej wiarygodnego modelu prawdopodobieństw warunkowych), kiedy to liniowa kombinacja pewnej liczby sąsiednich symboli warunkuje wystąpienie symbolu, dając de facto model warunkowy pierwszego rzędu, zależny jednak od kilku- czy kilkunastoelementowego sąsiedztwa.

\subsection{Miary ilości informacji} \label{Punkt_miary_infor}