NYHET När datorer behöver representera en menings innebörd används ofta grafer, bestående av noder och kanter, som är beräkningsmässigt svåra att verifiera. Genom att göra grafernas uppbyggnad tydlig kan många av svårigheterna hanteras mycket enklare. Petter Ericson försvarar resultaten i sin avhandling måndagen den 4 februari vid Umeå universitet.
Petter Ericsson, doktorand vid institutionen för datavetenskap.
BildUlrika BergforsDe vanligaste metoderna för automatöversättning, exempelvis Google Translate, är baserade på väldigt enkla regler som utnyttjar enorma mängder data för att skapa goda översättningar, något som gör att översättningar till mindre språk ofta håller betydligt lägre kvalitet. Genom att använda mer komplexa metoder kan man uppnå högre kvalitet med mindre data, men själva databehandlingen kan i stället snabbt ta ohanterligt mycket datorkraft i anspråk.
Hemligheten ligger i att begränsa hur många olika gissningar som måste göras under verifikationsprocessen. I de flesta formella modeller behöver en verifikationsalgoritm gissa både ordning och struktur i grafen i flera olika steg, vilket lätt kan ta exponentiellt lång tid.
I Petter Ericsons modell är i stället både struktur och ordning möjlig att läsa ut direkt, och verifieringen kan anta att ingenting ändras under körning.
Det finns ett antal förutsättningar för att hans formalismer ska kunna användas, vilket begränsar användningsområdena, men preliminära tester ser lovande ut för de semantiska grafer som motiverat arbetet. Grafer används inom många områden, inte bara språkbehandling, och det finns goda förhoppningar för att våra formalismer ska ha andra tillämpningar.
- En central del av resultaten är att vi skapar en direkt koppling mellan
vissa grafer och enklare strukturer för vilka det redan finns välkända effektiva algoritmer. Som bonus blir det relativt självklart att bevisa ett stort antal relaterade egenskaper, även om det i flera fall dykt upp både en och två oväntade komplikationer, säger Petter Ericson.
I förlängningen kan de nya modellerna leda till förbättrad språkförståelse och automatöversättning, men de är såpass generellt uttryckta att de teoretiskt skulle gå att använda i nästan alla områden där grafers struktur och sammansättning behöver verifieras algoritmiskt på ett eller annat sätt.
Petter Ericson kommer från Holmsjön utanför Umeå och har studerat civilingenjörsprogrammet i teknisk datavetenskap vid Umeå universitet.
Text: Ingrid Söderbergh
Läs hela avhandlingen digitalt
Måndagen den 4 februari försvarar Petter Ericson, Institutionen för datavetenskap vid Umeå universitet, sin avhandling med titeln: Order-preseving Graph Grammars. Svensk titel: Ordnade grafgrammatiker.
Disputationen äger rum klockan 13:00 i sal MA 121 vid Umeå universitet.
Fakultetsopponent är Professor Sebastian Maneth, Department of Computer Science, University of Bremen.
