May 13th, 2008 mejf
En Markovkedja är enligt Wikipedia “en tidsdiskret stokastisk process med Markovegenskapen, det vill säga att processens förlopp kan bestämmas utifrån dess befintliga tillstånd utan kännedom om det förflutna.“. Med andra ord har vi något slags process som befinner sig i ett tillstånd åt gången. Efter varje tillstånd har processen ett antal andra tillstånd till vilken den går vidare till med en viss sannolikhet.
Med lite vilja bör man kunna se språk som en Markovkedja av bokstäver, ord, meningar eller kanske till och med hela konversationer. Man kan genom att dela upp ett språkexempel i dessa tillstånd få ut en jättestor matris med alla dessa sannolikheter där raden representerar “från”-tillstånd och kolumnen “till”-tillstånd. Då innehåller elementet sannolikheten för just den övergången. Denna matrix kallas därför för “övergångsmatris”.
Analyserar vi exempelvis meningen “Hej jag heter Manfred” med avseende på ord så kommer det vara 100% sannolikhet att ordet “Hej” efterföljs av ordet “jag”, och så vidare. Ser man istället tecken (bokstäver) som tillstånd kommer det vara 25% (1/4) chans att bokstaven “e” följs av bokstaven “j”, 25% bokstaven “t”, osv.
Detta kan man givetvis leka med om man känner för det. Med ett oerhört litet, enkelt C-program kan man analysera en given text (med avseende på bokstäver) och sedan slumpa fram en ny text med den analyserade textens sannolikheter. Då kan man få resultat som:
“The homexis llle be!”, eller
“Fin suth! or mar thtou ghed thinechtew.”.
Kan du gissa vilken text det är jag har utgått från? Nej, misstänkte det. Det blir nog lite lättare om jag låter ord vara mina tillstånd istället. Det blev en något mer avancerad övergångsmatris, så det blev ett inte lika kort program, och dessutom skrivet i Java (för att enklare kunna bolla med datastrukturer). Då kan man få meningar som dessa:
“Prologue: Enter Nurse Nurse Madam, if they can give to stand: I cannot at graves!” eller
“Juliet Madam, if they can give to thee, they have to love, to Romeo There is shut.”
Ja, alldeles riktigt. Texten jag har analyserat är en omarbetad version Romeo och Julia av Shakespear (som kan laddas ner gratis på Wikisource). Nu återstår bara att komplettera så att man kan blanda sannolikheter från meningar till meningar och meningar till ord och bygga in IRC-stöd, så har jag en komplett chatbot! Eller nått…
Posted in Programmering | Tags: C, charbot, julia, markov, markovkedja, romeo | No Comments »
