Iti0210lab10

Allikas: Lambda

Peidetud Markovi mudel

Sissejuhatus

Peidetud Markovi mudel (hidden Markov model, HMM) esitab mingit ajas muutuvat nähtust, mis käitub nagu Markovi ahel. Seejuures ei ole see nähtus meile otseselt vaadeldav, vaid me näeme ainult mingit kaudset tunnust. Vt. Wikipedia näide.

sotsiaalvõrk

Ülesandes rakendame HMM-i sotsiaalvõrgu suhetele. Sõbraseosed sotsiaalvõrgus moodustavad graafi. Staatilisel kujul annab see graaf mingi ettekujutuse inimestevahelistest seostest, aga sõbraseoseid võib olla ka inimeste vahel, kes ei ole kunagi suhelnud ega kohtunud. Täpsema ettekujutuse suhetest saame, kui me jälgime ka sõnumite liikumist mööda graafi kaari ajas.

Võtame aluseks lähenemise, kus suhted sotsiaalvõrgus liigitatakse kolme faasi: avastamine, edaspidi tähistatud E(xploration), ülalhoidmine M(aintenance) ja unustamine F(orgetting) [1]. Kui leiame graafil kaared, mis on avastamise või ülalhoidmise faasis, siis see võiks anda meile inimese praeguse ja lähituleviku sõpruskonna.

Lähtume oletusest, et sõnumite arv ajaühikus on tingitud suhte faasist. Selle abil ehitame peidetud Markovi mudeli ning leiame Forward-algoritmiga praeguse oleku. Tegu on mänguülesandega, päris sotsiaalvõrgu andmeid ei kasutata.

Forward algoritm

Kõigepealt loe läbi [AIMA] 15.2.1 "Filtering and prediction", vajadusel mitu korda. Kokkuvõtlikult:

  1. Meil on mingi tõenäosusjaotus sisemisele olekule Iti0210lab10 f1.png. Tahame leida tõenäosusjaotust järgmisel ajahetkel t+1, kui me teame välist tunnust et+1 (antud juhul on selleks sõnumite sagedus).
  2. Arvutame, mis üleminekumudel järmiseks olekuks annaks Iti0210lab10 f2.png. Tegu on jaotuse valemiga, et programmis seda arvutada, tuleb aru saada, et Xt+1 on muutuja ning selle asemele tuleb kordamööda panna kõik tema võimalikud väärtused.
  3. Kasutades emissioonimudelit, täpsustame sisemise oleku hinnangut Iti0210lab10 f3.png. et+1 on välise tunnuse konkreetne väärtus.
  4. Normaliseerime. See tähendab, et nüüd on õige hetk leida eelmises valemis olev Iti0210lab10 f4.png. Näiteks, kui eelmises sammus arvutame numbrid <0.13, 0.21, 0.04>, siis need tuleks mingi arvuga läbi korrutada, et saada jaotus mille summa on 1. Seda arvu on üsna lihtne leida: 1 / (0.13 + 0.21 + 0.04). Saame lõpliku jaotuse <0.34, 0.56, 0.1>.

Alguses on meil vaatlustulemuste seeria, aga sisemiste olekute jaotuseid pole. Võtame appi eeltõenäosuse (prior) ja väidame, et see on jaotus vahetult enne vaatlustulemuste seeriat. See on küll väga umbkaudne, aga esiteks pole midagi paremat võtta, teiseks mõjutab esimene jaotus sisemist olekut seeria lõpus palju vähem, kui seeria alguses. Meid huvitab just seeria lõpp ehk värskeim olek.

Eeltõenäosuse ja esimese vaatlustulemuse pealt saame ülaltoodud sammudega arvutada esimese sisemise oleku jaotuse. Selle võtame aluseks järgmisele olekule jne, kuni jõuame iteratiivselt vaatlustulemuste seeria lõppu.

Algandmed

Sõnumid sotsiaalvõrgus on eri tüüpi (näiteks postitus, "like" jne), kahesuunalised, lisaks on inimese kaupa individuaalne, kui palju sõnumeid on "palju" või "vähe". Ülesandes eeldame, et iga graafi kaare kohta on sõnumite arv antud lihtsustatud kategooriatena: palju - H(igh), vähe - L(ow) või üldse mitte - N(one). Selline ühele skaalale viimine on tegelikult üsna praktiline, kui meil on üks tõenäosusmudel kogu võrgu kohta.

Vaatame sõnumite arvu kolmel sotsiaalgraafi kaarel (kasutajad Alice, Bob ja Carol) 12 nädala jooksul:

 A<->B  L N N L H N N N N N N H                                                  
 B<->C  N H L L L N L N L N N L                                                  
 C<->A  H L H N N L H N L L L N                                                  

Üleminekumudel faaside vahel. Tabelit tuleb lugeda nii: kui praegune olek on Explorationt, siis järgmise oleku tõenäosused on vastavalt P(Explorationt+1|Explorationt) = 0.6, P(Maintenancet+1|Explorationt) = 0.2 ja P(Forgettingt+1|Explorationt) = 0.2.

    E    M    F
 E  0.6  0.2  0.2
 M  0.01 0.8  0.19
 F  0.01 0.09 0.9

Emissioonimudel (sõnumite sageduse tõenäosusjaotus, kui seose olek on antud):

    N    L    H
 E  0.1  0.5  0.4
 M  0.3  0.4  0.3
 F  0.8  0.19 0.01

Eeltõenäosuseid ei ole antud. Seega võta eeltõenäosuseks iga oleku puhul 1/3.

Lahendus

Kirjuta programm, mis võtab sisendiks sõnumite sageduse seeria kahe kasutaja vahel. Programm peaks kasutama Forward algoritmi ning arvutama sisendseeria järgi kõige viimase sisemise oleku tõenäosusjaotuse. Programmi võib kirjutada ükskõik mis keeles.

Kui meil on tõenäosusjaotus olemas, siis selle pealt on lihtne leida kõige tõenäolisemat graafi kaare praegust olekut. Leia, millised kolmest sõbraseosest Alice, Bobi ja Caroli vahel on hetkel aktiivsed, ehk ei ole unustamise faasis.

Oodatavad tulemused (lõplik jaotus):

         X=E    X=M    X=F
 A<->B:  0.08   0.75   0.17
 B<->C:  0.02   0.29   0.68
 C<->A:  0.01   0.4    0.59

Viited

  1. Yang, Z., Xue, J., Wilson, C., Zhao, B.Y. and Dai, Y. (2015) Uncovering User Interaction Dynamics in Online Social Networks. Proceedings of the 9th International Association for the Advancement of Artificial Intelligence (AAAI) Conference on Web and Social Media, Oxford, 26-29 May 2015, 698-701.