Iti0210lab10

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
2. Arvutame, mis järgmine oleks peaks olema üleminekumudeli järgi . Tegu on jaotuse valemiga, et programmis seda arvutada, tuleb aru saada, et X_t+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
4. Normaliseerime. See tähendab, et tuleb leida eelmises valemis olev .

Algandmed

Üleminekumudel:

    H   C
 H  0.7 0.3
 C  0.3 0.7

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

    S   M   L
 H  0.1 0.4 0.5
 C  0.7 0.2 0.1

Eeltõenäosused

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.