Kirjeldati, kuidas treenida neutronite võrku nii, et see mängiks Mariot või juhiks robotit. Aga saab närvivõrk teksti genereerida? Markovi ketid võivad selles aidata.

Seetõttu "armastan" venekeelset Vikipeediat, sest igasugust lihtsat nähtust/võrrandit/reeglit, eriti matemaatikast, kirjeldatakse kohe nii üldsõnaliselt, nii mõistusevastaste valemitega, et ilma selleta ei saagi aru. pool liitrit. Pealegi ei vaevu artiklite autorid andma lihtsat kirjeldust (vähemalt paar lauset) inimkeel ja minge otse valemite juurde.

Kui keegi tahab teada, mis on Markovi ketid, siis esimeses tõlkes saab ta teada, et:
"Markovi kett on jada juhuslikud sündmused Lõpliku või loendatava arvu tulemustega, mida iseloomustab omadus, et fikseeritud olevikuga on tulevik minevikust sõltumatu. Nimetatud A. A. Markovi (vanem) auks."

Ja seda hoolimata asjaolust, et Markovi kettide põhiidee on väga lihtne, kuid ilma matemaatilise hariduseta on seda Wikipediast lihtsalt võimatu mõista.

Markovi ahelad on vaid süsteemi ühest olekust teise ülemineku tõenäosuse kirjeldus. Kõiki olekuid saab kirjeldada graafiku tippudega. Näiteks võivad sellised tipud olla inimese asendid: [lamamine], [istumine], [seismine], [kõndimine]

Siin on näha, et graafik on suunatud, mis tähendab, et igast olekust teise ei ole võimalik jõuda. Näiteks kui oled pikali, siis on võimatu kohe kõndida. Kõigepealt tuleb istuda, siis püsti tõusta ja alles siis kõndida. Kuid võite kukkuda ja lõpuks pikali jääda igast asendist))
Igal ühendusel on teatud tõenäosus. Nii on näiteks seisvast asendist kukkumise tõenäosus väga väike, palju tõenäolisem on seista kaugemale, kõndida või istuda. Kõigi tõenäosuste summa on 1.

Markovi ketid võimaldavad muu hulgas genereerida sündmusi. Nii või teisiti on enamik tekstigeneraatoreid üles ehitatud Markovi ahelatele.

Proovime kirjutada pirukate generaatori.

Pirukad

Pirukad – neljavärsked ilma riimita, kirjavahemärkideta, numbriteta, ilma suured tähed. Silpide arv peaks olema 9-8-9-8.

Enamik tekstigeneraatoreid kasutab morfoloogilisi analüsaatoreid. Aga me teeme selle lihtsamaks. Jagame lihtsalt sõnad silpideks ja arvutame välja tõenäosuse, et üks silp tuleb teise silbi järel. See tähendab, et graafiku sõlmedeks on silbid, servad ja nende kaalud - esimesele järgneva teise silbi sagedus.
Järgmisena toidame programmi viiskümmend pirukat.

Näiteks pärast silpi “at” võivad olla järgmised silbid (ääred ja nende kaalud):
"chem" (1) "ho" (4) "mina" (1) "du" (2) "chi" (4) "yatel" (4) "läks" (5) "ku" (1) " " (9) "su"(1) "vych"(3) "mi"(1) "kos"(1) "ob"(1) "det"(2) "sõitis"(1) "uchi"(1) ) "mu"(1) "bi"(1) "tse"(1) "int"(2) "tom"(1) "ko"(1) "võll"(1) "nes"(1) " det"(1) "aga"(1) "vez"(1) "meth"(1) "veterinaar"(1) "dia"(1) "teie"(1)

Nüüd pole vaja teha muud, kui võtta juhuslik silp (näiteks "at"). Kõigi pärast seda tulevate silpide summa on 58. Nüüd peate võtma järgmise silbi, võttes arvesse nende silpide sagedust (arvu):

suurus_t nth = rand() % count;

suurus_kõik = 0 ;

