Markov-kjeden er enkel: la oss se på prinsippet i detalj. Legge til tweets til databasen og legge ut på Twitter

Det ble beskrevet hvordan man trener et nøytronnettverk slik at det spiller Mario eller styrer en robot. Men kan nevrale nettverket generere tekst? Markov-kjeder kan hjelpe med dette.

Dette er grunnen til at jeg "elsker" den russiskspråklige Wikipedia, fordi ethvert enkelt fenomen/ligning/regel, spesielt fra matematikk, umiddelbart blir beskrevet på en så generell måte, med så utrolige formler at du ikke kan finne ut av det uten en halv liter. Dessuten gidder ikke forfatterne av artiklene å gi en enkel beskrivelse (minst et par setninger) menneskelig språk, og gå rett til formlene.

Hvis noen vil vite hva Markov-kjeder er, vil han i den første oversettelsen finne ut at:
"Markov-kjeden er en sekvens tilfeldige hendelser med et begrenset eller tellbart antall utfall, karakterisert ved egenskapen at, løst sett, med en fast nåtid, er fremtiden uavhengig av fortiden. Oppkalt til ære for A. A. Markov (senior)."

Og dette til tross for at den grunnleggende ideen til Markov-kjeder er veldig enkel, men det er rett og slett umulig å forstå dette fra Wikipedia uten en matematisk utdanning.

Markov-kjeder er bare en beskrivelse av sannsynlighetene for at et system går fra en tilstand til en annen. Alle tilstander kan beskrives ved toppunktene i grafen. For eksempel kan slike hjørner være menneskelige posisjoner: [liggende], [sittende], [stående], [gå]

Her kan du se at grafen er rettet, noe som betyr at det ikke er mulig å komme seg fra hver stat til en annen. Hvis du for eksempel ligger nede, er det umulig å gå med en gang. Du må sette deg ned først, så stå opp, og først deretter gå. Men du kan falle og ende opp med å legge deg ned fra hvilken som helst posisjon))
Hver forbindelse har en viss sannsynlighet. Så, for eksempel, er sannsynligheten for å falle fra en stående stilling veldig liten, det er mye mer sannsynlig å stå lenger, gå eller sette seg ned. Summen av alle sannsynligheter er 1.

Blant annet lar Markov-kjeder deg generere arrangementer. På en eller annen måte er de fleste tekstgeneratorer bygget på Markov-kjeder.

La oss prøve å skrive en generator av paier.

Paier

Paier - kvad uten rim, tegnsetting, tall, uten store bokstaver. Antall stavelser skal være 9-8-9-8.


De fleste tekstgeneratorer bruker morfologiske analysatorer. Men vi skal gjøre det lettere. La oss bare dele opp ordene i stavelser og regne ut sannsynligheten for at en stavelse kommer etter en annen stavelse. Det vil si at nodene til grafen vil være stavelsene, kantene og vektene deres - frekvensen til den andre stavelsen etter den første.
Deretter mater vi programmet med femti paier.

For eksempel, etter stavelsen "pri" kan det være følgende stavelser (kanter og deres vekt):
"chem" (1) "ho" (4) "meg" (1) "du" (2) "chi" (4) "yatel" (4) "gikk" (5) "ku" (1) " " (9) "su"(1) "vych"(3) "mi"(1) "kos"(1) "ob"(1) "det"(2) "kjørte"(1) "uchi"(1) ) "mu"(1) "bi"(1) "tse"(1) "int"(2) "tom"(1) "ko"(1) "shaft"(1) "nes"(1) " det"(1) "men"(1) "vez"(1) "meth"(1) "vet"(1) "dia"(1) "du"(1)

Nå er alt du trenger å gjøre å ta en tilfeldig stavelse (for eksempel "at"). Summen av alle stavelsene som kommer etter den er 58. Nå må du ta neste stavelse, ta hensyn til frekvensen (antallet) av disse stavelsene:

size_t nth = rand() % telling;

size_t all = 0 ;

