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.

Ülesandes rakendame HMM-i Twitteri säutsude meeleolu tuvastamiseks. Sellisest tegevusest on huvitatud näiteks ettevõtted, kes tahavad teada kasutajate suhtumist oma toodetesse või teenustesse, sotsiaalsete uurimuste tegijad jne.

Meeleolu või hoiak on meie jaoks peidetud. Näeme aga, mida inimene on kirjutanud ning sõnade põhjal me juba oskame lühikesi tekste klassifitseerida. Markovi mudeli toome sisse eelneva sõnamudeli täpsustamiseks ja stabiliseerimiseks (treeningandmete põhjal on alati tõenäolisem, et inimese hoiak kahe säutsu vahel ei muutu, kui et ta muutub).

Loomuliku keele ja meeleolude analüüs on keeruline ülesanne ja kodutöös ei taha me saada väga suurt täpsust. Eesmärk on aru saada, kuidas peidetud Markovi mudel töötab.

Teooria ja praktika

Kõigepealt loe läbi [AIMA] 15.2.1 "Filtering and prediction", vajadusel mitu korda. Töös kasutame sellest Forward algoritmi.

Oletame, et meil on mingi vaatluste seeria e₁ kuni e_n. Lisaks, võtame kusagilt algsed sisemise olekute tõenäosused X₀.

Nüüd arvutatakse Forward algoritmiga X1 = forward(X0, e1). Saame X₁, millest saab jälle järgmise olekute jaotuse jne kuni lõpuni.

Meie Twitteri ülesande puhul on vaatlustulemusteks järjestikused säutsud. Iga säutsu juures arvutatakse eelmist ajahetke arvesse võttes uus sisemiste olekute tõenäosusjaotus. Tähistame võimalikke sisemisi olekuid positiivne ja negatiivne. Pane tähele, et Forward algoritm ühelgi hetkel ei vali, milline on "õige" peidetud olek. Läbi kogu tsükli peetakse arvet mõlema oleku tõenäosuse üle.

Forward algoritm

Forward algoritm arvutab korraga ühe sammu arvutuses, ajahetkest t kuni t+1.

Näide Klassid on lühidalt: p, n.

1. Sisemise oleku üleminek .

Eelmine sisemine olek (t): P(p) = 0.9, P(n) = 0.1
Oletame, et üleminekumudel on selline:
             uus olek
vana olek     p    n
   p          0.7  0.3
   n          0.2  0.8
Uus olek (t+1): P(p) = 0.7 * 0.9 + 0.2 * 0.1 = 0.65
                P(n) = 0.3 * 0.9 + 0.8 * 0.1 = 0.35

2. Vaatlustulemuste lisamine .

Säuts: "w1 w2 w3 w2"
Oletame, et meil on sõnade sageduse mudel (NB mudeli stiilis):
P(w1|p) = 0.1     P(w1|n) = 0.001
P(w2|p) = 0.02    P(w2|n) = 0.1
P(w3|p) = 0.05    P(w3|n) = 0.05

P(säuts|p) = P(w1|p) * P(w2|p) * P(w3|p) = 0.1 * 0.02 * 0.05 = 0.0001
P(säuts|n) = P(w1|n) * P(w2|n) * P(w3|n) = 0.001 * 0.1 * 0.05 = 0.000005

Sisemise oleku jaotus, arvestades säutsu sisu (t+1):
P(p) = 0.0001 * 0.65 = 0.000065   (* alpha)
P(n) = 0.000005 * 0.35 = 0.00000175   (* alpha)

3. Normaliseerime

Leiame tundmatu alpha, korrutame läbi. Lõplik jaotus (t+1):
P(p) = 0.97
P(n) = 0.03

Vajalikud tegevused

1. Leia üleminekute tõenäosused treeningandmetelt.
2. Treeni eelmise kodutöö Naiivne Bayesi mudel säutsudelt. Oluline on eelkõige sõnade esinemine mõlema klassi puhul, eeltõenäosust võib kasutada Forward algoritmi esimeses sammus, aga ei pea.
3. Implementeeri ülaltoodud kirjelduse järgi Forward algoritm, nii et see saaks sisendiks listi säutsudest ning suudaks anda sisemiste olekute (positiivne, negatiivne) jaotuse peale viimast sammu või ka peale iga sammu.

