Tiedon entropia

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 17.1.2020 tarkistetusta versiosta . tarkastukset vaativat 35 muokkausta .

Tiedon entropia on tietyn järjestelmän epävarmuuden mitta ( tilastofysiikassa tai informaatioteoriassa ), erityisesti ensisijaisen aakkoston minkä tahansa merkin esiintymisen arvaamattomuudesta . Jälkimmäisessä tapauksessa informaatiohäviön puuttuessa entropia on numeerisesti yhtä suuri kuin informaation määrä lähetetyn viestin symbolia kohti.

Esimerkiksi venäjänkielisen lauseen muodostavassa kirjainsarjassa eri kirjaimet esiintyvät eri taajuuksilla , joten joidenkin kirjainten esiintymisen epävarmuus on pienempi kuin toisten. Jos otamme huomioon, että jotkut kirjainyhdistelmät (tässä tapauksessa ne puhuvat -: nnen kertaluvun entropiasta, katso alla ) ovat erittäin harvinaisia, niin epävarmuus pienenee entisestään. $n$

Muodolliset määritelmät

Tiedon binäärinen entropia lasketaan Hartley-kaavalla , jos informaatiota ei menetetä :

$i=\log _{2}N$ ,

missä on aakkosten teho, on viestin kunkin symbolin tiedon määrä. Satunnaismuuttujalle , joka ottaa riippumattomia satunnaisarvoja todennäköisyyksien kanssa ( ), Hartleyn kaava muuttuu Shannonin kaavaksi: $N$ $i$ $x$ $n$ $x_{i}$ $p_{i}$ $i=1,...,n$

$H(x)=-\sum _{i=1}^{n}p_{i}\log _{2}p_{i}.$

Tätä määrää kutsutaan myös keskimääräiseksi viestientropiaksi . Suureksi kutsutaan osittaista entropiaa , joka luonnehtii vain -e-tilaa. $H_{i}=-\log _{2}{p_{i))$ $i$

Siten järjestelmän entropia on tilan (tapahtuman) kaikkien suhteellisten esiintymistiheysten vastakkaisen etumerkin omaava summa luvulla , kerrottuna niiden binäärilogaritmeilla [1] . Tämä diskreettien satunnaistapahtumien määritelmä voidaan muodollisesti laajentaa todennäköisyystiheysjakauman antamiin jatkuviin jakaumiin , mutta tuloksena olevalla funktionaalisella funktiolla on kuitenkin hieman erilaiset ominaisuudet (katso differentiaalinen entropia ). $x$ $i$

Yleensä logaritmin kanta entropian määritelmässä voi olla mikä tahansa suurempi kuin 1 (koska vain yhdestä merkistä koostuva aakkoset eivät voi välittää tietoa); logaritmin kantakohdan valinta määrää entropian yksikön. Binäärilukujärjestelmään perustuvissa tietojärjestelmissä tiedon entropian (itse asiassa informaation) mittayksikkö on hieman . Matemaattisten tilastojen ongelmissa voi olla kätevämpää käyttää luonnollista logaritmia , jolloin tiedon entropian yksikkö on nat .

Shannonin määritelmä

Claude Shannon ehdotti, että tiedon voitto on yhtä suuri kuin menetetty epävarmuus, ja asetti vaatimukset sen mittaamiselle:

toimenpiteen on oltava jatkuva; eli todennäköisyysarvon arvon muutoksen pienellä määrällä pitäisi aiheuttaa pieni nettomuutos funktiossa;
siinä tapauksessa, että kaikki vaihtoehdot (kirjaimet yllä olevassa esimerkissä) ovat yhtä todennäköisiä, vaihtoehtojen (kirjainten) lukumäärän lisäämisen tulisi aina lisätä funktion arvoa;
pitäisi olla mahdollista tehdä valinta (esimerkissämme kirjaimet) kahdessa vaiheessa, jossa lopputuloksen funktion arvon tulee olla välitulosten funktioiden summa.[ tyhjentää ]

Siksi entropiafunktion on täytettävä ehdot $H$