for (konst auto &n: neste) (

Alle += n.antall;

if (alle >= nth)

returnere n.ord;

Dermed genererer vi linjer slik at den første linjen har 9 stavelser, den andre - 8, deretter 9 og 8, får vi:

Det var en gang en vits om vekkerklokken
han ble kidnappet mens det var
sjefen din er her ja
Onegin effekter sofa

Så langt ser det ikke ut som en spesielt sammenhengende tekst. Ikke-eksisterende ord ("poku") blir ofte møtt. Det er nå bare én stavelse som nøkkel. Men det er vanskelig å bygge en setning basert på én stavelse. La oss øke antallet stavelser som vi vil generere neste stavelse på grunnlag av til minst 3:

Nok asfalt for sinnet
klokken er syv delt på
bordet er tatt ut, den svarte boksen er
han vokste opp, tok hevn, fant
Her er den første paien som mer eller mindre kan forveksles med å være skrevet av en person.
For å gjøre teksten mer meningsfull, må du bruke morfologiske analysatorer, og da vil nodene ikke være stavelser, men metabeskrivelser av ord (for eksempel "verb, flertall, fortid").

Slike programmer lar deg allerede skrive mer "meningsfull" tekst. For eksempel er en rooter en artikkel skrevet av en vitenskapelig tekstgenerator, som ble gjennomgått og til og med publisert i et vitenskapelig tidsskrift.

En Markov-kjede er en serie med hendelser der hver påfølgende hendelse avhenger av den forrige. I denne artikkelen vil vi undersøke dette konseptet mer detaljert.

En Markov-kjede er en vanlig og ganske enkel måte å modellere tilfeldige hendelser på. Brukes i det meste ulike områder, fra tekstgenerering til finansiell modellering. Det meste kjent eksempel er SubredditSimulator. I i dette tilfellet Markov-kjeden brukes til å automatisere innholdsoppretting gjennom hele subredditen.

Markov-kjeden er oversiktlig og enkel å bruke fordi den kan implementeres uten å bruke noen statistiske eller matematiske konsepter. Markov-kjeden er ideell for å lære probabilistisk modellering og datavitenskap.

Scenario

Tenk deg at det bare er to værforhold: Det kan være enten sol eller skyet. Du kan alltid nøyaktig bestemme været i dette øyeblikket. Garantert klart eller overskyet.

Nå vil du lære hvordan du kan forutsi været for morgendagen. Intuitivt forstår du at været ikke kan endre seg dramatisk på en dag. Dette påvirkes av mange faktorer. Morgendagens vær avhenger direkte av det gjeldende, osv. For å forutsi været samler man altså inn data for flere år og kommer til den konklusjonen at etter en overskyet dag er sannsynligheten for en solskinnsdag 0,25. Det er logisk å anta at sannsynligheten for to overskyede dager på rad er 0,75, siden vi kun har to mulige værforhold.

Nå kan du varsle været flere dager i forveien basert på gjeldende vær.

Dette eksemplet viser nøkkelkonsepter Markov kjeder. En Markov-kjede består av et sett med overganger som bestemmes av en sannsynlighetsfordeling, som igjen tilfredsstiller Markov-egenskapen.

Vær oppmerksom på at i eksemplet avhenger sannsynlighetsfordelingen kun av overgangene med gjeldende dag til den neste. Dette unik eiendom Markov-prosessen - den gjør dette uten å bruke minne. Vanligvis er denne tilnærmingen ikke i stand til å lage en sekvens der noen trend observeres. For eksempel, mens en Markov-kjede kan simulere skrivestil basert på bruksfrekvensen til et ord, kan den ikke lage tekster med dyp betydning, siden det bare kan fungere med store tekster. Dette er grunnen til at en Markov-kjede ikke kan produsere kontekstavhengig innhold.

Modell

Formelt sett er en Markov-kjede en probabilistisk automat. Over vanligvis representert som en matrise. Hvis en Markov-kjede har N mulige stater, da vil matrisen ha formen N x N, der oppføringen (I, J) vil være sannsynligheten for overgang fra tilstand I til tilstand J. I tillegg må en slik matrise være stokastisk, det vil si radene eller kolonner må legges sammen til én. I en slik matrise vil hver rad ha sin egen sannsynlighetsfordeling.

Generelt bilde av en Markov-kjede med tilstander i form av sirkler og kanter i form av overganger.

Et eksempel på overgangsmatrise med tre mulige tilstander.

En Markov-kjede har initial vektor tilstander, representert som en N x 1 matrise Den beskriver sannsynlighetsfordelingene for starten i hver av de N mulige tilstandene. Oppføringen I beskriver sannsynligheten for at kjeden starter i tilstand I.

Disse to strukturene er ganske tilstrekkelige til å representere en Markov-kjede.

Vi har allerede diskutert hvordan man får sannsynligheten for en overgang fra en tilstand til en annen, men hva med å få den sannsynligheten i noen få trinn? For å gjøre dette, må vi bestemme sannsynligheten for overgang fra tilstand I til tilstand J i M-trinn. Det er faktisk veldig enkelt. Overgangsmatrisen P kan bestemmes ved å beregne (I, J) ved å heve P til potensen M. For små verdier av M kan dette gjøres manuelt ved gjentatt multiplikasjon. Men for store verdier M hvis du er kjent med lineær algebra, mer effektiv måteå heve en matrise til en potens vil først diagonalisere den matrisen.

Markov-kjeden: konklusjon

Når du nå vet hva en Markov-kjede er, kan du enkelt implementere den i et av programmeringsspråkene. Enkle kjeder Markov er grunnlaget for å studere mer komplekse metoder modellering.

Jeg surfet på forumene på jakt etter spørsmål som Python-programmerere blir stilt under intervjuer, og kom over et veldig flott spørsmål. Jeg vil sitere ham fritt: "De ba meg skrive en tullgenerator basert på en nth order Markov-kjede." "Men jeg har ikke en slik generator ennå!" - ropte min indre stemme- "Skynd deg, åpne sublime og skriv!" – fortsatte han iherdig. Vel, jeg måtte adlyde.

Og her skal jeg fortelle deg hvordan jeg laget det.

Det ble umiddelbart bestemt at generatoren skulle uttrykke alle sine tanker på Twitter og nettsiden. Jeg valgte Flask og PostgreSQL som hovedteknologiene. De vil kommunisere med hverandre gjennom SQLAlchemy.

Struktur.

Så. På følgende måte modeller ser slik ut:
klasse Srt(db.Model): id = db.Column(db.Integer, primary_key = True) set_of_words = db.Column(db.Text()) list_of_words = db.Column(db.Text()) class UpperWords(db .Model): word = db.Column(db.String(40), index = True, primary_key = True, unique = True) def __repr__(self): returner self.word class Phrases(db.Model): id = db .Column(db.Integer, primary_key = True) opprettet = db.Column(db.DateTime, default=datetime.datetime.now) frase = db.Column(db.String(140), index = True) def __repr__(self ): return str(selv.frase)
Som kildetekster Det ble besluttet å ta undertekster fra populære TV-serier. Srt-klassen lagrer et ordnet sett med alle ord fra de behandlede undertekstene for én episode og et unikt sett med de samme ordene (uten repetisjoner). Dette vil gjøre det lettere for roboten å søke etter en setning i spesifikke undertekster. Den vil først sjekke om settet med ord er inneholdt i settet med ord i undertekstene, og deretter se om de ligger der i i riktig rekkefølge.

Det første ordet i setningen fra teksten er et tilfeldig ord som begynner med store bokstaver. UpperWords brukes til å lagre slike ord. Ordene er skrevet der på samme måte uten repetisjon.

Vel, Phrases-klassen er nødvendig for å lagre allerede genererte tweets.
Strukturen er desperat enkel.

Undertekstparseren av .srt-formatet er inkludert i en egen modul add_srt.py. Det er ikke noe ekstraordinært der, men hvis noen er interessert, er alle kildene på GitHub.

Generator.

Først må du velge det første ordet for tweeten din. Som nevnt tidligere, vil dette være et hvilket som helst ord fra UpperWords-modellen. Valget er implementert i funksjonen:
def add_word(word_list, n): hvis ikke word_list: word = db.session.query(models.UpperWords).order_by(func.random()).first().word #postgre elif len(word_list)<= n: word = get_word(word_list, len(word_list)) else: word = get_word(word_list, n) if word: word_list.append(word) return True else: return False
Valget av dette ordet implementeres direkte av linjen:

Word = db.session.query(models.UpperWords).order_by(func.random()).first().word

Hvis du bruker MySQL, må du bruke func.rand() i stedet for func.random(). Dette er den eneste forskjellen i denne implementeringen, alt annet vil fungere helt identisk.

Hvis det første ordet allerede er der, ser funksjonen på lengden på kjeden, og velger avhengig av dette med hvilket antall ord i teksten vi trenger for å sammenligne listen vår (nth order chain) og få neste ord.

Og vi får det neste ordet i get_word-funksjonen:
def get_word(word_list, n): queries = models.Srt.query.all() query_list = list() for query in queries: if set(word_list)<= set(query.set_of_words.split()): query_list.append(query.list_of_words.split()) if query_list: text = list() for lst in query_list: text.extend(lst) indexies = ) if text == word_list] word = text return word else: return False
Først av alt kjører skriptet gjennom alle innlastede undertekster og sjekker om vårt sett med ord er inkludert i settet med ord med spesifikke undertekster. Deretter blir tekstene til de filtrerte undertekstene kombinert til én liste, og det søkes etter treff på hele fraser, og posisjonene til ordene etter disse frasene returneres. Det hele ender med et blindt ordvalg. Alt er som i livet.
Slik legges ord til listen. Selve tweeten er satt sammen til en funksjon:
def get_twit(): word_list = list() n = N mens len(" ".join(word_list))<140: if not add_word(word_list, n): break if len(" ".join(word_list))>140: word_list.pop() bryter mens word_list[-1][-1] ikke er i ".?!": word_list.pop() returnerer " ".join(word_list)
Det er veldig enkelt – tweeten må ikke overstige 140 tegn og avsluttes med et skilletegn som avslutter setningen. Alle. Generatoren har gjort jobben sin.

