Entropia - teoria informacji - Polski Serwis Naukowy

Ten artykuł dotyczy pojęcia z dziedziny teorii informacji. Zapoznaj się również z: inne znaczenia tego terminu.

Entropia – w ramach teorii informacji jest definiowana jako średnia ilość informacji, przypadająca na znak symbolizujący zajście zdarzenia z pewnego zbioru. Zdarzenia w tym zbiorze mają przypisane prawdopodobieństwa wystąpienia.

Proces Markowa – ciąg zdarzeń, w którym prawdopodobieństwo każdego zdarzenia zależy jedynie od wyniku poprzedniego. W ujęciu matematycznym, procesy Markowa to takie procesy stochastyczne, które spełniają własność Markowa.

Ban (czasem także hartley - oznaczenie Hart, określany też jako dit od decimal digit ) – jednostka informacji lub entropii. Konstrukcja tej miary informacji oparta jest o logarytm o podstawie 10 (logarytm dziesiętny). Jednostkę miary informacji opartą o logarytm o podstawie 2 nazywamy bitem. Podobnie jak bit odpowiada cyfrze dwójkowej, ban odpowiada cyfrze dziesiętnej. Decyban jest jedną dziesiątą bana.

Wzór na entropię: $H(x)=\sum_{i=1}^np(i)\log_r \frac{1}{p(i)}= - \sum_{i=1}^np(i)\log_r {p(i)}\,\!$

gdzie p(i) – prawdopodobieństwo zajścia zdarzenia i, a n – liczba wszystkich zdarzeń danej przestrzeni. W przypadku kodowania ciągu znaków jest to prawdopodobieństwo wystąpienia i-tego znaku. W teorii informacji najczęściej stosuje się logarytm o podstawie r=2, wówczas jednostką entropii jest bit. Dla r= e jednostka ta nazywa się nat (nit), natomiast dla r=10 – dit lub hartley.

Entropia – termodynamiczna funkcja stanu, określająca kierunek przebiegu procesów spontanicznych (samorzutnych) w odosobnionym układzie termodynamicznym. Entropia jest miarą stopnia nieuporządkowania układu. Jest wielkością ekstensywną. Zgodnie z drugą zasadą termodynamiki, jeżeli układ termodynamiczny przechodzi od jednego stanu równowagi do drugiego, bez udziału czynników zewnętrznych (a więc spontanicznie), to jego entropia zawsze rośnie. Pojęcie entropii wprowadził niemiecki uczony Rudolf Clausius.

Alfréd Rényi (20 marca 1921 w Budapeszcie – 1 lutego 1970 tamże) – węgierski matematyk, który znacząco przyczynił się do rozwoju kombinatoryki, teorii grafów, teorii liczb i szczególnie probablilistyki. Ze względu na żydowskie pochodzenie przebywał w obozie pracy w 1944.

W latach 60-tych węgierski matematyk Alfred Rényi uogólnił pojęcie entropii do zbioru funkcji za pomocą których można opisać ilościowo różnorodność, niepewność czy losowość systemu. Miara ta od jego nazwiska nazywana jest entropią Rényi.

Entropię można interpretować jako niepewność wystąpienia danego zdarzenia elementarnego w następnej chwili. Jeżeli zdarzenie występuje z prawdopodobieństwem równym 1, to jego entropia wynosi 0, gdyż z góry wiadomo, co się stanie – nie ma niepewności.

Własności entropii:

Ilość informacji – wielkość ujmująca (przedstawiająca) ilościowo właściwość zmniejszania (usuwania) nieokreśloności (niepewności), czyli informację, termin używany w matematycznej teorii informacji.

Histogram to jeden z graficznych sposobów przedstawiania rozkładu empirycznego cechy. Składa się z szeregu prostokątów umieszczonych na osi współrzędnych. Prostokąty te są z jednej strony wyznaczone przez przedziały klasowe (patrz: Szereg rozdzielczy) wartości cechy, natomiast ich wysokość jest określona przez liczebności (lub częstości, ewentualnie gęstość prawdopodobieństwa) elementów wpadających do określonego przedziału klasowego.

jest nieujemna

jest maksymalna, gdy prawdopodobieństwa zajść zdarzeń są takie same

jest równa 0, gdy stany systemu przyjmują wartości tylko 0 albo tylko 1

własność superpozycji – gdy dwa systemy są niezależne, to entropia sumy systemów równa się sumie entropii.

jeśli ze źródła danych pobierane są k-literowe ciągi, wówczas entropia wynosi $H(x^{(k)}) = kH(x)$

Definicja informacyjna była pierwotnie próbą ujęcia tradycyjnego pojęcia entropii znanego z termodynamiki w kategoriach teorii informacji. Okazała się jednak, że definicja ta jest przydatna w ramach samej teorii informacji.