Treeningandmed

Treenimiseks leiad failid siit.

• users_5000.csv - väiksem fail 5000 kasutaja säutsudega
• users_50000.csv - suurem fail

Treenimiseks on parem rohkem andmeid kasutada, aga esimesteks katsetusteks võib väiksem fail mugavam olla.

Failid on CSV formaadis, ilma päiseta.

klass,ajatempel,kasutaja," säuts"

Kasutajad on anonümiseeritud. Klass on kas 0 - negatiivne või 4 - positiivne, mida võib tõlgendada meeleolu või hoiakuna.

Tõenäosusjaotuste P(sõna|klass) leidmiseks pead säutsud sõnadeks tükeldama ja samasugust loendamist kasutama nagu eelmises ülesandes. Täiendavalt on kasulik kirjavahemärke eemaldada. Võid eemaldada ka "@" märgiga algavad stringid.

Katsetamine

Kas nad on heas või halvas tujus? Leia vastus oma programmiga. Kasuta Forward algoritmi. Eeltõenäosusteks võid võtta P(positiivne) = 0.5 ja P(negatiivne) = 0.5 või leida nende jaotus treeningandmetelt.

Kasutaja A:

"@anon @anon thx 4 the laughs. I'm going to sleep. My head hurts & my scan is butt crack early. Have fun @anon "
"@anon doing good. Going to take pics of my sidekick in a little bit. She is going to prom today "
"@anon how are you feeling that both of your teams lost hahahahahaha...sorry "
"@anon lol looks like I'm just going to catch a regular season game NEXT YEAR "
"@anon I like that. I'm going to put that one in my notebook "
"@anon ok kidding about Dwight. He's cute but I really admire him as a bball player.  I love the game again "
"Wow once again home alone for the night...hmm now this is sad. I have no life. Nah I take that back, have time to spend w/ God "
"@anon just wanted to say hi "
"I'm sorry if I'm a downer but it's hard to not be emotional right now. I didn't want to see Monica pass so I stayed home... "
"@anon yeah yeah I know.....not really thrilled about that place sorry....that was my bad "

Kasutaja B:

"Going to search out areas we would like for our dream home to also home my home based business one day soon. "
"Have beautiful dreams all, I'm off to snuggle down with my beautiful babies as they are done with the outdoors. "
"@anon Cheeers to a dull day girl.. hoping for one here also. "
"@anon That sounds like an awesome day.  Have a terrific time. "
"Mmmm.. fresh nettle tea so yummy. "
"I'm wondering what to have for Breaky along with my iced nettle tea??!   Don't really feel hungry for anything else."
"@anon Oh I love this and have joined myself.. or maybe it was Kind Blog I joined.. I best make sure.   Peace to you lovely lady!"
"@anon Cool!  Thank you.. it's a beautiful flower now is it medicinal? "
"@anon Good morning hairy vegan rock loving guy!  No dreams that I remember but a lovely sleep non the less!  What did you dream?"
"@anon Sweet book!  I think.. lol  Sounds good anyway. "
"@anon I'm excited but offering someone a sound healing also sounds great.  I'm starting Reiki at the farmers market also! Here we go! "
"http://url - Full Moon Wild Rose Petal Rose Quartz honey, vinegar and infusion picked and co-created today.  Love!"

Kasutaja C:

"@anon @anon you guys are going to make me cry "
"@anon I AM NOT MEAN "
"@anon your not following me yet??? "
"@anon why do you have nothing to say?? huh huh "
"@anon i am not showing off you think so crude of me your so mean  you make me want to cry"
"@anon yeah i know i did that to my friends cats too "
"@anon thanks for biting me  hahaha"
"@anon how sad "
"@anon @anon hello swati chuby cheeks where are you people??!??!?!?!    "
"@anon but you scare me when you get mad "
"@anon i am not a goddess no more cause colin is not there to help me rule! "
"@anon happy ur back not happy chuby cheeks and i still fighting "
"@anon oh i am okay my dog just had a seizure "

Kasutaja D:

"i can't go to sleep "
"@anon thanx "
"...on his car system...crazy...i love random moments "
"no more puppy  i'm really sad"
"@anon it's a mini poodle my sis was going to get but she just told me some things came up and she's not getting it anymore "
"i'm all awake but no one else is "