Borgmästaren äter pizza med bestick: Hur man lär datorn satsanalys
1/2014

Joakim Nivre

Borgmästaren äter pizza med bestick: Hur man lär datorn satsanalys

Hur lär man en dator att ta ut satsdelar med en hastighet av 10 000 meningar i sekunden? Detta är en utmaning för världens språkteknologer när företag som Google, Microsoft och Yahoo! vill analysera all text som finns på Internet. Lösningen består än så länge av snabba algoritmer, statistiska modeller och en god portion traditionell grammatik.

Informationshantering på Internet har historiskt sett byggt på enkla metoder som exakt matchning av nyckelord i texter. Om man söker på ”grammatik”, hittar man de dokument som innehåller ”grammatik” (men kanske inte dem som innehåller ”grammatisk” eller ”syntax”). I takt med att de tekniska resurserna har förbättrats, har emellertid också användarnas krav skärpts och alltmer sofistikerade metoder har utvecklats för att med större precision tillgodose våra informationsbehov. En viktig pusselbit har då visat sig vara gammal hederlig satslösning, det vill säga att analysera meningar genom att ta ut satsdelar såsom predikat, subjekt och objekt. Detta är egentligen inte är särskilt förvånande när man tänker närmare på saken. Om en dator till exempel ska kunna svara på frågan ”Ska Microsoft köpa Nokia?”, räcker det inte med att den kan hitta dokument som innehåller orden ”Microsoft”, ”köpa” och ”Nokia”. Den måste också kunna avgöra huruvida ”Microsoft” är subjekt och ”Nokia” objekt till predikatet ”köpa”. Dessutom måste den kunna avgöra huruvida texten i fråga är en trovärdig källa, men det är ett problem som vi lämnar därhän i denna artikel.

Så varför kan vi inte lära datorer att ta ut satsdelar på samma sätt som elever i skolan? Vad är det som sker? Någon ”köper”. Vem är det som köper? ”Nokia”. Och så vidare. Kruxet är att denna fråga-svar-metod förutsätter att eleven redan förstår innebörden i meningen ”Microsoft köper Nokia”. Och datorer förstår egentligen ingenting, mer än möjligen att meningen är en sekvens av tre enheter som vi kallar ”ord” och som i sin tur består av olika bokstäver. Det är ungefär som om vi skulle be våra elever att ta ut satsdelar i en mening på ett för dem okänt språk och skriftsystem (här illustrerat med en översättning av ”Microsoft köper Nokia” till Hindi i skriftsystemet devanagari):

SB-114_Nivre_1.jpg

På något sätt måste vi därför ge datorn en möjlighet att känna igen återkommande mönster i språket, så att den kan lära sig att ”köper” är ett verb som ofta förekommer med subjekt och objekt. Om vi sedan ska använda den satslösande datorn i ett system för informationssökning på Internet, måste analysen dessutom gå med blixtens hastighet så att vi kan analysera miljarder dokument varje dag.

Med dagens språkteknologi är det tre väsentliga ingredienser som måste till för att lösa problemet. Den första är en stor samling av grammatiskt analyserade meningar, en s.k. trädbank. Den andra är ett sätt att bryta ned analysen i små steg som är så enkla att de kan utföras helt mekaniskt av en dator, dvs. en algoritm för satslösning. Det tredje är en statistisk modell för maskininlärning, som gör det möjligt för datorn att lära sig av exemplen i trädbanken. Låt oss i tur och ordning titta på dessa tre komponenter.

Trädbanker

Huruvida man bäst lär sig grammatik med hjälp av regler eller exempel är en gammal tvistefråga. Tidiga försök att skapa datorer med språkförståelse byggde till övervägande del på regler skapade av lingvister, men man har med tiden kommit fram till att språket är så rikt och varierat att det inte låter sig beskrivas med en liten mängd formella regler.

