torsdag 3 januari 2013

Förvirrat om entropi och information

Forskning och Framsteg är en utmärkt tidskrift som jag levt med i cirka tre decennier. Ett och annat lågvattenmärke förekommer dock i dess spalter, som den text med rubriken Finns slumpen? av Allan Gut, professor emeritus i matematisk statistik, som återfinns i senaste numret 1/2013.1,2 Det rör sig om en allmänt pladdrig text, vars absoluta nadir nås då Gut tar på sig att förklara hur informationsteorins centrala storheter hänger samman:
    Inom informationsteorin används entropi som ett mått på informationsinnehållet, där ett högt informationsinnehåll svarar mot låg entropi och tvärtom.
Ojdå, hur tänkte han nu? Det var min första reaktion. Min andra reaktion var att det nog ändå måste röra sig om ett förargligt skrivfel, där han råkat knappa in ordet "låg" istället för "hög".3 Det visade sig emellertid snabbt att min första reaktion var den mer relevanta, ty Gut förklarar hur han tänkt:
    Matematisk analys av entropin visar att det symmetriska fallet ger störst entropi, och då är också slumpen som störst. Medan entropi för ett mynt med en klave och en krona på vardera sidan är lika med noll.

    För att tolka detta kan vi tänka så här. Slumpen kan vi som bekant inte veta något om i förväg. Inte ens om vi singlar ett symmetriskt mynt många gånger får vi någon ledtråd om vilket utslaget blir nästa gång. Alla gissningar är lika bra, eller dåliga. Om vi däremot singlar ett asymmetriskt mynt, där sannolikheten för klave är 90 procent och sannolikheten för krona bara 10 procent, så är det rimligare att gissa på klave än på krona – det blir oftare rätt. Extremfallet är förstås ett mynt med krona på bägge sidor. Då vet vi allt. Det symmetriska myntet som har störst entropi ger oss således minst information.

Här började jag fundera över lämpliga sokratiska metoder att försöka förklara informationsteorins informationsbegrepp för Gut. "Om du hade behov av att hämta så mycket information som möjligt från en digital kanal, skulle du då föredra en som på ett oförutsägbart sätt blandar nollor och ettor, eller skulle du välja en som inte förmår annat än att leverera en monoton och aldrig sinande ström av ettor?" Inför en sådan fråga borde han väl begripa att han fått informationsbegreppet om bakfoten? Fast nej, kanske ändå inte, ty en liten bit fram i texten ger Gut själv ett liknande exempel, där han menar att om han behöver söka information bland sina medmänniskor så har han mest att hämta hos dem vilkas yttranden han redan på förhand kan förutsäga:
    Ta till exempel entropi och människotyp. En pålitlig, ordningsam, förutsägbar, inflexibel människa överraskar föga; man vet precis vad hon ska svara, säga, göra och därför kan hon beskrivas med en entropi nära noll, medan en nyckfull, impulsiv, spontan och kaotisk person ger mycket lite information, och på så vis inte är förutsägbar. En sådan person kan identifieras med hög entropi.
Ack så tokigt!

Fotnoter

1) Det här är inte första gången jag råkar på dumheter i en text av Allan Gut. I sin bok Sant eller sannolikt (Norstedts, 2002) bjuder han på s 137-138 på ett exempel på den vanligt förekommande statitiska metod som kallas stickprovsdragning, men exemplet är så till den grad illa valt att det ger en gravt vilseledande bild av vad finessen med att dra ett stickprov egentligen är. Det hela kändes såpass pinsamt, för att komma från en professor i matematisk statistik, att jag i min recension av boken i (den sedemera nedlagda) tidskriften Dagens Forskning avstod från att orda om saken, annat än med det mer allmänna påpekandet om att
    författaren borde ha anslagit något mera tid åt sitt bokprojekt, då ett antal av exemplen framstår som ogenomtänkt utvalda och/eller slarvigt genomförda.
Dock hörde jag av mig till Gut med ett påpekande om hans fadäs. Något tack eller erkännande från hans sida fick jag inte, men man får glädjas åt det lilla: i den påföljande pocketupplagan av boken är de felande sidorna (i tysthet) strukna.

