Så kan datorn översätta språket bättre
Vid automatöversättning krävs stora datamängder, något som saknas för små språk. Då blir datahanteringen mer komplex – och tar längre tid. En menings innebörd representeras ofta av grafer. Genom att göra grafernas uppbyggnad tydligare kan verifikationsalgoritmen lättare gissa ordning och struktur i grafen – och översättningen går snabbare.
De 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. 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.
Gissa ordning och struktur
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. Genom att göra grafernas uppbyggnad tydlig kan många av svårigheterna hanteras mycket enklare.
Petter Ericson har i sin avhandling vid Umeå universitet utvecklat en modell där både struktur och ordning möjlig att läsa ut direkt. Verifieringen kan då 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.
Avhandling:
Order-preserving Graph Grammars
Kontakt:
Petter Ericson, Institutionen för datavetenskap, Umeå universitet, petter.ericson@umu.se
