Matematici speciale

Seminar 13

Mai 2017

ii

”Viitorul incepe astazi, nu maine.”

Papa Ioan Paul al II-lea

14Procese stocastice. Lanturi Markov.

Procese Poisson

Algoritmul PageRank:

Succesul extraordinar si dominatia motorului Google se datoreaza in prin-cipal algoritmului PageRank, care exploateaza structura link-urilor din wwwpentru a determina un indice de popularitate al fiecarei pagini, independent deinterogarea formulata de utilizator.

1

Documentele de pe web (paginile web) sunt identificate de aplicatiile softwareale motorului, numite roboti sau crawlere. Documentele sunt apoi indexate.Modulul de indexare extrage cuvintele cheie constituind asa numitul sac de cu-vinte. Un alt modul, numit query module (modulul de interogare), convertestecererea formulata de utilizator in limbaj natural, intr-un vector cerere, cu careconsulta indexul de continut si extrage paginile relevante cererii. Modulul deierarhizare ordoneaza aceste pagini in ordinea descrescatoare a popularitatii lor.PageRank-ul este un vector ale carui coordonate sunt coeficientii de popular-itate ai paginilor web identificate de crawler. Acest vector este distributia deechilibru a unui lant Markov definit pe graful web.

Sa definim mai precis lantul Markov ce sta la baza algoritmului PageRank.Fie 𝑊 = {1, 2, ...,𝑚}, multimea tuturor paginilor web, 𝐻 = (ℎ𝑖𝑗) matricea deconectivitate a lui 𝑊 , sau matricea hyperlink:

ℎ𝑖𝑗 =

