Kul och illustrativ regel för grafer MIT visade för "stjärnor" och "cirklar"

2010-08-28

Det här pressmeddelandet från MIT om en studie publicerad i IEEE Transactions on Signal Processing (Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures (PDF)) gjord vid MIT av Tan är både som vi kommer se illustrativt och kul:

"In an article published this spring in IEEE Transactions on Signal Processing The researchers demonstrated that trees with a “star” pattern — in which one central node is connected to all the others — are the hardest to recognize; their shape can’t be inferred without lots of data. Suppose, for instance, that the central node represents asthma, and 100 other nodes represent all the factors that can contribute to it. If the computer system looks at 100 data samples, each one could imply a different predictor of asthma. It might require tens of thousands of samples before the system could reliably conclude which factors have stronger correlations than others."

Från: Sizing samples - Many scientific disciplines use computers to infer patterns in data. But how much data is enough to ensure that the inferences are right? | MIT.edu

Först kan vi konstatera att även om det inte är uppenbart för mig hur man kan bevisa det här (och jag nöjde mig med att läsa pressmeddelandet) är det på sätt vis uppenbart. Oavsett om som här rent av värderar vikter i mönsterigenkänning kommer stjärnan ändå ner till att vi gör saker motsvarande en i sänder som i exemplet längre ned (där dock hjärnan gör motsvarande arbete men utan att jag annat behöver göra än att försöka hjälpa det på traven).

Det som är komiskt med det här är att detta kan vara det mönster vi själva upplever är enklast eller mest uppenbart när vi vill förklara saker. Vad som kan vara förklaringen till det är att mönstret bär mycket mindre information eller mening jämfört med mer "komplexa" grafer. Det är lättare och trevligare åtminstone initialt för vår hjärnans perceptiva nätverk (vilka är de delar vi troligen mer kan jämföra med neuronnät även om jag är tveksam till att det är riktigt samma sak praktiskt) där det helt enkelt är en mindre sak att komma att tänka på och hålla i huvudet.

Genom att stjärnan bär mindre mening kommer den också lösa uppgiften sämre. Den kan inte uttrycka något lika smart.

Vi kan illustrera sambandet praktiskt via det intelligens-pussel jag köpte på Clas Ohlsson 22 juli och skrev om runt algoritmer för att lösa det "optimerat".


Pusslet kostade 19 kr på Clas Ohlson. Det fanns också fler varianter men jag köpte endast detta och valde det därför att jag tyckte det var ett intressant mönster.

Här kan vi antingen göra en cirkel eller en stjärna och om inte exakt samma sak (enklare samband här) jämfört med när vi är vikter och söker mönster i data kommer det ner till samma sak där här cirkeln är bättre än stjärnan. Eller som jag förklarade det:

"Av bitarna i pusslet är en bit speciell och skiljer sig från samtliga övriga. Vad som är speciellt med den är att den har två blåa symboler. Ingen annan bit har två symboler i samma färg.

Denna bit har lägre entropi än övriga därför att den reducerar antalet möjligheter som finns kvar. Att börja med en bit som t.ex. har alla färger kan verka bra därför att det håller möjligheter öppna men det är falskt. Vi vill reducera antalet möjliga kvarstående kombinationer och antal bitar.

Att reducera antalet kombinationer kan resultera i att vi inte kan gå vidare men detta är omöjligt för den första biten. När vi börjar kan vi placera vilken som helst bit var som helst på brädet utan att det kan innebära att vi inte kommer kunna lösa pusslet.

Börjar vi med denna bit har vi direkt reducerat rymden för problemet enormt jämfört med vilken annan bit som helst.

På samma sätt ska vi placera den vid en kant. Teoretiskt reducerar det däremot inte rymden men praktiskt för oss blir den mindre och det utan att ha begränsat lösningsrymden därför att vi ännu kan flytta denna och en eller flera bitar vi ansluter till den horisontellt eller vertikalt.