$H(p_{1},\;\ldots ,\;p_{n})$ on määritelty ja jatkuva kaikille , missä kaikille ja . (Tämä funktio riippuu vain todennäköisyysjakaumasta, ei aakkosesta.) ${\displaystyle p_{1},\dotsc ,p_{n))$ $p_{i}\in [0,\;1]$ $i=1,\dotsc ,n$ $p_{1}+\dotsb +p_{n}=1$
Positiivisille kokonaisluvuille seuraavan epäyhtälön on oltava voimassa: $n$ $H\alijaviiva {\left({\frac {1}{n)),\;\ldots ,\;{\frac {1}{n}}\oikea)}_{n}<H\underbrace {\left ({\frac {1}{n+1)),\;\ldots ,\;{\frac {1}{n+1}}\right)}_{{n+1}}.$
Positiivisia kokonaislukuja , Jossa , tasa-arvon on oltava voimassa $b_{i}$ $b_{1}+\ldots +b_{k}=n$ $H\underbrace {\left({\frac {1}{n)),\;\ldots ,\;{\frac {1}{n))\right)}_{n}=H\left({\ frac {b_{1}}{n}},\;\ldots ,\;{\frac {b_{k}}{n}}\right)+\sum _{{i=1}}^{k} {\frac {b_{i}}{n}}H\underbrace {\left({\frac {1}{b_{i}}},\;\ldots ,\;{\frac {1}{b_{ i}}}\oikea)}_{{b_{i}}}.$

Shannon osoitti [2] , että ainoa funktio, joka täyttää nämä vaatimukset, on

-K\sum _{{i=1}}^{n}p(i)\log _{2}p(i),

missä on positiivinen vakio (ja sitä tarvitaan todella vain entropiayksikön valitsemiseen; tämän vakion muuttaminen vastaa logaritmin kantakohdan vaihtamista). $K$

Shannon päätti, että tietolähteeseen sovellettu entropian mittaus ( ) voi määrittää vähimmäiskaistanleveysvaatimukset, jotka vaaditaan tiedon luotettavaan siirtoon koodattujen binäärilukujen muodossa. Shannonin kaavan johtamiseksi on tarpeen laskea kuvan sisältämän "informaation määrän" matemaattinen odotus tietolähteestä. Shannonin entropiamitta ilmaisee satunnaismuuttujan toteutumisen epävarmuutta. Siten entropia on ero viestin sisältämän tiedon ja sen informaation osan välillä, joka on tarkasti tiedossa (tai erittäin ennustettavissa) viestissä. Esimerkki tästä on kielen redundanssi - kirjainten, peräkkäisten kirjainten parien, kolmosten jne. ulkonäössä on selvät tilastolliset kuviot (katso Markovin ketjut ). $H=-p_{1}\log _{2}p_{1}-\ldots -p_{n}\log _{2}p_{n}$

Shannonin entropian määritelmä liittyy termodynaamisen entropian käsitteeseen . Boltzmann ja Gibbs tekivät paljon työtä tilastollisen termodynamiikan parissa, mikä vaikutti sanan "entropia" hyväksymiseen informaatioteoriassa. Termodynaamisen ja informaatioentropian välillä on yhteys. Esimerkiksi Maxwellin demoni vastustaa myös tiedon termodynaamista entropiaa, ja minkä tahansa informaatiomäärän saaminen on yhtä kuin menetetty entropia.

Määritelmä omilla tiedoilla

On myös mahdollista määrittää satunnaismuuttujan entropia ottamalla ensin käyttöön käsite sellaisen satunnaismuuttujan jakaumasta, jolla on äärellinen määrä arvoja: [3] $X$

P_{X}(x_{i})=p_{i},\quad p_{i}\geqslant 0,\;i=1,\;2,\;\ldots ,\;n

\sum _{{i=1}}^{n}p_{i}=1

ja omat tiedot :

I(X)=-\log P_{X}(X).

Sitten entropia määritellään seuraavasti:

H(X)=\mathbb {E} (I(X))=-\sum _{i=1}^{n}p(i)\log p(i).

Tiedon entropiayksiköt

Tiedon määrän ja entropian mittayksikkö riippuu logaritmin kannasta: bit , nat , trit tai hartley .

Ominaisuudet

Entropia on tietolähteen todennäköisyysmallin yhteydessä määritetty suure . Esimerkiksi kolikon heitolla on entropia:

-2\left({\frac {1}{2}}\log _{2}{\frac {1}{2}}\right)=-\log _{2}{\frac {1}{2 }}=\log _{2}2=1

