Ordningen i naturligt språk svårt för datorn att förstå

Martin Berglund har utvecklat algoritmer och metoder för att med datorers hjälp förstå strukturen i text och information, i de fall där ordningen spelar stor roll. Ett av studiens fokus ligger på att uttyda meningar och strukturer som har sammanflätats med annan irrelevant information, ett problem som liknar att uttyda hur en kortlek var ordnad innan den blandades en gång. Martin försvarar sin avhandling vid Umeå universitet onsdagen den 22 maj.

Martin Berglund har forskat om problemet att få datorer att räkna ut hur strängar av symboler kan genereras av enkla system av regler, givet att maskinen får både strängen och reglerna.

– Det omedelbaraste exemplet är i naturligt språk där det finns ett, visserligen stort, antal regler som bestämmer vilka ord som kan sammanfogas med vilka, och akten att läsa och förstå en text görs genom att undermedvetet förstå vilka regler som använts för att konstruera den. Att få datorer att helt förstå naturligt språk är därför ett svårt problem, förklarar Martin Berglund.

Ett särskilt tydligt exempel på komplicerad ordning i naturligt språk är bruket av ordet "respektive", vilket kan användas i meningar som "Anna, Hans och Johan fick 20, 30 och 40 kronor respektive", där den första listningens ordning reflekteras i den andra. Denna typ av struktur kan hanteras av så kallade milt kontextberoende grammatiker, en typ av regelsystem som kan uttrycka komplicerade språk men har en hög beräkningskostnad vid tolkning.

Naturligt språk är dock bara ett av områdena där denna typ av regelbaserad struktur med ordning figurerar, man kan också tänka sig säkerhetssystem som givet ett händelseförlopp på formen "12:04 öppnas dörr A, 12:05 används nyckelkort X i dörr C, 12:09 stängs dörr A, ..." ska tolka huruvida en viss delsekvens har någon speciell betydelse. Det vill säga, alla dörröppningar hänger inte ihop, men möjligen finns det urval av dörröppningar som tillsammans utgör ett misstänkt beteende.

– Denna typ av sammanflätade förlopp, där oberoende sekvenser blandats på det sätt man blandar en kortlek, hanteras av så kallade shuffle-formalismer. Också dessa har många intressanta beräkningsaspekter, säger Martin Berglund.

 Avhandlingen behandlar ytterligare typer av regelsystem, och de beräkningsmässiga problem de medför för tolkning av strängar på datorer. I de flesta fall är de beräkningsproblemen visserligen svåra, men faller i en kategori där de tycks praktiskt lösbara.

– Arbetet lägger teoretiska grundstenar för datorers förståelse av mänskligt språk och förmåga att känna igen mönster i en kaotiskt ordnad verklighet.

Om disputationen: 
Onsdag den 21 maj försvarar Martin Berglund, institutionen för datavetenskap vid Umeå universitet sin avhandling med titeln: Compexities of order-related formal language extensions. Svensk titel: Kompexiteter hos ordnings-relaterade utökningar av formella språk.
Disputationen äger rum klockan 13:15, i sal N320 i Naturvetarhuset.
Fakultetsopponent är Professor Markus Holzer, Institut Für Informatik, Justus-Liebig-Universität Giessen, Germany.
Huvudhandledare är Frank Drewes.

För mer information kontakta gärna:
Martin Berglund, institutionen för datavetenskap
Telefon: 070-33 42 841
E-post: martin.berglund@cs.umu.se

Avhandlingen är publicerad digitalt 

Högupplöst porträttfoto på Martin Berglund. Foto: Ingrid Söderbergh