jaoks (const auto &n: next) (

Kõik += n.count;

kui (kõik >= n-s)

tagasi n.sõna;

Seega genereerime read nii, et esimesel real on 9 silpi, teisel - 8, seejärel 9 ja 8, saame:

Kunagi oli nali äratuskella üle
ta rööviti selle ajal
teie ülemus on siin jah
Onegini efektiga diivan

Siiani ei tundu see eriti sidusa tekstina. Sageli kohtab olematuid sõnu (“poku”). Nüüd on võtmena ainult üks silp. Kuid ühe silbi põhjal lauset on raske koostada. Suurendame silpide arvu, mille alusel genereerime järgmise silbi, vähemalt 3-ni:

Asfalti mõistusele piisavalt
kell on seitse jagatud
laud on välja võetud, must kast on
ta kasvas üles, maksis kätte, leidis
Siin on esimene pirukas, mida võib enam-vähem ekslikult pidada inimese kirjutatud.
Teksti sisukamaks muutmiseks peate kasutama morfoloogilisi analüsaatoreid ja siis pole sõlmedeks silbid, vaid sõnade metakirjeldused (näiteks "verb, mitmuses, minevikuvorm").

Sellised programmid võimaldavad teil juba "sisukamat" teksti kirjutada. Näiteks rooter on teadusteksti generaatori kirjutatud artikkel, mis on läbi vaadatud ja isegi teadusajakirjas avaldatud.

Markovi kett on sündmuste jada, milles iga järgnev sündmus sõltub eelmisest. Selles artiklis käsitleme seda kontseptsiooni üksikasjalikumalt.

Markovi kett on levinud ja üsna lihtne viis juhuslike sündmuste modelleerimiseks. Kasutatud enamikus erinevad valdkonnad, teksti genereerimisest finantsmodelleerimiseni. Kõige kuulus näide on SubredditSimulator. IN sel juhul Markovi ketti kasutatakse sisu loomise automatiseerimiseks kogu subredditi ulatuses.

Markovi kett on selge ja hõlpsasti kasutatav, kuna seda saab rakendada ilma statistilisi või matemaatilisi kontseptsioone kasutamata. Markovi kett sobib ideaalselt tõenäosusliku modelleerimise ja andmeteaduse õppimiseks.

Stsenaarium

Kujutage ette, et neid on ainult kaks ilmastikutingimused: Võib olla päikesepaisteline või pilvine. Saate alati täpselt kindlaks määrata, milline ilm on Sel hetkel. Garanteeritud on selge või pilvine ilm.

Nüüd soovite õppida, kuidas ennustada homset ilma. Intuitiivselt mõistate, et ilm ei saa ühe päevaga dramaatiliselt muutuda. Seda mõjutavad paljud tegurid. Homne ilm sõltub otseselt praegusest jne. Seega kogutakse ilma ennustamiseks andmeid mitme aasta kohta ja jõutakse järeldusele, et pärast pilvist päeva on päikesepaistelise päeva tõenäosus 0,25. Loogiline on eeldada, et kahe järjestikuse pilvise päeva tõenäosus on 0,75, kuna meil on ainult kaks võimalikku ilmastikuolukorda.

Nüüd saate praeguse ilma põhjal ilma ennustada mitu päeva ette.

See näide näitab võtmemõisteid Markovi ketid. Markovi ahel koosneb üleminekute komplektist, mis on määratud tõenäosusjaotusega, mis omakorda rahuldavad Markovi omadust.

Pange tähele, et näites sõltub tõenäosusjaotus ainult üleminekutest praegune päev järgmisele. See ainulaadne vara Markovi protsess - see teeb seda ilma mälu kasutamata. Tavaliselt ei suuda see lähenemine luua järjestust, milles suundumusi täheldatakse. Näiteks kui Markovi kett võib sõna kasutamise sageduse põhjal simuleerida kirjutamisstiili, ei saa see luua tekste sügav tähendus, kuna see töötab ainult suurte tekstidega. Seetõttu ei saa Markovi kett toota kontekstist sõltuvat sisu.

Mudel

Formaalselt on Markovi ahel tõenäosuslik automaat. Ülemineku tõenäosusjaotust esitatakse tavaliselt maatriksina. Kui Markovi ketil on N võimalikud olekud, siis saab maatriks kuju N x N, milles kirje (I, J) on olekust I olekusse J ülemineku tõenäosus. Lisaks peab selline maatriks olema stohhastiline, see tähendab, et read või veergude summa peab olema üks. Sellises maatriksis on igal real oma tõenäosusjaotus.

Markovi ahela üldvaade, mille olekud on ringidena ja servad üleminekutena.

Kolme võimaliku olekuga siirdemaatriksi näide.

Markovi kett on algvektor olekuid, mis on esitatud maatriksina N x 1. See kirjeldab alguse tõenäosusjaotust igas N võimalikus olekus. Kirje I kirjeldab tõenäosust, et ahel algab olekus I.

Need kaks struktuuri on Markovi ahela esindamiseks täiesti piisavad.

Oleme juba arutanud, kuidas saada ühest olekust teise ülemineku tõenäosust, aga kuidas oleks selle tõenäosuse saamisega mõne sammuga? Selleks peame määrama M-sammuga olekust I olekusse J ülemineku tõenäosuse. See on tegelikult väga lihtne. Üleminekumaatriksi P saab määrata arvutades (I, J), tõstes P astmeni M. Väikeste M väärtuste korral saab seda teha käsitsi, kasutades korduvat korrutamist. Aga selleks suured väärtused M kui oled tuttav Lineaaralgebra, rohkem tõhus viis maatriksi tõstmine astmeni diagonaliseerib selle maatriksi esmalt.

Markovi kett: järeldus

Nüüd, teades, mis on Markovi kett, saate seda hõlpsasti ühes programmeerimiskeeles rakendada. Lihtsad ketid Markov on aluseks, et rohkem õppida keerulised meetodid modelleerimine.

Sirvisin foorumeid ja otsisin küsimusi, mida Pythoni programmeerijatele intervjuude ajal esitatakse, ja leidsin ühe väga imelise küsimuse. Tsiteerin teda vabalt: "Nad palusid mul kirjutada n-nda järgu Markovi keti põhjal jamade generaator." "Aga mul pole veel sellist generaatorit!" - hüüdis mu sisemine hääl- "Kiirustage, avage ülev ja kirjutage!" - jätkas ta visalt. No ma pidin kuuletuma.

Ja siin ma räägin teile, kuidas ma seda tegin.

Kohe otsustati, et generaator avaldab kõik oma mõtted Twitteris ja oma veebisaidil. Peamisteks tehnoloogiateks valisin Flask ja PostgreSQL. Nad suhtlevad üksteisega SQLAlchemy kaudu.

Struktuur.

Niisiis. Järgmisel viisil mudelid näevad välja sellised:
class Srt(db.Mudel): id = db.Veerg(db.Täisarv, esmane_võti = Tõene) sõnade_hulk = db.Veerg(db.Tekst())_sõnade_loend = db.Veerg(db.Tekst()) klass Ülemised sõnad(db) .Model): sõna = db.Veerg(db.String(40), indeks = Tõene, esmane_võti = Tõene, unikaalne = Tõene) def __repr__(self): return self.word class Fraasid(db.Model): id = db .Veerg(db.Täisarv, esmane_võti = Tõene) loodud = db.Veerg(db.Kuupäev, kellaaeg, vaikimisi=kuupäevaeg.kuupäevaaeg.now) fraas = db.Column(db.String(140), indeks = tõene) def __repr__(self ): return str(self.frase)
Nagu lähtetekstid Otsustati võtta subtiitrid populaarsetest teleseriaalidest. Srt-klass salvestab ühe episoodi töödeldud subtiitrite kõigi sõnade järjestatud komplekti ja nende samade sõnade kordumatu komplekti (ilma kordusteta). See hõlbustab robotil konkreetsete subtiitritega fraasi otsimist. Esmalt kontrollib see, kas sõnade komplekt sisaldub subtiitrite sõnade hulgas ja seejärel vaatab, kas need on seal õiges järjekorras.