2) I det outtröttliga korståg mot dumheter som jag driver här på bloggen och annorstädes, är det påtagligt ofta just professorer som kommer i skottlinjen. Jag när ännu en lite romantisk föreställning om att vi professorer har ett särskilt ansvar för sanning, vetenskaplighet och intellektuell hederlighet, och tenderar därför att reagera starkare när det är just en professor som häver ur sig något vilseledande eller dumt. Bland de svenska professorer som jag gått hårt fram mot återfinns bl.a. Bosse Holmqvist, Claes Johnson, Ingemar Nordin, Peter Stilbs och Moira von Wright. Gemensamt för dessa är att de driver en given agenda (oftast om än inte uteslutande klimatförnekeri) så hårt att det får dem att tappa omdömet och glömma de vetenskapliga och retoriska redlighetskrav de naturligtvis egentligen känner till. Allan Gut faller lite utanför denna ram - jag kan inte identifiera någon agenda från hans sida. Snarare verkar det som om han känner ett behov av att göra sig hörd i största allmänhet, men inte riktigt har det tålamod som krävs för att se till att det han skriver är vederhäftigt.

3) Förklaringar som bättre ansluter sig till den gängse informationsteoretiska definitionen av information finner vi t.ex. i Wikipedia...
    In information theory, entropy is a measure of the uncertainty in a random variable. In this context, the term usually refers to the Shannon entropy, which quantifies the expected value of the information contained in a message. Entropy is typically measured in bits, nats, or bans. [...] Shannon entropy is the average unpredictability in a random variable, which is equivalent to its information content.
...eller i Nationalencyklopedin:
    Inom informationsteorin används entropin som ett mått på informationsinnehållet i ett meddelande. Om det finns n=2m tänkbara meddelanden som alla är lika sannolika, definieras entropin som S=log2n=m och kan tolkas som antalet binära siffror som behövs för att definiera meddelandet. Om meddelandena däremot är olika sannolika kan medelantalet använda siffror i bästa fall reduceras till
      S=-p1log2p1 -...- pnlog2pn,
    där pk är sannolikheten för meddelande nr k.