I bilden nedan såg vi att biten placerades i högre nedre hörnet. Där försvinner två sidor på biten som inte behöver beaktas samtidigt som den inte lika lätt glider i väg på brädet."

Från: Pussel med 8 bitar för högre IQ

Här är det åtminstone en övertygelse jag bär och många andra att sambanden för entropi både rörande information (Shannon) och energi är tämligen allmänna i universum. Det innebär givetvis inte att det nödvändigtvis innebär att man kan lösa särskilt många problem med man kan åtminstone mäta saker med Shannons entropi (se A Mathematical Theory of Communication (PDF) för Shannons artikel från 1948 som publicerades i The Bell System Technical Journal).

Entropi för information respektive energi

Ska vi försöka förklara eller inse skillnaden mellan Shannons entropi och entropi för energi (där ju båda formlerna kan variera en del) är det åtminstone för mig svårare och vad jag av och till funderat på kanske mest senaste sex månaderna. När jag e-postade Hong (som gjorde studien nyligen publicerad i PLoS One - Uncertainty Compensation in Human Attention: Evidence from Response Times and Fixation Durations (PDF) jag diskuterade i Mycket större värde i ett forskningsprojekt vid Uppsala Universitets än normalt) med några frågor rörande hans studie uttryckte han sig på följande sätt vilket väl illustrerar likheten i formlerna:

"For the second question… The primary difference between energy entropy (Boltzmann) and the Shannon is actually only the base of the logarithm used to calculate it. Entropy, Shannon or otherwise is fundamentally an issue of the number degrees of freedom, as defined from the classical mechanics standpoint (given by the entropy = k log w, w being the number of ways the particles are configured in space). The study (Hong & Beck) in PLOS One is very similar to Danielle Bassett’s work. Really what Bassett is showing is an entropy/information-based description of the structures of neural networks (biological and man-made). Our data mirror that by using entropy as the basis for describing the behavior generated by these underlying neural networks."

Det säger oss (eller mig särskilt men jag aldrig riktigt funnit fysikens formler den för mig mest illustrativa vägen för att förstå universum, naturen eller livsmedelsbutikens moms) egentligen inte så mycket om vad likheten egentligen här. Nyligen uttryckte jag ett sätt kanske möjligt att se på det så här:

"Här roade jag mig dock med att göra samma sak mer filosofiskt för vad i universum vi kan uppleva:
  • Båda typerna av entropi uttrycker troligen egenskaper som ligger mer i universum och oss själva och är allmänna för "allt".
  • Hur vi uttrycker dem påverkas dock av oss själva.
Därför såg jag det som meningsfullt att faktiskt uttrycka vad respektive entropi motsvarar i vår omedelbara värld:
  • Språk uttrycker givetvis entropi enligt Shannon.
  • Vad vi säger och skriver kan vi se som en karta eller en instruktion hur vi skulle kunna förändra omvärlden om vi är tillräckligt motiverade och börjar realisera den.
  • I detta fall investerar vi energi som flyttas om och vi får ett uttryck i entropi sett som energi.
Språk säger vad vi kan göra eller har gjort. Det bär i sig inte energi entropi men dess Shannon entropi går att översätta till energi entropi när vi realiserar det."

Vi kan också se det som potentiellt rekurisvt rörande tror jag alla samband. Där samband vi har för språk och entropi minus energikostnaden (vilken kan variera t.ex. beroende av om du lider av depression i ögonblicket eller är trött) utan för i hjärnan kommer ner exakt samma relationer för populationer av människor precis som organisation i hjärnan på ett företag, Twitter, mellan tidningar (ovanför enskilda medarbetare), städer eller hela länder o.s.v.

