Nada

Laboration 5:
Maskininlärning, Named Entities och TBL

Laboration måndag 11 oktober 2004, 10-12 i Röd

Jonas Sjöbergh

Relaterad kurslitteratur

I kursboken handlar avsnitt 8.6 (sid 307 och framåt) om transformationsbaserad inlärning, vilket tas upp i denna lab. På sidan 118 och sidan 636 står det lite om maskininlärning. På sidan 580 står det lite om igenkänning av namn, vilket är en sorts named entity recognition. Man behöver dock inte ha läst detta innan man gör labben, även om det kan vara bra.

Översikt, läs detta

I denna labb kommer vi pröva på Named Entity Recognition (fast på ett tämligen naivt sätt). Det innebär att man vill leta reda på alla saker som nämns i en text som är namn på något. Dessutom vill man veta vilka av dessa som representerar personer, platser, företag, m.m. Närmare bestämt kommer labben handla om hur man gissar vilka namn som tillhör vilken kategori. Hur man får reda på vad som är namn antar vi att någon redan ordnat (det är ganska lätt på svenska, eftersom namn skrivs med stor bokstav och nästan inget annat gör det).

Vi ska hålla på med "supervised learning", dvs att maskininlärningsprogrammet får lära sig något genom att titta på text där någon talat om vad rätt svar är.

Maskininlärningsdelen består av att använda en TBL-implementation (Transformation Based Learner). Denna lär sig transformationsregler av typen "byt taggen A till B om ordet före är 'och'". Lärandet går till så att man ger programmet en korpus med annotering av var det ska stå t.ex. "B", samt en lista på vilka sorters regler man vill ha. Programmet skapar då samtliga möjliga regler och tittar vilken som ger flest nya korrekta annoteringar. Den regeln sparas och man kör även den regeln på sin träningskorpus. Sen tar man den regel som nu är bäst och gör samma sak med den. Så håller man på tills man uppnått något stoppvilkor (t.ex. att den bästa regeln bara bidrog med 7 nya korrekta annoteringar). Reglerna körs sen i turordning (eftersom de ändrar resultat från tidigare regler) när man ska annotera nytt data.

Inlärningssteget i TBL kan vara resurskrävande. Det är inte ovanligt att man behöver flera gigabyte internminne och att det tar ett antal timmar innan man är klar (eller veckor för den delen). I denna labb ska vi dock leka med ett mindre exempel som inte tar fullt så lång tid. När man väl har genererat sina regler kan man dock göra en blixtsnabb implementation som tillämpar dessa på nytt data. Mer om TBL finns att läsa i kursboken (Jurafsky & Martin: "Speech and Language Processing") på sid 307 och framåt.

Saker att göra

Programkod

TBL-implementation ligger i filen maskinlab.py och är ett Python-program. Spara en egen kopia av den någonstans. På Nada kan man behöva ladda någon modul med Python för att köra sådana ("module add python/latest"). Sedan skriver man i terminalfönstret "python maskinlab.py ". Värt att veta om python: allt som följer tecknet # är en kommentar (fram till radslutet), hur långt indrag en rad har spelar stor roll.

Programmet kan göra lite olika saker och tar lite olika parametrar. Mer om det nedan, när det blir aktuellt. Pythonkod är ganska lättläst för folk som programmerat åtminstone lite, så är man nyfiken på vad som händer eller hittar ett fel i programmet går det bra att se efter i koden.

Träningsdata

För att slippa problemet med att leta upp alla namn i en text använder vi en text annoterad med PoS (part-of-speech). Det innebär att alla verb har fått en tagg som börjar med "vb", substantiv "nn", adjektiv "jj" osv. (Mer information om taggsetet finns här.) Taggar som börjar med "pm" (Proper name) räknar vi som namn, allt annat som övriga ord.

Här finns filen news.txt som innehåller ca. 10000 ord och deras PoS. Spara denna fil tillsammans med programkoden ovan. Vill vi använda någon annan text som inte redan har PoS-annotering finns det ett program på Nada som automatiskt sätter ut PoS (för text på svenska).

