januari 24, 2010

Eureqa: equation discovery med genetisk programmering

(For English readers: This blog post is available as a Google Translation from this Swedish text: Eureqa: equations discovery with genetic programming.)

För mer än 6 år sedan bloggade jag om equation discovery (att hitta ekvationer/samband givet en datamängd) och hittade några roliga system som jag då kollade in rätt mycket.

Nu är det dags igen: Eureqa är ett modernt equations discovery-system baserat på genetisk programming (närmare bestämt symbolisk regression) och det har ett fint GUI etc.

Eureqa blev världskänt i början av december förra året genom att Wired skrev en artikel om systemet och forskningen/forskarna bakom: Download Your Own Robot Scientist. Faktum är att jag laddade ner systemet och testade det lite men jag höll på på med andra saker.

De senaste dagarna har jag suttit med några enkla problem (dvs datafiler) för att lära känna Eureqa mer. Mer avancerade saker såsom dynamiska modeller (differentialekvationer) och komplexa ekonomiska system (såsom börskurser) tar jag tag i senare.

Jag tänker inte gå in på vad genetisk programmering är mer än att säga att det använder inspiration från biologin för att leta rätt på en lösning. Se vidare genetic programming (Wikipedia) för mer info och länkar.

Huvudprincipen för den variant av genetisk programmering som Eureqa använder är att man har
- en datamängd
- ett visst antal matematiska funktioner ("byggklossar")
- en relation mellan variabler som man vill studera

Eureqa hittar då givet variablerna och funktioner ett antal samband (lösningar, modeller). Med en "felfunktion" (error function) kommer diskrepansen mellan data och den skapade modellen att minska till ett så litet värde som möjligt, förhoppningsvis 0.

Här följer några kommentarer och ett och annat tips. Först beskrivs Eureqa, sedan lite mer om modelleringen med några exempel. Efter det länkar till några av de datafiler som används, och sist mer länkar om Eureqa.

Mycket kortfattat: Jag tycker Eureqa är ett riktigt trevlig och skoj system, tyvärr rätt mycket CPU-slukande för att min dator ska må riktigt bra. Men skoj.

Min vana trogen skapades även en My Eureqa page för länkar, filer och annat etc.

Installation

Programmet finns att ladda ner här.

Tyvärr finns endast en Windows-version men det ska komma klienter för åtminstone Linux. Jag har inga större svårigheter att köra Eureqa under Wine förutom att det alltså tar väldigt mycket kräm när det bearbetar data.

Det installerades på min burk med följande kommando:

wine msiexec /i eureqa_full_0.7.7.msi

och kör det sedan med

wine "<installation path in Wine>/Eureqa.exe"

Mer om systemet

Eureqa har ett mycket trevligt GUI med olika tabbar för data, plottning/smoothing av data, modellering, start/stop och lösning. Dessa tabbar presenteras här kortfattat.

* "Enter Data"
Man kan skriva in data som i ett enkelt spreadsheet ā la Open Office Calc eller Excel (vad jag vet stöds inte formler etc). Det sätt jag använder är dock att skapa en text fil (ASCII) som består av följande:
- header med information om fälten. T.ex.
% | x y z |
där "%" är kommentar och de två "|" är avgränsare för variabelnamnen. Tänk på att det bör vara relativt korta namn annars kan det bli svårläst med mer komplexa uttryck.
- sedan data med mellanslag som separator.

För att hämta in en datafil används "File", "Import data...". Om det är fel i filen kommer mer eller mindre lättförståeliga felmeddelanden. Jag har inte testat så mycket att manuellt lägga in data via kalkylprogram men det ska gå.


* "Preview Data" (och smoothing)
I detta fönster man man se de olika värdena plottade i en x/y-graf. Man kan även göra en smoothing (vad jag förstår är det loess man använder), t.ex. om det är mycket brus för någon variabel.

* "Pick Modeling Task"
Här gör man själva modellen, dvs skapar förutsättningen för uttrycket. Se även nedan under "Modellering, några exempel".

- Search for a formula: Här skriver man formen för uttrycket, t.ex.
x1 = f(x2,x3).