Det innebär dock inte att vi alltid väljer de mest effektiva metoderna själva och ibland så vitt jag kan se mycket sämre än vad vår hjärna gör. Därför kan man se exempelvis för organisationer som har dåligt gjorda hierarkier att de har för "dyr" (inte just i ekonomisk mening där vi kanske istället kan se det som att medarbetare, organisationer o.s.v. skapar små vågar som färdas ut där de kan samverka med varandra) kommunikation i företaget kan hamna i stjärnor och cirklar eller enklast och mest korrekt helt enkelt är ett onödigt kostsamt avstånd (d.v.s. inte "kulturellt avstånd" där begreppet och andra från min modell grundläggande väldigt enkelt sammanfattades i första inlägget från: Nulägesstatus: Modell av människans språk samt där vi även har Människans kreativitet och språk där längre artiklar kan nås).

Dessutom är du över-mätt och förslöad skapar du inte tillräckligt med energi oavsett om vi betraktar information eller fysisk värld för att något ska hända alls. D.v.s. vad jag uttryckte så här kring innovationer till stora äldre organisationer där det för mer pengar är viktigt att hålla dem hungriga:

"Därmed inte sagt att jag tror på att vräka in en massa pengar i sådant här bara för att möjligt värde finns. För mig tycks det sällan som det ger särskilt mycket i som här områden med mycket stora potentiella värden där det är mycket viktigare om man just söker kommersiella företag (vilket givetvis regering m.m. normalt vill se) att personerna är hungriga och inte sitter och fokuserar på att organisationer, konferenser, möten på innovationsskapelsefabriken (eller vad du statliga projekt eller motsvarande i sådant här för ögonblicket kallas), styrelsen på universitetet o.s.v. Särskilt är det för mycket pengar gör det entiteter tunga och slöa där mindre pengar och en lättare snabb styrka kan prestera mycket mer där mindre tid slösas på vad som konkret saknar betydelse vilket man helt säkert ska vara mer observant på när det gäller universitet."

Sedan är visst motsatsen möjligt också om du slagits hungrig länge men rörande just det enklast att antingen gå fram, bak eller frysa vet jag inte om man egentligen tappar särskilt mycket på även om man inte ska försöka avgöra det själv.

Vidare där vi för våra tänkar till Harvard University under denna prövningens tid för dem går det givetvis att t.ex. bli över-hungrig på motsatt sätt ungefär som kaffe för att publicera studier eller bli övertränad på ett språk och se samband som inte finns.

Mycket större värde i ett forskningsprojekt vid Uppsala Universitets än normalt

Här har vi nu ett vad jag bedömer som nytt område vid Uppsala Universitet när jag gick igenom deras pressmeddelanden från senaste året (vilket säkert inte speglar allt man gör) som har potential att leda till konkreta världen:

Rekordstort anslag till forskning om datoriserade system (2010-01-13]) | Uppsala Universitet