Fraasi esimene sõna tekstist on juhuslik sõna, mis algab tähega suured tähed. Selliste sõnade salvestamiseks kasutatakse UpperWords. Sinna kirjutatakse sõnad samamoodi ilma kordamiseta.

Noh, fraaside klassi on vaja juba loodud säutsude salvestamiseks.
Struktuur on meeleheitlikult lihtne.

Srt-vormingu subtiitrite parser sisaldub eraldi moodulis add_srt.py. Midagi erakordset seal pole, aga kui kedagi huvitab, siis kõik allikad on GitHubis.

Generaator.

Esiteks peate valima oma säutsu jaoks esimese sõna. Nagu varem mainitud, on see mis tahes sõna UpperWordsi mudelist. Selle valik rakendatakse funktsioonis:
def add_word(word_list, n): kui mitte sõnaloend: sõna = 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
Selle sõna valikut rakendab otse rida:

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

Kui kasutate MySQL-i, peate func.random() asemel kasutama funktsiooni func.rand(). See on ainus erinevus selles teostuses; kõik muu töötab täiesti identselt.

Kui esimene sõna on juba olemas, vaatab funktsioon ahela pikkust ja valib sellest sõltuvalt, millise arvu sõnadega tekstis peame oma nimekirja (n-ndat järku ahel) võrdlema ja saama järgmine sõna.

Ja järgmise sõna saame funktsioonis get_word:
def get_word(sõnaloend, n): päringud = mudelid.Srt.query.all() query_list = list() päringu jaoks päringutes: if set(sõnaloend)<= 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
Kõigepealt jookseb skript läbi kõik laetud subtiitrid ja kontrollib, kas meie sõnade komplekt on kindlate subtiitrite sõnade komplektis. Seejärel kombineeritakse filtreeritud subtiitrite tekstid üheks loendiks ja otsitakse tervete fraaside vasteid ning tagastatakse nendele fraasidele järgnevate sõnade asukohad. Kõik lõpeb pimeda sõnavalikuga. Kõik on nagu elus.
Nii lisatakse loendisse sõnad. Säuts ise on kokku pandud funktsiooniks:
def get_twit(): word_list = list() n = N while len(" ".join(word_list))<140: if not add_word(word_list, n): break if len(" ".join(word_list))>140: word_list.pop() katkeb, samas kui word_list[-1][-1] ei ole ".?!!": word_list.pop() return " ".join(word_list)
See on väga lihtne – säuts ei tohi ületada 140 tähemärki ja lõppeda lauselõpulise kirjavahemärgiga. Kõik. Generaator on oma töö teinud.

Kuva saidil.

Moodul views.py haldab kuvamist saidil.
@app.route("/") def index(): return render_template("main/index.html")
See kuvab lihtsalt malli. Kõik säutsud tõmmatakse sellest js-i abil.
@app.route("/page") def page(): page = int(request.args.get("page")) diff = int(request.args.get("erinevus")) limiit = 20 fraasi = models.Phrases.query.order_by(-models.Phrases.id).all() pages = math.ceil(len(fraasid)/float(limit)) count = len(fraasid) fraasid = fraasid return json.dumps(( "fraasid":fraasid, "lehed":lehed, "count":count), cls=controllers.AlchemyEncoder)
Tagastab säutsud konkreetselt lehelt. See on vajalik lõpmatuks kerimiseks. Kõik on üsna tavaline. diff – säutsude arv, mis on lisatud pärast saidi laadimist värskendamise ajal. Lehe säutsude näidis tuleks selle summa võrra nihutada.

