Algorytm Blahuta-Arimoto

Termin algorytm Blahuta-Arimoto jest często używany w odniesieniu do klasy algorytmów do numerycznego obliczania teoretycznej pojemności informacyjnej kanału, funkcji zniekształcenia szybkości źródła lub kodowania źródła (tj. kompresji w celu usunięcia nadmiarowości). Są to algorytmy iteracyjne , które ostatecznie zbiegają się do jednego z maksimów problemu optymalizacyjnego , który jest związany z tymi koncepcjami teorii informacji.

Historia i zastosowanie

W przypadku pojemności kanału algorytm został niezależnie wynaleziony przez Suguru Arimoto i Richarda Blahuta . Ponadto podejście Blahuta daje algorytmy do obliczania zniekształcenia szybkości i uogólnionej przepustowości z ograniczeniami wejściowymi (tj. funkcja przepustowości-kosztu, analogiczna do zniekształcenia szybkości). Algorytmy te mają największe zastosowanie w przypadku dowolnych skończonych źródeł alfabetu. Wykonano wiele pracy, aby rozszerzyć go na bardziej ogólne przypadki problemów. Niedawno zaproponowano wersję algorytmu uwzględniającą wyjścia ciągłe i wielowymiarowe z zastosowaniami w sygnalizacji komórkowej. Istnieje również wersja algorytmu Blahuta-Arimoto dla informacji kierowanej .

Algorytm pojemności kanału

Dyskretny kanał bez pamięci (DMC) można określić za pomocą dwóch zmiennych losowych ${\ mathcal {X}}, {\ mathcal {Y}}$ X $\ Displaystyle$ i prawo kanału jako rozkład prawdopodobieństwa warunkowego ${\ Displaystyle p (y | x)}$ . Pojemność kanału , $_$ _ komunikować się w jednostce bitu na użycie. Teraz, jeśli oznaczymy liczność ${\ Displaystyle | {\ mathcal {X}} | = n, | {\ mathcal {Y}} | = m}$ , a następnie ${\ Displaystyle p_ {Y|X}}$ jest macierzą ${\ displaystyle n \ razy m}$ , którą oznaczamy wierszem, $\ displaystyle i ^ {th}}$${\ displaystyle j ^ {th}}$ wpis w kolumnie przez ${\ displaystyle w_ {ij}}$ . W przypadku pojemności kanału algorytm został niezależnie wynaleziony przez Suguru Arimoto i Richarda Blahuta . niezależnie znalazł następujące wyrażenie określające pojemność DMC z prawem kanału:

${\ Displaystyle C = \ max _ {\ mathbf {p}} \ max _ {Q }\sum _{i=1}^{n}\sum _{j=1}^{m}p_{i}w_{ij}\log \left({\dfrac {Q_{ji}}{p_{ i}}}\prawo)}$

gdzie i są maksymalizowane przy następujących wymaganiach: $\ displaystyle \ mathbf {p}$${$

• ${\ displaystyle \ mathbf {p}}$ jest rozkładem prawdopodobieństwa na ${\ displaystyle X}$ , to znaczy, jeśli napiszemy ${\ displaystyle \ mathbf {p}}$ jako ${\ Displaystyle (p_ {1}, p_ {2} ..., p_ {n}), \ suma _ {i = 1} ^ {n} p_ {i }=1}$
• $\ Displaystyle Q = (q_ {ji})}$$Displaystyle$ jest , która zachowuje się jak macierz przejścia z $Y}$ do $Y} displaystyle X}$ w odniesieniu do prawa kanału. To znaczy dla wszystkich ${\ Displaystyle 1 \ równoważnik i \ równoważnik n, 1 \ równoważnik j \ równoważnik m}$ :
  • ${\ Displaystyle q_ {ji} \ geq 0, q_ {ji} = 0 \ strzałka w lewo w_ {ij} = 0}$
  • Każdy wiersz sumuje się do 1, tj. ${\ Displaystyle \ suma _ {i = 1} ^ {n} q_ {ji} = 1}$ .

Następnie po wybraniu losowego rozkładu prawdopodobieństwa ${\ Displaystyle \ mathbf {p} ^ {0}: = (p_ {1} ^ {0}, p_$${\ Displaystyle ( ( \mathbf {p} ^{0},Q^{0},\mathbf {p} _{1},Q^{1}...)}$$)$ na możemy wygenerować sekwencję iteracyjnie w następujący sposób:

${\ Displaystyle (q_ {ji} ^ {t}): = {\ dfrac {p_ {i} ^ { t}w_{ij}}{\suma _{k=1}^{n}p_{k}^{t}w_{kj}}}}$

${\ Displaystyle p_ {k} ^ {t +1}:={\dfrac {\prod _{j=1}^{m}(q_{jk}^{t})^{w_{kj}}}{\suma _{i=1}^{ n}\prod _{j=1}^{m}(q_{ji}^{t})^{w_{ij}}}}}$

dla ${\ Displaystyle t = 0,1,2 ...}$ .

Następnie, korzystając z teorii optymalizacji, a konkretnie zejścia współrzędnych , Yeung wykazał, że sekwencja rzeczywiście zbiega się do wymaganego maksimum. To jest,

${\ Displaystyle \ lim _ {t \ do \ infty} \ suma _ { i=1}^{n}\sum _{j=1}^{m}p_{i}^{t}w_{ij}\log \left({\dfrac {Q_{ji}^{t}} {p_{i}^{t}}}\right)=C}$ .

$,$ biorąc pod uwagę prawo kanału numerycznie z dowolną

Algorytm zniekształcenia szybkości

$symbolu$$,$ źródło z prawdopodobieństwem danego Chcemy znaleźć kodowanie , które generuje skompresowany sygnał $\ kapelusz {x}} | x)$ oryginału ${\ Displaystyle p ({$$\ Displaystyle \ langle d (x, {\ kapelusz {x}}) \ rangle}$ re { , gdzie oczekiwanie przejmuje wspólne prawdopodobieństwo ${\ displaystyle X}$ i ${\ Displaystyle {\ kapelusz {X}}}$ . Możemy znaleźć kodowanie, które lokalnie minimalizuje funkcjonał zniekształcenia szybkości, powtarzając następującą iterację aż do zbieżności:

${\ Displaystyle p_ {t + 1} ({\ kapelusz {x}}) = \ suma _ {x} p ( x) p_ {t} ({\ kapelusz {x}}|x)}$

${\ Displaystyle p_ {t + 1} ({\ kapelusz {x}} | x) = {\ Frac {p_ {t} ( {\kapelusz {x}}}\exp(-\beta d(x,{\kapelusz {x}}))}{\sum _{\kapelusz {x}}p_{t}({\kapelusz {x} })\exp(-\beta d(x,{\kapelusz {x}}))}}}$

gdzie jest parametrem związanym z nachyleniem $krzywej$ współczynnika zniekształceń, na który celujemy, a zatem jest związany z tym, jak bardzo preferujemy kompresję w porównaniu z zniekształceniami (wyższy mniejszą kompresję) ${\ displaystyle \ beta }$ .