Post on 03-Feb-2018
transcript
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