bittiä heittoa kohden (olettaen, että se on riippumaton), ja mahdollisten tilojen määrä on yhtä suuri kuin: mahdolliset tilat (arvot) ("heads" ja " tails ").

2^{1}=2

Lähteessä, joka generoi merkkijonon, joka koostuu vain kirjaimista "A", entropia on nolla: , ja mahdollisten tilojen lukumäärä on: mahdollinen tila (arvo) ("A") eikä se riipu merkkijonon kannasta. logaritmi. Tämä on myös tieto, joka on myös otettava huomioon. Esimerkki muistilaitteista, jotka käyttävät bittejä, joiden entropia on nolla, mutta joiden informaatiomäärä on yhtä suuri kuin yksi mahdollinen tila eli ei nolla, ovat ROM :iin tallennetut databitit , joissa jokaisella bitillä on vain yksi mahdollinen valtio . $-\sum _{{i=1}}^{\infty }\log _{2}1=0$ $2^{0}=1$

Joten esimerkiksi empiirisesti voidaan todeta, että englanninkielisen tekstin entropia on 1,5 bittiä per merkki, mikä vaihtelee eri teksteillä. Tietolähteen entropiaaste tarkoittaa keskimääräistä bittien lukumäärää dataelementtiä kohden, joka tarvitaan niiden (datan) salaukseen ilman tiedon menetystä, optimaalisella koodauksella.

Jotkut databitit eivät välttämättä siirrä tietoa. Esimerkiksi tietorakenteet tallentavat usein redundanttia tietoa tai niillä on identtiset osiot riippumatta tietorakenteen tiedoista.
Entropian määrää ei aina ilmaista bittien kokonaislukuna.

Matemaattiset ominaisuudet

Ei-negatiivisuus : . $H(X)\geqslant 0$
Rajaus : , joka seuraa Jensenin epäyhtälöstä koveralle funktiolle ja . Jos kaikki alkiot kohteesta ovat yhtä todennäköisiä, . $H(X)=-\mathop {\mathbb {E} } (\log _{2}p_{i})=\sum _{i=1}^{n}p_{i}\log _ {2}{\frac {1}{p_{i}}}=\sum _{i=1}^{n}p_{i}f(g_{i})\leqslant f\left(\sum _{ i=1}^{n}p_{i}g_{i}\right)=\log _{2}n$ $f(g_{i})=\log _{2}g_{i}$ $g_{i}={\frac {1}{p_{i}}}$ $n$ $X$ $H(X)=\log _{2}n$
Jos itsenäinen, niin . $X,\;Y$ $H(X\cpiste Y)=H(X)+H(Y)$
Entropia on ylöspäin kupera funktio elementtien todennäköisyysjakaumasta.
Jos niillä on sama elementtien todennäköisyysjakauma, niin . $X,\;Y$ $H(X)=H(Y)$

Tehokkuus

Aakkosten todennäköisyysjakauma voi olla kaukana yhtenäisestä . Jos alkuperäinen aakkosto sisältää merkkejä, sitä voidaan verrata "optimoituun aakkoseen", jonka todennäköisyysjakauma on tasainen. Alkuperäisen ja optimoidun aakkoston entropian suhde on alkuperäisen aakkoston tehokkuus , joka voidaan ilmaista prosentteina. Alkuperäisen symbolisen aakkoston tehokkuutta voidaan myös määritellä sen -ary-entropiaksi. $n$ $n$ $n$

Entropia rajoittaa suurinta mahdollista häviötöntä (tai lähes häviötöntä) pakkausta, joka voidaan toteuttaa käyttämällä teoreettisesti tyypillistä joukkoa tai käytännössä Huffman -koodausta , Lempel-Ziv-Welch- koodausta tai aritmeettista koodausta .

Muunnelmia ja yleistyksiä

b -ary entropia

Yleensä lähteen b - ary entropia (jossa b on 2, 3, …), jolla on alkuaakkosto ja diskreetti todennäköisyysjakauma, jossa on todennäköisyys ( ) saadaan seuraavasti: ${\mathcal {S}}=(S,\;P)$ $S=\{a_{1},\;\ldots ,\;a_{n}\}$ $P=\{p_{1},\;\ldots ,\;p_{n}\},$ $p_{i}$ $a_{i}$ $p_{i}=p(a_{i})$