Vi kan konstatera att de liksom övriga svenska universitet av och till ger ifrån sig nya företag (se t.ex. Quality. Innovation. Future. Området (och därför ev. projektet) kan vi dock ha mycket större potentiell möjlighet än vad som oftast är fallet för jämförbart därför att:

1. Praktiska tillämpningar finns inom medicinteknik vilket är en mycket stor bransch som omsätter ordentliga pengar.

2. Mer "kortsiktigt" och vad jag antar att projektet berör finns helt säkert ett antal applikationer rörande mätning på patienter där precis som man indirekt pekar på inarbetade teorier och tillämpningar finns inom signalbehandling att "översätta över" där jag ser flera möjligheter som bör gå att realisera relativt tidigt samtidigt som det kan ha möjlighet att vara en typ standardutrustning som används under många år.

3. Mer allmänt gäller att även om signalbehandling har haft utrymme inom medicin sedan länge t.ex. för att mäta exempelvis hjärtfrekvens och aktivitet i hjärnan är när det gäller åtminstone hjärnan tillämpningar av teorier tillämpade inom andra områden eftersatta och det gäller också mycket dyr utrustning (vilket kanske inte är just det område som är främst intressant här där kommersiella aktörer redan arbetar på detta och där riktade lösningar publicerats).

Att mäta detta är vad signalbehandling är som gjort för och genom att föra samman två vetenskapsgrenar kan det skapa fler värden än man räknat med därför att man inte sett möjligheter respektive behov av lösningar som finns (jämför med vad som diskuterats i inläggen samlade i Nulägesstatus: Modell av människans språk).

4. Ser vi det mer generellt har vi delvis enkla sammanband mellan informationsteori (eller signalbehandling, mönsterigenkänning o.s.v. beroende på hur man ser på det eller kallar det). Vi har t.ex. ett färskt exempel på det i Hongs (Indiana University) studie:

Uncertainty Compensation in Human Attention: Evidence from Response Times and Fixation Durations | PLoS One
DOI: 10.1371/journal.pone.0011461 S. Lee Hong1 och Melissa R. Beck,
2010.

Vi kan också jämföra det med studien Bassets (University of California Santa Barbara) gjorde publicerad i PLoS Computational Biology, 2009 (Efficient physical embedding of topologically complex information processing networks in brains and computer circuits) där jag skrev följande som del av en forskningsnyhet:

"För människans hjärna (B) gäller Rent's regel när sambandet mellan vit materia (motsvarar antalet anslutningar mellan noder) och grå materia (motsvarar antalet beräknande enheter d.v.s. noder). Orsaken tros vara att evolutionen optimerat åtgång av energi mot beräkningskraft."

Från: Likheter mellan datorchips, människans hjärna och maskars nervsystem

Här har vi två exempel på studier där entropi uttrycks i två perspektiv på sätt som både möjliggör mer allmänna och tillämpningsnära modeller vilket Hong sammanfattade bättre för mig:

"For the second question… The primary difference between energy entropy (Boltzmann) and the Shannon is actually only the base of the logarithm used to calculate it. Entropy, Shannon or otherwise is fundamentally an issue of the number degrees of freedom, as defined from the classical mechanics standpoint (given by the entropy = k log w, w being the number of ways the particles are configured in space). The study (Hong & Beck) in PLOS One is very similar to Danielle Bassett’s work. Really what Bassett is showing is an entropy/information-based description of the structures of neural networks (biological and man-made). Our data mirror that by using entropy as the basis for describing the behavior generated by these underlying neural networks."

Enkla modeller som här helt säkert går att skapa har många möjliga praktiska tillämpningar även när de p.s.s. som det här projekt vid UU som diskuterades sannolikt är väldigt avgränsade. Områden är t.ex. dataspel, kontroller av elektronik (mobiltelefoner m.m.) med gester, anpassning av musik, ljud m.m. för känslomässig påverkan, analys av text (tidningar m.m.) för direkt anpassning, mer meningsfull indexering av data o.s.v.

Därmed inte sagt att jag tror på att vräka in en massa pengar i sådant här bara för att möjligt värde finns. För mig tycks det sällan som det ger särskilt mycket i som här områden med mycket stora potentiella värden där det är mycket viktigare om man just söker kommersiella företag (vilket givetvis regering m.m. normalt vill se) att personerna är hungriga och inte sitter och fokuserar på att organisationer, konferenser, möten på innovationsskapelsefabriken (eller vad du statliga projekt eller motsvarande i sådant här för ögonblicket kallas), styrelsen på universitetet o.s.v. Särskilt är det för mycket pengar gör det entiteter tunga och slöa där mindre pengar och en lättare snabb styrka kan prestera mycket mer där mindre tid slösas på vad som konkret saknar betydelse vilket man helt säkert ska vara mer observant på när det gäller universitet.

Dock skulle man se att området tycks leverera i en hastighet där det vore möjligt hinna prestera mer övergripande kommersiellt där det är oavsett värde är lätt tappa allt värde trots stora investeringar om man inte är snabb är det vettigt att investera mer verkliga pengar för att skapa något.

Vad som dock är obegripligt för mig här är varför EU har verksamhet där de delar ut småsummor. Rimligen kostar det ordentligt i allmän infrastruktur. I EU finns 500 miljoner innevånare. Det tycks vettigt att de fokuserar sådant här på stora mer gemensamma projekt. Projekt på den här storleksordningen kan rimligen enskilda länder hantera själva.