Göm menyn

TDDD02 Språkteknologi för informationssökning

Laboration 2


TDDD02 Laboration 2, HT 2012

Tekniker för stavningskontroll - redigeringsavstånd och språkmodeller

I den här labben ska ni titta på olika tekniker för stavningskontroll och stavningskorrigering. Följande texter kommer att behövas till labben.

Ett stavningskorrigeringssystem ska kunna ge förslag på det mest troliga korrekta ordet, givet det ord användaren skrivit in. Hur vet man vilket ord som är mest troligt? Ska ordet 'tomet' korrigeras till 'komet', 'tomat' eller 'tomte'? Och på vilka grunder?

Ett probabilistiskt sätt att uttrycka problemet är att vi vill hitta det ord som maximerar sannolikheten P(k|o) (sannolikheten för det korrekta ordet k, givet det ursprungliga ordet o). Frågan är alltså vilken sannolikhet som är störst av följande:

  • P("komet"|"tomet") dvs. sannolikheten att det korrekta ordet är "komet" givet indata "tomet"
  • P("tomat"|"tomet") dvs. sannolikheten att det korrekta ordet är "tomat" givet indata "tomet"
  • P("tomte"|"tomet") dvs. sannolikheten att det korrekta ordet är "tomte" givet indata "tomet"

Med Bayes teorem kan denna formel skrivas om så att vi istället vill hitta det k som maximerar sannolikheten för uttrycket P(o|k) P(k). 

     
  • Argmax P(k|o) = Argmax P(o|k) P(k)
       k               k               
    •
På så sätt delar vi upp problemet i två olika modeller, en modell för felskrivning P(o|k) vilket är sannolikheten för att en person råkar skriva ordet o fastän man menade det korrekta ordet k, t.ex. P("tomet"|"tomat"), och en språkmodell P(k) som beskriver hur vanligt det korrekta ordet är i text. Vilket ord är troligast i en text, är P("tomat") större än P("tomte")?

Uppgifter

Obs! att bara uppgift 3 kräver att ni sitter vid en dator.

1. Redigeringsavstånd

Ett sätt att rangordna olika rättstavningsförslag är att mäta redigeringsavståndet mellan det felstavade ordet och ett korrigeringsförslag. Ju kortare avstånd mellan orden, desto troligare är det att korrigeringsförslaget är det ord som skribenten egentligen ville skriva. "Avståndet" mellan två strängar är det minsta antal editeringar som krävs för att göra om den första strängen till den andra. Algoritmen kallas minimum edit distance eller Levenshtein distance

  1. Välj två olika svenska ord som är minst 5 bokstäver långa. Ta fram redigeringsavståndet mellan strängarna genom att utföra minimum edit-distance algoritmen på papper. Använd operationerna tillägg, borttagning och substitution. Varje operation har kostnaden 1.
  2. Gör om ovanstående uppgift men ge varje substitution kostnaden 2 istället.
  3. Låt säga att du har tillgång till information om vanliga stavningsmissar t.ex. är det vanligt att förväxla två bokstäver som är bredvid varandra på tangentbordet eller förväxla bokstäver som låter likadant t.ex. k och c eller o och å. Hur skulle man kunna ta hänsyn till sådan information för att få fram ett bättre redigeringsavstånd som avspeglar att dessa misstag är mer troliga än andra?

2. Språkmodeller

För att kunna ta fram det mest troliga korrigeringsförslaget behöver vi en språkmodell P(k) som talar om hur stor sannolikhet ett ord har i svensk text. Sannolikheter för olika ord beräknas utifrån stora korpusar. Ju större korpus desto bättre blir de uppskattade sannolikheterna.

  1. Skapa en unigram-språkmodell utifrån denna korta text:

    En lukt av lack i huset, av hyacint och gran,
    och mycket pappersprassel och mycket marsipan.

    Tänk på att:

    • Den totala sannolikheten för alla ord måste bli 1.
    • Språkmodellen ska också innehålla en rimlig sannolikhet för okända ord (X). Denna sannolikhet används för att modellen ska kunna ge en sannolikhet större än 0 till ord som 'midsommarstång' eller 'dator'. Den enklaste metoden är add-one smoothing som beskrivs i N-gram och i Föreläsning 3.
  2. Om du istället bygger en bigrammodell utifrån texten, vilket ord har störst sannolikhet att komma efter ordet 'och'? Motivera svaret.
  3. Om man skriver in 'gratis på födelsedagen' i Googles sökmotor, får man förslaget 'grattis på födelsedagen' fastän 'gratis' är ett korrekt svenskt ord. Hur kan språkmodeller användas för att hitta ord som är fel i kontexten?

3. Ett enkelt program för stavningskorrigering

I sista delen av labben ska ni testa ett enkelt program för stavningskorrigering skrivet av av Peter Norvig. Det här programmet skapar en enkel unigram språkmodell från en valfri text och föreslår rättstavningar som är max 2 editeringar från det felstavade ordet. Mer information: How to Write a Spelling Corrector

Programmet heter spell.py och ligger i kurskatalogen ~TDDD02/www-pub/Lab2
I samma katalog ligger ett par textfiler för två olika domäner. Filerna heter hp-train (romantext) och eu-train (texter från europaparlamentet). Programmet använder från början romantexten för att bygga sin språkmodell över vanliga ord i svenska språket. Sökvägen till romantexten är inskriven i filen. Öppna spell.py i en texteditor för att byta sökväg.

  • Spara ner spell.py och och textfilerna i din egen katalog.
  • Om coding är angivet till 'utf-8' på den andra raden, byt ut det mot 'iso-8859-1'.
  • Lägg till rätt version av Python genom att köra följande kommando i skalet:
    module add prog/python/2.6
    module initadd prog/python/2.6
  • Ställ dig i din katalog där du sparade filerna och starta python-skalet:
    >python
  • Importera modulen spell.py med kommandot 'import spell'
    Python 2.6 (r26:66714, Oct 22 2008, 12:54:59)
    [GCC 3.4.6] on sunos5
    Type "help", "copyright", "credits" or "license" for more information.
    >>> import spell
    >>> spell.correct('coh')
    'och'
    >>> spell.correct('jatte')
    'satte'

Testa olika felstavningar och ord och se vad programmet föreslår för korrigeringar. Ändra sedan så att språkmodellen skapas från filen eu-train istället. Blir det skillnader? Skriv ner era resultat.

Besvara följande frågor:

  1. Är ni nöjda med korrigeringsförslagen programmet ger? Hur skulle man kunna förbättra resultaten?
  2. Hur skiljer sig redigeringsavståndet i programmet från levenshtein-avståndet?
  3. Hur kan man anpassa ett stavningskorrigerings/ordförslags-system för att passa sökfrågor som ställs till en sökmotor bättre än exempelvis text som skrivs i ett ordbehandlingsprogram.

Redovisning

Redovisa alla uppgifter på papper och lämna till din labgruppshandledare i ett underskrivet labomslag. Det är viktigt att ni visar att ni har förstått de begrepp som tas upp på labben. Förklara och motivera därför era beräkningar och skriv hellre för mycket än för lite när ni beskriver vad ni har gjort.


Sidansvarig: Lars Ahrenberg
Senast uppdaterad: 2012-10-12