16 kommentarer:

  1. Märkligt! Men kanske ändå ett resultat av "life at the edge of chaos", på nåt sätt... ;-)

    Nu väntar jag på din recension av "The signal and the noise"!

    SvaraRadera
  2. "Inom informationsteorin används entropin som ett mått på informationsinnehållet i ett meddelande."

    Begreppsförvirringen blir mindre om "information", i likhet med "statistiskt beroende" och "korrelation", får vara något man bara talar om som en relation mellan (minst) två slumpvariabler. I(X;Y) = H(X)+H(Y)-H(X,Y) är ett kvantitativt mått på hur mycket information X innehåller om Y. I(X;X) = H(X) är ett mått på hur mycket information X innehåller om sig själv. Nedkortningen av det sistnämnda till att H(X) är "informationen i X" är lite olycklig. En lång slumptalssekvens innehåller förvisso massor av information om sig själv, men inte nödvändigtvis så mycket information om något annat.

    /Erik

    SvaraRadera
  3. Ajaj, och i FoF dessutom. Man kan ju förstå känslan att en sändning av "Aktuellt" ger mer information än en timme av "Myrornas krig", men att en helt svart tv-ruta skulle ge maximalt informationsutbyte...
    Begreppet "relativ entropi" ligger närmare det Allan beskriver: den relativa entropin av X relativt till exempel likformig fördelning över 1,2,...,m ges av väntevärdet av log(mf(X)) där f är X's frekvensfunktion (till skillnad från vv av -log(f(X)) som är den vanliga entropin).

    SvaraRadera
  4. Allan Gut verkar använda ordet information i betydelsen förutsägbarhet (hur mycket "information" man har om det som man ännu inte har sett), när det inom informationsteori snarare används som oförutsägbarhet (jag brukar tänka mig att det handlar om hur mycket information som krävs för att beskriva strängen av nollor och ettor). Det var onekligen inte så lyckat. Även om det inte är särskilt svårt att förstå vad han menar i krönikan i FoF, blir det förvirrande för den läsare som kan lite informationsteori.

    Jag känner inte Allan Gut så väl, men din slutsats av denna populärvetenskapliga krönika att han inte kan någon informationsteori alls verkar förhastad tycker jag. Det kan väl lika gärna vara ett misslyckat försök att popularisera.

    Din "sokratiska" fråga känns inte heller så lyckad:
    "Om du hade behov av att hämta så mycket information som möjligt från en digital kanal, skulle du då föredra en som på ett oförutsägbart sätt blandar nollor och ettor, eller skulle du välja en som inte förmår annat än att leverera en monoton och aldrig sinande ström av ettor?"
    Vad menar du med att "hämta" information från totalt brus? Hur skall man kunna förstå vad som menas med informationsbegreppet från den frågan?

    SvaraRadera
    Svar
    1. Tack Svante för dina funderingar!

      Det är naturligtvis fullt möjligt att Allan Gut behärskar grundläggande informationsteori, men jag tycker faktiskt att hans okonventionella användning av informationsbegreppet tyder på motsatsen. Det vore intressant att höra vad han själv säger om saken (jag har uppmärksammat honom på denna bloggpost).

      När det gäller den binära kanal ("som på ett oförutsägbart sätt blandar nollor och ettor") jag omnämner i min sokratiska fråga, så låt oss anta att denna har maximal entropi och alltså maximal informationsöverföringshastighet. Frågan om informationsöverföringshastigheten är dock skild från frågan om informationen är intressant eller inte. Om det, som du föreslår, är fråga om "totalt brus" så är informationen ointressant, men det behöver faktiskt inte vara fråga om brus: en kanal maximal entropi kan alternativt härröra från en optimalt kodad (komprimerad) källa av högintressant information. En diskussion om detta vore en sannolik fortsättning på den sokratiska diskussionen, och jag tycker för övrigt att Johan J:s TV-exempel i kommentaren ovan är ett utmärkt pedagogiskt redskap i sammanhanget.

      Radera
    2. "[S]kulle du då föredra en [kanal] som på ett oförutsägbart sätt blandar nollor och ettor, eller skulle du välja en som inte förmår annat än att leverera en monoton och aldrig sinande ström av ettor?"


      Båda dessa verkar tämligen oanvändbara som kanaler eftersom det mottagna meddelandet inte har något med det som skickas att göra. Kanalens kapacitet (informationsöverföringsförmåga) ges av hur många olika meddelanden den *skulle kunna* överföra (utan fel), inte vilka egenskaper det meddelande den faktiskt överför har (ettor eller ej). TV-kanalen kan överföra både en svart bild och myrornas krig -- samt mycket annat som tur är. (En kanal har väl för övrigt ingen entropi i sig.)


      Hur informativt ett meddelande M sedan är för mottagaren beror på hens kunskap/bakgrundsinformation I: hur mycket minskar osäkerheten om den utsaga/det tillstånd X hen är intresserad av -- osäkerheter kvantifierade som entropin hos P(X|I) respektive P(X|MI). När vi *har* mycket information om X är entropin liten. Om ett meddelande minskar entropin mycket så var det meddelandet informativt (i informationsteoretisk mening, även om denna personberoende beskrivning sällan tas upp i skolböckerna).


      (Jag håller alltså i stort med Svante.)


      Jag tycker den andra professorn förvirrar den första professorns "lågvattenmärke" med sitt slarvigt formulerade kanalexempel.


      /SP

      Radera
  5. Med så många kloka människor i närheten hoppas jag att en dumbom som jag kan få svar på några undringar (trots talesättet om dårar och vise män) om information och entropi (som ex-fysiker har jag hyfsad koll på entropibegreppet inom fysiken, men informationsteorin är en annan femma.)

    Låt mig ta ett exempel, i tre steg. I samtliga fall tänker vi oss ett system med en sändare och en mottagare som ska förmedla en viss informationsmängd, till exempel tretton stycken variabler som vardera kan anta tre värden; låt oss, av skäl som förmodligen redan blivit uppenbara, beteckna dem med för "1", "x" och "2". De tre fall som jag tänker mig är (a) vi har ingen som helst information om vad dessa tecken står för, (b) vi vet att de är tipstecken för matcher i diverse engelska ligor, och (c) vi vet exakt vilka engelska lag som spelar de olika matcherna. Låt oss vidare tänka oss tre meddelanden/utfall, till exempel (1) 1111111111111, (2) xxxxxxxxxxxxx och (3) x2x12xx111x12 (detta "meddelande" är avsett att vara "slumpmässigt"), som kodas efter alla konstens regler och skickas från sändare till mottagare.

    Kan någon reda ut var och hur informationen och/eller entropin manifesterar sig här; i meddelandena eller "systemen"? I (b) (och förmodligen (c)) är (1) mycket mer sannolikt än (2); i (c) skulle eventuellt (3) kunna vara det mest sannolika utfallet -- hur påverkar det entropin? Jag misstänker att det jag har svårast att få kläm på är sambandet mellan den "externa" informationen, ett enskilt meddelande och entropibegreppet.

    SvaraRadera
    Svar
    1. Hm, bosjo, det där ser ut att kräva en smärre uppsats till svar. Jag tror jag väljer en avvaktande metod: att luta mig tillbaka och hoppas att någon av mina övriga läsare känner sig manad att rulla upp skjortärmarna och ta sig an din fråga...

      Radera
    2. För att tala om entropi (i statistisk mening) så behöver man: en slumpvariabel X och en sannolikhetsfördelning P(X=x). För en diskret variabel ges entropin av H(X) = -\sum_k P(X=x_k) log(P(X=x_k)).

      För att tala om information (i statistisk mening) behöver man: Två slumpvariabler X och Y. Och en simultanfördelning P(X=x,Y=y), så att man kan beräkna sannolikheten för att X=x *och* att Y=y. Informationen i X om Y definieras som I(X;Y) = -\sum_km P(x_k,y_m) log(P(x_k,y_m) / (P(x_k) P(y_m))). (Alternativt, så definierar en del framställningar "information" som differensen i entropin före och efter en uppdatering av sannolikhetsfördelningen. Då behöver man en en slumpvariabel X, en sannolikhetsfördelning Pföre(X) och en sannolikhetsfördelning Pefter(X). Här är det underförstått att det är information om X man talar om.)

      Information är alltså inte en egenskap hos individuella meddelanden. Liksom korrelation så är information en egenskap hos en simultanfördelning P(X,Y) (alternativt en egenskap hos paret (Pföre(X),Pefter(X))).

      I dina scenarier (a)-(c) finns ganska stort tolkningsutrymme när det gäller att fylla ut detaljerna. Här är ett förslag:

      (a) Slumpvariabeln Z antar värden som består av 13 tecken långa symbol-sekvenser från att alfabet med tre tecken. En vanlig tolkning av "ingen som helst information" är att motsvarande sannolikhetsfördelning är likformig, så anta att P(Z) är likformig över {1,x,2}^13. Entropin blir H(Z) = 20.6 bits. Någon poäng med att tala om "information" kan jag inte se här.

      (b) När man lär sig att de 13 tecknen ska tolkas som fotbollsmatch-resultat uppdaterar man kanske sin sannolikhetsfördelning till någon icke-likformig fördelning Q(Z). Fråga mig inte om detaljer, man kan kanske åtminstone kan ta hänsyn till några empiriska data om hur vanligt det är med oavgjorda matcher inom fotboll. Differensen Hföre(Z) - Hefter(Z) = -\sum_k P(z_k) log(P(z_k)) + \sum_k Q(z_k) log(Q(z_k)) är ett mått på hur mycket information man fått om Z i och med uppdateringen.

      (c) Om man anser sig veta mycket om engelsk fotboll uppdaterar man säkert sannolikhetsfördelningen en gång till när man lär sig exakt vilka lag som spelar matcherna. Säg att man uppdaterar från Q(Z) till R(Z). Differensen Hföre(Z) - Hefter(Z) = -\sum_k Q(z_k) log(Q(z_k)) + \sum_k R(z_k) log(R(z_k)) är ett mått på hur mycket information man fått om Z i och med denna andra uppdatering.

      Vad gäller kodning av 1111111111111, xxxxxxxxxxxxx och x2x12xx111x12, så kan man, givet en sannolikhetsfördelning P(Z), beräkna optimal längd för kodorden. Med optimal kodning blir längden på kodordet för en symbolsekvens z ca. -log(P(z)). När man uppdaterar sin sannolikhetsfördelning bör man alltså uppdatera kodorden också.

      /Erik

      Radera
  6. One of the best popular references to the concept of entropy and information theory is Alfréd Rényi's 1984 book "A Diary on Information Theory", Wiley Series on Probability and Mathematical Statistics. A large part of it can be read with a background on high school mathematics only (albeit there are some subtle things, e.g., towards the end where the Prüfer code is offered as an explanation for the number of labeled trees on n vertices).

    I have used the book, in conjunction with teaching a course for last year mixed-audience undergraduate students in Computer Science and Electrical Engineering, titled Information and Cryptography (when I was in the US.) I have it in my office, but these days it is very hard (and expensive) to find.

    Popularization of science (and mathematics) is very difficult and very dangerous. It is so much easier to presume that your audience knows some mathematics rather than face an audience consisting of people who think that "mathematics was so hard when I was at school".

    SvaraRadera
  7. Finns det någon koppling mellan entropibegreppen inom termodynamik och informationsteorin? Eller råkar de bara ha samma namn?

    Borde kanske ligga under "Fråga olle"

    SvaraRadera
    Svar
    1. Jodå, det finns starka samband mellan begreppen (jämför t.ex. Wikipediaartikelns Gibbsentropi (3) med definitionen i bloggpostens Fotnot 3).

      Radera
    2. Kanske är de samma sak. Man behöver bara acceptera att information är energi/temperatur. Det hade jag svårt för, men nu inser jag det.

      Radera
    3. Vad menas egentligen med att "information är energi/temperatur"?

      Det är i princip samma formel för statistisk entropi och Gibbs-entropi i statistisk mekanik, men olika restriktioner på vilka sannolikhetsfördelningar man kan plugga in i formeln. Statistisk entropi kan man beräkna för vilken sannolikhetsfördelning som helst. Gibbs-entropi kan man bara beräkna för en sannolikhetsfördelning över mikrotillstånd för ett fysiskt system i termodynamisk jämvikt. Generellt sett finns det alltså inget samband, men i sammanhang där man begränsar sig till att betrakta sannolikhetsfördelningar som har något med mikrotillstånd & termodynamisk jämvikt att göra så kan det finnas samband.

      /Erik

      Radera
  8. Erik
    Med det menar jag att information kan anges i joule. Den allra enklaste klockan, som visar om det är natt eller dag, kräver energi för att fungera. Ju varmare det är, desto mer energi måste tillföras. Vid absoluta nollpunkten behövs ingen energi. Det leder till en paradox, men det är ju sällan så kallt.

    SvaraRadera
  9. Olle, tack för fina kommentarer om entropin. Själv Chalmerist; dock av årgång 1971.
    Borde inte entropibegreppet användas mera frekvent - då skulle man snart see dess nytta. I hela västvärden växer byråkratin så, att en stor del av sammhällets produktiva vinster äts upp i gigantiska och överbefolkade byråkratier. Kan man då säga, att den eller den personen på Försäklringskassan är improduktiv medan andra personer är produktiva? Nej alla statistiska begrepp förutsätter ett relevant urval varför begreppet inte är tillämpbart i enskilda fall.

    Men idag är hela vår kultur överbefolkad av byråkrater (både offentliga och privata!) I Sverige är det idag cirka 1.5 miljoner individer som producerar medan det är ungefär tre gånger så många som övervakar, administrerar (som vi dagligen ser med utomordentligt dåligt resultat).

    Är det inte uppenbart, att vår kultur är utsatt för en oerhörd entropitillväxt. Om så är fallet: Går vi mot en social nedkylning i likhet med Clausius nedkylning av värlen?

    Sedan 1960-talet har vår industriella produktion ökat i storleksordningen 50 gånger om. Ur produktiv synvinkel borde därför entropin ha krympigt mycket fördelaktigt. Men ökningen i byråkrati för samma samhälle är våldsam, och sammantaget står vi nu i en fälla där inget land kan "få igång tillväxten".

    Troligen är det omöjligt att förstå för vanligt folk, att om arbetslösheten på t ex 1960-talet var 5%, och vi har en våldsam produktivitetsökning sedan dess, hur kan då fortfarande arbetslösheten vara ungefär samma storleksordning. Vart har alla friställda individer tagit vägen sedan 1960-talet?

    Om man inte tvingade in ofantliga mängder individer i alla tunga byråkratier med våldsam entropitillväxt som följd; då borde dagens arbetslöshet vara 70%.

    ***
    Uppenbart saknar vi verktyg att behandla sådana här frågor. Dessa frågor blir ju alltmer akuta, därför att inget EU-folk; USA - folk kan ju lösa denna fråga om byråkratins entropitillväxt; vilken effektivt och metodiskt kväver oss.

    ***

    Jättekul om ni vill kommentera

    Martin

    SvaraRadera