„Celem tego kursu jest przygotowanie Cię na przyszłość techniczną.”
Witaj, Habr. Pamiętajcie o niesamowitym artykule „Ty i Twoja praca” (+219, 2588 zakładek, 429 tys. odczytów)?
Zatem Hamming (tak, tak, samokontrola i samokorygowanie Kody Hamminga) jest całość книга, napisany na podstawie jego wykładów. Tłumaczymy to, bo człowiek mówi, co myśli.
To książka nie tylko o IT, to książka o stylu myślenia niesamowicie fajnych ludzi. „To nie tylko zastrzyk pozytywnego myślenia; opisuje warunki, które zwiększają szanse na wykonanie wspaniałej pracy”.
Dziękuję Andreyowi Pakhomovowi za tłumaczenie.
Teorię informacji opracował C. E. Shannon pod koniec lat czterdziestych XX wieku. Kierownictwo Bell Labs nalegało, aby nazwał tę teorię „teorią komunikacji”, ponieważ… to jest o wiele bardziej trafna nazwa. Z oczywistych względów nazwa „Teoria Informacji” wywiera znacznie większy wpływ na opinię publiczną, dlatego Shannon ją wybrała i jest to nazwa, którą znamy do dziś. Sama nazwa sugeruje, że teoria ta zajmuje się informacją, co czyni ją ważną, gdy wchodzimy głębiej w erę informacji. W tym rozdziale poruszę kilka głównych wniosków z tej teorii, przedstawię nie ścisłe, ale raczej intuicyjne dowody na niektóre poszczególne zapisy tej teorii, abyś zrozumiał, czym właściwie jest „Teoria Informacji”, gdzie można ją zastosować a gdzie nie.
Po pierwsze, czym jest „informacja”? Shannon utożsamia informację z niepewnością. Wybrał logarytm ujemny prawdopodobieństwa zdarzenia jako ilościową miarę informacji, które otrzymujesz, gdy zajdzie zdarzenie z prawdopodobieństwem p. Na przykład, jeśli powiem Ci, że pogoda w Los Angeles jest mglista, to p będzie bliskie 1, co tak naprawdę nie daje nam zbyt wielu informacji. Ale jeśli powiem, że w czerwcu w Monterey będzie padać, przekaz będzie niepewny i będzie zawierał więcej informacji. Wiarygodne zdarzenie nie zawiera żadnych informacji, ponieważ log 1 = 0.
Przyjrzyjmy się temu bardziej szczegółowo. Shannon uważał, że ilościowa miara informacji powinna być ciągłą funkcją prawdopodobieństwa zdarzenia p, a dla zdarzeń niezależnych powinna być addytywna – ilość informacji uzyskana w wyniku zajścia dwóch niezależnych zdarzeń powinna być równa ilość informacji uzyskanych w wyniku wystąpienia wspólnego zdarzenia. Na przykład wynik rzutu kostką i monetą zwykle traktuje się jako niezależne zdarzenia. Przełóżmy powyższe na język matematyki. Jeżeli I (p) jest ilością informacji zawartą w zdarzeniu z prawdopodobieństwem p, to dla łącznego zdarzenia składającego się z dwóch niezależnych zdarzeń x z prawdopodobieństwem p1 i y z prawdopodobieństwem p2 otrzymujemy
(x i y są zdarzeniami niezależnymi)
Jest to funkcjonalne równanie Cauchy’ego, prawdziwe dla wszystkich p1 i p2. Aby rozwiązać to równanie funkcjonalne, załóżmy, że
p1 = p2 = p,
to daje
Jeśli p1 = p2 i p2 = p to
itp. Rozszerzając ten proces za pomocą standardowej metody na wykładnicze, dla wszystkich liczb wymiernych m/n prawdą jest, co następuje
Z przyjętej ciągłości miary informacyjnej wynika, że jedynym ciągłym rozwiązaniem równania funkcyjnego Cauchy’ego jest funkcja logarytmiczna.
W teorii informacji często przyjmuje się, że podstawa logarytmu wynosi 2, więc wybór binarny zawiera dokładnie 1 bit informacji. Dlatego informacje mierzy się za pomocą wzoru
Zatrzymajmy się i zrozummy, co wydarzyło się powyżej. Przede wszystkim nie zdefiniowaliśmy pojęcia „informacji”, zdefiniowaliśmy po prostu wzór na jej miarę ilościową.
Po drugie, środek ten jest obarczony niepewnością i chociaż jest w miarę odpowiedni dla maszyn – na przykład systemów telefonicznych, radia, telewizji, komputerów itp. – nie odzwierciedla normalnego ludzkiego podejścia do informacji.
Po trzecie, jest to miara względna, zależy od aktualnego stanu Twojej wiedzy. Jeśli spojrzysz na strumień „liczb losowych” z generatora liczb losowych, zakładasz, że każda kolejna liczba jest niepewna, ale jeśli znasz wzór na obliczenie „liczb losowych”, następna liczba będzie znana, a zatem nie będzie zawierać informacje.
Zatem definicja informacji Shannona w wielu przypadkach jest odpowiednia dla maszyn, ale wydaje się, że nie pasuje do ludzkiego rozumienia tego słowa. Z tego powodu „teorię informacji” należało nazwać „teorią komunikacji”. Jednakże jest już za późno na zmianę definicji (co dało tej teorii początkową popularność i które nadal utwierdzają ludzi w przekonaniu, że teoria ta dotyczy „informacji”), więc musimy z nimi żyć, ale jednocześnie trzeba jasno zrozumieć, jak daleko definicja informacji Shannona odbiega od jej powszechnie używanego znaczenia. Informacje Shannon dotyczą czegoś zupełnie innego, a mianowicie niepewności.
Oto coś, o czym warto pomyśleć, proponując jakąkolwiek terminologię. W jaki sposób proponowana definicja, taka jak definicja informacji Shannona, zgadza się z Twoim pierwotnym pomysłem i jak bardzo się od niej różni? Prawie nie ma terminu, który dokładnie odzwierciedlałby twoją poprzednią wizję koncepcji, ale ostatecznie to zastosowana terminologia odzwierciedla znaczenie koncepcji, więc sformalizowanie czegoś poprzez jasne definicje zawsze wprowadza pewne zamieszanie.
Rozważmy system, którego alfabet składa się z symboli q z prawdopodobieństwem pi. W tym przypadku średnia ilość informacji w systemie (jego wartość oczekiwana) jest równa:
Nazywa się to entropią układu o rozkładzie prawdopodobieństwa {pi}. Używamy terminu „entropia”, ponieważ ta sama forma matematyczna pojawia się w termodynamice i mechanice statystycznej. Dlatego też termin „entropia” tworzy wokół siebie pewną aurę ważności, która ostatecznie nie jest uzasadniona. Ta sama matematyczna forma zapisu nie implikuje tej samej interpretacji symboli!
Entropia rozkładu prawdopodobieństwa odgrywa główną rolę w teorii kodowania. Nierówność Gibbsa dla dwóch różnych rozkładów prawdopodobieństwa pi i qi jest jedną z ważnych konsekwencji tej teorii. Musimy to więc udowodnić
Dowód opiera się na oczywistym wykresie, rys. 13.I, który to pokazuje
a równość osiągamy tylko wtedy, gdy x = 1. Zastosujmy nierówność do każdego wyrazu sumy od lewej strony:
Jeżeli alfabet systemu komunikacyjnego składa się z q symboli, to biorąc prawdopodobieństwo transmisji każdego symbolu qi = 1/q i podstawiając q, otrzymujemy z nierówności Gibbsa
Rysunek 13.I
Oznacza to, że jeśli prawdopodobieństwo przesłania wszystkich symboli q jest takie samo i równe - 1 / q, to maksymalna entropia jest równa ln q, w przeciwnym razie nierówność zachodzi.
W przypadku kodu jednoznacznie dekodowalnego mamy nierówność Krafta
Jeśli teraz zdefiniujemy pseudoprawdopodobieństwa
gdzie oczywiście = 1, co wynika z nierówności Gibbsa,
i zastosujmy małą algebrę (pamiętajcie, że K ≤ 1, więc możemy porzucić wyraz logarytmiczny i być może później wzmocnić nierówność), otrzymamy
gdzie L jest średnią długością kodu.
Zatem entropia jest minimalną granicą dla dowolnego kodu znak po symbolu o średniej długości słowa kodowego L. Jest to twierdzenie Shannona dla kanału wolnego od zakłóceń.
Rozważmy teraz główne twierdzenie o ograniczeniach systemów komunikacyjnych, w których informacja jest przesyłana w postaci strumienia niezależnych bitów i występuje szum. Przyjmuje się, że prawdopodobieństwo poprawnej transmisji jednego bitu wynosi P > 1/2, a prawdopodobieństwo, że podczas transmisji wartość bitu zostanie odwrócona (wystąpi błąd) jest równe Q = 1 - P. Dla wygody założyć, że błędy są niezależne i prawdopodobieństwo wystąpienia błędu jest takie samo dla każdego wysłanego bitu – czyli w kanale komunikacyjnym występuje „biały szum”.
Sposób, w jaki mamy długi strumień n bitów zakodowany w jedną wiadomość, polega na n - wymiarowym rozszerzeniu kodu jednobitowego. Wartość n określimy później. Rozważmy wiadomość składającą się z n-bitów jako punkt w przestrzeni n-wymiarowej. Ponieważ mamy przestrzeń n-wymiarową - i dla uproszczenia założymy, że każda wiadomość ma to samo prawdopodobieństwo wystąpienia - możliwych jest M wiadomości (M również zostanie określone później), zatem prawdopodobieństwo wysłania dowolnej wiadomości wynosi
(nadawca) Załącznik 13.II
Następnie rozważ ideę pojemności kanału. Bez wchodzenia w szczegóły, przepustowość kanału definiuje się jako maksymalną ilość informacji, która może zostać niezawodnie przesłana kanałem komunikacyjnym, przy uwzględnieniu zastosowania najbardziej wydajnego kodowania. Nie ma argumentu, że kanałem komunikacyjnym można przesłać więcej informacji niż jego pojemność. Można to udowodnić dla binarnego kanału symetrycznego (którego używamy w naszym przypadku). Pojemność kanału podczas wysyłania bitów jest określana jako
gdzie, jak poprzednio, P jest prawdopodobieństwem braku błędu w żadnym wysłanym bicie. Przy wysyłaniu n niezależnych bitów pojemność kanału jest określona wzorem
Jeżeli zbliżamy się do pojemności kanału, to musimy przesłać prawie taką ilość informacji dla każdego z symboli ai, i = 1, ..., M. Biorąc pod uwagę, że prawdopodobieństwo wystąpienia każdego symbolu ai wynosi 1/M, dostajemy
kiedy wysyłamy którykolwiek z M równie prawdopodobnych komunikatów ai, mamy
Kiedy zostanie wysłanych n bitów, spodziewamy się wystąpienia błędów nQ. W praktyce dla wiadomości składającej się z n-bitów w odebranej wiadomości będziemy mieli w przybliżeniu nQ błędów. Dla dużego n zmienność względna (odchylenie = szerokość rozkładu, )
rozkład liczby błędów będzie coraz węższy w miarę wzrostu n.
Zatem od strony nadajnika biorę wiadomość ai do wysłania i rysuję wokół niej kulę o promieniu
która jest nieco większa o kwotę e2 od oczekiwanej liczby błędów Q, (rysunek 13.II). Jeśli n jest wystarczająco duże, wówczas istnieje dowolnie małe prawdopodobieństwo, że punkt komunikatu bj pojawi się po stronie odbiorcy, który będzie wykraczał poza tę kulę. Narysujmy sytuację tak, jak ja ją widzę z punktu widzenia nadawcy: mamy dowolne promienie od przesłanego komunikatu ai do odebranego komunikatu bj z prawdopodobieństwem błędu równym (lub prawie równym) rozkładowi normalnemu, osiągającemu maksimum z nQ. Dla dowolnego e2 istnieje n tak duże, że prawdopodobieństwo, że powstały punkt bj znajdzie się poza moją sferą, jest tak małe, jak chcesz.
Teraz spójrzmy na tę samą sytuację z Twojej strony (ryc. 13.III). Po stronie odbiorcy znajduje się kula S(r) o tym samym promieniu r wokół odbieranego punktu bj w przestrzeni n-wymiarowej, tak że jeśli odebrana wiadomość bj znajduje się wewnątrz mojej sfery, to wiadomość ai wysłana przeze mnie znajduje się w twojej kula.
Jak może wystąpić błąd? Błąd może wystąpić w przypadkach opisanych w poniższej tabeli:
Rysunek 13.III
Widzimy tutaj, że jeśli w sferze zbudowanej wokół odebranego punktu znajduje się jeszcze co najmniej jeden punkt odpowiadający możliwej wysłanej wiadomości niekodowanej, to podczas transmisji wystąpił błąd, ponieważ nie można określić, która z tych wiadomości została przesłana. Wysłany komunikat jest wolny od błędów tylko wtedy, gdy odpowiadający mu punkt znajduje się w kuli, a w danym kodzie nie ma możliwości, aby inne punkty znajdowały się w tej samej sferze.
Mamy matematyczne równanie prawdopodobieństwa wystąpienia błędu Pe w przypadku wysłania wiadomości ai
Możemy odrzucić pierwszy czynnik w drugim wyrazie, przyjmując go jako 1. W ten sposób otrzymujemy nierówność
Oczywiście,
stąd
zastosuj ponownie do ostatniego wyrazu po prawej stronie
Biorąc pod uwagę wystarczająco duże n, pierwszy wyraz można przyjąć tak mały, jak to pożądane, powiedzmy mniejszy niż pewna liczba d. Dlatego mamy
Przyjrzyjmy się teraz, jak możemy skonstruować prosty kod podstawieniowy, aby zakodować M wiadomości składających się z n bitów. Nie mając pojęcia, jak dokładnie skonstruować kod (nie wynaleziono jeszcze kodów korygujących błędy), Shannon wybrała kodowanie losowe. Rzuć monetą dla każdego z n bitów wiadomości i powtórz proces dla M wiadomości. W sumie trzeba wykonać nM rzutów monetą, więc jest to możliwe
słowniki kodu mające to samo prawdopodobieństwo ½nM. Oczywiście losowy proces tworzenia słownika oznacza, że istnieje możliwość duplikatów, a także punktów kodowych, które będą blisko siebie i przez to będą źródłem prawdopodobnych błędów. Należy udowodnić, że jeśli nie zachodzi to z prawdopodobieństwem większym niż dowolny wybrany mały poziom błędu, to dane n jest wystarczająco duże.
Kluczową kwestią jest to, że Shannon uśrednił wszystkie możliwe słowniki, aby znaleźć średni błąd! Będziemy używać symbolu Av[.] do oznaczenia średniej wartości ze zbioru wszystkich możliwych losowych książek kodowych. Uśrednianie po stałej d oczywiście daje stałą, ponieważ w przypadku uśredniania każdy wyraz jest taki sam jak każdy inny wyraz sumy,
które można zwiększyć (M–1 przechodzi do M)
Dla dowolnej wiadomości, podczas uśredniania wszystkich książek kodowych, kodowanie przebiega przez wszystkie możliwe wartości, więc średnie prawdopodobieństwo, że punkt znajduje się w kuli, jest stosunkiem objętości kuli do całkowitej objętości przestrzeni. Objętość kuli wynosi
gdzie s=Q+e2 <1/2 i ns musi być liczbą całkowitą.
Ostatni wyraz po prawej stronie jest największy w tej sumie. Najpierw oszacujmy jego wartość, korzystając ze wzoru Stirlinga na silnię. Następnie przyjrzymy się malejącemu współczynnikowi wyrazu przed nim, zauważmy, że współczynnik ten rośnie w miarę przesuwania się w lewo, więc możemy: (1) ograniczyć wartość sumy do sumy postępu geometrycznego za pomocą ten początkowy współczynnik, (2) rozszerzyć postęp geometryczny z ns wyrazów na nieskończoną liczbę wyrazów, (3) obliczyć sumę nieskończonego postępu geometrycznego (algebra standardowa, nic istotnego) i w końcu uzyskać wartość graniczną (dla wystarczająco dużego N):
Zwróć uwagę, jak entropia H(s) pojawiła się w tożsamości dwumianowej. Należy zauważyć, że rozwinięcie w szereg Taylora H(s)=H(Q+e2) daje oszacowanie otrzymane przy uwzględnieniu tylko pierwszej pochodnej i pominięciu wszystkich pozostałych. Teraz ułóżmy ostatnie wyrażenie:
gdzie
Wszystko, co musimy zrobić, to wybrać e2 takie, że e3 < e1, a wtedy ostatni wyraz będzie dowolnie mały, o ile n jest wystarczająco duże. W rezultacie średni błąd PE można uzyskać tak mały, jak jest to pożądane, przy przepustowości kanału dowolnie bliskiej C.
Jeśli średnia wszystkich kodów ma wystarczająco mały błąd, to przynajmniej jeden kod musi być odpowiedni, a zatem istnieje co najmniej jeden odpowiedni system kodowania. Jest to ważny wynik uzyskany przez Shannona - „Twierdzenie Shannona dla kanału zaszumionego”, choć należy zauważyć, że udowodnił to dla znacznie bardziej ogólnego przypadku niż dla prostego binarnego kanału symetrycznego, którego użyłem. W ogólnym przypadku obliczenia matematyczne są znacznie bardziej skomplikowane, ale pomysły nie są tak różne, dlatego bardzo często na przykładzie konkretnego przypadku można odkryć prawdziwe znaczenie twierdzenia.
Krytykujmy wynik. Wielokrotnie powtarzaliśmy: „Dla wystarczająco dużego n.” Ale jak duże jest n? Bardzo, bardzo duży jeśli naprawdę chcesz być jednocześnie blisko pojemności kanału i mieć pewność poprawnego przesyłu danych! W rzeczywistości tak duży, że będziesz musiał bardzo długo czekać, aby zgromadzić wiadomość zawierającą wystarczającą liczbę bitów, aby ją później zakodować. W tym przypadku rozmiar słownika kodów losowych będzie po prostu ogromny (w końcu takiego słownika nie da się przedstawić w formie krótszej niż pełna lista wszystkich bitów Mn, mimo że n i M są bardzo duże)!
Kody korygujące błędy pozwalają uniknąć czekania na bardzo długą wiadomość, a następnie kodowania i dekodowania jej za pomocą bardzo dużych słowników, ponieważ same unikają książek kodowych i zamiast tego używają zwykłych obliczeń. W prostej teorii takie kody zwykle tracą zdolność zbliżania się do przepustowości kanału i nadal utrzymują niski poziom błędów, ale gdy kod koryguje dużą liczbę błędów, działają dobrze. Innymi słowy, jeśli przeznaczysz część przepustowości kanału na korekcję błędów, to będziesz musiał przez większość czasu korzystać z możliwości korekcji błędów, co oznacza, że w każdej wysłanej wiadomości musi być poprawiana duża liczba błędów, w przeciwnym razie zmarnujesz tę pojemność.
Jednocześnie udowodnione powyżej twierdzenie nadal nie jest bez znaczenia! Pokazuje, że wydajne systemy transmisji muszą wykorzystywać sprytne schematy kodowania dla bardzo długich ciągów bitów. Przykładem są satelity, które przeleciały poza planetami zewnętrznymi; W miarę oddalania się od Ziemi i Słońca zmuszone są poprawiać coraz więcej błędów w bloku danych: niektóre satelity korzystają z paneli słonecznych, które dostarczają około 5 W, inne korzystają ze źródeł energii jądrowej, które zapewniają mniej więcej tę samą moc. Mała moc zasilacza, małe rozmiary czasz nadawczych i ograniczone rozmiary czasz odbiorczych na Ziemi, ogromna odległość, jaką musi pokonać sygnał – wszystko to wymaga zastosowania kodów o wysokim poziomie korekcji błędów do zbudowania efektywny system komunikacji.
Wróćmy do przestrzeni n-wymiarowej, którą wykorzystaliśmy w powyższym dowodzie. Omawiając to pokazaliśmy, że niemal cała objętość kuli skupiona jest w pobliżu powierzchni zewnętrznej – zatem niemal pewne jest, że wysyłany sygnał będzie zlokalizowany w pobliżu powierzchni kuli zbudowanej wokół odbieranego sygnału, nawet przy stosunkowo mały promień takiej kuli. Nic więc dziwnego, że odebrany sygnał po skorygowaniu dowolnie dużej liczby błędów nQ okazuje się dowolnie zbliżony do sygnału pozbawionego błędów. Kluczem do zrozumienia tego zjawiska jest przepustowość łącza, o której mówiliśmy wcześniej. Należy zauważyć, że podobne kule skonstruowane w celu korekcji błędów kodów Hamminga nie nakładają się na siebie. Duża liczba prawie ortogonalnych wymiarów w przestrzeni n-wymiarowej pokazuje, dlaczego możemy zmieścić M sfer w przestrzeni z niewielkim nakładaniem się. Jeśli pozwolimy na małe, dowolnie małe nakładanie się, które może prowadzić do niewielkiej liczby błędów podczas dekodowania, możemy uzyskać gęste rozmieszczenie kul w przestrzeni. Hamming gwarantował pewien poziom korekcji błędów, Shannon - niskie prawdopodobieństwo błędu, ale jednocześnie utrzymywał rzeczywistą przepustowość dowolnie blisko przepustowości kanału komunikacyjnego, czego kody Hamminga nie są w stanie zrobić.
Teoria informacji nie mówi nam, jak zaprojektować wydajny system, ale wskazuje drogę do wydajnych systemów komunikacji. Jest to cenne narzędzie do budowania systemów komunikacji maszyna-maszyna, ale, jak zauważono wcześniej, ma niewielkie znaczenie dla sposobu, w jaki ludzie komunikują się między sobą. Nie wiadomo, w jakim stopniu dziedziczenie biologiczne przypomina systemy komunikacji technicznej, dlatego obecnie nie jest jasne, w jaki sposób teoria informacji ma zastosowanie do genów. Nie mamy innego wyjścia, jak tylko spróbować, a jeśli sukces pokaże nam maszynową naturę tego zjawiska, to porażka wskaże inne istotne aspekty natury informacji.
Nie dygresujmy za bardzo. Widzieliśmy, że wszystkie oryginalne definicje, w większym lub mniejszym stopniu, muszą wyrażać istotę naszych pierwotnych przekonań, ale charakteryzują się pewnym stopniem zniekształcenia i dlatego nie mają zastosowania. Tradycyjnie przyjmuje się, że ostatecznie definicja, której używamy, faktycznie definiuje istotę; ale to tylko mówi nam, jak przetwarzać rzeczy i w żaden sposób nie przekazuje nam żadnego znaczenia. Podejście postulacyjne, tak bardzo preferowane w kręgach matematycznych, w praktyce pozostawia wiele do życzenia.
Teraz przyjrzymy się przykładowi testów IQ, których definicja jest tak okrągła, jak sobie tego życzysz, i w rezultacie wprowadza w błąd. Powstaje test, który ma mierzyć inteligencję. Następnie jest on korygowany tak, aby był jak najbardziej spójny, a następnie publikowany i prostą metodą kalibrowany tak, aby zmierzona „inteligencja” okazała się mieć rozkład normalny (oczywiście na krzywej kalibracyjnej). Wszystkie definicje należy ponownie sprawdzić nie tylko przy ich pierwszym zaproponowaniu, ale także znacznie później, gdy zostaną użyte w wyciąganych wnioskach. W jakim stopniu granice definicyjne są odpowiednie dla rozwiązywanego problemu? Jak często definicje podane w jednym kontekście mają zastosowanie w zupełnie innych okolicznościach? To zdarza się dość często! W naukach humanistycznych, z którymi nieuchronnie spotkasz się w swoim życiu, zdarza się to częściej.
Zatem jednym z celów tej prezentacji teorii informacji, oprócz wykazania jej użyteczności, było ostrzeżenie o tym niebezpieczeństwie, czyli pokazanie dokładnie, jak z niej korzystać, aby uzyskać pożądany rezultat. Już dawno zauważono, że wstępne definicje determinują to, co ostatecznie znajdziemy, w znacznie większym stopniu, niż się wydaje. Wstępne definicje wymagają od Ciebie dużej uwagi, nie tylko w każdej nowej sytuacji, ale także w obszarach, z którymi pracujesz od dłuższego czasu. Pozwoli to zrozumieć, w jakim stopniu uzyskane wyniki są tautologią, a nie czymś użytecznym.
Słynna historia Eddingtona opowiada o ludziach, którzy łowili ryby w morzu za pomocą sieci. Po zbadaniu wielkości złowionych ryb określili minimalny rozmiar ryby występującej w morzu! Do ich wniosków zadecydował zastosowany instrument, a nie rzeczywistość.
To be continued ...
Kto chce pomóc w tłumaczeniu, szacie graficznej i wydaniu książki - pisz w wiadomości prywatnej lub na maila [email chroniony]