Huvudmeny

2014-03-18 12:01

Se in i framtiden med genetisk programmering


Med tekniker för prediktiv modellering kan man förutspå allt från kunders köpbeteende och sjukdomar till en golfspelares handicap. Bara man har tillräckligt många exempel. I en avhandling vid Högskolan i Borås har Rikard König anpassat tekniken genetisk programmering så att den kan användas till detta.

Rikard KönigAvhandlingen, Enhancing Genetic Programming for Predictive Modeling, handlar om maskininlärning och mer specifikt prediktiv modellering, ett område inom datavetenskap. Maskininlärning innebär att få datorn att lära sig något – att datorn ska bli intelligent. Prediktiv modellering är ett brett område inom maskininlärning där datorn lär sig utifrån positiva och negativa exempel, hittar samband och förklarar varför det blir på ett visst sätt.

Inom prediktiv modellering finns en uppsjö tekniker som används för att ta fram modeller som kan förutspå allt möjligt, ett exempel kan vara vilket gensvar man kan förvänta sig på reklam. Eftersom teknikerna är generella kan man förutspå egentligen vad som helst så länge man har tillräckligt många tidigare exempel, alltså tillräckligt mycket information. Målet med prediktiv modellering är att hitta en träffsäker modell och helst en som också förklarar någonting man tidigare inte visste.

Genetisk programmering (GP) är en generell optimeringsteknik som är baserad på Darwins teorier om evolutionen och det naturliga urvalet. Det är en teknik som egentligen inte är designad för prediktiv modellering.
– I min avhandling presenterar jag flera förbättringar som ökar träffsäkerheten och tolkningsbarheten för modellerna skapade med GP. Det finns många forskare som jobbar med GP men mina lösningar är unika, säger Rikard König, doktorand vid Institutionen Handels- och IT-högskolan vid Högskolan i Borås.

För att ta fram en modell med hjälp av GP börjar man med, till exempel, tusen slumpmässiga modeller och låter dem tävla med varandra. Man beräknar hur mycket fel modellerna gör på kända exempel och baserar ett naturligt urval på resultatet. De mest träffsäkra modellerna får större chans att överleva och skaffar ”barn” – man parar två modeller. Då blir ”barnen” kombinationer av sina föräldrar och bildar en ny, förhoppningsvis starkare generation. Ett fåtal modeller kan även utsättas för en mutation precis som i naturen.
– Den nya generationen utvärderas på samma sätt mot de kända exemplen. De tävlar, parar sig och ger upphov till en ny ännu starkare generation. Processen upprepas tills en tillräckligt träffsäker modell har hittats. Det fascinerande är att evolutionen är ett så kraftfullt sätt att söka över alla möjliga lösningar, säger Rikard König.

GP har flera lämpliga egenskaper för prediktiv modellering. Ett exempel är att sökningen är oberoende av den modellens representation. Detta gör att den exakta representationen och sättet man mäter felet på kan anpassas för det enskilda problemet. Det är inte normalfallet för traditionella prediktiva tekniker. Samtidigt får tekniken problem när en mycket komplex modell krävs då sökningen sker över alla möjliga lösningar och att antalet lösningar växer exponentiellt med komplexiteten på modellerna.
– Ett exempel på en av mina förbättringar är en hybridteknik för att skapa en träffsäker och tolkningsbar modell när sökrymden blir extremt stor, det vill säga när en modell med hög komplexitet krävs. Lösningen är att skicka in relativt starka modeller skapade av en traditionell prediktiv teknik i en generation för att guida sökning i en lovande riktning.

Som ett led i sin forskning har Rikard König även tagit fram en applikation som realiserar forskningsresultaten. Programmet går att ladda ner på www.grex.se.

Rikard König arbetar i flera forskningsprojekt där lösningarna kan komma till användning. Bland annat ett i samarbete med Scania där data från tiotusentals lastbilar har sparats och ska analyseras för att förklara förarens påverkan på bränsleförbrukningen. Ett annat exempel, som också visar på hur generell tekniken är, ett nytt projekt där golfsvingar från 500 golfare ska analyseras. Här är tanken att hitta generella förklaringar för vad som skiljer bra svingar från dåliga men också att automatiskt kunna rekommendera övningar för en enskild golfare utifrån just dennes förutsättningar.

Exempel:
Genetisk programmering

Ovanstående modell är skapad med G-REX och kan användas för att förutsäga om en patient har diabetes (om ett test visat positivt eller negativt resultat). Modellen är skapad utifrån data om 700 patienter och grundas på ”plas” dvs. ”plasma glukos” koncentration, ”insu” dvs. 2-Hour serum insulin, ”age” dvs. ålder och ”mass” dvs. BMI. Om ett test är sant går man till vänster i trädet annars till höger. Ex: Vänster gren av trädet säger att: Ett lågt plas och insu värde är tecken på att men ej har diabetes (plas <= 112 och insu<= 156). Är insu högre än 156 har patienten trots detta troligen inte diabetes om denne är högst 35 år.

Text & bild: Anna Kjellsson
Illustration: Rikard König