Numb3rs

Der var Venn-diagrammer, “Syndromic surveillance”, en “sexual networking model” og mere om Higgs bosonen, som Larry skal med i jagten på. (Se tidligere indlæg)

Venn diagrammer
Et venndiagram (opkaldt efter logikeren John Venn, 1834-1923), er en skematisk repræsentation af mængder som områder i planen

Billedet er fra MathWorld. Jeg ved ikke, hvorfor det bliver sort her – der er hvid baggrund i det oprindelige; men I kender jo nok godt den slags diagrammer. Man kan se områder, der er med i en af mængderne, i fællesmængden af to og inde i midten er fællesmængden af alle tre. Et godt spørgsmål er, om man kan lave et tilsvarende diagram med 4 mængder og alle deres mulige fællesmængder.
Herunder er diagrammer for 5, 7 og 11 (fra Mathworld, som har dem fra Ruskey, F.; Savage, C. D.; and Wagon, S. “The Search for Simple Symmetric Venn Diagrams.” Notices Amer. Math. Soc. 53, 1304-1311, 2006.

Det er slet ikke klart, at man kan producere diagrammer med mere end tre mængder og alle de mulige fællesmængder. Især, hvis man vil have dem symmetriske, som dem ovenfor. Et Venn diagram for n mængder, som er rotationssymmetrisk som ovenfor (randkurven for en af mængderne kan roteres en vinkel på (360/n) grader, og, ved gentagen rotation, give randkurver for alle de andre), findes hvis og kun hvis n er et primtal (vist i 2004 af Griggs, Killian og Savage.) Her kan man se, hvordan de 5 mængder og deres fællesmængder er repræsenteret i “blomsten” ovenfor:

I anvendelser kan en grafisk repræsentation være meget effektiv – se f.eks. dette diagram over aminosyrer grupperet efter deres egenskaber:

Fra denne beskrivelse af aminosyrers egenskaber. Det er ikke et Venn diagram, da ikke alle fællesmængder er repræsenteret – kun dem, der faktisk optræder, i.e., som ikke er tomme.
Det fascinerende ved Venn diagrammer fra et matematiker synspunkt er ikke så meget, at de repræsenterer mængder og fællesmængder, men at man kan se dem fra mange andre synsvinkler: geometrisk – symmetriegenskaber m.v.
kombinatorisk – i branchen grafteori.

Her er tre repræsentationer af tre mængder A,B,C og deres fællesmængder. (fra Frank Ruskey and Mark Weston, A survey of Venn diagramsElectronic Journal of Combinatorics.
Som Venn diagram, som en graf – kanten af Venn diagrammet med knuder i grafen der, hvor kurverne skærer.
Det sidste er den duale graf. Der er en knude for hvert område i venndiagrammet – de tre lyseblå punkter skal betragtes som et punkt, nemlig det om råde, der ikke er i nogen af de tre mængder (komplementærmængden).
Gør man det, får man en terning. Hjørnerne (knuder i grafen) skal navngives, så man kan se, hvilket område de repræsenterer. Hvis (000) betyder, ikke i A, ikke i B og ikke i C. (100) betyder i A ,men ikke i hverken B eller C, etc. Så får det lyseblå hjørne nummer (000), det i fællesmængden af alle tre er (111) og de andre er så 100,010,001,110, 101,011. der er kanter mellem to hjørner, hvis de kun er forskellige i en koordinat eks. fra 100 er der kanter til 110, til 101, til 000 og ikke andre.

Syndromic Surveillance
Man overvåger data fra apoteker, læger og hospitaler for at kunne forudsige, at en epidemi er på vej. Og i øvrigt også for at afsløre biologisk terror, inden det har forårsaget for megen skade. Se fo eksempel USA’s Center for Disease Control and prevention (CDC)
Kunsten er at opdage problemerne, men at undgå for mange gange falsk alarm – så der er statistik og risikovurdering involveret: Med disse data, hvor sandsynligt er det så, at der er et problem? Hvis der er et problem, hvor alvorligt er det så (sandsynligvis)? Hvor dyrt vil det være at sætte massivt ind nu i stedet for at vente og håbe, det ikke var et problem?

man kan finde eksempler her (USA)
Og ellers kan man jo tænke på svineinfluenzaen. Den slags overvåges i danmark af Sundhedsstyrelsen. Her om svineinfluenza.

Charlie bruger den slags data til at finde den modstandsdygtige type gonorre og dermed kvinder, der er blevet voldtaget.

Jeg spottede en analyse at trafikken (det, Charlie sagde til journalisten, de ville bruge, men som de nu vist ikke brugte). Der var assymmetrisk trusselsvurdering. Og noget om ejendomsvurderinger og hvordan de afhænger af vurderingen af nabohusene.

Asymmetrisk trusselsvurdering
Når en stat trues af en meget svagere modstander, som f.eks. en eller flere terrororganisationer, er det en asymmetrisk trussel. Og der er selvsagt en del asymmetrisk trusselsvurdering for tiden.
her er en artikel om ATAT, Asymmetric Threat Assessment Tool. Man forsøger at modellere effekten af forskellige manøvrer i Somalia, Afghanistan eller Irak. Hvor pointen er, at der er både primær effekter a la folk der bliver skudt. Og sekundære effekter af mere psykologisk karakter – “heart an mind”. Basalt set, at ellers venligt indstillede personer med tiden skifter mening, hvis de hører om eller måske selv ser, at civile bliver skudt.
Modellerne er ganske indviklede- man bygger en slag modelsamfund og simulerer visse begivenheder. Man regner altså ikke et facit i en lang formel, men har en hel stribe individuelle aktører, som man har givet visse karakteristika, så de med en vis sandsynlighed fortæller andre, hvad de har set, med en vis sandsynlighed bliver ophidsede, … og så lader man programmet rulle og ser, hvad effekten er ved at køre en divsion igennem centrum af en stor by (eksempelvis.)

Charlie sagde noget i den retning – noget med, at nogen personer fik nok – det var ballonerne, der sprang.

Ejendomsvurdering
Charlie sagde noget om et halvautonomt system, og det kan jeg altså ikke se, hvad han mente med. Men pointen var vist, at ejendomsvurdering i et område er en blanding af noget individuelt og noget fælles. Og den grumme entreprenør havde fået alle de ejendomme, han ville købe sat til en lavere værdi end naboejendommene, og det er mistænkeligt.

Egress path og traffic flow
Det kan være mange ting. Både analyse af trafik på vejene og af trafikken i et netværk af en slags, altså trafik i mere overført betydning. En egress path er en “udvej”.

I får ikke mere idag – men skriv endelig, hvis I kan bidrage til at opklare noget af ovenstående.

I USA sender de Numb3rs episode nummer 100 1.maj.
Det blev fejret, da de indspillede det – se her. (Videoen er der ikke mere – ser jeg nu januar 2015)

https://youtu.be/iGdjY4j1i9Q (ikke tilgængelig)

Charlie var lige en tand for filosofisk efter min smag idag! Han nævnte elevatorparadokset, Turing test, det kinesiske værelse (eller den kinesiske æske?), Cluster analyse, Invers geometri og (igen) noget spilteori (chomp). Der var en hel del matematik i anvendelse f.eks. bag “varmesignaturbillederne”, men det blev ikke bragt op.
Cluster analyse
I denne sammenhæng drejede det sig om at skille “varmebilledet” af David fra det af hans kidnapper, Blakely. Illustrationen var en fiskestime, hvor man skulle skille en slags fisk fra en anden, og på Mathworld mener de, algoritmen er “fuzzy c-means”.
Cluster analyse optræder i mange sammenhænge og mange variationer. Overordnet drejer det sig om at dele sine data op i ensartede grupper – samle de fisk, der har røde striber i en gruppe og dem med grønne striber i en anden – og data i forskellige grupper skal ikke ligne hinanden for meget. Det skal gøres af en computer; så man ønsker en algoritme, der kan gøre det. Og den skal selv kunne finde ud af, at det faktisk er grønne og røde striber, der er karakteristisk.
Hvert datapunkt har en vektor af karakteristika: (x1,x2,x3,x4,…,x17). Det kan være placering i rummet, farve, striber, volumen,… Og man har et afstandsmål – fra en fisk med to grønne og to røde striber til en med en grøn og tre røde er der måske lige så langt som fra “tre grønne og en rød” til “to grønne og to røde”. Og det afhænger nok af rækkefølgen af striberne. Den samlede afstand tager alle koordinaterne med i betragtning.
I Fuzzy c-means algoritmen (FCM), kan et datapunkt tilhøre flere grupper (en fisk har måske grønne og røde striber) og “fuzzy” elementet ligger desuden i, at det kan tilhøre den ene gruppe mere end den anden – måske er der kun en enkelt grøn stribe, men mange røde.
Har man kun en koordinat (f.eks.antallet af striber ), kan man repræsentere data på en linie, og grupperingerne handler om, at man kan samle dem i “klumper” efter, om de ligger tæt på hinanden.

Figuren, som er fra den applet, jeg henviser til nedenfor, viser 20 punkter delt i 3 grupper. De fede lodrette linier indikerer centret i hver af grupperne, og punkterne er farvet efter, hvilken gruppe, de hører mest til. Kurverne med hhv. grønt, blåt og magenta areal, er en beskrivelse af i hvor høj grad, et punkt ligger i den ene eller den anden gruppe. Bemærk, at den samlede vægt for hvert punkt er et fast tal. Man kan f.eks. have vægt 1 blå eller (1/4 grøn +1/4 magenta+1/2 blå), men altid ialt 1.

Der er en applet, man kan lege med, her. Man kan vælge antal punkter, antal grupper (clusters), fuzzyness, som er noget med, hvor vægelsindet man kan være – hvor meget kan et punkt tillades at høre til flere grupper Hvis fuzzyness er 1, kan hvert punkt kun ligge i en gruppe. For voksende fuzzyness kan de være i flere og flere. Desuden vælges en nøjagtighed, som siger, hvornår algorimen skal stoppe.

Algoritmen skal optimere en funktion, som måler hvor god en gruppering, vi har. Altså hvor meget elementer i samme grupper ligner hinanden, og hvor meget elementer, der ikke er i gruppe, afviger fra hinanden.

Fuzzy c-means bruges i mønstergenkendelse, i billedanalyse – det kan være medicinsk: hvad er blodkar og hvad er muskelvæv, i marketing: klassificer forbruger efter adfærd, i analyse af forsikringskunder med høj risiko/lav risiko. I bioinformatik til klassifikation af gener Og sikkert meget mere.

Om det kan bruges til det, Charlie ville, ved jeg ikke. Men det er da billedanalyse, så mon ikke.

Chomp
Chomp er et spil for to. Man har et rektangel, af en eller anden grund tænker man her på en plade chokolade, med n felter på den ene led og m på den anden. Det øverste venstre hjørne erklæres “giftigt”. Man kan brække stykker af ved at tage et felt og alt, hvad der ligger nedenfor og til højre for dette.Den, der tager det giftige stykke har tabt.
Eksempel:

Billeder fra Cornell’s side om Numb3rs

Man kan spille det her.
Man kan vise, at den, der starter, altid kan vinde. Men man kan ikke give en generel vindende strategi.
Turing test og kinesisk værelse
Man diskuterer, om det er muligt at skabe kunstig intelligens, og hvordan man ville kunne se, at man havde en intelligent computer. Turing testen (beskrevet af Alan Turing i 1950 i artiklen Computing Machinery and Intelligence) drejer sig om, at en “dommer” “konverserer” (skriver spørgsmål til ) computeren og et menneske og ikke udfra svarene kan se, hvem der er mennesket.
Endnu har der ikke været nogen computerprogrammer, der har været i nærheden af at bestå Turing testen. Der er en pris, Loebner prisen, for det program, der kommer tættest på – se vinderne her. Man kan også læse udkrifter af konversationen under Turingtesten.

Det kinesiske værelse er et argument for, at man ikke kan lave kunstig inteligens. Se f.eks. Stanford Encyclopedia of philosophy eller Den Store Danske Encyklopædi.

OBS. Dette er om afsnittet i aften, så læs nu ikke forud…Jeg poster nu for at holde lidt påskeferie.
Charlie brugte fraktal dimension til at gennemskue, at visse tegneseriealbums var forfalskninger. Og han brugte en anden type billedanalyse (eller muligvis var det også fraktal dimension – det fik jeg ikke fat i) til at se, at det var samme person, der havde forfalsket dem.
Han brugte også auktionsteori til at gennemskue, hvornår det rigtige album kom – men det var nu lidt overkill, skulle jeg mene. Det kunne man nok godt have gennemskuet uden…
For de modebevidste, der vil have en T-shirt som den, Charlie har på, da han går rundt og ser på tegneserier, kan den faktisk købes hos Mathworld. Se her. Prisen er 8 engelske pund plus moms. Vil man have Charlies frisure, skal man nok gøre noget helt særligt.

Fraktal dimension
Teknikken, der omtales, stammer fra Sung-Hyuk Cha, Charles C. Tappert, Michael Gibbons, and Yi-Min Chee, Automatic Detection of Handwriting Forgery using a Fractal Number Estimate of Wrinkliness, Int. J. Pattern Recognition and Artificial Intelligence, 2004.
Den handler om at genkende forfalskede underskrifter.

Man så formlen

Wrinkliness= log (high_resolution/low_resolution)/log(2)

Ideen bag er, at man bruger længere tid på at “tegne af”, altså efterligne en håndskrift, end på at skrive frit. Så den streg, man laver, når man forfalsker, vil have små bitte “rystelser”, som man kan se, når man forstørrer den op.

Den fraktale dimension skal fungere som et mål for, hvor “rynket” stregen er. Dens “wrinkliness”.

En pæn glat “urynket” kurve kan tilnærmes med en stykvist lineær kurve:

Jo flere knæk man tillader, eller jo kortere linjestykker – det er det samme for en pæn glat kurve, men vi skal se nedenfor, at det ikke altid er rigtigt- jo bedre tilnærmes kurven. Man kan finde længden af den “pæne” kurve ved at tage længden af de stykvis lineære tilnærmelser og se, hvad dette tal nærmer sig nå man tillader flere og flere delepunkter. Hvis det nærmer sig et tal, er dette tal længden af kurven. For en cirkel kan man tænke på at nærme sig med polygoner med flere og flere kanter. En ligesidet n-kant, hvis hjørner ligger på en cirkel med radius r, har sidelængde 2r sin(pi/n), og altså omkreds 2n rsin(pi/n). Tænker man i stedet på at tilnærme med polygoner “udefra”, så er sidelængden i en omskreven n-kant 2r tan(pi/n) og altså er den samlede længde 2nr tan(pi/n)

Tegningen her (fra MathWorld) viser en femkant indskrevet i en cirkel med radius R og omskrevet en med radius r. Man har altså omkredsen af en cirkel klemt

2nr sin(pi/n) < omkredsen < 2nr tan(pi/n)

Man argumenterer nu for, at 2n sin(pi/n) vokser med n, mens 2nr tan(pi/n) aftager, og at de nærmer sig hinanden.

MEN det virker ikke altid – det er ikke alle kurver, der har en længde – hvis man bruger kortere og kortere stykker i polygonen, der skal tilnærme, bliver den samlede længde ustyrlig:

Her er nogle skridt i konstruktionen af Von Kochs snefnug. En fraktal kurve konstrueret af Helge Von Koch i 1904 – længe før fraktaler blev et hit. Billedet er fra Mathworld.

Kurven “knækker hele tiden”. Hvis man forstørrer et stykke af den op, ser det hele tiden kvalitativt ens ud. Forsøger man at måle den ved at bruge kortere og kortere linjestykker, vil man skulle ind i flere og flere af knækkene, så det løber løbsk:

Her er en lille del af snefnugget. Start med et linjestykke, der er L langt. Del i tre lige store dele og lav en ligesidet trekant på midterstykket. Hvert af de 4 stykker på den knækkede kurve er nu L/3. Lav samme manøvre på hvert af de 4 stykker og få en kurve af 16 stykker hver med længde L/9. Og så fremdeles.

Den kurve, der fremkommer, ser lidt “ulden” ud, og når man kigger nærmere paa den, kan man se knækkene – flere og flere, jo tættere, man går på. Og det ser hele tiden ens ud- lige meget,hvor meget man forstørrer. Det er det, der karakteriserer en fraktal.

Den fraktale dimension af Von Koch fraktalen er ln(4)/ln(3)=1,262… Det er altså ikke et helt tal!!!
Den fremkommer sådan: Hvis man gør målestokken 3 gange finere (tillader at liniestykkerne er 1/3 så lange som før), er der 4 gange så mange knæk/”stykker” i den approksimerende kurve.
For en pæn glat kurve vil man få dobbelt så mange kanter i den approksimerende kurve, hvis man lader stykkerne blive halvt så lange. Altså får man fraktal dimension 1.

En glimrende dansk side findes på Nørre Gymnasium: Fraktaler og Kaos af Torsten Meyer. Der kan man også se udregning af den fraktale dimension af Englands kystlinie. Kystlinjers fraktale dimension afhænger af, hvordan de er dannet – noget med istider og sådan…

I den algoritme, Charlie bruger, tager man to digitale billeder (med en sædvanlig scanner) af den “streg” S, man vil undersøge. Antallet af pixels i billede 2 er 4 gange så højt som i billede 1 (pixels ser “halvt så store” ud – på begge leder).
rynketheden er
log(“antal pixels langs randen af S i billede 2″/”antal pixels langs randen af S i billede 1”)/log(2)

(log er her den naturlige logaritme). Det er sådan set ikke en fraktal, så det er heller ikke fraktal dimension, men ideen er den samme; man bruger bare kun et enkelt skridt med at “zoome ind”

I artiklen påstås, at man kan gennemskue forfalskninger ved metoden; at de er mere rynkede end de virkelige. Men det gælder kun gode forfalskede underskrifter. Hvis man ikke gør sig umage, skriver man hurtigt, og det rynker ikke så meget….

At kystlinier bliver længere, hvis man måler den med en kortere målestok kaldes Richardson effekten, da det er en observation, der skyldes Lewis Fry Richardson, engelsk matematiker, fysiker, psykolog, pacifist m.v.

Titlen på dette afsnit, Tabu, henviser bl.a. til den matematiske metode, Charlie omtaler som Tabusøgning (Tabu search). Desuden var der henvisninger til spilteori: minimax principper, spil med ufuldstændig information. Og (igen) noget om beslutninger og analyse af taktik udfra beslutnings analyse (da Charlie blev inspireret af en analogi med en sommerfugl).
Der var noget data, der blev vægtet med en Bayesiansk prior.
Der var noget fysik – her kan man se, hvordan man bygger Herons fontæne/springvand og her er en anden konstruktion, hvor de fysiske principper bag forklares. Der var meget mere fysik – Larry siger meget om analogier mellem Megans problemer og diverse fysik, men det lader jeg ligge.

Tabusøgning
Vil man læse rigtig meget om emnet, er bogen Tabu Search af Fred Glover og Manuel Laguna en ret omfattende kilde. Glover er, så vidt jeg kan finde ud af, ophavsmanden til Tabusøgning. En kortere kilde er A tutorial on Tabu search, Hertz, de Werra og Taillard.
En tabusøgning skal generelt løse et optimeringsproblem ved at søge struktureret iblandt mulige løsninger. Optimering kan i denne sammenhæng være

• find et skema, for en folkeskole for næste skoleår, hvor de små klasser ikke har mellemtimer, lærerne ikke skal stå i to klasseværelser på en gang, ingen klasser er i samme klasseværelse samtidigt, store klasser (og lærere)har få mellemtimer, klasserne har timerne nogenlunde jævnt fordelt over ugen etc.
• Planlæg valgfag for et gymnasium. Skemaerne skal passe, alle elever skal have passende antal valgfag etc. (Så vidt jeg kan se af denne artikel fra LMFK-bladet, bruger Lectio Tabusøgning til denne opgave. Det baseres på et speciale fra DTU)
• planlæg flytider/ruter for et flyselskab
• lav en rute for et handelsrejsende, der skal besøge byerne A,B,C,….,Y, som er kortest mulig, og hvor man ikke kommer tilbage til nogen af byerne. Man kender afstandene mellem hvert par af byer. Problemet kaldes Travelling Salesman Problem og er et klassisk grafteoretisk optimeringsproblem. Det er NP-fuldstændigt.
• “Classical Vehicle Routing Problem”, CVRP: Man har et antal lastbiler, som skal bringe varer ud fra et depot. Man kender kunderne og deres behov – hvor meget skal de bruge og hvor lang tid tager det at servicere dem (der skal læsses af, og måske skal der installeres noget). Lastbilerne har en maksimum kapacitet Q. Afstanden mellem kunderne parvis og mellem depotet er karakteriseret ved dels en omkostning (broafgifter, benzinforbrug,…) og et tidsforbrug. Opgaven er nu at finde ruter, så
  • hver rute begynder og slutter ved depotet
  • Hver kunde besøges præcis en gang
  • Det samlede leverance på en rute er mindre end Q
  • Den samlede varighed af hver rute (transporttid plus tid hos hver kunde) er ikke større end et fastsat maksimum (8 timer måske)
  • Den totale omkostning er mindst mulig

Problemerne kan i en vis forstand overskues; man kan karakterisere de mulige løsninger. Eksempelvis kan man for den handelsrejsende kigge på alle mulige ruter A,C,B,U,X,M,… altså alle de måder, man kan skrive byerne i rækkefølge på. Og så vælge den, der er kortest. Men der er alt for mange muligheder. Eller mere præcist: Tilføjer jeg blot en enkelt by, vokser antallet af mulige ruter meget hurtigt. Med tre byer er mulighederne med start i A ABC, ACB (man tager tilbage til A til sidst, men det skriver jeg ikke på listen). Med fire er der ABCD, ABDC, ADBC, ACBD, ACDB, ADCB (for hver af de to, jeg havde, får jeg tre nye, ved at placere D de tre mulige steder) Fra ruten ABCD kan jeg tilføje E som ABCDE, ABCED, ABECD, AEBCD, så jeg får fire nye for hver, jeg havde i forvejen. Antallet af ruter vokser som 1,2,6,24,120,720 … eksponentielt. Man er nødt til at være smartere.
Man kan forestille sig, at man leder igennem løsningsforslag ved at starte med en løsning, som (formentlig) ikke er optimal. Dernæst ser man på alle de løsninger, der ligger “tæt på” – som man kan få ved at ændre den, man har, en lille smule: Byt om på to af byerne på ruten for den handelsrejsende. Er der en af de nye, der er kortere, tager man den og kigger igen på dens “naboer” – man kan vælge at tage den første, man møder, der er kortere, eller at se  alle naboer igennem og vælge den korteste blandt naboerne. Det er nu fristende at tro, at man kan stoppe, når alle naboerne er længere – er dårligere løsninger, men man risikerer at snyde sig selv.

Optimeringsproblemer har ofte lokale maksima. Altså løsningsforslag, som er de bedste i forhold til naboerne, men som ikke er de bedste, hvis man sammenligner med alle andre. Man kan tænke på et landskab. Vi vil finde det højeste punkt ved at starte et sted og hele tiden gå opad. Står man på Himmelbjerget, er alt lige i nærheden lavere, men Mount Everest er jo højere.

Man skal altså kigge lidt længere end bare på naboerne. I en tabusøgning holder man styr på, hvor man allerede har været. Man vil forebygge, at man går i ring og går tilbage til steder, hvor man har været. Og helt fundamentalt skal man have fastlagt, hvad et nabolag overhovedet er.

Eksempelvis:

I CVRP har vi lavet et antal ruter, R1,…,R7 som opfylder betingelserne – kundernes samlede behov og tidsforbruget er ok for hver rute. Og alle kunder bliver besøgt en gang. Men vi vil jo have minimeret omkostningerne. Hvad er nu nabolaget for vores løsningsforslag- hvilke små modifikationer kan man lave på det løsningsforlag og få et nyt?

• Man kan flytte en kunde til et andet sted på samme rute eller til en anden rute, hvor der er ledig kapacitet (både tid og plads i lastbilen).
• Man kan bytte om på to kunder – fra to forskellige ruter (igen skal der være tid og plads)
• Man kan flytte en fra rute 1 til rute 2, en fra rute 2 til rute 3 og en fra rute 3 til rute 1

Der er mange muligheder.

Med nabolagsstrukturen fastlagt skal man bestemme en tabustruktur. Husk, ideen er, at man skal kunne komme væk fra et lokalt maksimum ved at gå lidt “ned ad bakke”. Og undgå at gå i ring.

Bemærk, at man måske har været i nærheden af Mount Everest og har valgt at gå op mod K2, fordi der umiddelbart så stejlest ud. Så man skal altså muligvis passere steder, hvor man har været. En tabustruktur forhindrer, at man går i små cirkler, men ikke store. Man husker lidt af fortiden, men ikke det hele.

For CVRP kunne man forbyde (erklære det for tabu) at flytte en kunde k1, der lige er flyttet fra R1 til R2, tilbage igen (i hukommelsen skal man have k1,R1,R2),. Et lidt stærkere tabu vil være at fobyde at flytte k1 tilbage til R1 overhovedet (man husker (k1,R1)) Eller endnu stærkere: Man forbyder at flytte k1 igen (hukommelsen har k1).

Man beholder sine tabuer et vist stykke tid – det er også en parameter i tabusøgningsalgoritmen.

Man husker naturligvis hele tiden

• den hidtil bedste løsning.
• Hvor god den er (i CVRP er det dens omkostninger),
• den løsning, vi lige nu ser på og hvor god den er
• dens nabolag
• dens tilladte nabolag – dem, der ikke er tabu.

For at undgå, at tabuerne spænder ben for en måske virkelig god løsning, vil man normalt kigge dem, der er tabuiseret i nabolaget igennem. Og hvis en af disse er bedre end den hidtil bedste løsning, tager man den med – husk, ideen er at gå nedad for at kunne gå endnu højere op senere.

CVRP og tilsvarende problemer er væsentlige, da computere med flere processorer vil distribuere opgaver til de forskellige processorer, og det er netop et problem af den type. Og det skal løses effektivt af en computer.

Spilteori:

Det er et stort emne, og vi har haft det på bloggen tidligere – om kageudskæring, Tit for Tat og fangernes dilemma, Cooperative Gametheory og Multiplayer og Mere overordnet om spilteoretiske problemer
Denne gang omtalte Charlie minimax strategier. Det er strategier, hvor man forsøger at minimere det maksimale tab, man kan have. En lidt pessimistisk strategi, hvor man hele tiden har øje for, hvor galt det kan gå.
Charlie nævner også spil med ufuldstændig information. I kryds og bolle og i skak har man fuld information – man kender modstanderens mulige træk. I poker har man ufuldstændig information – modstanderen har kort på hånden, som man ikke kender.
Man kan opdele spil efter, om spillerne har fuldstændig modstridende interesser – f.eks. hvis der er en samlet pulje, der skal deles. Eller spil, hvor det kan være gavnligt at samarbejde – f.eks. i fredsforhandlinger.
Der står rigtig meget om spilteori på Encyclopedia Britannica. Der er mange fine figurer om flere af de problemer, jeg har omtalt tidligere på bloggen.

Idag klokken 12 meddelte Abelpriskommiteen, at “matematikkens Nobelpris” går til Mikhail Gromov. Her er Abelprisens hjemmeside. Det er syvende gang Abelprisen uddeles, og der gives hver gang gode forklaringer på prismodtagernes arbejde – også om Gromov. Det kan I finde her. Vagn Lundsgaard fra DTU fik i år opgaven med at introducere prismodtagerens arbejde, og det synes jeg, han har gjort rigtig godt, som man ser her (lige nu er der en tegning, hvor der er byttet om på en kugleflade og en cylinder – jeg har skrevet det til nordmændene, så det bliver nok rettet…).

Det handlede om virtuelle verdener og rollespil – men med opgaver, der skal udføres i den virkelige verden; et forholdsvis nyligt eksempel på sådan et spil blev lanceret op til premieren på Batman, the dark knight. Spillet hed “Why so serious”, men man kan vist ikke spille det mere, for opgaverne IRL er løst. Der er (selvfølgelig) matematik i den slags spil- underliggende algoritmer, grafik etc., men den matematik, Charlie brugte , var evolutionære algoritmer, som han brugte til at finde en særlig aggressiv gruppe i spillet. Og Amita nævnte kombinatorisk matrix teori.

I øvrigt findes det spil, skurken ville sætte i værk, chain factor, allerede her. Muligvis som en slags henvisning til Numb3rs; det kan jeg ikke rigtig gennemskue – men jeg har nu heller ikke spillet det.
Desuden var Larry på jagt efter Higgs bosonen, og jeg kan i den forbindelse ikke modstå fristelsen til at henvise til min søsters udmærkede beskrivelse En boson er ikke et blæseinstrument og i øvrigt også Nedtælling til Big Bang 2.0 begge skrevet i forbindelse med forsøget på CERN, som nu er sat i bero, indtil de har repareret acceleratoren.

Hans Hüttel har skrevet et glimrende indlæg om evolutionære algoritmer, så det slipper jeg for at rode mig ud i. Jeg vil i stedet kaste mig ud i kombinatorisk matrixteori, som Amita åbenbart underviser i.

En matrix er simpelthen en organisation af tal i et rektangel. en slas tabel- f.eks. er en Sudoku en matrix med 9 rækker og 9 søjler, en 9×9 matrix. Hver af de 81 tal er en indgang i matricen. En 5×7 matrix har 5 rækker og 7 søjler.
Matricer kan lægges sammen, hvis de har lige mange søjler og rækker. Man lægger matchende indgange sammen. De kan ganges sammen – se f.eks. en lang, men instruktiv video på på you tube (denne er på engelsk), men de findes såmænd også på tysk:

I videoen ganges en 2×2 matrix A med en 2×3 matrix B, og man får en 2×3. Man beregner f.eks.  den indgang i produktet, der er i række 2 og søjle 3, ved at “gange” række 2 fra A med søjle 3 fra B – efter opskriften ( 7  -2) (8  5)= 7×8 + (-2)x5=46.

Man har altså en struktur på matricer – de kan adderes og multipliceres.

Det er imponerende effektivt at organisere problemer via matricer.

I lineær algebra repræsenterer en matrix med  2 rækker og 3 søjler sommetider 2 ligninger med 3 ubekendte:

5x+7y+z=0

3x+2y-z=0

organiseres i en 2×3 matrix med første række (5  7  1) anden række (3  2  -1)

Men samme matrix kan også repræsentere en “lineær afbildning”. Nemlig den afbildning, der sender (x,y,z) over i (5x+7y+z, 3x+2y-z)

Matrixmultiplikation er så sammensætning af lineære afbildninger.

I kombinatorisk matrixteori kan en matrix  f.eks. repræsentere en graf, som jeg beskrev det under afsnittet Protest

Den struktur man har på matricer – multiplikation m.v.- giver så struktur på graferne, og man kan dermed håndtere grafteoretiske problemer fra en mere algebraisk sysnvinkel. Mere struktur giver mere værktøj.

I aftenens afsnit forekommer der evolutionære algoritmer. Opgaven er at finde abnorm opførsel i et online computerspil á la World of Warcraft.

Evolutionære algoritmer kalder man de typer algoritmer, der finder frem til et resultat ved brug af metoder, der er baseret på principperne bag biologisk evolution, nemlig

– Rekombinering og mutation, der skaber mangfoldighed inden for en population af individer, og

– Udvælgelsen af de “bedst egnede” individer

Den grundlæggende observation bag evolutionære algoritmer er, at naturen har kunnet løse rigtig mange problemer og frembringe meget avancerede organismer ved brug af disse simple principper. Derfor må man også kunne bruge en tilsvarende tilgang, når man vil løse et svært problem ved brug af en algoritme.

Der er mange forskellige tilgange til evolutionære algoritmer. Den, jeg vil beskrive her, kaldes genetiske algoritmer, og jeg vil tage udgangspunkt i et eksempel, der på samme tid er let at forklare og formodentlig svært at løse, nemlig rygsækproblemet.

Rygsækproblemet er dette:

Givet en øvre grænse MAX og en mængde af n naturlige tal c_1,…,c_n, hvordan kan vi da vælge en delmængde af disse tal, således at deres sum er mindre end MAX og så forskellen MAX – S er minimal?

Tænk på problemet som et problem om at pakke en rygsæk, der kan rumme MAX liter med ejendele med rumfang c_1,…,c_n således at rygsækken bliver så fyldt som overhovedet muligt.

Rygsækproblemet er det, man kalder optimeringsversionen af det tilsvarende beslutningsproblem:

Givet en øvre grænse MAX, en forskelsværdi K (der er et naturligt tal) og en mængde af n naturlige tal c_1,…,c_n, kan vi da vælge en delmængde af disse tal, deres sum er mindre end MAX og så forskellen MAX – S er mindre end eller lig K?

Dette beslutningsproblem er NP-fuldstændigt, og vi har talt om denne slags problemer før her på bloggen. Hvis et beslutningsproblem er NP-fuldstændigt gælder det, at ingen kender en hurtig algoritme der altid kan give det korrekte svar for vilkårlige instanser af problemet. Af denne grund kan der derfor heller ikke være en hurtig algoritme, der kan beregne en løsning for optimeringsversionen af problemet. Hvis man vil have en hurtig algoritme, må man give køb på at være sikker på at finde en optimal løsning – og her er netop en evolutionær algoritme et godt bud.

Her er et eksempel på en evolutionær algoritme (af den slags, man kalder en genetisk algoritme) til at beregne en løsning på rygsækproblemet.

Ideen er vi repræsenterer et bud på en løsning som en streng af k bits, dvs. en streng af 0’er og 1’er. Hvis tallet c_i er med i mængden, skal der være et 1 på position nr. i i strengen, ellers skal der være et 0.

Lad os som eksempel antage, at vi har de 4 c-værdier 3,4,9 og 12. Så svarer delmængden {4,9} til strengen  0110.

Der er et problem her, da strengens værdi kan blive > MAX. Så nogle strenge kan aldrig være bud på løsninger. Dette kan vi nemmest løse ved at beregne strengens “faktiske værdi” V(S) på denne måde:

Vi læser positionerne i strengen S fra venstre, så længe den samlede værdi af de læste bits er højst MAX. Herefter skal evt. følgende bits ignoreres.

Fitness af en streng S kan vi nu definere som F(S) = MAX – V(S). Hvis M er en mængde af strenge, er FV(M) den højeste fitness-værdi for strengene i M.

Algoritmen udvælger en mængde af K startstrenge og gennemløber derefter en løkke indtil populationens fitness er stabil. Lad os sige at dette kræver 25 generationer, og at der er 500 startstrenge. Så ser algoritmen således ud:

1. Lav 500 start-strenge.

2. Gentag følgende

– Skab en ny generation M’

– Beregn FV(M’)

3. Indtil FV(M’) ikke har ændret sig i 25 generationer

Nu skal vi bare have defineret, hvordan man skaber en ny generation.

Vi skaber en ny generation fra M på denne måde:

– Inddel generationen i forældrepar ved en turnering.

– Hvert forældrepar får 2 afkom ved rekombinering og mutation.

– Mængden af disse afkom udgør den nye generation.

“Forældre-turneringen” kan f.eks. foretages ved en udvælgelse uden tilbagelægning: Vi vælger en tilfældig mængde af 4 strenge og lade et nhyt forældrepar være de to strenge hvis V(S) er størst.

En enkel form for rekombinering er overkrydsning. Overkrydsning finder sted med en på forhånd fastlagt sandsynlighed; lad os her sige at denne sandsynlighed er 70%.

Vi tager to bitstrenge. Herefter vælger vi et tilfældigt tal x mellem 0 og 1. Hvis x > 0,7 beholder vi de to bitstrenge som de er. Ellers vælger vi en vilkårlig position og bytter de to strenges indhold efter denne position. Hvis positionen er 4 og vi har strengene

0001110101

1010100010

får vi således de nye strenge

0001100010

1010110101

En enkel form for mutation er at ændre en tilfældig bit i strengen. Mutation finder også sted med en på forhånd fastlagt sandsynlighed; lad os her sige at denne sandsynlighed er 5%.

Her tager vi én bitstreng. Herefter vælger vi et tilfældigt tal x mellem 0 og 1. Hvis x < 0,95 beholder vi strengen som den er. Ellers vælger vi en vilkårlig position og ændrer den bit, der er på positionen. Hvis positionen er 6 og vi har strengen

0001110101

får vi

0001100101

Vores evolutionære algoritme er derfor en systematisk prøven-sig-frem. Af denne grund er der heller ingen garanti for at den finder den optimale løsning, endsige at den finder en god løsning. Hvis vores startstrenge er valgt uhensigtsmæssigt, er der nemlig en lille (omend meget lille) sandsynlighed for at vi efter 25 gennemløb stadig vil have de strenge, der var vores start-strenge.

Charlie analyserede en tegning, som havde en skjult besked. Matematikken bag var, ifølge Charlie, morfologisk “billedrensning” (morphological image cleaning). Han lavede en CART analyse (Classification and Regression Tree) af et beslutningstræ for at se, om det var sandsynligt, at det var Don, der ledte morderen på sporet. Det blev også brugt til at forbinde to af personerne – McGurn og Gibbs.

Og så var der et flot billede på Charlies nyudkomne bog. Det var et icosidodekaeder:

(den havde spidser stikkende ud fra alle sideflader – på engelsk kaldes det en “stellated icosidodecahedron”) Her er den:

Det er den, der blev brugt i serien, og den er lavet på en 3D printer, siger de hos MathWorld, og de ved det, for det er dem, der har lavet den….
CART-analyse

Classification And Regression Trees, CART, er en del af branchen datamining. Det er en bestemt algoritme, lavet af Breiman, Friedman, Olshen og Stone i 1986.Bogen fås på Amazon. Eksemplet hos Breiman et. al. er, om man kan forudse forløbet for hjertepatienter udfra de tal, man måler. Kan man for nye patienter forudsige noget udfra, hvad man ved, om de patienter, man allerede har set.
Her er et træ vedr. hjertepatienter:

CART er en metode til bygning af et beslutningsstøttetræ. Strukturen i et træ er, at man har en stribe spørgsmål/tests med to mulige udfald (ja/nej). Man starter altid samme sted – et indgangsspørgsmål. Ja leder en til nye spørgsmål, mens nej leder til nogen andre. Med de data man har, løber man ned gennem træet (træer står på hovedet i den slags analyser…) og følger forgreningerne. Man ender yderst i et blad, hvor man i eksemplet her kan aflæse, om der er stor, eller lille risiko for, at patienten dør. I mere avancerede modeller kan man også knytte en sandsynlighed til svarene – hvor sandsynligt er udfaldet ja, og hvor sandsynligt er nej. Det gør, at man kan regne baglæns: Hvis udfaldet er, at patienten døde, hvad er så de sandsynlige årsager – hvor ville man have kunnet forudse det? (Det må være det, Charlie vil – forudse, om Dons handlinger var årsag).

Man har metoder, som udfra en stor datamængde laver den slags træer, så man kan lære af de data, man allerede har, når der kommer en ny patient/et nyt firma udsteder aktier etc.

Et lidt mere indviklet træ fra Pouls Svante Eriksens kursus om netop CART for Produkt og Design psykologuddannelsen i Aalborg

Her er et par beslutningsstøttetræer fra Miljøstyrelsen. (Noget med pesticider i overfladevand)

Steganografi, Morfologisk billedrensning,

Vi har haft steganografi tidligere på bloggen, hvor hemmelige beskeder blev skjult i “unødvendige” bits i et billede. Denne gang var det en håndtegning, som gemte på en besked, og Charlie bruge en “billedrensnings” algoritme til at finde det, der var længere streger – thin features . Den type algoritme, han påstod at bruge, (Morphological Image Cleaning, MIC) fjerner “støj” fra et billede og bevarer skarpere elementer som f.eks. kanter. Om det virker, når man har lavet en tegning, der inkluderer den hemmelige besked, tvivler jeg på. En tegning er ikke støj.

Morfologi er studiet af struktur og facon. Det bruges meget generelt og mange forskellige steder, f.eks. om en proces, der udfra “rodede” problemer laver struktur, så man kan stille mere kvantitative spørgsmål og derefter forhåbentlig får disse stillet som “opgaver”, der kan angribes med matematik. Dette beskrives på Swedish Morphological Society, hvor man gennemgår forskellige eksempler. Et “rodet” spørgsmål kunne være “Hvad gør vi ved økonomisk kriminalitet?” (Eller bandekriminalitet, kunne man måske tilføje i disse dage).
Man skal have klargjort, hvilke problemer, der er, (skatteunddragelse, bestikkelse, bedrageri, konkurrenceforvridning, hvidvaskning…), metoder (regnskabssnyd, falske produkter (IT-factory), diverse finansielle fiksfakserier…), hvem går det ud over, motiver… Og hvad har man af midler? Der vil være sammenhænge – nogen midler virker mod noget; nogen ting kan ikke foregå samtidig etc. Man skal finde en konsistent strategi uden indre modstrid.
I analysen fastlægger man, hvilke variable, der indgår, hvilke værdier, disse kan have – det kan godt være “ja/nej”, der er muligheden, og hvilke der kan optræde samtidig.
En senere analyse kan gå på kausalitet – hvad kan forårsage hvad og med hvilke sandsynligheder.

At strukturere sådanne rodede problemer kaldes morfologi. Det går tilbage til F.Zwicky, som var ansat på CalTech. Han påstod selv, at han brugte metoden til mange af sine opdagelser i astronomi/astrofysik.

MIC-algoritmen – ( R.A. Peters, A new algorithm for image Noise Reduction Using mathematical Morphology, IEEE transactions on Image processing, 1995) er en kombination af flere billedbehandlingsalgoritmer.

Først finder man en “udglattet” version af billedet: Hver pixel forventes at ligne sine naboer. Man definerer først, hvad naboerne er f.eks.
De ialt fire pixels, der ligger lige oven for, neden for, til venstre eller til højre for
De 8 pixels, der foruden de fire fra før, er dem skråt op til højre, skråt ned til højre og tilsvarende til venstre
Eller mere indviklede nabolag – det kaldes “strukturerende elementer” og bestemmer, hvor udglattet, billedet bliver.

I en udglatning skifter man farve på en pixel efter en funktion af naboernes farve.

Det oprindelige billede kalder vi B, den udglattede version U. Differensen imellem de to (man kan trække pixelværdier fra hinanden) B-U indeholder nu dels støj og dels “kanterne” – en kantpixel ligner jo netop ikke sine naboer.

MIC algoritmen leder efter kanterne i B-U. Og tilføjer til sidst disse kanter til U. Den bruger information fra det oprindelige billede og fra “udglatningen” – f.eks. noget om forskellen på, om man glatter ud ved at lade en pixel have samme farve som sin lyseste nabo eller sin mørkeste nabo (så vidt jeg har forstået- det hedder open-close og close-open, hvis nogen vil vide mere).

I seneste nummer af Plus Magazine beskrives en anden type billedrensning/gendannelse, hvor man bruger partielle differentialligninger – varmeledningsligningen – til at ændre pixels i forhold til deres naboer: Restoring Profanity – om restaurering af nogle østrigske fresker.