Därför har man i stället övergått till att skapa så stora samlingar av exempel som möjligt och att programmera datorn till att göra generaliseringarna själv. Detta betyder inte på något sätt att lingvisterna har blivit överflödiga. För att resultatet ska bli bra krävs nämligen att de exempelmeningar som datorn lär sig av är annoterade med en korrekt grammatisk analys, vilket än så länge bara kan göras av mänskliga experter. Så här kan en annoterad mening till exempel se ut:

 SB-114_Nivre_2.jpg

Analysen består av en uppmärkning med ordklasser (under meningen) och en dependensanalys (ovanför meningen) som väsentligen är en traditionell satslösning som visar att ”åt” är predikat, ”Borgmästaren” subjekt, ”pizza” objekt och ”med bestick” adverbial. Den senare har formen av ett träd (i matematisk mening), vilket är skälet till att en samling annoterade meningar vanligtvis kallas för en trädbank.

En viktig sak att lägga märke till är att analysen visar hur man ska lösa upp den strukturella flertydighet som finns i meningen. Om vi till exempel ersätter ordet ”bestick” med ordet ”svamp”, ser vi att prepositionsuttrycket teoretiskt sett kan vara antingen adverbial (bestämning till verbet ”åt”) eller attribut (bestämning till substantivet ”pizza”). Att på detta sätt visa den mest plausibla tolkningen av ett stort antal konkreta exempelmeningar är själva poängen med en trädbank (i motsats till en samling abstrakta grammatikregler).

Ju fler meningar trädbanken innehåller, desto bättre kan datorn lära sig språket och för att få ett bra resultat krävs tusentals meningar. Samtidigt är manuell satslösning ett tidskrävande arbete, så de trädbanker som finns i dag innehåller sällan mer än 50 000 meningar.

Algoritmer

Eftersom en dator bara kan utföra enkla mekaniska instruktioner, måste vi tillhandahålla en instruktion som entydigt och enkelt visar hur man steg för steg bygger upp en grammatisk analys. En sådan instruktion kallas för en algoritm och liknas ofta vid ett matlagningsrecept som steg för steg förklarar hur man till exempel lagar lasagne. En mycket enkel algoritm för satslösning kan se ut så här:

1. För varje ord x från början till slutet av meningen gör följande:

1.1. Märk x med sin ordklass

1.2. För varje ord y som föregår x i meningen gör följande:

1.2.1. Om x är bestämning till y med funktion z, sätt ut en båge y à x med etikett z

1.2.2. Om y är bestämning till x med funktion z, sätt ut en båge y ß x med etikett z

Genom att utföra denna algoritm kan datorn i ett ändligt antal steg konstruera en grammatisk analys för vilken mening som helst. Det kvarstår dock ett problem. Hur ska datorn veta vilken ordklass den ska sätta på ordet x? Och hur ska den veta om x är bestämning till y med funktion z (eller tvärtom)? Det är detta problem vi löser med maskininlärning.

Maskininlärning

Maskininlärning handlar enkelt uttryckt om att använda empiriska data för att skapa sannolikhetsmodeller. På samma sätt som vi exempelvis kan förutsäga aktiekursers utveckling genom att samla historiska data, kan en dator utföra satslösning genom att jämföra med liknande meningar som är analyserade i trädbanken. I båda fallen är analysen behäftad med en större eller mindre osäkerhet beroende på hur stort och tillförlitligt det statistiska underlaget är, och helt säker kan man aldrig vara.

Låt oss anta att datorn ska analysera meningen ”Borgmästaren åt pizza med bestick” som ovan, och låt oss också anta att denna mening inte finns analyserad i den trädbank som datorn har tillgång till. Då måste den först ta ställning till vilken ordklass ordet ”Borgmästaren” har. Om ordet överhuvudtaget förekommer i trädbanken, har det med säkerhet alltid märkts upp som substantiv, så datorn kan i detta fall vara säker på att det är rätt analys. Om ordet inte förekommer alls i trädbanken, blir det lite svårare, men i analogi med andra ord som slutar på ”-aren” (”läraren”, ”skrivaren” osv.) är substantiv ändå det mest sannolika.