Vårt maskininlärningsprogram ska nu lära sig att gissa vilka som är personer, vilka som är företag osv. Som tidigare nämnts ska vi använda supervised learning, så vi behöver en fil med personer och företag uppmärkta. Filen news.txt har inte sådan information. Ett alternativ är att manuellt gå igenom filen och skriva ned rätt svar, men det visar sig snabbt vara väldigt tråkigt. Istället ska vi göra en latmansvariant av annotering.

Uppgift 1, lat annotering

För att slippa annotera hela filen letar vi upp ett par saker av varje sort och talar om vilka som är personer, vilka som är företag osv. Dessa automatannoterar vi sedan och sen hoppas vi att det räcker. (Tekniker som bygger på den här inställningen kallas ibland weakly supervised.)

I pythonkoden finns en kommentar "Uppgift 1". Leta upp den (tidigt i filen). Därunder finns de saker vi vill basera vår annotering på. Fyll i några fler personer, platser och företag som förekommer i träningsdatat. För att se vilka namn som finns i träningsdatat kan man t.ex. ge kommandot "grep pm.nom news.txt | sort | uniq -c | sort -n", vilket letar upp namn och talar om hur många förekomster det var av varje.

När du fyllt i några namn av varje sort kan du köra programmet i fuskannoteringsläge. Det görs med "python maskinlab.py seed news.txt". Vi vill egentligen inte se resultatet utan spara det på en fil, så gör då "python maskinlab.py seed news.txt > news.annoterad". När det gäller maskininlärning är det en sund tumregel att ju fler saker man annoterar desto bättre blir resultaten. Det innebär att är man för lat får man dåliga regler för named entities.

Uppgift 2, träning

En TBL-implementation lär sig regler. För att veta vilka regler som är värda att prova behöver den få regelmallar. Det är nästa steg. I pythonkoden finns en kommentar "Uppgift 2". Hoppa dit och titta lite på hur regelmallarna verkar fungera. Ju fler mallar man har desto långsammare kommer träningen gå. Det spelar också roll vilken sorts villkor man har i sina mallar. En mall som tittar på både närliggande ord och annotering kan ge upphov till massor av regler, vilket tar tid och minne. Fördelen med många regelmallar är att resultatet normalt kan bli bättre då (dock finns risk för överinlärning).

Ta bort och lägg till lite regelmallar så du har några som du tycker verkar lämpliga (ha inte för många mallar i början, då kan det ta lång tid att generera regler).

Kör nu programmet med "python maskinlab.py train news.annoterad X" där "X" är ett värde som talar om hur bra/dålig den bästa regeln ska vara för att vi ska ge upp och sluta leta efter fler regler. Ett bra värde att börja med kan vara 1. (Apropå tröskelvärde kan nämnas att om man vill ha en högre tröskel än den man nyss använde går det bra att bara ta bort reglerna bakifrån i regelfilen, reglerna genereras alltid i samma ordning med de bästa först.)

Om det verkar ta väldigt lång tid (mer än en minut) kan det bero på att du har regelmallar som ger upphov till väldigt många regler. Då kan du trycka Ctrl-C (Control-knappen och C-knappen samtidigt). Då bör programmet dö (med lite felgnäll) och du kan ändra så det går fortare.

Om allt gick bra så matar programmet ut en massa info om vad som händer, dels alla regler som genererades och hur bra dessa var från början ("score: x bla bla") och dels alla regler som det behöll ("best score: x bla bla"). De "bra" reglerna sparades också i en fil vid namn "rules" (fast i ett lite mindre läsbart format).

Titta på reglerna som skapades. Verkar de vettiga? Är några regler bättre än andra? Ett vanligt fenomen vid maskininlärning är överinlärning. Det innebär att man lär sig ett samband som förekommer av en slump i träningsdatat. Ett exempel skulle kunna vara att ord som står efter ordet "och" alltid är personer. Så är ju inte fallet i allmänhet, men har man otur kan träningsdatat se ut så. Detta är ett extra stort problem om man har väldigt lite träningsdata (som i vårt fall).

För att få bra resultat använder man i praktiken oftast ordlistor (med vanliga personnamn, företagsnamn osv.) för att med hög precision ta hand om de vanligaste orden man stöter på. Eftersom vi inte gör det i labben kommer våra resultat vara en bra bit ifrån bästa möjliga prestanda.

Användning/testning