{1, daca exista hyperlink in pagina 𝑖 catre pagina 𝑗

0, daca nu exista hyperlink in pagina 𝑖 catre pagina 𝑗

H este o matrice rara, adica cu foarte multe zerouri (in medie cu 3−10 elementenenule pe o linie). Suma elementelor de pe linia 𝑖 a matricii 𝐻 indica numarulde out-linkuri, adica numarul de linkuri din pagina 𝑖, catre alte pagini sau catreea insasi. Notam aceasta suma cu:

𝑟𝑖 =

𝑚∑𝑗=1

ℎ𝑖𝑗

si 𝑟𝑖 se numeste ordinul iesirilor din pagina. Suma elementelor de pe coloana𝑖 a matricii hyperlink indica numarul de in-linkuri ale paginii 𝑖, adica numarulde linkuri catre pagina 𝑖.

Larry Page si Serghei Brin au definit un mers aleator pe graful WEB, con-siderand ca un surfer ajuns in pagina 𝑖 alege cu aceeasi probabilitate oricare dinpaginile catre care aceasta are linkuri, prin urmare probabilitatea de a trece dinpagina 𝑖 in pagina 𝑗 este:

𝑃𝑖𝑗 =ℎ𝑖𝑗

𝑟𝑖=

{1𝑟𝑖, daca exista link in pagina 𝑖 catre pagina 𝑗

0, daca nu exista link in pagina 𝑖 catre pagina 𝑗

De exemplu daca:

𝐻 =

⎛⎜⎜⎜⎜⎜⎜⎝0 0 1 1 0 0 1 0 0 1

1 0 0 0 1 0 0 1 0 0

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

0 0 1 0 0 1 0 1 0 0

⎞⎟⎟⎟⎟⎟⎟⎠atunci ordinul de iesire din pagina 2 este 𝑟2 = 3 si deci probabilitatea de a

trece din pagina 2 in oricare din paginile {1, 2, ..., 10} este 𝑃2𝑗 =ℎ2𝑗

3 , adica cuaceeasi probabilitate de 1

3 un surfer poate trece din pagina 2 in pagina 1, 5 sau 8.Vom exemplifica constructia propusa de L. Page si S. Brin prin modelul simplu,de retea izolata, de pagini WEB (retea intranet), din figura ce va urma. Notam

2

cu 𝑃 = (𝑃𝑖𝑗) matricea probabilitatilor de tranzitie 𝑃𝑖𝑗 =ℎ𝑖𝑗

𝑟𝑖, 𝑖, 𝑗 = 1, 6. Se

observa din structura grafului de conectivitate ca paginile 2 si 6 sunt pagini cenu contin link-uri catre alte pagini. Acestea se numesc dangling pages. Deexemplu fisierele pdf, ps sau fisierele imagine sunt pagini dangling. Prinurmare liniile 2 si 6 din matricea de tranzitie au toate elementele nule si astfel𝑃 nu este o matrice stochastica, deci nu poate fi interpretata ca matricea detranzitie a unui lant Markov cu spatiul starilor 𝑆 = {1, 2, 3, 4, 5, 6}:

Pentru a remedia aceasta situatie, L. Page si S. Brin au propus ca vector deprobabilitate de tranzitie dintr-o pagina dangling 𝑖, distributia uniforma:

𝑃𝑖𝑗 =1

𝑚, ∀, 𝑗 = 1,𝑚.

Adica, in mod artificial se adauga link-uri dintr-o pagina dangling catre toatepaginile web sau echivalent, ajuns intr-o pagina dangling, un navigator poateapoi alege cu o probabilitate uniforma orice pagina din www. Astfel matriceastochastica 𝑄 obtinuta din matricea 𝑃 este:

iar graful asociat va fi:

Lantul Markov definit de matricea stochastica, 𝑄, nu este in general ire-ductibil (adica nu exista drum de link-uri intre orice doua pagini sau echivalent,

3

graful WEB nu este tare conex) si pot exista traiectorii periodice, adica surferulnavigand conform matricii de tranzitie 𝑄 ar putea fi prins ca intr-o capcana,intr-o miscare aleatoare ciclica. Din acest motiv, dar si pentru ca la un mo-ment dat si in realitate, orice surfer renunta sa navigheze urmand linkurile dinpagini, cei doi, L. Page ¸si S. Brin, au introdus ipoteza ca doar cu probabili-tatea 𝛼 ∈ (0, 1), surferul navigheaza conform matricii 𝑄 si cu probabilitateacomplementara, 1 − 𝛼, ignora hyperlink-urile si alege cu probabilitate uniformaoricare din paginile de pe web, introducand adresa URL in linia de comanda abrowser-ului. Probabilitatea 𝛼 se numeste factor de damping si in lucrarea ini-tiala a fondatorilor Google, 𝛼 era mentionat ca avand valoarea 0.85. Cu aceastamodificare matricea de tranzitie este:

𝐺 = 𝛼𝑄 + (1 − 𝛼)

⎛⎜⎜⎜⎜⎜⎜⎝1𝑚

1𝑚 . . . 1

𝑚

1𝑚

1𝑚 . . . 1

𝑚

. . . . . . . . . . . .

1𝑚

1𝑚 . . . 1

𝑚

⎞⎟⎟⎟⎟⎟⎟⎠Matricea 𝐺 se numeste matricea Google, iar matricea de elemente identice 1

𝑚 ,notata 𝐸, se numeste matricea de teleportare, deoarece surferul se teleporteazadin navigarea aleatoare urmand link-uri intr-o ”navigare artificiala”. Evidentca si matricea 𝐸 este o matrice stochastica pe linii, iar 𝐺 fiind o combinatieconvexa de astfel de doua matrici este o matrice stochastica. Mai mult:

𝐺𝑖𝑗 > 0, ∀ 𝑖, 𝑗 = 1,𝑚

si deci matricea Google este ireductibila si aperiodica. Se presupune ca matriceaGoogle este cea mai ”uriasa” matrice cu care se lucreaza in vreo aplicatie la oraactuala.

Lantul Markov avand spatiul starilor constituit din:∙ multimea paginilor web la un moment dat, de cardinal 𝑚,∙ matricea de tranzitie de tipul 𝐺, cu 𝛼 fixat∙ distributia initiala de probabilitate 𝑝(0) (distributia uniforma, de exemplu)

este un lant ireductibil si aperiodic, deci are o unica distributie de echilibru 𝑣,numita vectorul PageRank. PageRank–ul 𝑣 este este limita sirului 𝑝(𝑛), cu𝑝(𝑛) = 𝑝(0)𝐺𝑛. Limita este aceeasi indiferent de distributia initiala de proba-bilitate 𝑝(0) adica indiferent cu ce probabilitate surferul alege pagina din careincepe navigarea. 𝑝(𝑗) se numeste PageRank-ul paginii 𝑗 si reprezinta sansaasimptotica pe care o are pagina 𝑗 de a fi vizitata de navigatorul aleator sauproportia din timpul de navigare pe care surferul ar petrece-o vizitand pagina𝑗. Deci 𝑝(𝑗) este un indice de popularitate al paginii. Cand un utilizatorintroduce cuvinte cheie in bara de cautare, motorul Google cauta paginile cecontin cuvintele cheie si le afiseaza in ordinea descrescatoare a PageRank-uluilor. Remarcam ca PageRank-ul unei pagini este independent de interogareaformulata de utilizator. Ea depinde doar de structura grafului WEB si se poatecalcula offline. PageRank-ul se calculeaza la intervale regulate de timp. Panain 2008 se calcula lunar, dar acum se actualizeaza la intervale mai scurte detimp. Vectorul Pagerank se calculeaza numeric, folsind asa numita metoda aputerii, adica se calculeaza recursiv, pornind de la 𝑝(0) si 𝐺, distributiile (sauPageRankul la 𝑛 pasi de navigare) 𝑝(𝑛) = 𝑝(𝑛− 1)𝐺. Se considera ca metoda

4

a atins stadiul de convergenta (adica s-a ajuns la echilibru) intr-o etapa 𝑛, incare ‖𝑝(𝑛) − 𝑝(𝑛− 1)‖ < 𝜀, unde 𝜀 este un numar pozitiv foarte mic, prescris.

S-a demonstrat ca viteza de convergenta a metodei puterii este aceeasi curata de convergenta a lui 𝛼𝑛, unde 𝛼 este factorul de damping. Implicatiiasupra PageRankului. Din punctul de vedere al vitezei de convergenta ar fipreferabil un factor 𝛼 cat mai apropiat de zero. In acest caz insa tinand seamaca matricea Google este 𝐺 = 𝛼𝑄 + (1 − 𝛼)𝐸, ar rezulta ca se acorda o pondereredusa 𝛼 navigarii conform linkurilor din graful WEB (cu modificarea pentrupagini dangling) si o pondere mai mare navigarii artificiale, conform matricei deteleportare 𝐸. Cu alte cuvinte in acest caz PageRank–ul asociat nu ar reflectapopularitatea reala a paginilor web. De aceea o valoare rezonabila, asa cuma fost ea aleasa init ial de Larry Page si Serghei Brin, 𝛼 = 0.85, conducela rezultate mai apropiate de realitate si la o viteza de convergenta suficientde buna (un reprezentant Google a declarat ca metoda puterii converge dupa100 − 200 de iteratii). Daca vreti sa aflati Pagerankul unor pagini WEB intratiaici:

Pentru o ierarhizare personalizata a paginilor web, matricea de teleportare𝐸, se calculeaza luand in considerare vectorul personalizat 𝑤, ce este un vectorprobabilist ale carui coordonate 𝑤 = (𝑎1, 𝑎2, ...𝑎𝑚), reprezinta probabilitatea casurferul, ce iese din navigarea conform linkurilor, sa aleaga pagina 1, 2, ...,𝑚, dinweb. Cu alte cuvinte el nu alege o pagina in mod uniform, ci are anumite prefer-inte, identificate de motor in decursul timpului. Astfel matricea de teleportareva fi 𝐸 = 𝑒𝑤 , unde 𝑒 = (1, 1, ..., 1)𝑡 , si matricea Google, corespunzatoare:

𝐺 = 𝛼𝑄 + (1 − 𝛼)𝑒𝑤

iar distributia de echilibru corespunzatoare este Pagerank-ul personalizat.

5

Notiuni teoretice:

Notiuni utile: proces stocastic, stare esentiala, stare tranzienta, stare aperi-odica, perioada unei stari esentiale, lant Markov ireductibil

Lanturi Markov finite

∙ evolutia in timp a unui sistem (𝑋𝑘)𝑘≥0 reprezinta un lant Markov finitdaca:

=⇒ starile posibile ale sistemului apartin unei multimi numita multimeastarilor:

𝑆 = {𝑠1, 𝑠2, . . . 𝑠𝑛}.

=⇒ starea viitoare a sistemului depinde doar de starea prezenta nu si destarile trecute:

𝑃 (𝑋𝑘+1 = 𝑠𝑘+1|𝑋𝑘 = 𝑠𝑘, 𝑋𝑘−1 = 𝑠𝑘−1, . . . , 𝑋0 = 𝑠0) = 𝑃 (𝑋𝑘+1 = 𝑠𝑘+1|𝑋𝑘 = 𝑠𝑘)

pentru niste stari 𝑠0, 𝑠1, . . . , 𝑠𝑘+1 din 𝑆.

Interpretare intuitiva: viitorul depinde doar de prezent, trecutul nu con-teaza !

Lanturi Markov omogene

Vom lucra cu lanturi Markov omogene, aceasta insemnand ca matricea 𝑃 aprobabilitatilor de trecere nu depinde de 𝑘 si astfel:

𝑃 =

⎛⎜⎜⎜⎝𝑃11 𝑃12 . . . 𝑃1𝑛

...... . . .

...

𝑃𝑛1 𝑃𝑛2 . . . 𝑃𝑛𝑛

⎞⎟⎟⎟⎠unde 𝑃𝑖𝑗 := 𝑃 (𝑋𝑘+1 = 𝑗|𝑋𝑘 = 𝑖).

∙ probabilitatea ca sistemul sa se afle in starea 𝑖 dupa 𝑘 pasi (unitati detimp) se noteaza:

𝑝𝑖(𝑘) = 𝑃 (𝑋𝑘 = 𝑖)

uneori vom folosi notatia:

𝑝𝑠𝑖(𝑘) = 𝑃 (𝑋𝑘 = 𝑠𝑖)

aceasta insemnand ca avem urmatoarea distributie pentru variabilele aleatoare𝑋𝑘:

𝑋𝑘 :

⎛⎝ 𝑠1 𝑠2 . . . 𝑠𝑛

𝑝1(𝑘) 𝑝2(𝑘) . . . 𝑝𝑛(𝑘)

⎞⎠ , 𝑘 ≥ 0.

∙ are loc relatia Chapman-Kolmogorov intre vectorii de probabilitate simatricea de tranzitie:

6

𝑝𝑖(𝑘) =

𝑛∑𝑗=1

𝑝𝑗(𝑘 − 1) · 𝑃𝑗𝑖

sau scrisa vectorial:

𝑝(𝑘) = 𝑝(𝑘 − 1) · 𝑃

∙ probabilitatea ca lantul sa evolueze pe traiectoria 𝑠0, 𝑠1, 𝑠2, ..., 𝑠𝑘 ∈ 𝑆 este:

𝑃 (𝑋0 = 𝑠0, 𝑋1 = 𝑠1, 𝑋2 = 𝑠2, . . . , 𝑋𝑘 = 𝑠𝑘) = 𝑝𝑠0(0) · 𝑃𝑠0𝑠1𝑃𝑠1𝑠2 . . . 𝑃𝑠𝑘−1𝑠𝑘

∙ daca un lant Markov omogen are vectorul initial de stare (distributiainitiala de probabilitate):

𝑝(0) = (𝑝𝑠1(0), 𝑝𝑠2(0), . . . , 𝑝𝑠𝑛(0))

si matricea de tranzitie 𝑃, atunci probabilitatile corespunzatoare starilor saledupa 𝑛 unitati de timp sunt date de:

𝑝(𝑛) = 𝑝(0) · 𝑃𝑛

∙ pentru a calcula 𝑃𝑛 putem utiliza transformata 𝑍 si anume:

𝑃𝑛 = 𝑍−1{𝑧(𝑧𝐼 − 𝑃 )−1

}(𝑛), 𝑧 ∈ C

Lanturi Markov absorbante

∙ stare absorbanta: o stare 𝑖 este absorbanta daca 𝑃𝑖𝑖 = 1Un lant Markov este un lant Markov absorbant daca lantul are cel putin o

stare absorbanta si este posibil sa ajungem din orice stare neabsorbanta intr-ostare absorbanta.

∙ fie 𝑃 matricea de tranzitie a unui lant Markov absorbant, rearanjand liniilesi coloanele astfel ca starile absorbante se fie primele matricea 𝑃 se poate scriesub forma:

𝑃 =

⎛⎝𝐼 0

𝑅 𝑄

⎞⎠∙ matricea fundamentala este definita prin 𝐹 = (𝐼 −𝑄)−1 si se poate arata

ca:

𝑃𝑛 →

⎛⎝ 𝐼 0

𝐹𝑅 0

⎞⎠ , 𝑛 → ∞

∙ matricea 𝐹𝑅 este matricea probabilitatilor ca plecand dintr-o stare initialneabsorbanta sistemul sa ajunga intr-o stare absorbanta.

Lanturi Markov regulate

Un lant Markov este un lant Markov regulat daca matricea sa de tranzitieeste regulata i.e. o putere a acesteia are toate elementele strict pozitive.

7

∙ pentru un lant Markov regulat exista un unic vector de stare 𝑣 astfel capentru orice vector initial de stare 𝑣0 :

𝑣0𝑃𝑛 → 𝑣, 𝑛 → ∞

∙ vectorul 𝑣 se numeste distributia de echilibru si furnizeaza trend-ul petermen lung al lantului Markov

∙ vectorul 𝑣 = (𝑣1, 𝑣2, . . . , 𝑣𝑛) se poate afla folosind identitatile:

𝑣𝑃 = 𝑣

si𝑣1 + 𝑣2 + . . . + 𝑣𝑛 = 1.

∙ un lant Markov finit este aperiodic si ireductibil daca si numai daca esteregulat.

8

Probleme rezolvate

Problema 1. Un grup de soareci se afla intr-o cusca care are trei com-partimente conectate intre ele A, B si C. Soarecii din compartimentul Ase muta in compartimentul B cu o probabilitate 0.3 si in C cu o probabili-tate 0.4. Cei din compartimentul B se muta in A sau C cu probabilitatile0.2 si 0.25, respectiv. Usa compartimentului C nu poate fi deschisa dininterior. Aflati probabilitatea cu care un soarece din compartimentul Ava ajunge in cele din urma blocat in compartimentul C.

Solutie: Matricea de tranzitie, asociata lantului Markov cu ajutorul caruiamodelam matematic problema, este:

𝑃 =

𝐴 𝐵 𝐶

𝐴

𝐵

𝐶

⎛⎜⎜⎜⎝0.3 0.3 0.4

0.2 0.55 0.25

0 0 1

⎞⎟⎟⎟⎠Se observa ca starea C este o stare absorbanta, 𝑃𝐶𝐶 = 1. Conform teoriei

lanturilor Markov absorbante daca reanranjam matricea de tranzitie sub forma:

𝑃 =

𝐶 𝐴 𝐵

𝐶

𝐴

𝐵

⎛⎜⎜⎜⎝1 0 0

0.4 0.3 0.3

0.25 0.2 0.55

⎞⎟⎟⎟⎠obtinem 𝑅 =

⎛⎝ 0.4

0.25

⎞⎠ si 𝑄 =

⎛⎝0.3 0.3

0.2 0.55

⎞⎠Prin calcul matricea fundamentala este 𝐹 ≈

⎛⎝1.76 1.17

0.78 2.74

⎞⎠ si matricea prob-

abilitatilor de a ajunge in starea absorbanta C este 𝐹𝑅 ≈

⎛⎝0.99

0.99

⎞⎠Asadar un soarece din compartimentul A are o sansa 99% sa ajunga blocat

in compartimentul C. (rezultat identic pentru un soarece din compartimentulB)

9

Probleme propuse

Problema 1. Desenati graful de tranzitie corespunzator matricei de tranzitie:

𝑃 =

⎛⎜⎜⎜⎝0.5 0.3 0.2

0 1 0

0.2 0.2 0.6

⎞⎟⎟⎟⎠si reciproc alcatuiti matricea de tranzitie corespunzatoare grafului orientat:

Problema 2. Un computer poate opera in doua moduri diferite. La fiecareora el ramane in acelasi mod sau comuta la modul al doilea conform matriceiprobabilitatilor de tranzitie:

𝑃 =

⎛⎝0.4 0.6

0.6 0.4

⎞⎠Daca computerul este in modul 1 la ora 5 : 30 pm, care este probabilitatea sa fiein acelasi mod la ora 7 : 30 pm in aceeasi zi ?

Problema 3. La sfarsitul lui iunie 40% dintre votanti sunt inregistrati ca fiindliberali, 45% ca si conservatori si 15% independenti. Peste o luna liberalii si-aupastrat 80% conservatori iar 5% s-au declarat independenti. Conservatorii si-aupastrat 70% dintre votanti si au pierdut 30% in favoarea liberalilor. Independen-tii au pastrat 60% dintre votanti si au pierdut 20% in favoarea liberalilor si aconservatorilor. Presupunem ca aceste trenduri vor continua.

a. Scrieti o matrice de tranzitie folosind aceste informatii.b. Aflati procentajul fiecarui tip de votanti la finalul lui august.c. Daca ar avea loc alegeri in octombrie 2018 care partid va avea cele mai

multe sanse sa castige alegerile ?

10

Problema 4. Un analist a pietei este interesat daca consumatorii prefera com-puterele Dell sau pe cele HP. Doua studii de piata, realizate in decursul unuian, au scos la iveala urmatoarele fenomene: 10% dintre detinatorii de computereDell au schimbat si au optat pentru unul HP in timp ce restul nu au avut motivesa renunte la computerele lor Dell. 35% dintre cei care detineau un computerHP au optat pentru unul Dell iar restul si-au pastrat computerele HP. Aflatidistributia pietei pentru o perioada lunga de timp.

Problema 5. Probabilitatile de tranzitie pentru un lant Markov sunt caracter-izate prin matricea de tranzitie

𝑃 =

⎛⎝ 25

35

110

910

⎞⎠ .

Calculati atunci 𝜋1000 daca 𝜋0 =

⎛⎝ −5 1

12

12

⎞⎠.

Problema 6. Notam prin 𝑆 = {𝐼, 𝑃, 𝑍,𝐵} multimea starilor vremii, undeInnorat, Ploios, Zapada si Buna. Presupunem ca avem o matrice a probabil-itatilor de tranzitie intre aceste stari dupa cum urmeaza:

𝑃 =

⎛⎜⎜⎜⎜⎜⎜⎝0.35 0.25 0.15 0.25

0.35 0.35 0.20 0.10

0.35 0.15 0.45 0.05

0.34 0.05 0.01 0.60

⎞⎟⎟⎟⎟⎟⎟⎠Daca luni vremea este buna care este predictia meteo pentru miercuri? (adica

sansele sa fie innorat, ploios, zapada sau vreme buna). Aflati probabilitatea camarti sa ploua, miercuri sa fie innorat si joi sa ploua din nou.

Problema 7. Simplificam problema anterioara presupunand doar trei stari alevremii Innorata, Ploiosa si Buna cu matricea de tranzitie:

𝑃 =

⎛⎜⎜⎜⎝0.5 0.2 0.3

0.4 0.4 0.2

0.3 0.3 0.4

⎞⎟⎟⎟⎠Daca luni este ploios cum va fi vremea de Craciun ?

11