Vises på nettstedet.

views.py-modulen håndterer visningen på nettstedet.
@app.route("/") def index(): return render_template("main/index.html")
Den viser ganske enkelt malen. Alle tweets vil bli trukket fra den ved hjelp av js.
@app.route("/page") def page(): page = int(request.args.get("page")) diff = int(request.args.get("difference")) limit = 20 setninger = models.Phrases.query.order_by(-models.Phrases.id).all() pages = math.ceil(len(phrases)/float(limit)) count = len(phrases) phrases = phrases return json.dumps(( "phrases":phrases, "pages":pages, "count":count), cls=controllers.AlchemyEncoder)
Returnerer tweets fra en bestemt side. Dette er nødvendig for uendelig rulling. Alt er ganske vanlig. diff – antall tweets lagt til etter at nettstedet ble lastet under oppdateringen. Utvalget av tweets for siden bør flyttes med dette beløpet.

Og selve oppdateringen:
@app.route("/update") def update(): last_count = int(request.args.get("count")) phrases = models.Phrases.query.order_by(-models.Phrases.id).all( ) count = len(phrases) if count > last_count: phrases = phrases[:count-last_count] return json.dumps(("phrases":phrases, "count":count), cls=controllers.AlchemyEncoder) else: return json .dumps(("count":count))
På klientsiden kalles den hvert n. sekund og laster nye tweets i sanntid. Dette er hvordan vår tweet-skjerm fungerer. (Hvis noen er interessert, kan du se på AlchemyEncoder-klassen i controllers.py, den brukes til å serialisere tweets mottatt fra SQLAlchemy)