Ja värskendus ise:
@app.route("/update") def update(): last_count = int(request.args.get("count")) fraasid = models.Phrases.query.order_by(-models.Phrases.id).all( ) count = len(fraasid) if count > last_count: fraasid = fraasid[:loend-viimane_loendus] return json.dumps(("fraasid":fraasid, "count":count), cls=controllers.AlchemyEncoder) else: return json .dumps(("count":count))
Kliendi poolel helistatakse sellele iga n sekundi järel ja see laadib reaalajas värskelt lisatud säutsu. Nii töötab meie säutsukuva. (Keda huvitab, võib controllers.py-st vaadata AlchemyEncoder klassi, seda kasutatakse SQLAlchemyst saadud säutsude serialiseerimiseks)

Säutsude lisamine andmebaasi ja Twitterisse postitamine.

Ma kasutasin Twitterisse postitamiseks tweepyt. Väga mugav aku, käivitub kohe.

Milline see välja näeb:
def twit(): fraas = get_twit() twited = mudelid.Fraasid(fraas=fraas) db.session.add(twited) db.session.commit() auth = tweepy.OAuthHandler(CONSUMER_KEY, CONSUMER_SECRET)ENAC_CESSTOenKENACces_CESSTOen , ACCESS_TOKEN_SECRET) api = tweepy.API(auth) api.update_status(status=fraas)
Panin selle funktsiooni kutse projekti juure faili cron.py ja nagu võite arvata, käivitab selle cron. Iga poole tunni tagant lisatakse andmebaasi ja Twitterisse uus säuts.


Kõik toimis!

Lõpuks.

Hetkel olen alla laadinud kõik sarjade “Sõbrad” ja “Suure paugu teooria” subtiitrid. Siiani olen valinud Markovi ahela astme väärtuseks kaks (subtiitrite baasi kasvades aste suureneb). Näete, kuidas see sees töötab

Veebiehituses ja SEO-s kasutatakse Markovi ahelaid lähtetekstide põhjal pseudotähenduslike tekstide genereerimiseks. Seda kasutatakse etteantud märksõnadega ukseavade tembeldamiseks, sisu tekstimassi tippimiseks jms “mustade” trikkide tegemiseks. Õnneks on otsingumootorid õppinud Markovi kettide põhjal loodud sisu tõhusalt tuvastama ja sellised nutikad inimesed ära keelama. Ma ei hakka teile selliseid tehnoloogiaid õpetama, selleks on spetsiaalsed nõmedad saidid, mind huvitab ainult algoritmi tarkvara rakendamine.

Markovi ahel on katsete jada, millest igaühes esineb ainult üks k kokkusobimatust sündmusest Ai kogu rühmast. Sel juhul ei sõltu tingimuslik tõenäosus pij(id), et sündmus Aj toimub s-s katses, eeldusel, et sündmus Ai leiab aset (s–1)-ndas katses, eelmiste katsete tulemustest.

Need, kes tahavad ajudele puhuda, saavad lugeda matemaatilisest mudelist. Inimkeeles taanduvad kõik need valemid järgmisele. Lähtetekstis defineeritakse sõnad ja jäetakse järjekord, mille järel sõnad tulevad. Seejärel luuakse nende andmete põhjal uus tekst, milles sõnad ise valitakse juhuslikult, kuid nendevahelised seosed säilivad. Võtame näitena lastelaulu:

Metsa pärast, mägede pärast
Vanaisa Egor tuleb:
ma ise hobuse seljas,
naine lehmal,
lapsed vasikatel,
lapselapsed kitsepoegadel.

Parsisime teksti linkideks ja linkideks

Sest [mets, mäed]
metsad [tänu]
mäed [sõidud]
[vanaisa] tuleb
vanaisa [Egor]
Egor [ise]
mina [on]
[hobune, lehm, vasikad, lapsed]
hobune [naine]
naine [on]
lehm [lapsed]
lapsed [peal]
vasikad [lapselapsed]
lapselapsed [on]

Selle loendi lingid esindavad ainulaadseid sõnu tekstist ja nurksulgudes olevad lingid on lingid – sõnade loend, mis võivad ilmuda selle sõna järel.

Linkide loendist teksti genereerimisel valitakse esimesel iteratsioonil juhuslik link, määratakse selle ühendused, valitakse linkide loendist juhuslik link ja võetakse see vastu uue lingina. Seejärel korratakse toimingut kuni soovitud tekstisuuruse saavutamiseni. Tulemuseks võib olla näiteks midagi sellist:

Egor ise vasikal, lapselapsed hobusel, naine lehmal, lapsed lehmal
Selles näites erineb saadud tekst algtekstist vähe, kuna algtekst on väga lühike. Kui võtta esialgne mitme kilobaidi või isegi megabaidine sõnastik, on väljundiks täiesti ühtne tekst, kuigi sellel pole mõtet.