Termodynamika - nauka o energii, dział fizyki zajmujący się badaniem energetycznych efektów wszelkich przemian fizycznych i chemicznych, które wpływają na zmiany energii wewnętrznej analizowanych układów. Wbrew rozpowszechnionym sądom termodynamika nie zajmuje się wyłącznie przemianami cieplnymi, lecz także efektami energetycznymi reakcji chemicznych, przemian z udziałem jonów, przemianami fazowymi, a nawet przemianami jądrowymi i energią elektryczną.

Logarytm (łac. [now.] logarithmus, w sensie stosunek, z gr. λόγ- log-, od λόγος logos , „słowo”, w sensie proporcja, i ἀριθμός árithmós, „liczba”). Logarytm przy podstawie a z liczby b (symbolicznie log ab) oznacza liczbę c, będącą potęgą, do której podstawa a musi być podniesiona, aby dać liczbę b, czyli

Pojęcie entropii jest bardzo przydatne w np. dziedzinie kompresji danych. Entropię zerowego rzędu można obliczyć znając histogram ciągu symboli. Jest to iloczyn entropii i liczby znaków w ciągu. Osiągi kodowania Huffmana są często zbliżone do tej granicy, jednak lepszą efektywnością charakteryzuje się kodowanie arytmetyczne.

Bit (w ang. kawałek, skrót od binary digit, czyli cyfra dwójkowa) – najmniejsza ilość informacji potrzebna do określenia, który z dwóch równie prawdopodobnych stanów przyjął układ. Jednostka logiczna.

Teoria informacji – dział matematyki na pograniczu statystyki i informatyki, mający również olbrzymie znaczenie w współczesnej telekomunikacji, dotyczący przetwarzania informacji oraz jej transmisji, kompresji, kryptografii itd.

Przyjęcie modelu, w którym uwzględnia się kontekst znaku, pozwala zwykle na bardzo duże obniżenie entropii.

Przykład

W przypadku, gdy prawdopodobieństwa poszczególnych zdarzeń w zbiorze są równe, powyższy wzór można stosować w postaci uproszczonej: $H(x)=\log_2(n)$

gdzie n oznacza wielkość zbioru. Przykładowo dla zbioru 26 liter alfabetu (n=26) entropia każdej z nich wynosi około 4,7, więc ośmioznakowy ciąg liter wykorzystywany np. jako hasło będzie miał entropię 37,6.

Entropia metryczna – entropia (teoria informacji) znormalizowana przez długość wiadomości. Pozwala zmierzyć losowość informacji, ponieważ entropia Shannona wzrasta liniowo ze wzrostem długości wiadomości. Normalizacja przez długość wiadomości daje tą samą informację, ale jest niezależna od długości wiadomości.

Moneta, która wyrzuca z takim samym prawdopodobieństwem orły i reszki, ma 1 bit entropii na rzut: $- p_{O} \log_2 p_{O} - p_{R} \log_2 p_{R} = - \frac 1 2 \log_2 \frac 1 2 - \frac 1 2 \log_2 \frac 1 2 = \frac 1 2 + \frac 1 2 = 1$

Jednakże, jeśli jeśli moneta z jakieś przyczyny daje zafałszowany wynik (statystycznie częściej daje albo orła albo reszkę z określonym prawdopodobieństwem) mamy do czynienia z sytuacja w której jest mniejsza niepewność (możemy łatwiej przewidzieć wynik). Objawia się to niższą entropią. Przykładowo, jeśli założymy, że z czterech rzutów wypadły 3 reszki to podstawiając do wzoru otrzymamy entropię równą 0.81. Idąc do ekstremum, przy czterech rzutach i 4 reszkach lub 4 orłach entropia osiąga minimum czyli 0, ponieważ nie ma niepewności (wiemy co wydarzy się w następnym rzucie). Oczywiście przedstawiony przykład jest skrajnie uproszczony i próba czterech rzutów jest za mała, aby wyciągać jakieś statystyczne wnioski, ale dobrze obrazuje problem.

Ogólniej każde źródło dające $N$ równie prawdopodobnych wyników ma $log_2 N$ bitów na symbol entropii: $- \sum_{i=1}^N \frac 1 N \log_2 \frac 1 N = - N \frac 1 N \log_2 \frac 1 N = -\log_2 \frac 1 N = \log_2 N$

Ponadto inną miarą związaną z entropią Shannona jest entropia metryczna, która uwzględnia długość informacji (entropia dzielona jest przez długość wiadomości) i pozwala zmierzyć losowość informacji.

Zobacz też

Zobacz hasło entropia w Wikisłowniku

łańcuch Markowa

Linki zewnętrzne

kalkulator entropii - jak obliczyć i interpretować entropię dowolnej wiadomości