Legge til tweets til databasen og legge ut på Twitter.

Jeg brukte tweepy til å legge ut på Twitter. Veldig praktisk batteri, starter umiddelbart.

Hva det ser ut som:
def twit(): phrase = get_twit() twited = modeller.Phrases(phrase=phrase) db.session.add(twited) db.session.commit() auth = tweepy.OAuthHandler(CONSUMER_KEY, CONSUMER_SECRET) auth.set_access_TOKEN( , ACCESS_TOKEN_SECRET) api = tweepy.API(auth) api.update_status(status=frase)
Jeg plasserte kallet til denne funksjonen i cron.py i roten av prosjektet, og som du kanskje gjetter, er den lansert av cron. Hver halvtime legges en ny tweet til databasen og Twitter.


Alt fungerte!

Endelig.

For øyeblikket har jeg lastet ned alle undertekstene til seriene “Friends” og “The Big Bang Theory”. Så langt har jeg valgt graden av Markov-kjeden til å være lik to (ettersom undertekstbasen øker, vil graden øke). Du kan se hvordan det fungerer i

Innen nettkonstruksjon og SEO brukes Markov-kjeder for å generere pseudo-meningsfulle tekster basert på kildetekster. Dette brukes til å stemple døråpninger med gitte nøkkelord, for å skrive innholdstekstmasse og lignende "svarte" triks. Heldigvis har søkemotorer lært å effektivt identifisere innhold skapt basert på Markov-kjeder og forby slike smarte mennesker. Jeg kommer ikke til å lære deg slike teknologier, det er spesielle skitne nettsteder for det, jeg er bare interessert i programvareimplementeringen av algoritmen.


En Markov-kjede er en sekvens av forsøk der bare én av de k inkompatible hendelsene Ai fra hele gruppen vises. I dette tilfellet avhenger ikke den betingede sannsynligheten pij(er) for at hendelsen Aj inntreffer i den s. prøven, forutsatt at hendelsen Ai inntreffer i den (s - 1) prøven, av resultatene fra tidligere forsøk.

De som vil blåse hjernen kan lese om den matematiske modellen. På menneskelig språk koker alle disse formlene ned til følgende. Kildeteksten definerer ord og opprettholder rekkefølgen av hvilke ord som kommer etter. Deretter, basert på disse dataene, lages en ny tekst der selve ordene velges tilfeldig, men forbindelsene mellom dem er bevart. La oss ta et barnerim som et eksempel:

På grunn av skogen, på grunn av fjellene
Bestefar Egor kommer:
meg selv på en hest,
kone på en ku,
barn på kalver,
barnebarn på geiter.

La oss analysere teksten i lenker og lenker

På grunn av [skog, fjell]
skog [på grunn av]
fjell [ritt]
[bestefar] kommer
bestefar [Egor]
Egor [seg selv]
meg selv [på]
på [hest, ku, kalver, barn]
hest [kone]
kone [på]
ku [barn]
barn [på]
kalver [barnebarn]
barnebarn [på]

Lenkene i denne listen representerer unike ord fra teksten, og lenkene i hakeparenteser er lenker - en liste over ord som kan vises etter det ordet.

Når du genererer tekst fra en liste med lenker, ved den første iterasjonen, velges en tilfeldig lenke, dens koblinger bestemmes, en tilfeldig lenke velges fra listen over lenker og aksepteres som en ny lenke. Deretter gjentas handlingen til ønsket tekststørrelse er nådd. Resultatet kan for eksempel være noe slikt:

Egor selv på en kalv, barnebarn på en hest, kone på en ku, barn på en ku
I dette eksemplet skiller den resulterende teksten seg lite fra originalteksten fordi originalteksten er veldig kort. Hvis du tar en innledende ordbok på flere kilobyte eller til og med megabyte, vil utgangen være en fullstendig sammenhengende tekst, selv om det ikke vil gi noen mening.

  1. // Les kildeteksten som en ny vil bli generert på grunnlag av
  2. $str = file_get_contents("markov.txt");
  3. // Angi systemkoding
  4. setlocale(LC_ALL, "ru_RU.CP1251");
  5. // Fjern tegn fra teksten unntatt tall, bokstaver og noen skilletegn
  6. $str = eregi_replace ("[^-a-zа-я0-9 !\?\.\,]" , " " , $str );
  7. // Rydd opp mellomrom før du avslutter setninger
  8. $str = eregi_erstatt (" (1,)([!\?\.\,])" , "\\1" , $str );
  9. // Del opp teksten i ord
  10. $tmp = preg_split ("/[[:mellomrom:]]+/is" , $str );
  11. // En rekke "lenker"
  12. $ord =Array();
  13. // Fyll ut lenkene
  14. for($i = 0 ; $i< count ($tmp ); $i ++) {
  15. if ($tmp [ $i + 1 ]!= "" ) (
  16. $words [ $tmp [ $i ]]= $tmp [ $i + 1 ];
  17. $words = array_map("array_unique" , ​​​​$words );
  18. // En rekke innledende ord i setninger
  19. $start =Array();
  20. foreach($words as $word => $links) (
  21. if (eg ("^[A-Z][a-Z]+" , $ord )) (
  22. $start = $ord ;
  23. // Generer 100 setninger basert på kildeteksten
  24. for ($i = 0; $i< 100 ; $i ++) {
  25. mens (sant) (
  26. $w = $start [ rand (0 ,(tell ($start )- 1 ))];
  27. if (eg ("[\.!\?]$" , $w )) ( fortsett; )
  28. $setning = $w . " " ;
  29. // Antall ord i en setning
  30. $cnt = 1 ;
  31. // Generer tilbud
  32. mens (sant) (
  33. $links = $words [ $w ];
  34. // Bytt kjede
  35. $w = $ord [ $w ][ rand (0 ,(telling ($ord [ $w ])- 1 ))];
  36. $setning .= $w . " " ;
  37. // Hvis ordet var på slutten av setningen
  38. if (eg ("[\.!\?]$" , $w )) ( break; )
  39. $cnt++;
  40. // Hvis generatoren er i en sløyfe, tving deretter ut
  41. if ($cnt > 19 ) ( break; )
  42. // En setning med en lengde på 5-20 ord anses som vellykket
  43. if ($cnt > 5 && $cnt< 20 ) { break; }
  44. // Generert tilbud
  45. ekko $setning ;

En liten forklaring på hvordan det hele fungerer. Først blir filen "markov.txt" lastet, den må være i win-1251-koding. Deretter fjernes alle tegn fra den, bortsett fra bokstaver og noen skilletegn, og deretter kuttes unødvendige mellomrom ut. Det viser seg klartekst, som deretter deles inn i individuelle ord. Det er det, vi har individuelle ledd i kjeden. Nå må vi bestemme sammenhengene mellom ord, det vil si hvilke ord som kan ligge bak hvilke. Dette er den mest ressurskrevende prosessen, så du må være tålmodig med store filer. Hvis generering kreves ofte, er det sannsynligvis fornuftig å lagre en rekke lenker og lenker i en database for å få rask tilgang til den. Neste steg- identifisere ordene som setningene begynner med. Jeg godtok betingelsen om at den første bokstaven i slike ord skulle være stor, du kan gjøre mer presis definisjon. Tekstgenerering utføres i henhold til algoritmen beskrevet ovenfor, jeg har bare lagt til flere kontroller mot looping til den.

Du kan se et fungerende eksempel på en tekstgenerator basert på Markov-kjeder og skriptet ovenfor

Denne artikkelen gir generell idé om hvordan man genererer tekster ved hjelp av Markov prosessmodellering. Spesielt vil vi introdusere Markov-kjeder, og som praksis vil vi implementere en liten tekstgenerator i Python.

Til å begynne med, la oss skrive ned de nødvendige, men ennå ikke veldig klare, definisjonene fra Wikipedia-siden for i det minste å forstå hva vi har å gjøre med:

Markov-prosessen t t

Markov kjede

Hva betyr alt dette? La oss finne ut av det.

Grunnleggende

Det første eksemplet er ekstremt enkelt. Ved å bruke en setning fra en barnebok skal vi mestre grunnleggende konsept Markov lenker, og definerer også hva de er i vår sammenheng kropp, lenker, sannsynlighetsfordeling og histogrammer. Selv om forslaget er gitt på engelske språk, essensen av teorien vil være lett å forstå.

Dette forslaget er ramme, det vil si grunnlaget som teksten vil bli generert på i fremtiden. Den består av åtte ord, men samtidig unike ord bare fem er lenker(vi snakker om Markovian kjeder). For klarhet, la oss fargelegge hver lenke i sin egen farge:

Og vi skriver ned antall opptredener av hver lenke i teksten:

På bildet over kan du se at ordet "fisk" vises i teksten 4 ganger oftere enn hvert av de andre ordene ( "En", "to", "rød", "blå"). Det vil si sannsynligheten for å møte ordet i vårt korpus "fisk" 4 ganger høyere enn sannsynligheten for å møte annethvert ord vist i figuren. Når vi snakker på matematikkspråket, kan vi bestemme fordelingsloven til en tilfeldig variabel og beregne med hvilken sannsynlighet et av ordene vil vises i teksten etter det gjeldende. Sannsynligheten beregnes som følger: vi må dele antall forekomster av ordet vi trenger i korpuset med totalt antall alle ordene i den. For ordet "fisk" denne sannsynligheten er 50 % siden den vises 4 ganger i en 8-ords setning. For hver av de gjenværende koblingene er denne sannsynligheten 12,5% (1/8).

Viser fordelingen grafisk tilfeldige variabler mulig å bruke histogrammer. I dette tilfellet er hyppigheten av forekomsten av hver lenke i setningen tydelig synlig:

Så teksten vår består av ord og unike lenker, og vi viste sannsynlighetsfordelingen for utseendet til hver lenke i en setning på et histogram. Hvis du synes det ikke er verdt å bry seg med statistikk, les videre. Og kanskje det vil redde livet ditt.

Essensen av definisjonen

La oss nå legge til tekstelementer som alltid er underforstått, men som ikke uttrykkes i dagligtale - begynnelsen og slutten av setningen:

Enhver setning inneholder disse usynlige "begynnelsen" og "slutten"; la oss legge dem til som lenker til distribusjonen vår:

La oss gå tilbake til definisjonen gitt i begynnelsen av artikkelen:

Markov-prosessen - tilfeldig prosess, hvis utvikling etter evt angi verdi tidsparameter t er ikke avhengig av utviklingen som gikk forut t, forutsatt at verdien av prosessen i dette øyeblikket er fast.

Markov kjede - spesielt tilfelle Markov-prosessen, når rommet til dens tilstander er diskret (dvs. ikke mer enn tellelig).

Så hva betyr dette? Grovt sett modellerer vi en prosess der systemets tilstand i neste øyeblikk kun avhenger av tilstanden i det nåværende øyeblikket, og ikke på noen måte er avhengig av alle tidligere tilstander.

Forestill deg hva som er foran deg vindu, som bare viser den nåværende tilstanden til systemet (i vårt tilfelle er det ett ord), og du må bestemme hva neste ord vil være basert bare på dataene som presenteres i dette vinduet. I vårt korpus følger ord hverandre etter følgende mønster:

Dermed dannes ordpar (selv slutten av setningen har sitt eget par - en tom betydning):

La oss gruppere disse parene etter det første ordet. Vi vil se at hvert ord har sitt eget sett med lenker, som i sammenheng med setningen vår kan Følg etter ham:

La oss presentere denne informasjonen på en annen måte - for hver lenke tildeler vi en rekke av alle ord som kan vises i teksten etter denne lenken:

La oss ta en nærmere titt. Vi ser at hver lenke har ord som kan komme etter det i en setning. Hvis vi skulle vise diagrammet ovenfor til noen andre, kunne denne personen med en viss sannsynlighet rekonstruert vår første tilbud, altså kroppen.

Eksempel. La oss begynne med ordet "Start". Deretter velger du ordet "En", siden dette ifølge skjemaet vårt er det eneste ordet som kan følge begynnelsen av en setning. Bak ordet "En" også bare ett ord kan følge - "fisk". Nå ser det nye forslaget i mellomversjon ut "En fisk". Videre blir situasjonen mer komplisert - for "fisk" det kan være ord med lik sannsynlighet på 25 % "to", "rød", "blå" og slutten av setningen "Slutt". Hvis vi antar at neste ord er "to", vil gjenoppbyggingen fortsette. Men vi kan velge en lenke "Slutt". I dette tilfellet, basert på skjemaet vårt, vil en setning genereres tilfeldig som er veldig forskjellig fra korpuset - "En fisk".

Vi har nettopp simulert Markov-prosessen- identifiserte hvert neste ord kun på grunnlag av kunnskap om det gjeldende. For å forstå materialet fullt ut, la oss bygge diagrammer som viser avhengighetene mellom elementene i korpuset vårt. Ovalene representerer lenker. Pilene fører til potensielle lenker som kan følge ordet i ovalen. Ved siden av hver pil er sannsynligheten for at neste lenke vil vises etter den gjeldende:

Flott! Vi har lært nødvendig informasjonå gå videre og analysere mer komplekse modeller.

Utvide ordforrådet

I denne delen av artikkelen skal vi bygge en modell etter samme prinsipp som før, men i beskrivelsen vil vi utelate noen trinn. Hvis du har noen problemer, gå tilbake til teorien i den første blokken.

La oss ta fire sitater til fra samme forfatter (også på engelsk, det vil ikke skade oss):

"I dag du er du. Det er sannere enn sant. Det er ingen i live som er deg enn deg.»

« Du har hjernen i hodet. Du har føtter i skoene. Du kan styre deg selv i hvilken som helst retning du velger. Du er helt alene."

"Jo mer du leser, jo flere ting vil du vite." Jo mer du lærer, jo flere steder vil du gå.»

"Tenk venstre og tenke rett og tenk lavt og tenk høyt. Å, tenker du kan tenk deg om bare du prøver."

Korpusets kompleksitet har økt, men i vårt tilfelle er dette bare et pluss - nå vil tekstgeneratoren kunne produsere mer meningsfulle setninger. Faktum er at på ethvert språk er det ord som vises i tale oftere enn andre (for eksempel bruker vi preposisjonen "i" mye oftere enn ordet "kryogen"). Hvordan flere ord i vårt korpus (og dermed avhengighetene mellom dem), jo mer informasjon har generatoren om hvilket ord som mest sannsynlig vil vises i teksten etter det gjeldende.

Den enkleste måten å forklare dette på er fra et programsynspunkt. Vi vet at for hver lenke er det et sett med ord som kan følge den. Og også, hvert ord er preget av antall opptredener i teksten. Vi trenger en måte å fange all denne informasjonen på ett sted; For dette formålet er en ordbok som lagrer "(nøkkel, verdi)"-par best egnet. Ordboknøkkelen vil registrere den nåværende tilstanden til systemet, det vil si en av koblingene til kroppen (for eksempel, "de" på bildet nedenfor); og en annen ordbok vil bli lagret i ordbokverdien. I den nestede ordboken vil nøklene være ord som kan vises i teksten etter den gjeldende lenken til korpuset ( "tenker" Og "mer" kan gå etter i teksten "de"), og verdiene er antall opptredener av disse ordene i teksten etter lenken vår (ordet "tenker" vises i teksten etter ordet "de" 1 gang, ord "mer" etter ordet "de"- 4 ganger):

Les avsnittet ovenfor flere ganger for å være sikker på at du forstår det nøyaktig. Vær oppmerksom på at den nestede ordboken i dette tilfellet er det samme histogrammet, det hjelper oss med å spore koblinger og hyppigheten av deres forekomst i teksten i forhold til andre ord. Det skal bemerkes at selv en slik vokabularbase er veldig liten for riktig generering av tekster i naturlig språk- det bør inneholde mer enn 20 000 ord, eller enda bedre, mer enn 100 000, og enda bedre, mer enn 500 000, men la oss se på ordforrådet vi har.

Markov-kjeden i dette tilfellet er konstruert på samme måte som det første eksemplet - hvert neste ord velges bare på grunnlag av kunnskap om det gjeldende ordet, alle andre ord tas ikke i betraktning. Men takket være lagringen i ordboken av data om hvilke ord som vises oftere enn andre, kan vi godta når vi velger informert beslutning. La oss se på et spesifikt eksempel:

Mer:

Det vil si hvis det gjeldende ordet er ordet "mer", etter det kan det være ord med lik sannsynlighet på 25 % "tingene" Og "steder", og med en sannsynlighet på 50% - ordet "at". Men sannsynlighetene kan alle være like:

Synes at:

Arbeid med Windows

Til nå har vi kun vurdert vinduer på størrelse med ett ord. Du kan øke størrelsen på vinduet slik at tekstgeneratoren produserer flere "verifiserte" setninger. Dette betyr at jo større vinduet er, jo mindre avvik fra kroppen under generering. Å øke vindusstørrelsen tilsvarer overgangen til Markov-kjeden til mer høy orden. Tidligere bygde vi en førsteordens krets for et vindu, to ord vil produsere en andreordens krets, tre vil produsere en tredjeordens krets, og så videre.

Vindu- dette er dataene i nåværende situasjon systemer som brukes til å ta beslutninger. Hvis vi matcher stort vindu og et lite sett med data, så vil vi mest sannsynlig få samme setning hver gang. La oss ta vokabularbasen fra vårt første eksempel og utvide vinduet til størrelse 2:

Utvidelsen har ført til at hvert vindu nå kun har ett alternativ for neste tilstand av systemet – uansett hva vi gjør vil vi alltid få samme setning, identisk med vårt tilfelle. Derfor, for å eksperimentere med vinduer, og for at tekstgeneratoren skal returnere unikt innhold, fyll opp ordforrådsgrunnlag fra 500 000 ord.

Implementering i Python

Diktogram datastruktur

Et diktogram (dict er en innebygd ordbokdatatype i Python) vil vise forholdet mellom lenker og hvor ofte de forekommer i teksten, det vil si deres distribusjon. Men samtidig vil det ha ordbokegenskapen vi trenger - utførelsestiden til programmet vil ikke avhenge av mengden inndata, noe som betyr at vi lager en effektiv algoritme.

Importer tilfeldig klasse Dictogram(dict): def __init__(self, iterable=Ingen): # Initialiser distribusjonen vår som nytt objekt klasse, # legg til eksisterende elementer super(Dictogram, self).__init__() self.types = 0 # antall unike nøkler i distribusjonen self.tokens = 0 # totalt antall av alle ord i distribusjonen hvis iterable: self.update( iterable) def update (self, iterable): # Oppdater distribusjonen med elementer fra det eksisterende # iterable datasettet for element i iterable: if item in self: self += 1 self.tokens += 1 else: self = 1 self. typer += 1 self.tokens += 1 def count(self, item): # Returner elementets tellerverdi, eller 0 hvis element in self: return self return 0 def return_random_word(self): random_key = random.sample(self, 1) # En annen måte: # random .choice(histogram.keys()) return random_key def return_weighted_random_word(self): # Generer et pseudo-tilfeldig tall mellom 0 og (n-1), # der n er det totale antallet ord random_int = random.randint(0, self.tokens-1 ) index = 0 list_of_keys = self.keys() # print "random index:", random_int for i in range(0, self.types): index += self] # print index if(index > random_int): # print list_of_keys [i] returner liste_over_nøkler[i]

Konstruktøren av diktogramstrukturen kan sendes et hvilket som helst objekt som kan itereres over. Elementene i dette objektet vil være ordene for å initialisere diktogrammet, for eksempel alle ordene fra en bok. I dette tilfellet teller vi elementene slik at vi ikke trenger å gå gjennom hele datasettet for å få tilgang til noen av dem hver gang.

Vi laget også to funksjoner for å returnere et tilfeldig ord. Den ene funksjonen velger en tilfeldig nøkkel i ordboken, og den andre, med tanke på antall forekomster av hvert ord i teksten, returnerer ordet vi trenger.

Markov kjedestruktur

fra histogrammer import Dictogram def make_markov_model(data): markov_model = dict() for i i range(0, len(data)-1): if data[i] i markov_model: # Bare legg til en eksisterende distribusjon markov_model].update( ]) else: markov_model] = Diktogram() returnerer markov_modell

I implementeringen ovenfor har vi en ordbok som lagrer vinduer som en nøkkel i et "(nøkkel, verdi)"-par og distribusjoner som verdier i det paret.

Nth order Markov kjedestruktur

fra histogrammer import Dictogram def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Create a window window = tuple(data) # Legg til i ordboken if window in markov_model: # Koble til en eksisterende distribusjon markov_model.update() else: markov_model = Dictogram() return markov_model

Veldig lik en første ordre Markov-kjede, men i dette tilfellet lagrer vi kortegen som en nøkkel i et "(nøkkel, verdi)"-par i en ordbok. Vi bruker den i stedet for en liste, siden tuppelen er beskyttet mot eventuelle endringer, og dette er viktig for oss - tross alt skal nøklene i ordboken ikke endres.

Modellanalyse

Flott, vi har implementert ordboken. Men hvordan kan vi nå generere innhold basert på den nåværende tilstanden og steget til neste tilstand? La oss gå gjennom modellen vår:

Fra histogrammer import Diktogram import tilfeldig fra samlinger import deque import re def gener_random_start(modell): # For å generere et startord, fjern kommentarfeltet: # return random.choice(model.keys()) # For å generere det "riktige" startordet , bruk koden nedenfor: # Riktig innledende ord- dette er de som var begynnelsen på setninger i korpuset hvis "END" i modellen: frø_ord = "END" mens frøord == "END": frøord = modell["END"].return_weighted_random_word() returner frøord returner tilfeldig. choice(modell .keys()) def generere_tilfeldig_setning(lengde, markov_modell): gjeldende_ord = generere_tilfeldig_start(markov_modell) setning = for i i rekkevidde(0, lengde): current_dictogram = markov_modell random_weighted_word = current_dictogram.return_weighted_random_word() current_weighted_random_word() current_dictogram (current_word) setning = setning.capitalize() returnerer " ".join(setning) + "." tilbake setning

Hva blir det neste?

Prøv å tenke på hvor du selv kan bruke en tekstgenerator basert på Markov-kjeder. Bare ikke glem at det viktigste er hvordan du analyserer modellen og hvilke spesielle begrensninger du setter for generering. Forfatteren av denne artikkelen brukte for eksempel et stort vindu da han opprettet tweetgeneratoren, begrenset det genererte innholdet til 140 tegn og brukte bare "riktige" ord for å begynne setninger, det vil si de som var begynnelsen på setninger i korpuset.



© 2024 netdenegnakino.ru - Nei for to. Kjemi. Fysikk. Staving. Geografi