- Using building blocks: Här väljs de funktioner ("byggklossar" som man vill att Eureqa ska testa. Normal vill man alltid ha "+","-","*","/", men sedan beror det lite på vad det är för typ av data. Intressant nog är "sin" och "cos" alltid med, vilket väl speglar utvecklarnas preferens för fysiska system. Eftersom de flesta av mina datamändger inte är fysiska system brukar jag börja med att ta bort sin och cos och i stället välja t.ex. square root, exponential och logarithm, eller helt enkelt endast börja med de fyra räknesätten.

Det finns ett flertal andra byggstenar, t.ex. minimum, maximum, Logistic, Gaussian, Gamma, Step och Sign, man inverser och hyperboliska varianter av trigonometriska funktionerna. På forumet antyds att det kommer flera i nästa version, t.ex. de booleanska AND, OR, XOR, samt att man ska kunna definiera egna varianter.

Det finns även andra saker på denna sida, t.ex. att välja Fitness metric och viktningen av datapunkterna.

Det går också att använda flera datorer till en körning. I "Use the following servers" väljer man eventuellt andra datorer som kör en Eureqa server. Detta har jag inte testat.

"Seed previous solution(s)": Här kan man skriva uttryck (formler) som en vink ("bias" till Eureqa att dessa är viktiga formler. Detta har jag inte kollat in så mycket.

* "Start/stop"
Här startar, stoppar och pausar man en körning. Förutom dessa knappar finns en mängd annan information om hur körningen går.

* "Solution Results"
Det är här man ser lösningen både som ett uttryck och även en graf hur bra lösningen är jämfört med de givna datapunkterna. Det är fascinerande att se den växa fram och lära sig.

Datamängden delas upp (automatiskt av Eureqa) innan körningen i två delar: träningsdata (train data) och valideringsdata (validation data). Sedan körs modellen på träningsdatan och valideras på valideringsdatan. Dessa två delar presenteras med olika färger här så man ser hur bra eller dåligt den valda modellen (uttrycket) passar. Mycket trevligt.

Olika statistiska metriker visas för respektive träning- och valideringdata:
- Fitness
- R-squared
- Correlation Coeff
- Mean Squared Error
- Mean Absolute Error
- Minimum Error
- Maximum Error

De flesta av dessa kan man använda som fitness metric i modelleringstabben.

I listan över lösningar ser man en handful lösningar som anses som mest intressanta, med den mest lovande överst. Denna lista växer dynamiskt hela tiden efter hand Eureqa hittar nya modeller. Om man klickar på en av modellerna visar både statistik och plottningen för den valda modellen. Dubbelklickar man på en formel kopieras den för att sedan klistras in i något finns program (t.ex. om man vill blogga om det).

Modellering, några exempel

Här en kort beskrivning om modelleringen. Till skillnad från traditionell "curve-fitting" så skriver man inte några matematiska uttyck som ska parametriseras, utan endast vilka variabler som ska vara med i uttrycket. För dessa variabler väljs om de överhuvudtaget ska vara med samt eventuell parameter. Eureqa hittar även olika konstanter, både "globala" och inom uttryck.

Exempel med sinus
En av de första sakerna jag testade var att skapa en datafil med två kolumner (x och y) skapad på följande sätt (med Perl):

perl -le 'for (-100..100) { print $_/100, " ", sin(2*$_/100)+3}'

som skapar data för sambandet y = sin(2*x) + 3. De sparades i datafilen sin_formula.txt.

Eureqa hittar lösningen efter cirka 10-15 sekunder. Notera att x motsvaras av "x0" och y av f(x0) (eller x1):

  f(x0) = 3 + sin(2 * x0)

Detta var alltså 201 datapunkter, men man behöver inte alls så mycket data för att Eureqa ska hitta en lösning.

En variant där man endast tar 20 slumpmässiga punkter är sin_formula_rand20.txt som är skapad genom att ta 20 punkter mellan 0 och 2*Pi:

perl -le 'for (1..20) { my $x = rand(2*3.14159); print "$x ", sin(2*$x)+3}'

Eureqa hittar 3+sin(2*x0) på cirka 30 sekunder. Det gick (denna gången i alla fall) lite långsammare eftersom det är färre punkter. Man ska dock komma ihåg att färre punkter gör att det är snabbare att kontrollera hur bra lösningen är.

Den viktigaste delen i modelleringen, förutom att hitta tillförlitlig data, är att hitta rätt byggstenar, dvs de matematiska funktioner som ska användas. Det bör göras med viss försiktighet och eftertanke: Om man väljer för många kan det ta väldigt lång tid och man kan får konstiga resultat. Väljer man för få så hittas inte en enkel lösning. Detta är en konst.

Fibonacci-serien
En annan skoj sak som man kan testa är tidsserier eller data som kan ses som tidsserier. T.ex. kan Eureqa hitta en formel för Fibonacci-serien? De 25 första talen i Fibonacciserien är: 1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946.

För att göra detta till en lämplig representation - och som vanligt är representationen av problemet väldigt viktigt - är att man tar (tids)serien och lägger den i sekvens över flera variabler.

Låt oss anta att vi inte vet så mycket om denna serie, men anar att det finns en rekursivitet i serien, dvs att senare värden beror på de tidigare, normalt de omedelbart föregående (andra tidsserier, till exempel de ekonomiska kan ha andra beoenden såsom säsonger och veckodagsberoenden).

Här tas serien om fyra. Den första raden är 1,1,2,3, och sedan förskjuts serien för varje rad. Hela serien finns alltså i första kolumnen.

% | t1 t2 t3 t4 |
1 1 2 3
1 2 3 5
2 3 5 8
3 5 8 13
5 8 13 21
8 13 21 34
13 21 34 55
21 34 55 89
34 55 89 144
55 89 144 233
89 144 233 377
144 233 377 610
233 377 610 987
377 610 987 1597
610 987 1597 2584
987 1597 2584 4181
1597 2584 4181 6765
2584 4181 6765 10946
4181 6765 10946 17711
6765 10946 17711 28657
10946 17711 28657 46368

Nu kan vi modellera problemet i Eureqa på följande sätt:
- Formel: t4 = f(t1,t2,t3)
- Byggklossar: "+","-","*","/"

Det tar mellan 5 och 10 sekunder för Eureqa att hitta sambandet:
t4 = t3 + t2

Correlation Coefficient är 1.00000, R-squared är 1 och alla error är exakt 0 så det ser helt korrekt ut.

Detta är skoj!

Man kan här notera att egentligen behövde vi ju bara de tre första variablerna t1, t2 och t3 men jag valde att ta med den extra kolumnen t4 för att inte fuska för mycket. En annan sak att notera att det är viktigt att titta på Correlation Coefficient och R-squared samt Error för att se hur bra lösningen är.

Nu kan man göra lite mer roliga saker. Given en lite större datamängd (fib_38.txt) med 38 värden kan vi kolla om Eureqa hittar några andra samband, t.ex. mellan endast två variabler t1 och t2, dvs mellan ett värde och endast de närmast föregående. Här lägger jag till funktionerna "exp", "sqrt" och "log".

Här är några samband som hittades i flera olika körningar. Samtliga dessa har en fitness error på 0.000 (det som i lösningstabben kallas "Error") och correlation coefficient på 1.0

f(t1) = 1.61803*t1
f(t1) = 1.61803*t1 - 0.472137/t1
f(t1) = 1.61803*t1 - 1.67999/exp(t1)
f(t1) = 1.61803*t1 - 1.67999/exp(t1)
f(t1) = 0.809017*t1 + 0.809017*sqrt(t1)*sqrt(t1) - 0.470881/t1
f(t1) = 1.61803*t1 + 0.221196/(t1*t1 - 1.61571*t1 - 1.70552)
f(t1) = 1.61803*t1 + -3.39888*log(t1)/exp(t1*t1 - 1.69947)
f(t1) = (1.61803*t1*t1 - 0.459213)/t1
f(t1) = 1.61803*t1 - 0.440428/(t1 - 0.440428/(1.61803*t1))
f(t1) = 1.61803*t1 - 0.3884/(t1 - 0.354305)

Notera att Eureqa har identifierat konstanten 1.61803 i flera av ovanstående lösningar vilket är väldigt nära phi, dvs "gyllene snittet" (golden ratio) = (1+sqrt(5))/2 ~ 1.6180339...). phi är precis förhållandet mellan två intilliggande Fibonaccital, så det är ju inte konstigt att Eureqa hittade detta samband. Se Fibonacci number på Wikipedia och Encyclopedia of Integer Sequences:A000045 för mycket mer info om detta.

Man kan säkert hitta andra matematiska konstanter om man letar vidare. Plouffe's Inverter är en guldgruva för sådant. T.ex. här är en sökning på konstanten 1.61803. Tyvärr är det väldigt många träffar eftersom det är så liten precision på talet.

Formeln f(t1) = 1.61803*t1 är alltså en approximering av nästa tal i Fibonacci-serien, dvs F[n+1] = phi*F[n] (avrundat till heltal).

Ett mera avancerat exempel är om Eureqa månne kan hitta den slutna formeln för Fibonaccital, dvs

F(n) = (phi^n - (1-phi)^n)/sqrt(5)

För detta krävs en ytterligare parameter i datafilen, nämligen n, dvs index för raden. Så här ser filen ut nu (fib_50.txt"), utökat till 50 rader. Den första kolumnen är alltså index.

% | ix t1 t2 t3 t4 |
1 1 1 2 3
2 1 2 3 5
3 2 3 5 8
4 3 5 8 13
...
48 4807526976 7778742049 12586269025 20365011074
49 7778742049 12586269025 20365011074 32951280099
50 12586269025 20365011074 32951280099 53316291173

Jag vet inte riktigt hur stora tal som Eureqa kan använda, men det saknas i alla fall stöd för arbiträr precison.

När jag skapat filen testades först med samtliga variabler:

t4 = f(ix,t1,t2,t3)

Då kommer lite mer avancerade förslag än tidigare körning, samtliga med Error 0 och correlation coeff på 1.0000 (dock inte med Maximum error 0), några av dem innehåller n, dvs index.

f(ix, t1, t2, t3) = sqrt(1.61803*t2*t3) + (t2*sqrt(t3) - t2*t2)/(sqrt(t3) - t2)

OK, nu till problemet om den slutna formeln
Formel: t1 = f(ix)
Funktioner: +,-,*,/, sqrt

Det vi vill ha är alltså något som liknar:

(phi^n - (1-phi)^n)/sqrt(5)

eller snarare den numeriska motsvarigheten

f(ix) = (1.61803^ix - (1-1.61803)^n)/2.2361
= (1.61803^ix - (-0.61803)^n)/2.2361
= 0.4472071911*1.61803^ix - 0.4472071911*(-0.61803)^ix

(Den tredje varianten hittades via ett matematikverktyg.)

Intressant nog började Eureqa med lösningar där endast ix upphöjt till stora tal (t.ex. 18) samt addition, multiplikation med konstanter. Efter ett tag började experimenten med sqrt, men den körningen hittade inte skoj på många minuter så jag stoppade den.

För att komma runt detta testade jag "hints", dvs "Seed previous solution(s)" på "Pick Modeling Task"-tabben, genom att skriva 1.61803^ix samt sqrt(5). Då kom följande lösningar efter liten stund. De har alla korrelationskoefficient på 1, Error på 0 men stora Maximum Error.

f(ix) = ix + 4*ix*ix*ix + 0.0256922*ix*1.58422^ix
f(ix) = 0.445386*ix + 0.445386*1.61817^ix
f(ix) = 0.0893707 + 0.399785*sqrt(1.61804^ix) + 0.447094*sqrt(1.61804^ix)*sqrt(1.61804^ix)
f(ix) = 2*ix + 0.447097*1.61804^ix
f(ix) = 0.611078*sqrt(1.62499^ix) + 0.447094*1.61804^ix - 127.933

Jag undrar dock hur "naturligt" det är för Eureqa att testa formler på formatet "konstant^variabel", så detta anser jag vara lite fusk. Däremot, om det skulle gärna mer seriösa experiment är denna typ av hintar vettiga. Då anger man vissa samband som grund, ett "alfabet" att bygga vidare på. Jag tror att mer stöd för detta kommer i senare versioner.

Efter detta - ska vi säga misslyckande - skippade jag hintarna och lade på funktionerna "exp", "sin", "cos" och då hittades detta samband och flera liknande, som jag faktiskt inte vet hur det ska tydas. Vad är 0.481188 för något tal i detta sammanhang?

f(ix) = 0.447755*exp(0.481188*ix) - 0.481188*ix*ix*ix

Om man däremot lägger till funktioner "power" (och tar bort alla hintar) så kommer lösningar på formen konstant^ix väldigt snabbt (dvs inom en minut eller så), t.ex.

f(ix) = 32.1653 + 0.446572*1.61809^ix

Där vi möjligen kan ana phi i konstanten 1.61809.

En kommentar om "power": När man väljer den i funktionslistan kommer meddelandet Tip: integer powers are implemented automatically with the multiply operation. This more general power operator may not be needed for modeling the dataset.. Här har vi tydligen ett fall där "power" behövs.

Andra lösningar i olika körningar:

f(ix) = 1.61808^(ix - 1.67492)
f(ix) = 0.0893756 + 0.399799*1.27202^ix + 0.447099*1.27202^ix*1.27202^ix
f(ix) = 1.61804^(ix - 1.67287) + 1.61804^(0.478442*ix - 0.800371)
f(ix) = 1.26564^(2*ix - 1.26564) + 2*ix - 1.26564
f(ix) = ix + 0.447144*1.61804^ix

(Jag har inte analyserat vidare eventuella matematiska samband...)

Notera att även om det är 0 i Error och 1 i korrelationskoeffient så kan det vara stora fel när man pumpar i konkreta värden.

En intressant lösning är följande där man möjligen kan skymta de viktiga beståndsdelarna i den slutna formeln:
- sqrt(5) ~ 2.2361
- 0.4472071911*1.61803 (från tredje varianten av den sökta formeln)

f(ix) = 2.23642*ix + 0.447144*1.61804^ix

Mer komplexa varianter:

f(ix) = 0.447144*1.61804^ix + 2.61804*ix*ix - (ix*ix)^(ix - 48.6408) - 48.6408*ix

Efter detta avslutade jag testet p.g.a. tidsfaktorer.

Slutsats: Vi hittade alltså inte formeln under dessa experiment, men vissa av sambanden kanske kan vara intressanta att studera vidare. Och så lärde vi oss det där med "power". En annan sak detta visar är att man kan vara tvungen att starta om flera gånger för att få mer aptitliga lösningar.

Derivata
Som nämnts några gånger tidigare så har jag inte labbat så mycket med dynamiska modeller, ävenom Eureqa skapats för detta ändamål. En av anledningarna är att jag inte har så bra data tillgänglig, en annan är att de mer intressanta körningarna kan ta lång tid, i vissa fall många timmar; "över natten" är ett uttryck som används några gånger i skrifterna.

Som videon (se Eureqas hemsida för länk) visar finns det möjlighet att använda derivata på följande format:

D(x1,t) = f(x1,x2,t)

och även i högerledet

D(x1,t) = f(x1,x2,D(x2,t))

Andra derivatan skrivs på följande sätt:

D(x1,t,2) = f(x1,x2,t)

Man ska dock tänka på att med derivata så krävs en preprocessing som kan ta mycket lång tid.

Andra modelleingsexempel beskrivs nedan.

Datafiler

Här är några av de datafiler som jag testat. För det mest är det enklare saker, och inte någon dynamisk data. De läses in med "File", "Import data...". Datafilerna finns även att tillgå på My Eureqa page.
  • gelman.csv: Linjär regressionsexempel.

    Data från Andrew Gelman's bloggpost Equation search, part 1, Equation search, part 2. Problemet beskrivs även lite mer i A linear regression example, and a question.

    Skriv följande i Pick Modelling Task:
    y = f(x1,x2)
    och lägg till "sqrt" som funktion.

    En lösning är mycket riktigt

    f(x1,x2) = sqrt(x1^2+x2^2)

    Med en korrelationskoefficient på 1.0 (och det är alltså bra).

  • planets.txt: Keplers tredje lag

    Detta exempel baseras på DTREG, ett annat symboliskt regressions-verktyg. Här hittas Keplers tredje lag baserat på den data som Kepler hade. Keplers tredje lag är:

    Period^2 = Distance^3

    Formel: Period = f(Distance)
    Funktioner: Skippa sin och cos, lägg till square root, exp och logarithm.

    Eureqa hittar rätt snabbt samband såsom:

    Period = sqrt(Distance)*Distance

    och det går snabbt.

  • odd_parity.txt
    En test på "paritet", men det funkar inte eftersom Eureqa än så länge saknar booleanska operatorer såsom OR, AND och XOR. Det ska komma "snart".

  • sin_formula.txt
    Se ovan.

  • sin_formula2.txt
    Se ovan.

  • sqrt_formula.txt

    Skapad så här:

    perl -le 'for (-100..100) { print $_/100, " ", sqrt(abs(2*$_/100))+3}'

    Glöm inte att lägga till sqrt, abs och lite andra funktioner.

  • iris.txt: Iris data
    Iris är ett standardproblem (-datamängd) inom machine learning och traditionell multivariat statistisk analys. Se Iris flower data set (Wikipedia) för mer information. Kortfattat handlar det om att klassifiera tre olika blomtyper (Iris setosa, Iris virginica and Iris versicolor) med avseende på fyra attribut: (Sepal Length, Sepal Width, Petal Length, Petal Width). 50 mätningar gjordes för respektive blomtyp.

    Jag tänkte att det skulle vara skoj att testa det med Eureqa också. Tyvärr klarar inte Eureqa att hantera kategorier (dvs strängrepresentation) så jag döpte om dem till "1", "2", samt "3" vilket troligen förvirrar Eureqa. En standardlösning för visssa typer av analysverktyg/-metoder som inte klarar kategorier är att i stället använda tre binära variabler som representation för de tre kategorierna. Men jag vet inte hur man får in sådant i Eureqa.

    Jag började med att representera attributen som sepallength, sepalwidth, petallength, petalwidth men det blev så trångt i lösningsfönstret att jag ändrade till kortnamnen sl, sw, pl, pw.

    Problemet skrivs på följande sätt

    class = f(sl, sw, pl, pw)

    Första körningen, med standarduppsättningen "+","-","*","/" samt "sin" och "cos" gick inte alls bra. Men när - som experiment - jag lade till funktionerna "minimum", "maximum" och "sqrt" så hittas följande rätt snart

    class = f(sl,sw,pl,pw) = max(1,pw + 2.20/sw)

    med en error på 0.179, fitness på -0.18, correlation coeff på 0.96, mean squared error 0.04. Traditionella metoder inom data mining/machine learning såsom beslutsträd brukar ligga ungefär där med 5-10 felklassificerade instanser.

    Efter lite mer tuggande kommer några bättre lösningar.

    error 0.129:

    f(sl, sw, pl, pw) = 0.975279 + min(0.624122*pw*pw, 2.02407)

    error 0.124:
    f(sl, sw, pl, pw) = 0.926007 + min(max(0.63846*pw*pw, 0.0735181), 2.07556)

    Jag är inte nöjd med detta eftersom min och max inte är så naturliga i sammanhanget och jag har inte analyserat vidare ramifikationerna av detta. Men det är ett roligt experiment. Man skulle kunna gå vidare och kontrollera vad som händer om man representerar de tre kategorierna med talen 100, 200, 300 istället, eller lägger till andra funktioner såsom sign etc.

    Som jämförelse kan nämnas att andra metoder (t.ex. via machine learningverktyget Weka) ger följande resultat, båda med ett antal felklassifikationer.

    J48 (beslutsträd):

    petalwidth <= 0.6: Iris-setosa (50.0)
    petalwidth > 0.6
    | petalwidth <= 1.7
    | | petallength <= 4.9: Iris-versicolor (48.0/1.0)
    | | petallength > 4.9
    | | | petalwidth <= 1.5: Iris-virginica (3.0)
    | | | petalwidth > 1.5: Iris-versicolor (3.0/1.0)
    | petalwidth > 1.7: Iris-virginica (46.0/1.0)


    JRIP (regelbaserad method):

    (petallength <= 1.9) => class=Iris-setosa (50.0/0.0)
    (petalwidth >= 1.7) => class=Iris-virginica (48.0/2.0)
    (petallength >= 5) => class=Iris-virginica (5.0/1.0)
    => class=Iris-versicolor (47.0/0.0)

    Se även min My Weka page för mer saker om Weka.

  • Sunspots.txt: Sunspots
    Solfläcksdata är ett annat standardproblem inom statistik och tidserieanalys. Tyvärr är jag lite osäker på vad denna data kommer ifrån, men det ska mätning av solfläckar på årsbasis. Så ta följande med en viss nypa salt och se det som ett generellt experiment.

    Detta är alltså en tidsserie med 11 "förskjutna" variabler.

    Formel t11 = f(t1,t2,t3,t4,t5,t6,t7,t8,t9,t10)
    Funktioner: +,-,*,/, sin, cos

    Notera att jag lät sin och cos vara med men de användes inte under den cirka halvtimmen jag körde (förutom några tidigare lösningar som förkastades snabbt).

    Efter ett par minuter var följande med i listan över aktuella lösningar (avrundat till 2 decimaler):

    Error: Solution
    0.215: 0.65*t10 + 0.66* (t10 / (0.32+0.08*t8)
    0.237: 7.20+1.34*t10 - 0.58*t9
    0.261: 1.39*10-0.54*t9
    0.302: 1.91*t10-t9
    0.307: t10-0.19*t9
    0.342: 0.84*t10
    0.400: t10

    Ingen av lösningarna är speciellt bra. Vi ser dock att t10 - inte förvånande - alltid är med, ibland t9 och vid ett tillfälle (det bästa) med t8 vilket visar att det finns någon form av beroende av tidigare värden.

  • sin_formula_rand20.txt

    Skapad med följande:

    perl -le 'for (1..20) { my $x = rand(2*3.14159); print "$x ", sin($x)+exp($x)+3}'

    Hittar följande snabbt:

    3 + exp(x0) + sin(x0)

    Testar genom att skippa sin(), men låter cos() vara kvar. Det tar en stund, sedan hittar den följande

    3.00 + exp(x0) + cos(1.57-x0)

  • boyles_law.txt: Boyles gaslag
    Se mer på Wikipedia Boyle's law.

    Detta är en klassiker i sammanhanget (dvs equation/scientific discovery), från boken Langley et.all Scientific discovery (ISBN: 9780262620529, länk till Bokus), sidan 82. Boken beskriver hur systemet BACON angriper problemet. BACON är ett system med liknande intentioner som Eureqa men använder en annan teknik. Boken är för övrigt mycket intressant.

    Eureqa hittar relativt snabbt samtliga samband (vid var sin körning):

    PV = P*V
    V = PV/P
    P = PV/V

    Corelation coeff är 1 och mean error i princip 0.

    Intressant nog kommer under körningen VP=f(V,P) även andra samband efter en stund:

    f(V, P) = (V*P*cos(-1*P - 1.36791) - V*P*P)/(cos(-1*P - 1.36791) - P)

  • fib_25.txt: Fibonacci
    Se ovan.
  • fib_35.txt
    Se ovan.

  • catalan.txt: Catalan-talen.

    Har inte hittat något skoj hittills, men ska nog leta vidare...

  • not_squares.txt
    Tal som inte är kvadrater. Hittade inget skoj.

  • primes.txt: Primtal
    Detta är också en tidsserie-variant med 10 variabler för att se om något skoj samband hittas. Även här får man leta vidare.

  • primes_with_index.txt: Primtal med index (dvs ordningstalet för primtalet)
    Se ovan om primes.txt

  • p4_gap.txt: Polynom
    Detta är ett av exempelproblem från JGAP (ett generellt genetisk programmingssystem i Java) där problemet är att hitta polynomet x^4 + x^3 + x^2 - x.

    Detta tog cirka 30 sekunder att hitta denna funktion i Eureqa. Notera att jag tog bort "sin" och "cos".

    Som jämförelse kan nämnas att JGAP-versionen tog cirka 12 minuter (vid första och enda körningen), men det är inte en rättvis jämförelse eftersom Eureqa är optimerat för denna typ av körningar. Uppdatering: . Jag noterade att anledningen till att det tog så lång tid i JGAP var att det inte fanns några operatorer för Add (+) eller Subtract (-) vilket ju gör problemet mycket svårare. När dessa lades till (samt Sine och Exp togs bort) tog det cirka 10 sekunderi JGAP. JGAP är helt klart ett intressant system för genetisk programmering.

  • p4_1.txt: Polynom
    Jag skrev ett litet program som skapar slumpdata för polynom på formen x^n+n^(n-1)+...n^2+x^1+x. Sådan problem kallar jag för p(n) nedan.

    Detta är alltså p(4). Det tog Eureqa cirka 20 sekunder att hitta

    p(4) = x^4 + x^3 + x^2 + x

    baserat på 30 punkter x,y inom intervallet -5.0..5.0.

  • p10_1.txt Polynom P(10)
    Däremot var det lite problem med p(10) över intervallet -2.5..2.5 och 100 punkter. Jag startade om ett antal gånger efter att ha väntat - ovetenskapligt nog - "några minuter .

    Rätt tidigt hittades x^10+x^8+x^7 men sedan tog det stopp
    och Eureqa började labba med x^12, t.ex. (x^12-x^2)/(x^2-x).

    En trolig förklaring till detta är att Eureqa straffar flera termer till förmån för färre.

    Jag startade om och ändrade Fitness Metric till "Maximum Error" (på tabben "Pick Modeling Task"). Efter cirka 6 minuter hittades

    0.73*x+x^2+x^3+x^4+x^5+x^6+x^7+x^9+x^9+x^10

    med ett Maximum error på 1.76. Correlations coefficienten är 1.0000 vilket ju är bra.

    Lösningen
    (x^12-x^2)/(x^2-x)
    har ett mindre felvärde för den datamängd jag testade, det var ju bara 100 punkter, så en del kan förklaras utifrån slump.

    Jag tröttnade efter typ 20 minuter.

  • p6_1.txt: p(6)

  • p7_1.txt: p(7)

  • circle_1_fixed.txt: Cirkel

    Detta är ett av exemplen till Eureqa, som finns att laddas ner här. Tyvärr är de i ett konstigt format så jag var tvungen att snygga till dem lite, härav namnet "_fixed.txt".

    Formel: x3 = f(x1,x2)

    Hittar lösningen 4*sin(x1) på 20 sekunder.

    Formal: x2 = f(x1,x3)
    Hittar lösningen 4*sin(x1) på 20 sekunder.

    Testar nu derivata:

    Formel: D(x3,x1) = f(x1,x2)
    Lösningen verkar vara

    dx3/dx1 = x2

    Testar formeln D(x3,x2) = f(x1,x2)
    Lösningen är 0 som Eureqa hittar omedelbart.

    Formeln D(x2, x1) = f(x1, x3)
    ger lösningen x3.

Mer om Eureqa

Här är en samling länkar om Eureqa.

Mer om symbolisk regression som är den metod Eureqa använder: Symbolic regression (Wikipedia)

* Andra artiklar om Eureqa:


Posted by hakank at 09:16 FM Posted to Dynamiska system | Machine learning/data mining | Pyssel | Statistik/data-analys

november 23, 2004

Kaosteori - den riktiga historien? II

I Kaosteori - den riktiga historien? berättades om ett paper som försökte reda ut hur kaosteorien uppstått.

I den nyss infådda - och som verkar helt lysande - boken Slumpens skördar (innehållsförteckning) av matematikern Olle Häggström kan man läsa på sidan 11 att "den bästa framställning [Häggström] känner till om dessa frågor" (dvs kaosteorins utveckling) är Science of Chaos or Chaos in Science? (från 1996) av Jean Bricmont.
Abstract till papret är:
I try to clarify several confusions in the popular literature concerning chaos, determinism, the arrow of time, entropy and the role of probability in physics. Classical ideas going back to Laplace and Boltzmann are explained and defended while some recent views on irreversibility, due to Prigogine, are criticized.

Jean Bricmont är kanske mer känd för den bok han skrev tillsammans med Alan Sokal: Fashionable Nonsense: Postmodern Intellectuals' Abuse of Science. Lite mer recensioner och länkar om boken finns t.ex. här.


Boken "Slumpens skördar" innehåller f.ö. flera mycket spännande kapitel, t.ex. om perkolation, "Världen är liten", dvs small world-forskningen (och som har - och nu kommer en googlelänk - skrivits om tidigare), spelteori och slumpvandringar. Spännande!

Posted by hakank at 08:41 EM Posted to Dynamiska system

februari 28, 2004

Mer om myntsingling

Mer om Diaconis om myntsingling.

Science News har två artiklar:
Erica Klarreich: Toss Out the Toss-Up: Bias in heads-or-tails

Ivars Peterson: Heads or Tails? som innehåller lite mer bakgrund och referenser.

Posted by hakank at 09:01 FM Posted to Dynamiska system

februari 27, 2004

Äggskalsforskning

Philip Ball skriver i sin Nature-artikel Shattered eggs reveal secrets of explosions om forskning kring exploderande ägg.

Exploding eggs might help investigators work out the causes of industrial explosions or airline disasters, according to researchers who have been smashing egg-shells.

The distribution of sizes of fragments left after a blast can be used to work out the pressure of the explosion, say Ferenc Kun of the University of Debrecen in Hungary and his co-workers.


Naturligtvis hittar man power laws även här:

The mathematical equations that predict the number of pieces of each size can be described by something called a power law [...].
...
[Hans] Herrmann speculates that their mathematical formula could also be used to figure out the size of fragments missing from broken archaeological vessels, provided that enough shards are found to map out the overall size distribution of the pieces.

The problem, Herrmann says, will be in gathering enough fragments to do any calculations. Debris in aircraft explosions can be scattered over kilometres, he says, and the smaller the fragments, the harder they are to find.


Se Falk Wittel, Ferenc Kun, Hans J. Herrman, Bernt H. Kroplin: Fragmentation of shells
Abstract:
We present a theoretical and experimental study of the fragmentation of closed thin shells made of a disordered brittle material. Experiments were performed on brown and white hen egg-shells under two different loading conditions: impact with a hard wall and explosion by a combustible mixture both give rise to power law fragment size distributions. A three-dimensional discrete element model of shells is worked out. Based on simulations of the model we give evidence that power law fragment mass distributions arise due to an underlying phase transition which proved to be abrupt for explosion and continuous for impact. We demonstrate that the fragmentation of closed shells defines a new universality class of fragmentation phenomena.


Se även
Ferenc Kun
Hans Herrmann som nämndes tidigare i Sanddynematematik.

Posted by hakank at 09:57 FM Posted to Dynamiska system

februari 05, 2004

Physics of Society

Via Explikation hittades Guardian Unlimited-artikeln Futurology gets a little more exact som beskriver "physics of society", olika modeller för att förklara samhällsfenomen, bland annat agentbaserade. (Explikation gör även en jämförelse med Asimons psykohistoria, vilken läs.)

Ett utdrag ur artikeln:
In the past few years, physicists have started applying their ideas to the social sciences in an attempt to figure out whether there exists a "physics of society". At the same time, social and political scientists have begun to adopt some of the methods pioneered in physics to understand and predict the behaviour of large groups of people. Unlikely as it might sound, there are signs that aspects of social behaviour follow mathematical laws akin to those obeyed by insensate matter in the physical sciences.
...
Social physics won't solve all of society's problems, but it might provide a more rational basis for making social decisions. It can be hard to predict the effect of particular laws and policies once they are unleashed on a highly interactive population. By using agent-based modelling, and by understanding the analogies that such models often show with behaviour seen in physics, it might become possible to base some of those decisions on more than wishful thinking or dodgy statistics. In other words, it might become easier to anticipate the kinds of society that might result from certain choices. The hardest issue, of course - and here physics can offer no help - is to decide what kind of society we want in the first place.

Artikeln avslutas med en kort presentation av artikelförfattaren Philip Ball där det nämns att denne kommit ut med en ny bok Critical Mass vars underrubrik varierar. I artikeln är den "the Physics of Society", på Amazon står det "How One Thing Leads to Another".

Ett utdrag ur boken finns hos Random House.

Se även Seminar Notes On 'The Physics of Institutions' (PDF) av Philip Ball och Paul Ormerod, som handlar om samma saker som i boken. Bilder saknas tyvärr

Abstract: Philip Ball traces the development of statistical physics, first proposed by James Clerk Maxwell and Ludwig Boltzman and shows how its principles can be used to understand human systems. He shows how rules of interaction between agents can give rise to such phenomena as phase change and self organised criticality and looks at the use of such models for understanding traffic states and the evolution of business organisations, as well as other social science issues such as the effect of social forces on marriage. Paul Ormerod looks at models used to tackle racial segregation, financial markets and crime studies and suggests how powerful insights into the aggregate properties of human organisations can be gained using quite simple agent characterisation and rules of interaction.

Posted by hakank at 10:12 FM Posted to Agentbaserad modellering | Dynamiska system | Komplexitet/emergens

januari 05, 2004

Sanddynematematik

Från New York Times When Sand Dunes Collide, Sometimes They Mate and Multiply:
Veit Schwämmle, a physicist, conducted the research with a colleague at the University of Stuttgart using a computer program that predicted what would happen when one of the crescent-shaped dunes called barchans (pronounced bar-KAHNS) wandered into another.

Länkar:
Veit Schwaemmle, hans Dunes-sida samt thesis Modeling of Dune Morphology (PDF).

Hans Herrmann har även forskat om Dunes.


Tidigare blogganteckningar om sand:
Simulering av sand
... Nu även med lite granularitetsforskning.

Posted by hakank at 10:49 FM Posted to Dynamiska system

november 01, 2003

Musik till det engelska TV-prorammet om kaos identifierat

I flera av de TV-program om kaos från det glada 90-talet som jag har inspelade finns det några musikstycken som fastnat i huvudet. Det är välkända stycken, men det har tagit ett tag innan de identifierades.

Lättast var det med Bachs "Preludium och Fuga 1 C Major", från "The Well-Tempered Clavier". Det ska dock spelas snabbt, lätt och flytande, och inte så långsamt som Glenn Gould gör på den inspelning jag har: "The Original Jacket Collection: Glenn Gould Plays Bach" (en 10-pack Bach).

Svårare har det varit med introduktionmusiken till det där engelska TV-programmet "Chaos" (med dansk speakertext) där bland annat Ian Stewart är med, stående ute i träskmarken, pratande om det känsliga ekologiska systemet.

För en liten stund sedan råkade jag höra musiken på den svenska musikkanalen P2 Det är "Totenfeier" av Gustav Mahler.

Skönt, nu vet jag det.

För övrigt tycker jag inte att "El Condor Pasa" passar så där väldigt bra när man zoomar in och ut i en Mandelbrotfraktal. Där passar Bach mycket bättre.

Posted by hakank at 02:42 EM Posted to Dynamiska system | Comments (8)

oktober 09, 2003

Stephen Wolfram i "Senate Subcommittee on Science, Space, and Technology"

Stephen Wolfram har pratat för "Senate Subcommittee on Science, Space, and Technology" om sin bok A New Kind of Science. En textversion av talet finns här (PDF-fil). Det refereras även till denna www.senate.gov-sida, men den kommer jag inte åt.

Fler transcripts finns här.

Posted by hakank at 09:41 EM Posted to Dynamiska system

oktober 08, 2003

Analys av ekonomiska bubblor. Lomb-periodogram.

I Nature-artikeln Physicists predict Christmas crisis for UK housing market beskrivs en ny bubbla, nämligen i den brittiska fastighetsmarknaden.

"Mayhem may be in store" for the British property market, say scientists in California. They claim to see the "unmistakable signature of a strong unsustainable bubble" in UK house prices, which could burst around the end of this year.

There is no comparable danger in the US real-estate market, say Wei-Xing Zhou and Didier Sornette of the University of California, Los Angeles, despite fears among investors of a "bubble mentality".
...
Sornette believes that most market crashes arise from the internal dynamics of trade, rather than being a response to some external shock to the system. A crash, he suggests, is preceded by a period of very fast growth in economic indices, plus a series of wobbles or oscillations stretching over several years, which come increasingly close together.

Papret är 2000-2003 Real Estate Bubble in the UK but not in the USA av W.-X. Zhou och Didier Sornette.

Sournette har skrivit böckerna Why Stock Markets Crash: Critical Events in Complex Financial Systems och Critical Phenomena in Natural Sciences: Chaos, Fractals, Selforganization and Disorder: Concepts and Tools. Jag har läst ingendera. En intervju med honom finns här.

Lomb-periodogram
I papret visas bland annat Lomb-periodogram (google-sök). Det finns, upptäckte jag efter lite sökande, ett R-paket för att visa sådana: paketet nlt, (non)linear time series analysis, som finns här. Han som skapat paketet är Ottar Nordal Bjørnstad. Se även hans publikationer. Bjørnstad forskar dock inte i ekonomiska bubblor utan i dynamiska biologiska system.

Posted by hakank at 09:43 FM Posted to Dynamiska system

oktober 01, 2003

Varför klustrar sig bussar?

I Nature-artikeln There's chaos on the buses diskuteras problemet att bussar tenderar att klustra sig.


You wait half an hour for an airport shuttle bus, then two show up at once. It's not bad planning, it's chaos, says Japanese researcher Takashi Nagatani of Shizuoka University.

The unpredictability of shuttle-bus services may be inherent in the shuttling process, calculates Nagatani. He demonstrates that the average number of passengers aboard a bus and the distance between vehicles can fluctuate unpredictably, resulting in a less efficient system. Chaos emerges even in a very simple set up of two buses picking up regularly arriving passengers and taking them at constant speed to one destination.

Papret som refereras är Fluctuation of riding passengers induced by chaotic motions of shuttle buses. av Takashi Nagatani. Har dock inte hittat det på en publik sajt.

Se även artikelns "related stories" samt blogganteckningarna Simulering av "Vågen", trafikfenomen och Crowd Dynamics och Agent-baserad modellering - simuleringar av emergenta fenomen.

Posted by hakank at 11:53 EM Posted to Dynamiska system

september 27, 2003

Segregeringseffekter inom yrken

Råkade höra P1:s Människor och tro fredag kväll (26 september) där det bland annat diskuteras om kvinnliga präster och dess motståndare. Djuplänk till programmet finns här, det bytas dock varje vecka.

Cirka 11.40 minuter in i programmet säger Helene Egnell, forskare och präst i Stockholms stift, att forskning har visat att "när kvinnorna blivit 30% inom ett område upplevs det som om de tagit över". Prästyrket slutar då att vara ett "manligt yrke" och blir ett "kvinnligt yrke", och får därmed lägre status. Något senare pratas även om att samma fenomen verkar finnas inom politiken.

Detta verkar vara ett exempel på den modell för segregering som Thomas Schelling utvecklat och det är därför jag blev intresserad just nu. Se t.ex. mina anteckningar Matematiska och statistiska "självklarheter" samt avsnittet "Agentbaserat" i Länkdump efter restaurangbesök.


Tidigare har jag hört/läst om de uppgifter som nämdes i programmet, men blev nyfiken på exakt vilken forskning som Egnell refererar till. Tyvärr hittade jag inte något relevant paper. Någon?


Dock hittades ett intressant citat från Jämställdhet är ett farligt ord i medierna. Jag lyckades inte hitta någon författare, men en lite omarbetad version finns som ett debattinlägg där Anne Jalakas står som författare. (Se under rubriken "Jämställdhet ger kalla kårar".)
...
Det verkar finnas en 20-80-regel som är i det närmaste helig. Någon gång kan den nog överskridas, men när andelen kvinnor närmar sig 30 procent börjar det bli farligt. Det brukar visa sig genom att avdelningar läggs ned och redaktioner struktureras om. Inte sällan med motiveringar som nysatsning eller förnyelsebehov.
30-procentsgränsen har nu inget särskilt med kvinnor att göra utan är den nivå då de som har makt börjar reagera. Det kan vara vita amerikaner i ett område där svarta flyttar in eller pojkar i ett svenskt klassrum där taltiden plötsligt börjar fördelas mer jämlikt.
När den underordnade gruppen utgör 30 procent börjar det kännas som om de tagit över. Och då höjs ropen på återställare.


I citatet ovan nämns 20-80 (eller 80-20 regeln) som är "Paretos lag/princip", dvs att 20 procent av en population utgör/har/äger 80 procent av någonting, t.ex. 20% av mänskligheten äger 80% av tillgångarna, i programutveckling sägs 80% av buggarna finnas i 20% av koden, 80% av ett företags omsättning kommer från 20% av produkterna etc. Förhållandet kan även vara 90-10.

Jag förutsätter att det inte är endast till denna allmänna Pareto-princip (med värdena 30-70) som Egnell och Jalakas hänvisar till med de 30 "magiska" procenten, utan någon annan, mer specifik forskning om jämställdhet inom yrken.


Pareto-principen är dock väldigt intressant i sig, så här är lite länkar:

Aside
Andra intressanta "lagar" finns här, mestadels från Computer Sweden-artiklar.

Posted by hakank at 12:04 FM Posted to Dynamiska system | Komplexitet/emergens

september 01, 2003

Data mining, machine learning och emergens

Sedan ett antal (4-5) år har jag varit intresserad av data mining och machine learning, och läst en hel del böcker om den mer statistiska approachen, artificiella neurala nätverk, genetiska algoritmer etc, men inte förrän på sistone upptäckt kopplingen till emergensteorin.

"Data mining" och "machine learning" betecknar olika saker men används ofta för samma sak, nämligen att utifrån en datamängd (eller system som genererar data) lista ut något om den process (etc) som genererat datan. Machine learning betecknar också forskning kring hur man skapar system som lär sig själva via input, t.ex. en bil som styr givet input till ett neuralt nätverk, backgammon-spelande system (via neurala nätverk/genetiska algoritmer), vilket är något som är tätare kopplat till emergensteorin än ren dataanalys.


En av de orsaker till att jag är fascinerad av data mining/machine learning (och statistisk analys) är just att man med hjälp av data kan skapa en "bild" av ett "system" för att se vad som döljer sig bakom, t.ex. lära ett begrepp med hjälp av exempel, lista ut köpvanor hos de som köper saker, se vilka attribut (faktorer) som är viktigast bland en stor mängd olika attribut etc etc.

Det verkar nästan magiskt att man kan göra sådant. Algoritmerna är relativt enkla så magin försvinner kanske lite grand när man läser mer i ämnet. Å andra sidan är jag fortfarande fascinerad när jag ser en duktig trollkonstnär även om jag vet hur denne gör sina tricks.


När jag nu har börjat läsa mer om komplexa adaptiva system utifrån emergensperspektivet har jag upptäckt viktiga länkar mellan neurala nätverk, genetiska algoritmer, och andra (själv)lärande system till emergensteorin.

Speciellt genetiska algoritmer skapades (i alla fall om man får tro Mitchell Waldrop i hans Complexity) för att undersöka teorin om hur sådana emergenta fenomen uppstår, liksom neurala nätverk skapades för att studera hur det mänskliga medvetandet fungerar. Andra tekniker, t.ex. Quinlans beslutsträd (se slutet på min anteckning JMLR Special Issue on Inductive Logic Programming) skapades bland annat för att förstå hur vi kan lära oss begrepp induktivt med hjälp av data, vilket kan ses som ett emergent fenomen eller åtminstone kopplat till detta.

Böckerna jag tidigare läst tar nämligen inte upp den emergenta sidan av forskningen utan behandlar i stort sett endast den tekniska delen, dvs teorin bakom (matematiken och/eller algoritmerna) eller hur man implementerar sådana system. Möjligen står det lite historiskt i inledningarna av böckerna, men alltså inget jag har "tänt till" på. Trist att jag inte upptäckt/insett detta tidigare!

Genetiska algoritmer har jag i princip sett endast som ett sätt att optimera lösningar, även om det har lockat lite med den biologiska kopplingen. Cellulära automater, som jag bland annat läste en del om när jag pluggade datalogi, sågs som teoretiska beräkningssystem, men inte som något emergent, även om jag tillbringade ett rätt stort antal timmar med Game of Life-simuleringar. Och Hofstadter skrev i sin Gödel Escher Bach-bok en hel del om emergenta fenomen.


Den första gången jag "nysåg" t.ex. genetiska algoritmer var i Duncan Watts bok Small Worlds, där han skrev om dem på ett sådant sätt att jag började bli intresserad igen, men eftersom jag inte ville avvika från min social network analysis/complex networks-väg så ignorerade jag denna "irrfärd".

Jag inser att jag - nu i min feberyra - möjligen överskattar kopplingarna. Men, hur som helst, data mining/machine learning är ett fascinerande område. (Man kanske inte ska blogga feberanfrätt i seriösare ämnen, liksom man inte bör blogga intoxikerad då...)


Böcker om data mining/machine learning
Här är några av de böcker jag läst om data mining/machine learning, beskrivet från den "tekniska sidan". Notera att dessa böcker alltså inte tar upp emergensfenomenet utan diskuterar en massa tekniker för att analysera datamängder eller lösa optimeringsproblem etc.


Tom Mitchell: Machine Learning
Är nog fortfarande den bästa introduktionsboken, även om den har några år
på nacken. Har ett kapitel om genetiska algoritmer som optimeringsmetod, liksom ett kapitel om neurala nätverk.


David J. Hand, Heikki Mannila, Padhraic Smyth: Principles of Data Mining
En inträngande genomgång om en massa olika tekniker att analysera data.


Richard O. Duda, Peter E. Hart, David G. Stork: Pattern Classification
En annan klassiker. Teknisk.


Jiawei Han, Micheline Kamber: Data Mining: Concepts and Techniques.
Behandlar ämnet utifrån ett databasperspektiv.


Ian H. Witten, Eibe Frank: Data Mining: Practical Machine Learning Tools and Techniques with Java Implementations.
Detta är en av mina biblar eftersom den beskriver mitt favorit-data mining-system (Weka). Den är inte lika teknisk som ovanstående böcker och behandlar inte allt som de gör. Däremot förklarar den de saker den förklarar på ett föredömligt sätt.


Michael J. A. Berry, Gordon Linoff:Data Mining Techniques For Marketing, Sales, and Customer Support
Lite gammal (1997) men behandlar data mining på ett konkret sätt, utifrån marknadsdata. Målgruppen är managementpersoner och kan läsas som en introduktion till data mining. Deras Mastering Data Mining: The Art and Science of Customer Relationship Management (från 2000) tyckte jag däremot inte alls lika bra om.


Se även mina bokrecensioner: Recension av Jesus Menas "Data Mining Your Website" och Recension av 'Building Data Mining Applications for CRM'.


Några lite mer lättsamma böcker:

Thomas A. Bass Predictors.
En underbar bok som berättar i en romanliknande form om några av hjältarna från både kaosforskningen och - visar det sig - emergensforskningen, nämligen Doyne Farmer och Norman Packard, som startar ett företag för att bli stenrika på börsen. De använder främst genetiska algoritmer och artificiella neurala nätverk för detta. Det står mycket lite om det tekniska men är en fascinerande resa.

Se även A few Prediction Company references.


David B. Fogel:
Blondie24
Självbiografi som berättar om hur författaren skapar ett Checkers-system med genetiska algoritmer och artificiella neurala nätverk. När jag nu tänker tillbaka på vad som står i boken är detta ett tydligt exempel på en "emergensapproach": författaren försöker att skapa en "riktigt" AI-system som utifrån nästan ingenting alls lär sig spelet och att spela riktigt bra. "Riktigt AI-system" i jämförelse med IBM:s schackmaskiner som "bara" är number crunching.

Själv har jag nu Prey av Michael Crichton som godnattlitteratur.
En vän till mig rekommenderade den och när han berättade att boken hade fyra sidors litteraturreferens om svärmintelligens, agent-baserad programmering/modellering samt Thomas Schellings 'Micromotives and Macrobehavior' var jag bara tvungen att köpa den. Speciellt långt har jag ännu inte kommit.

Posted by hakank at 07:26 EM Posted to Agentbaserad modellering | Böcker | Dynamiska system | Komplexitet/emergens | Machine learning/data mining

augusti 26, 2003

Brian Arthur: Lock-in och El Farol

I Growing Artificial Societies - recension skrev jag lite om kritik av traditionella ekonomisk teorier. En av de personer som alltid dyker upp i sådana diskussioner är Brian Arthur. Han nämns i flera böcker om komplexa nätverk och komplexitetsteori, så jag beslöt mig att kolla in lite mer vad han skrivit.


Det jag läst är ett fåtal dokument, vilket kanske kan vara en bra introduktion även för andra. Arthur har skrivit en andra saker, men just nu ville jag bara ha en lite mer övergripande syn. Anledningen till att det blev just dessa dokument får tillskrivas olika delar slumpen, googles PageRank samt medvetetet planerande.

Första kapitlet i Complexity: The Emerging Science at the Edge of Order and Chaos av Mitchell Waldrop handlar i stort sett endast om Brian Arthur. Här beskrivs hur Arthur var väldigt otillfredsställd med de förhärskande ekonomiska teorierna och hur han vände sig till biologin (främst molekylärbiologin) och fysiken, speciellt teorierna om icke-linjära system, för att få inspiration. Teorierna om lock-in beskrivs övergripande.

Många av de fenomen, speciellt i de högteknologiska branscherna, som Arthur skriver om i sina "lock-in"-dokument är i enlighet med maximen "åt den som har ska vara givet", dvs att den som redan är rik blir rikare. En svensk biblisk förklaring till detta uttryck finns här.

Teorin om lock-in innebär att en teknik som är tekniskt underlägsen kan, ofta av rena tillfälligheter, börja med en liten ledning över konkurrenterna, för att sedan ta över ("lock-in") hela eller stora delar av marknaden.


Positive Feedbacks in the Economy (PDF) publicerad i Scientific American, Feb. 1990.
Detta är en populärt hållen och läsvärd artikel om Arthurs "lock-in"-tankar som betonar den positiva (förstärkande) feedback, increasing returns, som finns i världen, till skillnad från den negativa (förminskande, neutraliserande) feedbacken, diminishing returns, som traditionella ekonomiska teorier bygger på.
Artikeln är mycket läsbar och har flera exempel, t.ex. varför VHS vann striden över Beta Max, QWERTY-tangentbordet etc. "Åt den som har ska vara givet".

Naturligtvis bör man här även göra en koppling till vad systemdynamikerna har sagt rätt länge.


Competing Technologies, Increasing Returns and Lock-in by Historical Events (PDF)
Detta är ett betydligt mer tekniskt paper än 'Positive Feedbacks in the Economy', där "tekniken" består av en sannolikhetsteoretisk diskussion. Den är snårigt här och där, men eftersom det är ett av de berömda papers som "alla" refererar till, är det bra att ha läst det.

Notera att jag hade problem att skriva ut de sista sidorna. Vad som saknas är - troligen - delar av Appendix och en litteraturförteckning.


Inductive Reasoning and Bounded Rationality (The El Farol Problem).
(Finns som PDF-dokument här.)
Detta paper är inte direkt kopplat till locked-in-teorin, men eftersom jag har läst om El Farol-problemet på ett flertal ställen var det lika bra att läsa även detta.

Här beskriver Arthur hur ekonomer bör tänka i sitt teoretiserande: i stället för att anta rationella "deduktiva" agenter (individer), ska man skapa teorier som handlar om induktiva agenter som endast har ofullständig (lokal) information om ett problem.

Han visar genom ett enkelt problem, El Farol-problemet, hur sådana resonemang kan göras. Det beskrivs på följande sätt:

Consider now a problem I will construct to illustrate inductive reasoning and how it might be modeled. N people decide independently each week whether to go to a bar that offers entertainment on a certain night. For concreteness, let us set N at 100. Space is limited, and the evening is enjoyable if things are not too crowded--specifically, if fewer than 60% of the possible 100 are present. There is no way to tell the numbers coming for sure in advance, therefore a person or agent: goes--deems it worth going--if he expects fewer than 60 to show up, or stays home if he expects more than 60 to go. (There is no need that utility differ much above and below 60.) Choices are unaffected by previous visits; there is no collusion or prior communication among the agents; and the only information available is the numbers who came in past weeks. (The problem was inspired by the bar El Farol in Santa Fe which offers Irish music on Thursday nights; but the reader may recognize it as applying to noontime lunch-room crowding, and to other coordination problems with limits to desired coordination.) Of interest is the dynamics of the numbers attending from week to week.

Notice two interesting features of this problem. First, if there were an obvious model that all agents could use to forecast attendance and base their decisions on, then a deductive solution would be possible. But this is not the case here. Given the numbers attending in the recent past, a large number of expectational models might be reasonable and defensible. Thus, not knowing which model other agents might choose, a reference agent cannot choose his in a well-defined way. There is no deductively rational solution--no "correct" expectational model. From the agents' viewpoint, the problem is ill-defined and they are propelled into a world of induction. Second, and diabolically, any commonalty of expectations gets broken up: If all believe few will go, all will go. But this would invalidate that belief. Similarly, if all believe most will go, nobody will go, invalidating that belief. Expectations will be forced to differ.

Diskussionerna som sedan följer är, intressant nog, snarlika de diskussioner som Thomas Schelling gör (1978) i sin Micromotives and Macrobehavior. Schellings bok är full av sådana exempel och (matematiskt enkla) diskussioner kring dem. Se även min anteckning Matematiska och statistiska "självklarheter" för lite mer om Schellings bok. (Jag vet dock inte om det fanns någon direkt påverkan mellan Schelling och Arthur.)

Papret är lätt att följa även om det är, liksom med Schelling, en hel del tal-swischande.

Det som skiljer Brian Arthurs paper från Schellings bok är att Arthur, som jag ser det, sätter en något annan ram kring diskussionerna, främst genom att han diskuterar något mer utifrån en komplexitetsteoretiskt perspektive (komplexa adaptiva system), t.ex. nämner han genetisk programmering, men även att han diskuterar ur ett mer teoretiskt perspektiv än vad Schelling gör i boken.

Möjligen finns det mycket mer av El-Farol-liknande diskussioner i senare papers av Brian Arthur, men de har jag alltså inte läst.


[En aside:
Ett annat känt bar-exempel finns i filmen A Beautiful Mind, där det visas hur John Nash kommer fram till den spelteori-teori som gav honom Nobel-priset 1994. Enligt kommentatorspåret är det dock en fantasiprodukt för att visa principen bakom teorin.]


The Pretext Interview: W. Brian Arthur talks to Dominic Gates
Detta är en intervju med Brian Arthur från 1998 bland annat om Microsofts antitrust-utredning, lite modernare exempel på increasing returns (Java vs. ActiveX), samt svar på vissa kritiker.

Arthur säger bland annat följande om huruvida teorin om increasing returns fortfarande är kontrolversiell, vilket jag just undrade över när jag läste de andra dokumenten.

Gates: Is the theory of increasing returns still controversial?

Arthur: Absolutely not. This is now completely taken for granted in Silicon Valley. I don't have to go around California telling the Marc Andreesens of the world or the Andy Groves of the world that there are increasing returns. Intuitively, the smart people in high tech knew this all along.
...
Gates: So you don't see these ideas in opposition to classical economic theories, the Chicago school?

Arthur: Not at all.

However, some people who are great proponents of Chicago neoclassical economics seem to get uptight every so often in the opinion pages of the Wall Street Journal. The source of the problem is that if I say that markets can lock in to one product or one company, not necessarily the best, then that's taken as a threat to the whole ideology of capitalism.

The only controversies are ideological ones. I think it's inevitable that any important theory, or any new theory of any importance, does have a trail of flat-earthers behind it, a trail of creationists; people who won't get it and don't get it, for one or other ideological reason.


Lite andra länkar (rätt slumpmässigt hittade eller ihågkomna):

Posted by hakank at 01:07 FM Posted to Agentbaserad modellering | Dynamiska system | Komplexitet/emergens

augusti 25, 2003

Senaste Edge

Senaste Edge handlar om The Blackout där olika artiklar om strömavbrottet kommer att läggas. I skrivande stund finns både Strogatz och Barabasis texter där.

Även The Moral Sense Test (om moraliska dilemman) behandlas. Tyvärr kräver själva testet den senaste Flash-guckelimucken vilken jag inte har.

Posted by hakank at 10:56 EM Posted to Dynamiska system

augusti 24, 2003

Simulering av "Vågen", trafikfenomen och Crowd Dynamics

Dirk Helbing är en av de som forskat kring panik (se min anteckning Applåder och panik härförleden).

Helbing har även forskat kring andra liknande fenomen, såsom Mexican Wave ("Vågen"). Läs gärna Nature-artikeln Mexican waves in an excitable medium (PDF) eller kika på simuleringar som finns på sajten. Trafiksimuleringar: Microsimulation of road traffic with a time-continuous model för exempel (laddar en Java-applet direkt). Källkoden finns att ladda ner (långt ner i högerspalten). Gångtrafikanter i en korsning: Pedestrians Interacting at a Crossing.


Se även den relaterade sajten Crowd Dynamics Limited som bland annat innehåller avhandlingen Crowd Dynamics av G. Keith Still.

Abstract:
Crowd dynamics are complex. This thesis examines the nature of the crowd and its dynamics with specific reference to the issues of crowd safety. A model (Legion) was developed that simulates the crowd as an emergent phenomenon using simulated annealing and mobile cellular automata. We outline the elements of that model based on the interaction of four parameters: Objective, Motility, Constraint and Assimilation. The model treats every entity as an individual and it can simulate how people read and react to their environment in a variety of conditions, this allows the user to study a wide range of crowd dynamics in different geometries and highlights the interactions of the crowd with its environment. We demonstrate that the model runs in polynomial time and can be used to assess the limits of crowd safety during normal and emergency egress.

Over the last 10 years there have been many incidents of crowd related disasters. We outline deficiencies in the existing guidelines relating to crowds and, by comparison and contrast with the model, we highlight specific areas where the guides may be improved. We demonstrate that the model is capable of reproducing crowd dynamics without additional parameters thus satisfying Occam’s Razor.

We propose an alternative approach to assessing the dynamics of the crowd through the use of the simulation and analysis of least effort behaviour. The model is tested against known crowd dynamics from field studies, including Wembley Stadium, Balham Station and the Hong Kong Jockey club. Finally we test the model in a variety of applications where crowd related incidents warrant structural alterations at client sites. We demonstrate that the model explains the variance in a variety of field measurements, that it is robust and that it can be applied to future designs where safety and crowd comfort are criteria for design and cost savings.

Posted by hakank at 11:29 EM Posted to Dynamiska system | Komplexitet/emergens

augusti 16, 2003

Wolframs "A New Kind of Science"

Trots all kritik beställde jag till slut Wolframs A New Kind of Science (Ankos eller ANOKOS). Den kom häromdagen, en stor och tung tegelsten. Jag har ännu bara bläddrat i den, och den verkar mycket spännande. Tyvärr är jag tvungen att lägga den lite längre bak i bok-kön eftersom det är andra böcker som jag hellre vill läsa (dvs projekt att gå vidare med).

I dagens Science News-artikel In Search of a Scientific Revolution diskuterar man Ankos och försöker förklara vad som är så revolutionerande med boken. Det finns många bra länkar både och efter i artikeln.

Se även Jan Tångrings blogg-anteckning Chaitin refererar till Wolfram, som var den tipping point som fick mig att faktiskt beställa boken.

Posted by hakank at 05:37 EM Posted to Dynamiska system

augusti 04, 2003

Framsticks, ALife simulator

Framsticks är ett verktyg för att skapa och simulera ALife (artificial life). Man kan t.ex. göra 3D-filmer som är rätt fotorealistiska, några exempel finns här.

Jag har mest lekt med existerande konfigurationer och inte skapat så mycket eget. Men imponerande är det.

Ladda ner systemet kan man göra här. Finns för MS Windows och Linux. Varning! Jag har haft problem med att Linux-varianten är lite instabil. Har dock inte testat Windows-versionen.

Posted by hakank at 06:35 EM Posted to Dynamiska system

Matematiska och statistiska "självklarheter"

Thomas Schellings bok Micromotives and Macrobehavior handlar om hur beteende på individnivå kan påverka en grupps beteende, vilket i sin tur påverkar individen, vilket i sin tur.... Han ger många exempel på sådana fenomen såsom trafikköer, hur man väljer en plats i en föreläsningslokal, skickar julkort till varandra, hur man grupperar sig på fester etc.

En av de saker Schelling är mest känd för (han har även skrivit betydande verk inom spelteorin) är sin analys av segregering: om samtliga inom en befolkning kan acceptera ett blandat grannskap men kräver att det åtminstone finns minst 30% av grannar av "samma slag", så tenderar det att bli en rätt kraftig segregering. Det är alltså makrobeteende (segregering) som uppstår ur mikromotiv (minst 30% grannar av samma slag). Segregering inom bostadsorter, och grupperingar på fester är några exempel på detta.

Kapitel 2 ('The inescapable mathematics of musical chairs') handlar om vissa grundläggande "självklara" sanningar om aggregerade värden, dvs värden för en hel grupp (medelvärden etc) som man kanske inte så ofta tänker på eller inser vidden av. Schelling listar upp en rad sådana sanningar, t.ex. att det alltid finns någon som är först respektive sist när vi sorterar personer enligt något specifikt kriterium, t.ex. längd, betyg på ett prov eller inkomst. Han drar en hel del slutsatser, t.ex. vad man ska tänka på när man planerar trafikljus eller skidliftar.

[Mer om mikromotiv/makrobeteende och hur de kan simuleras kommer, som tidigare utlovats, inom en framtid.]

När jag läste detta kapitel om matematiska/statistiska "självklarheter" kom jag att tänka på några bra artiklar jag läste för ett tag sedan. De handlar om olika typer av feltänk som är mycket lätta att göra och som vi rätt ofta gör. Artiklarna kan förhoppningsvis öka känsligheten att detektera sådana feltänk.

Of birthdays and clusters. I data över en tillräckligt stor grupp finns det alltid någon typ av kluster att hitta, om man letar tillräckligt länge. Vi har en tendens att övertolka dessa kluster och dess betydelser.

One of the concepts that gets the media excited and brings a glow of expectation to the eyes of compensation lawyers is the cluster. Every time there is a disease outbreak, cluster-watching comes back into vogue, as is now happening in the UK during the foot and mouth epidemic.

The extreme value fallacy förklarar lite om en viss typ av elakartad 'data snooping' som övertolkar att det alltid finns någon som har högst eller lägst värde. Artikeln ger också en kort introduktion i den fascinerande statistiska tekniken extremvärdesanalys.

A very common example is the birth month fallacy, which recurs in the media several times a year. It usually takes the form of a headline such as People born in July are more likely to get toe-nail cancer or more fancifully Cancerians are more likely to get toe-nail cancer. What the 'researchers' have done is look at the statistics for each of the twelve months, pick out the biggest, and then marvel that it seems large compared with what you would expect for a random month.

Birth daze gör en något mer matematisk genomgång av ovanstående.

It's a record!: Rekord kan, per definition, endast förbättras. Artikeln diskuterar lite om konsekvenserna av detta enkla faktum.

(Det var bland annat ovanstående artiklar som fick mig att intressera mig för just ämnet extremvärdesanalys för ett bra tag sedan.)


Sajten där dessa artiklar finns, Number Watch, är en ständig källa till intressant, ibland provokativ, läsning. Programförklaring: This site is devoted to the monitoring of the misleading numbers that rain down on us via the media. Whether they are generated by Single Issue Fanatics (SIFs), politicians, bureaucrats, quasi-scientists (junk, pseudo- or just bad), such numbers swamp the media, generating unnecessary alarm and panic. ... .

Frequently Asked Questions ger en bra översikt över saker som behandlas.

Posted by hakank at 09:17 FM Posted to Dynamiska system | Statistik/data-analys | Comments (2)

juli 27, 2003

Systemdynamisk analys av Kuhns paradigmteori

Jason Wittenberg och John D Sterman gjorde 1999 en systemdynamisk analys av hur vetenskapliga teorier uppstår och försvinner, baserad på Kuhns paradigmteori.

Läs mer på Path Dependence, Competition, and Succession in the Dynamics of Scientific Revolution (PDF av hela dokumentet här).

Abstract: What is the relative importance of structural versus contextual forces in the birth and death of scientific theories? We describe a dynamic model of the birth, evolution, and death of scientific paradigms based on Kuhn's Structure of Scientific Revolutions. The model creates a simulated ecology of interacting paradigms in which the creation of new theories is stochastic and endogenous. The model captures the sociological dynamics of paradigms as they compete against one another for members. Puzzle solving and anomaly recognition are also endogenous. We specify various regression models to examine the role of intrinsic versus contextual factors in determining paradigm success. We find that situational factors attending the birth of a paradigm largely determine its probability of rising to dominance, while the intrinsic explanatory power of a paradigm is only weakly related to the likelihood of success. For those paradigms that do survive the emergence phase, greater explanatory power is significantly related to longevity. However, the relationship between a paradigm's `strength' and the duration of normal science is also contingent on the competitive environment during the emergence phase. Analysis of the model shows the dynamics of competition and succession among paradigms to be conditioned by many positive feedback loops. These self-reinforcing processes amplify intrinsically unobservable micro-level perturbations in the environment - the local conditions of science, society, and self faced by the creators of a new theory - until they reach macroscopic significance. Such dynamics are the hallmark of self-organizing evolutionary systems.

Koden för modellen finns att ladda ner, skriven i Dynamo. Tyvärr har jag inte Dynamo, och när jag försökte porta koden till Vensim gick det inte speciellt bra.

För mer om Kuhns och hans paradigmteori, se t.ex. google-kategorin Society, Philosophy, Philosophers, Kuhn, Thomas S.

Posted by hakank at 10:29 FM Posted to Dynamiska system | Filosofi

Journal of Artificial Societies and Social Simulation

Journal of Artificial Societies and Social Simulation är en mycket intressant (öppen) tidskrift som utkommer fyra gånger per år. Den innehåller papers om simuleringar av sociala system och teorier såsom sociala och komplexa nätverk, organisationer, undersökningar av sociologiska, politiska, ekonomiska och spelteoretiska teorier, samt även mer metodologiska betraktelser över sådana simuleingar. Det finns även längre och penetrerande recensioner av böcker i relaterade ämnen.

Några exempel på vad man kan läsa här:


Det är bland annat denna tidskrift som gjort mig storligen intresserad av agent-baserad modellering (agent-based modeling, ABM) som är en av teknikerna för att undesöka sociala och andra komplexa adaptiva system, t.ex. synkronisering och självorganisation i biologiska system.

Det är för övrigt just ABM som jag just nu håller på att kolla in, och det finns mycket att läsa, lära och programmera i ämnet. En liten drapa om mina findings kan nog förväntas inom några veckor, förevisande även några simuleringar (andras och kanske några egna).

Posted by hakank at 09:32 FM Posted to Dynamiska system | Social Network Analysis/Complex Networks

juli 23, 2003

Komplexitet i mjukvaruarkitektur

I forskningsrapporten Hierarchical Small Worlds in Software Architecture används tekniker från teorin om komplexa nätverk för att undersöka komponentstrukturen i flera olika större utvecklingsprojekt. Man hittar - naturligtvis! - "small worlds-"effekter och skafria beteenden.

Abstract : The components of a large software application do not interact in random ways. Instead, class diagrams exhibit remarkable topological similarities to other natural and artificial systems. The components of a large software application are very well connected because the mean shortest distance between them is very low in spite of having a relatively small number of connections per class. In addition, these diagrams are very heterogeneous. These measurements are of a general nature and are largely independent of the particular semantics of the application. As shown in this paper, and irrespective of the specific features of each system analyzed, the final outcome of software evolution is a small world, hierarchical class diagram with well-defined statistical properties. The consequences for software evolution are outlined.

Från rapportens avslutande kommentarer: The important point of our work is that different software architectures share the same universal topological features, that is, small-worldness and scale-free behavior. This is a very surprising result and raises several interesting questions about how we (as human designers) organize knowledge and express the inner workings of a very complex, and abstract machine.

Posted by hakank at 10:27 EM Posted to Dynamiska system | Systemutveckling

juli 22, 2003

Edge

Det senaste numret av Edge innehåller: The Politics of Christianity: A Talk with Elaine Pagels.. Det förra var om Murray Gell-Mann.

Posted by hakank at 07:48 FM Posted to Dynamiska system

juli 14, 2003

Litterärt om kaosteori - fortsättningen

För nästan en månad sedan (den 18 juni) skrev jag lite om Litterärt om kaosteori med några referenser till icke-fack-böcker om kaosteori.

I dag frågade Tatjana Samopjan om jag visste några nordiska författare som skrivit om kaos. Hennes fråga finns i kommentarerna till ovanstående inlägg, liksom mitt, ganska utsvävande, svar.

Jag fick sedan även tipset om att Unni Drougges roman Regnbågens tid skulle beröra kaosbegreppet, fraktaler närmare bestämt. En recensioner där detta diskuteras är Inger Littbergers I Regnbågens tid: bland humana häxor, healers och hackers i Unni Drougges värld (finns lite längre ned på sidan).

Fler tips om nordisk och icke-nordisk skönlitteratur emottages tacksamt.

Posted by hakank at 06:38 EM Posted to Böcker | Dynamiska system | Comments (1)

juli 11, 2003

Resampling - Statistik utan tårar

När jag nu läser om systemdynamik och dess förespråkare har jag flera gånger kommit att tänka på Julian Simons Resampling-projekt som innebär att lära ut 'statistisk utan tårar'.

En parentetisk not: Julian Simon är möjligen mer känd som en "miljöoptimist"/"teknikoptimist" vilket - intressant nog - går stick i stäv mot slutsatser som vissa systemdynamiker kommit fram till. Se till exempel Julian Simons Bet. Notera att jag inte alls är någon expert i denna debatt, knappast - och tyvärr - inte ens newbie. Jag vet inte heller om Simons miljöoptimism är kopplad till hans resamplingprojekt på något sätt, men inget jag läst i hans resamplingsskrifter har antytt detta, mer än möjligen i något förfluget exempel.

Efter denna utvikning: tillbaka Simons resampling. Simon var mycket kritiskt till hur statistisk analys lärs ut i skolorna och används av statistiker. Den statistika formalismen - menar Simon - har dels som konsekvens att det är få som förstår vad statistikerna pratar om och därmed har svårt att följa tankegångar och slutsatser som bygger på statistisk analys. Dels passar den statistika teorin endast för vissa typer av problem som ofta inte är speciellt realistiska i "den verkliga världen". Ett annat problem är att även enklare sannolikhetsteoretiska resonemang är svårt för en icke invigd att ta till sig. Hans lösning var att man i stället skulle lära ut en teknik för att göra analyser tillgängliga för alla - en statistik utan tårar.

Likheten mellan Simon och systemdynamikerna är att man försöker få ut ett mer tillgängligt sätt att använda matematiska metoder till dem som inte är matematiskt skolade. För Simon var det den matematiska statistiken som kritiseras, för systemdynamikerna var det dynamiska system med differens-/differentialekvationer. Båda mycket lovvärda projekt!

Här kan man också jämföra med t.ex. John Allen Paulos Innumeracy, som är en mycket arg och mycket bra bok om att vi är väldigt dåliga på att förstå även enkla statistiska/sannolikhetsteoretiska resonemang och konsekvenserna av detta. Paolos böcker ger dock ingen systematisk lösning på hur man löser problemet, villket Simon gör.

Simons lösning heter alltså resampling, vilket helt enkelt innebär är att man simulerar problem i stället för att försöka få in dem i statistikens matematiska apparat (som kan vara mycket komplicerad att förstå). Simuleringen görs genom att programmera problemet med ett programspråk. Simon skapade ett system med ett eget programspråk, Resampling Stat, som endast är till för sådana simuleringar, vilket gör det enkelt att förstå och använda. I ärlighetens namn måste jag säga att jag inte kört just Resamplig Stats speciellt mycket; i stället har jag använt statistikspråket R, Java eller andra generella språk. Däremot har jag översatt mycket Resampling Stat-kod, och kortare tester med Resampling Stats gör att jag tycker det verkar lätt att använda för någon som inte har programmeringserfarenheter.

Väldigt mycket mer om Resamplig Stats finns på www.resample.com. En utomordentligt trevlig introduktionsbok Resampling: The New Statistics finns online.

Båda systemdynamikernas och Simons resamplingsmetoder går alltså ut på att förstå verkliheten genom att simulera den, däremot gör systemdynamikerna det vanligen i mycket mer grafiskt aptitliga system.

För några månader sedan skrev jag en hel del om resampling etc i Lite om resampling, simulering, sannolikhetsproblem etc. som jag hänvisar till. Sidan innehåller en hel del relaterade länkar, och en massa simuleringar (skrivet främst i R) av sannolikhetsteoretiska problem av olika digniteter.

Personligen anser jag att man bör, om det är möjligt, kombinera (Simons) simuleringsmetoder och mer formell statistisk analys. Man kan t.ex. använda resampling/simulering för få en känsla för problemet, prototypa problemet, kontrollera resultat eller om man inte är expert inom statistisk analys.

I den (formella) statistiska analysen finns det även något som heter resampling som har mycket av Simons idé, och är en accepterad och matematiskt väl underbyggd teori. Men den är inte lika enkel att ta till sig som Simons mer pedagogiska variant.

Ett tips är att börja läsa Simons skrifter och sedan läsa mer formell statistik och sannolikhetslära. En utmärkt introduktion i sannolikhetslära är Introduction to Probability av Charles M. Grinstead och J. Laurie Snell, som också använder mycket simulering för att visa hur begreppen hänger i hop. Det finns kod skriven i Mathematica, Maple, True Basic och Java Applets. Själv gjorde jag exempel och övningar i R.

En utmärkt svensk bok om sannolikhetsproblem är Sant eller sannolikt : Tankar kring matematik, statistik och sannolikheter av Allan Gut. Det är dock ingen lärobok utan innehåller en mängd essäer i ämnet.


En sista not: Jag har även testat att modellera några enklare sannolikhetsproblem, av den typ som Simon koncenterar sig på, i systemdynamikprogrammet Vensim. I vissa fall kändes de inte riktigt lika enkelt som att programmera problemen i R eller Java, möjligen är detta en vanesak. Fortsatt forskning pågår...

Posted by hakank at 11:15 FM Posted to Dynamiska system | Statistik/data-analys

juli 04, 2003

Systemdynamik

En av anledningarna till min relativa tystnad de senaste dagarna är att jag kollat in mer om dynamiska system, det som Thorvald Freiholtz skrev om härom veckan. Det är väldigt intressant.

Jag har skrivit lite om mina första erfarenheter, speciellt olika dokument att läsa, system att testa etc. Dokumentet är dock för stort för att ha i min blogg, därför finns det som ett separat dokument: Systemdynamik - System Dynamics.

Och om jag är tyst den närmsta tiden beror det kanske på att jag sitter och modellerar.

Posted by hakank at 08:26 EM Posted to Dynamiska system | Comments (6)

juni 29, 2003

Complexity Digest

Senaste numret av Complexity Digest är ute.

Några intressanta saker:

Posted by hakank at 06:05 EM Posted to Dynamiska system

juni 24, 2003

Komplexa system och software engineering

Detta är en kommentar till Peter Lindbergs artikel från 9 mars i år Software systems are complex systems. Se även hans artikel Network science and software från 8 maj. Peter vill bl.a. ha tips på lite nyare böcker om komplexa system, speciellt med inriktning mot software engineering.

Här är lite nyare (inköpta men icke lästa) böcker om komplexitet och liknande som kan vara intressanta:


  • Steven Strogatz Sync, där han bland annat förklarar sina teorier om kopplade oscillatorer, dvs vad som gör att delar i (naturliga) system synkar med varandra, t.ex. eldflugor. Den kom i år, så den är rackarns ny.
  • Mark Buchanans Ubiquity: Why Catastrophes Happen (2002 enligt Amazon). Buchanan har även skrivit om komplexa nätverk i sin Nexus.
  • Kauffmans At Home in the Universe (1996). Många komplexitetiker hänvisar till Kauffman, vilket gjorde att jag beställde denna bok.

Det Peter skriver om kopplingen till software engineering fick mig också att tänka på en del av teorierna i social network analysis. Några förflugna tankar:


  • hur man med dessa modeller kan mäta graden av sammansättningar (cohesion) av en grupp (här: program, moduler eller system). "Om man kan mäta något så förstår man det bättre"
  • hur olika entiteter i en grupp (här: klasser eller komponenter) påverkar en grupp genom sin position i strukturen
  • "strukturella hål", som är ett högnivå-teori om hur/när/var en aktör ska stiga in i en struktur för att hitta en optimal nisch. Det handlar alltså främst om konkurrens, men jag tror att det skulle kunna vara något även för systemutveckling. Bibeln att läsa är Ronald Burts Structural Holes: The Social Structure of Competition, som utvidgar social network analysis till att gälla konkurrens
  • använda t.ex. Barabasis nätverks-modell för att mäta sårbarheten i en systemstruktur.

Posted by hakank at 03:00 EM Posted to Dynamiska system | Komplexitet/emergens | Social Network Analysis/Complex Networks | Systemutveckling

juni 18, 2003

Edge - The Third Culture

Kan rekommendera ett besök på Edge - The Third Culture. Intervjuer (Real Audio), korta sammanfattningar etc om spjutspetsforskning och dess förespråkare.

I detta nummer intervjuas t.ex. Matt Ridley of Genome fame. För ett tag sedan var min nye husgud Steven Strogatz intervjuad, Gerd Gigerenzer som skrivit några intressanta böcker om praktiskt risktagande och sannolikhetstänkande (en kort biografi), Marvin Minsky, Per Bak, m.fl m.fl..

Notera att det ibland kan vara lite trixigt att hitta intervjuerna, men det tenderar fungera om man klickar på menyn till vänster.

Posted by hakank at 10:51 EM Posted to Dynamiska system | Sajter | Comments (1)

Böcker för tillfället - och varför

Följande är en lite mer strukturerad samling av böcker och andra skrifter med fler än 5 sidor som jag för tillfället läser, har läst eller bryr mig om. Jag hade tänkt mig att detta skulle bli ett återkommande tema framgent.

Som ni möjligen förstår är jag just nu inne på kaos/dynamiska system. Anledningen är att när jag läste om komplexa nätverk tyckte jag att vissa teorier och frågeställningar hängde lite i luften, och för att få ett mer grundat fundament i detta behöver jag förkorvra mig i komplexa system (a.k.a. dynamiska adaptiva system etc), vilket i sin tur kräver en djupdykning i de matematiska modellerna för dynamiska system (a.k.a. kaosteori).

Mycket av det jag läste för en 15 år sedan när kaosteorin var som populärast har jag glömt, så jag slukar det jag kommer över. En del av länkarna har jag redan nämt (artiklarna "Differentialekvationer - lite mer praktiskt" och "Kaosteori - den riktiga historien?" tidigare idag) men här är de lite mer samlade.

Steven Strogatz Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry and Engineering.
- höjdarbok. Mycket pedagogisk. Har många bra exempel, mestadels från fysikens värld men även från biologi och sociala verksamheter, t.ex. Romeo och Julias kärleksliv.

Kaplan och Grass: Understanding Nonlinear Dynamics. Denna bok har jag upptäckt är bra som komplement till Strogatz eftersom boken koncentrerar sig på biologiska exempel. Ett mycket bra kapitel om booleanska nätverk och cellulära automater piggar upp och gör bilden mer komplett än Strogatz. I dessa kapitel en viss närhet till de problem som finns i komplexa nätverk.

Gleicks lite skvalleraktiga Chaos - denna läser jag om, mest som sänglitteratur.

Andrew Ilachinski, Land Warfare and Complexity, Part I: Mathematical Backgorund and Technical Sourcebook (PDF). Detta är första delen av två och ger översiktligt grunderna i komplexitetsteori (inklusive kaos, cellulära automater, neurala nät, genetiska algoritmer, self-organized criticality) för att sålunda försöka skapa en teori kring landsstrider (riktigt krig, inga dataspel eller så). Inte så mycke bjäfs som det brukar vara i andra likande översikter och hajpen som naturligtvis finns där hålles med strama tyglar.

Essäsamlingen Universality in Chaos med de flesta av klassikerna. Tyvärr saknar jag Ruelle ochTakens "On the Nature of Turbulence". Har du den elektroniskt får du gärna kontakta mig!

Systemet XPPAUT som är förträffligt för att modellera dynamiska system. Det krävs en del inkörningstid men har i gengäld en massa exempel som visar hur man skriver de flesta standardsystemen.
Ett sådant exempel är dynamiken i en droppande kran, och det kommer kommer jag ihåg som en av de intressantaste sakerna i kaosforskningen: att man kan hitta kaos i så enkla och jordnära saker som en droppande kran. (Det var för övrigt då jag började bli intresserad av talteori och hittade en del lustiga samband....) Det är även möjligt att modellera (biologiska) neurala nätverk, cellulära automater fast det kräver en del trixande.

Jag har också börjat kika på Stephen Wolframs artiklar om celluära automater. Just nu känns hans A New Kind of Science lite väl tung, dyr och nerskriven. för att jag ska köpa och framförallt läsa den.

Andra böcker som eventuellt är på gång:
Yaneer Bar-Yam:s online-bok Dynamics of Complex Systems.

En annan onlinebok: Julien C. Sprott Strange Attractors: Creating Patterns in Chaos (PDF), men jag tror att den är lite redundant om man läser flera av ovanstående böcker.

Posted by hakank at 04:56 EM Posted to Böcker | Dynamiska system

Differentialekvationer - lite mer praktiskt

Här är några sajter (och en bok) som fokuserar på differentialekvationer och dess applikationer, vilket innebär fysiska, biologiska eller sociala system. Det verkar som om de amerikanska universiteten kring 1998 beslöt att man skulle förbättra undervisningen i differentialekvationer (dynamiska system) så att de blev mer lättförståeliga, t.ex. genom att mer fokusera på grafiska metoder och applikationer.

En av de bästa interaktiva sajterna är http://www.awlonline.com/ide/index.html som innehåller en herrans massa exempel, allt från vanliga pendlar till Steven Strogatz Romeo och Julia-exempel från Nonlinear Dynamics and Chaos (jepp, det är komplexa nätverk-Strogatz!). Exemplet finns här.

En annan sajt, där man kompletterar en bok (PDF-filer) med Java-exempel är
Chaos on the Web. (Tips: Jag hade problem att skriva ut filerna via AcroReader så jag fick använda XPDF för att skapa en Postscript-fil och sedan skriva ut.)

Slutligen, en kurs i matematisk modellering
Introduction to Continuous Mathematical Modeling där föreläsningsanteckningarna ger många bra exempel på hur man analyserar verkligheten med hjälp av differentialekvationer.
Favoritexempel:


Notera att vissa av dessa skrifter inte är helt triviala att följa, men man får en bra känsla för vad man kan göra.

Posted by hakank at 03:01 FM Posted to Dynamiska system

Litterärt om kaosteori

För de flesta av mina intressen brukar jag försöka hitta skönlitterära verk (böcker eller filmer) som behandlar ämnet. T.ex. har Asimovs Stiftelsetrilogi (eller nonologi?) inspirerat mig vad gäller statistisk analys, data mining etc.

Vad gäller kaosteori (eller dynamiska system som det lär heta när man ser det från den matematiska sidan) läste jag häromdagen Tom Stoppards Arcadia, ett skådespel på en cirka 130 sidor som till viss del handlar om en del av de saker som kaosteorin handlar om: känslighet för initialvillkor, iterativa system etc. Det är en rolig (dråplig) pjäs med många bottnar. Till viss del tycker jag att man märker att Stoppard använt Gleicks "Chaos"-bok som underlag för "det tekniska" (fast jag har just nu igen aning hur jag själv skulle skriva det).

Några sajter som handlar om pjäsen och dess kopplingar till kaosteorin med bilder och allt:

Jag har inte läst något av Stoppard tidigare men Arcadia gav mig mersmak. Boken jag har (Tom Stoppard Plays 5: Arcadia, the Real Thing, Night and Day, Indian Ink, Hapgood) innehåller även pjäsen Hapgood som ska handla om Kvantfysik om jag förstått det rätt.

För övrigt kan jag rekommendera några böcker som är något mer perifert kopplade till kaosteori, nämligen Thomas Bass två "projekto-grafier": Först är det The Eudaemonic Pie (eller The Newtonian Casino) som handlar om ett gäng kaosforskare (några mycket kända, bland annat Doyne Farmer och Norman Packard som skrev flera tidiga skrifter inom kaosforskningen) som försöker slå kasinon genom att studera roulettehjulens beteende. Sedan är det The Predictors som handlar om i princip samma gäng som skapar ett företag (The Prediction Company) som ska tjäna en massa pengar på börsen. Här handlar det om genetiska algoritmer och neurala nätverk.

Båda dessa böcker är mycket roliga att läsa och rekommenderas som säng-/hängmatte-litteratur för en som läst allting.

Posted by hakank at 02:22 FM Posted to Böcker | Dynamiska system | Comments (8)

Kaosteori - den riktiga historien?

Under tiden jag återigen läser bl.a. Gleicks Chaos: Making a New Science har jag även läst följande historieskrivning om hur kaosteorin uppstod/skapades:
Writing the History of Dynamical Systems and Chaos: Longue Dur´ee and Revolution, Disciplines and Cultures (PDF) av David Aubin och Amy Dahan Dalmedico. Cirka 67 sidor.

Uppsatsen verkar klart mycker mer vederhäftigt än Gleicks populärt hållna, effektsökande och amerikaniserande beskrivning, och - därigenom - något mer svårtillgänglig.

Det är många intressanta saker som nämns t.ex. kopplingen till katastrofteorin, men tyvärr är alltför många refererede arbeten på franska.

Posted by hakank at 01:55 FM Posted to Dynamiska system | Comments (4)