Nästa steg är att bestämma ordklass på ordet ”åt”, som kan vara både verb och preposition. Här måste vi använda en lite mera komplex modell, som tar hänsyn till sannolikheten i en större kontext. Statistiskt sett är det vanligare att ”åt” är ett verb än en preposition när det förekommer mellan två substantiv, i synnerhet om det andra substantivet är ”pizza”.

Efter det att ordklasserna har bestämts, måste datorn ta ställning till vilken grammatisk relation som råder mellan ”Borgmästaren” och ”åt”. Det är betydligt mer sannolikt att ”Borgmästaren” är en bestämning till ”åt” än tvärtom, eftersom substantiv ofta är bestämningar till finita verb men inte vice versa. Statistiskt sett är det också vanligast i svenska att det substantiv som föregår det finita verbet är subjekt, men det är fullt möjligt att det är objekt som i följande mening: ”Borgmästaren åt draken upp”. Återigen måste vi därför använda en sannolikhetsmodell där vi förutom de aktuella orden också väger in den större kontexten, i synnerhet ordet ”pizza” som ser ut som ett mycket sannolikt objekt (men inte subjekt) för verbet ”åt”.

Samma sak gäller när datorn senare ska ta ställning till om ”med bestick” är bestämning till ”åt” (adverbial) eller ”pizza” (attribut). Med ett tillräckligt stort statistiskt underlag kan datorn således lära sig att ”äta pizza med bestick” vanligen har den förra tolkningen men ”äta pizza med svamp” den senare.

Som synes är det många olika egenskaper hos orden och deras kontext som är relevanta för att finna den mest sannolika analysen. Med en gemensam term kallas dessa egenskaper i samband med maskininlärning för särdrag. En del särdrag är rent grammatiska, såsom att ett substantiv kan vara subjekt till ett verb men inte vice versa, men andra handlar snarare om encyklopedisk kunskap, såsom att svamp är en vanlig pizza-ingrediens medan kniv och gaffel inte är det. För att nå ett så bra resultat som möjligt använder dagens grammatikkunniga datorer miljontals olika särdrag som sedan viktas samman i sannolikhetsmodell för att välja rätt ordklass och satsdel.

Framtiden

Med den metod som skisserats ovan kan man få en dator att analysera tusentals meningar per sekund med över 95 procent av alla ordklasser och över 90 procent av alla satsdelar korrekt analyserade, vilket är tillräckligt bra för att användas i söksystem som Google. Detta gäller dock än så länge bara om vi har att göra med välredigerad text på engelska.

Om vi går till mer okonventionella texttyper, såsom Twitter och SMS, blir det betydligt svårare, främst därför att denna typ av text inte är väl representerad i våra trädbanker. Men även om vi går till andra språk, såsom svenska och finska, tvingas vi konstatera att det är mer som blir fel i den grammatiska analysen. Detta kan till viss del förklaras med att engelska är det språk som är i särklass mest studerat och för vilket man också har tillgång till de flesta och största trädbankerna. Men det råder ingen tvekan om att det också hänger samman med språkens struktur, där i synnerhet finska med rik böjningsmorfologi och förhållandevis fri ordföljd ställer datorn inför delvis andra utmaningar än ett språk som engelska.

Forskningsbilden kompliceras ytterligare av det faktum att olika språk har olika grammatiska traditioner, vilket gör det svårt att direkt jämföra analyser och resultat. På senare år har det därför tagits flera initiativ till att skapa en universell modell som ska gå att tillämpa på alla språk. Här anknyter språkteknologin till en lång tradition inom teoretisk lingvistik som kanske framför allt förknippas med den amerikanske lingvisten Noam Chomsky och som syftar till att beskriva alla världens språk utifrån en universell teori om den mänskliga språkförmågan. I bästa fall kan man därför hoppas att försöken att lära datorer att ta ut satsdelar faktiskt på sikt också kan lära oss något om hur den mänskliga språkförmågan fungerar, men det dröjer nog några år till.


 

Joakim Nivre
Skribenten är professor i datorlingvistik vid Uppsala universitet. Han forskar inom olika områden av språkteknologi men framför allt om robusta och effektiva metoder för storskalig grammatisk analys.

I denna tidskrift: 1/2014