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
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.
