să scriem împreună un generator de text markov (iv)
sâmbătă, 26 ian. 2013, 12:40
Am stabilit în cadrul părții a treia a seriei că urmează să construim un generator de text Markov format din două componente:
- O componentă care primește la intrare un model statistic, adică un lanț Markov, și întoarce un text generat aleator. Aceasta a constituit subiectul celei de-a doua părți a tutorial-ului.
- O componentă care primește la intrare unul sau mai multe texte într-o limbă oarecare și construiește pe baza lui, respectiv a lor, lanțul Markov necesar generării de text. În cele ce urmează vom implementa această a doua parte, care este de fapt prima parte a algoritmului în totalitatea sa.
Am observat de asemenea că problema construirii unui model pentru generarea propozițiilor într-o limbă oarecare este teoretic intractabilă. Pe de o parte un „corpus al limbii” complet ar putea fi constituit doar din totalitatea textelor și cuvintelor scrise în limba respectivă. Pe de altă parte limba este o unealtă flexibilă, cu reguli și excepții care pot fi încălcate în diverse contexte, și a cărei formalizare este un subiect de cercetare intens la ora actuală în știința lingvisticii. (mai mult…)
să scriem împreună un generator de text markov (iii)
vineri, 4 ian. 2013, 23:44
Până acum am povestit despre lanțuri Markov și am găsit un model computațional de reprezentare a acestora, după care am construit pe baza modelului un program care parcurge pseudo-aleator lanțul și întoarce stările parcurse. Am arătat că stările pot diferi de la un apel la altul și că valoarea stării următoare depinde de distribuția de probabilitate formată de stările succesoare. Din fericire generatoarele de numere pseudo-aleatoare din calculatoarele de zi cu zi sunt suficient de bune încât să asigure încadrarea cu o anumită eroare (suficient de mică) în distribuția fiecărei stări.
O abordare mai serioasă a lanțurilor Markov ar presupune parcurgerea unor subiecte destul de aride precum procesele stochastice și distribuțiile de probabilitate. Din nefericire noi nu avem loc aici să intrăm în astfel de subiecte, motiv pentru care abordarea folosită în continuare va fi una așa-zis „intuitivă”, sau mai degrabă o bâjbâială empirică având rolul de a familiariza cititorul cu problema lanțurilor Markov și a generării de text pe baza lor. (mai mult…)
să scriem împreună un generator de text markov (ii)
joi, 27 dec. 2012, 11:32
În cadrul articolului introductiv am prezentat pe scurt ideea de a implementa un generator de text Markov ca exercițiu pur didactic, am explicat câteva din conceptele teoretice fundamentale pe care se constituie aplicația și nu în ultimul rând am definit o structură de date în Haskell, structură care se mapează unu la unu pe cea a unui lanț Markov. Mai departe voi da un exemplu de construcție (non-algoritmică) a unui obiect de tipul Chain, după care vom porni spre a programa un simulator de procese Markov, definit printr-o interfață oarecare, fixă, interfață care la rândul ei se constituie pe baza unor funcții Haskell.
O primă și importantă funcționalitate a acestei interfețe o reprezintă aceea de construire a lanțurilor Markov. Modulul Data.Map oferă tot soiul de modalități de construire a dicționarelor, printre care inserarea, reuniunea etc. Dat fiind că în programarea funcțională cea mai naturală metodă de a reprezenta chestii este lista, noi vom defini o funcție fromList, care se va folosi de omoloaga din Data.Map pentru a construi lanțuri Markov din asocieri stare-listă (de tupluri stare-probabilitate):
fromList :: Ord a => [(a, [(a, Float)])] -> Chain a fromList = M.fromList |
să scriem împreună un generator de text markov (i)
sâmbătă, 15 dec. 2012, 15:29
Invit cititorul de Cărămizi să ia parte la o inițiativă
- (a) destul de rar întâlnită pe blog-urile românești,
- (b) pur didactică,
- (c) destinată programatorilor amatori, profesioniști sau pur și simplu oamenilor cărora le place să-și folosească chestia aia dintre umeri, și nu în ultimul rând
- (d) aparent inutilă.
De fapt punctul (d) e în mare parte fals; stând un pic și cugetând, realizez că ar fi foarte util să urmăriți tutorialul dacă doriți de exemplu să învățați Haskell sau să vă faceți o idee legată de analiză statistică și lanțuri Markov, sau pur și simplu dacă vreți să vă dezvoltați un generator de spam [i]. (mai mult…)
- Nu văd care-i problema. Scopul meu e acela de a le arăta oamenilor cum să folosească cuțitul, nu să le explic cum ar putea să-l vâre în alți indivizi. [↩]
să scriem împreună un simulator de automate celulare (iii)
duminică, 18 nov. 2012, 14:56
Am pus până acum bazele unui simulator de automate celulare și apoi am ajuns la o implementare funcțională conform unor specificații. Pe scurt, am obținut o mașinărie capabilă de a primi la intrare un șir de celule „goale” sau „umplute” (fiecare), prelucrându-l inductiv și obținând la fiecare pas de inducție un alt șir de celule cu aceleași proprietăți. Zisa mașinărie nu prelucrează celulele arbitrar, ci pe baza unui set de reguli care iau în calcul valoarea celulei și a vecinilor direcți, stabiliți după ordinea din șir. Putem privi șirul de șiruri rezultat fie ca pe o secvență de evenimente, fie ca pe un „covor” care are pe prima linie primul șir de celule, pe a doua șirul următor și așa mai departe.
Uneltele folosite până acum ne-au permis să vizualizăm datele doar în cel de-al doilea mod. Exemplele relevă astfel șabloane fractale precum cel al triunghiului Sierpinski, imagini regulate sau care se autoreglează „în jos”, sau dimpotrivă, reprezentări profund neregulate [i] care aduc a „randomness”. Acest al doilea mod de vizualizare oferă deci o privire sintetică asupra evoluției unui automat celular elementar oarecare.
Putem însă la fel de bine să folosim Haskell și unele din bibliotecile grafice avute la dispoziție pentru a vizualiza rezultatele în primul mod. Având la dispoziție o listă de stări, deci o listă de liste de celule, putem afișa o stare sub forma unui cadru într-o animație, extinzând astfel evoluția pe axa timpului. Propun astfel ca o celulă să fie afișată sub forma unui „petic” de 20 x 20 pixeli dintr-o imagine, după cum urmează: o celulă având valoarea E va fi reprezentată printr-un pătrat alb, în timp ce o celulă F va avea asociat un pătrat umplut cu negru. „Peticele” care formează o stare vor fi concatenate de la stânga la dreapta într-o imagine/cadru cu înălțimea 20 și lățimea 20 x lungimea șirului. (mai mult…)
- Studiul regularității automatelor celulare elementare plecând de la stări inițiale aleatoare a dus la împărțirea acestora în patru clase distincte. E demn de menționat și faptul că regularitatea de un anumit fel și interacțiunea între celule fac ca anumite automate celulare să fie echivalente computațional cu o mașină Turing. [↩]