När man har tränat sin TBL (genererat reglerna) är den färdig att användas (i vårt fall dock bara på text med PoS-annotering). För att se vad reglerna egentligen gör (det är inte i alla fall uppenbart vad som händer, eftersom senare regler ändrar vad tidigare regler skrivit) kan man köra reglerna på lite data. "python maskinlab.py use rules news.txt" matar t.ex. ut träningstexten uppmärkt enligt de genererade reglerna.

Oftast går det rätt bra för reglerna på träningsdatat, eftersom de genererats för att vara optimala på just det datat. Därför testar man normalt sina regler på något annat data. I filen test.txt finns lite mer data med PoS-annotering. Spara en kopia av den filen också. "python maskinlab.py use rules test.txt" matar förstås ut vad reglerna tycker att det datat borde annoteras med. Om man sparar detta i en fil ("python maskinlab.py use rules test.txt > test.resultat") kan man snabbkolla vilka ord som blev personer, företag m.m. i detta data lite enklare. T.ex. med "grep company test.resultat | cut -f1,3 | sort | uniq -c | sort -n" som letar upp alla företag ("company") och talar om hur många av varje som dök upp.

Normalt när man utvärderar sitt program så har man ett manuellt annoterat facit att jämföra sina resultat med. Det finns en fil test.facit med just sådan information. Om man kör "python maskinlab.py eval test.facit test.resultat" matar programmet ut statistik om hur bra ens regler klarade sig på testdatat.

För att bli godkänd

Ändra tröskelvärde, regelmallar, listor på personer m.m. tills du får några regler du tycker är hyfsat bra. Förmodligen kommer inte resultatet bli spektakulärt bra, eftersom vi dels kör med lat annotering och dels har väldigt lite data. För godkänt på labben bör man ha åtminstone 50% rätt enligt utvärderingsprogrammets sätt att räkna. Det går att komma över åtminstone 65% rätt utan att behöva ändra egentlig kod.

Det går också bra att införa någon annan ändring i koden som gör att resultaten blir bättre. Det finns t.ex. en rad i koden som ser ut som "entity = int(lex[-1]["entity"])", om man byter den mot "entity = -1" beter sig inlärningen annorlunda. Funktionen "initial_guess" är också otroligt naiv och kan enkelt göras bättre.

Ytterligare ett angreppssätt är att annotera lite data på ett mer traditionellt vis, dvs gå igenom det ord för ord och skriva ned om det är en person eller en plats.

Man kan även generera lite regler först, sen köra dem på träningsdatat och göra antagandet att alla ord som bara hamnade i en enda grupp, t.ex. "person" alltid tillhör den gruppen, och sedan automatannotera på nytt med även dessa personer. Sen kan man upprepa detta fram och tillbaka några gånger. Detta är en väldigt enkel variant av något som kallas "co-learning", vilket är ett ganska hett forskningsområde nuförtiden.

Slutligen kan man notera att om det t.ex. inte finns så många företag omnämnda i träningsdatat, så blir det svårt att lära sig den kategorin. Det är ju ingenting som säger att man måste ha just de här grupperna (annat än att de traditionellt är vanligast och att programkoden råkar förutsätta det). Om man vill kan man lägga till eller ta bort kategorier (det är ganska rättframt att ändra det i koden) och se om resultaten blir bättre eller trevligare på andra sätt.

Labben redovisas genom att man visar upp sina listor för lat annotering, sina regelmallar, sina regler, samt statistik över hur bra det gick på testdatat. Man ska också nämna insiktsfulla kommentarer (muntligt) om ett par av sina regler såsom "det verkar rimligt att saker som säger något är personer" eller "regeln om att allt efter kommatecken är företag tyder på överinlärning". Visa gärna även upp exempel på ord i testdatat som blev fel respektive rätt. Slutligen talar man om vad man gjort för ändringar i systemet (om några skett). Ju kortare tid man spenderar på labben, desto mer förväntas man ha gjort.

Att fortsätta senare

Det går bra att göra en uppsatsuppgift om named entities, t.ex. genom att modifiera koden i denna lab, eller lösa något annat språkteknologiskt problem med samma maskininlärningsalgoritm (eller rent av en annan algoritm). Det går även att göra exjobb om named entities.


Sidansvarig: Jonas Sjöbergh <jsh@nada.kth.se>
Senast ändrad 17 september 2004
Tekniskt stöd: <webmaster@nada.kth.se>