H_{b}({\mathcal {S)))=-\sum _{{i=1}}^{n}p_{i}\log _{b}p_{i}.

Erityisesti, kun , saamme tavallisen binäärientropian, mitattuna bitteinä . Kohdalla , saamme triteinä mitatun entropian (yhdessä tritissä on tietolähde, jossa on kolme yhtäläistä todennäköistä tilaa). Kun saamme tietoa mitattuna nats . $b = 2$ $b = 3$ $b=e$

Ehdollinen entropia

Jos aakkosten kirjainjärjestys ei ole itsenäinen (esim. ranskaksi kirjainta "q" seuraa melkein aina "u" ja sanan "peredovik" jälkeen Neuvostoliiton sanomalehdissä sana "tuotanto" tai "työvoimaa" seurattiin yleensä), tällaisten symbolien sekvenssin kantaman tiedon määrä (ja siten entropia) on pienempi. Ehdollista entropiaa käytetään selvittämään tällaisia tosiasioita.

Ensimmäisen kertaluvun ehdollinen entropia (samanlainen kuin ensimmäisen kertaluvun Markovin malli ) on aakkosten entropia, jossa tunnetaan todennäköisyydet kirjainten esiintymiselle toisensa jälkeen (eli kahden kirjaimen yhdistelmien todennäköisyydet) :