1. // Loe läbi lähtetekst, mille põhjal genereeritakse uus
2. $str = file_get_contents("markov.txt");
3. // Süsteemi kodeeringu määramine
4. setlocale(LC_ALL, "ru_RU.CP1251");
5. // Eemaldage tekstist tähemärgid, välja arvatud numbrid, tähed ja mõned kirjavahemärgid
6. $str = eregi_replace ("[^-a-zа-я0-9 !\?\.\,]" , " " , $str );
7. // Puhastage tühikud enne lausete lõpetamist
8. $str = eregi_asendamine (" (1,)([!\?\.\,])" , "\\1" , $str );
9. // Jaga tekst sõnadeks
10. $tmp = preg_split ("/[[:space:]]+/is" , $str );
11. // "Linkide" massiiv
12. $sõnad =Massiiv();
13. // Täida lingid
14. for($i = 0 ; $i< count ($tmp ); $i ++) {
15. if ($tmp [ $i + 1 ]!= "" ) (
16. $sõnad [ $tmp [ $i ]]= $tmp [ $i + 1 ];
17. $sõnad = massiivi_kaart("massiivi_unikaalne" , ​​$sõnad );
18. // Algsõnade massiiv lausetes
19. $start =Massiiv();
20. foreach($words as $word => $lings ) (
21. if (ereg ("^[A-Z][a-Z]+" , $word )) (
22. $algus = $sõna ;
23. // Loo lähteteksti põhjal 100 lauset
24. jaoks ($i = 0; $i< 100 ; $i ++) {
25. samas (tõsi) (
26. $w = $start [ rand (0 ,(count ($start )- 1 ))];
27. if (ereg ("[\.!\?]$" , $w )) ( jätka; )
28. $lause = $w . "" ;
29. // Sõnade arv lauses
30. $cnt = 1 ;
31. // Loo pakkumine
32. kuigi (tõsi) (
33. $lingid = $sõnad [ $w ];
34. // Lüliti kett
35. $w = $sõnad [ $w ][ rand (0 ,(loend ($sõnad [ $w ])- 1 ))];
36. $lause .= $w . "" ;
37. // Kui sõna oli lause lõpus
38. if (ereg ("[\.!\?]$" , $w )) ( break; )
39. $cnt++;
40. // Kui generaator on ahelas, siis sund välju
41. if ($cnt > 19 ) ( break; )
42. // Edukaks loetakse lause pikkusega 5-20 sõna
43. if ($cnt > 5 && $cnt< 20 ) { break; }
44. // Loodud pakkumine
45. kaja $lause ;

Väike selgitus, kuidas see kõik töötab. Esiteks laaditakse fail "markov.txt", see peab olema win-1251 kodeeringus. Seejärel eemaldatakse sellelt kõik märgid, välja arvatud tähed ja mõned kirjavahemärgid, ning seejärel lõigatakse välja mittevajalikud tühikud. Selgub selge tekst, mis seejärel jaguneb üksikud sõnad. See on kõik, meil on ahelas üksikud lülid. Nüüd tuleb määrata sõnadevahelised seosed ehk millised sõnad milliste taga võivad asuda. See on kõige ressursimahukam protsess, nii et suurte failide puhul peate olema kannatlik. Kui genereerimist nõutakse sageli, on tõenäoliselt mõistlik salvestada mõnda andmebaasi linkide massiivi, et sellele kiirelt juurde pääseda. Järgmine samm- sõnade tuvastamine, millega laused algavad. Ma nõustusin tingimusega, et selliste sõnade esimene täht peaks olema suur, saate rohkem täpne määratlus. Teksti genereerimine toimub ülalkirjeldatud algoritmi järgi, lisasin sellele lihtsalt mitu kontrolli silmuste vastu.

Näete Markovi ahelate ja ülaltoodud skripti põhjal töötavat tekstigeneraatori näidet

See artikkel annab üldine idee selle kohta, kuidas Markovi protsessi modelleerimist kasutades tekste genereerida. Eelkõige tutvustame Markovi ahelaid ja praktikana rakendame Pythonis väikese tekstigeneraatori.

Alustuseks kirjutame Vikipeedia lehelt üles vajalikud, kuid veel mitte väga selged määratlused, et vähemalt ligikaudselt mõista, millega tegu:

Markovi protsess t t

Markovi kett

Mida see kõik tähendab? Selgitame välja.

Põhitõed

Esimene näide on äärmiselt lihtne. Kasutades lauset lasteraamatust, me meisterdame põhikontseptsioon Markovi ahelaid ja määratleda ka, mis need meie kontekstis on keha, lingid, tõenäosusjaotus ja histogrammid. Kuigi ettepanek antakse edasi inglise keel, on teooria olemust lihtne mõista.

See ettepanek on raami, ehk siis alus, mille alusel edaspidi tekst genereeritakse. See koosneb kaheksast sõnast, kuid samal ajal ainulaadsed sõnad ainult viis on lingid(me räägime Markovianist ketid). Selguse huvides värvime iga lingi oma värviga:

Ja kirjutame tekstis üles iga lingi ilmumiste arvu:

Ülaltoodud pildil näete seda sõna "kala" esineb tekstis 4 korda sagedamini kui iga teine ​​sõna ( "Üks", "kaks", "punane", "sinine"). See tähendab tõenäosust kohata sõna meie korpuses "kala" 4 korda suurem kui joonisel näidatud iga teise sõna kohtumise tõenäosus. Rääkides matemaatika keeles, saame määrata juhusliku suuruse jaotusseaduse ja arvutada, millise tõenäosusega ilmub üks sõnadest tekstis pärast praegust. Tõenäosus arvutatakse järgmiselt: peame jagama meile vajaliku sõna esinemiste arvu korpuses koguarv kõik sõnad selles. Sõna pärast "kala" see tõenäosus on 50%, kuna see esineb 4 korda 8-sõnalises lauses. Iga ülejäänud lingi puhul on see tõenäosus 12,5% (1/8).

Esitage jaotust graafiliselt juhuslikud muutujad võimalik kasutada histogrammid. Sel juhul on lause iga lingi esinemissagedus selgelt nähtav:

Niisiis koosneb meie tekst sõnadest ja ainulaadsetest linkidest ning me kuvasime histogrammil iga lingi ilmumise tõenäosusjaotuse lauses. Kui arvad, et statistikaga ei tasu vaeva näha, siis loe edasi. Ja võib-olla päästab see teie elu.

Määratluse olemus

Nüüd lisame oma tekstile elemendid, mis on alati vihjatud, kuid mida igapäevases kõnes ei esitata - lause algus ja lõpp:

Iga lause sisaldab neid nähtamatuid "algusi" ja "lõppusid"; lisame need meie levitamise linkidena:

Tuleme tagasi artikli alguses antud määratluse juurde:

Markovi protsess - juhuslik protsess, mille evolutsioon pärast mis tahes seatud väärtus aja parameeter t ei sõltu eelnevast arengust t, eeldusel, et protsessi väärtus sel hetkel on fikseeritud.

Markovi kett - erijuhtum Markovi protsess, kui selle olekute ruum on diskreetne (st mitte rohkem kui loendatav).

Mida see siis tähendab? Jämedalt öeldes modelleerime protsessi, kus süsteemi olek järgmisel ajahetkel sõltub ainult selle olekust praegusel hetkel, mitte aga ei sõltu kuidagi kõigist eelnevatest olekutest.

Kujutage ette, mis on teie ees aken, mis kuvab ainult süsteemi hetkeseisu (meie puhul on see üks sõna) ja peate määrama, milline on järgmine sõna, ainult selles aknas esitatud andmete põhjal. Meie korpuses järgivad sõnad üksteist järgmise mustri järgi:

Seega moodustuvad sõnapaarid (isegi lause lõpus on oma paar - tühi tähendus):

Rühmitame need paarid esimese sõna järgi. Näeme, et igal sõnal on oma lingid, mis meie lause kontekstis saab järgne talle:

Esitame selle teabe muul viisil - iga lingi jaoks määrame massiivi kõigist sõnadest, mis võivad pärast seda linki tekstis ilmuda:

Vaatame lähemalt. Näeme, et igal lingil on sõnad, mis saab tulge sellele lausega järele. Kui peaksime ülaltoodud diagrammi kellelegi teisele näitama, saaks see inimene suure tõenäosusega meie rekonstrueerida esialgne pakkumine, see tähendab keha.

Näide. Alustame sõnast "Alusta". Järgmisena valige sõna "Üks", kuna meie skeemi järgi on see ainus sõna, mis võib järgneda lause algusele. Sõna taga "Üks" samuti võib järgneda ainult üks sõna - "kala". Nüüd näeb uus ettepanek vahepealses versioonis välja selline "Üks kala". Edasi muutub olukord keerulisemaks - jaoks "kala" võib olla sõnu võrdse tõenäosusega 25% "kaks", "punane", "sinine" ja lause lõpp "Lõpp". Kui eeldame, et järgmine sõna on "kaks", rekonstrueerimine jätkub. Kuid me saame valida lingi "Lõpp". Sel juhul genereeritakse meie skeemi alusel juhuslikult lause, mis on korpusest väga erinev - "Üks kala".

Me lihtsalt simuleerisime Markovi protsess- tuvastas iga järgmise sõna ainult teadmiste põhjal praeguse sõna kohta. Materjali täielikuks mõistmiseks koostame diagrammid, mis näitavad meie korpuses olevate elementide vahelisi sõltuvusi. Ovaalid tähistavad linke. Nooled viivad potentsiaalsete linkideni, mis võivad ovaalis olevale sõnale järgneda. Iga noole kõrval on tõenäosus, millega järgmine link praeguse lingi järel ilmub:

Suurepärane! Oleme õppinud vajalikku teavet liikuda edasi ja analüüsida keerukamaid mudeleid.

Sõnavarabaasi laiendamine

Artikli selles osas koostame mudeli sama põhimõtte järgi nagu varem, kuid kirjelduses jätame mõned sammud välja. Kui teil on raskusi, pöörduge tagasi esimese ploki teooria juurde.

Võtame veel neli tsitaati samalt autorilt (ka inglise keeles, see ei tee meile haiget):

"Täna sina Kas sa oled. See on tõest tõesem. Pole elus kedagi, kes oleks sina - kui sina.

« Sul on ajud peas. Sul on jalad kingades. Saate end juhtida mis tahes valitud suunas. Sa oled omaette."

"Mida rohkem loed, seda rohkem asju saate teada." Mida rohkem õpid, seda rohkematesse kohtadesse sa lähed.

"Mõtle vasakule ja mõtleõige ja mõtle madalalt ja mõtle kõrgelt. Oh, mõtteid sa saad mõelge järele, kui ainult proovite."

Korpuse keerukus on suurenenud, kuid meie puhul on see ainult pluss - nüüd saab tekstigeneraator toota sisukamaid lauseid. Fakt on see, et igas keeles on sõnu, mis esinevad kõnes sagedamini kui teised (näiteks kasutame eessõna "in" palju sagedamini kui sõna "krüogeenne"). Kuidas rohkem sõnu meie korpuses (ja seega ka nendevahelistes sõltuvustes), seda rohkem on generaatoril infot selle kohta, milline sõna esineb tekstis kõige tõenäolisemalt pärast praegust sõna.

Lihtsaim viis seda selgitada programmi vaatenurgast. Teame, et iga lingi jaoks on sõnad, mis võivad sellele järgneda. Ja ka iga sõna iseloomustab selle esinemiste arv tekstis. Meil on vaja mingit viisi kogu selle teabe ühte kohta kogumiseks; Selleks sobib kõige paremini sõnaraamat, mis salvestab paare “(võti, väärtus)”. Sõnastikuvõti salvestab süsteemi hetkeseisu, st ühe keha lingi (näiteks "te" alloleval pildil); ja sõnastiku väärtusesse salvestatakse teine ​​sõnastik. Pesastatud sõnastikus on võtmeteks sõnad, mis võivad esineda tekstis pärast korpuse aktiivset linki ( "mõtleb" Ja "rohkem" võib tekstis järele minna "te") ja väärtused on nende sõnade esinemiste arv tekstis pärast meie linki (sõna "mõtleb" ilmub tekstis sõna järel "te" 1 kord, sõna "rohkem" pärast sõna "te"- 4 korda):

Lugege ülaltoodud lõik mitu korda uuesti läbi, et veenduda, et saate sellest täpselt aru. Pange tähele, et pesastatud sõnastik on sel juhul sama histogramm; see aitab meil jälgida linke ja nende tekstis esinemise sagedust võrreldes teiste sõnadega. Tuleb märkida, et isegi selline sõnavarabaas on tekstide õigeks genereerimiseks väga väike loomulik keel- see peaks sisaldama rohkem kui 20 000 sõna või veel parem, üle 100 000. Ja veel parem, rohkem kui 500 000. Aga vaatame sõnavarabaasi, mis meil on.

Markovi ahel on sel juhul konstrueeritud sarnaselt esimesele näitele - iga järgmine sõna valitakse ainult praeguse sõna teadmiste põhjal, kõiki teisi sõnu ei võeta arvesse. Kuid tänu sellele, et sõnaraamatus on salvestatud andmed selle kohta, millised sõnad ilmuvad teistest sagedamini, võime valimisel nõustuda teadlik otsus. Vaatame konkreetset näidet:

Veel:

See tähendab, kui praegune sõna on sõna "rohkem", pärast seda võivad olla sõnad võrdse tõenäosusega 25% "asjad" Ja "kohad", ja 50% tõenäosusega - sõna "see". Kuid tõenäosused võivad kõik olla võrdsed:

Mõtle:

Windowsiga töötamine

Siiani oleme akendega arvestanud vaid ühe sõna suurust. Saate akna suurust suurendada, nii et tekstigeneraator toodab rohkem "kontrollitud" lauseid. See tähendab, et mida suurem on aken, seda väiksemad on genereerimisel kerest kõrvalekalded. Akna suuruse suurendamine vastab Markovi ahela üleminekule rohkemale kõrge järjekord. Varem ehitasime esimest järku vooluringi; akna jaoks loob kaks sõna teist järku ahela, kolm kolmandat järku vooluringi ja nii edasi.

Aken- need on andmed praegune olek süsteemid, mida kasutatakse otsuste tegemiseks. Kui sobime suur aken ja väike kogum andmeid, siis suure tõenäosusega saame iga kord sama lause. Võtame sõnavarabaasi meie esimesest näitest ja laiendame akent suurusele 2:

Laiendus on tähendanud, et igal aknal on nüüd ainult üks võimalus süsteemi järgmise oleku jaoks – ükskõik, mida me teeme, saame alati sama lause, mis on identne meie juhtumiga. Seetõttu varustage akendega katsetamiseks ja tekstigeneraatori ainulaadse sisu tagastamiseks sõnavara baas alates 500 000 sõnast.

Rakendamine Pythonis

Diktogrammi andmestruktuur

Diktogramm (dict on Pythonis sisseehitatud sõnastiku andmetüüp) kuvab linkide vahelise seose ja nende esinemissageduse tekstis, st nende leviku. Kuid samal ajal on sellel sõnastiku omadus, mida me vajame – programmi täitmisaeg ei sõltu sisendandmete hulgast, mis tähendab, et loome tõhusa algoritmi.

Impordi juhuslik klass Diktogramm(dict): def __init__(self, iterable=None): # Initsialiseeri meie distributsioon uus objekt klass, # lisa olemasolevad elemendid super(diktogramm, ise).__init__() self.types = 0 # unikaalsete võtmete arv distributsioonis self.tokens = 0 # kõigi jaotuse sõnade koguarv, kui itereeritav: self.update( itereeritav) def update (self, iterable): # Värskenda jaotust olemasoleva # itereeritava andmekogumi elementidega iterable: if iter in self: self += 1 self.tokens += 1 else: self = 1 self. tüübid += 1 self.tokens += 1 def count(self, item): # Tagastab üksuse loenduri väärtuse või 0, kui üksus ise: return self return 0 def return_random_word(self): random_key = random.sample(self, 1) # Teine võimalus: # juhuslik .valik(histogramm.võtmed()) return random_key def return_weighted_random_word(self): # Genereeri pseudojuhuslik arv vahemikus 0 kuni (n-1), # kus n on sõnade koguarv random_int = random.randint(0, self.tokens-1 ) index = 0 list_of_keys = self.keys() # print "juhuslik indeks:", random_int for i in range(0, self.types): index += ise] # prindi indeks if(indeks > juhuslik_int): # prindi_võtmete_loend [i] return_of_keys[i]

Diktogrammi struktuuri konstruktorit saab edasi anda mis tahes objektist, mida saab itereerida. Selle objekti elementideks on sõnad diktogrammi lähtestamiseks, näiteks kõik sõnad raamatust. Sel juhul loendame elemente nii, et ühelegi neist juurde pääsemiseks ei pea me iga kord kogu andmestikku läbima.

Samuti tegime juhusliku sõna tagastamiseks kaks funktsiooni. Üks funktsioon valib sõnastikus juhusliku võtme ja teine, võttes arvesse iga sõna esinemiste arvu tekstis, tagastab meile vajaliku sõna.

Markovi ahela struktuur

histogrammidest import Diktogramm def make_markov_model(data): markov_model = dict() for i in range(0, len(data)-1): if data[i] in markov_model: # Lihtsalt lisa olemasolevale distributsioonile markov_model].update( ]) else: markovi_mudel] = Diktogramm() tagastab markovi_mudel

Ülaltoodud teostuses on meil sõnastik, mis salvestab aknad võtmena paaris „(võti, väärtus)” ja jaotused selle paari väärtustena.

N-ndat järku Markovi ahela struktuur

histogrammidest import Diktogramm def make_higher_order_markov_model(order, data): markov_model = dict() for i in range(0, len(data)-order): # Loo akna aken = korteež(andmed) # Lisa sõnaraamatusse if window in markov_model: # Lisa olemasolevale distributsioonile markov_model.update() else: markov_model = Dictogram() return markov_model

Väga sarnane esimese järjekorra Markovi ketiga, kuid sel juhul laos autokolonn võtmena sõnaraamatu paaris “(võti, väärtus)”. Kasutame seda loendi asemel, kuna korteež on muudatuste eest kaitstud ja see on meie jaoks oluline - lõppude lõpuks ei tohiks sõnaraamatu võtmed muutuda.

Mudeli parsimine

Suurepärane, oleme sõnastiku kasutusele võtnud. Aga kuidas saaksime luua sisu, mis põhineb praegusel olekul ja sammul järgmisse olekusse? Vaatame läbi oma mudeli:

Histogrammide import Diktogrammide import juhuslikult kogumitest import deque import re def gener_random_start(modell): # Mis tahes algussõna genereerimiseks tühjendage rida: # return random.choice(model.keys()) # "Õige" algussõna genereerimiseks , kasutage allolevat koodi: # Õige algussõnad- need on need, mis olid korpuse lausete alguseks, kui "END" mudelis: seed_word = "END" while seed_word == "END": seed_word = model["END"].return_weighted_random_word() return seed_word return juhuslik. valik(mudel .keys()) def genereeri_juhuslik_lause(pikkus, markovi_mudel): praegune_sõna = genereeri_juhuslik_algus(markovi_mudel) lause = i jaoks vahemikus(0, pikkus): praegune_diktogramm = markovi_mudel juhuslik_kaalutud_sõna = praegune_diktogramm.tagasi_kaalutud_juhuslik_sõna. (praegune_sõna) lause = lause.suurtäht() return " ".join(lause) + "." tagasilause

Mis järgmiseks?

Proovige välja mõelda, kus saate ise Markovi ahelatel põhinevat tekstigeneraatorit kasutada. Lihtsalt ärge unustage, et kõige olulisem on see, kuidas te mudelit sõelute ja millised eripiirangud genereerimisele seate. Selle artikli autor kasutas näiteks säutsu generaatorit luues suurt akent, piiras genereeritava sisu 140 tähemärgini ja kasutas lausete alustamiseks ainult “õigeid” sõnu, st neid, mis olid lausete alguseks. korpus.