« september 2009 | Main | februari 2010 »

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