Iti0210lab10: erinevus redaktsioonide vahel

Allikas: Lambda
Mine navigeerimisribale Mine otsikasti
← Vanem muudatus
PriitJ (arutelu | kaastöö)
1416 muudatust
PriitJ (arutelu | kaastöö)
1416 muudatust
 
(ei näidata sama kasutaja 10 vahepealset redaktsiooni)
6. rida: 6. rida:
[https://en.wikipedia.org/wiki/Hidden_Markov_model#A_concrete_example Wikipedia näide].
[https://en.wikipedia.org/wiki/Hidden_Markov_model#A_concrete_example Wikipedia näide].


[[Image:Iti0210lab10_sn.png|150px|right|sotsiaalvõrk]]
Ü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.


Ü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.
Meeleolu või hoiak on meie jaoks peidetud. Näeme aga, mida inimene on kirjutanud ning sõnade põhjal me juba oskame [[Iti0210lab91|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).


Võtame aluseks lähenemise, kus suhted sotsiaalvõrgus liigitatakse kolme faasi: avastamine, edaspidi tähistatud <code>E(xploration)</code>, ülalhoidmine <code>M(aintenance)</code> ja unustamine <code>F(orgetting)</code> [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.
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.


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.
== Teooria ja praktika ==


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


Kõigepealt loe läbi [''AIMA''] 15.2.1 "Filtering and prediction", vajadusel mitu korda. Kokkuvõtlikult:
Oletame, et meil on mingi vaatluste seeria e<sub>1</sub> kuni e<sub>n</sub>. Lisaks, võtame kusagilt algsed sisemise olekute tõenäosused X<sub>0</sub>.


# Meil on mingi tõenäosusjaotus sisemisele olekule [[Image:Iti0210lab10_f1.png]]. Tahame leida tõenäosusjaotust järgmisel ajahetkel ''t+1'', kui me teame välist tunnust ''e<sub>t+1</sub>'' (antud juhul on selleks sõnumite sagedus).
Nüüd arvutatakse ''Forward'' algoritmiga <code>X1 = forward(X0, e1)</code>. Saame X<sub>1</sub>, millest saab jälle järgmise olekute jaotuse jne kuni lõpuni.  
# Arvutame, mis üleminekumudel järmiseks olekuks annaks [[Image:Iti0210lab10_f2.png]]. Tegu on jaotuse valemiga, et programmis seda arvutada, tuleb aru saada, et ''X<sub>t+1</sub>'' on muutuja ning selle asemele tuleb kordamööda panna kõik tema võimalikud väärtused.
# Kasutades emissioonimudelit, täpsustame sisemise oleku hinnangut [[Image:Iti0210lab10_f3.png]]. ''e<sub>t+1</sub>'' on välise tunnuse konkreetne väärtus.
# Normaliseerime. See tähendab, et nüüd on õige hetk leida eelmises valemis olev [[Image: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.
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.


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.
===''Forward'' algoritm ===


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


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 - <code>H(igh)</code>, vähe - <code>L(ow)</code> või üldse mitte - <code>N(one)</code>. Selline ühele skaalale viimine on tegelikult üsna praktiline, kui meil on üks tõenäosusmudel kogu võrgu kohta.
'''Näide''' Klassid on lühidalt: ''p'', ''n''.


Vaatame sõnumite arvu kolmel sotsiaalgraafi kaarel (kasutajad Alice, Bob ja Carol) 12 nädala jooksul:
1. Sisemise oleku üleminek [[Image:Iti0210_hmm2.gif]].
<pre>
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
</pre>
2. Vaatlustulemuste lisamine [[Image:Iti0210_hmm3.gif]].
<pre>
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)
</pre>
3. Normaliseerime
<pre>
Leiame tundmatu alpha, korrutame läbi. Lõplik jaotus (t+1):
P(p) = 0.97
P(n) = 0.03
</pre>
 
=== Vajalikud tegevused ===
 
# Leia üleminekute tõenäosused treeningandmetelt.
# 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.
# 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.


  A<->B  L N N L H N N N N N N H                                                 
== Treeningandmed ==
  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 ''Exploration<sub>t</sub>'', siis järgmise oleku tõenäosused on vastavalt ''P(Exploration<sub>t+1</sub>|Exploration<sub>t</sub>) = 0.6'', ''P(Maintenance<sub>t+1</sub>|Exploration<sub>t</sub>) = 0.2'' ja ''P(Forgetting<sub>t+1</sub>|Exploration<sub>t</sub>) = 0.2''.
Treenimiseks [http://dijkstra.cs.ttu.ee/~priit/Iti0210_lab101.zip leiad failid siit].


    E    M    F
* <code>users_5000.csv</code> - väiksem fail 5000 kasutaja säutsudega
  E  0.6  0.2  0.2
* <code>users_50000.csv</code> - suurem fail
  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):
Treenimiseks on parem rohkem andmeid kasutada, aga esimesteks katsetusteks võib väiksem fail mugavam olla.
 
Failid on CSV formaadis, ilma päiseta.
 
<pre>
klass,ajatempel,kasutaja," säuts"
</pre>


    N    L    H
Kasutajad on anonümiseeritud. Klass on kas <code>0</code> - negatiivne või <code>4</code> - positiivne, mida võib tõlgendada meeleolu või hoiakuna.
  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.
Tõenäosusjaotuste ''P(sõna|klass)'' leidmiseks pead säutsud sõnadeks tükeldama ja samasugust loendamist kasutama nagu [[Iti0210lab91|eelmises ülesandes]]. Täiendavalt on kasulik kirjavahemärke eemaldada. Võid eemaldada ka "@" märgiga algavad stringid.


== Katsetamine ==
== Katsetamine ==
86. rida: 119. rida:
"@anon Sweet book!  I think.. lol  Sounds good anyway. "
"@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! "
"@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://twitpic.com/6v4u4 - Full Moon Wild Rose Petal Rose Quartz honey, vinegar and infusion picked and co-created today.  Love!"
"http://url - Full Moon Wild Rose Petal Rose Quartz honey, vinegar and infusion picked and co-created today.  Love!"
</pre>
</pre>


Viimane redaktsioon: 11. aprill 2019, kell 16:31

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 e1 kuni en. Lisaks, võtame kusagilt algsed sisemise olekute tõenäosused X0.

Nüüd arvutatakse Forward algoritmiga X1 = forward(X0, e1). Saame X1, 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 "
Pärit leheküljelt "http://www.lambda.ee/w/index.php?title=Iti0210lab10&oldid=15778"