H_{1}({\mathcal {S))=-\sum _{i}p_{i}\sum _{j}p_{i}(j)\log _{2}p_{i}(j ) ,

missä on tila, joka riippuu edellisestä merkistä, ja on todennäköisyys , joka on annettu edellinen merkki. $i$ $p_{i}(j)$ $j$ $i$

Esimerkiksi venäjän kielelle ilman kirjainta "e" [4] . $H_{0}=5,\;H_{1}=4{,}358,\;H_{2}=3{,}52,\;H_{3}=3{,}01$

Yksityisten ja yleisten ehdollisten entropioiden kannalta informaatiohäviöt kuvataan täydellisesti tiedonsiirron aikana kohinaisessa kanavassa. Tätä varten käytetään niin kutsuttuja kanavamatriiseja . Lähdepuolen häviön kuvaamiseksi (eli lähetetty signaali tunnetaan) harkitse ehdollista todennäköisyyttä vastaanottaa symboli , jos symboli on lähetetty . Tässä tapauksessa kanavamatriisilla on seuraava muoto: $p(b_{j}\mid a_{i})$ $b_{j}$ $a_{i}$

	$b_{1}$	$b_{2}$	…	$b_{j}$	…	$b_{m}$
$a_{1}$	$p(b_{1}\mid a_{1})$	$p(b_{2}\mid a_{1})$	…	$p(b_{j}\mid a_{1})$	…	$p(b_{m}\mid a_{1})$
$a_{2}$	$p(b_{1}\mid a_{2})$	$p(b_{2}\mid a_{2})$	…	$p(b_{j}\mid a_{2})$	…	$p(b_{m}\mid a_{2})$
…	…	…	…	…	…	…
$a_{i}$	$p(b_{1}\mid a_{i})$	$p(b_{2}\mid a_{i})$	…	$p(b_{j}\mid a_{i})$	…	$p(b_{m}\mid a_{i})$
…	…	…	…	…	…	…
$olen$	$p(b_{1}\mid a_{m})$	$p(b_{2}\mid a_{m})$	…	$p(b_{j}\mid a_{m})$	…	$p(b_{m}\mid a_{m})$

Diagonaalia pitkin sijaitsevat todennäköisyydet kuvaavat oikean vastaanoton todennäköisyyttä, ja minkä tahansa rivin kaikkien elementtien summa antaa 1. Häviöt lähetettyä signaalia kohti on kuvattu osittaisen ehdollisen entropian avulla: $a_{i}$

H(B\mid a_{i})=-\sum _{{j=1}}^{m}p(b_{j}\mid a_{i})\log _{2}p(b_{j }\mid a_{i}).

Kaikkien signaalien lähetyshäviön laskemiseen käytetään ehdollista kokonaisentropiaa:

H(B\mid A)=\sum _{i}p(a_{i})H(B\mid a_{i}).

$H(B\keski A)$ tarkoittaa entropiaa lähteen puolelta, entropiaa vastaanottajan puolelta katsotaan samalla tavalla: sen sijaan se ilmoitetaan kaikkialla (yhteenveto merkkijonon alkioista saat , ja diagonaalin elementit tarkoittavat todennäköisyyttä, että täsmälleen merkki lähetettiin, eli oikean lähetyksen todennäköisyys). $H(A\keski B)$ $p(b_{j}\mid a_{i})$ $p(a_{i}\mid b_{j})$ $p(a_{i})$

Keskinäinen entropia

Keskinäinen entropia tai liittoentropia on suunniteltu laskemaan toisiinsa yhdistettyjen järjestelmien entropia (tilastollisesti riippuvaisten viestien yhteisen esiintymisen entropia) ja sitä merkitään , missä kuvaa lähettimen ja - vastaanottimen. $H(AB)$ $A$ $B$

Lähetettyjen ja vastaanotettujen signaalien suhdetta kuvaavat yhteiset tapahtumatodennäköisyydet , ja tarvitaan vain yksi matriisi kuvaamaan täydellisesti kanavan ominaisuuksia: $p(a_{i}b_{j})$

$p(a_{1}b_{1})$	$p(a_{1}b_{2})$	…	$p(a_{1}b_{j})$	…	$p(a_{1}b_{m})$
$p(a_{2}b_{1})$	$p(a_{2}b_{2})$	…	$p(a_{2}b_{j})$	…	$p(a_{2}b_{m})$
…	…	…	…	…	…
$p(a_{i}b_{1})$	$p(a_{i}b_{2})$	…	$p(a_{i}b_{j})$	…	$p(a_{i}b_{m})$
…	…	…	…	…	…
$p(a_{m}b_{1})$	$p(a_{m}b_{2})$	…	$p(a_{m}b_{j})$	…	$p(a_{m}b_{m})$

Yleisemmässä tapauksessa, kun ei ole kuvattu kanavaa, vaan vuorovaikutuksessa olevia järjestelmiä kokonaisuutena, matriisin ei tarvitse olla neliö. Numerolla varustetun sarakkeen kaikkien alkioiden summa antaa , numeron sisältävän rivin summa on ja matriisin kaikkien elementtien summa on . Tapahtumien yhteinen todennäköisyys ja lasketaan tulona alku- ja ehdollinen todennäköisyys: $j$ $p(b_{j})$ $i$ $p(a_{i})$ $p(a_{i}b_{j})$ $a_{i}$ $b_{j}$

p(a_{i}b_{j})=p(a_{i})p(b_{j}\mid a_{i})=p(b_{j})p(a_{i}\mid b_{ j}).

Ehdolliset todennäköisyydet tuotetaan Bayesin kaavalla . Siten on kaikki tiedot lähteen ja vastaanottimen entropioiden laskemiseksi:

H(A)=-\sum _{i}\left(\sum _{j}p(a_{i}b_{j})\log \sum _{j}p(a_{i}b_{j} )\oikea),

H(B)=-\sum _{j}\left(\sum _{i}p(a_{i}b_{j})\log \sum _{i}p(a_{i}b_{j} )\oikea).

Keskinäinen entropia lasketaan kaikkien matriisitodennäköisyyksien peräkkäisten rivien (tai sarakkeen) summalla kerrottuna niiden logaritmilla:

H(AB)=-\sum _{i}\sum _{j}p(a_{i}b_{j})\log p(a_{i}b_{j}).

Mittayksikkö on bitti / kaksi merkkiä, tämä johtuu siitä, että keskinäinen entropia kuvaa epävarmuutta merkkiparille: lähetetty ja vastaanotettu. Yksinkertaisilla muunnoksilla saamme myös

H(AB)=H(A)+H(B\mid A)=H(B)+H(A\mid B).

Keskinäisellä entropialla on tiedon täydellisyyden ominaisuus - siitä voidaan saada kaikki harkitut suureet.

Historia

Vuonna 1948 tutkiessaan rationaalisen tiedonsiirron ongelmaa meluisan viestintäkanavan kautta Claude Shannon ehdotti vallankumouksellista todennäköisyyspohjaista lähestymistapaa viestinnän ymmärtämiseen ja loi ensimmäisen todella matemaattisen entropiateorian . Hänen sensaatiomaiset ideansa toimivat nopeasti perustana kahden pääalueen kehittämiselle: tietoteorialle , joka käyttää todennäköisyys- ja ergodisten teorian käsitettä tieto- ja viestintäjärjestelmien tilastollisten ominaisuuksien tutkimiseen, sekä koodausteoria , joka käyttää pääasiassa algebrallisia ja geometrisia työkaluja. kehittää tehokkaita koodeja.

Entropian käsitteen satunnaisuuden mittana esitteli Shannon artikkelissaan " A Mathematical Theory of Communication " , joka julkaistiin kahdessa osassa Bell System Technical Journal -lehdessä vuonna 1948.

Muistiinpanot

↑ Tämä esitys on kätevä binäärimuodossa esitetyn tiedon käsittelyssä; yleensä logaritmin kanta voi olla erilainen.
↑ Shannon, Claude E. Viestinnän matemaattinen teoria (määrittelemätön) // Bell System Technical Journal. - 1948. - Heinäkuu ( osa 27 , nro 3 ) . - S. 419 . - doi : 10.1002/j.1538-7305.1948.tb01338.x .
↑ Gabidulin E. M. , Pilipchuk N. I. Luennot informaatioteoriasta - MIPT , 2007. - S. 16. - 214 s. — ISBN 978-5-7417-0197-3
↑ Lebedev D.S., Garmash V.A. Mahdollisuudesta lisätä lennätinviestien siirtonopeutta. - M .: Electrosvyaz, 1958. - Nro 1. - S. 68-69.

Katso myös

Differentiaalientropia (entropia jatkuvalle jakautumiselle)
keskinäistä tietoa
Entropiakoodaus
Markovin ketju
Kullback-Leibler etäisyys

Linkit

Shannon Claude E. Viestinnän matemaattinen teoria Arkistoitu 31. tammikuuta 1998 Wayback Machinessa
Korotaev S.M. Entropia ja informaatio ovat universaaleja luonnontieteen käsitteitä .

Kirjallisuus

Shannon K. Työskentelee informaatioteorian ja kybernetiikan parissa. - M .: Toim. ulkomaalainen lit., 2002.
Volkenshtein M. V. Entropia ja informaatio. - M .: Nauka, 2006.
Tsymbal VP Tiedon ja koodauksen teoria. - K . : Vishcha School, 2003.
Martin, Nathaniel FG & England, James W. Matemaattinen entropian teoria. - Cambridge University Press, 2011. - ISBN 978-0-521-17738-2 .
Shambadal P. Entropian käsitteen kehittäminen ja soveltaminen. - M .: Nauka, 1967. - 280 s.
Martin N., England J. Entropian matemaattinen teoria. - M .: Mir, 1988. - 350 s.
Khinchin A. Ya. Entropian käsite todennäköisyysteoriassa // Matemaattisten tieteiden edistysaskeleet . - Venäjän tiedeakatemia , 1953. - V. 8 , no. 3(55) . - S. 3-20 . (Venäjän kieli)
Brulluen L. Tiede ja informaatioteoria. - M. , 1960.
Viner N. Kybernetiikka ja yhteiskunta. - M. , 1958.
Wiener N. Kybernetiikka eli ohjaus ja viestintä eläimissä ja koneissa. - M. , 1968.
Petrusenko L. A. Aineen itseliike kybernetiikan valossa. - M. , 1974.
Ashby W. R. Johdatus kybernetiikkaan. - M. , 1965.
Yaglom A.M. , Yaglom I.M. Todennäköisyys ja tiedot. - M. , 1973.
Volkenshtein M. V. Entropia ja informaatio. - M . : Nauka, 1986. - 192 s.
Vereshchagin N.K., Shchepin E.V. Tietoa, koodausta ja ennustamista. - M. : FMOP, MTsNMO, 2012. - 238 s. - ISBN 978-5-94057-920-5 .

Sanakirjat ja tietosanakirjat

Bibliografisissa luetteloissa
BNE : XX535116 BNF : 11985913j GND : 4743861-7 J9U : 987007550784405171 LCCN : sh85044152 NDL : 01191172 NKC : ph425914